4 papers
Shor's algorithm requires Fanout
Lucas Gretta, Malvika Raj Joshi
Shor's algorithm is a canonical quantum supremacy target whose core operation relies on the Quantum Fourier Transform (QFT). In this note, we resolve an open question of Fang, Fenn…
Polylogarithmic-Weight Dicke States in QAC and Arbitrary Symmetric States in QAC
Lucas Gretta, Meghal Gupta, Malvika Raj Joshi
An -qubit Dicke state of weight , is the uniform superposition over all -bit strings of Hamming weight . Dicke states are central to quantum algorithms exhibiting speed…
Parity QAC0 QAC0 is Fourier-Concentrated
Lucas Gretta, Meghal Gupta, Malvika Raj Joshi
A major open problem in understanding shallow quantum circuits (QAC) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC$…
More Efficient -wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
Lucas Gretta, William He, Angelos Pelecanos
We prove that the permutation computed by a reversible circuit with random -bit gates is -approximately -wise independen…