Advanced Search  Browse by Discipline  Scientific Societies
E-print Alerts  Add E-prints  E-print Network    Advanced Search
   A Full Characterization of Quantum Advice Scott Aaronson
Summary: A Full Characterization of Quantum Advice Scott
Aaronson  Andrew Drucker  We prove the following surprising
result: given any quan- tum state 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 on all quantum circuits of fixed polynomial size. In
terms of complexity classes, this implies that BQP/qpoly
QMA/poly, which supersedes the previous result of Aaronson that
BQP/qpoly PP/poly. Indeed, we can exactly charac- terize quantum
advice, as equivalent in power to untrusted quantum advice
combined with trusted classical advice. Proving our main result
requires combining a large num- ber of previous tools--including
a result of Alon et al. on     Collections: Physics; Computer
Technologies and Information Scie