In this paper we extend the algorithm for extraspecial groups in \cite{iss07}, and show that the hidden subgroup problem in nil-2 groups, that is in groups of nilpotency class at most 2, can be solved efficiently by a quantum procedure. The algorithm presented here has several additional features. It contains a powerful classical reduction for the hidden subgroup problem in nilpotent groups of constant nilpotency class to the specific case where the group is a $p$ -group of exponent $p$ and the subgroup is either trivial or cyclic. This reduction might also be useful for dealing with groups of higher nilpotency class. The quantum part of the algorithm uses well chosen group actions based on some automorphisms of nil-2 groups. The right choice of the actions requires the solution of a system of quadratic and linear equations. The existence of a solution is guaranteed by the Chevalley-Warning theorem, and we prove that it can also be found efficiently.In this paper we extend the algorithm for extraspecial groups in \cite{iss07}, and show that the hidden subgroup problem in nil-2 groups, that is in groups of nilpotency class at most 2, can be solved efficiently by a quantum procedure. The algorithm presented here has several additional features. It contains a powerful classical reduction for the hidden subgroup problem in nilpotent groups of constant nilpotency class to the specific case where the group is a $p$-group of exponent $p$ and the subgroup is either trivial or cyclic. This reduction might also be useful for dealing with groups of higher nilpotency class. The quantum part of the algorithm uses well chosen group actions based on some automorphisms of nil-2 groups. The right choice of the actions requires the solution of a system of quadratic and linear equations. The existence of a solution is guaranteed by the Chevalley-Warning theorem, and we prove that it can also be found efficiently.

arXiv:0707.1260Jul 9, 20071 citation

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.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.

arXiv:quant-ph/0504083Annual Symposium on Foundations of Computer ScienceNov 15, 2005124 citations

Hidden Symmetry Subgroup Problems

Thomas Decker, Gábor Ivanyos, Miklós Sántha +1 more

We advocate a new approach for addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the hidden symmetry subgroup problem (HSSP), which is a generalization of the well-studied hidden subgroup problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSSP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSSP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSSP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSSP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms.We advocate a new approach for addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the hidden symmetry subgroup problem (HSSP), which is a generalization of the well-studied hidden subgroup problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSSP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSSP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSSP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSSP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms.

arXiv:1107.2189SIAM Journal on ComputingJan 1, 20137 citations

p

-group of exponent

p

and the subgroup is either trivial or cyclic. This reduction might also be useful for dealing with groups of higher nilpotency class. The quantum part of the algorithm uses well chosen group actions based on some automorphisms of nil-2 groups. The right choice of the actions requires the solution of a system of quadratic and linear equations. The existence of a solution is guaranteed by the Chevalley-Warning theorem, and we prove that it can also be found efficiently.