Zero sum subsequences and hidden subgroups

DOI10.1007/S11128-023-04228-2MaRDI QIDQ6182403zbMATH OpenFDO

Authors

Publication date 25 January 2024

Published in Quantum Information Processing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

exact quantum algorithmhidden subgroup problemnilpotent groupzero sum subsequence

Mathematics Subject Classification ID

Quantum computation (81P68)

Abstract: We propose a method for solving the hidden subgroup problem in nilpotent groups. The main idea is iteratively transforming the hidden subgroup to its images in the quotient groups by the members of a central series, eventually to its image in the commutative quotient of the original group; and then using an abelian hidden subgroup algorithm to determine this image. Knowing this image allows one to descend to a proper subgroup unless the hidden subgroup is the full group. The transformation relies on finding zero sum subsequences of sufficiently large sequences of vectors over finite prime fields. We present a new deterministic polynomial time algorithm for the latter problem in the case when the size of the field is constant. The consequence is a polynomial time exact quantum algorithm for the hidden subgroup problem in nilpotent groups having constant nilpotency class and whose order only have prime factors also bounded by a constant.

Recommendations

• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
• Solutions to the hidden subgroup problem on some metacyclic groups
• Quantum algorithms for the hidden subgroup problem on some semi-direct product groups by reduction to abelian cases
• Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups

Cites work

• A combinatorial problem on finite Abelian groups. I
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
• Computational complexity of uniform quantum circuit families and quantum Turing machines
• EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
• Hidden shift quantum cryptanalysis and implications
• Hidden translation and translating coset in quantum computing
• scientific article; zbMATH DE number 824935 (Why is no real title available?)
• Is Grover's algorithm a quantum hidden subgroup algorithm?
• Optimal separation in exact query complexities for Simon's problem
• Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families
• Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem
• Quantum algorithms for Simon's problem over general groups
• Quantum algorithms for solvable groups
• Quantum and classical query complexities for generalized Simon's problem
• Quantum Complexity Theory
• Quantum computation and quantum information. 10th anniversary edition
• Quantum hidden subgroup algorithms: an algorithmic toolkit
• Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
• Solving systems of diagonal polynomial equations over finite fields
• The hidden subgroup problem and post-quantum group-based cryptography
• The quantum query complexity of the hidden subgroup problem is polynomial
• Tight bounds for Simon's algorithm
• Two remarks on the vectorization problem
• Uniformity of quantum circuit families for error-free algorithms

This page was built for publication: Zero sum subsequences and hidden subgroups

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