QMA-complete problems for stoquastic Hamiltonians and Markov matrices

Abstract

We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is QMA-complete. We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation using certain excited states of a stoquastic Hamiltonian is universal. We also show that adiabatic evolution in the ground state of a stochastic frustration free Hamiltonian is universal. Our results give a new QMA-complete problem arising in the classical setting of Markov chains, and new adiabatically universal Hamiltonians that arise in many physical systems.

11 pages. Contains several new results not present in version 1.

References in corpus (7)

• Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
• N-representability is QMA-complete
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Quantum NP - A Survey
• Merlin-Arthur Games and Stoquastic Complexity
• Quantum Computation Beyond the Circuit Model
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems

Cited by in corpus (25)

• Adiabatic Quantum Computing
• Perspectives of quantum annealing: Methods and implementations
• Hamiltonian complexity
• Quantum Hamiltonian Complexity
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Biology and medicine in the landscape of quantum advantages
• Easing the Monte Carlo sign problem
• Accuracy and Resource Estimations for Quantum Chemistry on a Near-term Quantum Computer
• Demonstration of nonstoquastic Hamiltonian in coupled superconducting flux qubits
• Exponential quantum speedup in simulating coupled classical oscillators
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
• Fibonacci anyons versus Majorana fermions
• Measures of quantum computing speedup
• Approximation algorithms for QMA-complete problems
• Monte Carlo simulation of stoquastic Hamiltonians
• Complexity classification of local Hamiltonian problems
• The Complexity of Translationally Invariant Problems beyond Ground State Energies
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• A distribution testing oracle separation between QMA and QCMA
• Pinned QMA: The power of fixing a few qubits in proofs
• Excited-State Adiabatic Quantum Computation Started with Vacuum States
• Quantum Eigenvalue Estimation for Irreducible Non-negative Matrices
• Optimization of ARQ Protocols in Interference Networks with QoS Constraints