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• 147 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•20 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 Quantum Complexity of the Continuous Hidden Subgroup Problem

Koen de Boer, Léo Ducas, Serge Fehr

Lecture notes in computer science•Jan 1, 2020•7 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

Hidden Symmetry Subgroup Problems

Thomas Decker, Gábor Ivanyos, Miklós Sántha +1 more

We advocate a new approach for addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the hidden symmetry subgroup problem (HSSP), which is a generalization of the well-studied hidden subgroup problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSSP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSSP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSSP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSSP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms.

arXiv:1107.2189•SIAM Journal on Computing•Jan 1, 2013•7 citations

Quantum Query Complexity for Some Graph Problems

Aija Bērziņa, Andrej Dubrovsky, Rūsiņš Freivalds +2 more

Lecture notes in computer science•Jan 1, 2004•38 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 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
We advocate a new approach for addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the hidden symmetry subgroup problem (HSSP), which is a generalization of the well-studied hidden subgroup problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSSP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSSP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSSP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSSP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms.