pdf files of
Programme Booklet >>
and
Abstracts of all Talks >>

You will receive a hard copy of these files at the registration desk.

Sponsors

Pauli Center for Theoretical Studies

The Swiss National Science Foundation

ETH Zurich (Computer Science and Physics Department)

Quantum Science and Technology

CQT Singapore

QAP European Project

Sandia National Laboratories

Institute for Quantum Computing

id Quantique

A full characterization of quantum advice

Scott Aaronson, MIT

joint work with Andrew Drucker

We prove the following surprising result: 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 quantum circuits of fixed polynomial size.  In complexity terms, this implies that BQP/qpoly is contained in QMA/poly, which supersedes the previous result that BQP/qpoly is contained in PP/poly and refutes a conjecture made by Aaronson in 2004.  Indeed, we can exactly characterize quantum advice, as equivalent in power to untrusted quantum advice combined with trusted classical advice.

One implication of our result is that it is possible to send both a quantum state rho and a polynomially-larger classical string x through a one-way communication channel, in such a way that the recipient can use x to verify (in polynomial time) that rho still produces the measurement outcomes that the sender intended on every small circuit.  Another implication is a quantum analogue of the famous Karp-Lipton Theorem: if NP-complete problems are efficiently solvable by quantum computers with quantum advice, then Pi2P is contained in QMA^PromiseQMA.

Proving our main result requires combining a large number of previous tools and also creating some new ones.  In particular, we need a result of Aaronson on the learnability of quantum states, a result of Aharonov and Regev on "QMA₊ super-verifiers," and a result of Alon et al. on fat-shattering dimension of concept classes.

The main new tool is a so-called Majority-Certificates Lemma, which has already found some independent applications in complexity theory.  In its simplest version, this lemma says the following.  Given any set S of Boolean functions on n variables, any function f in S can be expressed as the pointwise majority of m=O(n) other functions in S---f(x)=MAJ(f1(x),...,fm(x))---such that each fi is the unique function in S compatible with O(log|S|) input/output constraints.