{"id":"arxiv/2609.40180","url":"https://arxiv.org/abs/2609.40180","tags":["quant-ph","cs.DS"],"score":0,"title":"Improved Quantum Query Bounds for Boolean Matrix Product Verification","domain":"quant-ph","source":"arxiv","authors":["Amin Shiraz Gilani","François Le Gall","Xingyu Zhou"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}