[QIP-Sem] QIP seminar, Tue 1/20, 4:15, 36-428, Sattath,Or
Peter Shor
shor at math.mit.edu
Fri Jan 16 07:32:17 EST 2009
MIT Quantum Information Processing seminar
Tuesday 1/20 at 4:15 in 36-428
-------------------------------------------------
Sattath,Or ()
The Pursuit For Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
Abstract:
In 1985, Valiant-Vazirani showed [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) [AN02].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, 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 [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 loc
al Hamiltonian which allows the efficient calculation of expectation values.Finally, we conjecture that an analogous result to the class Quantum Merlin-Arthur(QMA) is impossible. This is formulated by separating between the two relavant classes, QMA and its "unique" version UQMA, using the definition by Aaronson and Kuperberg [AK06] of quantum oracles.
-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem
More information about the QIP-Sem
mailing list