The quantum query complexity of the abelian hidden subgroup problem

DOI10.1016/j.tcs.2007.02.057zbMath1118.68068OpenAlexW2092946121WikidataQ59567887 ScholiaQ59567887MaRDI QIDQ2373740

Natacha Portier, Vincent Nesme, Pascal Koiran

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 boundsquantum computingquery complexitypolynomial methodhidden subgroup problemsSimon's problem

Mathematics Subject Classification ID

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

Related Items (7)

The quantum query complexity of the abelian hidden subgroup problem ⋮ Tight bounds for Simon's algorithm ⋮ Optimal separation in exact query complexities for Simon's problem ⋮ Quantum and classical query complexities for generalized Simon's problem ⋮ Adversary lower bounds for nonadaptive quantum algorithms ⋮ Quantum algorithms for algebraic problems ⋮ New approaches to designing public key cryptosystems using one-way functions and trapdoors in finite groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the degree of Boolean functions as real polynomials
• The theory of finite groups. An introduction.
• The quantum query complexity of the abelian hidden subgroup problem
• The quantum query complexity of the hidden subgroup problem is polynomial
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum algorithms and the Fourier transform
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• On the Power of Quantum Computation
• Quantum lower bounds by polynomials
• Automata, Languages and Programming
• Quantum computing

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