arXiv:2609.40180
Improved Quantum Query Bounds for Boolean Matrix Product Verification
Amin Shiraz Gilani, François Le Gall, Xingyu Zhou
Abstract
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.
AI Summary
Boolean Matrix Product Verification asks whether three Boolean $n\times n$ matrices satisfy $A\circ B=C$, with multiplication over the Boolean semiring. The paper studies bounded-error quantum query complexity under entrywise oracle access. It gives an upper bound of $\widetilde O(n^{17/12})$, improving the previous $O(n^{3/2})$ Grover-search bound, and a lower bound of $\Omega(n^{5/4})$, improving $\widetilde\Omega(n^{19/18})$. The analysis establishes equivalences, up to constant-factor changes in instance size, between verification, finding an orthogonal pair among $n$ Boolean vectors of dimension $n$, and deciding whether an undirected graph has diameter at most two. Verification is split into two inequalities: one reduces to triangle detection, while the other reduces to Orthogonal Vectors. The upper bound combines sampled pivot vectors, a decomposition of coordinate-search work, variable-time quantum search, and Johnson-graph quantum walks. Tracking first common coordinates removes an intermediate promise on pairwise intersections. The lower bound encodes multiple independent surjectivity instances and uses adversary composition. For the related task of finding a product row equal to a specified vector, the bounds are $\Omega(n^{3/2}/\sqrt{\log n})$ and $O(n^{3/2})$. These also hold for deciding whether graph radius is at most two, giving a polynomial query separation from diameter at most two. The verification bounds remain nonmatching. The upper bound charges only queries, allowing unrestricted computation; comparable running time is left open. Other stated directions include unequal vector dimensions, rectangular products, and radius–diameter separations at larger fixed distance thresholds.
OpenAI GPT 6 Astra and Anthropic Opus 5.5 were used for literature searches, manuscript drafting and revision, proof development and checking, and LaTeX preparation.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 38 pages