Name
Abstract | ||
|---|---|---|
Motivated by the quantum algorithm for testing commutativity of black-box groups (Magniez and Nayak, 2007), we study the following problem: Given a black-box finite ring by an additive generating set and a multilinear polynomial over that ring, also accessed as a black-box function (we allow the indeterminates of the polynomial to be commuting or noncommuting), we study the problem of testing if the polynomial is an identity for the given ring. We give a quantum algorithm with query complexity sub-linear in the number of generators for the ring, when the number of indeterminates of the input polynomial is small (ideally a constant). Towards a lower bound, we also show a reduction from a version of the collision problem (which is well studied in quantum computation) to a variant of this problem. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.4230/LIPIcs.STACS.2009.1801 | symposium on theoretical aspects of computer science |
Keywords | DocType | Volume |
query complexity,multilinear polynomials.,identity testing,quantum algorithm | Journal | abs/0807.1 |
Issue | Citations | PageRank |
086 | 1 | 0.36 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 296 | 38.18 |
| Partha Mukhopadhyay | 2 | 91 | 12.71 |