In this paper, we study quantum query complexity of the following rather natural tripartite generalisations (in the spirit of the 3-sum problem) of the hidden shift and the set equality problems, which we call the 3-shift-sum and the 3-matching-sum problems. The 3-shift-sum problem is as follows: given a table of $3\times n$ elements, is it possible to circularly shift its rows so that the sum of the elements in each column becomes zero? It is promised that, if this is not the case, then no 3 elements in the table sum up to zero. The 3-matching-sum problem is defined similarly, but it is allowed to arbitrarily permute elements within each row. For these problems, we prove lower bounds of $Ω(n^{1/3})$ and $Ω(\sqrt n)$, respectively. The second lower bound is tight. The lower bounds are proven by a novel application of the dual learning graph framework and by using representation-theoretic tools.
In this paper, we study quantum query complexity of the following rather natural tripartite generalisations (in the spirit of the 3-sum problem) of the hidden shift and the set equality problems, which we call the 3-shift-sum and the 3-matching-sum problems. The 3-shift-sum problem is as follows: given a table of 3×n elements, is it possible to circularly shift its rows so that the sum of the elements in each column becomes zero? It is promised that, if this is not the case, then no 3 elements in the table sum up to zero. The 3-matching-sum problem is defined similarly, but it is allowed to arbitrarily permute elements within each row. For these problems, we prove lower bounds of Ω(n1/3) and Ω(n), respectively. The second lower bound is tight. The lower bounds are proven by a novel application of the dual learning graph framework and by using representation-theoretic tools.
In this paper, we prove a polynomial lower bound of Ω(n1/3) on the quantum query complexity of the following rather natural generalisation of both the hidden shift and the 3-sum problem. Given an array of 3×n elements, is it possible to circularly shift its rows so that the sum of the elements in each column becomes zero? It is promised that if this is not the case, then no 3 elements in the table sum up to zero.
The lower bound is proven by a novel application of the dual learning graph framework. Additionally, we state a property testing version of the problem, for which we prove a similar lower bound.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning x is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→R the ratio of the maximum value of f to the maximum (over T∈Q) standard deviation of f on a subcube whose free variables are exactly T.'
To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
The set equality problem is to decide whether two sets A and B are equal or disjoint, under the promise that one of these is the case. Some other problems, like the Graph Isomorphism problem, is solvable by reduction to the set quality problem. It was an open problem to find any w(1) query lower bound when sets A and B are given by quantum oracles with functions a and b. We will prove Ω(log1/3nn1/3) lower bound for the set equality problem when the set of the preimages are very small for every element in A and B.
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that Θ(N) queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where N denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform O(N1/3) queries, showing a polynomial speedup. They also proved that Ω(N1/4) queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight Ω(N1/3) quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.
The last decade witnessed a great surge of fruitful studies in the new paradigm of quantum computing. Remarkable progress has been made in all the areas including quantum algorithms, quantum complexity theory, quantum error-correcting code, quantum information theory, quantum cryptography and physical implementations of quantum computers. However, quantum algorithm design, probably the most important task in quantum computing, did not make as much progress as people expected. This thesis aims at both designing new quantum algorithms and studying why efficient quantum algorithms are so hard to design by proving many lower bounds on quantum query complexity for various problems.
We first review (and generalize) known techniques for designing quantum algorithms and for proving quantum lower bounds. Using these techniques, we then study the quantum query complexity for many problems, including some specific problems such as Graph Matching and other natural graph properties, the general tuple search, and local search. We also study the lowest possible quantum query complexity for a class of functions as a whole, such as graph properties, circular functions, and functions invariant of a transitive permutation group, where tight results are given in all these cases.
Finally for the quantum lower bounds techniques themselves, we study the main two techniques and show that they are incomparable in power. For the most widely used one, which has a lot of parameters to choose, we show limitations for it in terms of certificate complexity. This implies that we cannot use the method to prove better lower bounds for almost all known open problems in this area.
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2) bound for finding a maximum-out-degree vertex in an n-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an n-vertex undirected graph requires Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)-Cut, which asks for the largest cut with one side of size k. For every constant k≥1, we give an O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)-Cut involving k-Graph Collision, which asks whether the marked vertices of a known graph contain a k-clique. For k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for k-Graph Collision, the reduction yields a lower bound matching our upper bound above.