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

lower boundsquery complexityquantum computingpolynomial methodhidden subgroup problemsSimon's problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) 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

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1559521 (Why is no real title available?)
• Automata, Languages and Programming
• On the Power of Quantum Computation
• On the degree of Boolean functions as real polynomials
• 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

(17)

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

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)