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:1304.0845

Adversary Lower Bound for the Orthogonal Array Problem

Robert Špalek

Published Apr 3, 2013• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1304.0845

Related papers

Adversary lower bound for the k-sum problem

Aleksandrs Belovs, Robert Špalek

We prove a tight quantum query lower bound Omega(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.

Conference on Innovations in Theoretical Computer Science•Jan 3, 2013•49 citations

Adversary Lower Bound for Element Distinctness with Small Range

Ansis Rosmanis

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 $Θ(N^{2/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 $Ω(N^2)$. We construct a tight $Ω(N^{2/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.

arXiv:1401.3826•Jan 16, 2014•5 citations

Quantum Lower Bounds for Collision Problems

Pan Peng, Jingyu Wu

We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised $k$-to-one Finding on an exactly $k$-to-one input string $x\in\mathbb Z_q^n$, for every fixed $k\ge2$ and every feasible alphabet size $q\ge n/k$. The lower bounds are $Ω_k(n^{1/2-1/(2(2^k-1))})$ for unrestricted adaptive algorithms and $Ω_k(n^{1-1/k})$ for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound $Ω_k(\sqrt{n/k})$ for $k$-to-one Testing when $q\ge n$, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10]. Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.

quant-pharXiv:2611.01767•Nov 3, 2026•0 citations

Improved Quantum Query Bounds for Boolean Matrix Product Verification

Amin Shiraz Gilani, François Le Gall, Xingyu Zhou

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an $Ω(n^{5/4})$ lower bound, which improves over the previous best known lower bound of $\widetildeΩ(n^{19/18})$ by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors ($\mathsf{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 $\mathsf{OV}$ and $\mathsf{BMPV}$ and establish the above bounds for $\mathsf{OV}$. We also prove a tight $\widetilde Θ(n^{3/2})$ bound for a variant of $\mathsf{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.

quant-pharXiv:2609.40180•Oct 1, 2026•0 citations

Adversary Lower Bound for the k-sum Problem

Aleksandrs Belovs, Robert Špalek

We prove a tight quantum query lower bound $Ω(n^{k/(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.

arXiv:1206.6528•Jun 27, 2012•21 citations

Adversary lower bounds for the collision and the set equality problems

Aleksandrs Belovs, Ansis Rosmanis

We prove tight \Omega(n^{1/3}) lower bounds on the quantum query complexity of the Collision and the Set Equality problems, provided that the size of the alphabet is large enough. We do this using the negative-weight adversary method. Thus, we reprove the result by Aaronson and Shi, as well as a more recent development by Zhandry.

arXiv:1310.5185•Quantum Information and Computation•Mar 1, 2018•20 citations
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.
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)Θ(N^{2/3})Θ(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)Ω(N^2)Ω(N2). We construct a tight Ω(N2/3)Ω(N^{2/3})Ω(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 establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised kkk-to-one Finding on an exactly kkk-to-one input string x∈Zqnx\in\mathbb Z_q^nx∈Zqn​, for every fixed k≥2k\ge2k≥2 and every feasible alphabet size q≥n/kq\ge n/kq≥n/k. The lower bounds are Ωk(n1/2−1/(2(2k−1)))Ω_k(n^{1/2-1/(2(2^k-1))})Ωk​(n1/2−1/(2(2k−1))) for unrestricted adaptive algorithms and Ωk(n1−1/k)Ω_k(n^{1-1/k})Ωk​(n1−1/k) for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound Ωk(n/k)Ω_k(\sqrt{n/k})Ωk​(n/k​) for kkk-to-one Testing when q≥nq\ge nq≥n, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10]. Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.
We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification (BMPV\mathsf{BMPV}BMPV), answering a longstanding open question in quantum query complexity. For n×nn\times nn×n matrices, our upper bound is O~(n17/12)\widetilde O(n^{17/12})O(n17/12), improving on the standard O(n3/2)O(n^{3/2})O(n3/2) bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an Ω(n5/4)Ω(n^{5/4})Ω(n5/4) lower bound, which improves over the previous best known lower bound of Ω~(n19/18)\widetildeΩ(n^{19/18})Ω(n19/18) by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors (OV\mathsf{OV}OV), which asks whether an indexed list of nnn Boolean vectors of dimension nnn contains two vectors with disjoint supports. In particular, we prove equivalences between OV\mathsf{OV}OV and BMPV\mathsf{BMPV}BMPV and establish the above bounds for OV\mathsf{OV}OV. We also prove a tight Θ~(n3/2)\widetilde Θ(n^{3/2})Θ(n3/2) bound for a variant of BMPV\mathsf{BMPV}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 prove a tight quantum query lower bound Ω(nk/(k+1))Ω(n^{k/(k+1)})Ω(nk/(k+1)) for the problem of deciding whether there exist kkk numbers among nnn 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.