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.
- Log in to post comments
Wow! I'm *very* excited by the title of the Schuch-Verstraete talk!
Dave, if you happen to hear the mathematical terms "Grassmannian" or "Plucker embedding" or "Kälerian" during this talk ... then please try to figure out "what the hey" is being talked about.
Because, as Enrico Fermi famously said: "For me, there are two kinds of mathematical articles: the ones where I don't understand the first page, and the ones where I don't understand the first sentence." :)
What on earth is that a photo of?
Um... what's that in the picture?
Breakfast.
I see cheese on top of a tortilla and I'm sure green chile is involved. Beyond that, I don't think it really matters...
Regarding the Schuch-Verstraete presentation, there's an even more recent PRL that covers much the same material:
@article{Schuch et al, Author = {Schuch, Norbert and Cirac, Ignacio and Verstraete, Frank}, Title = {Computational difficulty of finding matrix product ground states},Journal = {Physical Review Letters}, Year = {2008}, Volume = {100}, Number = {25}, Pages = {250501}}
This is outstanding work!
My present (exceedingly non-rigorous) understanding is that these results are compatible with quantum simulation having a complexity structure that is broadly reminiscent of the Spielman-Teng analysis of the simplex algorithm.
Namely, the simplex algorithm is (rigorously) polynomial only for smoothed classes of problems ... problems whose result is insensitive to small perturbations of the input.
Similarly, quantum simulation is (heuristically) polynomial only for smoothed classes of outputs ... namely, outputs that are insensitive to small perturbations of the simulation parameters (e.g., parametric and thermal noise).
An example of an non-smooth simulation output would be a ground-state wave-function of a spin-glass (which could be altered by changing just one bond, for example). An example of a smooth simulation output would be the finite-temperature heat capacity of the system (which heuristically is insensitive to changes in individual bonds), or the systems glass-phase transition temperature.
Of course, we are a long way from proving this rigorously (which does not obstruct us from using it heuristically). Here again there is (seemingly) a parallel with simplex optimization methods.
Dave, were there any audience questions about applying the methods of smoothed analysis to these systems? More broadly, what kinds of questions *were* asked?
Say ... I found the QIP schedule on-line, and it turns out that the above Schuch-Cirac-Verstraete work ("The computational difficulty of finding MPS ground states") will be presented at 3:00 pm on the final QIP day (Thursday). Good!
Oh to have the opportunity to sniff the air the Sidles breathes for even a few short months.
David says: "Oh to sniff the air the Sidles breathes ..."
A trade secret that works for me is a trick that jazz musicians call "circular breathing" ... the idea being to breath in succession from the literature of pure math, physics, applied math, engineering, and finally medicine.
Then begin the cycle again ... with air that is never stale.
The great Rahsaan Roland Kirk was a master of this remarkable art ...perhaps the Google video "Rahsaan Roland Kirk plays 3 saxes + flute at once" will inspire quantum information scientists to work along similar lines! :)
In the impish hope of filling the QIP lecture hall with the sound of Rahsaan Roland Kirk playing 3 saxes + flute, here is a jazz critic's commentary that begins at minute 2:05 (and there is a dubbed English voice-over to go with it) ....
Un camion qui passe, est-il musique? Pourquoi est-ce si difficile pour tellement de gens d'ecouter? Pourquoi se mettent-ils a parler lorsqu'ils devraient entendre? N'ont-ils pas les oreilles sur les deuz cotes de la tete, mais don la bouche, ce qui les incite a parler au moindre son qu'ils entendent? Cela devrait etre plus anormal, ne croyez-vous pas?
The jazz critic's questions are oddly apt for quantum information theory too! :)
Heh. Circular breathing was a revelation in my saxophone playing as a kid. I was fortunate to have friend whose brother was a pro, and willing to spend time with us talking technique.
I just hope that when I have climbed on the mountain as long as you have, I will have made it as high.