ECCC-Report TR08-086https://eccc.weizmann.ac.il/report/2008/086Comments and Revisions published for TR08-086en-usWed, 17 Sep 2008 21:12:50 +0300
Paper TR08-086
| Quantum Query Complexity of Multilinear Identity Testing |
Vikraman Arvind,
Partha Mukhopadhyay
https://eccc.weizmann.ac.il/report/2008/086 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.
Wed, 17 Sep 2008 21:12:50 +0300https://eccc.weizmann.ac.il/report/2008/086