A Caltech Library Service

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

Aharonov, Dorit and Ben-Or, Michael and Brandão, Fernando G. S. L. and Sattath, Or (2022) The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings. Quantum, 6 . Art. No. 668. ISSN 2521-327X. doi:10.22331/q-2022-03-17-668.

[img] PDF (11 Mar 2022) - Published Version
Creative Commons Attribution.

[img] PDF (27 Oct 2008) - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Alternate Title:The Pursuit For Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
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.
Funding AgencyGrant Number
Engineering and Physical Sciences Research Council (EPSRC)GR/S82176/0
IST Directorate015848
Record Number:CaltechAUTHORS:20160527-123057985
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67457
Deposited By: Joy Painter
Deposited On:27 May 2016 19:44
Last Modified:18 Apr 2022 20:27

Repository Staff Only: item control page