Quantum Query Complexity of Multilinear Identity Testing

Arvind, Vikraman; Mukhopadhyay, Partha

doi:10.4230/LIPIcs.STACS.2009.1801

Document

Quantum Query Complexity of Multilinear Identity Testing

Authors Vikraman Arvind, Partha Mukhopadhyay

Part of: Volume: 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NoDerivs 3.0 Unported license
Publication Date: 2009-02-19

PDF

File

PDF

LIPIcs.STACS.2009.1801.pdf

Filesize: 151 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2009.1801
URN: urn:nbn:de:0030-drops-18014

Subject Classification

Keywords

Quantum algorithm
Identity testing
Query complexity
Multilinear polynomials

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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 \emph{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.

Cite As Get BibTex

Vikraman Arvind and Partha Mukhopadhyay. Quantum Query Complexity of Multilinear Identity Testing. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 87-98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.STACS.2009.1801

Author Details

Vikraman Arvind

Partha Mukhopadhyay

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail