New bridges between Computer Science and Quantum Computation

Invited perspective talk: Umesh Vazirani

It’s a talk on relationship between theoretic computer science, quantum computer science and quantum physics.
« Computer scientists spend their lives trying to avoid to use continuous variables »
Old question still not answered: How powerful is BQP? Scott Aaronson’s conjecture: Fourier checking is in BQP, but not in PH. (see Scott’s blog post to understand the relation between theoretical CS and quantum CS)
QIP = IP = PSPACE (solved in the framework of SDP. Hey that’s from classical CS too! More on that later)
Now the other side: classical problems solved with quantum technics.
Lattice based cryptography: Post quantum crypto: classical crytpo systems that are resistant to quantum attacks.
Is there a quantum PCP theorem?
D-wave bashing, but most importantly he’s explaining the work of Broadbent, Fitzsimons and Kashefi on blind computing: can we check if a computer is an actual quantum computer without opening it?

The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems

Daniel Gottesman and Sandy Irani — arXiv:0905.2419

QMA_{EXP} is QMA but with exponential size witnesses and checking circuits.
Theorem: 2-LOCAL-HAMILTONIANS in 1D is QMA_{EXP}-complete when the Hamiltonians involve translation-invariant nearest-neighbor interactions.

On the power of a unique quantum witness

Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang — arXiv:0906.4425

Why are NP-complete problems hard? Because they are too many witnesses? No. (Valiant-Vazirani work on Unique-SAT: if there is an efficient algorithm for unique-SAT, then there is an efficient algorithm for SAT)
Why are QMA-complete problems hard? FewQMA is not harder than Unique-QMA. Next goal: proving the QMA is no harder than Unique-QMA.

A full characterization of quantum advice

Scott Aaronson and Andrew Drucker

Motivating question: How much useful computational work can you “store” in a quantum state for later retrieval? Result: BQP/qpoly = YQP/poly
Trusted quantum advice is equivalent in power to trusted classical advice combined with untrusted quantum advice. (“Quantum states never need to be trusted”)

You can find an other version of Scott’s slides on his webpage.

Last slide of Scott. “Please, if you can explain what squeezed states, parametric down-conversion and homodyne measurements mean to a computer scientist, please talk to me”. I never wrote parametric down-conversion in my papers…