dorsal/arxiv
View SchemaEfficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs
| Authors | Thomas Decker, Pawel Wocjan |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0703195 |
| URL | https://arxiv.org/abs/quant-ph/0703195 |
Abstract
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.
{
"annotation_id": "da0ca948-423e-4145-9334-225b018ef9ad",
"date_created": "2026-03-02T18:02:37.246000Z",
"date_modified": "2026-03-02T18:02:37.246000Z",
"file_hash": "0bc093ea41f65c665a11a5453c9a2fd1459b54d84bf1aceb0ac973f85ad3f094",
"private": false,
"record": {
"abstract": "We introduce the Hidden Polynomial Function Graph Problem as a natural\ngeneralization of an abelian Hidden Subgroup Problem (HSP) where the subgroups\nand their cosets correspond to graphs of linear functions over the finite field\nF_p. For the Hidden Polynomial Function Graph Problem the functions are not\nrestricted to be linear but can also be multivariate polynomial functions of\nhigher degree.\n For a fixed number of indeterminates and bounded total degree the Hidden\nPolynomial Function Graph Problem is hard on a classical computer as its black\nbox query complexity is polynomial in p. In contrast, this problem can be\nreduced to a quantum state identification problem so that the resulting quantum\nquery complexity does not depend on p. For univariate polynomials we construct\na von Neumann measurement for distinguishing the states. We relate the success\nprobability and the implementation of this measurement to certain classical\nproblems involving polynomial equations. We present an efficient algorithm for\nhidden quadratic and cubic function graphs by establishing that the success\nprobability of the measurement is lower bounded by a constant and that it can\nbe implemented efficiently.",
"arxiv_id": "quant-ph/0703195",
"authors": [
"Thomas Decker",
"Pawel Wocjan"
],
"categories": [
"quant-ph"
],
"title": "Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs",
"url": "https://arxiv.org/abs/quant-ph/0703195"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f319c546-608b-4e91-bf9f-ab1248e00bb3",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}