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:0706.1219 · Quantum Information and Computation

Efficient quantum algorithm for identifying hidden polynomials

Thomas Decker, Jan Draisma, Paweł Wocjan

Published Mar 1, 2009• 13 citations
arXivHTMLPDF

Abstract

We consider a natural generalization of an abelian Hidden Subgroup Problem where the subgroups and their cosets correspond to graphs of linear functions over a finite field $\F$ with $d$ elements. The hidden functions of the generalized problem are not restricted to be linear but can also be $m$-variate polynomial functions of total degree $n\geq 2$. The problem of identifying hidden $m$-variate polynomials of degree less or equal to $n$ for fixed $n$ and $m$ is hard on a classical computer since $\Omega(\sqrt{d})$ black-box queries are required to guarantee a constant success probability. In contrast, we present a quantum algorithm that correctly identifies such hidden polynomials for all but a finite number of values of $d$ with constant probability and that has a running time that is only polylogarithmic in $d$.

DOI
10.26421/qic9.3-4-3

Related papers

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

Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs

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 F_p. 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 quadratic and cubic function graphs by establishing that the success probability of the measurement is lower bounded by a constant and that it can be implemented efficiently.

arXiv:quant-ph/0703195•Mar 21, 2007•2 citations

Hidden Subgroup States are Almost Orthogonal

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

It is well known that quantum computers can efficiently find a hidden subgroup $H$ of a finite Abelian group $G$. This implies that after only a polynomial (in $\log |G|$) number of calls to the oracle function, the states corresponding to different candidate subgroups have exponentially small inner product. We show that this is true for noncommutative groups also. We present a quantum algorithm which identifies a hidden subgroup of an arbitrary finite group $G$ in only a linear (in $\log |G|$) number of calls to the oracle function. This is exponentially better than the best classical algorithm. However our quantum algorithm requires an exponential amount of time, as in the classical case.

arXiv:quant-ph/9901034•Jan 14, 1999•40 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

The Hidden Subgroup Problem for Universal Algebras

Matthew Moore, Taylor Walenczyk

The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for abelian groups, but despite focused research no polynomial-time solution for general groups has yet been found. We propose a generalization of the HSP to include arbitrary algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, or classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.

arXiv:2001.11298•ACM/IEEE Symposium on Logic in Computer Science (LICS)•May 26, 2020•0 citations

Hidden subgroup problem in quantum computing

Shuhong Gao, Prasit Limbupasiriporn

We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups. We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture. For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem. In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.

•Jan 1, 2005•0 citations
We consider a natural generalization of an abelian Hidden Subgroup Problem where the subgroups and their cosets correspond to graphs of linear functions over a finite field \F\F\F with ddd elements. The hidden functions of the generalized problem are not restricted to be linear but can also be mmm-variate polynomial functions of total degree n≥2n\geq 2n≥2. The problem of identifying hidden mmm-variate polynomials of degree less or equal to nnn for fixed nnn and mmm is hard on a classical computer since Ω(d)\Omega(\sqrt{d})Ω(d​) black-box queries are required to guarantee a constant success probability. In contrast, we present a quantum algorithm that correctly identifies such hidden polynomials for all but a finite number of values of ddd with constant probability and that has a running time that is only polylogarithmic in ddd.
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 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 F_p. 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 quadratic and cubic function graphs by establishing that the success probability of the measurement is lower bounded by a constant and that it can be implemented efficiently.
It is well known that quantum computers can efficiently find a hidden subgroup HHH of a finite Abelian group GGG. This implies that after only a polynomial (in log⁡∣G∣\log |G|log∣G∣) number of calls to the oracle function, the states corresponding to different candidate subgroups have exponentially small inner product. We show that this is true for noncommutative groups also. We present a quantum algorithm which identifies a hidden subgroup of an arbitrary finite group GGG in only a linear (in log⁡∣G∣\log |G|log∣G∣) number of calls to the oracle function. This is exponentially better than the best classical algorithm. However our quantum algorithm requires an exponential amount of time, as in the classical case.
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.
The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for abelian groups, but despite focused research no polynomial-time solution for general groups has yet been found. We propose a generalization of the HSP to include arbitrary algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, or classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.
We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups. We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture. For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem. In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.