Papers

Fault-tolerant preparation of logical states is a critical primitive for the realization of large-scale fault-tolerant quantum computing. This paper introduces SpiderCSS, a scalable compilation pipeline that generates highly-optimized, fault-tolerant state preparation circuits for arbitrary Calderbank-Shor-Steane (CSS) codes. Starting from an idealized specification of a CSS state, we use the ZX-calculus and fault-equivalent rewrites to construct a diagram that prepares the given state while preserving the fault tolerance of the initial ideal ZX-diagram. From this diagram, SpiderCSS constructs a fault-tolerant CSS-state preparation circuit using a modular construction that is CNOT-minimal both within each component and also in the way these components are connected together. By only using fault-equivalent rewrites, the final circuit is provably fault-tolerant without needing expensive verification. Monte Carlo simulations across a variety of CSS codes up to distance 15 show that SpiderCSS scales efficiently and constructs circuits with substantially reduced depth and qubit footprint compared to existing scalable and heuristic methods, while simultaneously achieving an average decrease of 33.7% in logical error rate and an increase of 9.5% in acceptance rate.

We provide the first evidence relative to a classical oracle that pseudorandom unitaries (PRUs) can exist without quantum-computable one-way functions. To obtain this result, we first prove that five independent random diagonal phase layers interleaved with Hadamard transforms \[ U=F_5HF_4HF_3HF_2HF_1 \] form a strong PRU with security under adaptive, controlled access to the unitary, its inverse, transpose, and complex conjugate. Our main result is that, when the phase layers are implemented using a classical random oracle O, the construction remains secure against uniform BQP adversaries with coherent access to suitable Boolean completions of classical-input $QMA^{PH}^{O}}$ decision problems. Such an adversary can invert (even quantum-computable) one-way functions and solve efficiently verifiable one-way puzzles defined relative to O. Our result therefore provides classical-oracle evidence that PRUs do not imply quantum-computable one-way functions, in the form of a black-box separation. We substantially strengthen the classical-oracle result of Kretschmer, Qian, and Tal (STOC 2025) by obtaining PRUs secure against these QMA-aided adversaries. Our construction also consists of a simple, efficient circuit that queries a random function, suggesting a route to concrete implementation via the random-oracle heuristic.

Recent examples have shown that zero private capacity need not imply antidegradability and that two channels with zero private capacity can nevertheless transmit private information together. Existing entropic channel orders compare what a receiver and its environment can learn and thereby bound capacities. We connect these orders to the recent constructions through binary estimation, whose minimum mean-square error is governed by measured $\chi^2$ divergence. A new integral representation shows how measured $\chi^2$ on a qubit extension recovers quantum $\chi^2$. It lets us pass from complete measured-$\chi^2$ ordering to complete quantum-$\chi^2$, relative-entropy, and less-noisy ordering. Zhu and Wang used a signed lift to show that their qutrit channel has zero private capacity. We show that Hermitian-smoothed measured-$\chi^2$ ordering characterizes when such lifts exist, even with a quantum reference. Environmental dominance in binary estimation at every blocklength yields a finite-code reliability–secrecy bound. These results explain why complete comparison prevents activation with antidegradable helpers whereas regularized comparison alone does not. Building on that qutrit example, we establish this stability for a range of noisy Werner–Holevo channels, determine sharp private-capacity and antidegradability thresholds, and compute exact complementary capacities in a nondegradable range. By contrast, we extend Pauli half-erasure activation to all $1/2\le p<1$ and establish the same range for a new four-level family. Reference-assisted measured-$\chi^2$ witnesses show why these activating constructions lack complete comparison.

We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{NEXP}$. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in $\mathsf{unitaryPSPACE}$ either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for $\mathsf{NEXP}$ search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving $\mathsf{unitaryPSPACE}$ would imply breakthrough classical lower bounds such as $\mathsf{NC} \neq \mathsf{NP}$. Along the way, we propose new definitions for the unitary complexity classes $\mathsf{unitaryP}$ and $\mathsf{unitaryPSPACE}$. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that $\mathsf{unitaryPSPACE}$ has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that $\mathsf{unitaryPSPACE}$ can generically erase garbage, a result that provably fails relative to unitary oracles.

We present a blueprint for implementing the physical QRAM operation in a scalable, passive manner, proving its feasibility in principle. Our construction is passive because for an $n$-qubit address over $N = 2^n$ memory bits the energy cost per QRAM query is $O(\log N)$, and to our knowledge it is the first construction to use $\operatorname{polylog} N$ energy. The runtime for each query is $O(\log^2 N)$. It is achieved by evolving a pre-manufactured time-independent 4-local Hamiltonian with $O(N)$ terms where every qubit participates in at most 4 terms.

Recent algorithms for classical simulation of quantum mechanics have runtime whose superpolynomial component is given by a linear dependence on the number of terms required to write large tensor products of certain "magic" states as superpositions of "free" states (which may be stabilizer states, fermionic Gaussian states or others). Surprisingly little is known about the number of terms in such decompositions, called ranks (e.g. the stabilizer rank, fermionic-Gaussian rank etc.). For complexity theoretic reasons they are expected to grow exponentially in the number of tensor factors but, while exponential upper bounds are known for both the stabilizer and fermionic-Gaussian rank of magic states; the best known lower bounds on the stabiliser rank are quadratic, and no bounds on the fermionic-Gaussian rank are known beyond fixed constants. In this work we prove that any fermionic Gaussian decomposition of $\lvert M\rangle^{\otimes k}$ consists of $\Omega(1.4^k)$ terms. Here $\lvert M\rangle$ is the most standard magic state for fermionic linear optics: the $4$ qubit state that may be consumed to implement a swap gate. We also prove essentially matching bounds on the $\delta$-approximate rank of the same state, lower bounding it by the same quantity that bounds the exact rank, multiplied by a factor of $1-\delta^2$. Our results on exact fermionic Gaussian rank apply directly to any product of $k$ fixed parity non-Gaussian states, although the same is not true of the approximate rank. Finally, we prove that the coherent state border rank of an $n$-mode bosonic Fock state with $m_j$ bosons in mode $j$ is exactly $\prod_{j}(1+m_j)$, answering a conjecture of Ref. [1] and obtain lower bounds on the approximate coherent state rank given by the same quantity multiplied by a function of the fidelity of the approximation, emphasizing the broad applicability of the method we employ.

We consider a class of redudancy-free Hamiltonians, which are those where the trace vanishes for any product of Hamiltonian terms in which at least one term appears an odd number of times. This includes Hamiltonians which are sums of products of Paulis with no relations between them. These Hamiltonians arise naturally in Hamiltonian Decoded Quantum Interferometry, which separates the hardness of preparing quantum states into two steps: a classical decoding step, and a step preparing the thermofield double state of such a redundancy-free Hamiltonian. We focus on the hardness of these Hamiltonians, both for intrinsic interest and to understand the complexity of the state preparation step in Hamiltonian DQI. We present several results showing that the problem becomes easy at quadratically lower temperature than for a general Hamiltonian, with the complexity at given inverse temperature $\beta$ depending on $\beta^2 d$, where $d$ is the degree of the anticommutation graph. We give an efficient classical algorithm for small $\beta^2 d$ to approximate the partition function, while for large $\beta^2 d$ we show that approximating the partition function is NP-hard. To this end, we introduce what we call an anticommutation glass, where frustration arises purely from anticommutation relations. We give a subexponential time quantum algorithm to prepare the thermofield state for small $\beta^2 d$, and present some results toward a polynomial time algorithm based on the Feiguin-Klich Hamiltonian. As a result of possible independent interest, we show that this Hamiltonian leads to a polynomial time algorithm for preparing thermofield double states of general Hamiltonians on an interaction graph of degree $d$ for $\beta\lesssim 1/d$. Finally, we show that estimating the ground state energy of redundancy-free Hamiltonians is QMA-complete.

Correlation functions are central to understanding the behavior of quantum systems, with their spectra giving direct access to quasiparticle and collective excitations. However, the long-time evolution required for sufficient spectral resolution is challenging to reach for both classical and quantum simulations. In this work, we introduce a principled approach for extending time series of quantum correlation functions and reconstructing their spectral densities, based on their connection with covariance sequences of stationary stochastic processes. This connection enables us to apply Burg's maximum-entropy principle to find the least-committal extension compatible with the measured values of the correlation function, which corresponds to an all-pole autoregressive model whose coefficients solve a set of Yule–Walker equations. The resulting extension is positive semi-definite by construction, guaranteeing the positivity of the spectrum and the automatic satisfaction of its total spectral weight sum rule. The approach applies to both scalar and matrix-valued correlation functions, including those with highly structured or continuous spectra. The generalization to the matrix case makes it possible to trade simulation time for additional measured correlation functions, enabling accurate time-series extension and spectral reconstruction from short-time data, even in the presence of noise.

A key goal in the foundations of quantum mechanics is to identify operational constraints characterizing physical theories. Bell inequalities do so for classical probability theory, while Tsirelson's bound provides a first step for quantum mechanics. Here, we address the dual question: Can one certify that all correlations predicted by quantum theory are actually realizable? In this work, we construct a finite number of two-body correlations such that the only probabilistic theory that (1) realizes them, and (2) does so in a way that is stable under iterated teleportation, is quantum theory. For $n$ quantum systems of dimension $d$ each, Condition (1) can be verified using $\operatorname{poly}(d,n)$ measurement settings. Condition (2) may be understood as a hierarchy of tests, one for each number $N$ of teleportation steps. There is thus a sense in which finite-dimensional quantum theory can be self-tested. In particular, one can certify the existence of Bell inequality violations larger than any that have been directly observed.

How much can the action of an unknown unitary dynamics on one family of states reveal about its action elsewhere? We develop a general framework for out-of-distribution quantum dynamics learning based on the first and second moments of the input distribution. These define a notion of the bias and expressivity of an ensemble, which together control generalization between arbitrary pure-state training and testing distributions. Our framework shows that only studying the action of a unitary on random real states can learn its action on random complex states, that tensor products of unbiased pure-state ensembles preserve expressivity, and that single-qubit risks are independent of bias. It also recovers earlier locally scrambling results as loose special cases and yields tight product-to-Haar bounds. We conclude with a series of no-go results and limited generalization bounds for learning certain channels, which further serve to underscore the distinctive role of unitarity in enabling out-of-distribution generalization.

In fault-tolerant block encodings of structured Hamiltonians, the support geometry can set how the non-Clifford cost of SELECT scales with the system size, however many operators act on each support. We construct permute-act-unpermute circuits: a CSWAP network fixed by this geometry brings a selected support to a fixed target register, a shared local circuit acts there, and the permutation is undone. The operators add only an $XZ$ mask on this register, at a cost independent of the system size, and one query can mix several support geometries. For two-site supports, we establish and attain the minimum CSWAP count within address-controlled networks of site transpositions. Compiled for Pauli terms, these circuits use $8\mathrm{S}N+o(N)$ $T$ gates with $O(\log N)$ permutation work qubits, where $N$ is the number of system qubits and $\mathrm{S}$ is determined by the support geometry, with $\mathrm{S}=1$ for nearest-neighbour interactions and $\mathrm{S}=3/2$ for all-to-all pairs; in both cases the correction is $O(\log N)$. We also introduce a bridged CSWAP, which remembers the logical value of its temporary AND across the target action and repairs it from the prepared labels, so that the inverse CSWAP undoes the exchange without recomputing the value. When the repair is Clifford, it halves the $T$ count of a matched forward-inverse CSWAP pair at the cost of one retained work qubit. For a Heisenberg ring, the complete block-encoding query reduces the $T$ count by a factor approaching $3$ as the system size grows, relative to flat and product-wise Pauli walks. For a five-orbital Anderson impurity model, which combines nearest-neighbour and all-to-all support geometries, the reduction is about $1.7$ at large bath sizes, relative to the cheapest of three comparators, each built from the methods of the references it follows.

Recent work established that, for independent erasures, storing $K$ logical qubits for $S$ time steps with error at most $\varepsilon$ requires a spacetime cost of $\Omega(S(K+\log(S/\varepsilon)))$. A matching construction was also given, but assumes ideal error correction. Here we show that the same scaling can be achieved with an explicit noisy error-correction circuit and efficient decoding, counting all state-preparation, gate, measurement, and wait locations, provided that the hardware supports long-range qubit connectivity and fast, reliable classical processing. Thus, reliability adds only a logarithmic overhead shared by all stored qubits. The construction works for sufficiently weak but otherwise general circuit noise, including faults during syndrome extraction and correlated faults, and for independent erasures it matches the best known lower bound up to constant factors. We attain this scaling using quantum Tanner codes, with each memory step consisting of one round of syndrome extraction followed by a fixed number of parallel classical decoder steps that reduce the residual error enough to keep later faults correctable, regardless of memory size, storage time, or target accuracy. Together, this gives exponentially small failure probability per step while keeping the cost of each memory step linear in the code size. The same analysis also extends to certain constant-depth logical Clifford operations.

Given a finite-range, non-commuting Hamiltonian on a 1D chain of finite spins, we prove a modified logarithmic Sobolev inequality with constant $\Omega(1/\log n)$ for the heat-bath dynamics, a quasi-local Gibbs sampler, and for the regularised heat-bath dynamics. This implies rapid mixing of both samplers towards the Gibbs state in relative entropy and trace norm, with mixing times of order $\mathcal{O}(\log n\cdot \log(n/\epsilon))$. The interactions may be spatially inhomogeneous. The proof combines weak quasi-factorisation of relative entropy, decay-of-correlation estimates, a uniform conditional local gap, and a buffered comparison between conditional entropy and quadratic energy. The resulting bounded entropy defect is removed using the global gap. To the best of our knowledge, this is the first proof of MLSI in the non-commuting regime.

Realizing practical quantum computers requires quantum error correction, but the most widely implemented approach, the planar surface code, demands a substantial physical qubit overhead. Here, we demonstrate that partitioning quantum processors into manageable, flat modules with non-local inter-module connections provides a natural solution. By wiring sparse, static boundary connections between Euclidean planar modules, we construct modular hyperbolic surface and color codes, based on new families of semi-hyperbolic codes. Using modular syndrome extraction circuits and efficient neural network and matching decoders, our circuit-level simulations show that this modular memory design can reduce the physical qubit overhead by tenfold or more compared to the surface code, even under elevated inter-module seam error rates. Projecting to larger system sizes, we find modular codes with encoding rate $k/n=1/16$ and distance $d\geq 22$, exceeding both the rate and distance of the $[[288,12,18]]$ two-gross bivariate bicycle code while using mostly nearest-neighbor gates within planar modules, and implying an over $30\times$ overhead reduction relative to surface codes. We develop fault-tolerant walking circuits for implementing logic via code automorphisms, which we co-design with low-weight, highly symmetrical logical bases and a modular extractor system that is $\approx 4.5\times$ smaller than the code itself. Combining these methods, our modular memory can be used as dense storage in a universal fault-tolerant architecture, unlocking the efficiency of high-rate codes without sacrificing the fabrication advantages of planar modules.

We study exact recovery for non-Abelian topological surface codes based on the quantum double $D(G)$ of any finite group $G$. We determine an orthogonal error basis, that is comprised of group multiplication and irreducible representation operators. Whenever the errors are supported on closed loops on the lattice or dual lattice, there is a redundancy in the basis, due to stabilizers. To remedy this, we introduce a gauge-fixing that results in a complete and orthogonal error basis on the code space. Assuming as input predetermined, neutral correctable error clusters, we construct charge and flux transfer circuits that move the errors onto ancillas that then get projected out. This is an exact and deterministic recovery protocol, applicable to surface codes for any finite, in particular non-Abelian, group $G$.

The Redfield equation with time-dependent coefficients (or TCL2 equation) gives one of the simplest perturbative descriptions of open quantum system dynamics derived from a microscopic theory. Its status as an approximation is nevertheless subtle: while perturbation theory fixes the reduced dynamics order-by-order in the system-environment coupling, solving the Redfield equation yields a particular resummation that need not preserve complete positivity. Here we compare Redfield evolution with an exponentiated (Magnus) resummation of the same second-order perturbative map, which is completely positive and trace preserving (CPTP) for a broad class of physical conditions. We also construct a simple CPTP resolvent resummation, illustrating the non-uniqueness of resummations of the same perturbative map. The Redfield and Magnus prescriptions agree to second order but differ through time-ordering corrections at higher orders. We exhibit a weak-coupling criterion which guarantees that Redfield evolution, even when non-Markovian, remains close to a CPTP map. We illustrate the criterion in two examples, focusing on finite-dimensional (qubit) systems. Our results clarify when, and why, Redfield evolution can remain reliable even when it is highly non-Lindbladian.

While the ultimate limits on the rate of quantum communication over noisy channels are well-established, very few efficient coding schemes achieving these limits are known. This contrasts sharply with transmitting classical data over classical channels, where polar codes and low-density parity-check codes both efficiently achieve the classical capacity of any noisy channel. In this work we construct an efficient entanglement generation scheme which achieves the coherent information for a broad class of channels. For degradable channels in the class, which includes truncated versions of the pure loss Bosonic channel, the resulting scheme achieves the quantum capacity. The construction makes use of polar codes for two kinds of classical-input, quantum-output (CQ) channels: those with commuting outputs and those whose outputs are heralded mixtures of pure states. The former case is amenable to decoding by classical polar decoding algorithms, the latter by the belief propagation with quantum messages (BPQM) algorithm. To our knowledge, this construction is the first explicit and efficiently decodable protocol that achieves the energy-constrained quantum capacity of the pure-loss Bosonic channel.

We investigate algorithms for the quantum simulation of the Schrödinger equation on a Riemannian manifold, where the kinetic operator is defined by the Laplace–Beltrami operator corresponding to the metric. Our first algorithms are based on a global spectral method based on the identification of an efficient transform to the eigenbasis of the Laplace–Beltrami operator. We use this method to provide explicit, efficient, quantum simulation algorithms for the Riemannian Schrödinger equation on tori and spheres with their standard metrics, simplices with the Wright–Fisher metric, truncated positive orthants and their invertible affine images with the log-barrier Hessian metric, and $\ell_p$ balls with a metric induced by the Duffy map. Our second algorithm is based on a coherent simulation of local spectral methods on multiple charts, and is in principle applicable to any compact manifold. We first analyze this algorithm in the continuum and derive conditions under which a polynomial spectral cutoff suffices. We also provide a discretization analysis of a polynomial spectral cutoff for tensor-products of constant-dimensional manifolds. Finally, we consider applications of these methods to optimization and physical simulation. For optimization, we provide results including a generalization and convergence analysis of Quantum Hamiltonian Descent for geodesically convex functions that leads to explicit algorithms on the sphere and simplex, and a Riemannian generalization of the Real-Space Adiabatic Algorithm. For physical simulation, we show that our algorithms can simulate certain spatially discretized field theories, including a variant of the nonlinear sigma model.

Product formulas are a basic tool for simulating quantum many-body dynamics, but a fundamental degree of freedom in their application—the ordering of Hamiltonian terms—has remained largely unexplored. Here we systematically study such ordering effects, quantifying their impact on simulation accuracy and exploiting them to design more accurate product-formula simulations. We develop an efficiently computable, ordering-sensitive bound on the finite-step-size Trotter error for geometrically local Hamiltonians for arbitrarily high-order product formulas. For translation-invariant one-dimensional chains, our bounds are close to exact second-, fourth-, and sixth-order Trotter errors in small-system tests, while on large-scale systems they improve on previous higher-order analytical bounds by orders of magnitude. We further use the local structure of the error bounds and estimates to optimize ordering efficiently, reducing the long-chain problem to a minimum-mean-weight-cycle problem on a weighted de Bruijn graph. For random translation-invariant chains, sequential (staircase-like) orderings consistently outperform standard brickwall circuits; when circuit depth is restricted, the optimizer instead favors wave-like parallel-sequential orderings, which preserve much of the accuracy advantage over brickwall circuits. These results establish ordering as a useful degree of freedom for both understanding and improving product-formula simulation.

The collective excitation spectra of quantum magnets provide a direct test of quantum computers as tools for studying strongly correlated matter. Hardware noise limits the circuit depths available for these calculations, leaving the question of how much magnetic information can survive circuit compression. Using IonQ's 36 qubit Forte Enterprise processor, we simulate the magnetic excitation spectra and spin dynamics of a 36 site Heisenberg XXZ chain describing the quantum magnet Cs2CoCl4 in a transverse field using quantum circuits containing just 420 two qubit gates. The workflow combines an ancilla free local kick protocol with classical tensor network compression, encoding both ground state preparation and time evolution. The reconstructed dynamical structure factors capture the evolution from a broad two spinon continuum toward a dispersive branch with magnon character near the expected critical field. We observe an interesting field driven sign reversal of the nearest neighbor spin correlations which shows a complementary signature of this magnetic evolution. Our error mitigation methods bring the reconstructed total spectra into close agreement with density matrix renormalization group calculations, with Pearson correlation and structural similarity above 0.9 and normalized mean squared error below 0.15. We also perform comparisons with experimental inelastic neutron scattering measurements to connect the recovered excitations to the material's magnetic response. Our results demonstrate that circuit compression and error mitigation allow noisy quantum processors to recover both collective excitations and local magnetic correlations providing a quantitative benchmark for quantum spectroscopy and a basis for extending these methods to more complex magnetic systems.

Quantum Max-Cut is a well-studied local Hamiltonian problem for which the classical complexity of the bipartite case remains open. We give a polynomial-time classical randomized algorithm for the spin-$\tfrac12$ antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes $G(n,n,p)$ with high probability for every fixed $p>0$. The algorithm estimates the ground energy and any ground state edge correlation to additive error $\varepsilon$ in time polynomial in $n$ and $1/\varepsilon$. We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.

Linear combination of Hamiltonian simulation (LCHS) provides an asymptotically optimal framework for the quantum simulation of linear non-unitary dynamics. The LCHS approach approximately implements the Peano–Baker propagator through an integral representation determined by a kernel function. We establish an LCHS approximation theorem for a broadened class of admissible kernel functions, defined by natural complex-analytic conditions. In the standard time-independent block-encoding access model, we explicitly construct, for each target error $\varepsilon$, the unique kernel function in this class minimizing the query-cost functional and show that the minimum of this functional has the asymptotic expansion $\tfrac{2\mathrm{e}}{\pi}\big(\log\frac{1}{\varepsilon}-\log\log\frac{1}{\varepsilon}+o(1)\big)$ as ${\varepsilon\downarrow0}$. The provably optimal leading coefficient $2\mathrm{e}/\pi$ improves by a factor of approximately 2.1 on the coefficient obtained empirically by Low and Somma through numerical minimization over their family of optimally scaling kernel functions. We construct a spectrally convergent quadrature with explicit bounds on operator error and linear combination of unitaries (LCU) subnormalization, proving that this asymptotic improvement persists after discretization into a finite linear combination of unitaries suitable for implementation. Our results are based on Hardy space theory and convex analysis.

We introduce an algebraic framework for constructing a new class of quantum error-correcting codes, bosonic algebraically-restricted constellation (BARC) codes. The code states are finite superpositions of coherent-state constellations constrained by symmetries of solution sets to multivariate complex polynomial systems. The constraints are associated with photon-gain and photon-loss errors, thereby imposing approximate Knill–Laflamme conditions for such errors. For equally-weighted constellation points, we derive upper bounds on the minimum geometric separation between points, indicating how noise-resilient the code is. In the single-mode case, we characterize degree-two polynomial solution sets using an orthogonal group symmetry to obtain explicit ellipsoidal and hexagonal BARC codes. We benchmark representative instances of these families against spherical and cubature codes using the entanglement fidelity with optimal recovery under pure-loss noise.

Uncertainty relations impose fundamental constraints on quantum observables, yet optimal bounds are needed to determine their incompatibility through the minimum attainable uncertainty. Here we introduce a covariance-matrix formulation from which infinitely many uncertainty relations follow, encompassing Hermitian observables and non-Hermitian operators and recovering the variance sum as a special case. Within this family, a basis-independent uncertainty for simple and semisimple Lie algebras admits an exact solution: its optimal state-independent bound is an explicit pairing of root system with the highest weight of the representation. The minimum is attained by a highest-weight state, replacing a search over quantum states with a calculation in representation theory. A complementary result establishes that uncertainty is constant within each weight space, yielding a conservation law. The same commutation relations can therefore support distinct uncertainty limits, depending on their realization on the state space. By rendering these limits analytically accessible, the framework turns representation theory into a tool for quantifying quantum incompatibility and may help establish the boundary between attainable and impossible tasks in quantum theory.

Consider the task of identifying an unknown classical codeword delivered to a register of quantum sensor qubits through a sequence of weak phase interactions that each encode one bit. Suppose that each received bit controls an identical $Z$-rotation of angle $\theta$ applied to every sensor qubit; receivers may also use auxiliary qubits within a total qubit budget $Q$, with arbitrary control unitaries and entanglement among all qubits allowed during each reception step. When the total collected signal is weak ($Q\theta \rightarrow 0$), we establish that a sensor coupled to a persistent quantum memory can identify the original codeword more reliably than any receiver with the same $Q$ and $\theta$ but only classical memory between received bits, even when bit flips occur during transmission. In particular, for a family of $[n,k]$ binary simplex codes with even $k$ and $n=2^k-1$, we achieve exact correction of up to $t\leq(k-2)/4$ transmission errors by coupling the sensor register to a persistent quantum memory of the same size, using $Q = \Theta((t+1)\log n)$ and $\theta=\frac{2\pi}{k\sqrt{n+1}}$; for $t=o(\sqrt k)$, every comparable receiver with only classical memory instead has average success probability (over uniformly chosen codewords) tending to zero. Furthermore, under independent bit flips of any fixed probability $p<1/16$, our receiver with persistent quantum memory achieves decoding error tending to zero as $n\to\infty$ using $Q=O(\log n\log\log n)$ total qubits and the same $\theta$. In contrast, every otherwise equivalent receiver with only classical memory has vanishing average success probability under the same stochastic error model.

In this note, we consider tomography of $n$-qubit quantum states $|\psi \rangle$ that are promised to have stabilizer rank $k$ i.e., admit a stabilizer decomposition of $|\psi\rangle = \sum_{i=1}^k c_i |\phi_i\rangle$ where each $|\phi_i\rangle$ is a stabilizer state. We give a tomography protocol for such states up to trace distance $\varepsilon > 0$ running in $\textsf{poly}(n,2^k,1/\varepsilon)$ time and thus can handle $k=O(\log n)$ efficiently. This follows from first showing that the stabilizer extent $\xi(|\psi\rangle)$, which is the minimal $\ell_1$ norm over the coefficients $\{c_i\}$ of any stabilizer decomposition of $|\psi\rangle$, can be bounded as $\xi(|\psi\rangle) \leq 2^{O(k)}$ and improving upon the previous best bound of $k^{O(k)}$. The protocol is then obtained by utilizing a tomography protocol for states with bounded stabilizer extent.

A paradigmatic task in quantum metrology is that of phase estimation. For this task it is commonly believed, under reasonable assumptions about prior information, that a quadratic advantage in sensitivity is the maximum possible advantage offered by the use of quantum resources. In this work, we consider a channel that implements a phase shift by an angle $2\pi k/M$, where $k$ is a uniformly random unknown integer, in addition to a small unknown phase shift of interest. We show that, subject to a constraint on the mean photon number per channel use, there is a super-exponential separation between the quantum Fisher information (QFI) attainable using a squeezed vacuum state and that attainable using coherent states. This advantage holds over any state obtained from a coherent state via phase covariant channels. Specifically, when the mean photon number per channel use is 1, the ratio of their QFI grows as $\Omega[(M/\sqrt{2}e)^M]$. For a mean photon number per channel use of $M/\log(M)$, the squeezed vacuum QFI is $\Omega(M^{3/2}/\sqrt{\log(M)})$, whereas for a coherent state it is at most $\exp[-M\log\log(M)+O(M)]$. We complement this QFI analysis with non-asymptotic estimation results. For a mean photon number per channel use of $M/\log M$, an explicit squeezed-vacuum protocol estimates the phase to accuracy $O(1/M)$ using $O(\sqrt{M\log M})$ channel uses, whereas every coherent state protocol requires at least $\exp[M\log\log M-O(M)]$ channel uses. We consider the effects of noise and show that the ratio of their QFIs can still grow super-exponentially in $M$. Finally, under fixed optical loss and thermal noise, choosing $\bar n=M^2/(\log M)^{3/2}$ allows squeezed vacuum with heterodyne detection to achieve accuracy $O(1/M)$ using sub-polynomially many channel uses, whereas every protocol in the specified classical family requires super-polynomially many.

The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy $\epsilon$ in $\text{polylog}(1/\epsilon)$ time using any universal gate set. While Solovay and Kitaev's initial work addressed inverse-closed gate sets, recently Bouland and Giurgicǎ-Tiron showed it is possible to efficiently compile arbitrary gate sets without inverses. However, the exponent of their compilation algorithm is high. For example the inverse-free exponent for a qubit is over $8.62$, while information theoretically it is known that an inverse-free exponent of $3$ is possible in any dimension by a result of Oszmaniec, Sawicki, and Horodecki. This leads to a natural question: can one improve the exponent in Bouland and Giurgicǎ-Tiron's algorithm? And are there any cases where the inverse-free exponent is below 3, thus surpassing existing information-theoretic arguments? To answer this question, we first show that a special case of the inverse-free compiling problem – namely Pauli gates supplemented by an irrational rotation of a qubit - admits a highly efficient compilation algorithm with an exponent at most $\approx 2.138$. Our algorithm fuses ideas from prior algorithms of Kuperberg and Sardharwalla, Cubitt, Harrow and Linden to construct an efficient “Pauli golf” compilation routine. We then extend these ideas to the general inverse-free case for a qubit, where we give a compiling algorithm with exponent at most $2.988$. This result uses a novel form of approximate “aiming” of unitary corrections to improve the compilation efficiency. Our results give two examples of quantum compiling algorithms surpassing information-theoretic arguments, and demonstrate that there are many efficiency gains possible for inverse-free compilation.

Sample-based quantum diagonalization can reduce the classical cost of many-body calculations by restricting diagonalization to configurations identified through quantum sampling, but its efficiency depends on how compactly the target state is represented in the sampled basis. We investigate this dependence for sample-based Krylov quantum diagonalization of the half-filled Fermi-Hubbard ladder using physically motivated one-body orbital rotations. Across position, momentum, bonding/antibonding, and leg-mode representations, the most compressible basis varies systematically with interaction strength and hopping anisotropy, with momentum sampling favored in the weakly interacting regime and geometry- or interaction-adapted representations becoming advantageous as the dominant energy scale changes. Near intermediate interaction and isotropic hopping, however, even the most favorable representation remains poorly compressible. Statevector SKQD calculations further show that basis choice strongly affects sampling efficiency. Hardware calculations on systems containing up to 120 qubits retain qualitative signatures of this basis dependence while revealing increasing particle-number leakage and reconstruction sensitivity with system size. These results show that scalable sample-based diagonalization requires co-design of the sampled representation, quantum circuit, and classical reconstruction procedure.

We investigate the physical requirements to reach the ultimate limits of ground-state metrology – i.e., the estimation of an unknown parameter $\theta$ of an $N$-body Hamiltonian via measurements on its ground state – using many-body probes featuring either short-range or long-range interactions. We characterize the conditions to saturate two fundamental limits of the quantum Fisher information $F_\theta$: the static ground-state bound $F_\theta \lesssim N^2/\Delta^2$, where $\Delta$ is the spectral gap, and the dynamical Heisenberg limit $F_\theta \lesssim N^2 \tau^2$, where $\tau$ is the total protocol duration. To saturate the static limit, we argue that short-range interacting systems require a spectral gap that closes with $N$. At second-order quantum critical points this leads to a universal condition on the critical exponents, $\nu(d+z)=1$, which can be approached arbitrarily closely, as we show for the XXZ chain; cat-like ground states at first-order transitions provide an alternative route to static optimality. In contrast, we find that all-to-all interacting models can achieve optimality even in gapped regimes. Furthermore, reaching the dynamical bound is tightly related to the ground-state preparation time; we demonstrate that its optimal, inverse-gap profile can be obtained via local adiabatic protocols. By analyzing paradigmatic systems – the transverse-field Ising chain, the XXZ chain, a squeezing Hamiltonian, and the two-mode Bose-Hubbard model – we identify specific many-body probes capable of approaching both limits. Overall, our results provide a theoretical basis for the design of (local) many-body ground-state sensors operating at the ultimate limits of quantum precision.