Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR10-191 | 9th December 2010 23:54

#### Symmetry-assisted adversaries for quantum state generation

TR10-191
Authors: Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland
Publication: 10th December 2010 01:46
We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum state generation might be a route to tackle the {\sc Graph Isomorphism} problem. We show that for the related problem of {\sc Index Erasure} our method leads to a lower bound of $\Omega(\sqrt N)$ which matches an upper bound obtained via reduction to quantum search on $N$ elements. This closes an open problem first raised by Shi [FOCS'02].