Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0807.1412

Quantum Query Complexity of Multilinear Identity Testing

V. Arvind, Partha Mukhopadhyay

Published Jul 9, 2008• 1 citation
arXivHTMLPDF

Abstract

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,...,r_k}$ where $\{r_1,r_2,...,r_k\}$ is an additive generating set for $R$ and a multilinear polynomial $f(x_1,...,x_m)$ over $R$ also accessed as a black-box function $f:R^m\to R$ (where we allow the indeterminates $x_1,...,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,...,a_m)=0$ for all $a_i\in R$. We give a quantum algorithm with query complexity $O(m(1+α)^{m/2} k^{\frac{m}{m+1}})$ assuming $k\geq (1+1/α)^{m+1}$. Towards a lower bound, we also discuss a reduction from a version of $m$-collision to this problem. We also observe a randomized test with query complexity $4^mmk$ and constant success probability and a deterministic test with $k^m$ query complexity.

DOI
10.48550/arxiv.0807.1412

Related papers

Quantum Query Complexity of Multilinear Identity Testing

V. Arvind, Partha Mukhopadhyay

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.

Leibniz international proceedings in informatics•Jan 1, 2009•2 citations

Quantum Complexity of Testing Group Commutativity. (arXiv:quant-ph/0506265v4 CROSS LISTED)

Frédéric Magniez, Ashwin Nayak

We consider the problem of testing the commutativity of a black-box group specified by its k generators. The complexity (in terms of k) of this problem was first considered by Pak, who gave a randomized algorithm involving O(k) group operations. We construct a quite optimal quantum algorithm for this problem whose complexity is in O (k^{2/3}). The algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Omega(k^{2/3}), we give a reduction from a special case of Element Distinctness to our problem. Along the way, we prove the optimality of the algorithm of Pak for the randomized model.

•Mar 21, 2018•0 citations

The Quantum Query Complexity of Algebraic Properties

Sebastian Doern, Thomas Thierauf

We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether $S$ is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.

arXiv:0705.1446•May 10, 2007•15 citations

New Results on Quantum Property Testing

Sourav Chakraborty, Eldar Fischer, Arie Matsliah +1 more

We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle $f:[n]\to[m]$. Here the probability $\PP_f(j)$ of an outcome $j\in[m]$ is the fraction of its domain that $f$ maps to $j$. We give quantum algorithms for testing whether two such distributions are identical or $ε$-far in $L_1$-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles $f$ and $g$), then this testing can be done in roughly $\sqrt{m}$ quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly $m^{1/3}$ quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about $m^{2/3}$ queries in the unknown-unknown case and about $\sqrt{m}$ queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.

arXiv:1005.0523•May 4, 2010•16 citations

Quantum Oracle Classification - The Case of Group Structure

Mark Zhandry

The Quantum Oracle Classification (QOC) problem is to classify a function, given only quantum black box access, into one of several classes without necessarily determining the entire function. Generally, QOC captures a very wide range of problems in quantum query complexity. However, relatively little is known about many of these problems. In this work, we analyze the a subclass of the QOC problems where there is a group structure. That is, suppose the range of the unknown function A is a commutative group G, which induces a commutative group law over the entire function space. Then we consider the case where A is drawn uniformly at random from some subgroup A of the function space. Moreover, there is a homomorpism f on A, and the goal is to determine f(A). This class of problems is very general, and covers several interesting cases, such as oracle evaluation; polynomial interpolation, evaluation, and extrapolation; and parity. These problems are important in the study of message authentication codes in the quantum setting, and may have other applications. We exactly characterize the quantum query complexity of every instance of QOC with group structure in terms of a particular counting problem. That is, we provide an algorithm for this general class of problems whose success probability is determined by the solution to the counting problem, and prove its exact optimality. Unfortunately, solving this counting problem in general is a non-trivial task, and we resort to analyzing special cases. Our bounds unify some existing results, such as the existing oracle evaluation and parity bounds. In the case of polynomial interpolation and evaluation, our bounds give new results for secret sharing and information theoretic message authentication codes in the quantum setting.

arXiv:1510.08352•Oct 28, 2015•8 citations

Quantum Query Complexity of Unitary Operator Discrimination

Akinori Kawachi, Kenichi Kawano, François Le Gall +1 more

Unitary operator discrimination is a fundamental problem in quantum information theory. The basic version of this problem can be described as follows: Given a black box implementing a unitary operator U∈S:={U1, U2} under some probability distribution over S, the goal is to decide whether U=U1 or U=U2. In this paper, we consider the query complexity of this problem. We show that there exists a quantum algorithm that solves this problem with bounded error probability using $\lceil{\sqrt{6}\theta_{\rm cover}^{-1}}\rceil$ queries to the black box in the worst case, i.e., under any probability distribution over S, where the parameter θcover, which is determined by the eigenvalues of $U_1^\dagger {U_2}$, represents the “closeness” between U1 and U2. We also show that this upper bound is essentially tight: we prove that for every θcover > 0 there exist operators U1 and U2 such that any quantum algorithm solving this problem with bounded error probability requires at least $\lceil{\frac{2}{3 \theta_{\rm cover}}}\rceil$ queries under uniform distribution over S.

IEICE Transactions on Information and Systems•Feb 28, 2019•4 citations
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=∠r1,...,rkR=\angle{r_1,...,r_k}R=∠r1​,...,rk​ where {r1,r2,...,rk}\{r_1,r_2,...,r_k\}{r1​,r2​,...,rk​} is an additive generating set for RRR and a multilinear polynomial f(x1,...,xm)f(x_1,...,x_m)f(x1​,...,xm​) over RRR also accessed as a black-box function f:Rm→Rf:R^m\to Rf:Rm→R (where we allow the indeterminates x1,...,xmx_1,...,x_mx1​,...,xm​ to be commuting or noncommuting), we study the problem of testing if fff is an \emph{identity} for the ring RRR. More precisely, the problem is to test if f(a1,a2,...,am)=0f(a_1,a_2,...,a_m)=0f(a1​,a2​,...,am​)=0 for all ai∈Ra_i\in Rai​∈R. We give a quantum algorithm with query complexity O(m(1+α)m/2kmm+1)O(m(1+α)^{m/2} k^{\frac{m}{m+1}})O(m(1+α)m/2km+1m​) assuming k≥(1+1/α)m+1k\geq (1+1/α)^{m+1}k≥(1+1/α)m+1. Towards a lower bound, we also discuss a reduction from a version of mmm-collision to this problem. We also observe a randomized test with query complexity 4mmk4^mmk4mmk and constant success probability and a deterministic test with kmk^mkm query complexity.
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.
We consider the problem of testing the commutativity of a black-box group specified by its k generators. The complexity (in terms of k) of this problem was first considered by Pak, who gave a randomized algorithm involving O(k) group operations. We construct a quite optimal quantum algorithm for this problem whose complexity is in O (k^{2/3}). The algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Omega(k^{2/3}), we give a reduction from a special case of Element Distinctness to our problem. Along the way, we prove the optimality of the algorithm of Pak for the randomized model.
We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether SSS is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle f:[n]→[m]f:[n]\to[m]f:[n]→[m]. Here the probability $\PP_f(j)$ of an outcome j∈[m]j\in[m]j∈[m] is the fraction of its domain that fff maps to jjj. We give quantum algorithms for testing whether two such distributions are identical or εεε-far in L1L_1L1​-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles fff and ggg), then this testing can be done in roughly m\sqrt{m}m​ quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly m1/3m^{1/3}m1/3 quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about m2/3m^{2/3}m2/3 queries in the unknown-unknown case and about m\sqrt{m}m​ queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.
The Quantum Oracle Classification (QOC) problem is to classify a function, given only quantum black box access, into one of several classes without necessarily determining the entire function. Generally, QOC captures a very wide range of problems in quantum query complexity. However, relatively little is known about many of these problems. In this work, we analyze the a subclass of the QOC problems where there is a group structure. That is, suppose the range of the unknown function A is a commutative group G, which induces a commutative group law over the entire function space. Then we consider the case where A is drawn uniformly at random from some subgroup A of the function space. Moreover, there is a homomorpism f on A, and the goal is to determine f(A). This class of problems is very general, and covers several interesting cases, such as oracle evaluation; polynomial interpolation, evaluation, and extrapolation; and parity. These problems are important in the study of message authentication codes in the quantum setting, and may have other applications. We exactly characterize the quantum query complexity of every instance of QOC with group structure in terms of a particular counting problem. That is, we provide an algorithm for this general class of problems whose success probability is determined by the solution to the counting problem, and prove its exact optimality. Unfortunately, solving this counting problem in general is a non-trivial task, and we resort to analyzing special cases. Our bounds unify some existing results, such as the existing oracle evaluation and parity bounds. In the case of polynomial interpolation and evaluation, our bounds give new results for secret sharing and information theoretic message authentication codes in the quantum setting.
Unitary operator discrimination is a fundamental problem in quantum information theory. The basic version of this problem can be described as follows: Given a black box implementing a unitary operator U∈S:={U1, U2} under some probability distribution over S, the goal is to decide whether U=U1 or U=U2. In this paper, we consider the query complexity of this problem. We show that there exists a quantum algorithm that solves this problem with bounded error probability using ⌈6θcover−1⌉\lceil{\sqrt{6}\theta_{\rm cover}^{-1}}\rceil⌈6​θcover−1​⌉ queries to the black box in the worst case, i.e., under any probability distribution over S, where the parameter θcover, which is determined by the eigenvalues of U1†U2U_1^\dagger {U_2}U1†​U2​, represents the “closeness” between U1 and U2. We also show that this upper bound is essentially tight: we prove that for every θcover > 0 there exist operators U1 and U2 such that any quantum algorithm solving this problem with bounded error probability requires at least ⌈23θcover⌉\lceil{\frac{2}{3 \theta_{\rm cover}}}\rceil⌈3θcover​2​⌉ queries under uniform distribution over S.