Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 17, 2022 | Published + Submitted
Journal Article Open

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

Abstract

Valiant-Vazirani showed in 1985 [45] 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 [7]. 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 polynomialinverse 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, under randomized reductions. This is in stark contrast to the case of constant gapped 1-D Hamiltonians, which is in NP [24]. 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.

Additional Information

© 2022 The Author(s). Published under CC-BY 4.0. Published: 2022-03-17. We wish to thank the anonymous reviewers for their suggestions and careful editing. This work is part of the QIP-IRC supported by EPSRC (GR/S82176/0) as well as the Integrated Project Qubit Applications (QAP) supported by the IST directorate as Contract Number 015848' and was supported by an EPSRC Postdoctoral Fellowship for Theoretical Physics. Most of this work was done while O.S. was at the Hebrew University, and F.G.S.L.B. was at the Imperial College London.

Attached Files

Published - q-2022-03-17-668.pdf

Submitted - 0810.4840v1.pdf

Files

0810.4840v1.pdf
Files (1.4 MB)
Name Size Download all
md5:0a9655566d863751a8920f687d00736a
299.1 kB Preview Download
md5:d132df612a8811e341227ee14ad07d12
1.1 MB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 18, 2023