Luke Schaeffer

Daniel Grier, Hakop Pashayan, Luke Schaeffer

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 $ρ$ in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate $\mathrm{Tr}(O ρ)$ for any Hermitian observable $O$ to within additive error $ε$ provided $\mathrm{Tr}(O^2)\leq B$ and $\lVert O \rVert = 1$. Our main result applies to the joint measurement setting, where we show $\tildeΘ(\sqrt{B}ε^{-1} + ε^{-2})$ samples of $ρ$ 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 $ρ$ can be compressed for observable estimation. In the independent measurement setting, we show that $\mathcal O(\sqrt{Bd} ε^{-1} + ε^{-2})$ 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.

Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

Let $α$ and $β$ belong to the same quadratic field. We show that the inhomogeneous Beatty sequence $(\lfloor n α+ β\rfloor)_{n \geq 1}$ is synchronized, in the sense that there is a finite automaton that takes as input the Ostrowski representations of $n$ and $y$ in parallel, and accepts if and only if $y = \lfloor n α+ β\rfloor$. Since it is already known that the addition relation is computable for Ostrowski representations based on a quadratic number, a consequence is a new and rather simple proof that the first-order logical theory of these sequences with addition is decidable. The decision procedure is easily implemented in the free software Walnut. As an application, we show that for each $r \geq 1$ it is decidable whether the set $\{ \lfloor n α+ β\rfloor \, : \, n \geq 1 \}$ forms an additive basis (or asymptotic additive basis) of order $r$. Using our techniques, we also solve some open problems of Reble and Kimberling, and give an explicit characterization of a sequence of Hildebrand et al.

Avantika Agarwal, Amolak Ratan Kalra, Sungjai Lee et al.

The quantum capacity captures the value of a quantum channel for transmitting quantum information, establishing the fundamental limits on quantum communication. In spite of its central role in quantum information theory, the quantum capacity of most channels is unknown, with wide gaps between the best upper and lower bounds. Even deciding whether a channel has nonzero capacity -- finding its capacity threshold -- is difficult. In this paper we report significant increases in the capacity thresholds of two prototypical noise models: the depolarizing channel and Pauli channels. In the case of the depolarizing channel, this is the first improvement in 18 years, giving a bigger increase beyond the hashing bound than all previous improvements combined. Our starting point is the representation theoretic framework recently proposed by Bhalerao and Leditzky (2025) to compute coherent information for special permutation invariant states. We generalize their framework to the full symmetric subspace, which allow us to optimize coherent information over rank two states in that space. A representation theoretic calculation shows that exponentially many Kraus operators of the channel annihilate the symmetric space, corresponding to a massive decrease in environment entropy for states on the symmetric space compared to the maximally mixed state. This explains the enhanced coherent information as a manifestation of degeneracy for the resulting codes.

Daniel Grier, Hakop Pashayan, Luke Schaeffer

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.