Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0401083 · Information Processing Letters

The quantum query complexity of the hidden subgroup problem is polynomial

Mark Ettinger, Peter Høyer, Emanuel H. Knill

Published May 13, 2004• 162 citations
arXivHTMLPDF
DOI
10.1016/j.ipl.2004.01.024

Related papers

The quantum query complexity of the abelian hidden subgroup problem

Pascal Koiran, Vincent Nesme, Natacha Portier

Theoretical Computer Science•Mar 2, 2007•22 citations

On the Quantum Complexity of the Continuous Hidden Subgroup Problem

Koen de Boer, Léo Ducas, Serge Fehr

Lecture notes in computer science•Jan 1, 2020•9 citations

A Note on the Quantum Query Complexity of the Hidden Subgroup Problem

Troels Windfeldt

We are concerned with the Hidden Subgroup Problem for finite groups. We present a simplified analysis of a quantum algorithm proposed by Hallgren, Russell and Ta-Shma as well as a detailed proof of a lower bound on the probability of success of the algorithm.

arXiv:quant-ph/0404067•Apr 11, 2004•0 citations

On the Complexity of the Hidden Subgroup Problem

Stephen Fenner, Yong Zhang

Springer eBooks•Apr 29, 2008•2 citations

Quantum algorithm for identifying hidden polynomial function graphs

Thomas Decker, Jan Draisma, Paweł Wocjan

We introduce the Hidden Polynomial Function Graph Problem as a natural generalization of an abelian Hidden Subgroup Problem (HSP) where the subgroups and their cosets correspond to graphs of linear functions over a finite field F with d elements. For the Hidden Polynomial Function Graph Problem the functions are not restricted to be linear but can also be m-variate polynomial functions of total degree n ≥ 2. For fixed m and bounded n the problem is hard on a classical computer as the black box query complexity is polynomial in d. In contrast, we reduce it to a quantum state identification problem so that its query complexity is n m +n m−1 +...+n, independent of d. We derive an efficient measurement for distinguishing the resulting quantum states provided that the characteristic of F is sufficiently large. Its success probability and implementation are closely related to a classical problem involving polynomial equations.

Quantum Information and Computation•Jan 1, 2008•4 citations

Efficient Quantum Algorithm for the Hidden Parabola Problem

Thomas Decker, Paweł Wocjan

We introduce the Hidden Polynomial Function Graph Problem as a natural generalization of an abelian Hidden Subgroup Problem (HSP) where the subgroups and their cosets correspond to graphs of linear functions over the finite field Fp. For the Hidden Polynomial Function Graph Problem the functions are not restricted to be linear but can also be multivariate polynomial functions of higher degree. For a fixed number of indeterminates and bounded total degree the Hidden Polynomial Function Graph Problem is hard on a classical computer as its black box query complexity is polynomial in p. In contrast, this problem can be reduced to a quantum state identification problem so that the resulting quantum query complexity does not depend on p. For univariate polynomials we construct a von Neumann measurement for distinguishing the states. We relate the success probability and the implementation of this measurement to certain classical problems involving polynomial equations. We present an efficient algorithm for hidden parabola by establishing that the success probability of the measurement is lower bounded by a constant and that it can be implemented efficiently. 1

•Mar 21, 2007•0 citations
We introduce the Hidden Polynomial Function Graph Problem as a natural generalization of an abelian Hidden Subgroup Problem (HSP) where the subgroups and their cosets correspond to graphs of linear functions over a finite field F with d elements. For the Hidden Polynomial Function Graph Problem the functions are not restricted to be linear but can also be m-variate polynomial functions of total degree n ≥ 2. For fixed m and bounded n the problem is hard on a classical computer as the black box query complexity is polynomial in d. In contrast, we reduce it to a quantum state identification problem so that its query complexity is n m +n m−1 +...+n, independent of d. We derive an efficient measurement for distinguishing the resulting quantum states provided that the characteristic of F is sufficiently large. Its success probability and implementation are closely related to a classical problem involving polynomial equations.
We introduce the Hidden Polynomial Function Graph Problem as a natural generalization of an abelian Hidden Subgroup Problem (HSP) where the subgroups and their cosets correspond to graphs of linear functions over the finite field Fp. For the Hidden Polynomial Function Graph Problem the functions are not restricted to be linear but can also be multivariate polynomial functions of higher degree. For a fixed number of indeterminates and bounded total degree the Hidden Polynomial Function Graph Problem is hard on a classical computer as its black box query complexity is polynomial in p. In contrast, this problem can be reduced to a quantum state identification problem so that the resulting quantum query complexity does not depend on p. For univariate polynomials we construct a von Neumann measurement for distinguishing the states. We relate the success probability and the implementation of this measurement to certain classical problems involving polynomial equations. We present an efficient algorithm for hidden parabola by establishing that the success probability of the measurement is lower bounded by a constant and that it can be implemented efficiently. 1