Efficient Quantum Algorithm for Identifying Hidden Polynomials
| dc.creator | Decker, Thomas | |
| dc.creator | Draisma, Jan | |
| dc.creator | Wocjan, Pawel | |
| dc.date | 2007-06-08 | |
| dc.date | 2008-09-02 | |
| dc.date.accessioned | 2026-07-07T09:59:31Z | |
| dc.date.available | 2026-07-07T09:59:31Z | |
| dc.description | 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>=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. | |
| dc.description | 17 pages | |
| dc.identifier | https://arxiv.org/abs/0706.1219 | |
| dc.identifier | http://arxiv.org/abs/0706.1219 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/168051 | |
| dc.subject | Quantum Physics | |
| dc.title | Efficient Quantum Algorithm for Identifying Hidden Polynomials | |
| dc.type | text |