A half day at QIP.
The reason I’m having a hard time keeping away this morning:
Avinatan Hassidim, “Multi-prover interactive proofs with communicating provers”
Paper arXiv:0806.3982. Avinatan described work he performed with Michael Ben-Or and Haran Pilpel on multiprover interactive proofs in which the prover/verifier communication is quantum and the provers are allowed to communicate classically. One would expect, at first glance, that this model is very weak. For example if we augment the provers with entanglement they can then communicate and this model is equivalent to a single prover interactive proof: in this case the languages with such interactive proofs would be contained in EXP (exponential time deterministic algorithms). If, on the other hand the verifier were classical, then this would be a single prover classical interactive proof: in this case the languages with such interactive proofs is PSPACE. However, Avinatan descried in this talk how these interactive proofs (quantum communication between provers/verifiers and classical communication between provers) can be used to recognize any language in NEXP.
Andris Ambainis, “Quantum algorithms are at most polynomially faster than classical for any symmetric function”
Andris discussed the power (or lack thereof) of quantum algorithms in querying functions which are symmetric. Paper: arXiv:0902.xxxx. Andris showed that for symmetric functions the quantum query is at most the the 11th root of the classical query complexity.
Jean-Pierre Tillich, Quantum tornado codes
Tornado codes are not related to Kansas, but are instead classical error correcting codes with some nice properties (fast decoding/encoding near optimal codes.) In this talk Jean-Pierre discussed his work on quantum tornado codes. This resolves some the problems on quantum turbo codes and quantum LDPC codes.
Norbert Schuch and Frank Verstraete, “Interacting electrons, density functional theory, and quantum Merlin-Arthur”
Paper here: arXiv:0712.0483. The problem: N electrons in an external position dependent potential, find the ground state energy. Density functional theory is a very widely used way to find ground state energies. An important quantity which is needed in order to make the density functional theory work is called the “universal functional”. The results of this paper show that if there was efficient description of this functional, then QMA would equal NP.