%0 Journal Article
%D 2005
%T From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
%A Dave Bacon
%A Andrew M. Childs
%A Wim van Dam
%X 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 (Z_p)^r X| Z_p for 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.
%8 2005/04/11
%G eng
%U http://arxiv.org/abs/quant-ph/0504083v2
%! Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005)
%R 10.1109/SFCS.2005.38
%0 Journal Article
%D 2005
%T Optimal measurements for the dihedral hidden subgroup problem
%A Dave Bacon
%A Andrew M. Childs
%A Wim van Dam
%X We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.
%8 2005/01/10
%G eng
%U http://arxiv.org/abs/quant-ph/0501044v2
%! Chicago Journal of Theoretical Computer Science (2006)
%0 Journal Article
%J Physical Review A
%D 2001
%T Universal simulation of Markovian quantum dynamics
%A Dave Bacon
%A Andrew M. Childs
%A Isaac L. Chuang
%A Julia Kempe
%A Debbie W. Leung
%A Xinlan Zhou
%X Although the conditions for performing arbitrary unitary operations to simulate the dynamics of a closed quantum system are well understood, the same is not true of the more general class of quantum operations (also known as superoperators) corresponding to the dynamics of open quantum systems. We propose a framework for the generation of Markovian quantum dynamics and study the resources needed for universality. For the case of a single qubit, we show that a single nonunitary process is necessary and sufficient to generate all unital Markovian quantum dynamics, whereas a set of processes parametrized by one continuous parameter is needed in general. We also obtain preliminary results for the unital case in higher dimensions.
%B Physical Review A
%V 64
%8 2001/11/9
%G eng
%U http://arxiv.org/abs/quant-ph/0008070v2
%N 6
%! Phys. Rev. A
%R 10.1103/PhysRevA.64.062302