Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-086 | 9th July 2008 00:00

Quantum Query Complexity of Multilinear Identity Testing


Authors: Vikraman Arvind, Partha Mukhopadhyay
Publication: 17th September 2008 21:12
Downloads: 3250


Motivated by the quantum algorithm in \cite{MN05} for testing
commutativity of black-box groups, we study the following problem:
Given a black-box finite ring $R=\angle{r_1,\cdots,r_k}$ where
$\{r_1,r_2,\cdots,r_k\}$ is an additive generating set for $R$ and a
multilinear polynomial $f(x_1,\cdots,x_m)$ over $R$ also accessed as
a black-box function $f:R^m\rightarrow R$ (where we allow the
indeterminates $x_1,\cdots,x_m$ to be commuting or noncommuting), we
study the problem of testing if $f$ is an \emph{identity} for the
ring $R$. More precisely, the problem is to test if
$f(a_1,a_2,\cdots,a_m)=0$ for all $a_i\in R$.

1. We give a quantum algorithm with query complexity
$O(m(1+\alpha)^{m/2} k^{\frac{m}{m+1}})$ assuming $k\geq
(1+1/\alpha)^{m+1}$. Towards a lower bound, we also discuss a
reduction from a version of $m$-collision to this problem.
2. We also observe a randomized test with query complexity $4^mmk$
and constant success probability and a deterministic test with $k^m$
query complexity.

ISSN 1433-8092 | Imprint