3 papers
quant-ph2026
Superlinear Quantum Query Lower Bounds for Subgraph Detection
Amin Shiraz Gilani, Xingyu Zhou
Subgraph detection asks whether an -vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph . We prove the first unconditional superl…
quant-ph2026
Improved Quantum Query Bounds for Boolean Matrix Product Verification
Amin Shiraz Gilani, François Le Gall, Xingyu Zhou
We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification (), answering a longstanding open question in quan…
quant-ph2024
Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding
Amin Shiraz Gilani, Daochen Wang, Pei Wu +1
The edge list model is arguably the simplest input model for graphs, where the graph is specified by a list of its edges. In this model, we study the quantum query complexity of th…