Skip to content

Author

Amin Shiraz Gilani

6 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Nov 2026

Breaking the quantum barriers for Graph Collision

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
Preprint Oct 2026

Quantum Query Complexity of Maximum Degree and its Generalizations

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
Preprint Sep 2026

Superlinear Quantum Query Lower Bounds for Subgraph Detection

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.

Amin Shiraz Gilani, Xing-Yu Zhou · 2 citations
Preprint Sep 2026

Improved Quantum Query Bounds for Boolean Matrix Product Verification

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
#machine learning Preprint Sep 2026

Optimal Quantum-Classical Separations for Exact Learning

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
Preprint Sep 2026

Quantum Query Complexity Beyond the Worst Case

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...

Srinivasan Arunachalam, Yan-Lin Chen, Amin Shiraz Gilani · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.