printlogo
http://www.ethz.ch/index_EN
International Workshop on Quantum Information Processing
 
print
  

QIP 2010 at

ETH Life

The daily web-journal of ETH Zurich:

"Lifting the big veil"

"Nach dem grossen Schleier lüften"

18.01.2010

QIP 2010 at the

Swiss Radio DRS

Echo der Zeit

from Monday Jan 18, 2010

in German, Link >>

(Real Player recommended)

chocolate


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

pauliohne


The Swiss National Science Foundation

snflogo


ETH Zurich (Computer Science and Physics Department)

ethlogo


Quantum Science and Technology

qsitmitschrift


CQT Singapore

cqtlogo


QAP European Project

qaplogo3


Sandia National Laboratories

sandia


Institute for Quantum Computing

finaliqc


id Quantique

3rdideequantique

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.

 

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.
More information

© 2013 ETH Zürich | Imprint | Disclaimer | 5 January 2010
top