An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups

DOI10.1007/S00453-010-9467-0zbMATH Open1236.68071arXiv0707.1260OpenAlexW2049341040MaRDI QIDQ2428678FDOQ2428678

Authors: Gábor Ivanyos, Luc Sanselme, Miklos Santha 

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/0707.1260

Recommendations

• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups
• EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
• Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups
• The quantum query complexity of the hidden subgroup problem is polynomial

zbMATH Keywords

quantum computingnilpotent groupefficient algorithmhidden subgroup problem

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Finite nilpotent groups, (p)-groups (20D15)

Cites Work

• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Title not available (Why is that?)
• Quantum Computation and Lattice Problems
• On total functions, existence theorems and computational complexity
• Efficient collection in infinite polycyclic groups.
• Collection from the left and other strategies
• Title not available (Why is that?)
• Symbolic Collection using Deep Thought
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups
• Hidden translation and orbit coset in quantum computing
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups
• Orbit-stabilizer problems and computing normalizers for polycyclic groups.
• EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
• Title not available (Why is that?)
• Deterministic equation solving over finite fields
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups

Cited In (7)

• An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group
• On solving systems of diagonal polynomial equations over finite fields
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Zero sum subsequences and hidden subgroups
• Solving systems of diagonal polynomial equations over finite fields

This page was built for publication: An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2428678)