We prove a quantum query lower bound Ω(n^{(d+1)/(d+2)}) for the problem of deciding whether an input string of size n contains a k-tuple which belongs to a fixed orthogonal array on k factors of strength d<=k-1 and index 1, provided that the alphabet size is sufficiently large. Our lower bound is tight when d=k-1. The orthogonal array problem includes the following problems as special cases: k-sum problem with d=k-1, k-distinctness problem with d=1, k-pattern problem with d=0, (d-1)-degree problem with 1<=d<=k-1, unordered search with d=0 and k=1, and graph collision with d=0 and k=2.
We prove a quantum query lower bound Ω(n^{(d+1)/(d+2)}) for the problem of deciding whether an input string of size n contains a k-tuple which belongs to a fixed orthogonal array on k factors of strength d<=k-1 and index 1, provided that the alphabet size is sufficiently large. Our lower bound is tight when d=k-1. The orthogonal array problem includes the following problems as special cases: k-sum problem with d=k-1, k-distinctness problem with d=1, k-pattern problem with d=0, (d-1)-degree problem with 1<=d<=k-1, unordered search with d=0 and k=1, and graph collision with d=0 and k=2.
We prove a tight quantum query lower bound Ω(nk/(k+1)) for the problem of deciding whether there exist k numbers among n that sum up to a prescribed number, provided that the alphabet size is sufficiently large. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.
The Element Distinctness problem is to decide whether each character of an input string is unique. The quantum query complexity of Element Distinctness is known to be Θ(N2/3); the polynomial method gives a tight lower bound for any input alphabet, while a tight adversary construction was only known for alphabets of size Ω(N2). We construct a tight Ω(N2/3) adversary lower bound for Element Distinctness with minimal non-trivial alphabet size, which equals the length of the input. This result may help to improve lower bounds for other related query problems.
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 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.