16 citations · 19 across the 4 of their papers we have counts for
14 papers
A Quantum Lower Bound for Triangle Finding
Arjan Cornelissen, Amin Shiraz Gilani, Xingyu Zhou
Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For -vertex graphs given by their…
Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard
Joseph Carolan, Andrew M. Childs, Matthew Coudron +3
In the welded trees problem, an algorithm navigates a randomly labeled graph formed from two binary trees joined at their leaves through a "weld" of connecting edges. A quantum wal…
Breaking the quantum barriers for Graph Collision
Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali +3
In the graph collision problem, the task is to decide whether a known graph on vertices contains an edge with both endpoints marked, given query access to the input bits specif…
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…
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…
Optimal Quantum-Classical Separations for Exact Learning
Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande
We study exact learning with membership queries for concept classes , focusing on the relationships among their deterministic, randomized, and quantum…
Quantum Query Complexity Beyond the Worst Case
Srinivasan Arunachalam, Yanlin Chen, Amin Shiraz Gilani
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…
A quantum lower bound for path finding in welded trees
Joseph Carolan, Andrew M. Childs, Matthew Coudron +1
In the welded tree problem, an algorithm is tasked with navigating a graph formed from two binary trees joined at the leaves through a ``weld'' of connecting edges. A quantum walk…
Quantum algorithms for path and cycle containment problems
Arjan Cornelissen, Amin Shiraz Gilani, Subhasree Patro
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph is present in an input graph , has been the subject of considerable study.…
An Improved Quantum Algorithm for 3-Tuple Lattice Sieving
Lynn Engelberts, Yanlin Chen, Amin Shiraz Gilani +3
The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP…
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…
Quantum advantage and lower bounds in parallel query complexity
Joseph Carolan, Amin Shiraz Gilani, Mahathi Vempati
It is well known that quantum, randomized and deterministic (sequential) query complexities are polynomially related for total boolean functions. We find that significantly larger…
Quantum algorithms and the power of forgetting
Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani
The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm. Given the na…
Unlimited non-causal correlations and their relation to non-locality
Ämin Baumeler, Amin Shiraz Gilani, Jibran Rashid
Non-causal correlations certify the lack of a definite causal order among localized space-time regions. In stark contrast to scenarios where a single region influences its own caus…