The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings

Abstract

Valiant-Vazirani showed in 1985 [VV85] that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions). We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur MA and Quantum-Classical-Merlin-Arthur QCMA. Our results have implications for the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation (to within polynomial accuracy) of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard [AN02], under randomized reductions. This is in stark contrast to the case of constant gapped 1-D Hamiltonians, which is in NP [Has07]. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian that allows efficient calculation of expectation values. Finally, we discuss a few of the obstacles to the establishment of an analogous result to the class Quantum-Merlin-Arthur (QMA). In particular, we show that random projections fail to provide a polynomial gap between two witnesses.

26 pages, 5 figures

References in corpus (18)

• Entanglement renormalization
• An Area Law for One Dimensional Quantum Systems
• Undecidability of the Spectral Gap (short version)
• The power of quantum systems on a line
• Quantum Hamiltonian Complexity
• Quantum NP - A Survey
• Rigorous RG algorithms and area laws for low energy eigenstates in 1D
• Ground state approximation for strongly interacting systems in arbitrary dimension
• The computational difficulty of finding MPS ground states
• Undecidability of the Spectral Gap in One Dimension
• Several natural BQP-Complete problems
• Renormalization algorithm with graph enhancement
• The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
• Importance of the spectral gap in estimating ground-state energies
• On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
• The complexity of simulating local measurements on quantum systems
• Quantum Merlin Arthur with Exponentially Small Gap
• History-state Hamiltonians are critical

Cited by in corpus (13)

• Quantum Proofs
• On the complexity of quantum partition functions
• The Quantum PCP Conjecture
• The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
• Importance of the spectral gap in estimating ground-state energies
• General conditions for universality of Quantum Hamiltonians
• The complexity of simulating local measurements on quantum systems
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
• Quantum search-to-decision reductions and the state synthesis problem
• Approximation, Proof Systems, and Correlations in a Quantum World
• Total Functions in QMA
• On physical problems that are slightly more difficult than QMA
• Quantum Merlin-Arthur proof systems for synthesizing quantum states