[QIP-Sem] QIP seminar, Mon 5/16, 4:00, 36-428, Martin Roetteler

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 5/16 at 4:00 in 36-428
-------------------------------------------------

Martin Roetteler (NEC Laboratories America)

Quantum state generation: adversaries, algorithms, applications

Abstract:

We introduce a new quantum adversary method to prove lower bounds on the query complexity of quantum state generation problems. This encompasses both, the computation of partial or total functions and the preparation of target quantum states. There had been hope for quite some time that quantum state generation might be a route to tackle the Graph Isomorphism problem. We show that for the related Index Erasure problem our method leads to tight lower bound on the query complexity, showing that a simple reduction to quantum search is optimal. This closes an open problem first raised by Shi [FOCS'02]. Our approach is based on (i) a generalization of the additive and multiplicative adversary methods and (ii) a representation-theoretic way to exploit symmetries of the underlying problem. We construct adversary matrices from the Bose-Mesner algebra of an association scheme that is defined implicitly by the Index Erasure problem.  On the algorithmic side, we present a new technique 
 to tackle quantum state generation which can be thought of as a quantum analog of the classical rejection sampling method (von Neumann, 1951). We analyze the running time of our algorithm using semidefinite programming. As an application, we derive a new quantum algorithm for the hidden shift problem for an arbitrary Boolean function whose running time is obtained by "water-filling" its Fourier spectrum.  Joint work with Andris Ambainis, Loick Magnin, Maris Ozols, and Jeremie Roland and based on arXiv:1103.3017 and arXiv:1103.2774.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem