From the 1 of 5 linked papers with an AI index.
5 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
The paper shows that Dicke states with polylogarithmic weight can be prepared in constant-depth quantum circuits (QAC^0) using limited-width Toffoli and fanout gates, and extends t…
Improved Lower Bounds for QAC0
Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos +1
In this work, we prove the strongest known lower bounds for QAC, allowing polynomially many gates and ancillae. Our main results show that: (1) Depth-3 QAC circuits cannot…
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$…
Constant-Depth Unitary Preparation of Dicke States
Malvika Raj Joshi, Francisca Vasconcelos
Dicke states serve as a critical resource in quantum metrology, communication, and computation. However, unitary preparation of Dicke states is limited to logarithmic depth in stan…