4 papers
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}^…