In the graph collision problem, the task is to decide whether a known graph on $n$ vertices contains an edge with both endpoints marked, given query access to the input bits specifying the marked vertices. We first refute the conjectured $\Omega(n^{2/3})$ query lower bound with a bounded error quantum algorithm using $...
A. Cornelissen, Amin Shiraz Gilani, Shiva Kintali et al.· 0 citations
We study the quantum query complexity of several basic graph problems. 1) We prove a tight $\Theta(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a...
Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro et al.· 2 citations· ⚡1
This work proves the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of subgraph detection, and proves an all-ones certificate from a known family when the input bits are sampled independently.
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 o...
Amin Shiraz Gilani, François Le Gall, Xing-Yu Zhou· 0 citations
We study exact learning with membership queries for concept classes $\mathcal C\subseteq\{0,1\}^N$, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted $\mathsf{D}(\mathcal C)$, $\mathsf{R}(\mathcal C)$, and $\mathsf{Q}(\mathcal C)$, respectively. The two canonic...
S. Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande· 1 citation
Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total fun...