The quantum query complexity of the abelian hidden subgroup problem

DOI10.1016/J.TCS.2007.02.057MaRDI QIDQ2373740zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Pascal Koiran, Vincent Nesme, Natacha Portier

Publication date 16 July 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://hal-lara.archives-ouvertes.fr/hal-02101788/file/RR2005-17.pdf

zbMATH Keywords

hidden subgroup problemslower boundspolynomial methodquantum computingquery complexitySimon's problem

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68)

Recommendations

• On the quantum complexity of the continuous hidden subgroup problem
• The quantum query complexity of the hidden subgroup problem is polynomial
• Quantum algorithms for the hidden subgroup problem on some semi-direct product groups by reduction to abelian cases
• EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
• Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups
• On quantum algorithms for noncommutative hidden subgroups

Cites work

• Automata, Languages and Programming
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1559521 (Why is no real title available?)
• On the degree of Boolean functions as real polynomials
• On the Power of Quantum Computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithms and the Fourier transform
• Quantum computing
• Quantum lower bound for the collision problem with small range
• Quantum lower bounds by polynomials
• Quantum lower bounds for the collision and the element distinctness problems
• The quantum query complexity of the abelian hidden subgroup problem
• The quantum query complexity of the hidden subgroup problem is polynomial
• The theory of finite groups. An introduction.

Cited in

(20)

• Optimal separation in exact query complexities for Simon's problem
• New approaches to designing public key cryptosystems using one-way functions and trapdoors in finite groups
• Query complexity of generalized Simon's problem
• On the quantum complexity of the continuous hidden subgroup problem
• Tight bounds for Simon's algorithm
• Quantum dual adversary for hidden subgroups and beyond
• The quantum query complexity of the abelian hidden subgroup problem
• The quantum query complexity of the hidden subgroup problem is polynomial
• Sample complexity of hidden subgroup problem
• Quantum and classical query complexities for generalized Simon's problem
• Quantum algorithms for algebraic problems
• scientific article; zbMATH DE number 5320411 (Why is no real title available?)
• Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups
• The one-way communication complexity of subgroup membership
• Complexity bounds on some fundamental computational problems for quantum branching programs.
• Automata, Languages and Programming
• Quantum query lower bounds for key recovery attacks on the Even-Mansour cipher
• Quantum complexity for discrete logarithms and related problems
• Quantum query complexity with matrix-vector products
• Adversary lower bounds for nonadaptive quantum algorithms

This page was built for publication: The quantum query complexity of the abelian hidden subgroup problem

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