5 papers · 1 filter
New bounds on private simultaneous quantum message passing
Uma Girish, Alex May, Natalie Parham +1
In the private simultaneous message (PSM) setting, players obtain inputs and then each send messages to a referee, who should learn but no ot…
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…
Random Unitaries in Constant (Quantum) Time
Ben Foxman, Natalie Parham, Francisca Vasconcelos +1
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work ha…
Quantum circuit lower bounds in the magic hierarchy
Natalie Parham
We introduce the magic hierarchy, a quantum circuit model that alternates between arbitrary-sized Clifford circuits and constant-depth circuits with two-qubit gates ($\textsf{QNC}^…
On the Pauli Spectrum of QAC0
Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos +1
The circuit class was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower…