3 papers
quant-ph2025
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…
quant-ph2025
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…
quant-ph2025
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}^…