I got a complaint yesterday from Iordanis Kerenidis: I forgot to tell the Internet that he actually made people laugh during his (fabulous) talk about the power of unique quantum witness.

RT @qudit How many computer scientists does it take to connect a laptop to a projector? Latest count, 7. #qip

Span Programs and quantum algorithms

Ben Reichardt

Ben spoke about span programs (which is something totally new for me) and how they relate to the general adversary method for quantum query algorithms. He also gave the recipe for finding optimal quantum query algorithms (for Boolean functions).

Conjecture : when the adversary bound and the general adversary bound are equal, there is an optimal span program.
Partial answer: span programs are (almost) equivalent to quantum query algorithms for Boolean functions (up to a log/(log log) factor hat may even not be needed)
Open question: what is the lower of element distinctness (in the quantum case)?
Open question: how to extend the span programs framework beyond Boolean functions ?
Open question: what is the relation between time complexity and span programs?

Non-commutative compressed sensing: theory and applications for quantum tomography

David Gross, Yi-Kai Liu, Steve Flammia, Steven Becker, Jens Eisert and Vincent Nesme — arXiv:0909.3304, arXiv:0910.1879 and arXiv:10012738

«I will cite a Nobel Laureate: "Yes, we can!” »

Using matrix completion (reconstruct low rank matrix from a few randomly chosen matrix elements [Tao09]) the authors are able to prove
Theorem: Knowing rd log d randomly chosen Pauli expecation values, one can recover any rank-r density matrix.

He started by quoting a Nobel laureate, but he used results from Fields medalists and “The Chairman” aka Andreas Winter.

An efficient algorithm for finding Matrix Product ground states

Norbert Schuch, J. Ignacio Cirac, Dorit Aharonov, Itai Arad, and Sandy Irani — arXiv:0910.5055 and arXiv:0910.4264

Not attending to.

The query complexity of Hamiltonian simulation and unitary implementation

Dominic W. Berry and Andrew M. Childs — arXiv:0910.4157

Goal: simulation of a NxN Hamiltonian using a black box that outputs matrix elements.

For the first time since the beginning of QIP I’m feeling lost. The simulation is a quantum walk of O(√N) steps (grover-like search. Is that related to [ManiezNayakRolandSantha07]?) and in order to perform one step you need to call the oracle (how many times per step?) I have the feeling that this talk was design for people who already knew this kind of stuff and wanted to know the new refinements in that domain.

Simulating quantum computers with probabilistic methods

Maarten Van den Nest — arXiv:0911.1624

I just saw the ugliest picture of the conference…