We study the quantum query complexity of computing a semigroup product $x_1\cdots x_n$, when one query reveals one input element and the multiplication table is given. For a finite aperiodic semigroup of size $N-1$, the argument of Aaronson, Grier, and Schaeffer gives an upper bound of $\sqrt n\,(N\log(nN+2))^{O(N)}$ queries.
To obtain query bounds that reflect algebraic structure, we study the product breadth $β$: the smallest bound such that every input word has a subsequence of at most $β$ letters with the same product.
For nontrivial finite commutative aperiodic monoids, the bounded-error quantum query complexity is $Θ(\min\{n,\sqrt{nβ}\})$, and is thus characterized by product breadth. We further show that if such a monoid $M$ has aperiodicity index $k$ (the least positive integer satisfying $x^k=x^{k+1}$ for every $x\in M$), then $β=O(k\log(|M|+1)\log\log(|M|+2))$.
For monoids with a stable partial order in which the identity is the minimum element, we prove that the bounded-error quantum query complexity is at most $\sqrt{n+1}((β+2)\log(n+2))^{O(\log(β+2))}$.
For arbitrary finite aperiodic semigroups of order $N-1$, we improve the bound of Aaronson, Grier, and Schaeffer, obtaining a bounded-error quantum query complexity of at most \[ \min\left\{n,\sqrt n\, \log^{O((N\log(N+2))^{1/3})}(n+2)\right\}. \] The dependence on semigroup size is nearly tight: the bounded-depth Dyck lower bound of Ambainis et al. yields aperiodic monoids requiring $\sqrt n\,2^{Ω(N^{1/3})}$ quantum queries in the relevant parameter range.
We study the quantum query complexity of computing a semigroup product x1⋯xn, when one query reveals one input element and the multiplication table is given. For a finite aperiodic semigroup of size N−1, the argument of Aaronson, Grier, and Schaeffer gives an upper bound of n(Nlog(nN+2))O(N) queries.
To obtain query bounds that reflect algebraic structure, we study the product breadth β: the smallest bound such that every input word has a subsequence of at most β letters with the same product.
For nontrivial finite commutative aperiodic monoids, the bounded-error quantum query complexity is Θ(min{n,nβ}), and is thus characterized by product breadth. We further show that if such a monoid M has aperiodicity index k (the least positive integer satisfying xk=xk+1 for every x∈M), then β=O(klog(∣M∣+1)loglog(∣M∣+2)).
For monoids with a stable partial order in which the identity is the minimum element, we prove that the bounded-error quantum query complexity is at most n+1((β+2)log(n+2))O(log(β+2)).
For arbitrary finite aperiodic semigroups of order N−1, we improve the bound of Aaronson, Grier, and Schaeffer, obtaining a bounded-error quantum query complexity of at most [ \min\left{n,\sqrt n, \log^{O((N\log(N+2))^{1/3})}(n+2)\right}. ] The dependence on semigroup size is nearly tight: the bounded-depth Dyck lower bound of Ambainis et al. yields aperiodic monoids requiring n2Ω(N1/3) quantum queries in the relevant parameter range.
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.
Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting Q(f∘g)=Θ(Q(f)Q(g)) for all Boolean functions f and g; a direct sum theorem asserting that computing k copies of a function (or search problem) costs Ω(k) times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires Ω(k) times the cost of computing one copy to bounded error.
However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution μ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing k copies of f when the input comes from the product distribution μk instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions.
In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the γ2 norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.
We consider the problem of determining if a sequence of parentheses is well parenthesized, with a depth of at most h. We denote this language as Dyckh. We study the quantum query complexity of this problem for different h as function of the length n of the word. It has been known from a recent paper by Aaronson et al. that, for any constant h, since Dyckh is star-free, it has quantum query complexity Θ~(n), where the hidden logarithm factors in Θ~ depend on h. Their proof does not give rise to an algorithm. When h is not a constant, Dyckh is not even context-free. We give an algorithm with O(nlog(n)0.5h) quantum queries for Dyckh for all h. This is better than the trival upper bound n when h=o(loglognlog(n)). We also obtain lower bounds: we show that for every 00 such that Q(Dyckclog(n)(n))=Ω(n1−ε). When h=ω(log(n)), the quantum query complexity is close to n, i.e. Q(Dyckh(n))=ω(n1−ε) for all ε>0. Furthermore when h=Ω(nε) for some ε>0, Q(Dyckh(n))=Θ(n).
We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification (BMPV), answering a longstanding open question in quantum query complexity. For n×n matrices, our upper bound is O(n17/12), improving on the standard O(n3/2) bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an Ω(n5/4) lower bound, which improves over the previous best known lower bound of Ω(n19/18) by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors (OV), which asks whether an indexed list of n Boolean vectors of dimension n contains two vectors with disjoint supports. In particular, we prove equivalences between OV and BMPV and establish the above bounds for OV. We also prove a tight Θ(n3/2) bound for a variant of BMPV that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most k. We call this the Dyckk,n problem. We prove a lower bound of Ω(ckn), showing that the complexity of this problem increases exponentially in k. Here n is the length of the word. When k is a constant, this is interesting as a representative example of star-free languages for which a surprising O~(n) query quantum algorithm was recently constructed by Aaronson et al. Their proof does not give rise to a general algorithm. When k is not a constant, Dyckk,n is not context-free. We give an algorithm with O(n(logn)0.5k) quantum queries for Dyckk,n for all k. This is better than the trival upper bound n for k=o(loglognlog(n)). Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of Ω(n1.5−ε) for the directed 2D grid and Ω(n2−ε) for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order ℓ≥1 sum to at most cℓ(ℓd)(1+logn)ℓ−1, where n is the number of variables, d is the tree depth, and c>0 is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). The bounds prior to our work degraded rapidly with ℓ, becoming trivial already at ℓ=d. As an application, we obtain, for every integer k≥1, a partial Boolean function on n bits that has bounded-error quantum query complexity at most k and randomized query complexity Ω~(n1−2k1). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015) and Bravyi, Gosset, Grier, and Schaeffer (2021). Prior to our work, the best known separation was polynomially weaker: O(1) versus Ω(n2/3−ε) for any ε>0 (Tal, FOCS 2020). As another application, we obtain an essentially optimal separation of O(logn) versus Ω(n1−ε) for bounded-error quantum versus randomized communication complexity, for any ε>0. The best previous separation was polynomially weaker: O(logn) versus Ω(n2/3−ε) (implicit in Tal, FOCS 2020).