Dave Bacon

STOC Conference 2015 Conference Paper

Sparse Quantum Codes from Quantum Circuits

• Dave Bacon
• Steven T. Flammia
• Aram W. Harrow
• Jonathan Shi

SODA Conference 2007 Conference Paper

The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits

• Dave Bacon
• Isaac L. Chuang
• Aram W. Harrow

FOCS Conference 2005 Conference Paper

From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups

• Dave Bacon
• Andrew M. Childs
• Wim van Dam

We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form /spl Zopf//sub p/ /sup r/ /spl times/ /spl Zopf//sub p/ fixed r (including the Heisenberg group, r = 2). In particular our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.