7 papers
Read What Matters: Query-Adaptive Quantization for KV Caches
Siddharth Bhandari, Lucas Gretta, Krishna Balasubramanian +1
KV-cache entries are stored before their future queries are known, but each decoding query needs precision in different places. We study this mismatch using separate budgets for re…
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…
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…
Sharp Noisy Binary Search with Monotonic Probabilities
Lucas Gretta, Eric Price
We revisit the noisy binary search model of Karp and Kleinberg, in which we have coins with unknown probabilities that we can flip. The coins are sorted by increasing $p_…