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

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

2008-10-27

arxiv.org/abs/0810.4840v1

Physics

Quantum Physics

26 pages, 5 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Pursuit For Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Pursuit For Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Pursuit For Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-324318