Skip to Main content Skip to Navigation
Conference papers

Quantum Query Complexity of Multilinear Identity Testing

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 t hat 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, February 10, 2009 - 3:41:19 PM
Last modification on : Thursday, February 12, 2009 - 2:23:46 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 6:49:35 PM


Files produced by the author(s)


  • HAL Id : inria-00359727, version 1
  • ARXIV : 0807.1412



V. Arvind, Partha Mukhopadhyay. Quantum Query Complexity of Multilinear Identity Testing. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.87-98. ⟨inria-00359727⟩



Record views


Files downloads