4 papers
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…