[QIP-Sem] QIP seminar, Mon 3/16, 4:15, 36-428, Aaronson,Scott

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 3/16 at 4:15 in 36-428
-------------------------------------------------

 Aaronson,Scott (MIT)

The Power of Quantum Advice

Abstract:

I'll describe a powerful new result about quantum advice: namely, given any state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that *any* ground state of H can be used to simulate rho on all circuits of a fixed polynomial size.  In terms of complexity classes, this implies that BQP/qpoly is contained in QMA/poly, superseding the previous result that BQP/qpoly is contained in PP/poly.  Indeed, we can exactly characterize the /qpoly operator, as equivalent in power to *untrusted* quantum advice combined with trusted *classical* advice. The proof of this theorem relies on my previous result about the learnability of quantum states, as well as a new combinatorial result called the "majority-certificates lemma" that might be of independent interest.            Joint work with Andrew Drucker.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem