Improved Quantum Query Bounds for Boolean Matrix Product Verification
Abstract
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 Õ(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.
Related
- Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
- Verification Meets Calibration: Bounds and Secret-Independent State Preparation with an NV-Center as a Case Study
- Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
- Factorized Boolean representations for efficient quantum synthesis
- Practical fermionic shadows enabled by improved sample-complexity bounds
BibTeX
@misc{gilani2026improved,
title = {{Improved Quantum Query Bounds for Boolean Matrix Product Verification}},
author = {Amin Shiraz Gilani and François Le Gall and Xingyu Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.40180},
eprint = {2609.40180},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40180},
}
RIS
TY - UNPB
TI - Improved Quantum Query Bounds for Boolean Matrix Product Verification
AU - Amin Shiraz Gilani
AU - François Le Gall
AU - Xingyu Zhou
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.40180
UR - https://arxiv.org/abs/2609.40180
AB - 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 Õ(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 Ω̃(n^19/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 Θ̃(n^3/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.
ER -