The quantum query complexity of the abelian hidden subgroup problem

DOI10.1016/J.TCS.2007.02.057zbMATH Open1118.68068DBLPjournals/tcs/KoiranNP07OpenAlexW2092946121WikidataQ59567887 ScholiaQ59567887MaRDI QIDQ2373740FDOQ2373740

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

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

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)

Cites Work

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

Cited In (17)

• 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
• Title not available (Why is that?)
• 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
• Automata, Languages and Programming
• Optimal separation in exact query complexities for Simon's problem
• Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups
• Query complexity of generalized Simon's problem
• Quantum complexity for discrete logarithms and related problems
• Tight bounds for Simon's algorithm
• Complexity bounds on some fundamental computational problems for quantum branching programs.
• Quantum algorithms for algebraic problems

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)