A Caltech Library Service

The Pursuit For 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 (2008) The Pursuit For Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Valiant-Vazirani showed in 1985 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 on 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, under randomized reductions. This is in strong contrast to the case of constant gapped 1-D Hamiltonians, which is in NP. 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 which allows the calculation of expectation values efficiently. Finally, we discuss a few obstacles towards establishing 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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Additional Information: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.
Funding AgencyGrant Number
Engineering and Physical Sciences Research Council (EPSRC)GR/S82176/0
IST directorate 015848
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:30 Jul 2018 15:27

Repository Staff Only: item control page