6 papers
QAC0 Can Prepare Every Logarithmic-Qubit State
Lucas Gretta, Meghal Gupta, Malvika Raj Joshi
is the class of constant-depth -ancilla circuits obtained by extending , the class of local circuits, to include nonlocal interac…
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$…
Nearly Time-Optimal Pure State Tomography with Pauli Measurements
Sabee Grewal, Meghal Gupta, William He +2
We give an algorithm for pure state tomography with near-optimal copy and time complexity using only single-qubit measurements. Specifically, given copies of…
Tight bounds for stream decodable error-correcting codes
Meghal Gupta, Venkatesan Guruswami, Mihir Singhal
In order to communicate a message over a noisy channel, a sender (Alice) uses an error-correcting code to encode her message into a codeword. The receiver (Bob) decodes it corr…
Optimal quantile estimation: beyond the comparison model
Meghal Gupta, Mihir Singhal, Hongxun Wu
Estimating quantiles is one of the foundational problems of data sketching. Given elements from some universe of size arriving in a data stream, a qu…