About

I am an Assistant Professor in the Computer Science and Engineering and Mathematics departments at the University of California, San Diego. My research is in quantum complexity theory, focusing on near-term quantum computing paradigms and proving that they exhibit some kind of quantum advantage over their classical counterparts.

Research topics

• Computer Science
• Discrete mathematics
• Physics
• Algorithm
• Mathematical analysis
• Quantum mechanics
• Applied mathematics
• Mathematics

Selected publications

• $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)

  ArXiv.org · 2026-01-06

  articleOpen access1st authorCorresponding

  $\mathsf{QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical $\mathsf{AC}^0$ lower bounds to $\mathsf{QAC}^0$ have failed. We give one possible explanation of this: $\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ for decision problems, which also resolves for the first time whether $\mathsf{AC}^0$ could be more powerful than $\mathsf{QAC}^0$. Moreover, we prove that $\mathsf{QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.

  PublisherOA PDF

• $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)

  arXiv (Cornell University) · 2026-01-06

  preprintOpen access1st authorCorresponding

  $\mathsf{QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical $\mathsf{AC}^0$ lower bounds to $\mathsf{QAC}^0$ have failed. We give one possible explanation of this: $\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ for decision problems, which also resolves for the first time whether $\mathsf{AC}^0$ could be more powerful than $\mathsf{QAC}^0$. Moreover, we prove that $\mathsf{QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.

  PublisherDOI

• Streaming quantum state purification for general mixed states

  ArXiv.org · 2025-03-28

  preprintOpen access1st authorCorresponding

  Given multiple copies of a mixed quantum state with an unknown, nondegenerate principal eigenspace, quantum state purification is the task of recovering a quantum state that is closer to the principal eigenstate. A streaming protocol relying on recursive swap tests has been proposed and analysed for noisy depolarized states with arbitrary dimension and noise level. Here, we show that the same algorithm applies much more broadly, enabling the purification of arbitrary mixed states with a nondegenerate principal eigenvalue. We demonstrate this through two approaches. In the first approach, we show that, given the largest two eigenvalues, the depolarized noise is the most difficult noise to purify for the recursive swap tests, thus the desirable bounds on performance and cost follow from prior work. In the second approach, we provide a new and direct analysis for the performance of purification using recursive swap tests for the more general noise. We also derive simple lower bounds on the sample complexity, showing that the recursive swap test algorithm attains optimal sample complexity (up to a constant factor) in the low-noise regime.

  PublisherOA PDFDOI

• Tight bounds on depth-2 QAC-circuits computing parity

  ArXiv.org · 2025-04-08

  preprintOpen access

  We show that the parity of more than three non-target input bits cannot be computed by QAC-circuits of depth-2, not even uncleanly, regardless of the number of ancilla qubits. This result is incomparable with other recent lower bounds on constant-depth QAC-circuits by Rosenthal [ICTS~2021,arXiv:2008.07470] and uses different techniques which may be of independent interest: 1. We show that all members of a certain class of multivariate polynomials are irreducible. The proof applies a technique of Shpilka & Volkovich [STOC 2008]. 2. We give a tight-in-some-sense characterization of when a multiqubit CZ gate creates or removes entanglement from the state it is applied to. The current paper strengthens an earlier version of the paper [arXiv:2005.12169].

  PublisherOA PDFDOI

• Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

  ArXiv.org · 2025-10-09

  articleOpen access1st authorCorresponding

  We construct a family of distributions $\{\mathcal{D}_n\}_n$ with $\mathcal{D}_n$ over $\{0, 1\}^n$ and a family of depth-$7$ quantum circuits $\{C_n\}_n$ such that $\mathcal{D}_n$ is produced exactly by $C_n$ with the all zeros state as input, yet any constant-depth classical circuit with bounded fan-in gates evaluated on any binary product distribution has total variation distance $1 - e^{-Ω(n)}$ from $\mathcal{D}_n$. Moreover, the quantum circuits we construct are geometrically local and use a relatively standard gate set: Hadamard, controlled-phase, CNOT, and Toffoli gates. All previous separations of this type suffer from some undesirable constraint on the classical circuit model or the quantum circuits witnessing the separation. Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on the work of Bravyi, Gosset, and König (Science, 2018) to separate shallow quantum and classical circuits for relational problems.

  PublisherOA PDFDOI

• Quantum Threshold Is Powerful

  arXiv (Cornell University) · 2024-11-07 · 1 citations

  preprintOpen access1st authorCorresponding

  In 2005, Høyer and Špalek showed that constant-depth quantum circuits augmented with multi-qubit Fanout gates are quite powerful, able to compute a wide variety of Boolean functions as well as the quantum Fourier transform. They also asked what other multi-qubit gates could rival Fanout in terms of computational power, and suggested that the quantum Threshold gate might be one such candidate. Threshold is the gate that indicates if the Hamming weight of a classical basis state input is greater than some target value. We prove that Threshold is indeed powerful - there are polynomial-size constant-depth quantum circuits with Threshold gates that compute Fanout to high fidelity. Our proof is a generalization of a proof by Rosenthal that exponential-size constant-depth circuits with generalized Toffoli gates can compute Fanout. Our construction reveals that other quantum gates able to "weakly approximate" Parity can also be used as substitutes for Fanout.

  PublisherOA PDFDOI

• Principal eigenstate classical shadows

  arXiv (Cornell University) · 2024-05-22 · 1 citations

  preprintOpen access1st authorCorresponding

  Given many copies of an unknown quantum state $ρ$, we consider the task of learning a classical description of its principal eigenstate. Namely, assuming that $ρ$ has an eigenstate $|ϕ\rangle$ with (unknown) eigenvalue $λ> 1/2$, the goal is to learn a (classical shadows style) classical description of $|ϕ\rangle$ which can later be used to estimate expectation values $\langle ϕ|O| ϕ\rangle$ for any $O$ in some class of observables. We consider the sample-complexity setting in which generating a copy of $ρ$ is expensive, but joint measurements on many copies of the state are possible. We present a protocol for this task scaling with the principal eigenvalue $λ$ and show that it is optimal within a space of natural approaches, e.g., applying quantum state purification followed by a single-copy classical shadows scheme. Furthermore, when $λ$ is sufficiently close to $1$, the performance of our algorithm is optimal--matching the sample complexity for pure state classical shadows.

  PublisherOA PDFDOI

• Fast simulation of planar Clifford circuits

  Quantum · 2024-02-12 · 6 citations

  articleOpen access

  A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally exponential in the treewidth of the underlying graph. Separately, Gottesman and Knill showed that if all gates are restricted to be Clifford, then there is a polynomial time simulation. We combine these two ideas and show that treewidth and planarity can be exploited to improve Clifford circuit simulation. Our main result is a classical algorithm with runtime scaling asymptotically as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>&amp;#x03C9;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>&amp;#x003C;</mml:mo></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1.19</mml:mn></mml:mrow></mml:msup></mml:math> which samples from the output distribution obtained by measuring all <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> qubits of a planar graph state in given Pauli bases. Here <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&amp;#x03C9;</mml:mi></mml:math> is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. Our work improves known classical algorithms with cubic runtime.A key ingredient is a mapping which, given a tree decomposition of some graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>G</mml:mi></mml:math>, produces a Clifford circuit with a structure that mirrors the tree decomposition and which emulates measurement of the corresponding graph state. We provide a classical simulation of this circuit with the runtime stated above for planar graphs and otherwise <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi><mml:msup><mml:mi>t</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>&amp;#x03C9;</mml:mi><mml:mo>&amp;#x2212;</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:math> where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>t</mml:mi></mml:math> is the width of the tree decomposition. Our algorithm incorporates two subroutines which may be of independent interest. The first is a matrix-multiplication-time version of the Gottesman-Knill simulation of multi-qubit measurement on stabilizer states. The second is a new classical algorithm for solving symmetric linear systems over <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="double-struck">F</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:math> in a planar geometry, extending previous works which only applied to non-singular linear systems in the analogous setting.

  PublisherOA PDFDOI

• Improved classical shadows from local symmetries in the Schur basis

  arXiv (Cornell University) · 2024-05-15

  preprintOpen access1st authorCorresponding

  We study the sample complexity of the classical shadows task: what is the fewest number of copies of an unknown state you need to measure to predict expected values with respect to some class of observables? Large joint measurements are likely required in order to minimize sample complexity, but previous joint measurement protocols only work when the unknown state is pure. We present the first joint measurement protocol for classical shadows whose sample complexity scales with the rank of the unknown state. In particular we prove $\mathcal O(\sqrt{rB}/ε^2)$ samples suffice, where $r$ is the rank of the state, $B$ is a bound on the squared Frobenius norm of the observables, and $ε$ is the target accuracy. In the low-rank regime, this is a nearly quadratic advantage over traditional approaches that use single-copy measurements. We present several intermediate results that may be of independent interest: a solution to a new formulation of classical shadows that captures functions of non-identical input states; a generalization of a ``nice'' Schur basis used for optimal qubit purification and quantum majority vote; and a measurement strategy that allows us to use local symmetries in the Schur basis to avoid intractable Weingarten calculations in the analysis.

  PublisherOA PDFDOI

• Sample-optimal classical shadows for pure states

  Quantum · 2024-06-17 · 15 citations

  articleOpen access1st authorCorresponding

  We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&amp;#x03C1;</mml:mi></mml:math> in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="normal">T</mml:mi><mml:mi mathvariant="normal">r</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>O</mml:mi><mml:mi>&amp;#x03C1;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> for any Hermitian observable <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi></mml:math> to within additive error <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&amp;#x03F5;</mml:mi></mml:math> provided <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="normal">T</mml:mi><mml:mi mathvariant="normal">r</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>O</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mo>&amp;#x2264;</mml:mo><mml:mi>B</mml:mi></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mi>O</mml:mi><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:math>. Our main result applies to the joint measurement setting, where we show <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi mathvariant="normal">&amp;#x0398;</mml:mi><mml:mo stretchy="false">&amp;#x007E;</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>B</mml:mi></mml:msqrt><mml:msup><mml:mi>&amp;#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&amp;#x2212;</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:msup><mml:mi>&amp;#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&amp;#x2212;</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> samples of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&amp;#x03C1;</mml:mi></mml:math> are necessary and sufficient to succeed with high probability. The upper bound is a quadratic improvement on the previous best sample complexity known for this problem. For the lower bound, we see that the bottleneck is not how fast we can learn the state but rather how much any classical description of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&amp;#x03C1;</mml:mi></mml:math> can be compressed for observable estimation. In the independent measurement setting, we show that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>B</mml:mi><mml:mi>d</mml:mi></mml:msqrt><mml:msup><mml:mi>&amp;#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&amp;#x2212;</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:msup><mml:mi>&amp;#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&amp;#x2212;</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> samples suffice. Notably, this implies that the random Clifford measurements algorithm of Huang, Kueng, and Preskill, which is sample-optimal for mixed states, is not optimal for pure states. Interestingly, our result also uses the same random Clifford measurements but employs a different estimator.

  PublisherOA PDFDOI

Frequent coauthors

• Luke Schaeffer

  41 shared

• Hakop Pashayan

  Freie Universität Berlin

  13 shared

• David Gosset

  Perimeter Institute

  10 shared

• Scott Aaronson

  7 shared

• Miklós Sántha

  6 shared

• Stephen Fenner

  University of South Carolina

  4 shared

• Daniel J. Brod

  Universidade Federal Fluminense

  4 shared

• Thomas Thierauf

  4 shared

Labs

• Daniel Grier LabPI

Education

• B.S., Computer Science and Mathematics

  University of South Carolina

• Ph.D., Computer Science

  MIT