13/01/2006, 15:00 — 16:00 — Sala P4.35, Pavilhão de Matemática
Scott Aaronson, U Waterloo
Quantum Versus Classical Proofs And Advice
Quantum computing skeptics have claimed that any theory involving exponentially-long vectors is inherently unreasonable. But if someone hands you a quantum state, is that really like being handed an exponential amount of classical information? I will describe recent results suggesting that the answer, at least for complexity-theoretic purposes, is "no". These results include simulations of quantum advice using classical advice, and a conditional "dequantization" of John Watrous' quantum proof protocol for the Group Non-Membership problem. Based partly on joint work with Greg Kuperberg.
![Hiperligação para a sessão link](/img/link.png)
Apoiado por: Phys-Info (IT), SQIG (IT), CeFEMA e CAMGSD, com financiamento de FCT, FEDER and EU FP7, especificamente via o Doctoral Programme in the Physics and Mathematics of Information (DP-PMI), os projectos estratégicos FCT PEst-OE/EEI/LA0008/2013 e UID/EEA/50008/2013, o projecto IT QuSim, o projecto CRUP-CPU CQVibes, a Acção de Coordenação FP7 QUTE-EUROPE (600788) e os projectos FP7 Landauer (GA 318287) e PAPETS (323901).
![Instituto de Telecomunicações Instituto de Telecomunicações](/seminars/qci/img/it.png)
![CAMGSD](/img/logo_CAMGSD_new.svg)
![FCT](/img/2017_FCT_H_cor.svg)
![7th Framework Programme](/img/7thFP_small_trans.png)