Source-linked AI summary
Improved Quantum Query Bounds for Boolean Matrix Product Verification
Amin Shiraz Gilani, François Le Gall, Xingyu Zhou
TL;DR
Boolean Matrix Product Verification (BMPV) had an unresolved gap between its Grover-search upper bound and known lower bound. The paper connects BMPV with Orthogonal Vectors (OV) through reductions, obtaining improved query bounds for both problems. It also gives query bounds for graph radius-at-most-two and diameter-at-most-two decisions.
Problem
Whether BMPV’s O(n^3/2) quantum query upper bound is optimal remained a longstanding open question.
Source: §1.1 · p. 3Method
The paper connects BMPV with OV through reductions, uses sampling-based list construction for the promised OV case, and encodes surjectivity instances for row-search lower bounds.
Source: §1.2.3 · p. 9, §4.1 · pp. 20, 22Results
Q(BMPV_n) = ~O(n^17/12) and Ω(n^5/4); Q(DIAM≤2,n) = ~O(n^17/12) and Ω(n^5/4), while Q(RAD≤2,n) = ~Θ(n^3/2).
Source: §1.1 · pp. 3–4Takeaways & Limitations
The paper establishes quantum query bounds for deciding whether a graph has radius at most two or diameter at most two.
Source: §1.1 · p. 4The promised OV case assumes every distinct pair has either at most c_low log n or at least c_high n/log n common ones.
Source: §4.1 · p. 20
Abstract
from arXiv · showhide
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 \v{S}palek [SODA 2006]. We complement this result by showing an $\Omega(n^{5/4})$ lower bound, which improves over the previous best known lower bound of $\widetilde\Omega(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 \Theta(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.
1 Introduction
The introduction presents improved quantum query bounds for Boolean matrix product verification and related graph decisions, with Orthogonal Vectors as a central connection. It covers bounds for Orthogonal Vectors and Boolean Matrix Product Row Search, their relation to graph radius, and open questions about query bounds and problem variants.
1.1 Background and statement of the main results
- Q(BMPV_n) is eO(n^17/12) and Ω(n^5/4), improving Grover’s O(n^3/2) upper bound [BŠ06] and the eΩ(n^19/18) lower bound.The lower bound holds even when C is the all-ones matrix and B = A^T.Source: §1.1 · p. 3
- Diameter-at-most-two has eO(n^17/12) upper and Ω(n^5/4) lower bounds, while radius-at-most-two has eΘ(n^3/2), yielding polynomial separation.Diameter corresponds to BMPV with an all-ones target; radius corresponds to all-ones-target BMPRS, whose quantum query complexity is eΘ(n^3/2).Source: §1.1 · p. 4
1.2.1 Reductions and the lower bound
- The OV lower bound encodes missing function outputs as orthogonal row pairs, and the paper establishes matching complexity relationships between OV and BMPV up to dimension changes.The full construction combines √n surjectivity instances into one OV instance; the lower bound draws on the surjectivity lower bound of Beame and Machmouchi and adversary composition.Source: §1.2.1 · pp. 5–6
1.2.2 An upper bound for Orthogonal Vectors
- For Q(OV_n), the upper bound is eO(n^17/12), combining variable-time search with a quantum walk to detect an orthogonal pair; s = ⌈n^1/3⌉ and t = ⌈n^5/6⌉ balance the three walk terms.Source: §1.2.1 · p. 5, §1.2.2 · p. 8
- The general Orthogonal Vectors problem has an eO(n^17/12) query upper bound.Source: §1.2.2 · p. 9
1.2.3 Boolean Matrix Product Row Search and radius
- Boolean Matrix Product Row Search has O(n^3/2)-query complexity, optimal up to a √log n factor, with a surjectivity-based lower bound already for v = 1^n.The lower-bound construction encodes values using paired binary representations and expands the inner dimension with ORs of fresh variables.Source: §1.2.3 · p. 9
- Radius at most two reduces to row search with v = 1^n, and a layered graph construction makes radius at most two equivalent to an all-ones row in A • B.Source: §1.2.3 · p. 10
1.3 Other related work
- Prior quantum Orthogonal Vectors results use different query models or dimensions, while this work studies individual-entry queries at dimension n; adjacency-list graph bounds are likewise not directly comparable.Related quantum results include entire-vector queries, a QSETH framework, and an Ω(n^2/3) lower bound for dimension ω(log n); adjacency-list radius and diameter bounds are due to Wesołowski and Bao [WB25].Source: §1.3 · p. 10
1.4 Open problems
- The gap between Ω(n^5/4) and eO(n^17/12) remains open, and BMPV, Orthogonal Vectors, and diameter-at-most-two have equivalent quantum query complexity up to constant instance-size changes.Other open questions concern Orthogonal Vectors with dimension d differing from n, query-efficient running time, and whether the radius-versus-diameter separation persists for larger fixed thresholds.Source: §1.4 · p. 11
2 Preliminaries
The preliminaries define the query model and problem formulations, then collect quantum search and walk tools used in the upper bounds.
2.1 Model and problem definitions
- The bounded-error quantum query complexity counts oracle queries, while computation on acquired data and input-independent unitaries are free.Unless stated otherwise, reductions simulate each target query with constant input-query overhead.Source: §2.1 · pp. 11–12
- Orthogonal Vectors accepts when distinct indexed vectors have disjoint supports; equal vectors at different positions remain distinct choices.Source: §2.1 · p. 12
- The two-list and single-list OV formulations reduce to each other with dimensions and list lengths within constant factors of n.The reductions append distinguishing coordinates or position-specific unit vectors; target bits are fixed or copy input bits.Source: §2.1 · p. 12
2.2 Quantum algorithmic tools
- Implicit-set procedures estimate whether a set is empty, approximate its size, and prepare a uniform superposition over its members.Source: §2.2 · p. 13
- Ordered search locates the first marked position, while successive-position search finds up to K marks even when the predicate changes after each find.Source: §2.2 · p. 13
- Variable-time search handles candidate tests with unknown completion costs, and the MNRS Johnson walk expresses detection cost through setup, update, and checking.The Johnson walk replaces one member of an r-subset at each step; marked states include subsets containing a particular element.Source: §2.2 · p. 14
3 From verification to Orthogonal Vectors
The section connects Boolean matrix product verification (BMPV) to Orthogonal Vectors (OV): the problems have the same query complexity up to a constant-factor change in dimension. It uses this connection to establish an Ω(n^5/4) lower bound for BMPV and relates diameter-at-most-two testing to OV.
3.1 Reductions between verification and Orthogonal Vectors
- Missing-one errors reduce to triangle detection, while spurious-one errors reduce to OV, separating verification into two distinct detection tasks.The triangle reduction yields an O(n^5/4) query bound for missing-one errors; the OV reduction encodes a spurious-one error as an orthogonal pair.Source: §3 · p. 15, §3.1 · p. 15
3.2 A lower bound from surjectivity
- An AND of r independent surjectivity instances [2q − 2] → [q] requires Ω(q√r) queries, and missing outputs are encoded as orthogonal row pairs.The construction makes an instance contain an orthogonal pair exactly when one of the functions is not surjective.Source: §3.2 · pp. 16, 18
3.3 Equivalence of verification and Orthogonal Vectors
- Q(BMPV_n) = Ω(n^5/4), and BMPV and OV have the same query complexity up to a constant-factor change in problem dimension.The reduction also shows that testing X • X^T = J_n is as hard as verifying an arbitrary claimed product, up to replacing n by 2n + 2.Source: §3 · p. 15, §3.3 · p. 18
3.4 Diameter at Most Two
- For an n-vertex graph, diameter at most two exactly when the rows of bAG viewed as an OV instance contain no orthogonal pair; Q(DIAM≤2,n) = Ω(n5/4).Source: §3.4 · p. 19
4 An upper bound for Orthogonal Vectors
This section presents a bounded-error quantum query algorithm for Orthogonal Vectors, first under a pairwise-intersection promise and then for general inputs, achieving an eO(n^{17/12}) query bound.
4.1 The promise case
- A bounded-error quantum query algorithm solves PromOVn using eO(n^17/12) queries; choosing s = ⌈n^1/3⌉ and t = ⌈n^5/6⌉ yields this bound, with truncation counted as failure.Source: §4.1 · pp. 20, 25
- The promise-case algorithm filters candidate pairs by sampled coordinates, prunes coordinate searches using covered and heavy sets, and searches size classes with a Johnson walk.Its checker tests candidate partners using restricted coordinate sets that contain every common one; the walk stores left lists and marks states containing a vector with an orthogonal partner.Source: §4.1 · pp. 20, 23, 24
4.2 The general case
- eO(n^17/12) queries suffice for general OV, and the paper also derives the same upper bound for BMPV.The OV algorithm adapts the promise-case test sets, size classes, and quantum walk to inputs without the intersection promise.Source: §4.2 · p. 25
- For general inputs, candidate neighborhoods depend on the coordinate: a pair remains a candidate until its first common one, and sampled test sets support the covered and heavy estimates.The degree sample estimates uncovered candidate neighbors even though the covered sets depend on the pivot sample.Source: §4.2 · pp. 25–26
- With probability at least 0.98, the general preprocessing bounds hold simultaneously for all indices and coordinates, and every common one is included in Coordsij.Source: §4.2 · p. 26
- The general checker searches candidate vector pairs in increasing coordinate order, using stored records to construct search sets that contain every common one.It accepts exactly when an index in the tested class has an orthogonal partner, subject to the quantum searches’ error probability.Source: §4.2 · pp. 28–30
- The algorithm groups vectors by estimated left-list size and chooses walk subset size r = Θ(√na) for a class containing na vectors.For each nonempty class, it estimates na within a factor of two and sets r using that estimate.Source: §4.2 · pp. 27, 31
- eO(n^17/12) queries suffice for the general Orthogonal Vectors case with s = ⌈n^1/3⌉ and t = ⌈n^5/6⌉.The algorithm searches each nonempty size class using a quantum walk; its preprocessing and size-label events hold with probability at least 0.97, and its overall success probability is at least 2/3.Source: §4.2 · pp. 31–32
5 An existential analogue of verification
Replacing the universal condition in Boolean matrix product verification with an existential row condition yields a harder query problem: row search and graph radius at most two require eΘ(n^3/2) queries, versus eO(n^17/12) for their universal counterparts. The section defines row search, gives its query bounds, and connects it to graph radius through reductions.
5.1 Boolean Matrix Product Row Search
- For a target vector v, Boolean Matrix Product Row Search asks whether some row of A • B equals v; nested quantum searches decide it with O(n^3/2) queries.The tests search over product entries, then columns for a row mismatch, then rows; the bounded-error search method avoids logarithmic error reduction.Source: §5 · p. 32, §5.1 · p. 33
- The all-ones row-search problem requires Ω(n^3/2/√log n) queries, using an encoding of non-surjectivity composed with ORs at the encoded inputs.The construction uses an encoding of length Θ(log n) and OR blocks of size Θ(n/log n).Source: §5.1 · pp. 32–34
5.2 Radius at Most Two
- The graph reductions relate Radius at Most Two to all-ones row search: an augmented adjacency matrix maps radius to row search, and a layered graph gives the reverse reduction.The reverse construction uses row, middle, and column vertices, with auxiliary vertices arranged so only row vertices can be within distance two of every vertex.Source: §5.2 · pp. 34–35
- Row search with the all-ones target and Radius at Most Two have quantum query complexity eΘ(n^3/2), while their universal counterparts are decidable with eO(n^17/12) queries.Changing the outermost quantifier from “every” to “some” makes both problems polynomially harder.Source: §5.1 · p. 32, §5.2 · p. 35