3 citations · 7 across the 12 of their papers we have counts for
4 papers · 1 filter
Magic and communication complexity
Uma Girish, Alex May, Natalie Parham +1
We establish novel connections between magic in quantum circuits and communication complexity. In particular, we show that functions computable with low magic have low communicatio…
Fourier Spectrum of Noisy Quantum Algorithms
Uma Girish
Quantum computing promises exponential speedups for certain problems, yet fully universal quantum computers remain out of reach and near-term devices are inherently noisy. Motivate…
Forrelation is Extremally Hard
Uma Girish, Rocco Servedio
The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to -bit…
Comparing classical and quantum conditional disclosure of secrets
Uma Girish, Alex May, Leo Orshansky +1
The conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum…