2008/10/31 by Dorit Aharonov, Michael Ben-Or, Fernando G. S. L. Brandão +2 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics #Discrete mathematics #Ground state #Hamiltonian (control theory) #Mathematical analysis #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum many-body systems #Quantum mechanics #Uniqueness #cs.CC #quant-ph
paper · pdf · doi:10.22331/q-2022-03-17-668
published as Quantum 6, 668 (2022) · 26 pages, 5 figures
openalex created_date 2016/06/24 · arxiv created 2022/03/11 · openalex publication_date 2022/03/17 · arxiv updated 2022/03/23 · openalex updated_date 2026/08/05
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.