Natalie Parham

How fast can (pseudo)random unitaries be implemented on a quantum computer? O(1) time suffices (provided you can do things like intermediate measurements)! This -and more- is thanks to a superfun collaboration with Ben Foxman, @nat-parham.bsky.social, and @franvasco.bsky.social (all PhD students!).

Random Unitaries in Constant (Quantum) Time 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 has constructed unitar...

In exciting new work with Ben Foxman, @nat-parham.bsky.social , and @henryyuen.bsky.social we show that t-designs and pseudorandom unitaries are implementable in constant (quantum) time!

arxiv.org/abs/2508.11487

Thanks Philippe, that means a lot!

Improved classical simulation of quantum circuits dominated by Clifford gates The Gottesman-Knill theorem asserts that a quantum circuit composed of Clifford gates can be efficiently simulated on a classical computer. Here we revisit this theorem and extend it to quantum circui...

Though, T-count is really nice because a circuit with t T gates can be classically simulated in poly(n, 2^t) time (arxiv.org/abs/1601.07601)

thanks Clément! Vaguely, it refers to non-Clifford circuits or non-stabilizer states. Its typically quantified as T-count, the number of T gates in a circuit with only Clifford and T gates. The level of the MH can be interpreted as a gate-set-agnostic notion of magic.

In particular, KGP also used that stabilizer states have discrete mutual information, and WL also identified the infectiousness property, proving an exact version. (9/9)

Long-range nonstabilizerness and phases of matter Long-range nonstabilizerness can be defined as the amount of nonstabilizerness which cannot be removed by shallow local quantum circuits. In this work, we study long-range nonstabilizerness in the con...

I'd also like to highlight great recent work by Korbany–Gullans–Piroli (arxiv.org/abs/2502.19504) and Wei–Liu (arxiv.org/abs/2503.04566), who independently proved lower bounds for these circuits from a condensed matter perspective. (8/9)

This is a first step towards what I hope to be increasingly stronger circuit lower bounds beyond the lightcone argument :) (7/9)

Above a certain level, lower bounds for preparing an explicit quantum state would imply breakthrough classical circuit lower bounds—e.g., for depth-4 TC0, rubbing up against the natural proofs barrier. We estimate this threshold is at level ≤97. So theres still lots of room to explore below. (6/9)

We also develop a separate lower bound technique based on mutual information properties of quantum states. (5/9)

A key insight is an infectiousness property: if one of these circuits (Clifford followed by QNC0) can prepare a high-distance code state, the code must essentially be a stabilizer code. So for any non-stabilizer code, we get a lower bound against *all* its codestates.(4/9)

We prove lower bounds in level 1. Clifford circuits followed by QNC0 cannot approximately prepare several explicit quantum states including:
- Feynman-Kitaev history state for the CAT state
- nonstabilizer code states
- groundspaces of some topologically-ordered Hamiltonians
- biased cat state (3/9)

This hierarchy connects naturally to other complexity measures like fanout depth and intermediate measurements. (2/9)

The *magic hierarchy* is a circuit model with alternating layers of Clifford gates and constant-depth (QNC0) circuits. The number of alternations defines the level—capturing a notion of non-stabilizerness, or "magic". (1/9)

I have a new paper out: "Quantum Circuit Lower Bounds in the Magic Hierarchy".🔮🪜
arxiv.org/abs/2504.19966
a thread: