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

New evidence that quantum mechanics is hard to simulate on classical computers

Scott Aaronson, MIT

joint work with Alex Arkhipov

I'll discuss new types of evidence that quantum mechanics is intractable to simulate classically -- evidence that is more complexity-theoretic in character than (say) Shor's factoring algorithm, and that also corresponds to experiments that seem much easier than building a universal quantum computer. Specifically:

(1) I'll discuss recent oracle evidence that BQP has capabilities outside the polynomial hierarchy---namely, that there exists a black-box relational problem in BQP but not in BPP^PH, and that a decision problem separating BQP from PH (that is, an oracle relative to which BQP is not in PH) would follow from the "Generalized Linial-Nisan Conjecture."  The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Mark Braverman, after being open for 20 years. (Preprint at arXiv:0910.4698)

(2) I'll show that, using only nonadaptive linear optics, one can generate probability distributions that can't be efficiently sampled by a classical computer, unless P^#P = BPP^NP and hence the polynomial hierarchy collapses.  I'll also discuss an extension of this result to samplers that only approximate the photon distribution in variation distance. The extension relies on an unproved conjecture in classical complexity theory: namely, that approximating the permanent of a matrix of i.i.d. Gaussians is a random-self-reducible #P-complete problem.

 

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 | 2 January 2010
top