Showing quant-phShow all
3 papers · 1 filter
quant-ph2026
Improved Exact and Approximate Quantum Fourier Transforms from Multiplication
Chandrima Kayal, Rajat Mittal, Manaswi Paraashar +1
In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorit…
quant-ph2026
Quantum Query Lower Bounds from Classical Moment Matching
Chandrima Kayal, Frédéric Magniez, Sayantan Sen +1
We prove a quantum analogue of the classical moment matching method, a popular framework used to prove lower bounds in property testing. For two random variables and wh…
quant-ph2026
Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
Chandrima Kayal, Sayantan Sen, Dániel Szabó
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexit…