Quantum algorithms reduce queries for verifying boolean matrix products
Improved Quantum Query Bounds for Boolean Matrix Product Verification
Data Structures and Algorithms
Summary
Verifying whether a product of two true-or-false (Boolean) matrices is correct is a fundamental problem with applications in computer science. The authors improved quantum algorithms that check this by reducing the number of queries needed to confirm the result, making the verification more efficient. They connected this problem to a related challenge called Orthogonal Vectors and established new limits on how fast quantum verification can be done. Their work also shows a clear difference in quantum complexity for related graph problems, helping us understand what quantum computers can do better.
What this means in practice
- •For quantum algorithm developers: Design quantum verification methods for matrix computations that need fewer queries, improving efficiency in quantum algorithm implementations.
- •For graph algorithm engineers: Use the complexity separation between graph radius and diameter problems to better allocate resources for quantum graph analytics and optimization.
A theory result. No direct application yet.
Authors
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.