Quantum Physics Paper Analysis

We study Hamiltonian learning in a novel setting, where we are promised a physical structure that is obfuscated by a global unitary. In particular, we consider the task of learning the weights $E_i$ of a Hamiltonian $H=U^{\dagger}(\sum_{i \in I} E_i n_i + H_O)U$ comprised of a set of non-interacting modes $I$ and an arbitrary ``spectator'' $H_O$ acting on a disjoint set of modes $O$. The non-interacting structure is hidden by an unknown global unitary $U$, and our goal is to recover the $E_i$ without reconstructing $U$. Such Hamiltonians are well-motivated in the setting of materials modeling, where they find application for classical methods such as mean-field theory, Green's functions, and density functional theory. We show that this problem is DQC1-hard, despite the apparent simplification given by the non-interacting structure. We then introduce SPICES (single-particle inference via contour estimators), which combines a Hadamard test with a novel classical postprocessing procedure to efficiently recover the spectral distribution in Wasserstein distance under certain natural assumptions. The method exploits the correspondence between single-particle energies of the individual quasiparticles and the Fourier frequencies governing zeros of the partition function at complex inverse temperature. As quasiparticle spectra feature ubiquitously in downstream materials calculations, and with SPICES being simple and practical to execute, we expect that SPICES is a promising route to quantum applications in materials simulation.

We study the problem of learning the dense Sachdev--Ye--Kitaev (SYK) Hamiltonian from copies of its Gibbs state. Existing algorithms for Hamiltonian learning typically rely on geometric locality or bounded interaction degree and therefore do not apply to SYK, where each quartic interaction overlaps with $Θ(n^3)$ others. We show that this obstruction can be overcome by exploiting the random mean-field structure of the model. At any constant temperature, we prove that with high probability over the SYK couplings, the entire Hamiltonian can be learned to inverse-polynomial accuracy using polynomially many samples. Furthermore, when the inverse temperature is restricted to be a sufficiently small constant, we construct a quasipolynomial-time learning algorithm which is qualitatively different from the sample-efficient algorithm.

Correlations across channel uses can improve quantum communication rates, making optimization over arbitrarily large blocks a central difficulty in determining quantum capacity. We show how full permutation invariance limits this advantage for every finite-dimensional memoryless channel. The optimized coherent information per use converges to the single-use maximum and consequently attains its supremum at a finite block length. Thus finite-block superadditivity remains possible, while the asymptotic optimization reduces to a single channel use. We also establish a strong converse for pure-source entanglement generation with permutation-invariant inputs: at any fixed rate above the single-use coherent-information maximum, the fidelity tends to zero. Beyond these communication bounds, we identify a common structure underlying completely bounded norms and the sandwiched Rényi channel quantities governing discrimination against a replacer and entanglement-assisted communication. De Finetti reduction and permutation covariance yield systematic alternative proofs of their known multiplicativity and additivity results within a shared variational framework. We further show that, for permutation-invariant inputs, correlations cannot sustain an asymptotic reduction in output entropy per use below the single-use minimum. This entropy limit holds for Rényi orders greater than one and for the von Neumann entropy, extending the role of symmetry from communication bounds to the control of output entropy.

The power and limitations of classical simulation are central to understanding quantum computational advantages. A leading simulation paradigm is based on coherent decomposition into classically tractable free states where the decomposition rank determines the simulation complexity. Proving strong lower bounds on this number is a notoriously difficult and mathematically rich problem, as exemplified by the qubit stabilizer rank problem. Here, we study the Gaussian version of this problem in both bosonic and fermionic systems and establish robust exponential lower bounds on Gaussian rank. In particular, we prove that for every pure non-Gaussian state on finitely many modes, with definite parity in the fermionic case, the approximate border Gaussian rank of its tensor powers grows at least exponentially at any fixed norm error below one. Our proofs combine reduction to four modes with Majorana spectral bounds for fermions, and Gaussian postselection with an entropy-based rank bound for bosons. As concrete examples, we derive explicit exponential lower bounds for the four-mode fermionic GHZ state and the bosonic single-photon state. The bosonic results require no assumption on the energy of the target state. Our results show that non-Gaussianity universally entails exponential Gaussian decomposition complexity, setting fundamental limitations on decomposition-based classical simulation of bosonic and fermionic systems.

Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods. They describe a small subsystem of interacting fermions coupled to a large, noninteracting bath. We perform a comprehensive study of the computational complexity of simulating impurity models, delineating the boundary between classical and quantum tractability for this class of problems. Our main finding is that static properties of quantum impurity models can be calculated efficiently on a classical computer. Specifically, we give classical algorithms that (1) estimate the ground-state energy to additive precision $δ$ in time $\mathrm{poly}(n,δ^{-1})$, and (2) estimate the partition function at inverse temperature $β$ to relative precision $δ$ in time $\mathrm{poly}(n,β,δ^{-1})$, where $n$ is the system size. These results improve the previous best-known complexity for ground-state energy estimation from quasipolynomial to polynomial time, while establishing for the first time rigorous polynomial-time guarantees for simulating impurity models in thermal equilibrium. On the other hand, we find that simulating dynamical properties of impurity models is hard for classical computers but easy on a quantum computer. As a canonical example, we show that computing their nonequilibrium Green's functions captures the full power of quantum computation, even at finite temperature. Taken together, our results rule out superpolynomial quantum speedups for computing static properties, but provide an avenue for quantum advantage in simulating impurity physics out of equilibrium.

We introduce a method for studying state preparation complexity in dense quantum $p$-spin Hamiltonians on $n$ qubits, going beyond bounds based only on circuit lightcones. The key input is the class's effective profile complexity, which is derived from the metric entropy of its Pauli profiles. These profiles record expectations of all Pauli operators supported on exactly $p$ qubits. Classes with uniformly bounded quadratic effective profile complexity remain separated from the ground-state energy by a positive multiple of $\sqrt n$ for sufficiently large fixed $p$. At subquadratic effective profile complexity, the class cannot outperform a suitable benchmark class at leading order, with product states providing a universal benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem of Berta et al. (arXiv:1810.12197) with Gaussian process entropy bounds. Applying this framework, we show that attaining near-ground-state energy requires $Ω(n^2/\log n)$ one- and two-qubit gates, even with arbitrary discardable ancillas. We also obtain depth-width tradeoffs, entanglement-depth and matrix product state bond-dimension lower bounds, and obstructions for both orientations at every fixed level of Parham's magic hierarchy (arXiv:2504.19966), with total circuit width $O(n)$. In first-level reverse magic, a shallow circuit is followed by an unrestricted Clifford circuit. The latter can spread local observables across the system, preventing a direct application of small-lightcone bounds. For this first-level class, our bounds also allow arbitrarily many clean ancillas at fixed shallow-circuit depth. A sharper benchmark shows that Clifford+$T$ circuits with $o(n)$ $T$-gates have no leading-order energy advantage over product stabilizer states, even with unrestricted Clifford operations and arbitrary discardable ancillas.

Hamiltonian learning provides a systematic framework for reconstructing unknown quantum dynamics. However, existing protocols typically assume direct measurement access to the entire system. With fast single-qubit control and a connected reference backbone, we show that a single measurable qubit suffices to learn all $O(N)$ independent parameters of a bounded-degree two-body Hamiltonian on $N$ qubits at the Heisenberg limit. Crucially, our protocol uses robust SWAP gates synthesized by quantum signal processing, enabling coherent transfer of states evolving under distant Hamiltonian parameters to the measurable qubit. This transfer requires no prior calibration of the Hamiltonian parameters of the intermediate links. A parallel learning architecture achieves total query time $\widetilde{O}(N)$ for an $N$-qubit chain, while retaining Heisenberg-limited precision scaling. On the chain, these scalings match the fundamental precision and information-propagation lower bounds up to logarithmic factors. The framework further extends to arbitrary bounded-degree interaction graphs. Our results establish a scalable route to learning an extensive number of many-body Hamiltonian parameters through only a local measurement interface.

In this work we study the robustness of $\mathsf{QAC}^0$ with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for $\mathsf{QAC}^0$ circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel $W$-test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that $\mathsf{QAC}^0$ can \textit{exactly} simulate $\mathsf{TC}^0$ with polynomially many copies of the classical input and that for every fixed prime $p$ exact $\mathsf{QAC}^0$, $\mathsf{EQAC}^0$, can compute total Boolean functions outside of $\mathsf{AC}^0[p]$. Second, we ask to what extent the computational power of $\mathsf{QAC}^0$ follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that $\mathsf{QAC}^0$ is in fact robust to restrictions on which single-qubit gates are permitted: every $\mathsf{QAC}^0$ circuit can be approximately implemented by a $\mathsf{QAC}^0$ circuit consisting of just generalized Toffoli, $S$, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.

We give a deterministic classical algorithm that estimates $|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ time, where $U$ is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and $x$ is an arbitrary $n$-bit output string. This improves over prior state-of-the-art algorithms that takes $n^{O(log(n))}$ time for the same task, $n^{O(log(log(n))}$ when $U$ is geometrically local, and $n^{O(1)}$ for 2D geometrically-local circuits.

Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly larger gap on the folded OPI problem, yielding an even stronger quantum separation. As a concrete example, for code rate $0.3$, DQI and the modified algorithm achieve expected scores of approximately $0.85$ and $0.95$, respectively. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.

We first provide a simple proof showing that any single-shot code is self-correcting. We then show that any $[[n,k]]$ CSS quantum low-density parity-check (QLDPC) code can be transformed into an $[[nm,k]]$ CSS QLDPC code with single-shot (SS) quantum error correction and an efficient local decoder which runs in $O(\log m)$ parallel time. Below a constant threshold $p_{\rm RG}>0$ for joint local stochastic physical and measurement noise, the logical failure probability over $T$ correction rounds is bounded by \begin{equation*} O(T n)\exp[-Ω(m^α)] \end{equation*} for a constant $α>0$; we say that the \textit{threshold} is $p_{\rm RG}$ and \textit{error suppression} is $Ω(m^α)$. Moreover, if the input code is equipped with a single-shot decoder with threshold $p_c>0$ and error suppression $Ω(n^β)$, then the output code \textit{enhances} the error suppression to $Ω(m^α n^β)$, while maintaining the decoder-independent threshold $p_{\rm RG}$, and thus \textit{enhanced} if $p_c < p_{\rm RG}$.

Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. In this work, we establish quantitative guarantees for how accurately these designs reproduce the full distributions of individual output probabilities. We show that, for every strong $\varepsilon$-approximate unitary $k$-design on $n$ qubits, the distribution of each individual output probability is within $O\left(\sqrt{\frac{2^n}{k(k+2^n)}}+\varepsilon\right)$ in Kolmogorov distance of the finite-dimensional Porter-Thomas distribution, a beta distribution with parameters $1$ and $2^n-1$. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We further show that local invariance yields an exponential improvement in the dependence on $k$, with guarantees also in the stronger metric of total variation: every strong $\varepsilon$-approximate unitary $k$-design invariant under unitary translations acting on $\log k+O(1)$ qubits achieves error $2^{-Ω(k)}+O(\varepsilon)$ in Kolmogorov distance and $2^{-Ω(k)}+O(\varepsilon\log(2/\varepsilon))$ in total variation distance. These results identify both the distributional accuracy guaranteed by moment matching and the additional structure that substantially improves it. As an application, we show that if the marginal distribution of each output probability of a strong approximate design is within Kolmogorov distance $η$ of its Haar counterpart, then the expected Shannon entropy of the output distribution differs from its Haar value by $O(\sqrtη)$.

We prove a generalized quantum Stein lemma for i.i.d. normal states against convex, tensor-stable families on arbitrary von Neumann algebras. Assuming the existence of an alternative state with finite relative entropy from the null state, we show that, at every type-I error tolerance $\varepsilon\in (0,1)$, the worst case type-II error exponent is achieved with the regularized relative entropy with a strong converse. The proof combines the integral representation of relative entropy by hockey-stick divergences, a modular testing bound, and convex minimax argument.

Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state using a catalyst, an auxiliary vector that is left unchanged. They are a powerful tool in quantum algorithm design, especially in the context of quantum query complexity: feasible points of the (dual) adversary semidefinite program directly translate into transducers and the optimal transduction complexity is equal to the adversary bound, i.e. the Las Vegas complexity, which is known to characterize bounded-error quantum query complexity. Moreover, contrary to bounded-error algorithms, transducers compose exactly, which limits overheads due to controlling errors in algorithms constructed by composition. Constructing efficient, let alone optimal, transducers in terms of quantum query complexity nevertheless remains a hard task since it still requires solving the adversary SDP and constructing the unitary to obtain an explicit algorithm. In this paper, we show how using the symmetry group of state-conversion problems simplifies both steps. First, using a symmetrization argument, we prove an optimal catalyst can always be chosen covariant under a representation of the symmetry group. Second, we prove that the transducer intertwines two different representations of the group and can thus be chosen block diagonal in the isotypic decomposition of the Hilbert space. Using those methods, we then derive optimal transducers, with optimal constants, for different widely used quantum algorithmic primitives, such as unstructured search, amplitude amplification and amplitude estimation. Our approach extends previous work on the use of representation theory to compute adversary lower bounds (Høyer, Lee, and {\v S}palek, 2007; Ambainis, Magnin, Roetteler and Roland, 2011) to the systematic construction of optimal algorithms.

A quantum impurity model describes a small interacting subsystem embedded into a large bath of free fermions. Here we study the computational complexity of calculating the ground energy, thermal equilibrium, and dynamical properties of these models. Our work reveals a sharp contrast: equilibrium properties can be efficiently approximated by classical means, whereas time evolution can implement a universal quantum computation. More precisely, let $H$ be the Hamiltonian of an impurity model with $n$ fermionic modes and a constant-size impurity. We show that: (1) the ground energy of $H$ can be approximated to additive error $\varepsilon$ by a classical algorithm with runtime $\textsf{poly}(n,1/\varepsilon)$, improving on the quasi-polynomial runtime of the best previously known algorithm; (2) at inverse temperature $β$, the Helmholtz free energy and a classical description of the thermofield double state can be computed to precision $\varepsilon$ in time $\textsf{poly}(n,β,1/\varepsilon)$; (3) simulating the time evolution $e^{-iHt}$ is $\textsf{BQP}$-complete, for $H$ that is time-independent and has a fixed, constant impurity size. Our algorithms exploit exponential suppression of multi-particle bath excitations in a basis organized by energy scale and Krylov depth. Our universality construction realizes a stationary quantum processor whose program arrives in a stream of freely propagating fermions.

Fast and accurate qubit-state assignment is essential for feedback, calibration, and error correction in quantum processors. In superconducting platforms, frequency-multiplexed readout makes this task intrinsically multivariate as measured traces can encode crosstalk, qubit-state relaxation events, and other transient nonidealities that are not fully captured by conventional matched filtering. Here, we introduce spiking neural network (SNN) discriminators for superconducting qubit readout. By processing the measurement window in successive time chunks, the networks exploit temporal structure and update classification scores as data arrive, rather than waiting until the end of the readout window. The spiking networks outperform matched-filter discrimination and approach the accuracy of a full-trace artificial neural network. Beyond reaching the performance of artificial neural networks, the key advantage of SNNs is that they provide a streaming, time-resolved estimate of the qubit state that evolves as the readout signal is acquired. Using quantisation-aware training and hls4ml synthesis, we further demonstrate that each FPGA inference update can be completed before the next readout chunk arrives. These results establish spiking neural networks as a promising route to low-latency, real-time qubit readout on FPGA hardware, with broader implications for time-critical quantum-control and scientific-inference applications.

Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems. Convergence to Porter-Thomas plays a central role in random circuit sampling and experimental demonstrations of quantum advantage, where the output statistics of low-depth random quantum circuits are expected to be approximately Porter-Thomas, despite the absence of a rigorous proof of convergence. We show that the output distribution of polynomial-depth brickwork random circuits converges inverse-polynomially in total variation distance to the Porter-Thomas distribution. Specifically, consider the output probability distribution over a fixed bitstring of a local random quantum circuit, constructed from nearest-neighbor Haar random gates. Then, for any $m \geq 0$, the distribution corresponding to circuits of depth $O(n^{2m+1}\log(n))$ is at most $O(1/n^m)$ far in total variation distance from the Porter-Thomas distribution. Our proof uses moment bounds from approximate designs, analytic estimates for characteristic functions, and a local anticoncentration property for inverse moments.

We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length $n$, information-theoretic protocols require $Ω(\sqrt{n})$ error under pure differential privacy and $Ω(\sqrt{n}/\log n)$ error under strong approximate differential privacy, whereas computational security permits $O(1)$ error. In Klauck's honest, nonpreemptive, message-preserving model, we give an $O(n)$-communication quantum protocol with pure $\varepsilon$ quantum differential privacy (QDP) and expected error at most $\frac{2}{\sinh \varepsilon}+γ$, for every $γ>0$. For approximate $(\varepsilon, δ)$ QDP, an exact hockey-stick divergence calculation yields strictly smaller error, while preserving the $O(1)$-versus-$Ω(\sqrt{n}/\log n)$ separation for $δ=o(1/n)$. Thus, quantum communication achieves $O(1)$ information-theoretic error, matching the accuracy available classically only under computational assumptions. The main construction uses a guarded coherent round trip and an equal-Gram rigidity principle that prevents an honest player from retaining input-dependent complementary information. We separate this model from weaker prescribed-channel privacy, which already admits an exact classical realization, and from fully retention-robust security, against which measurement-and-abort attacks remain possible. Therefore, we identify preservation of non-orthogonal quantum messages as a resource for privacy.

Schur sampling is a fundamental primitive for extracting permutation-invariant information from many-body quantum systems and has broad applications in quantum information science. Circuit-based implementations typically rely on coherent representation-theoretic operations such as Clebsch-Gordan transforms, generalized phase estimation, or quantum Fourier transforms over the symmetric group. We show that unitary Schur sampling of arbitrary permutation-invariant mixed states on $n$ $d$-dimensional qudits can instead be implemented using only pairwise SWAP tests, namely, two-qudit projective measurements onto the symmetric and antisymmetric subspaces. Our protocol achieves error $ε$ in diamond distance using $O(n\min\{n,d\}^{3}\log^2(n/ε))$ random SWAP tests. The central idea is to repeatedly identify and extract the largest antisymmetric subsystem. This turns unitary Schur sampling into a search for antisymmetry and gives the algorithm a natural interpretation as a stochastic traversal of a Young diagram. The protocol preserves the $\mathrm{SU}(d)$-irrep state while preparing a canonical pure state in the multiplicity subsystem. As an application, we consider quantum purity amplification (QPA), in which multiple noisy copies of a pure quantum state are combined to produce a state of higher purity. We show that the optimal purified state can be obtained by retaining a single designated output qudit and discarding the rest.

We prove near-optimal time-space lower bounds for breaking quantum cryptography in the random oracle model. Specifically, we show that a $T$-query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$-qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$. In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$, with a trivial attack at $S = N$. This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving time-space tradeoffs for breaking post-quantum cryptography. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.

Can simple processes appear highly complex? Gowers (Comb. Prob. Comp. '96) conjectured that repeatedly composing local random reversible operations can yield global permutations that are indistinguishable from random. In this work, we study the unitary quantum analog of this question, in an attempt to make new progress on this longstanding conjecture. Our first result shows that statistical moment matching in the form of unitary designs does not generically lead to pseudorandomness---even for the simplest quantum processes: for every fixed $t$, we give an efficiently samplable family $\{ν_n\}_n$ of distributions on one- and two-qubit gates such that, after $T=O_t(n^2\log^2 n)$ independent steps, the resulting $n$-qubit ensemble is an approximate unitary $t$-design with negligible error $\exp(-Ω(\log^2 n))$, yet an efficient quantum algorithm distinguishes it from random using only $O_t(\log^2 n)$ queries. This refutes the unitary analog of the Hoory--Magen--Myers--Rackoff conjecture (ICALP '04) for permutations. Our second result is a stronger separation between unitary designs and pseudorandom unitaries at polynomially bounded moments; our counterexample, however, requires highly structured ensembles, in contrast with the simple local walks from before. This suggests caution when using unitary designs to model information scrambling in black-hole physics, as even maximally scrambled systems can exhibit structure which is accessible to efficient experiments. Motivated by these findings, we then propose new conjectures for how pseudorandomness can plausibly emerge within simple quantum processes, such as random quantum circuits.

A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions $f_n\colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ that can be computed with $O(\log n)$ bits of one-way classical communication given prior entanglement, but that require $Ω(n^{1/3})$ qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.

Electromagnetic duality in the toric code has order two at the level of anyon types and acts as a Hadamard-type logical transformation on the encoded quantum information. Here, we ask whether it can likewise be realized microscopically as an order-two Clifford operation. For the $\mathbb{Z}_2$ toric code, we prove that any locality-preserving Clifford realization of electric-magnetic exchange cannot have order two. Our proof is fully general and requires neither translation symmetry with restricted families of system sizes nor a fixed pairing between vertex and plaquette stabilizers. Geometrically, the proof locally emulates the unavoidable crossing between electric and magnetic strings, similar to a cross-cap in a non-orientable manifold. Extending the problem to the $\mathbb{Z}_N$ toric code, we find that an order-two Clifford realization exists for odd $N$, whereas it is impossible for even $N$. Our results show that the group law of an emergent electromagnetic duality need not lift faithfully to its microscopic Clifford realization.

The quantum state preparation problem is to, given a description of a quantum state, efficiently generate a quantum circuit computing the state. We show that for quantum states described by weighted d-DNNF (deterministic, decomposable pseudo-Boolean circuits) a quantum circuit computing the state can be obtained in linear time up to complex arithmetic.

Symmetric private information retrieval (SPIR) lets an inquirer obtain one specific bit only, without leaking any information about its index to the database owner. With a single server, this is impossible for parties with unrestricted quantum power. We show that it becomes possible, with information-theoretic security, when the server and the user hold only noisy intermediate-scale quantum (NISQ) devices without long-term quantum memory and measure each qubit on arrival, while the eavesdropper remains all-powerful; this is a stricter form of the memory restriction of the bounded- and noisy-quantum-storage models. The server sends BB84 states one way; the user discriminates them unambiguously and so knows a random subset of the bits. After a joint random permutation into blocks, the user announces the conclusive locations of one privately chosen block, and the server hashes and takes a random parity of these locations in every block; the permutation makes it exponentially unlikely that one set of locations fits two blocks. We prove secrecy against the eavesdropper, database privacy through an explicit size rule for the announced set, and user privacy against a server who prepares the prescribed BB84 states and announces truthfully, exactly for single photons and up to a small multi-photon term over a tolerated noise channel. The only addition to BB84 equipment is a passive linear-optical measurement with one ancillary mode. For a $10^{4}$-bit database and database privacy $10^{-6}$, blocks of about a thousand qubits suffice over a tolerated noise channel for a user who applies the prescribed measurement; certifying an arbitrary memoryless user and committing to the permutation need larger auxiliary transmissions, which we quantify with finite keys. Database privacy extends to decoy-state weak coherent pulses, and simulations show that the bound is nearly tight.

A stationary quantum state has one dynamical phase factor and one scalar energy even when its internal response spans a large Hilbert space. Our argument concerns not the value or observability of an absolute phase, but the one-ness of stationary time evolution. In regularized Hartree--Fock (reg-HF), the connection to the stationary mean field is established before any one-mode reduction: the primitive-product relative-coordinate Gaussian measure induced by the Gaussian HF representation fixes a covariance and, at that covariance, is simultaneously the minimum-Fisher-information and maximum-Shannon-differential-entropy distribution and the equality case of the Stam bound. The Coulomb operator admits a compatible Gaussian scale resolution, and virial completion converts the resulting regularized pair displacement into a stationary-compatible response. Stationarity motivates a one-mode constraint on the terminal scalar correlation response. The decisive reg-HF hypothesis is a one-mode exclusion axiom: covariance carried by response components orthogonal to the retained pair mode is excluded from the terminal scalar energy property, without asserting that the unrestricted response is one dimensional. Helium provides the minimal nontrivial test. The parameter-free retained Coulomb carrier $-δ/e$ and finite-$Z$ insertion $8δ/9$ closely reproduce independent He-like coefficients and energies, while an explicit Bethe--Goldstone calculation displays a broad non-single-denominator return spectrum even though its scalar energy is exactly moment-compressible. The result separates microscopic spectral complexity from one-mode energetic sufficiency.

Tensor networks are powerful tools for simulating quantum many-body systems, but the growth of spatial entanglement severely limits the direct evolution of pure states under chaotic unitary circuits. Here we consider a more targeted task: the approximate strong simulation of a specified output probability of a 1D chaotic brick-wall circuit at finite relative precision. Given input and output bit strings $\by$ and $\bx$, we evaluate $p(\bx|\by)=|\bra{\bx}U(T)\ket{\by}|^2$ using the Sweeping RTM algorithm, a transverse tensor-network contraction based on reduced transition matrices (RTMs). The algorithm compresses the left and right temporal boundary states jointly, seeking an output probability that converges across spatial cuts and as the bond dimension is increased. For chaotic one-dimensional brick-wall circuits at a fixed relative target precision, we find numerical evidence that the bond dimension required to obtain stable estimates grows subexponentially over the accessible time window. Our findings open a direct route to classical probability queries for chaotic quantum circuits, with potential applications to benchmarking and learning tasks.

Epitaxial quantum dots (QDs) are widely recognised as one of the best quantum light sources, given their good stability, brightness, quantum efficiency and coherence. To reach such properties, QDs are protected from potentially detrimental surface states by a relatively thick capping layer, typically exceeding 50nm. This prevents the implementation of near-field effects, like plasmonic-based ones, that can dramatically increase the light-matter interaction, since the control of the spontaneous emission dynamics and directionality of the emission can only occur if the emitter is in close proximity (typically tens of nanometers or less) from the metallic structures. In this work, we report the growth and optical characterisation of InAs/GaAs QDs with GaAs capping layer thickness of 10nm, 20nm, and a more standard 95nm. Remarkably, we observe emission linewidths up to 5 times smaller than previously reported, with unperturbed excitonic lifetimes. These results demonstrate that the epitaxial QD's high optical quality can be maintained even when the emitters are at reduced distances from the surface, opening the path for the exploration of near-field light-matter interactions with coherent and stable emitters, suitable for quantum technology applications.

We study the transverse field Ising model, defined by the Hamiltonian $H =\frac{1}{2}\sum_{i, j\in [n]} J_{ij} Z_i Z_j +\sum_{i=1}^n h_i^z Z_i + η\sum_{i} X_i$ where $J $ is the symmetric interaction matrix, and $η$ is the transverse field strength. Let $Δ(J)=λ_{\max}(J)-λ_{\min}(J)$ be the spectral width of $J.$ When the inverse temperature $β\geq0$ satisfies $Δ(J)\cdot\frac{\tanh(βη)}η\leq1$, we give a randomized classical algorithm that approximates the partition function $Z(β)=\operatorname{Tr}(e^{-βH})$ to a given relative error $ε\in(0,1)$ in time polynomial in $n$, $β$, the model parameters, and $ε^{-1}$. When $ Δ(J) \cdot \frac{\tanh(βη)}η > 1 ,$ we show that approximating $ Z(β)$ within an $\exp(o(n))$-multiplicative factor is $\textbf{NP}$-hard, and thus unlikely to admit an efficient classical or quantum algorithms under standard complexity theoretic assumptions. Furthermore, in the regime $Δ(J)\cdot \frac{\tanh(βη)}η\leq 1,$ we provide an efficient randomized classical algorithm that approximates Pauli string observables of the Gibbs state $ ρ_β= \frac{e^{-βH}}{\operatorname{Tr}(e^{-βH})}$ within an arbitrarily small additive error. In the special case when the observable is also diagonal in the $X$-basis, i.e. $P \in \{I, X\}^{\otimes n}$, the algorithm further achieves arbitrarily small relative error.

Fermionic non-Gaussianity is a resource for universal quantum computation that can be generated by interactions in quantum many-body systems. Using the magic Rényi entropy (MRE) as a measure of non-Gaussianity, we derive its universal upper bound and Haar mean, proving that typical Haar-random states attain the maximal MRE density of $\ln(4/3)$ per Majorana in the large-system limit. We also show that the MRE can differ extensively between states with identical covariance matrices. To investigate how non-Gaussianity grows toward this maximal density, we evolve a Gaussian state in imaginary and real time under the Sachdev-Ye-Kitaev Hamiltonian. By varying the imaginary- and real-time durations, we identify a first-order transition marked by a kink in the MRE density and spontaneous breaking of the permutation symmetry among the four copies used to evaluate the MRE. This transition represents a qualitative change in the non-Gaussianity of the state that is not reflected in the thermal free energy.

How complex can the responses of a quantum device become as it runs longer with a fixed internal memory? We quantify this complexity through sequential response capacity: how many adaptive testing stages, each using a fresh run, can continue to separate possible processes by a prescribed gap in response probabilities. For fixed system and memory sizes, we establish a tight law relating this capacity to run length and probability resolution. At fixed resolution, the capacity grows on the order of $K\log K$, where $K$ is the number of time steps in each run. Our construction attains this growth using time-dependent phase rotations on a single visible qubit with no additional internal memory; its tests give response probabilities exactly zero or one. Under the same tests, classical stochastic processes that measure in a fixed basis at every step have only linear capacity at fixed sizes and resolution. For phase sequences selected by a stored classical label, we then quantify how known independent Pauli noise changes this logarithmic enhancement. With ideal controls and weak residual phase noise after correction, we prove matching capacity bounds at a fixed small probability gap. These bounds identify the inverse residual phase-flip probability as the coherence timescale that limits the extra logarithmic growth.

The eight-component relativistic wave equation for spin-$\frac{1}{2}$ particles of Robson and Staudte (FV$\frac{1}{2}$), a Feshbach--Villars linearization of the Feynman--Gell-Mann equation, reproduces the Dirac hydrogenic spectrum with a doubled solution space and an indefinite inner product. Its exact Stark shifts must equal the Dirac ones; whether its indefinite-metric perturbation theory delivers them is not guaranteed. We compute the first- and second-order Stark shifts of the $n=1$--3 levels of hydrogenic ions from H to U$^{91+}$ in the Schrödinger, Dirac and FV$\frac{1}{2}$ theories, evaluating all spectral sums, continuum included, by the Dalgarno--Lewis method. The FV$\frac{1}{2}$ and Dirac shifts coincide level by level, to working precision at first order (closed-form roots) and to 45 significant figures at second order. Both ingredients are needed: without the explicit spin--field coupling the first-order roots become complex, and without the negative-norm states the $(Zα)^2$ coefficient is wrong. Norm sign and parity are locked in the doubled space: a potential lifting the $2s_{1/2}$--$2p_{1/2}$ degeneracy needs its own spin--gradient term, and shifts placed by hand on the $κ$-labeled states give a spurious imaginary linear Stark shift. The relativistic linear Stark effect is smaller by finite factors, but a second-moment sum rule shows the non-relativistic linear Stark strength is conserved, the missing part reappearing in singular $(Zα)^{-2}$ second-order terms. For levels with a fine-structure partner, an exact intra-shell/regular split of the second-order shift gives the $(Zα)^0$ coefficients analytically and relates the $π^2$ terms of the $(Zα)^2$ coefficients to the singular ones. The Dirac weak/strong-field crossover for $n=2$ of hydrogen lies near 2.8~kV cm$^{-1}$, and the perturbative window set by the fine structure grows as $Z^5$.

Deciding whether an unknown quantum state either belongs to, or is far from, a given family of states is a natural question of quantum information theory. In many such cases, there is a natural 2-copy test which always accepts whenever the state indeed belongs to the target family; it is often much more difficult, however, to bound the probability of acceptance for states that are far from the family. Here we develop a simple new technique for upper bounding this probability for general families, and therefore upper bounding the sample-complexity of the decision problem itself. As a particularly striking example of this framework, we show that deciding whether an unknown pure $n$-mode state is fermionic Gaussian, or at least $\varepsilon$-far in trace distance from all Gaussian states, can be accomplished using the optimal number $Θ(\varepsilon^{-2})$ of copies. Remarkably, our analysis applies to the well-known Bell sampling procedure for testing fermionic Gaussianity, which we therefore show to be optimal, even compared to protocols making arbitrary collective and adaptive measurements. As a second example, we show that the analogous decision problem for the family of Slater determinant states can also be solved with mode-independent sample-complexity.

Consider the following optimization problem over stabilizer product states: given an $n$-qubit stabilizer state $\left|ψ\right\rangle$ and a set of single-qubit stabilizer states $S$, maximize $\left|\langle ψ| φ_1, \ldots, φ_n \rangle\right|^2$ over single-qubit stabilizer states $\left|φ_i\right\rangle \in S$. By varying the set $S$, we show that solutions to this problem can be useful in a variety of settings: tighter runtime bounds for certain classical simulation algorithms; measures of entanglement; and the complexity of low-rank matrix completion. Moreover, we give a complete complexity classification of this nearest stabilizer product state problem. After accounting for the symmetries in the Clifford group, there are $9$ distinct possible sets $S$, and we show that all but the two simplest of these are $\NP$-complete.

We show that a pair of two-qubit product measurements can be perfectly distinguished when accessed jointly, yet cannot be perfectly distinguished when their local components are distributed between distant parties restricted to local quantum operations and classical communication (LOCC). This establishes a measurement analogue of nonlocality without entanglement that, unlike its state-based counterpart, emerges in a remarkably simple setting. We further uncover a hierarchy of LOCC discrimination strategies: adaptive protocols, in which the probe used at one site may depend on classical information obtained from another, can strictly outperform restricted non-adaptive protocols, as demonstrated by a set of six bipartite qutrit product measurements. We also show that LOCC distinguishability of bipartite measurements can be intrinsically directional, depending on which party initiates the protocol. More generally, we construct pairs of $n$-qubit product measurements that are globally perfectly distinguishable but cannot be perfectly distinguished across any bipartition, even when all parties on either side of the bipartition are allowed arbitrary joint quantum operations. Finally, we show how quantum data hiding based on quantum-process nonlocality without entanglement can be realized using elementary optical components.

Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an $n$-qubit stabilizer state can be learned from $Θ(n)$ copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require $Ω(n^2)$ copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary $n$-qubit stabilizer state from $Θ(n)$ single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements. The same ideas yield a sample-optimal single-copy tolerant tester and, with $k$ qubits of quantum memory, the optimal testing tradeoff $Θ(n-k+1/\varepsilon)$ at infidelity $\varepsilon$. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most $r$, including states prepared by Clifford circuits with a bounded number of $T$ gates, can be learned using $O(n2^{r})$ single-copy measurements.

We give a quantum algorithm for simulating a $d$-sparse Hermitian Hamiltonian $H$, assuming a known upper bound $Λ$ on its maximum column Euclidean norm $\|H\|_{1\to2}$. For $tΛ\ge1/2$, simulation with operator-norm error $ε$ uses \[ O\!\left(tΛ\sqrt d+\sqrt d\log(2/ε)\right) \] sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For $d>1$ and $tΛ\ge\log(2/ε)$, the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of $Λ$. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters. As applications, we obtain $O(κ\sqrt d\,\mathrm{polylog}(κ/ε))$ queries for solving $d$-sparse quantum linear systems with $\|A\|\le1$ and $\|A^{-1}\|\leκ$, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most $d$ nonzero entries per row and column using $O(\sqrt d\log(2/ε))$ queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields $Θ(\sqrt N)$ queries for arbitrary $N\times N$ unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].

Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.

Typically, multiple copies of a quantum state are described by a tensor power of that state. However, from an operational point of view, an experimentalist cannot, in general, rule out imperfections at unknown positions or correlations between copies, so assuming independent and identically distributed (iid) copies is not justified a priori. In the following, we relax the iid assumption by considering a whole set of resource states that are fundamentally indistinguishable from a tensor power state, and in that sense look like many copies of the quantum state to the experimentalist. Using a de Finetti-type argument, we show that this operational set of states can asymptotically be represented by almost-iid states. As an application, we introduce operational analogues of asymptotic transformation rates, such as entanglement cost and distillation. This raises the question of whether these rates coincide with their iid counterparts.

Knill-Laflamme coefficients characterize exact quantum error detection through scalar compressions of error operators to the code space. For prescribed Pauli observables and a fixed code dimension, attainable coefficient vectors form a joint higher-rank numerical range, whose Euclidean norm image is the signature spectrum. We study how operator representation, code dimension, and detection constraints govern this geometry. Our main theorem identifies representation multiplicity as sufficient to lift active expectation data to exact scalar compressions: a lift exists whenever each occupied block has multiplicity at least the code dimension times the rank of the corresponding active state. When multiplicity suffices to realize all active states, the coefficient range is the full active expectation body and is therefore convex and connected, with a closed interval as its signature spectrum. This framework unifies commuting Pauli families, where sufficient common-eigenspace degeneracy yields polytopes, and subsystem stabilizer codes, where protected logical subsystems supply multiplicity spaces for noncommuting gauge observables. Explicit examples show how increasing the code dimension can make a range shrink, collapse, or become empty, while increasing multiplicity can turn a Bloch sphere into a filled ball. In the subsystem setting, parent-Hamiltonian constructions realize exact detecting codes as degenerate ground spaces, selecting distinguished vectors and continuous paths within these ranges. A final three-qubit example shows additional noncommuting detection constraints reduce a tetrahedral range to its barycenter and four vertices, producing a disconnected signature spectrum. The results provide a structural framework for Knill-Laflamme coefficient geometry and motivate sharper criteria for connected coefficient ranges and interval signature spectra under structured error models.

Many quantum systems are believed to thermalize slowly at low temperatures due to the existence of metastable phases. However, there are cases where further cooling can restore polynomial-time thermalization: we demonstrate that the Davies dynamics of the mean-field interchange model with local dimension $d\geq 3$ and single-site generalized Pauli couplings exhibits this behavior. The dynamical phase diagram is beholden to two distinguished inverse temperatures, $β_{\mathrm{min}}(d)$ and $β=d$, with the static first-order phase transition lying between them. At low and high temperatures surrounding the interval $(β_{\mathrm{min}}(d),d)$, the spectral gap of the Davies generator is bounded below by an inverse polynomial in system size $n$. Meanwhile, in this interval, the gap vanishes exponentially in $n$, indicating metastability. The proof uses Schur-Weyl duality to decompose the Davies generator into a classical Markov generator on Young diagrams, and the restriction to the remaining symmetry sectors whose gap is $Ω(n^{-1})$. Thus, exponential slowdown arises entirely from the Young diagram chain.

We address the problem of testing whether an unknown $n$-qudit state $ρ$ is $a$-close to a product state or $b$-far away from any product state, as measured in terms of state overlap. We provide a time-efficient algorithm to solve this problem that requires an $n$-independent number of copies of the unknown state. Our random coloring argument shows that for any unknown state there always exists a partition of $[n]$ into $q$ parts such that the square of the overlap with the closest product state with respect to this partition is only an additive factor $O(1/q)$ larger. This reduces the problem to tolerant testing of $q$ parties, with potentially growing local dimensions. Combining this insight with blockwise spectral projection arguments we can show that the natural $k$-copy generalization of Harrow & Montanaro's product state test provides an efficient tolerant tester. We use the same random coloring and blockwise spectral projection techniques to obtain a substantially improved algorithm for closest product state learning. In particular we give an algorithm that takes in $\widetilde{O}\big((nd)^2\big)\, 2^{\widetilde{O}(1/\varepsilon^8)}$ copies of the unknown state and produces an $\varepsilon$-approximately optimal product state. The key technical components of this learner are a qudit variant of the Bakshi et al. high-fidelity product state learning algorithm and a sampling technique based on Werner's optimal cloning channel.

Compact ground-state preparation circuits are essential for early fault-tolerant quantum chemistry. We introduce Variational Imaginary-time Majorana Evolution (VIME), a classical pre-training algorithm that extends operator-projected variational quantum imaginary-time evolution (OVQITE) to molecular electronic structure using a single compiled Majorana-propagation (MP) surrogate graph. We pair VIME with a compressed tiled Unitary Product State (c-tUPS) ansatz that we develop to reduce both classical simulation and quantum state-preparation costs. In the strongly correlated ruthenium complex TLD-1411, active-space calculations requiring up to 52 qubits achieve chemical precision against DMRG reference energies, with energy errors approximately $400\times$ smaller than those from ADAPT-VQE-based variational Majorana-propagation (ADAPT-VMPE). Across the strongly multireference acene series up to heptacene (60 qubits), VIME matches or improves on the MP-reported energy accuracy of the ADAPT-VMPE comparison points with up to $26\times$ fewer CNOTs and $167\times$ lower two-qubit depth. These results establish imaginary-time classical pre-training of compressed variational ansätze as a promising route to resource-efficient molecular ground-state preparation.

Universal channel coding enables communication without a complete description of the channel. For classical channels, universal codes can attain both capacity and the optimal high-rate reliability. We show that this compatibility fails for classical-quantum channels in general; that is, the optimal reliability in the channel-aware scenario is not always achievable with universal coding due to the ignorance of the unitary rotation of the output system. We exhibit a family of classical-quantum channels for which one cannot achieve the channel-aware optimal reliability by a fixed coding scheme. We further derive a converse bound on the reliability for unitary-invariant decoders, a natural assumption for the universal coding scheme, that can be strictly smaller than the optimal channel-aware error exponent. Conversely, we construct a channel-independent encoder-decoder pair and establish a universally achievable bound on the reliability that matches this converse bound in the high-rate regime, thereby characterizing the optimal universal reliability. Specifically, the channel-aware and universal exponents are governed by the Petz and sandwiched Rényi divergences, respectively. These divergences coincide for commuting outputs but differ for noncommuting ones, explaining why universality preserves optimal reliability classically but can reduce it quantumly. Our results showcase the fundamental reliability cost of performing the classical-quantum channel coding task universally.

Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $δ$. Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$-query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$, together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.

We propose a novel approach to state preparation by embracing the full power of open quantum systems. Instead of working with the whole unitary group in $n$ qubits, we identify a small Lie group $G$ in $(n+3)$ qubits. The dimension of its Lie algebra is $\text{poly}(n)$. Every state can be approximated starting from any fixed input state by repeatedly using partial trace and state preparation in the environment alongside group operations. Moreover, we also identify a single (open system magic) interaction Hamiltonian whose unitary group can be combined with open system quantum technology mentioned above to achieve transitivity on the space of all densities. Similarly, we show that all channels on $n$ qubits can be approximated by using a larger environment, achieving channel universality. The interesting small groups we identify are derived from Lie algebras of local Pauli strings and lead to a new landscape of cheap and expensive states, densities, and channels.

Networking matter-based quantum processing units (QPUs) offers a promising route to scaling fault-tolerant quantum computers. This requires distributed logical operations to be performed across photonic links, where noise is characteristically different from and stronger than in local QPUs owing to photon loss and probabilistic linear-optical operations. Measurement- and fusion-based quantum computing are designed to be robust against loss and probabilistic photonic operations, suggesting they could complement circuit-based error correction at the interface between networked QPUs. We use ZX calculus transformations to construct hybrid syndrome extraction protocols and apply them to distributed rotated surface code lattice surgery, demonstrating that several protocols attain a $50\%$ interface-erasure threshold when local noise is absent, including circuit-based lattice surgery using fused Bell pairs and hybrid protocols using linear cluster states. Relative to a straight Bell-pair interface geometry, the hybrid protocols increase the merge-observable interface distance from $d+1$ to $2d+1$ and restore the perpendicular-observable interface distance from $\lfloor(d+1)/2\rfloor$ to $d$. We calculate how the threshold decreases when using truncated resource states and map correctable regions under resource-state errors, local circuit noise, and fusion erasure. We then convert these erasure thresholds into photon-loss thresholds and probe subthreshold performance using fusion boosting. At circuit and resource-state error rates of $10^{-3}$, local errors largely mask the interface-distance advantage. As local noise is reduced to $10^{-4}$ and below, the linear-chain protocols improve more rapidly with decreasing erasure, suggesting that interface distance enhancements are effective in low local noise regimes.

Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Besides time, space is another central resource: storing and manipulating a massive input can be very challenging, especially when logical qubits carry substantial fault-tolerant implementation overhead. This motivates the following question: does DQI yield quantum advantages in memory, and can we prove it unconditionally? We give an affirmative answer to this question in the streaming setting. In particular, we consider a natural generalization of OPI using Hermite interpolation and Hasse derivatives, which asks for a low-degree polynomial satisfying as many constraints on its values and derivatives as possible. As a concrete example, we show [Quantum efficiency.] An adaptation of the DQI algorithm produces a polynomial satisfying $93\%$ of the constraints; moreover, it only reads the input stream in one pass, uses polylogarithmic space, and has polylogarithmic computation time per stream entry. [Classical hardness.] Any classical algorithm that produces an answer satisfying just $76\%$ of the constraints requires polynomial space, even if it can read the input stream with polynomially many passes and can use unlimited time. Our result provides a complete tradeoff curve for the tunable parameters, and implies that DQI has provable quantum advantages for the original OPI problem.

We study classical and quantum superintegrability of a resonant three-dimensional Hamiltonian with indefinite kinetic energy and three Poisson descriptions of the same flow. Besides three commuting quadratic Hamiltonians, the polynomial first-integral ring contains two primitive degree-four generators, $I_4^{\rm o}$ and $I_4^{\rm e}$, of odd and even momentum parity. A single octic relation leaves the polynomial invariant ring with transcendence degree four. Solving the complete first-integral equation shows that every rational first integral is a rational function of $H_1,H_2,H_3,I_4^{\rm o}$, so that the rational invariant field likewise has generic functional rank four. A branch-free transcendental invariant raises the generic smooth functional rank to five on the invariant open set $Δ>0$. The system is therefore minimally superintegrable in the polynomial and rational classes and maximally superintegrable on this invariant domain when transcendental integrals are admitted. Weyl quantisation yields exact higher-order differential symmetries in all three Poisson realisations. The branch-free fifth classical invariant also admits a densely defined nonlocal quantum counterpart, providing a concrete quantum realisation of the transcendental completion.

The chirality-induced spin selectivity (CISS) effect, the coupling between structural chirality and electron spin polarization, has been experimentally observed across many diverse systems. However, despite extensive theoretical effort, a unified mechanistic understanding remains elusive. In this perspective, we demonstrate how some of the basic properties of the fascinating effects of CISS can be understood based on straightforward symmetry considerations commonly employed in fundamental particle physics. In particular, we show that CISS does not violate any fundamental symmetries including parity and time-reversal. By anchoring CISS within the universal language of symmetry, we offer a robust conceptual foundation for interpreting experiments and guiding future theoretical and experimental designs.

Given multiple uses of an unknown quantum channel, we determine whether it is a specified non-mixed-unitary channel or belongs to the set of mixed-unitary channels. Formulating this as a composite channel hypothesis testing problem, we characterize the Stein exponents achievable by parallel strategies under progressively weaker restrictions on probe states and auxiliary memory. In particular, we consider block-i.i.d. probes, which allow arbitrary correlations within blocks of fixed size while remaining i.i.d. across blocks, and derive finite-letter expressions of the corresponding Stein exponents. Varying the block size, which interpolates between fully i.i.d. and arbitrary probes, together with further restrictions on intra-block correlations and access to auxiliary memory, results in a multifaceted hierarchy. We establish several strict separations within this hierarchy. Without auxiliary memory, we prove that fully i.i.d. probes yield a vanishing Stein exponent for every unital non-mixed-unitary channel, while blocks of three product probes suffice to obtain a strictly positive exponent for the qutrit Werner-Holevo channel. For block size two, although product probes seem to be insufficient for O(3)-covariant channels, an entangled probe achieves a strictly positive exponent for the qutrit Werner-Holevo channel, even though every maximally entangled probe fails. In contrast, auxiliary memory makes fully i.i.d. probes sufficient by yielding a strictly positive exponent for every non-mixed-unitary channel, even without requiring input-reference entanglement, and this exponent admits a lower bound determined by the diamond-norm distance from the mixed-unitary set. Moreover, for odd-dimensional Werner-Holevo channels, we find that this exponent is infinite, with every full-Schmidt-rank pure state being optimal.

It is well-known that every $n$-qubit unitary can be implemented by a $2^{O(n)}$-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is \emph{necessary} for general unitaries, even when allowing for unlimited number of ancilla qubits. We show, perhaps surprisingly, that all unitaries can be approximated to operator norm $ε$ by a circuit of one- and two-qubit gates of depth $\poly(n,\log 1/ε)$ with $2^{O(n)}$ ancilla qubits. In other words, every $n$-qubit unitary can be parallelized to polynomial depth. Moreover, if we allow unbounded fan-out gates, these circuits can be reduced further to \emph{constant} depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography.

Pseudorandom permutations are ubiquitous in theoretical and applied cryptography. PRPs that offer security even against adversaries making quantum queries are of increasing interest, and used in applications ranging from constructing pseudorandom unitaries to separating SZK from BQP. A successful framework for constructing classically-secure PRPs is the key-alternating Even-Mansour approach, which interleaves applications of public permutations with additions of round keys. The single-round construction is already classically secure in the ideal permutation model (IPM), with added rounds offering improved concrete security. However, in the quantum-query setting, the status of this framework is presently unclear. A simple quantum-query attack based on Simon's algorithm breaks the one-round cipher. For two or more rounds, security is only known against non-adaptive adversaries who must prepare all queries in advance. In this work, we show that the two-round Even-Mansour cipher is information theoretically secure in the IPM against adversaries making polynomially-many adaptive forward and inverse quantum queries to all available oracles. Our proof uses compressed permutation oracles and a specially crafted isometry relating the ideal and real experiments. We also show that this construction is minimal, in the sense that essentially any cipher constructed via a single call to a public permutation is quantumly insecure.

A majority of measurable dynamic quantities of a physical system is described as an equilibrium correlation function of the form $G_{AB}(t-t') = \left<A(t)B(t')\right>$, where $t'$ represents the impact time and $t$ represents the response time. Conventional quantum algorithms to compute such quantities via Hamiltonian simulation such as the Hadamard test, variational methods, or linear-response-based algorithms share one feature in common: each time point $t-t'$ is calculated by a different quantum circuit, leading to at least $O(N_t)$ total shots, and at least $O(N_t^2)$ total quantum gates. Here, we provide a different approach: utilizing $O(\log N_t)$ ancilla qubits to store time as a quantum variable, and effectively parallelize the computation of an equilibrium correlation function by requiring only a single quantum circuit for all time points. We show that this circuit needs to be run only $O(\log N_t)$ times, which in total requires $O(N_t \log N_t)$ quantum resources in the large system size limits. We prove that this scaling is optimal, and demonstrate our algorithm calculating the Green's function of a one-dimensional spinless Hubbard model.

Multiterminal Josephson junctions, in which one weak link couples three or more superconductors, are studied as hosts of topological Andreev bands, multi-pair supercurrents and tunable circuit elements. Their currents are modeled both as pairwise networks of two-terminal couplings and through genuinely multiterminal processes such as quartets. We ask how accurate the pairwise description is and what controls its error. In a microscopic scattering model of planar junctions, we compare exact currents with the best pairwise approximation, which allows arbitrary nonsinusoidal couplings. In ensembles of disordered three- and four-terminal junctions, the pairwise terms capture nearly all of the energy variation, yet the median current error ranges from 8.0 to 21.2 percent, about twice the energy error, because currents weigh the multiterminal harmonics more strongly. Designed devices extend the comparison to sixteen terminals. We identify a mechanism that controls this error. A normal-region mode near the Fermi level that couples to three or more terminals produces large nonpairwise currents, and detuning it with a gate suppresses them. Shifting only this mode, selected from normal-state properties, predicts the gate dependence of the error in eight three- and four-terminal devices without fitting currents. Finite-gap calculations in two clean devices confirm a drop from tens of percent near resonance to below one percent. An analytic single-level model gives a sufficient detuning for pairwise accuracy at any terminal count. Planar junctions thus inherit the resonant and cotunneling regimes known from quantum dots, and normal-state properties identify the mode that selects between them.

We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task of Gibbs sampling for classical Ising $k$-spin glasses (or Max-$k$-XORSAT) on random Erdős-Rényi hypergraphs with average degree $D\ge k$. In a temperature range beginning asymptotically at the predicted dynamical phase transition, $β_{\rm dyn}(k,D) = \sqrt{(2\ln k)/D}\times [1+o_{k\to\infty}(1)]$, we show that shattering and disorder chaos form a topological barrier that obstructs many algorithms, including Glauber dynamics and any algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical algorithm based on Prange's method, and by DQI equipped with a quantum decoder. For example, when $D=αk$ with fixed $α>1$, both Prange's algorithm and DQI can sample at any inverse temperature $β< \tanh^{-1}(1/α)$ for sufficiently large $k$, well beyond the dynamical threshold $β_{\rm dyn} \sim \sqrt{2\ln k / (αk)}$. Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.

Standard finite quantum de Finetti theorems approximate the $k$-system marginals of permutation-invariant states of $n$-systems by mixtures of independent and identically distributed (iid) states, usually in trace distance. We prove both standard and Renner's exponential de Finetti theorems in the stronger form of operator inequalities, implying bounds in every Schatten norm and for every quantum Rényi divergence satisfying data processing. In the standard case, for fixed local dimension, our $k/n$ error bound in max-relative entropy improves on the previously best known $k^2/n$ scaling, even in the classical setting. The operator-inequality approach is particularly suited to study channel de Finetti representations because operator order between Choi states is equivalent to completely positive (CP) order between the underlying channels. For permutation-covariant channels $N^{(n)}:A^{\otimes n}\to B^{\otimes n}$, where $d_A=\dim A$, we prove that the $k$-system reduced channel is CP-dominated by a mixture of tensor-power channels with error $O(k/\sqrt{n})$ and polynomial dependence on the local dimensions, addressing a question raised by Berta et al. [Math. Program. 194, 781-829 (2022)]. Under the no-signalling condition, we also prove an exponential channel de Finetti theorem where the approximating mixture consists of Choi-almost-iid channels, whose normalized Choi states are almost-iid in the sense of Mazzola-Sutter-Renner. In the case of $r$ defects, the representation error is at most $\mathrm{poly}(n)\bigl(2d_A^4k^3/(nr^2)\bigr)^{(r+1)/2}$ and decays exponentially in $n$ for a suitable choice of parameters $r$ and $k$.

We study multi-armed bandits whose arms supply unknown quantum states and whose mean rewards are defined by a known effect $F$. Each fresh copy may be measured by an arbitrary, adaptively chosen POVM. We prove an exact collapse: the measured relative entropy from an arm state to its confusing reward half-space equals the classical Burnetas-Katehakis functional of $F$'s spectral statistics, and the spectral measurement of $F$ together with an explicit least-favorable state, built from the derivative of the matrix logarithm, forms a saddle point of the underlying measurement game. Consequently, spectral measurement followed by classical KL-UCB is asymptotically instance-optimal among all consistent single-copy policies, in every finite dimension and for every reward effect under the stated nondegeneracy assumptions: adaptive and randomized measurement design cannot improve the leading logarithmic regret coefficient, and neither can storing copies for later single-copy measurement. A self-contained finite-time bound covers general effects and boundary distributions. Any further improvement must come from measurements outside the single-copy class. For consistent policies with arbitrary quantum memory, an amortized relative-entropy argument gives a converse with the Umegaki half-space divergence, and the two per-arm regret floors, $1/K_{\mathrm{inf}}$ and $1/D_{\mathrm{inf}}$, coincide if and only if the arm commutes with $F$. Whether the Umegaki floor is attainable involves a composite quantum Stein problem and a separate reduction to adaptive regret; we pose it as an open problem, with two-copy numerical evidence.

Convex relaxation hierarchies provide lower bounds to the ground state energy of quantum many-body systems that can be computed in polynomial time on a classical computer, at any fixed hierarchy level. However, scaling these methods to large systems and accurate approximations remains challenging due to the computational cost of traditional solvers and the scarcity of efficiency guarantees. In this work, we develop local relaxation hierarchies and efficient, highly parallelisable message passing algorithms for estimating the relaxed ground state energies. We show that the first level of the hierarchy---based on local consistency of pairwise reduced density matrices---is exact for commuting Hamiltonians on trees. We further establish that another hierarchy, based on consistent intervals, converges exponentially fast in the interval size to the ground state energy for weak perturbations of separable Hamiltonians on a chain, thereby providing an efficient classical algorithm for these systems. Then, we introduce two variants of message passing algorithms that run in $\mathcal{O}(n/ε^2)$ and $\mathcal{O}(n/ε)$ time for any fixed level of the local hierarchy on bounded-degree graphs, where $ε$ is the precision for the relaxed ground state energy per site. This assumes that the optimal messages have $\mathcal{O}(1)$ norm---a condition we observe in practical settings in our experiments. These algorithms are based on the subgradient method and the Nesterov-type accelerated gradient descent method applied to an entropy-smoothed objective. Finally, we benchmark the message passing algorithms across different quantum Hamiltonians, lattice geometries, and relaxation levels, validating the theoretical predictions and their potential to surpass standard convex optimisation solvers for this problem. We release the resulting library at github.com/rick1924/gse-message-passing.

Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. In quantum computation our tools for proving unconditional tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting.We prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical arguments, which makes it particularly simple to use. We also us it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require a quantum algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ queries to an input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a similar classical lower bound using their hash mixing lemma. Our noise operator method allows us to use a related but simpler property of hash functions to prove our lower bounds.

Quantum data hiding concerns pairs of states which are highly distinguishable with global measurements, yet nearly indistinguishable when restricted to local operations and classical communication. More than two decades after Eggeling and Werner introduced a multipartite hiding scheme based on Werner states, the optimal dependence of its uniform security guarantee on the number of parties and local dimension remained unknown. We resolve this problem by showing that the distinguishing bias of any pair of $n$-qudit Werner states is $O(n^2/d)$ under measurements whose effects remain positive under partial transposition (PPT) across every bipartition. An explicit pair attains this scaling using only nonadaptive local measurements, establishing worst-case optimality and showing that the PPT relaxation preserves the optimal dependence on both the number of parties and the local dimension. At fixed security, this extends the certified hiding regime from $n=O(d^{1/4})$ to $n=O(\sqrt d)$. Beyond data hiding, the same bound implies that testing any nontrivial unitarily invariant property with adaptive single-copy measurements requires $Ω(\sqrt d)$ copies, yielding separations for any property with dimension-independent sample complexity under collective measurements. Our proof reduces the distinguishing bias to trace norms of partially transposed operators and analyzes them using mixed Schur-Weyl duality, demonstrating the utility of representation theoretic methods developed for port-based teleportation to data hiding and quantum property testing.

Linear threshold functions are $f_{w,θ}(x)=\text{sign}(\langle x,w \rangle -θ)$, where the weight vector $w\in\mathbb{R}^n$ is a unit vector, $θ\in\mathbb R$ is a threshold, and typically $x\in\mathbb{R}^n$ or $x\in\{-1,1\}^n$. When $θ=0$, the LTF is called homogeneous, and we write $f_w:=f_{w,0}$. Such functions are among the most important objects in machine learning, since they serve to linearly discriminate positive and negative examples. We give three positive results about learning LTFs: 1. Suppose we can make real-domain queries, meaning we can compute $f_{w,θ}(x)$ at any $x\in\mathbb{R}^n$ of our choice. We give a quantum algorithm that learns $f_{w,θ}$ up to Euclidean error~$ε$ using $O(\log(n/ε))$ membership queries and $\widetilde{O}(n)$ other gates. Then we have also learned $f_{w,θ}$ up to error $O(ε)$ when $x$ is Gaussian. Classical algorithms need $Ω(n\log(1/ε))$ queries. 2. A homogeneous LTF $f_w$ on domain $\{-1,1\}^n$ where $w$ has only $k$ nonzero entries of the same value, is the Majority function on the support of $w$. Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns $f_w$) using $O(k^{1/4})$ queries. We give an exponential improvement, using $O(\log k)$ queries. 3. Suppose we have a unitary $U$ that can produce (discretized) \emph{quantum examples} under Gaussian measure, corresponding to $\int_x \sqrt{γ_n(x)}|x\rangle |f_w(x)\rangle dx$. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient \emph{Hermite transform} of Jain et al.\ to learn homogeneous LTFs~$f_w$ with error~$ε$ under the Gaussian distribution, using $O(n^{1/4}/\sqrtε)$ applications of $U$ and $U^\dagger$ and $\widetilde{O}(n^2/ε^4)$ other gates.

Cooling an arbitrary mixed state to a pure ground state requires transferring its entropy to an environment. Can a single coherent bath contact accomplish this without repeated bath resets? We develop a new cooling mechanism that transfers the input information into bath degrees of freedom that subsequently decouple, while the system and the remaining bath follow a ground-state path. The bath is discarded only at the end, and the system Hamiltonian remains on and unmodified throughout. We rigorously realize this mechanism for a class of weakly interacting, gapped fermionic systems with local interactions. Starting from any mixed state, our protocol prepares the interacting ground state in total physical time polylogarithmic in the system size and inverse global trace-norm error. It uses two initially empty bath modes per system mode and a single pulse shared across all onsite system--bath couplings. The same pulse prepares each admissible system's own ground state without knowledge of its microscopic parameters. The guarantees follow directly from a non-Markovian system--bath dynamics without an effective Lindbladian description.

Modern smart grids generate increasingly rich operational data and deploy greater numbers of remotely controlled switching assets than ever before, creating new opportunities for data-driven distribution network reconfiguration (DNR). DNR optimizes grid topology to improve efficiency, reduce power losses, and maintain operational constraints, but finding optimal switch configurations remains a computationally demanding combinatorial problem. In this paper, we propose a deep reinforcement learning (DRL) framework for static DNR to systematically investigate how the Q-network architecture affects both solution quality and learning performance. We evaluate multiple architectures within a controlled DRL framework, varying only the Q-network to isolate the contribution of each architectural choice. Our results show that quantum-enhanced Q-networks can achieve higher rewards with fewer parameters than their classical counterpart, suggesting that such architectures are a promising direction for combinatorial power systems optimization.

We prove maximal separations: $n$-qubit systems can have $Θ(n)$ ergotropy, while every efficient process extracts negligible work, even for Hamiltonians consisting of single-qubit terms. We establish an unconditional existential separation and give an explicit construction in the random oracle model. Assuming the existence of quantum-secure pseudorandom functions, this separation extends to the plain model. This work uncovers an important connection between ergotropy and the complexity of catalytic computation---computation where auxiliary qubits must be finally restored to their initial state. Relative to a random oracle, we establish relational and decision problems that: (i) can be solved efficiently with $λ$ catalysts; but (ii) cannot be solved by any algorithm with $cλ$ catalysts, for any $c<1$. We show this by proving query lower bounds for quantum-space bounded algorithms. As a consequence, for computational ergotropy, catalysts prove to be surprisingly powerful---there is a family of Hamiltonians and states for which catalysts enable efficient extraction of the full $Θ(n)$ ergotropy, while every efficient non-catalytic process extracts negligible work. Furthermore, catalysts also allow us to introduce and instantiate the notion of pseudoergotropy---analogous to pseudorandomness. On the other hand, we show catalysts do not change (information-theoretic) ergotropy. Finally, our work also sheds light on the classical aspect of the problem. First, most of our constructions rely on classical states and Hamiltonians and therefore imply analogous results for classical ergotropy. Second, we show that certain proof of quantumness protocols can be used to generically separate classical and quantum catalytic ergotropy.

We study vector subset sum over $\mathbb{F}_3^n$: given $m$ random vectors from $\mathbb{F}_3^n$, find a nonempty subset that sums to zero; the smaller $m$, the more difficult it is to find such a subset. Chen, Liu, and Zhandry (EUROCRYPT'22) introduced an efficient quantum algorithm that solves this problem when $m\approx n^2/2$, where a naive classical algorithm would require exponential time. Subsequently, Kothari, O'Donnell, and Wu (STOC'2026) gave an efficient classical algorithm that only requires $m \approx n^2/3$ vectors, thus removing the hope for an exponential quantum advantage in this parameter regime. Using the framework of Chen, Liu, and Zhandry, we give quantum algorithms that require much fewer input vectors, renewing the possibility of an exponential quantum speedup: for any fixed $ε>0$, our quantum algorithm solves $\mathbb{F}_3$-subset sum in polynomial time with $m=ε\cdot n^2$ vectors. More generally, we establish a full sample--time tradeoff that interpolates between exponential and polynomial runtime. The main ingredient is a deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest. For this, we rigorously establish a sample--time tradeoff that was predicted by earlier algebraic heuristics. For vector subset sums over larger fields, we also significantly improve classical algorithms in Kothari, O'Donnell, and Wu (STOC'2026).

Low-depth syndrome extraction for Calderbank-Shor-Steane (CSS) quantum low-density parity-check codes can be formulated as a proper ordered edge-coloring problem subject to quantum parity constraints. A proper edge-coloring of the CSS Tanner graph ensures that each data or ancilla qubit participates in at most one two-qubit gate per layer, but does not guarantee a valid interleaving of the X- and Z-check measurements as for every overlapping X/Z check pair, the number of shared data qubits on which the X interaction precedes the Z interaction must be even. The minimum number of colors in a proper ordered edge-coloring satisfying the quantum parity constraints equals the minimum two-qubit depth when each stabilizer check is measured with a single ancilla. We introduce local automorphism-aware syndrome compilation (LocalASC), which reduces the constraint system to edge-orbit variables under a subgroup of the Tanner graph automorphisms and lifts each feasible orbit assignment to the full graph. Although the $6$-layer degree lower bound is unattainable for the published weight-$6$ IBM bivariate bicycle codes, we show that this is not universal among two-block CSS codes. Among code instances for which the maximum check weight equals the maximum Tanner graph degree, LocalASC finds depth-optimal syndrome-extraction schedules for several two-block CSS codes with odd component weights, including instances with unequal odd weights. We also obtain lower-bound-saturating syndrome-extraction schedules for several quantum Tanner codes satisfying the same degree condition. To obtain the subgroups used by LocalASC without computing the full automorphism group of the Tanner graph, we construct translation subgroups for two-block group-algebra CSS codes over abelian groups. For quantum Tanner codes, we give conditions under which square-complex symmetries extend to Tanner graph automorphisms.

We present a quantum algorithm that generates a uniform superposition over the spanning trees of a graph -- also known as a q-sample -- using only a sub-linear number of queries to the graph. This goes beyond previous work that focuses on generating classical samples, including a recent quantum algorithm by Apers, Gao, Ji, and Liu [ICALP 2025]. For an $n$-vertex, $m$-edge graph, our algorithm admits a pre-processing step of $\tilde{O}(\sqrt{mn} + m^{1-δ})$, after which each q-sample can be generated in $\tilde{O}(n^{1+2δ})$ for any $δ$. Alternatively, $k$ independent q-samples can be generated at a total cost of $\tilde{O}(\sqrt{kmn})$. We also prove a matching lower bound up to logarithmic factors, showing that our algorithm is essentially optimal. Further tradeoffs are given in the paper. In comparison, the optimal classical algorithms (Anari, Liu and Vuong [FOCS 2022]) need an $\tilde{O}(m)$ pre-processing step, after which each sample costs $\tilde{O}(n)$ operations. These results yield faster quantum walk-based algorithms for counting spanning trees or finding a marked one. Our result is obtained via quantum walk sampling over a sequence of slowly-changing Markov chains. Each chain is an isotropized up-down walk that mixes rapidly to the spanning tree distribution of the input graph. A key ingredient is an amortized data structure supporting fast implementation of the associated quantum walk operators throughout the sequence. This data structure maintains access to a spectral sparsifier and a leverage score sampler that evolve with the underlying graph.

In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.

Mutually unbiased bases (MUBs) describe quantum measurements for which certainty in one basis gives uniform outcomes in the others. Their maximum number remains unknown in dimensions that are not powers of a prime. We introduce an ansatz that, in many dimensions, allows us to construct more MUBs than have previously been found. Each basis in the ansatz consists of a diagonal phase matrix applied to a fixed unitary, which is a tensor product of Fourier matrices and, optionally, any real Hadamard matrix. This construction yields five MUBs in dimension 12, six in dimensions 48, 96, and 192, seven in dimensions 36 and 108, and ten in dimension 648. These bases can then be extended to exceed the tensor product bound, asymptotically, in every eighteenth dimension. Moreover, we show that Paley's real Hadamard matrix can be used to construct $q+1$ bases in dimension $d = q(q+1)$ for every prime power $q\equiv3\pmod4$. This count grows as $\sqrt d$ and cannot be exceeded by tensor products of smaller sets.

The planted clique problem is a promising candidate for quantum advantage with a wide computational-statistical gap and substantial evidence for classical hardness. We study two quantum encodings of classical samples, a natural binary phase state encoding and symmetry-adapted measurements, and determine if they preserve enough information for planted-clique detection, as well as discuss their potential towards algorithmic efficiency. For the binary phase state encoding, we show that constant-advantage detection requires $Ω(n^{1+2\varepsilon}\ln^2 n)$ copies, even under arbitrary joint measurements. Measurements on $\tilde{O}(n^2)$ copies suffice statistically above the logarithmic clique threshold. The symmetry-adapted measurements on the full graph register arise naturally from the Schur transform. We show that the outcome distribution of weak Schur sampling depends on the sampled graph only through its edge count and fails to distinguish the distributions; whereas retaining the representation label and Specht register after discarding multiplicity preserves distance $1-o(1)$. Near-perfect distinguishability survives even if the label is also discarded. We calculate the retained states, providing concrete targets for efficient measurement. Finally, we show that one supplied coherent quantum sample enables an efficient quantum distinguisher, which yields a conditional computational separation from one classical sample under quantum planted-clique hardness. Our results are structural and information-theoretic; efficient detection from one classical graph in the conjectured hard regime remains open.

The Quantum Approximate Optimization Algorithm (QAOA) is regarded as a promising candidate for near-term quantum advantage in combinatorial optimization, yet our ability to study it at scale is limited. Exact recursive formulas have been introduced for predicting QAOA performance on large spin glasses, but the computational cost of evaluating them grows exponentially with the number of QAOA layers, preventing the study of QAOA in the promising high-depth regime. In this work, we show that for the task of computing QAOA energy on any mixed dense spin glass problem, spins approximately decouple into independent spin-boson systems. In the infinite-size limit, the decoupling becomes exact, establishing the spin-boson mapping as a natural framework for the many-body physics of QAOA. This generalized spin-boson mapping gives a recursive procedure for computing QAOA energies that can be executed at modest cost using tensor networks. As a numerical application, we optimize QAOA on pure and mixed spin glasses at depths intractable for prior techniques, observing that higher-degree problems require more layers for a comparable approximation ratio while angle optimization becomes more challenging. While decoupling enables the evaluations of QAOA energies at large size and depth, it does not enable strong simulation of QAOA; a quantum computer is required to sample the bitstring corresponding to the predicted energy.

A central yet mysterious problem in quantum information is the asymptotic distinguishability of quantum states under restricted measurements. Here we look at asymptotic asymmetric hypothesis testing for general multi-mode bosonic Gaussian states restricted to arbitrary collective Gaussian measurements. We establish a single-letter formula for the Stein exponent for many pairs of states, featuring two distinct contributions, corresponding to first and second moments, respectively. Remarkably, the Gaussian-measured relative entropy exhibits genuine non-additivity, but the only effect of additivity violations is to asymptotically decouple first and second moments. We prove this by establishing sufficient conditions for additivity of the second-moment term via novel log-determinant matrix inequalities. Our results not only identify a single-letter expression for the Gaussian Stein exponent in a wide range of practical situations, but also rule out any possible advantage from collective Gaussian measurements when considering centred Gaussian states.

We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input matrix sparsity and $γ:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $γ^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$. For $γ=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic quantum advantage for generic sparse SDP solving.

We construct quantum oracles relative to which quantum-secure one-way functions (OWFs) exist but pseudorandom states (PRSs) with superlogarithmic output length do not. At first glance, this appears to contradict the known black-box constructions of PRS generators from quantum-secure OWFs. The distinction lies in the access model to the oracles; our oracle separation uses \emph{classical-accessible} random oracles that can be accessed only classically even by quantum algorithms. In fact, our impossibility of PRSs applies to \emph{any} classically accessible classical oracle in place of the random oracle, while keeping the other oracle component unchanged, showing the need for coherent access in constructing PRSs. We further show that logarithmic output length pseudorandom function-like states (PRFSs) exist relative to our oracles, giving an oracle separation between classically accessible logarithmic length PRFSs and superlogarithmic length PRSs. This shows that fully black-box PRS length extension from logarithmic to superlogarithmic output length must use coherent access to the underlying short PRS.

Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension $d$ and $M\geq d^2-1$ ports, we construct a unitary circuit of depth $O(\sqrt d)$, independent of $M$ and including resource preparation and port selection, with entanglement fidelity at least $(1-(d^2-1)/(2M))^2$. Thus, at fixed $d$, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on $d$ can also be removed remains open.

In classical fine-grained complexity, the 3SUM Conjecture is used to prove a variety of conditional lower bounds on data structure and graph problems via an initial reduction to the SetDisjointness problem. However, there is an $\tilde{O}(n)$-time quantum algorithm for 3SUM and a direct application of Grover's algorithm to SetDisjointness queries beats the state-of-the-art classical conditional bound by Kopelowitz, Pettie, and Porat (SODA 2016); this shows that these classical bounds do not apply in the quantum setting. Thus establishing analogous conditional lower bounds in the quantum setting requires applying the quantum 3SUM Conjecture to a \emph{quantum} fine-grained reduction from 3SUM to SetDisjointness. We give the first sub-linear time quantum reductions from 3SUM to online SetDisjointness. Via our reduction, the quantum 3SUM conjecture implies a $p + 2q \geqslant 1$ tradeoff bound for quantum SetDisjointness algorithms with $O(N^p)$ preprocessing time and $O(N^q)$ query time. We also give an analogous reduction from 3XOR. These results are derived from a general framework for fine-grained reductions to SetDisjointness which applies to any Abelian 3-Orthogonal Array (3OA) problem with suitable almost-linear hash functions.

We construct protocols for classically verifiable quantum advantage and classical verification of $\mathsf{BQP}$ computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of $\mathsf{BQP}\neq\mathsf{BPP}$, we construct a two-message quantum-advantage protocol that is efficiently and publicly verifiable. Our result can be viewed as a rigorous cryptographic foundation for the heuristic quantum advantage proposals based on \emph{peaked random circuit sampling} of Aaronson and Zhang (arXiv:2404.14493). We also construct two simple protocols for classically verifying arbitrary $\mathsf{BQP}$ computations. The first protocol is privately verifiable and assumes only the existence of qiO. This gives a rare example of a nontrivial cryptographic application of (quantum) iO that does not make additional computational hardness assumptions. The second protocol additionally assumes post-quantum one-way functions and is \emph{publicly verifiable}. To our knowledge, this is the first publicly verifiable protocol for classical verification of $\mathsf{BQP}$ computations under computational assumptions in the standard model. We show that all our results hold when qiO is assumed only for ancilla-free unitary circuits. As evidence supporting this assumption, we prove a worst-to-average-case reduction for obfuscating such circuits. This reduction extends the local-mixing framework of Canetti, Chamon, Mucciolo and Ruckenstein (TCC 2024) under quantum analogues of their assumptions.

Multi-tenant quantum processors expose a pulse-level attack surface in which coherent crosstalk can mimic benign calibration drift at matched average gate infidelity. We present a structural verification and detection framework based on the residual Pauli transfer matrix (PTM). We prove that products of local unital, trace-preserving channels cannot mix weight-1 and weight-2 Pauli operators, even under coherent drift of arbitrary strength or axis. Building on established PTM-to-Hamiltonian relations, we prove that, for any specified qubit pair in an arbitrarily large system, the first-order map from its nine interaction coefficients to the antisymmetric cross-weight feature is an isometry up to scale. Thus, every interaction direction is locally observable near the identity. We also exhibit cancellation of this feature under large local rotations and prove that the full cross-weight norm is invariant under local unitary composition, providing a structural countermeasure. For calibrated small local rotations, shared randomized-Pauli measurements support periodic verification using the evaluated antisymmetric detector. In simulation, $16{,}384$ randomized settings yield a detection threshold of $λ_{\min}\approx0.13$ at a $5\%$ calibrated false-positive target, with approximately $M^{-1/2}$ scaling in the number of settings $M$. Further experiments characterize detection under relaxation, depolarization, native ZZ fluctuations, and time-dependent pulse dynamics. Finally, an FRQI encoding with Pauli-graph quantum Hadamard edge detection reproduces the classical structural edge score to numerical precision.

Characterising open quantum dynamics requires identifying the environmental degrees of freedom that shape the system's evolution. The memory dimension, defined as the size of the smallest effective memory needed to reproduce this influence, quantifies the dynamically relevant environmental resources and provides a common basis for comparing different many-body environments. Here we introduce a pseudo-control protocol that encodes information about the memory dimension in an experimentally accessible interference matrix, whose rank certifies a lower bound on this dimension without direct access to the environment or full process-tensor tomography. Applied to quantum many-body environments, the protocol allows flexible adjustment of the interaction and interval times, revealing how these parameters, environmental dynamics, and system-environment interactions shape detectable memory. Our approach provides a new operational technique for characterising open quantum dynamics and probing the structure of system-environment interactions through their memory signatures.

We give a polynomial-time classical algorithm which samples from the syndrome distribution of a surface code state corrupted by coherent nearest-neighbor $ZZ$ crosstalk. Our algorithm complements the known efficient simulation algorithms for coherent single-qubit errors in the surface code. When both single-qubit coherent noise and coherent crosstalk are present, we find a complexity-theoretic obstruction to efficient simulation: unless the polynomial hierarchy collapses, there is no efficient classical algorithm for sampling from the syndrome distribution, even up to a constant multiplicative error. This is obtained by connecting the syndrome distribution under coherent noise to the output distribution of certain IQP circuits associated with a non-planar graph.

The $f$-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers; our new techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length. We show that, for input length $n$ and sufficiently small constant $ε>0$, a uniformly generated strategy using $q$ qubits and having description length $\mathrm{poly}(q)$, with success probability at least $1-ε$ on every input, implies the following computational bounds on $f$: 1. If the strategies are arbitrary quantum channels, then $f\in\mathrm{QSZK}(\mathrm{poly}(nq))$, where $\mathrm{QSZK}(T)$ is the class of languages having quantum statistical zero knowledge proofs in which the verifier runs in time $T$ (and the simulator in time $\mathrm{poly}(T)$). 2. If the strategies are explicit Pauli-sparse unitaries on $q$ qubits that have at most $s$ nonzero Pauli coefficients, then $f\in\mathrm{DTIME}(\mathrm{poly}(nqs))$. 3. If the strategies are Clifford+T circuits using at most $t$ magic gates, then $f\in\mathrm{DTIME}(\mathrm{poly}(nq2^t))$. Time and space hierarchies then yield explicit functions secure against polynomial and even quasipolynomial qubits $q$ under our computational restrictions. These bounds exceed the $q\le\log n$ bound of Bluhm, Christandl, and Speelman (2022) for inner product function $f=\mathrm{IP}$, at the cost of restricting adversarial computation and increasing honest evaluation complexity.

We present an efficient quantum algorithm for the non-uniform Chebyshev transform. It is defined as the projection of a function onto Chebyshev polynomials sampled at given nodes that are uniform in $x\in[-1,1]$, and hence non-uniform in the angle $θ=\arccos x$, a setting that QFT-based quantum Chebyshev transforms cannot handle. Our construction is based on an improvement of an existing Non-uniform Quantum Fourier Transform (NUQFT) whereby we remove the conditioning from non-uniform node sampling. Hence, error bounds are independent of the geometry-dependent parameter $κ$ of prior work. We use the fact that Chebyshev transform matrix is the average of two Type-II non-uniform DFTs, which we implement with a single controlled NUQFT circuit. We provide explicit oracle constructions, including the row-access oracle previously left as an assumption. The resulting $\varepsilon$-accurate block encoding has $O(1)$ normalization and uses $O(L)$ qubits and $\widetilde O(L^2)$ gates, where $L=\log N+\log(1/\varepsilon)$. We give an end-to-end implementation with complexity analysis, including the success probability and output-state error.

We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Product problem, that requires only $O(\log n)$ NOF quantum communication but $\widetildeΩ(n^{1/32})$ randomized communication. This function builds on the two-party unitary product problem of Arunachalam, Girish, and Lifshitz (TQC 2024). The main technical obstacle is that discrepancy, the standard lower-bound method for NOF, also lower-bounds quantum communication. We instead develop a regularity-based argument for randomized NOF lower bounds, building on the approach of Kelley, Lovett, and Meka and adapting the regularity decomposition of Abboud, Fischer, Kelley, Lovett, and Meka (STOC 2024) to cylinder intersections. Combined with matrix-product estimates of Arunachalam, Girish, and Lifshitz, this yields our randomized lower bound.

Protocols for quantum state tomography can be characterized either by their sample complexity or by the tomographic rate function that governs the large deviation behaviour of error estimates. We establish a framework for the analysis of covariant protocols which allows us to compare these measures. First, we derive the rate functions for several protocols, including random purification-based protocols and the sample-optimal protocol of Haah et al. These rate functions are expressed in terms of a new family of divergences which includes the reverse sandwiched Rényi divergence and Keyl's annealed quantum relative entropy as special cases. We show that these rate functions obey a strict ordering, even though the sample complexity of each protocol is order optimal. We consider a different version of sample complexity based on Wasserstein distance rather than trace distance, and show that the ordering of the rate functions implies analogous strict inequalities for the Wasserstein-type sample complexity. Thus the tomographic rate function is a more fine-grained indicator of the performance of a tomography protocol than the usual sample complexity.

Efficiently testing whether a quantum state possesses a given structure is both a fundamental and a practical task in quantum information. Among the most important structured families are Gaussian states, which underpin quantum optics and many-body physics while defining paradigmatic regimes of efficient classical simulation. Despite the central role of Gaussian states, optimal tests of Gaussianity have remained unknown. Here we give optimal and robust algorithms for testing fermionic and bosonic Gaussian states, with sample complexity independent of system size, particle number, and energy. Remarkably, the protocols implement experimentally feasible measurements associated with known exact symmetry characterizations of Gaussianity, using Bell sampling on two copies for fermions and passive interferometry with photon counting on three copies for bosons. We further obtain tolerant testers requiring joint measurements on a larger, but still constant, number of copies. At the heart of our analysis is a unified approach---which we call the gradient-flow method---that applies across all structured families considered here and underlies our optimal testers: representation theory turns approximate satisfaction of the defining symmetry into quantitative control of the gradient of the rejection probability, allowing a continuous descent from the input state to the target family whose length bounds their distance.

A fundamental problem in physics as well as engineering is equilibration. For example, the regulation of thermal and quantum fluctuations enables thermal and quantum annealing of complex systems. A key question is how different subsystems, such as electrons, nuclear spins and phonons equilibrate on their own as well as with each other. Level crossings play a special role in the dynamics of coupled degrees of freedom, for it is here that entanglement can be maximized to speed up relaxation. Here we use optical methods to establish the electronuclear level scheme, including avoided and unavoided crossings, and to examine equilibration of a rare earth ion (Ho$^{3+}$) in a salt (LiYF$_4$), a model system with quantum fluctuations which can be tuned via an external magnetic field transverse to the crystallographic long axis of the tetragonal host. We track the state of the system by monitoring the populations of the levels as a function of swept longitudinal fields, and discover that at low temperatures, depending on the experimental protocol, vastly different non-equilibrium states arise. We find evidence that nuclear spin excitations diffuse and equilibrate without the assistance of phonons, and tend to acquire higher effective temperatures than the electronic spins and the yet cooler lattice. A theory of thermally assisted tunneling rules out the standard scenario of phonon -assisted tunneling, and instead suggests that fast dynamics at level anti-crossings are facilitated entirely by nuclear spin diffusion. This provides a new understanding of thermalization and related slow relaxation phenomena in dense, multi-component interacting quantum systems.

Measurement compatibility asks whether a family of quantum measurements can be simulated by one parent measurement followed by classical post-processing. We extend this measurement compatibility to the notion of \emph{$d$-compatibility} for measurements, channels, and instruments whose parent passes a $d$-dimensional quantum system and unlimited classical information to the post-processing. We formulate $d$-compatibility as a common linear factorization of operator spaces and operator systems and show that $d$-compatible families form a closed set, even with infinitely many settings and a separable infinite-dimensional input. To certify $d$-incompatibility, we define the compatibility functional as the smallest product of completely bounded norms over common factorizations through a $d$-dimensional register. Using factorization theory of operator spaces, we show that measure-and-prepare channels defined in terms of mutually unbiased bases and pinching channels defined in terms of Heisenberg-Weyl operators are $d$-incompatible in certain regimes of $d$. We also link $d$-compatibility of multi-instruments to the preparability of Choi assemblages using channel-state duality, and use this connection to show that for bipartite states the (in)compatibility of instruments can be used to certify Schmidt numbers and the implementability of the instrument using one-way LOCC protocols. Finally, our compatibility functional also bounds the generalized robustness of compatibility, which we interpret through a memory-bounded nontransient preparation game.

Distribution network reconfiguration (DNR) is a combinatorial optimization problem that seeks a low-loss network topology subject to topological and electrical operating constraints. In this work, we propose a two-stage quantum-classical method for DNR. First, an iterative linear-ramp Quantum Alternating Operator Ansatz (LR-QAOA) searches topologically feasible subspaces constructed using a novel cycle-edge encoding. The encoding guarantees that every represented configuration is a spanning tree while allowing the size and coverage of each subspace to be adjusted to the available qubit budget. Second, the resulting sample distribution is used to guide a mixed-integer second-order-cone programming (MISOCP) solver. The method is evaluated on six distribution networks ranging from 33 to 417 buses through simulation and execution on trapped-ion quantum hardware. Across all six test systems, the MISOCP solver guided by hardware-derived distributions reaches an incumbent within 1\% of the best-known solution in less median solver time than the corresponding unguided solver.

Subgraph detection asks whether an $n$-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph $H$. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of $H$ is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed $r\ge 4$, detecting the clique $K_r$ requires $n^{λ_r-o(1)}$ queries, where $λ_4=19/18$, the exponents $λ_r$ increase strictly with $r$, and $λ_r\ge 2-4\sqrt{2/r}+O(1/r)$. More generally, we prove superlinear lower bounds for detecting every fixed connected graph $H$ with chromatic number $c\ge 4$. These bounds approach quadratic as $c$ grows: for sufficiently large $c$, detection requires $n^{2-O(\sqrt{\log\log c/c})-o(1)}$ queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph $K_{r,r}$ requires $n^{β_r-o(1)}$ queries, where $β_{10}=181/180$ and $β_r\ge 2-O(1/\sqrt{r})$. Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle (CRYPTO 2019) with conditioning on a randomly planted certificate, adapting an argument of Belovs (FOCS 2026). Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer (CPC 2021); for complete bipartite graphs, we use a random construction.

Quantum list recovery (QLR) and quantum list decoding (QLD) seek short lists of logically distinct Pauli corrections consistent with a syndrome and prescribed error constraints. For CSS codes, two issues arise: treating the \(X\)- and \(Z\)-sectors separately can multiply their output list sizes, while distinct classical candidates can collapse after stabilizer quotienting. We study combinatorial upper and lower bounds for balanced folded quantum Reed--Solomon (FQRS) codes and balanced random CSS codes, both studied by Bergamaschi, Golowich, and Gunn (STOC 24). Let \(R\in(0,1)\) be the quantum rate and \(R_1=(1+R)/2\) the common component rate. As the radius \(ρ=(1-R)/2-γ\) approaches the quantum Singleton bound, we have, deterministically for FQRS codes and w.h.p. for balanced random CSS codes, \[ L^\star_{\rm QLR} = \ell^{Θ(R_1/γ)}, \qquad L^\star_{\rm QLD} = Θ\!\left(\frac{1-R}γ\right) \qquad (γ\downarrow0). \] The asymptotically exact QLD radius tradeoff is \[ ρ_L^\star = \frac{L}{L+1}\frac{1-R}{2}. \] These conclusions extend to the average-radius setting. For achievability, building on the work of Brakensiek, Chen, Dhar, and Zhang (STOC 2026), we establish a pairing lemma for joint \(X/Z\) candidate lists that preserves the one-sector coefficient and avoids a product loss in list size. For the QLD converse, we prove a quantum generalized Singleton bound based on the classical projection-and-patching argument with stabilizer distinctness. For the QLR lower bounds, we adapt the folded Reed--Solomon construction of Chen and Zhang (STOC 2025) so that the candidates remain stabilizer distinct. For random CSS codes, we show classical bad lists survive the stabilizer quotient with high probability.

In this paper, we present a polynomial-time quantum algorithm for computing a minimum-sized generating set of solvable black-box groups. Next, we consider the class $Γ_d$ of black-box groups, where every non-abelian composition factor is isomorphic to a subgroup of the symmetric group $S_d$ for a fixed $d$. We design polynomial-time quantum algorithms to compute the direct product decomposition of abelian factor groups and solve the constructive membership problem for factor groups of groups from $Γ_d$. With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from $Γ_d$. Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from $Γ_d$. Finally, we show that the minimum generating set problem for general black-box groups is in $\textrm{NP} \cap \textrm{coAM}$.

Device-independent self-testing certifies a multipartite quantum state from the correlations it produces alone, without assumptions on the inner workings of the devices. Most existing self-tests, however, break down as soon as the parties can exchange messages. We consider a relaxed setting in a quantum network, where in the honest version of the protocol, the parties never communicate, yet certification remains sound even in an untrusted case where the untrusted devices secretly exchange classical messages within a bounded distance in the network. We show that the code space of the toric code, distributed over a network with the geometry of a torus, can be self-tested in this setting in a noise-robust way, against communication up to distances proportional to the network diameter. We also develop an algorithmic method for constructing such protocols and extend our results to the surface code and cluster states, robust to one round of nearest-neighbor classical communication

Resource theories provide a universal framework for quantifying properties of quantum states, such as entanglement, magic, athermality, and asymmetry, as resources under various constraints encountered in quantum science. Since realistic settings typically impose several constraints at once, it is important to study multi-resource theories that combine them. Among these, combinations with asymmetry are especially natural, as symmetry is fundamental and ubiquitous in physics. Here we develop a general theory that treats combinations of finite-group asymmetry with a broad range of resource theories in a unified manner. Our key observation is that the effect of combining the two constraints is governed by the accessibility of symmetry information under the underlying resource theory: whether the information needed for the conversion can be extracted from the input and used to control free operations. If this can be done with asymptotically vanishing error, we show that the conversion rate of the combined theory equals the smaller of the rates of the two constituent theories, so combining them incurs no additional cost. This condition holds for LOCC on arbitrary mixed multipartite states, magic-state conversion of multiqubit systems under Clifford symmetries, and Gibbs-preserving operations. Thermal operations, being time-translation covariant, can access only limited symmetry information, giving an additional compatibility condition between the two symmetries. We also analyze symmetry imposed on elementary operations rather than only on the resulting channel. We establish analogous results for LOCC and thermal operations under suitable assumptions, and for magic when the symmetry is represented by Pauli operators. Finally, we show that finite-group symmetry does not reduce the asymptotic ergotropy per copy and hence introduces no new completely passive states.

Every square matrix decomposes its underlying Hilbert space into generalized, nonorthogonal eigensubspaces. We show that a quantum computer can perform such an oblique eigenprojection $Π$ given block encoding access to the input matrix. Our approach has a query complexity nearly linear in the inverse gap and a normalization factor close to $\lVertΠ\rVert$ under a spectral-set condition on the input. This covers common assumptions on the numerical range or diagonalizability and matches known results for orthogonal eigenprojections. We achieve this with a two-sided block preconditioning that uses a discrete Fourier transform of the matrix resolvent. We describe applications to: (i) preparing eigenstates of matrices with complex eigenvalues, extending the quantum eigenvalue transformation algorithm of Low and Su beyond real spectra; (ii) solving continuous-time algebraic Riccati equations, cubically speeding up a prior solver of Rodenas-Ruiz, Zhao, and Lee; and (iii) solving ordinary Sylvester equations, quadratically improving a direct augmented method of Wang and Liu. Our result suggests a promising route to applying nonanalytic matrix functions on quantum computers.

Constructing explicit codes matching the parameters of random codes has been a central and largely elusive question in coding theory. The quantum setting is even more challenging since it is highly desirable that the quantum code be an LDPC code. Local coordinate-wise linear (LCL) [Levi, Mosheiff, and Shagrithaya, FOCS 2025] witnesses provide a unifying language for many coding-theoretic properties, from distance to list decoding and list recovery. In particular, it provides a framework to study properties of random linear codes, which achieve optimal parameters for many properties of linear codes. For CSS quantum codes, however, a local witness has two distinct ranks: its physical rank before quotienting by stabilizers and its logical rank after quotienting. We develop a quantum version of the LCL framework for nested spaces $S \subseteq C$, in which local constraints are imposed on physical representatives while independence is measured in the logical quotient $C/S$. The resulting theory gives a threshold theorem for random CSS codes, and as a consequence shows that the per-sector rate threshold is equal to the classical rate threshold. We also define a quantum analogue of subspace design [Guruswami and Xing, STOC 2013] and show that they can be described in a natural manner within the quantum-LCL framework. Finally, we give explicit constructions for arbitrary folded quantum-LCL properties, in a manner similar to the LCL derandomization of [Jeronimo and Shagrithaya, STOC 2026]. As a consequence, we obtain the first explicit constructions of quantum list-decodable codes and list-recoverable codes that have optimal list sizes, in addition to explicit quantum subspace design codes. We note that all our explicit constructions are qLDPC codes, an important property for quantum error-correcting codes.

Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum $p$-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum $p$-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum $p$-spin model at temperatures below that for which classical algorithms are also (almost) efficient.

In this work, we consider the fundamental task of estimating the purity of an unknown state to within $\textit{multiplicative}$ error $\varepsilon$. When one can perform general collective measurements, $Θ\left(\frac{\sqrt{d}}{\varepsilon^2} + \frac{d}{\varepsilon}\right)$ copies are known to be necessary and sufficient for this problem [AISW20]. However, implementing collective measurements on such a large number of copies can be experimentally demanding, and we thus aim to characterize the copy complexity of this problem with incoherent measurements. In this setting, the only non-trivial result is a non-adaptive algorithm that uses $O\left( \frac{d}{\varepsilon^2} + \frac{d^2}{\varepsilon} \right)$ copies [PTTW26], which is polynomially larger than the best-known lower bound. Our first result is a new algorithm performing non-adaptive incoherent measurements that succeeds using $O\left( \frac{d}{\varepsilon^2} + \frac{d^{3/2}}{\varepsilon} \right)$ copies, improving on the latter term in the copy complexity. Moreover, we show that for any algorithm restricted to non-adaptive measurements, the above copy complexity is optimal. We also develop a new adaptive estimator for the purity of a state that improves on the above complexity in the high-precision regime, i.e., for $\varepsilon = o(1/d)$. We also show that the non-adaptive and adaptive estimators together yield the optimal complexity for incoherent purity estimation; in particular, we show that the copy complexity of this problem is $$ Θ\left(\min\left\{ \frac{d}{\varepsilon^2} + \frac{d^{3/2}}{\varepsilon}, \frac{d^2}{\varepsilon} + \frac{\sqrt{d}}{\varepsilon^2}\right\} \right). $$

We study a generalization of undirected $st$-connectivity to graphs whose edges carry quantum operations. Let $G=(V,E)$ be an undirected graph on $n$ vertices in which each edge $\{u,v\}$ is labeled by a unitary $U_{uv}\in\mathbb{C}^{k\times k}$, with $U_{vu}=U_{uv}^\dagger$. We assume the labels form a \emph{flat} connection: the ordered product of labels along any path between a pair of vertices $u$ and $v$ is independent of the path. Equivalently, the connection is pure gauge, i.e., gauge-equivalent to the trivial connection; such graphs are exactly the consistent connection graphs of spectral graph theory and the noiseless instances of group synchronization. Consequently, whenever $s$ and $t$ are connected, transporting a state from $s$ to $t$ defines a unique unitary $U_s(t)$. Given states $|ψ_s\rangle,|ψ_t\rangle\in\mathbb{C}^k$ and an oracle that returns the neighbours of a vertex while coherently applying the corresponding edge unitaries, the \emph{$st$-transport problem} is to decide whether $s$ and $t$ are connected and, if so, to estimate the squared overlap between $U_s(t)|ψ_s\rangle$ and $|ψ_t\rangle$ to additive error $\varepsilon$. When $k=1$ and all labels are trivial, this is exactly undirected $st$-connectivity. We give a bounded-error quantum algorithm for $st$-transport that runs in time $\widetilde{O}(n/\varepsilon)$ and uses $O(\log n+\log k+\log(1/\varepsilon))$ space. We do this by designing a transducer and applying a Metropolis-Hastings reweighting to the input graph. We also prove an $Ω(n)$ quantum query lower bound that holds even when $s$ and $t$ are promised to be connected, so for constant $\varepsilon$ our algorithm is optimal up to polylogarithmic factors.

Non-local quantum computation (NLQC) asks two parties to apply a joint operation to their quantum inputs using an entangled resource state and one round of simultaneous quantum communication. NLQC has applications across quantum information, including attacks on quantum position verification, communication complexity, and quantum gravity. Every bipartite unitary has an approximate NLQC protocol with finite entanglement, and exact protocols are known for several structured families. However, it has remained open whether every fixed unitary admits an exact protocol with finite-dimensional resources. We show that, even for two qubits, Haar-almost every unitary does not admit such a protocol, even when the resource state and local operations are tailored to the target. The proof first shows that smooth deformations of an exact protocol can only change its target by local unitaries. For a fixed architecture, semialgebraic geometry limits the exact protocols to finitely many connected families, so each architecture reaches only finitely many local-unitary orbits. Taking the union over all architectures, the exactly implementable unitaries form countably many local-unitary orbits. We also show that some natural targets do not admit a protocol: the controlled phase $\mathrm{diag}(1,1,1,e^{iθ})$ has no exact protocol with finite-dimensional resources whenever $e^{iθ}$ is transcendental, for instance for $θ= 1$. Our results also apply to localizable quantum measurements, whose outcome is obtained from local measurements on inputs and a shared entangled resource state without communication. A rank-one projective measurement in a Haar-random basis is almost surely not localizable with a finite-dimensional resource state and finitely many local outcomes.

Entanglement and state distinguishability have long been central topics in quantum foundations. While each has developed into a rich subject in its own right, they can be connected through measurements in complementary bases. This connection provides insights into quantum and classical correlations and underlies many information-processing tasks, most notably quantum error correction (QEC). However, it has remained largely open whether the connection between entanglement and distinguishability extends to general measurements without assuming complementarity. We answer this question in the affirmative: the key is irreducibility induced by measurements, a much more relaxed condition than complementarity. Specifically, for POVMs satisfying an irreducibility condition, we establish a quantitative relation between the infidelity of one-sided local transformation into a maximally entangled state and the failure probability in state discrimination. We then characterize when both errors can vanish simultaneously. Our results have direct applications to entanglement distillation and QEC. Their errors can be certified by estimating classical input-output correlations from experimentally accessible local measurements, without requiring complementarity. The results also extend to quantum measurement theory. We derive novel trade-off relations that bridge two historically distinct approaches: information gain--irreversibility and observable noise--disturbance. Our connection between entanglement and distinguishability via irreducibility thus offers a common framework for entanglement distillation, QEC, and measurement trade-offs.

Quantifying dissipation is essential for controlling quantum noise and characterizing open-system dynamics. In practical experimental settings, residual noise may still persist despite efforts to suppress it, making it important to determine whether the dissipative strength remains within a prescribed tolerance threshold. We study this question for an unknown, time-independent Lindblad generator with bounded strength, where the jump operators are local but with unrestricted overlap, using only memoryless forward-evolution access. The task is to distinguish dissipative strength of at most $\varepsilon_1$ from strength of at least $\varepsilon_2$, for $0 \leq \varepsilon_1 < \varepsilon_2$, measured in the canonical dissipator's normalized Frobenius norm. We give an algorithm that solves this task in total evolution time $O(\varepsilon_2/(\varepsilon_2-\varepsilon_1)^2)$ for all nontrivial thresholds, with constant success probability, and provide a matching lower bound $Ω(\varepsilon_2/(\varepsilon_2-\varepsilon_1)^2)$ that establishes optimality even for adaptive protocols. This extends dissipation testing to the tolerant setting and eliminates the bounded-degree requirement, making the framework applicable to a broader range of experimentally relevant settings.

In the study of quantum process tomography, it has remained open how to learn a unitary channel in diamond distance with strictly parallel queries as efficiently as with sequential queries. Sequential queries allow one to exploit adaptivity to refine the estimate and adjust the learning strategy accordingly, whereas such adjustments are impossible for parallel queries. From the perspective of higher-order quantum operations, any parallel learning strategy can be simulated by a sequential one, whereas the converse does not hold in general, suggesting that sequential learning strategies are potentially more powerful. Contrary to this intuition, we present a new protocol for learning an unknown $d$-dimensional unitary channel to within $\varepsilon$ in diamond distance using $\mathcal{O}(d^2/\varepsilon)$ parallel queries, matching the lower bound presented in [Haah, Kothari, O'Donnell, and Tang, FOCS '23]. Our protocol thus closes the gap between parallel and sequential strategies for unitary channel tomography. As applications, it achieves optimal query complexity for boundary-regime quantum channel tomography and improves the query efficiency of the best-known protocol for tomography of fermionic linear optics.

We determine the exact strong converse exponent for secret-key transmission and generation over general finite-dimensional quantum wiretap channels, measuring reliability and secrecy jointly by squared fidelity to an ideal secret key. We introduce a novel Renyi private information whose regularization characterizes this exponent. An exact integral representation in terms of ordinary private information gives a uniform continuity bound, showing that the regularized quantity converges to private capacity as the Renyi order approaches one. This establishes for any wiretap channel an exponential fidelity decay at every rate above private capacity.

We introduce a local and distributed framework for decoding quantum LDPC codes. Built atop belief propagation (BP), the architecture combines strictly local processing of syndrome information, local feedback, autonomous operation, and highly parallelized decoding. We establish the framework at two complementary levels. First, we show that any code exhibiting a threshold under iterative BP decoding can be promoted to an autonomous local measurement-and-feedback dynamics while preserving that threshold. We then turn to codes for which naive BP does not itself exhibit threshold behavior. Our key observation is that BP can nevertheless provide sufficiently accurate \emph{local} marginal information: active syndrome defects use these local beliefs to \emph{move}, pair, and annihilate through asynchronous feedback. We demonstrate numerically that this construction exhibits threshold behavior in the point-like sectors of the two- and three-dimensional toric codes, where conventional BP decoding fails. Exploiting the graph-generality of BP, we then study the inference dynamics on the membrane-like sector of the three-dimensional toric code and in a family of bivariate-bicycle quantum LDPC codes.

Can a symmetry be tested optimally without using the quantum resource naturally associated with it? For parallel subgroup-versus-Haar testing, we derive a quantitative representation-theoretic converse for every protocol with zero type-I error: the excess type-II error is bounded below by the sum of two nonnegative penalties, one for weight on suboptimal subgroup types and one for deviations of within-type Schur profiles from their typewise extremal profiles. At optimality, both penalties vanish, yielding support and weight locking for every optimal system marginal. Disjointness of the resulting locked set and the free marginal set rules out resource-free optimality, whereas overlap alone does not establish attainability. For the diagonal torus in dimension $d\geq 2$, optimal testing without coherence is possible only with a single query. We determine both the exact optimal type-II error over all protocols with incoherent system marginals and the minimum system-marginal coherence required to attain the unrestricted optimum. For the orthogonal subgroup in dimension $d\geq 2$, a real protocol attains the optimum at every query number. For the qutrit Clifford group, Wigner-positive optimal protocols exist at three and four queries but not from five through nine; whether they exist beyond nine queries remains open. Together, these results relate the subgroup- and query-dependent resource requirements of optimal symmetry testing to structural constraints on optimal system marginals.

Multimode optomechanical scattering is ubiquitous in free-space imaging protocols, but its radiation pressure counterpart is challenging to detect with extended objects. Here we demonstrate radiation pressure actuation of a nanomechanical membrane using dynamically structured light from a spatial mode demultiplexer (SPADE). Using single- and two-mode illumination, we directly image the position-dependent intermodal coupling between Hermite-Gauss (HG) modes as mediated by the membrane's motion. As an application, we use multimode radiation pressure feedback to simultaneously cool two nearly degenerate membrane modes. Our results are applicable to diverse mechanical systems and serve as a stepping stone to SPADE-based quantum optomechanics.

It is shown that Shannon entropy, Fisher information, and quantum-mechanical kinetic energy may all be viewed as measures of correlation. We begin with a fundamental correlation-destroying map: a joint probability density $ρ(x,y)$ is replaced by $ρ_x(x)ρ_y(y)$, the product of its marginal distributions. In the discrete case, Shannon's entropy is nondecreasing under this map. For continuous distributions, this fundamental map leads to a well-behaved, coordinate-invariant correlation measure, analogous to the discrete Shannon entropy: \[ I[ρ] = h[ρ_x] + h[ρ_y] - h[ρ]. \] In the continuous case, however, another measure appears: Fisher information. The relative Fisher information $J(ρ\|ρ_xρ_y)$ behaves similarly under the fundamental map. For a normalized real quantum wavefunction, this decrease is exactly proportional to the decrease in mean kinetic energy, \[ \langle T\rangle_ψ- \langle T\rangle_Φ= \frac{\hbar^2}{8m} J(ρ\|ρ_xρ_y), \qquad Φ= \sqrt{ρ_x ρ_y}. \] In Jaynes's language, the result supports a principle of minimum justified correlation: given physical constraints and a set of possible distributions or related amplitudes satisfying those constraints, select from that set those with the least correlation. This is Part I of a two-part paper. Here we develop the entropy, Fisher-information, and kinetic-energy identities above, and state the principle they support. Part II addresses questions which Part I raises but leaves unanswered: multiple solutions, time dependence, the role of spin, a route to the Schrödinger equation itself, and a proposed experimental test. AI has been used.

Suppose a Hamiltonian $H$ has a unique ground state $|ψ_0\rangle$ with an eigenvalue $E_0$, and we have an estimate $\tilde{E}_0$ such that $|\tilde{E}_0-E_0|\leqδ$, and there is a gap of at least $3δ$ between $E_0$ and all other eigenvalues. Suppose we have a unitary $A$ available that can produce a "guiding state'" $A|0\rangle$ that has overlap at least $γ$ with $|ψ_0\rangle$. We show how to obtain an $\varepsilon$-approximation of $|ψ_0\rangle$ using $O(\log(1/\varepsilon)/γδ)$ applications of $U=e^{iH}$ and $A$, and their inverses. We give two different algorithms, one based on interleaving amplitude amplification and error-reduction in the style of [HMdW03], and one using the composition of transducers. This paper is the state-preparation follow-up to our two recent ground-state-energy estimation papers [JW26, SdW26]. Combined, our results show an optimal $O(\log(1/\varepsilon)/γδ)$ upper bound for ground state preparation.

Quantum algorithms are powerful tools for finding symmetries of classical objects, most famously through Shor's algorithm and the framework of the Hidden Subgroup Problem (HSP). In this work, we study quantum algorithms for learning symmetries of quantum objects. Our starting point is the recently introduced State Hidden Subgroup Problem (StateHSP), a quantum generalisation of HSP in which the task is to learn the symmetry subgroup of a quantum state. We obtain positive results for non-abelian StateHSP, giving efficient quantum algorithms whenever the hidden subgroup is normal and for ambient groups belonging to a broad class of non-abelian groups, extending the previous general theory beyond the abelian setting. StateHSP learns \emph{Bose} symmetries, associated with linear representations, whereas physically equivalent pure states are defined only up to global phase. Motivated by this, we introduce a new \emph{Anyonic} state symmetry learning problem based on a more physically natural notion of symmetry than that considered by StateHSP. We give an efficient quantum algorithm by reducing the problem to StateHSP, where the reduction relies on a new connection between linearisations of projective representations and linear error-correcting codes. As an application, we obtain an improved algorithm for learning stabiliser groups that applies to mixed qudit states of arbitrary local dimension. Finally, we introduce symmetry learning problems for other quantum objects, including unitaries, Hamiltonians, and finite collections of states, and obtain efficient quantum algorithms by reducing them to instances of StateHSP.

We show that the optimal commuting operator correlation for a variant of Coladangelo's two-player generalized nonlocal game, based on the embezzlement of entanglement, is a commuting operator self-test. Our result gives the first correlation self-test for an exact entanglement embezzlement protocol in the commuting operator framework. Because the unique optimal correlation necessitates the exact embezzlement of entanglement, the correlation is unrealizable using quantum tensor-product models, even if the local spaces are allowed to be infinite dimensional. As such, our result provides an example of a commuting operator self-test where the Hilbert space shared by the two parties cannot be factored into a tensor-product of local spaces that is compatible with the local measurement operators. Our main proof technique relies on Harris' unique abstract state characterization of exact embezzlement of entanglement involving Cuntz algebras.

For every odd prime power $q$ and $D=q+1$, we construct an infinite family of Ramanujan quantum expanders of degree $D$. The construction transfers Morgenstern's Ramanujan Cayley graphs on $\operatorname{PSL}_2(\mathbb{F}_{p})$ for $p$ which is an even power of $q$, through the odd irreducible subrepresentation of the Weil representation of $\operatorname{SL}_2(\mathbb{F}_{p})$. For a quantum expander of dimension $N$, our implementation uses $O(\log^2 N)$ elementary gates, and $O(\log N)$ ancilla qudits, using a fixed finite gate set depending on $q$. An advantage compared to the previous work of Iyer, Jain, Jordan, and Somma (FOCS 2026) is that assuming the quantum circuit is implemented exactly, we satisfy the $2\sqrt{D-1}/D$ singular value bound exactly without any additive error.

We study exact learning with membership queries for concept classes $\mathcal C\subseteq\{0,1\}^N$, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted $\mathsf{D}(\mathcal C)$, $\mathsf{R}(\mathcal C)$, and $\mathsf{Q}(\mathcal C)$, respectively. The two canonical quantum speedups in this model are witnessed by Grover search and Bernstein-Vazirani, leading to the longstanding conjecture $$ \mathsf{R}(\mathcal C)=O(\mathsf{Q}(\mathcal C)^2+\mathsf{Q}(\mathcal C)\log N). $$ We first refute this conjecture by constructing concept classes $\mathcal C$ and $\mathcal C'$ satisfying \[ \mathsf{R}(\mathcal C)=Ω\!\left(\frac{\mathsf{Q}(\mathcal C)^3\log N}{\log \mathsf{Q}(\mathcal C)}\right) \qquad\text{and}\qquad \mathsf{D}(\mathcal C')=Ω(\mathsf{Q}(\mathcal C')^3\log N). \] The first bound matches the upper bound of Arunachalam et al.~[Quantum'21] up to constant factors, while the second matches the upper bound of Servedio and Gortler~[SICOMP'04]. In particular, this shows that the saving in the randomized upper bound of Arunachalam et al. fundamentally relies on randomness. Apart from characterizing the optimal relationship between classical and quantum query complexity, our results are the first to show that quantum speedups for learning can go beyond the Grover and Bernstein-Vazirani paradigms.

Computational self-testing gives a classical verifier command over the quantum register of a single computationally bounded prover. We use this framework to construct the first argument system for BQP with quasilinear total resource requirements in the circuit model. Our argument system is based on the learning with errors (LWE) assumption and requires total resources of $O(\mathrm{poly}(λ, \log g)\cdot g)$ for delegating a circuit with $g$ gates, where $λ$ is the LWE security parameter. This is achieved by constructing a new computational self-test for certifying the prover's quantum state and using it to dequantize the efficient verification protocol of Broadbent (ToC 2018). Specifically, this self-test enables the verifiable, random remote state preparation of tensor product states of the single-qubit Clifford observables $σ_X, σ_Y, σ_Z, (σ_Y-σ_X)/\sqrt{2}$ and $(σ_Y+σ_X)/\sqrt{2}$, with constant robustness: the verification error is independent of the number of prepared qubits. This approach was first proposed by Coladangelo et al. (ToC 2024) in the multi-prover setting. We replicate their result in the single-prover setting by applying the compiler proposed by Kalai et al. (STOC 2023)---which turns any nonlocal game into a single-prover argument system---to a modified version of their self-test.

We reveal an unexpected connection between the parallel Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. The twirling channel induced by the parallel Kac's walk on the symmetric subspace is exactly encoded by a classical Markov chain on partitions, which lifts to a parallel KMP process on complete graphs. This correspondence reduces the analysis of the twirling channel to the mixing of the parallel KMP process. We prove that $O(\log d+\log(1/\varepsilon))$ repetitions suffice to approximate Haar twirling on the symmetric subspace of $(\mathbb C^d)^{\otimes t}$ to error $\varepsilon$, uniformly in the number of copies $t$. For the standard KMP process on general graphs, we prove a mixing-time analogue of Aldous's conjecture: at fixed accuracy, the mixing time of the $t$-particle process is at most a constant times the single-particle mixing time multiplied by the logarithm of the number of vertices, uniformly in $t$. As an application, we improve the total variation mixing-time bound for coordinate hit-and-run on the $n$-dimensional standard simplex from $\widetilde O(n^3)$ (Kook and Vempala, 2026) to $\widetilde O(n)$, while removing the dependence on the initial distribution. Our main technical contribution is conditional product structure for both parallel and standard KMP processes. Conditioned on suitable auxiliary randomness, the labeled particles evolve independently. Combining this structure with an exact coupling yields mixing bounds uniform in the number of particles for both unlabeled KMP models. These bounds are sharp up to logarithmic factors and imply rapid convergence of the parallel Kac twirling channel on the symmetric subspace.

Entanglement distillation from noisy bipartite states and reliable quantum communication over noisy channels are fundamental tasks in quantum information theory, yet optimal coding schemes typically rely on prior knowledge of the underlying state or channel. Here, through Schur-Weyl duality, we establish a universal quantum error-correction principle that removes this dependence entirely. We show that the irreducible permutation spaces arising from the local Schur-Weyl decomposition of many identical copies of an unknown bipartite mixed state form maximally entangled quantum code spaces, with an error structure determined entirely by representation theory. Correcting these symmetry-resolved errors yields universal protocols for entanglement distillation and quantum communication that achieve coherent-information rates with exponentially vanishing error and optimal second-order correction. The protocols are invariant under local unitaries and allow both input marginals to be recovered exactly. At finite block length, their achievable rates are governed by an associated Schur-Weyl information spectrum, which we relate to Petz-Rényi conditional entropies of the underlying state. The resulting sample complexity depends only on the relevant spectral ranks, rather than on the respective Hilbert space dimensions. In particular, for $n$-qubit states of $O(\operatorname{poly} n)$ global rank, we show that a Petz-Rényi conditional-entropy promise suffices for optimal sample-efficient entanglement distillation. Altogether, these results identify Schur-Weyl duality as a fundamental and general mechanism for optimal, tomography-free universal quantum coding, placing entanglement distillation, quantum error correction and quantum communication within a unified representation-theoretic framework.

Pulsed light is represented by density matrices whose correlation functions have different properties of stationarity and coherence. We show that these density matrices yield equivalent measurement results after accounting for finite detection times. This in turn reveals a physical meaning to the length of a quantization cavity and explains the origin of the physical spectrum for pulsed light. By generalizing the density matrices for pulsed Gaussian states of light, we can describe pulsed light of varying statistics in the same basis and relate the photocount rate to the pulse spectrum.

We establish improved locally Markovian properties of quantum Gibbs states at every fixed positive temperature. For finite-range interactions of bounded interaction degree, the conditional mutual information (CMI) decays exponentially with separation, with a prefactor exponential in the boundary size. This improves the exponential volume dependence of the local Markov bounds established by Chen and Rouzé \cite{Chen2025}. For exponentially and stretched-exponentially decaying interactions, we obtain stretched-exponential CMI decay with a boundary-dependent prefactor. For power-law interactions, we prove inverse-logarithmic or algebraic decay with polynomial region-size dependence. Our proof is static, in contrast to the dynamical approach of Chen and Rouzé. We compare the Gibbs state with a product state obtained by removing boundary interactions, reducing the CMI bound to a relative-entropy loss that we control using locality estimates.

Kac's walk is a classical local random walk whose action on a single real unit vector in dimension $d$ mixes in total variation in $Θ(d\log d)$ sequential steps~\cite{PS17}. Lu, Qin, Song, Yao, and Zhao introduced a parallel version of Kac's walk that mixes a single quantum state in $O(\log d)$ rounds~\cite{LQSY+26}. After discretizing the randomness and replacing it by suitable pseudorandom primitives, this parallel walk gives rise to pseudorandom state scramblers, and was subsequently shown to yield pseudorandom unitaries~\cite{LQSY+25}. We study what happens when the parallel Kac's walk acts simultaneously on $k$ orthonormal quantum states. We prove that, for any $1\leq k < d$, after $O\!\left((k+\log d)\log(d/\varepsilon)\right)$ steps, the joint distribution of the $k$ output states is $\varepsilon$-close, in both Wasserstein and total variation distance, to that obtained by applying a common Haar-random unitary to the same inputs. This generalizes the dispersing property of the parallel Kac's walk from a single quantum state to multiple orthonormal quantum states. Equivalently, viewing an ordered collection of $k$ orthonormal states as a point on the complex Stiefel manifold $V_{d,k}=\{X\in\mathbb C^{d\times k}:X^\dagger X=I_k\}$, we show that the parallel Kac's walk mixes rapidly on $V_{d,k}$, with both Wasserstein and total variation mixing times bounded by $O\!\left((k+\log d)\log(d/\varepsilon)\right)$. This extends the Wasserstein mixing result of Pillai, Smith, and Vaikuntanathan for the standard Kac's walk on real Stiefel manifolds~\cite{PSV26}.

Strong-to-weak spontaneous symmetry breaking (SWSSB) is a novel phase transition in mixed states associated with the loss of global charge information. In this work we study fermions with $U(1)$ symmetry under infinite density dephasing and derive the SWSSB properties of the resulting mixed states. Our central observation is that at infinite dephasing every Renyi correlator is exactly the spin-spin correlator of a compact XY model, whose Boltzmann weight is the squared full-counting-statistics generating function of a classical ensemble built from the parent state. For the Renyi-2 correlator it is the full counting statistics of the parent state itself. We complement the infinite dephasing mapping with a novel diagrammatic expansion for the Renyi-1 correlator, applicable to any diagonal mixed state, which computes the couplings of the Renyi-1 XY model. We also study a replica field theory for even Renyi index quantities, applicable at finite dephasing. Our analysis indicates that fully dephased metals display long-range SWSSB in $d\geq 2$, as confirmed numerically and experimentally in $d=2$, and quasi-long-range SWSSB in $d=1$. For insulating parent states both an SWSSB and a trivial phase are possible at infinite dephasing depending on UV details. Long-range SWSSB in $d\geq 3$, or quasi-long-range SWSSB in $d=2$, survives above a nonuniversal, Renyi-index-dependent threshold and is lost when the parent state is deep in the insulating phase, with the exception of quantum Hall insulators which generically have quasi-long-range SWSSB. For even Renyi indices we also determine the stability of the SWSSB phase away from infinite dephasing and derive the universality class of the SWSSB transition.

We study the query complexity of testing quantum juntas. Given an unknown $n$-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most $k$ qubits or is $\varepsilon$-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to $U$, but not to $U^\dagger$ or controlled-$U$. We give tight bounds for both unitary and channel junta testing. For sufficiently large $k$, $n \ge 2k$, and a broad range of $\varepsilon$, both problems have query complexity $Θ\left(k/(\varepsilon^2\log k)\right)$. Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an $\widetilde{O}(k)$ upper bound and a $\widetildeΩ(\sqrt{k})$ lower bound at constant $\varepsilon$, establishing the optimal $Θ(k/\log k)$ query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant $\varepsilon$, they also give a separation between $Θ(k/\log k)$ forward queries and $\widetilde{O}(\sqrt{k})$ queries with inverse access.

Efficient end-to-end entanglement distribution in quantum information networks requires routing under limited resources and fidelity constraints. We study entanglement routing as a fidelity-constrained unsplittable multicommodity flow problem that maximizes the number of admitted requests. As a proof of concept, we integrate neutral-atom quantum optimization into a hybrid classical--quantum column-generation framework. A classical restricted master problem selects routes, while a pricing problem generates fidelity-feasible paths. We formulate this NP-hard constrained shortest-path pricing problem as a quadratic unconstrained binary optimization (QUBO) problem and address it with hardware-aware register embedding and instance-driven pulse shaping. To our knowledge, this is the first study of neutral-atom quantum optimization as a pricing oracle for fidelity-constrained entanglement routing. On small benchmark instances evaluated with neutral-atom processor emulators, the method, combined with warm-start and post-processing, achieves an optimality gap below 1% across all tested sizes; the selected simulated-annealing route-generation baseline exhibits gaps of up to 6%. These results indicate that the generated bitstrings can provide useful candidate routes for classical refinement within column generation. This proof of concept does not establish quantum utility or scalability; further evaluation on larger instances, against stronger classical baselines, and on quantum hardware is needed.

Demonstrating quantum advantage on current quantum hardware is a central goal of quantum computing, and random quantum circuits underpin many leading proposals. Yet sampling-based demonstrations are often difficult to verify, while observable-based approaches face a different challenge: concentration can suppress differences between circuit instances. Recent experiments have put forward the estimation of out-of-time-order correlators (OTOCs) in random circuits as a promising task for verifiable quantum advantage, yet whether their circuit-to-circuit fluctuations survive concentration as system size grows has remained open. Here we show that they do. For broad classes of local random circuits in any fixed spatial dimension, we prove inverse-polynomial fluctuations of fixed-order OTOCs at system-scale depths. In one-dimensional Haar-random brickwork circuits, we further show that macroscopically many gates contribute to these fluctuations, yet in each layer they remain confined to a sublinear-width region. As a byproduct, we develop a classical algorithm exhibiting the first rigorous improvement over brute-force classical simulation of OTOCs in 1D. Although classical hardness remains open, our results rule out strong concentration as an obstruction to OTOC-based proposals for verifiable quantum advantage.

Correlations between optical modes, ranging from classical fluctuations to quantum entanglement, are a cornerstone of modern optics and emerging quantum technologies. However, probing these correlations on the natural timescale of electronic motion - the attosecond regime - remains a major challenge. Here, we generate and characterize correlated attosecond extreme-ultraviolet (XUV) emission by perturbing gas-phase high-harmonic generation with two-mode bright squeezed vacuum. The signal and idler fields imprint their correlated amplitude and phase fluctuations onto two families of harmonics, thereby transferring these correlations from the infrared to broadband XUV modes. Even harmonics serve as an intrinsic attosecond phase-sensitive probe of these correlations through interference between indistinguishable XUV pathways. Shot-resolved covariance measurements reveal the amplitude correlations, while even-harmonics resolve the phase correlations with sub-cycle precision. Time-domain reconstruction of the correlated emission reveals a transition from maximal fluctuations to near-silence within only 30 as. Whereas the signal and idler driven attosecond pulse trains exhibit excess fluctuations individually, their joint reconstruction shows strongly suppressed fluctuations, reflecting their shared correlations. These results establish a framework for generating and probing quantum correlations on attosecond timescales, opening the door to quantum attosecond science.

The weak value of an operator is the average result of measuring that operator on a quantum system given specified initial and final states. The overlap between these states appears in the denominator of the weak value, and thus if that overlap is small, the weak value can be arbitrarily large. In 1988, Albert, Aharonov, and Vaidman proposed a weak Stern-Gerlach experiment which would be able to measure a so-called anomalous weak value, a measurement result which lies out- side of the eigenvalue spectrum of the operator being measured. Though anomalous weak values have been measured in numerous optical systems, here we present the first such realization of this experiment as originally proposed. By placing a Bose-Einstein condensate of 87Rb in a magnetic gradient and performing an unlikely postselection, we measure an effective magnification of a weak magnetic momentum kick (~ 8 $μ$m/s) by a factor of 14. We also demonstrate that increasing the momentum kick decreases the "weakness" of the measurement and reduces the amplification.

Simulating nonlinear dynamics with quantum computers has gained increasing attention. In general, such simulations require additional quantum resources because unitary quantum evolution is linear. A fundamental question is how nonlinear dynamics can be embedded into fully coherent, ancilla-free unitary circuits and how the complexity of the dynamics governs the required quantum resources. In this work, we generalize the ancilla-free double-bracket quantum algorithm for imaginary-time evolution by replacing its state-independent Hamiltonian with a state-dependent Hermitian operator. Our framework recursively calls an initial state preparation oracle and its inverse, and prepares the target solution to any prescribed accuracy using a fully coherent, ancilla-free unitary embedding. We relate the query cost to the complexity of the nonlinear dynamics, specifically their sensitivity to initial conditions. We obtain query upper bounds of $\exp(O(T))$, $\exp(O(T^2))$, and $\exp(\exp(O(T)))$ when the distance between solutions contracts at least exponentially (contractive), does not increase (nonexpansive), or grows at most exponentially (expansive), respectively, where $T$ is the target evolution time. For the discrete Gross--Pitaevskii equation, our ancilla-free double-bracket circuit achieves optimal worst-case query complexity $Θ(e^{gT/2})$ over a specified family of single-qubit initial states, where $g>0$ is the nonlinearity strength. These results connect the complexity of nonlinear dynamics to the query cost of coherent quantum simulation and provide a foundation for designing ancilla-free unitary embeddings with optimal query complexity.

Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments $\operatorname{Tr}(ρ^t)$, allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity $Θ(\sqrt d)$ at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer $t\ge 2$: for any sufficiently small constant additive error, the optimal sample complexity is \[ Θ\!\left(d^{\frac{\lceil\log_2 t\rceil}{1+\lceil\log_2 t\rceil}}\right) \] with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer $h\geq1$, all moment orders $2^{h-1}<t\leq2^h$ share the same exponent. In particular, the third and fourth moments both require $Θ(d^{2/3})$ copies. We also establish an $Ω(d^{1-1/t})$ lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every $t\geq4$. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond $\sqrt d$.

We derive nonlinear Zitterbewegung velocity of electrons augmented by band torsion in crystals. The equation of motion with multistate quantum geometric tensors and torsion culminates in transient nonlinear photocurrent responses distinct from the recently measured resonant steady-state photovoltaic effects induced by circularly polarized light. Tomography protocols for measuring the multistate quantum geometric torsion tensors are proposed.

Arrays of neutral atoms excited to Rydberg levels have emerged as one of the most promising platforms for quantum computation and simulation. With the hope to outperform classical devices, the number of atoms has been increased by orders of magnitude. However, the interaction time, i.e., the maximum accumulated time during which an atom interacts with its neighbours, has been limited to a few microseconds only. This restrains the number of gates per atom or prevents the simulation of long-time dynamics of quantum many-body systems. Here, we observe the spin-exchange interaction between two spin 1/2s encoded in laser-trapped circular Rydberg atoms over more than $60μs$ and 40 spin-oscillation periods, improving the state of the art by an order of magnitude. These unprecedented timescales allow us to record for weak atomic trapping a collapse and revival of the spin-exchange oscillation contrast induced by spin-motion coupling. Our results constitute the first observation of this coupling with laser-trapped Rydberg atoms. To counteract its detrimental effect for quantum simulation, we demonstrate a novel dynamical decoupling method that prevents the collapse of the spin oscillations. This method exploits the advantages of our recently developed hybrid platform that enables the measurement and the optical manipulation of long-lived circular Rydberg atoms with auxiliary Rydberg atoms. This work opens a direct route to long-duration quantum simulation of strongly-interacting many-body systems.

We introduce an exact algebraic architecture that evaluates an arbitrary finite Fourier series using a two-mode ($2 \times 2$) linear optical circuit, with the only tunable components being single-mode phase shifters encoding the function argument. We prove that such a circuit must exist for every Fourier series and derive an analytical method for its construction based on spectral factorisation. The resulting optical system exhibits an $\mathcal{O}(N)$ depth for an $N$-harmonic expansion, executing function evaluations in the passive optical time-of-flight. Finally, we validate our claims numerically, demonstrating that even for sequences with thousands of Fourier terms, our proposed circuit construction correctly synthesises continuous and discontinuous nonlinear functions. Our architecture thus provides a universal, deterministic foundation for single-variable nonlinear optical computing on integrated photonic platforms.

Second-quantized neural-network quantum states have achieved accurate molecular energies, but extending them across molecular geometries requires a shared representation of the geometry-dependent wavefunction coefficients. We introduce geometry-conditioned foundation neural-network quantum states for molecular electronic structure in second quantization. A single autoregressive model learns a family of ground states from sparse anchor geometries and provides wavefunctions at untrained geometries without further optimization. Orbital alignment matches orbital identities and transports their phases, establishing an aligned orbital basis across geometries. Frozen energies reach chemical accuracy at every untrained query geometry for N$_2$, CO, and H$_4$. On additional molecular paths, the energy-trained wavefunctions yield dipoles, quadrupoles, and natural occupations without property labels. Across three paired N$_2$ training seeds, orbital alignment lowers the mean absolute energy error over all untrained query geometries from 34-37 mHa to 0.049-0.085 mHa. At approximately 1 mHa mean absolute error, frozen evaluation reduces the per-geometry cost by $986\times$ relative to independent optimization, yielding an estimated $25.8\times$ end-to-end GPU-cost reduction on a 161-point N$_2$ grid.

Low-space-overhead fault-tolerant quantum computation requires not only high-rate quantum error-correcting codes but also space-efficient implementations of logical operations. Transversal and fold-transversal gates are promising since they limit error propagation and require no additional qubits. However, the logical operations they enable are typically restricted, and a central challenge is to construct codes that combine a complete set of logical Clifford gates with favorable code parameters. In this work, we introduce a family of quantum codes with an asymptotically constant encoding rate and sublogarithmically growing stabilizer weight, while supporting the entire logical Clifford group using only transversal and fold-transversal gates. Our construction is based on classical codes whose code spaces are absolutely irreducible Steinberg modules of their Tanner-graph automorphism groups. Taking hypergraph products of these classical codes yields quantum codes for which all logical Clifford operations can be synthesized from a fixed set of transversal and fold-transversal gates. Moreover, the slow growth of the stabilizer weight enables a high error-correcting performance in small instances. These results provide a path toward fault-tolerant quantum computation with low space overhead using transversal and fold-transversal gates.

A low-noise, high-speed balanced homodyne detector is demonstrated, combining a capacitive-feedback transimpedance amplifier implemented in 28 nm CMOS with a custom photonic integrated circuit fabricated in imec's iSiPP200 silicon photonics platform. The receiver achieves a 3-dB bandwidth of 7.6 GHz, a maximum shot noise clearance of 27 dB, a shot noise-limited bandwidth of 13.7 GHz and a common-mode rejection ratio up to 54.8 dB. These results demonstrate the suitability of CMOS capacitive-feedback transimpedance amplifiers for demanding quantum and coherent sensing optical applications, including continuous-variable quantum key distribution, quantum random number generation, and optical coherence tomography.

We argue that the exponential quantum advantage in Shor's algorithm is broken under one-layer depolarizing noise of arbitrary small error rate, by analyzing a resonance breaking phenomenon in noisy quantum circuits. First, we express the distribution of measurements on $n$-qubit strings as the superposition of the $4^n$ wave functions in the Pauli path integral. In the noiseless case, the bit-strings achieving resonant peaks guaranteed a constant rate of successful measurements to factor a large number. Secondly, when the middle layer of the quantum circuit has independent depolarizing noise of rate $λ$, for any Hamming weight $d$, we obtain corresponding measurement rate bounded by $2(1-λ)^d$ for higher frequency terms and by $O(n^d)/2^{n/2}$ for low frequency terms. The rate approaches to zero as $n$ and $d$ approaches to infinity. Resonance breaking destroys the exponential quantum advantage. Furthermore, we design a classical factoring algorithm in polynomial time $O(n^d)$ to substitute the low frequency contribution.

Accurate decoding of quantum low-density parity-check (qLDPC) codes often relies on expensive post-processing search, although decoding difficulty varies strongly between syndromes. We find that the benefit of deeper post-processing search is highly concentrated in a small subset of decoding instances, and that these instances can be identified directly from the decoder itself. To this end, we introduce an adaptive decoder based on belief propagation (BP) and ordered-statistics decoding (OSD), using the disagreement between the BP hard decision and the syndrome-consistent order-zero OSD solution as an internal risk signal to determine where deeper search is required. On a $[[144,12,12]]$ bivariate bicycle code under circuit-level depolarising noise, encoding $12$ logical qubits in $144$ data qubits with distance $12$, escalating only the highest-risk $20\%$ of instances recovers $85\%$ to $92\%$ of the improvement in logical error rate available from a full one-free-variable sweep, while reducing the mean serial decoding cost by a factor of $3.6$ relative to applying the same truncated search to every instance. At matched budget, disagreement-guided routing also outperforms routing based on the BP syndrome residual, syndrome weight and random selection. The same behaviour reappears on a structurally distinct radial qLDPC code obtained from a lifted-product construction, where escalating $20\%$ of instances recovers $87\%$ to $94\%$ of the available gain. A $Z$-memory experiment on the Quantinuum H2 trapped-ion processor, implementing both $X$-type and $Z$-type checks, further shows that the signal remains predictive under device noise. These results show that decoder-internal disagreement can expose where additional decoding effort is valuable, allowing classical computation to be concentrated on the instances most likely to benefit from it.

We use the analogy between the quadrature operators in quantum optics and the phase-space coordinates in a mechanical harmonic oscillator to generalise the theory of linear optics beyond quantum theory. For this, we introduce a framework for analysing photonic circuits within generalised probabilistic theories based on quadrature operators. Using this framework, we ask whether phenomena like the Hong-Ou-Mandel effect, Mach-Zehnder interferometry are specific to quantum theory or also occur across a broader class of theories. We find the latter: the vanishing photon coincidences at the output of a beam splitter also occur for classical light and for a modified version of quantised light. Similarly, for Mach-Zehnder interferometry we find that there is no qualitative difference between quantum theory and these alternative theories. Our framework can serve as a foundation to study generalised theories of complex photonic set-ups and photonic quantum computers.

Multiphoton indistinguishability is a key resource for photonic quantum technologies, yet its characterization typically relies on resource-intensive methods. In this work, we develop two efficient and experimentally friendly protocols to estimate or bound the fidelity $F_{\mathrm{ind}}$ of an $N$-photon state to the closest perfectly indistinguishable state. The first protocol applies to sources preparing separable states, uses a single Fourier interferometer together with photon-number-resolving detection, and yields tight two-sided bounds on $F_{\mathrm{ind}}$. The second protocol combines randomized implementations of linear-optical interferometers with photon counting, enabling direct estimation of $F_{\mathrm{ind}}$ for arbitrary $N$-photon states. Both protocols can certify $F_{\mathrm{ind}} = 1 - \mathcal{O}(ε)$ using provably optimal $\mathcal{O}(1/ε)$ samples, in contrast to previous approaches which required prior assumptions on the model of partial distinguishability. Our methods, based on a multiphoton generalization of the Hong-Ou-Mandel test, bring the rigorous and operationally meaningful certification of multiphoton indistinguishability within reach of current photonic technologies.

The ratio $T_2$/$T_2^*$ of the Hahn-echo and Ramsey times of nitrogen-vacancy (NV$^-$) ensembles is independent of the nitrogen concentration [N] and is $\approx$ 16 in diamond of natural isotopic abundance ($^{14}$N), yet a recent $^{15}$N-doped ensemble magnetometer gives only 8.05 $\pm$ 0.18 in the single-quantum convention. We ask whether the nitrogen nuclear isotope alone can cause such a reduction. Using a semiclassical spin-bath model with the Jahn-Teller-resolved P1 hyperfine tensor, we show that the fraction of P1 pairs that are hyperfine-degenerate, and hence free to flip-flop, is 1/4 for $^{14}$N (I = 1) but 5/16 for $^{15}$N (I = 1/2). Simulations over [N] = 0.1--100 ppm confirm that this shortens $T_2$ while leaving $T_2^*$ exactly unchanged: $T_2$($^{14}$N)/$T_2$($^{15}$N) = 1.118 $\pm$ 0.011, independent of [N] and 11$σ$ above unity. The measured contrast, 2.07 $\pm$ 0.25, is 3.8$σ$ larger, identifying resonant-channel counting as a real but partial contribution and setting a quantitative benchmark for many-body calculations.

We propose a quantum heat engine based on a two-component Fermi gas with s-wave contact interaction, operating across the BCS-BEC crossover. The work is extracted from the statistical properties of the gas, which are controlled by the interaction, rather than relying solely on compression and expansion stages. Using the functional renormalization group formalism, we obtain the equation of state in a non-perturbative form along the crossover, encompassing the superfluid-normal phase transition. The cycle combines isentropic density strokes, isochoric thermalization, and isothermal interaction sweeps. This construction makes it possible to integrate features of both Otto and Carnot cycles, in which the system simultaneously saturates both efficiency limits without the net work vanishing. In the absence of density variations, the cycle reduces to a statistical Stirling-like engine, in which the work generated arises exclusively from the interaction, achieving efficiencies up to $38\%$. A pronounced asymmetry emerges through the crossover, giving rise to distinct operating regimes depending on the trajectory followed in the phase diagram. Consequently, the same architecture can be tuned to function as an engine, refrigerator, accelerator, or heater. These findings highlight pairing correlations as a versatile thermodynamic resource for quantum heat machines.

Quantum state preparation is crucial for quantum algorithms, and improved state preparation methods can reduce resource requirements by orders of magnitude. In this work, we introduce a state preparation method for lattice Hamiltonians on digital quantum computers inspired by nucleation. In our method, the exact ground state of a small lattice Hamiltonian is prepared in a quantum circuit, then a series of growth stages are performed via Trotterized adiabatic evolution to increase the size of the lattice to the desired model. Using the adiabatic theorem and Trotter error bounds, we provide sufficient conditions on the total evolution time and number of Trotter steps required for nucleation to prepare an initial state with desired fidelity. In addition, we introduce optimized nucleation which considers variational optimization on top of the nucleation structure. For a two-dimensional Ising model, we show that optimized nucleation can outperform a current leading method for state preparation on digital quantum computers.

In periodically driven open quantum systems, nonnormality renders the Floquet spectrum insufficient as the system approaches the thermodynamic limit, so that pseudospectra are needed to characterize the dynamics accurately. While conventional approaches mainly focus on the local dynamics of isolated pseudospectra, their global connections and the resulting physical consequences for observables have remained largely unexplored. Here, we uncover this collective behavior by classifying the unit disk into distinct domains of exponential, algebraic, and bounded accuracy according to the asymptotic size-scaling laws of pseudospectral residuals, yielding an underlying geometric structure. We demonstrate the physical implications of this structure through two exactly solvable models. First, in a dissipative shift chain, parameter tuning drives geometric transitions that are detectable via spin-wave observables. Second, in a chiral XY model, we use this geometric structure to explain the origin of a measurable phenomenon: two correlation signals exchange their retention order under continuous parameter tuning. Our findings not only establish a new theoretical paradigm for understanding dissipative Floquet quantum systems, but also predict geometry-driven observables for quantum computing experiments.

Spontaneous parametric down-conversion is a primary resource for generating non-classical light, yet phase mismatch fluctuations from temperature drift, angular misalignment, and domain fabrication errors reduce pair-generation efficiency and phase stability. Here, we analyze error mitigation in spontaneous parametric down-conversion using composite segmentation governed by SU(1, 1) spatial dynamics. We show that odd spatial Fourier harmonics preserve error-cancellation flatness with pair-generation rates scaling asymptotically as $m^{-2}$, while a coordinate-dilation symmetry provides a design prescription for translating configurations across distinct operating wavelengths (405, 532, and 775 nm). Furthermore, an open-loop thermo-optic bias counteracts off-axis angular drift to broaden the 90%-efficiency angular acceptance half-width by 3.46x, and up to two missing poling domains are tolerated with no numerically resolved loss in relative conversion efficiency. Across a 5$^\circ$C thermal window, the generated pairs sustain a relative conversion efficiency of $η\ge 0.954$ with the modeled phase-coherence metric remaining above 0.95, providing a structurally robust approach for entangled photon generation without requiring continuous closed-loop feedback stabilization.

We study spin-current fluctuations of the folded XXZ chain, which describes the strong-anisotropy limit of the XXZ chain. We obtain an exact expression for the moment-generating function of the time-integrated spin current at infinite temperature. A long-time asymptotic analysis establishes that the rescaled time-integrated current converges to a non-Gaussian distribution described by the M-Wright function. The derivation relies on a nonlocal map to the one-dimensional t-0 model and its exact spin-charge separation. By extending this approach, we also show that the dynamical correlation function of the spins summed over two adjacent sites exhibits a diffusive Gaussian profile at long times.

Certifying Bell correlations in increasingly larger multipartite quantum systems is challenging because conventional Bell inequalities rely on many-body correlations, which become experimentally demanding to estimate as system size grows. Here we demonstrate that multipartite Bell correlations can be certified using few-body permutation-invariant (PI) correlations with a fixed maximal correlation order. We experimentally test few-body PI Bell correlation witnesses tailored for six- and eight-photon postselected Dicke states. The addition of a few four-body correlators is found to significantly enhance the noise tolerance compared with previously studied two-body witnesses: for instance, for six qubits, the selected witness tolerates a white-noise fraction of $p_c\approx0.301$, compared with $p_c\approx0.048$ for the best two-body PI inequality with the same two settings per party. For six and eight photons respectively, we observe violations of the witness bounds by $32$ and $8.9$ standard deviations, arising from postselected polarisation states with fidelities of $0.933(4)$ and $0.916(11)$ to the corresponding half-excitation Dicke states. The witnesses for the six- and eight-photon cases use the same symmetric two- and four-body correlators, just with different coefficients. These results demonstrate an experimentally accessible approach for certifying multipartite Bell correlations in larger systems without requiring full-body correlation measurements.

Succinct arguments are a fundamental cryptographic primitive for verifying computational claims with small communication. In the classical setting, succinct arguments for NP can be constructed from unstructured hardness alone (e.g., hash functions) by compiling probabilistically checkable proofs (PCPs) or interactive oracle proofs (IOPs) for NP via the commit-and-open paradigm. In contrast, known succinct arguments for QMA rely on ``structured'' cryptographic primitives, or on the quantum PCP conjecture. We construct the first succinct argument for QMA in the quantum random oracle model (QROM) without relying on additional cryptographic assumptions or unproven conjectures. This yields succinct arguments for QMA from unstructured hardness alone, showing that ideal hash functions not only suffice for succinct arguments for NP but also for QMA. Underlying our result is an efficiency-preserving transformation that compiles quantum interactive oracle proofs (QIOPs), a recently introduced interactive generalization of quantum PCPs, into quantum arguments for the same language, via a natural quantum commit-and-open paradigm. Our transformation applies to every QIOP with public-query soundness, a notion that we formalize to capture a natural requirement of the commit-and-open paradigm and is satisfied by a known QIOP for QMA. As a key ingredient in our transformation, we formalize and construct extractable vector commitments for quantum states with local openings in the QROM, which may be of independent interest.

The consistent histories formulation of quantum mechanics assigns classical probabilities to sequences of coarse-grained events when the corresponding interference terms vanish. In finite models these terms generically need not vanish exactly, and their smallness alone supplies no asymptotic geometry on the space of histories. We construct such a geometry for histories that accumulate quantum records. When the normalized Dowker - Halliwell interference between two histories factorizes as the cumulative fidelity of their records, its decay is controlled by the accumulated squared Bures distance. In the infinite registration limit, the Kakutani - von Neumann dichotomy gives a sharp sector alternative: summable Bures defect yields weakly equivalent record sequences, whereas nonsummable defect produces orthogonal superselection sectors and vanishing normalized interference. The convergence exponent of the Bures defect defines a pseudo-ultrametric on histories. After quotienting its zero distance degeneracy, it becomes a complete ultrametric, requiring neither compactness of the outcome space nor continuity of the record family, and coincides with the gauge invariant sector metric $\tilde d$ introduced in \cite{LesTP}. Its value, the \emph{consistency rate}, has three equivalent interpretations: it is the sector separation metric, the polynomial growth exponent of the negative logarithm of normalized interference, and, by the Helstrom formula, the corresponding exponent of the negative logarithm of the minimum error probability for discriminating the cumulative records. Classical separation profiles determine the rate: positive long time mean defect gives the maximal value $δ=1$, while the borderline profile $d_m^2\asymp m^{-1}$ produces distinct superselection sectors at zero polynomial rate, $δ=0$.

A phase that reaches a fault-tolerant processor in additive pieces can be remembered until the last piece arrives, or executed on arrival: the first option costs classical memory carried across rounds, the second costs magic states committed before the phase is known. We determine the exchange rate $α$, committed $T$ gates per bit of memory forgone, for ancilla-free coordinatewise Clifford+$T$ compilation. The Ramanujan bound for the Clifford+$T$ lattice gives $α\ge2$ with explicit constants, the square-root barrier of the spectral method. An elementary determinant method, using that quaternion numerators are lattice points on spheres in both real embeddings of $\mathbb{Q}(\sqrt2)$, counts words near an arbitrary rotation coset below that barrier and gives $α\ge11/5$ asymptotically and unconditionally, and a height dichotomy for the resulting sphere sections raises this to $α\ge17/7$. At Clifford-framed cosets the volume law holds up to subexponential factors: all but a vanishing fraction of $z$-rotations need $T$-count $(3-o(1))\log_2(1/\varepsilon)$, and processes whose committed pieces are close to Clifford-framed $z$-rotations, including per-rotation pipelines, have $α\ge3-o(1)$, which a fractional-passthrough family attains under the Ross-Selinger typical-cost hypothesis. Under an equidistribution conjecture supported by exhaustive enumeration to $T$-count 22, $α=3$ in general and memory should be shed in whole rotations. The bounds hold even when the phases cancel to the identity; side information enters through a conditional entropy; probabilistic mixing halves the costs but not the rate. With clean ancillas and a phase-gradient catalyst, table lookups batched across coordinates drive the rate to $O(1/\log\log(1/\varepsilon))$, so the constant-rate law is specific to coordinatewise synthesis.

We outline a complete set of operations for manipulating nuclear spin qubits of trapped-ions stored in high magnetic fields such as required for Penning trapping, where the nuclear and electron spins are largely decoupled due to the dominance of the external field Hamiltonian. The reduced nuclear magnetic moment results in insensitivity to external magnetic fields compared to the use of an electron spin, but also makes the nuclear spin hard to manipulate on fast timescales. To maintain speed, we propose a two-qubit phase gate technique which utilizes the electron spin, but for which the qubit remains protected from magnetic fields through retaining the nuclear encoding. This method works for magnetic-field insensitive qubits at lower fields as well as for both microwave and laser field gradients.

Programmable exchange interactions support quantum gates and many-body simulation in superconducting circuits. Fast excitation transfer, however, opens two leakage pathways in weakly anharmonic transmons, degrading gates and driving simulated dynamics outside the encoded state space. We introduce parametric derivative removal by adiabatic gate (PDRAG) to suppress both pathways while preserving the target exchange. Their conjugate structure determines first- and second-derivative corrections implemented through one real frequency command. At $g/2π=100$ MHz, calibrated PDRAG achieves a geometric-mean leakage reduction of $5.27\times10^5$ relative to the base pulse across 12.5--35 ns in Duffing simulations. At 13 ns, endpoint leakage reaches $1.98\times10^{-7}$ for the calibrated full-exchange pulse. Transferring the derivative coefficients to a charge Hamiltonian gives a mean 893-fold reduction over 12.5--22 ns after amplitude and carrier recalibration. Floquet return interference and charge-induced gap shifts explain the calibration and transfer gains, connecting compact pulse design to leakage-suppressed programmable interactions.

Quantum infrared (IR) spectroscopy is a novel technique based on nonlinear interferometry and quantum sensing with undetected photons. In this approach, spectrally far-separated correlated photon pairs are used for detection and probing, respectively. Hence, the probing wavelength domain (mid-IR) is substantially different from the detection spectral range (near-IR), which enables shot-noise-limited and cost-effective sensing schemes attractive for applied metrology. In this paper, we implement and employ a custom-built scanless quantum Fourier-transform mid-IR (sQFTIR) microspectrometer for chemical characterization and analysis of solids and interfaces. The sQFTIR system employs spectral-domain acquisition, without the need to scan the optical delay. This results in enhanced sensitivity and short measurement times and therefore enables rapid spectral acquisitions in 100~ms spanning a spectral band from 3000 cm$^{-1}$ - 2400 cm$^{-1}$. The capabilities of our approach are demonstrated for hyperspectral mid-IR imaging of dried pharmaceuticals (insulin on a gold surface) and investigation of a security feature on a banknote. Furthermore, we demonstrate hyperspectral imaging and spectroscopy through a turbid ceramic medium.

Lattice gauge theories are an important class of physical models with high-dimensional structured distributions that underpin first-principles calculations in particle, nuclear, and condensed-matter physics. Recent advances in generative modeling have opened new avenues for sampling Boltzmann distributions in lattice gauge theories, offering the potential to alleviate limitations of traditional Monte Carlo methods, including critical slowing down and topological freezing. However, generative samplers for lattice gauge theories are typically constructed in link space, where correlations become increasingly long-ranged toward weak coupling, posing a challenge for learning. Plaquettes provide a more natural representation, as the action is local in these variables. However, exact Bianchi constraints restrict them to a lower-dimensional manifold, complicating direct generative modeling. We introduce a multilevel normalizing-flow construction that samples directly in plaquette space while satisfying these constraints exactly. The key idea is a coarse-to fine factorization that transforms a globally coupled constraint problem into a sequence of local solves: at each refinement, every determined plaquette depends on at most four newly generated variables, while the size of the constraint problem remains independent of the lattice size. We validate the construction for $U(1)$ in two and four dimensions and for $SU(2)$ in two dimensions. Our multilevel Plaquette-Space Sampler (PSS) substantially outperforms link-space baselines, with the advantage increasing toward weak coupling, where the gauge coupling becomes small. This regime is particularly challenging for generative sampling and, in asymptotically free gauge theories, is relevant to continuum studies.

Vanadium color centers in silicon carbide (SiC) offer telecom O-band emission, sub-microsecond optical lifetimes, and second-scale spin relaxation times, rendering them promising candidates for quantum network nodes. However, efficient photon extraction from the high-refractive-index SiC host remains challenging. Here, we introduce a silicon-on-SiC heterogeneous photonic platform in which silicon nanocavities evanescently couple to shallow vanadium dopants in commercial 4H-SiC, enabling efficient zero-phonon line (ZPL) collection under resonant excitation. In as-grown ensembles, we observe Purcell-enhanced photoluminescence with transient spectral hole burning linewidths of 50 MHz on microsecond timescales. In dilute implanted samples, we isolate individual vanadium centers with high-purity single photon emission and a Purcell-enhanced lifetime of 109 ns. The entire optical interface operates through a single lensed fiber, including a 905 nm repump laser that recovers the vanadium charge state with 95% efficiency. These results establish Si-on-SiC as a scalable, foundry-compatible platform for telecom-wavelength spin-photon interfaces.

We propose a unified perspective on classical and quantum chaos based on the sensitivity of a system's stationary states to slow driving. We probe this sensitivity via the system's susceptibility to the average protocol speed, which we call the ``speed-Fisher information," and relate it to irreversible entropy production in the system. We show that chaotic dynamics manifests as a divergence of the speed-Fisher information with the protocol time, and that this response is controlled by the perturbation's low-frequency spectral weight. This approach to chaos applies to both classical and quantum Hamiltonian systems, and naturally extends to non-Hamiltonian classical flows. Additionally, we identify a quantum regime at times shorter than the Planckian timescale, in which the speed-Fisher information exhibits a uniquely quantum scaling. We illustrate this framework with simple classical and quantum examples

We determine the optimal query complexity of ground-state preparation to trace-distance error $\varepsilon$ when an energy threshold in the spectral gap is known. Let $U_H$ be an $α$-block-encoding of a Hamiltonian with unique ground state $|ψ_0\rangle$, and suppose $|\langleψ_0|U_I|0\rangle|\geγ$ for a state-preparation oracle $U_I$. The threshold lies at least $Δ/2$ above the ground-state energy and at least $Δ/2$ below every excited-state energy. We give two algorithms that prepare a state within trace distance $\varepsilon$ of the ground state. One uses $O((α/Δ)(γ^{-1}+\log(1/\varepsilon)))$ calls to $U_H$ in expectation; the other uses $O((α/(γΔ))\log(1/\varepsilon))$ calls to $U_H$ in the worst case. We prove a lower bound matching the expected query count; the corresponding worst-case lower bound follows from Somma and de Wolf [SdW26]. The respective bounds on calls to $U_I$ are $O(1/γ)$ in expectation and $O(γ^{-1}\log(1/\varepsilon))$ in the worst case. On $(N+1)$-dimensional systems, these $U_I$ bounds are also optimal when the expected or worst-case count of $U_H$ calls, respectively, is $o((α/Δ)\sqrt N)$. Both algorithms use a constant-accuracy spectral filter to construct a purifier, which we then sequentially compose during amplitude amplification to prepare a state with constant overlap with the ground state. The expected-query algorithm repeats the preparation followed by one high-accuracy spectral filter until success. The worst-case algorithm uses filters of increasing accuracy and limits the total number of queries.

In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $κ$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $ε$-approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$, while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$. We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.

In the quest to identify further quantum algorithms exhibiting superpolynomial speed-ups, a recurring theme is that the complexity of a problem is largely shaped by the input access model. Here, we study this phenomenon for the state hidden subgroup problem (StateHSP), a quantum generalization of the hidden subgroup problem in which the goal is to identify the symmetries of an unknown quantum state. For finite abelian groups, existing Fourier-sampling algorithms use $O(\log(|G|)/ε)$ copies of the state, but whether this scaling is optimal has remained open. We settle the complexity of the abelian StateHSP in both the previously studied sample model and a new query model, which is a stronger and operationally natural generalization that provides access to the state-preparation unitary and its inverse. In the query model, we give a time-efficient quantum algorithm using $O(\log(|G/H|)/\sqrtε)$ forward and inverse queries, and prove a matching $Ω(\log(|G/H|)/\sqrtε)$ lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, $Θ(\log(|G/H|)/ε)$ copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in $ε$ genuinely arises from coherent access to the preparation circuit. As applications, we obtain faster algorithms for learning stabilizer groups, locating unentanglement, and identifying hidden translation symmetries.

We study a quantum battery consisting of $N$ qubits interacting uniformly with each other. Starting from its ground state, the battery is charged by introducing periodic kicks in the transverse direction along with adding disorder in the interaction direction. Although the battery Hamiltonian along with the initial state preserves the permutation symmetry, the dynamics in presence of disorder during the charging phase takes the system out of the permutation symmetric subspace, resulting to a larger amount of stored energy as compared to that without disorder. In the limit of large disorder, this interplay brings in a possibility of a chaotic charging phase when stored energy can be exactly calculated using random matrix theory. More importantly, we also find that the energy fluctuations decrease and become negligible in the limit of large disorder, which is also when the energy stored is maximum, a condition highly desirable for the optimum functioning of the battery. We complete the battery cycle by considering the storage phase in the presence of dephasing noise. We find that for larger disorder strengths, the ergotropy remains close to the stored energy, indicating nearly complete energy extractability with an efficiency approaching unity.

We study the problem of learning a sparse quantum state, an $n$-qubit quantum state whose density matrix has at most $s$ nonzero matrix entries in an unknown product basis. While such states admit compact classical descriptions, they can carry long-range entanglement that prevents reconstruction from local reduced density matrices alone. Therefore, previous learning approaches addressed such long-range-entangled states using many entangling gates to extract the necessary information. In this work, we show that sparse states can nevertheless be efficiently learned using only single-qubit measurements. Specifically, when the sparsity $s$ is constant, our algorithm can learn sparse states from single-qubit measurements with polynomial sample complexity and classical computational complexity. When $s$ grows polynomially with $n$, sparse states can still be learned from single-qubit measurements with polynomial sample complexity, although efficient classical computation is not guaranteed in general. In this regime, however, the classical computational complexity becomes quasipolynomial when the state is sparse in an unknown basis that is a product of a known fixed finite set of single-qubit bases (e.g., eigenbases of Pauli operators). These results establish efficient learning of sparse states with long-range entanglement without entangling gates, and the single-qubit measurement requirements make our algorithms compatible with current quantum devices.

In materials machine learning, closely related retained structures can sustain accurate property predictions even after removing a specific record, rendering post-deletion prediction error an ambiguous metric for machine unlearning. To resolve this ambiguity, we define the deletion floor as the expected target loss under a specified retraining procedure at the deleted request. Standard indistinguishability constraints yield a sharp interval bounding an update's target loss around this baseline reference. Theoretically, a conditional neighbor bound links a low deletion floor directly to retained fit, prediction regularity, and local label agreement, while an exact ridge identity isolates residual fit from the prediction change induced by record deletion. Empirically, controlled redundancy sweeps show an $\approx 8\times$ drop in median normalized retraining loss when one retained relative remains after deletion. Across two distinct fitting regimes in a paired Materials Project study, the lower-floor regime also exhibits a larger prediction change on more than 50% of the shared requests. Systematic comparisons against approximate updates and the original model decouple deliberate target suppression from preserved overall model utility. Consequently, request-level unlearning evaluations should report reference loss, prediction change, and retained utility together, interpreting post-deletion accuracy against what retraining itself leaves behind.

We prove the existence of succinct arguments for QMA, assuming only the existence of collapsing hash functions. This is the first scheme that relies only on unstructured ``Minicrypt'' assumptions, which are not known to imply public-key encryption. Our main technical contribution is a quantum-succinct \emph{claw-state generation} protocol that allows us to bootstrap a small number of quantum correlations into an arbitrarily large number of claw-state correlations, using classical communication only. This improves upon the work of [Zhang, STOC 2021], having better round complexity, a proof in the standard model, and being overall much simpler. This yields a quantum-succinct blind delegation of quantum computation protocol from one-way functions, which we plug into the communication-compression compiler of [Bartusek, Liu, and Malavolta, EUROCRYPT 2026] to obtain succinct arguments for QMA.

Superconducting films native to a commercial CMOS process enable co-integration of superconducting devices (high-kinetic-inductance elements and nanowire detectors) with cryogenic CMOS on one monolithic die. Such films are buried in the front-end-of-line, beneath the back-end-of-line metal stack, an environment that might quench a self-heated hot spot. Current-voltage characteristics are reported for titanium nitride (TiN) nanowires in the polycrystalline-silicon resistor layer of a 22 nm FD-SOI process, and measured retrapping currents are compared with thermal models for longitudinal conduction to the contacts and interfacial phonon cooling into the stack. The wires are strongly hysteretic, with switching-to-retrapping current ratios I_sw/I_r of 7.4-9.8, sustaining a normal hot spot. For two wires of length ell = 50 micrometers and widths W = 0.50 and 1.00 micrometers, over bath temperatures T_b = 0.15-1.19 K, I_r follows the interfacial form (T_hs^n - T_b^n)^(1/2) with n = 4 (T_hs, the effective hot-spot temperature), and is strongly inconsistent with the (T_hs - T_b)^(1/2) constant-kappa longitudinal-conduction limit; free-exponent fits give n = approximately 4.8-5.0. An effective cooling coefficient Sigma_K = 7.9(3) W/(m^2 K^4) describes the data: 31(21) times below the acoustic- (diffuse-) mismatch value for a single clean interface, and approximately 12 times below the lowest previously reported comparable nanowire coefficient. The model-based film thermal conductivity is kappa = approximately 20 mW/(m K). Across lengths ell = 1-50 micrometers, I_r matches neither ell^(-1) of pure longitudinal conduction nor ell^0 of pure interfacial cooling; a two-channel model reproduces I_r(ell) with crossover length ell* = approximately 3.5 micrometers predicted, to an O(1) prefactor, from Sigma_K and kappa.

We construct complete canonical logical bases for qubit CSS codes by assigning quaternary coefficients to binary circulant permutation matrix pair-partition (CPM-PP) checks, constructing and normalizing logical representatives, and expanding the result into binary matrices. When the two check systems have invertible submatrices on disjoint column sets, cofactor representatives are canonically paired by the inverse of a single pairing polynomial. The resulting pairs span the entire logical space. When the pairing polynomial is a cyclic-shift monomial with coefficient one, normalization preserves the binary weights of the representatives. We state the construction for general block dimensions and CPM size, work through a corresponding example, and report the parameters, check ranks, and basis weights of seven binary codes. Representative examples have parameters $[[320,80,14]]$, $[[448,112,18]]$, and $[[2048,512,24]]$. All three have maximum check weight 10 on both the X and Z sides. Their canonical logical representatives have binary weights 25, 27, and 27, respectively, on both the X and Z sides.

Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary $U_{AB}$ by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary $U_{AB}$ whose implementation in NLQC requires extra quantum systems with dimensions ${\rm exp}(n^{Ω(1)})$, where $n$ is the dimension of systems $A$ and $B$. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in $n$. In this paper we consider the family of diagonal ${\pm 1}$ valued unitaries $U_{\varepsilon}$, indexed by an element of the Boolean hypercube $\varepsilon \in \{\pm 1\}^{n^2}$, i.e. $U_{\varepsilon}|i\rangle_A|j\rangle_B =\varepsilon_{ij} |i\rangle_A|j\rangle_B$. We show that if $U_{\varepsilon}$ can be implemented in NLQC with constant accuracy for all $\varepsilon$, and the dependency on $\varepsilon$ in the first round of the associated strategy is a polynomial of degree $O(n^{\frac{1}{4}-δ})$, then the implementation of at least one $U_{\varepsilon}$ in NLQC requires resources scaling as $\exp\left(Ω\left(\frac{n^{2δ}}{(\log n)^2}\right)\right)$. The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.

We introduce QC-Stark, a benchmark for evaluating large language models (LLMs) on 11 quantum computing (QC) tasks, spanning circuit construction, debugging, compilation, error correction, and simulation. Across 2,750 evaluations (10 models $\times$ 11 tasks x 5 difficulty levels x 5 seeds), we find that overall rankings mask substantial per-task variation. The Spearman correlation between overall and per-task rankings is statistically insignificant for 4 out of the 11 tasks included in this benchmark. A 2-parameter Item Response Theory (IRT) model validates measurement quality, and prompt sensitivity analysis confirms ranking robustness across prompt conditions. All tasks are auto-verifiable via execution, thus not requiring any manual evaluation. We make the code and data publicly available on Huggingface.

Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity. $(2)$ We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00]. $(3)$ We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups. Our main technical ingredients include a near-tight quantum algorithm for $\varepsilon$-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22]. Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.

We present a protocol that estimates the quantum fidelity, up to precision $\varepsilon$, between a known target state and unknown lab-prepared state with sublinear, $o(d^{0.9908}/\varepsilon^2)$, number of Pauli basis measurements.

This paper continues our analysis of NISQ experiments and especially the Google 2019 ``quantum supremacy" experiment. In arXiv:2008.05177 we proposed statistical tools to analyze symmetric and asymmetric readout errors, and the symmetric case was extensively developed and studied in arXiv:2404.00935, where we used Fourier methods combined with statistical tools. Here we extend and complement our earlier study and analyze asymmetric readout errors for data from experiments and simulations. Our study was further motivated by a paper by Fefferman et al. arXiv:2306.16659, who showed that the effect of amplitude damping gate errors is to have larger fractions of zeroes in the samples produced by the quantum computer. We show that this effect of gate errors is not observed in the Google experimental data, where, for the entire range of the number of qubits, $12 \le n \le 53$, the fraction of zeroes and ones reflects only the asymmetry of reported readout errors, and report on simulations with $n=12,14$ using IBM's and Google's simulators.

The wave-particle duality that manifests in the Young's double-slit interferometry satisfying the well known Englert-Greenberger-Yasin inequality has recently been shown to obey a universal triality relation involving coherence, predictability and rather surprisingly entanglement. In the present work, we explicitly demonstrate the persistence of the triality relation in the quantum induced coherence interferometer and the classical configuration recovers the well known duality inequality. Furthermore, we explore the origin of coherence and entanglement, in the induced coherence interferometer, and means to control them. We show that path indistinguishability (or intrinsic indistinguishability of the sources) in our setup plays a complementary role in influencing both interference and entanglement. We bring out manifestly the nature of coherence in both classical and quantum versions of induced coherence interferometers.

We give a quantum algorithm for stochastic $2$-player games. Their game trees are the expectiminimax trees of classical game search: $m$ adversarial layers alternate with $m$ chance layers, every node has $deg$ children, and the leaf values lie in an interval of length $N$. The algorithm estimates the value of the game to root mean square error $ε$ with \[ O\!\left( K^{D}\, deg^{\frac{D}{4}} \, \frac{N}ε \, D^{4D} \log\left( \frac{deg N}ε \right)^{4D} \right), \qquad D = 2m \] queries to the leaf values, where $K$ is an absolute constant. If we treat the depth $D$ as a constant as is sometimes done in the literature, the bound is $\widetilde O(deg^{m/2}ε^{-1})$ against the classical $\widetilde O(deg^{m}ε^{-2})$. So the quadratic speedup in the branching factor known for adversarial trees and the quadratic speedup in the accuracy known for a single expectation both survive when we nest one inside the other. We use a derandomised multilevel Monte Carlo estimator for chance layers and a coherent binary search for adversarial layers. The composition is done by introducing a conversion between root-mean-square and uniform error guarantees, and a composition to nest it with quantum mean estimation. We state the algorithm for stochastic games, but it is valid for the following conditions: the value of a parent is a Lipschitz function of the values of its children and the value at a chance vertex is linear in its children, however the speedup is preserved only if the deterministic step has a quantum subroutine with sublinear query complexity.

The coherence of free electrons sets fundamental limits on the resolution and contrast of phase-sensitive electron microscopy because coherence is lost whenever the electron leaves a distinguishing excitation in its environment. We develop a quantitative theory of fast-electron decoherence in two canonical geometries: a cylindrical hole drilled through a realistic metal and a circular aperture in a thin perfectly conducting film. By combining an electromagnetic Green-tensor formulation with the fluctuation--dissipation theorem while fully retaining retardation, we obtain the decoherence probability and elastic phase as functions of the electron trajectory, temperature, and material response. For the cylindrical hole, we obtain a closed-form, azimuthally resolved expression that separates the dependences on path position, temperature, and conductivity. In the high-conductivity and high-temperature limits, this result reduces to a universal expression that is linear in temperature and independent of both conductivity and electron velocity. For the circular aperture, which we solve using a cylindrical-wave modal expansion, the energy-loss probability diverges as $1/ω$ at low frequency, whereas the decoherence probability remains finite and reaches a maximum when the aperture radius is comparable to the relevant electromagnetic wavelength. Because the interaction is spatially localized, aperture-induced decoherence is generally weaker than that produced by a cylindrical hole, except for sufficiently large apertures at high temperature. Finally, we show that, for sufficiently large holes, decoherence can dominate the spatial broadening of a focused electron probe and must therefore be incorporated into the design of coherent electron-beam instruments.

The output of a parameterized quantum circuit (PQC) can be expressed as a finite Fourier series whose accessible frequencies are fixed by the data-encoding gates. While the encoder determines which frequencies can appear, the corresponding Fourier coefficients depend on how the trainable and entangling gates are arranged. Although existing studies provide metrics for characterizing how gate structure affects Fourier coefficients, they do not translate these analyses into an explicit design criterion specifying how gates should be arranged to make a target coefficient reachable. In this paper, we provide such a criterion. Using the adjoint action of the encoding generator, we decompose operator space into two-dimensional invariant planes indexed by frequency and show that each Fourier coefficient is exactly a sum of bilinear projections of the effective state and observable onto the planes at that frequency. Because, for Pauli encodings, high-frequency planes are spanned by mixed multi-qubit Pauli strings, a target coefficient can contribute to the output only when local rotations and entangling layers are arranged so that both the effective state and observable acquire support on one of its planes. For Pauli readouts and commuting two-qubit entanglers, this yields a circuit design rule that specifies, for a given interaction graph, a placement of local rotations and entangling layers that makes a target Fourier coefficient reachable. Using a single encoding layer, we validate the proposed design through a placement ablation, regression tasks from PDEBench and physics-informed Maxwell field modeling, and further demonstrate its robustness to moderate simulated gate noise and damping.

High-dimensional time-bin entanglement is known for having high potential for quantum key distribution (QKD) applications, being easily implementable, robust and may offer better keyrates than simple qubit protocols. The temporal encoding, combined with limited clock resolution, however, implies a trade-off: Is it better to send more low-dimensionally encoded photons or few high-dimensional ones? Answering this question presents a hard challenge as it depends on the entire context of the protocol, including the production rates, losses, dark counts, timing jitters and many more. We answer this question for single Franson based interferometers and asymptotic key rate and shared entanglement as main figures of merit. We present a flexible noise model incorporating all relevant parameters and find that there are indeed regions where high-dimensional encoding still outperforms any qubit based version when the pair arrival rate is limited, for instance through loss or limited pump power.

The hierarchical equations of motion (HEOM) approach is one of the most powerful methods avail- able to simulate the dynamics of open quantum systems. Although the HEOM approach has been shown to be stable and efficient in many parameter regimes and physical scenarios, it is also well known that the unavoidable finite truncation of the hierarchy can lead to fundamental numeri- cal instabilities for bosonic environments. In this work, we apply recently developed techniques to analyze these issues. We use an auxiliary Fock-space picture of the hierarchy to first identify the unbalanced hierarchy-raising terms responsible for the strong transient amplification associated with the non-normal algebraic structure of the HEOM generator. We then apply a non-unitary similarity transformation that converts these terms into balanced combinations of hierarchy-raising and hierarchy-lowering terms, thereby suppressing their numerical impact. We first demonstrate the efficacy of this approach via a spin-boson model with a simple Brownian oscillator spectral den- sity and subsequently extend the analysis to a structured spectral density, showing for both cases that the transformed HEOM approach allows simulations of much larger system-bath coupling than would otherwise be possible.

Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.

We establish a fully static, dissipation-only primitive for Gaussian state transfer in which collective coupling to a shared environment fixes a single transfer time without coherent transport or time-dependent control. The dynamics close in a bright--dark decomposition, yielding an analytic transfer time $t^{*} = π/ g_{a}$ and a real interference factor that eliminates dynamical phase accumulation, so that all phase sensitivity arises solely from the Gaussian fidelity metric. This defines a fixed-time Gaussian communication channel in which dissipation mediates information transfer without active control. Ensemble analysis shows that channel performance remains robust to amplitude-level asymmetries, which act as uniform-rate dressing, whereas phase-level system detuning disrupts the fixed-time mechanism via dynamical phase winding and produces revival behavior. Incorporating finite Ornstein--Uhlenbeck memory via a zeroth-order O-operator expansion yields only rate and phase renormalization without introducing new dynamical pathways. In the fast-memory regime, environmental correlations are rapidly suppressed, rendering the channel insensitive to environmental detuning and restoring the Markovian limit. These results show that collective dissipation alone is sufficient to support fixed-time Gaussian state transfer, challenging the assumption that coherent transport or active control are required for continuous-variable communication.

Connecting mathematical formalism in open quantum systems to its underlying physics necessitates the notion of a dilation, a way to bridge stochastic dynamics with deterministic Schrödinger evolution on a larger space. Although dilations are well known in the literature for states, channels, and quantum combs, there is a substantial gap when it comes to the fully general setting of non-Markovian dynamics on a continuous interval. In an accompanying work, we introduce a continuous process tensor (cPT) framework wherein these processes are represented by vectors in multi-species bosonic Fock spaces of $L^2$ functions. This accommodates all multi-time statistics of a quantum system on an interval. Here, we present a corresponding dilation theorem and show that all cPTs can be approximated arbitrarily well by an explicit closed description with system and environment coupled by a bounded Hamiltonian. As well as its physical appeal and demonstrating completeness of the framework, we show that such regular representations actually underpin the formalism, defining a dense subspace of all cPTs that is easy to handle. This leads to a continuum-suitable version of Choi duality, and permits the rigorous treatment of continuum controls.

We propose candidate lower bounds on the real Grothendieck constants $K_{\mathrm G}(d)$ and their infinite-dimensional limit $K_{\mathrm G}$ using rotationally invariant cubic kernels. For the continuous construction, we identify an explicit threshold above which hemispherical binary strategies are unstable under cubic boundary deformations. Supported by numerical evidence, we conjecture that hemispherical strategies are globally optimal at this threshold. This conjecture would imply $K_{\mathrm G}\geq9π/16\simeq1.767146$, improving the rigorous lower bound $6π/11\simeq1.713596$. We also construct finite symmetric coefficient matrices from unit vectors in dimensions up to $24$. Large-scale see-saw optimization supports the continuous predictions and suggests improved lower bounds on $K_{\mathrm G}(d)$ in the studied dimensions from $4$ to $24$, conditional on the conjectured binary optima being exact. Selected matrices also yield finite-setting candidate dimension witnesses when interpreted as bipartite correlation Bell functionals. If the corresponding binary upper bounds hold, these witnesses would certify a local Hilbert-space dimension of at least five for each party.

Zero-knowledge proofs (ZKPs) enable the verification of a statement without revealing any information beyond its validity and constitute a fundamental primitive in cryptography and information theory. However, existing constructions rely on computational assumptions and are predominantly confined to bipartite settings, leaving their information-theoretic realization in bipartite or network scenarios largely unexplored. Here we develop a framework for zero-knowledge verification based on the indistinguishability of quantum states under operational constraints. Exploiting the fundamental limitations imposed by local operations, we show that a verifier is inherently restricted from extracting information about the underlying state while retaining the ability to verify correctness. We construct explicit protocols for multiparty quantum networks that achieve information-theoretic security, ensuring that no subset of collaborating parties can gain knowledge beyond the validity of the statement, independent of their joint computational power.

A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution $μ_p$, where the input bits are independent Bernoulli variables with fixed bias $p$. We show that for every fixed $p \in (0, 1)$, quantum query algorithms under the $μ_p$ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution $ν_p$ that is uniform over the slice of strings with Hamming weight $\lfloor pn \rfloor$ and prove a similar equivalence for the $ν_p$ distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.

Scalable fault-tolerant quantum error correction based on Gottesman-Kitaev-Preskill (GKP) codes requires finite-rate outer codes that can exploit analog GKP information under realistic circuit noise. However, quantum low-density parity-check (qLDPC) outer codes have not been systematically compared as candidates for circuit-level GKP concatenation. Here, we benchmark BB and tricycle codes using a unified simulation framework that progresses from code-capacity noise to repeated noisy syndrome extraction and schedule-resolved displacement propagation. Across all three noise models, analog-informed belief-propagation with ordered-statistics decoding (BP-OSD) yields higher finite-size crossing estimates than hard-decision decoding. In the full circuit model, the analog-informed crossings are \(σ_{\mathrm{th}}\simeq0.212\) for the selected BB sequence and \(0.142\) for the tricycle sequence, corresponding to squeezing requirements of approximately \(10.46\,\mathrm{dB}\) and \(13.94\,\mathrm{dB}\), respectively. These results show that analog GKP information continues to improve decoding under circuit-level noise. Under the common simulation assumptions used here, the selected BB sequence also yields a higher finite-size crossing estimate than the selected tricycle sequence.

A reduced ordered decision diagram is the minimal automaton of a function on words of fixed length: its nodes are the residuals, and reduction is the Myhill--Nerode quotient. We study what happens when that quotient is coarsened by a group. Fix a group $G$ acting on residuals, merge two nodes when their residuals lie in one $G$-orbit, and record the group element on the edge. For functions $\{0,1\}^n\to\mathbb{C}$ and $G$ the Pauli group this is the Local Invertible Map Decision Diagram. We take $G$ from the two-parameter family generated by $C^{\leq k}R_q$, the phase rotation of order $q$ with up to $k$ control qubits, with and without the bit flip $X$. We show that this gives exponential succinctness improvements compared to Pauli-LIMDD, and we determine the succinctness order of the family completely. The separating objects are hypergraph states, which can always be efficiently represented by some member of the family. We settle the tractability of five queries and eight transformations, which is invariant across the family, and shows the same behavior as Pauli-LIMDD. We give a five-rule reduction system whose normal forms are unique for every member of the family, and we show that this canonical form is computable in polynomial time in the size of the LIMDD. We show that, when coarsening beyond the (anti-)diagonal groups, the calculation of a minimal sized normal form turns out to be non-local and it might to rebuild the whole diagram.

We study the problem of learning a local Lindbladian in the presence of state-preparation-and-measurement (SPAM) noise. Although recent work has developed scalable learning algorithms under idealized access assumptions, SPAM can make distinct Lindbladians experimentally indistinguishable, thus making part of the Lindbladian fundamentally unlearnable. We give a sharp characterization of this obstruction for bounded-degree local Lindbladians. We identify a family of locality-preserving gauge transformations that commutes with trusted single-qubit control, and use it to classify Lindbladian components. For the generically gauge dependent components, we construct Lindbladians to show that they can have $Ω(1)$ uncertainty independent of system size, even after imposing complete positivity. We complement this characterization with SPAM-robust algorithms for learning every universally gauge-invariant component. Our algorithms use only trusted single-qubit operations, require neither ancillas nor entangling control, and use $\widetilde{\mathcal O}\left(ε^{-2}\log(N/δ)\right)$ experiments and total evolution time for constant locality and degree. Our guarantees allow global SPAM to become arbitrarily far from ideal as $N$ grows, requiring only nonvanishing local visibility. We also establish sufficient conditions for boundary-induced gauge invariance of additional Hamiltonian coefficients under physical positivity constraints, though learning these additional parameters in general remains an open problem. More broadly, our gauge-aware framework and SPAM-cancellation techniques offer a practical toolkit for the scalable characterization of open quantum systems.

Time-multiplexed (TDM) photonic reservoirs are usually judged by their scores on a few datasets, which say little about a chip's overall performance, and designed by enumerating candidate circuits and simulating each one, which is inefficient and gives no guarantee of finding a good structure. For a time-unrolled passive linear network with data-modulated gates or sources and a ridge readout, we derive an exact bridge from the task to the prediction risk in three steps. (i) Task features: the finite-shot risk depends on the time series only through finitely many statistics of its training windows and their correlations with the target, selected by the encoding and the optical paths. (ii) Encoding: every output moment is a polynomial in the features of the data-modulated sites, with degree and support bounded by tuples of optical paths. Gate encoding reads the characteristic function and creates interactions across time lags; squeezing encoding reads the moment-generating function and displacement encoding low-order moments, and with quadrature receivers they yield only additive and linear models, respectively, for every topology. (iii) Readout: for homodyne, heterodyne and photon-number receivers the risk closes exactly, and its dependence on the number of shots is an explicit sum over signal-to-noise modes; threshold clicks admit finite-dictionary approximations with certified error. Parts of the network that share no light carry independent states, which a receiver combines only through measurement events that join them. Checks on seven datasets confirm every exact statement to machine precision. The three steps thus yield a useful space of candidate TDM architectures, pruned by exact statements rather than by trial simulation, which can in future guide the selection of TDM chips for target requirements.

A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied. The Clifford template compilation problem asks how to choose these repetition numbers so that the template realizes a target transformation of Pauli operators. This problem arises, for example, when searching for logical operations in quantum error correction using only Clifford operations permitted by physical or fault-tolerance constraints. Although forward Clifford dynamics is efficiently classically simulable, this inverse problem has sharp complexity transitions. For commuting templates with unrestricted integer exponents, feasibility lies in $\mathrm{NP}\cap\mathrm{BQP}$ and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at $k=1$, recovering the repetition number contains finite-field discrete logarithm over $\mathbb{F}_{2^r}^{\times}$. In general, restricting every exponent to $\{0,1\}$ removes the Abelian-group closure and makes feasibility NP-complete for variable $k$, even for exactly commuting CNOT-only operations and X-type Paulis. For commuting self-inverse Clifford actions, both binary feasibility and recovery of one solution are classically polynomial-time solvable, but imposing a bound on the total repetition count is NP-complete, even for CNOT-only operations. These results reveal a rich complexity landscape within Clifford template compilation, spanning classically tractable cases, problems admitting quantum polynomial-time algorithms, and NP-complete variants.

We introduce a technological capability scale that ranks civilizations by the control operations they can perform per second. A control operation is defined as setting one binary degree of freedom of matter to a specified value, whatever its previous state. Building on constructor theory, we sort them into construction and its special cases on information media, namely processing, storage and transfer. The index $Ξ= K + B$ adds to the Kardashev index $K$ an efficiency index $B$ of energy per operation, measured from the thermal floor at the microwave background temperature. The Kardashev scale gives the ceiling for resets of thermally random bits with heat radiated into the present sky, and the Barrow scale gives the floor, which for such a reset is the thermal floor at the heat-rejection temperature at every level. Since 1950 the energy per logic operation has fallen 11.7 orders of magnitude, around 5 through miniaturization. Humanity, at $K = 0.73$, computes with CMOS logic gates at $B = -0.78$ in primary energy. We describe the ultimate technology, at $Ξ= 7.58$, which would dissipate the conjectured largest power $c^5/4G$ into an uncharged, non-rotating black hole near its largest mass in de Sitter space.

The complex spacing ratio is the complex displacement from a reference eigenvalue to its nearest neighbor divided by the corresponding displacement to its next-to-nearest neighbor. Its statistics provide a useful diagnostic of spectral correlations and nonintegrability in open quantum systems. Here, starting from the exact joint eigenvalue probability densities, we derive finite-$N$ complex-spacing-ratio distributions for the Gaussian ensembles of non-Hermitian random matrices in classes AI$^†$ and AII$^†$, realized by complex symmetric and complex self-dual random matrices, respectively. In class AII$^†$, we obtain an exact algebraic expression for arbitrary $N$ and explicitly evaluate the distributions and representative moments for $N=3, 4, 5, 6$. In class AI$^†$, although the joint density retains a noncompact integral over nonunitary eigenvector degrees of freedom, we analytically derive a normalized one-dimensional integral representation for $N=3$ and determine the asymptotic behavior, including a logarithmic correction to the cubic level repulsion and a nonanalytic contribution to the angular density. We further confirm these analytical results through direct numerical diagonalization of non-Hermitian random matrices.

Vector-vortex photons, characterized by a nonseparable coupling between polarization and orbital angular momentum (OAM), offer opportunities for optical manipulation, quantum communication, nuclear photonics, etc. However, their generation in the $γ$-ray regime remains challenging. Here, we put forward a novel method to generate vector-vortex $γ$ photons via nonlinear Compton scattering in elliptically polarized laser pulses. We reveal that tailoring laser ellipticity directs the multiphoton absorption to coherently populate OAM modes with opposite winding numbers, $\pm \ell$, tied to orthogonal circular polarizations, producing nonseparable spin-OAM photon states. For a linearly polarized laser of moderate intensity (dimensionless amplitude $a_0 \sim 1$), the mode-pair concurrence--a 0-to-1 measure of spin-OAM entanglement--reaches unity for MeV $γ$ photons, realizing maximally nonseparable radial- or azimuthal-type vector-vortex states. The laser amplitude further controls the accessible OAM spectrum. Our method offers a route to MeV vector-vortex photons, opening a new avenue for nuclear-scale structured photonics and high-energy quantum information.

We numerically study laser deceleration, cooling and trapping of host fast ortho-positronium (Ps) bunches as produced in silica microchannel targets using positron bunches from a Surko trap. While Doppler laser cooling routinely allows to cool neutral atom species below milli-Kelvin kinetic temperatures, the fast ground state annihilation and the high recoil shift to line-width ratio in Ps pose new challenging limitations on timing and the required laser power. Earlier theoretical work and first experiments already exhibit viable prospects for radiation pressure cooling to create unprecedented cold and dense Ps ensembles. Our extended numerical studies confirm very good prospects to simultaneously decelerate, cool and optically trap Ps atoms in a standard Doppler cooling geometry on the $1^3\mathrm{S}$--$2^3\mathrm{P}$ transition. Including the full Zeeman state manifolds and adding additional transverse lasers on the $2^3\mathrm{P}$--$3^3\mathrm{D}$ transition improves timing and final temperature to allow for optical trapping at the end. The required laser powers and geometry parameters to implement effective slowing and trapping within a time frame, where the majority of atoms is not annihilated, is in reach of current technology of $\mathrm{mJ}$ energy pulses of approximately $100\ \mathrm{ns}$ duration. Future extensions to collectively enhance cooling and trapping in optical cavities or hollow-core fibres should finally allow fast preparation of ultra-cold Ps systems as future basis of superradiant lasing and Bose--Einstein condensates.

Quantum circuit Born machines (QCBMs) built with instantaneous quantum polynomial (IQP) circuits have loss functions that can be efficiently estimated classically, but require quantum computers during inference. Thus, classical computers can train large IQP QCBMs that exceed the qubit numbers of available quantum hardware. This motivates research into how qubit-limited quantum computers can be used to sample from larger IQP QCBMs. Leveraging insights from classical simulation of noisy IQP circuits, we propose a deployment protocol for IQP QCBMs that injects noise at the logical level to probabilistically decompose the original circuit into smaller clusters that can be sampled on qubit-limited quantum processors. We also apply lightweight resampling of known noisy qubits to mitigate the impact of the introduced error. Numerical simulations of our protocol applied to shallow IQP QCBMs and IBM Heron experiments deploying a 316-qubit IQP circuit onto 156-qubit hardware show that mitigation improves the similarity of the empirical distribution to the target distribution. The proposed deployment protocol also crucially preserves correlation structures more accurately than a classical baseline that has accurate single-qubit marginals.

Identifying regimes in which interacting fermionic systems admit efficient classical simulation is a crucial task in quantum many-body physics. In this work, we rigorously establish the Gaussianity and classical simulability of sufficiently weakly interacting fermions. For the Gibbs state of a local interacting fermionic Hamiltonian $H=H_0+V$ at any finite temperature and in any spatial dimension, where $H_0$ is quadratic and $V$ is the interaction term, we show that there exists a positive interaction strength below which the Gibbs state is a convex mixture of fermionic Gaussian states. Moreover, based on this structure, we construct a polynomial-time classical sampler for the Gibbs state via Metropolis updates on a tree whose leaves are Gaussian states.

In this paper, we prove that the Mean-Field Approximate Optimization Algorithm (MF-AOA), a quantum-inspired classical algorithm of the Quantum Approximate Optimization Algorithm (QAOA), is unable to give arbitrary near optimal solution for problems exhibiting the Overlap Gap Property (OGP). We show this by relating the MF-AOA to finite-memory Approximate Message Passing (AMP) algorithms, which are known to be limited in performance by the OGP. Thus, our paper argues that problems exhibiting the OGP are one such instance where the QAOA can outperform the MF-AOA and AMP algorithms in general. We supplement this by numerically simulating the performance of the QAOA on instances of Max-$4$-XORSAT that exhibit the OGP and find that the QAOA is able to surpass the barrier, while our finite-size scaling analysis favors a super-polynomial over a polynomial depth dependence. In addition, we observe a non-differentiable point in the performance of the QAOA near by the OGP barrier, where the optimal QAOA parameters change from an adiabatic to a non-adiabatic schedule.

Designing quantum codes with both transversal non-Clifford gates and good error-correcting parameters is an important goal in fault-tolerant quantum computation. Here, we construct an explicit family of binary CSS codes with constant rate and linear distance that admit fully addressable transversal $T$ gates. Specifically, any prescribed tensor product of logical powers of $T$ is implemented by a tensor product of physical powers of $T$, without any subsequent correction. Our construction combines algebraic-geometry codes with suitable binary embedding to obtain generalized divisibility of binary codes. This divisibility then enables fully addressable transversal $T$ gates. Furthermore, we formulate the minimum binary embedding length problem as a minimum-weight problem over an affine space and numerically improve the constants in the asymptotic rate and relative-distance bounds.

The exact classical simulation of non-integrable quantum systems rapidly becomes intractable beyond small system sizes, yet its role is central to predicting many-body dynamics. Approximate methods alleviate this cost but typically lack rigorous guarantees on their deviation from the exact result. For the infinite-temperature correlation function, we derive a rigorous error bound for approximating the full dynamics within a computable finite-sized region. Applied to autocorrelations, this finite-region approach is especially accurate across one-dimensional systems and beyond, and can further provide rigorous error bounds for other approximate methods, demonstrated here for matrix-product-operator simulations.

The Landau-Lifshitz-Gilbert (LLG) equation provides the fundamental description of dissipative magnetization dynamics. A recently proposed quantum analog, the quantum Landau-Lifshitz-Gilbert (QLLG) equation, extends this framework to quantum spin systems. However, whether the QLLG equation recovers the LLG equation in the classical large-spin limit for interacting spin systems remains an open question. Here, we demonstrate this connection by deriving the LLG equation as the classical large-spin limit of the QLLG equation. We establish this correspondence analytically and verify it numerically for an interacting spin system. These results provide a quantum-to-classical description of dissipative spin dynamics, offering a microscopic foundation for the LLG equation. From numerical calculations provided here, we also conclude that quantum effects become much less noticeable for systems with larger number of spins in the Hamiltonian.

Decoded quantum interferometry (DQI) and its Hamiltonian extension (HDQI) prepare states whose amplitudes are low-degree polynomials of an objective, using Fourier transforms and coherent decoding. We recast this approach as quantum state transduction through algebra homomorphisms. We transfer an efficiently preparable operator state of a degree-$D$ polynomial in a source Hamiltonian $H_A$ to the corresponding polynomial state of a target Hamiltonian $H_B=π(H_A)$, where $π$ is a unital $*$-homomorphism between the finite-dimensional source and target $C^*$-algebras. The transduction uses operator Fourier transforms and relative decoding to recover source operators rather than individual term-selection labels. The relative distance $d_{\mathrm{rel}}$ is the first degree at which source and target traces disagree. We prove that $2D<d_{\mathrm{rel}}$ is equivalent to preserving all inner products between degree-$D$ polynomials. Moreover, $d_{\mathrm{rel}}\ge d_{\mathrm{ord}}$, where $d_{\mathrm{ord}}$ is the ordinary distance used in (H)DQI, and we give families with $d_{\mathrm{ord}}=O(1)$ but $d_{\mathrm{rel}}=Θ(n)$ and efficient decoders. Our framework replaces the complicated pilot state preparation by the more modular task of preparing a source polynomial state. DQI and HDQI arise as relation-free special cases. The framework accommodates nonuniform coefficients and noncommuting interactions and extends to fermionic, qudit, and bosonic systems, with applications to approximate optimization and Gibbs sampling. As evidence of advantages, for a nonlinear pairwise variant of optimal polynomial intersection where constant $d_{\mathrm{ord}}$ limits DQI-style preparations, relative decoding yields an ideal quantum score of 0.643 versus 0.606 for the best tested classical heuristic, a gap exceeding 3 percentage points.

Dephasing can sharpen the activation of a dissipative quantum neuron, but a stationary response does not determine how much input information its output delivers per unit time. For a single qubit with partial-reset updates at rate $ν$, we derive the threshold response bandwidth and the exact local Fisher information rate of the complete record from repeated projective readouts, including their backaction. Near the activation threshold, the rate obeys $\mathcal R\leqν(1-s)(1+s)^2/2\leq16ν/27$, where $s$ is the retained amplitude of each update. For every fixed finite Markovian dephasing rate, optimization over the readout interval and $s$ gives the same supremum, approached at $s=1/3$ with arbitrarily rapid ideal readout. A finite measurement dead time instead selects a finite optimal interval, which we obtain by a dimensionless two-parameter optimization. The ideal bound is saturated by a classical two-state jump process: quantum coherence changes finite-cadence performance but cannot raise the optimized bound. These results separate noise-enhanced activation from the operational information throughput of a quantum neuron and provide a hardware-aware benchmark for finite-time quantum neural processing.

The combination of quantum sensing with quantum computing to provide an enhancement over conventional quantum sensing has recently emerged as a promising potential application of quantum computing that could give advantages without needing large-scale or fault-tolerant hardware. In this work, we report an experimental demonstration of a recent theoretical proposal to repurpose Grover's search algorithm to improve the ability to detect signals with unknown frequency within a large detection bandwidth. Our experiments were based on a system comprising a single superconducting qubit coupled to a single superconducting cavity, highlighting the modest hardware requirements for realizing the protocol. We found that Grover-based sensing was able to outperform the natural non-Grover baseline for our experimental platform for detection bandwidths $>$10~MHz, with an advantage that empirically grew superlinearly with the bandwidth beyond that break-even point. The use of the Grover-based protocol reduced the amount of signal that needed to be sensed to make an accurate detection decision by more than 10$\times$ for choices of larger detection bandwidth and higher desired detection accuracy. Our results provide a proof-of-principle validation that Grover-based quantum computational sensing can be realized in near-term hardware and provide a metrological advantage well beyond break-even in spite of the additional protocol complexity.

Enantiomer-specific state transfer (ESST) based on electric-dipole transitions has attracted considerable interest in the studies of manipulating molecules with electromagnetic fields. It also holds promise as a powerful tool for enantiomer detection and separation. To date, experimental demonstrations of ESST have focused mainly on molecules in the lowest rotational angular-momentum states, namely, $J=0$ and $J=1$. Realistic molecular samples, however, may contain appreciable populations in higher-$J$ rotational states, making it desirable to develop ESST schemes applicable to such states. Nevertheless, one cannot derive such schemes via a simple and straightforward extension of existing low-$J$ schemes, because higher-$J$ manifolds contain more magnetic sub-levels and involve more complicated networks of electric-dipole transitions. Here, we propose an ESST scheme for chiral molecules involving the $J=1$ and $J=2$ rotational states. Specifically, our scheme is based on enantiomer-specific pumping driven by three linearly polarized microwave fields and one laser beam. Under this scheme, one enantiomer is pumped into an enantiomer-specific dark state within a sub manifold with $J=1,2$, whereas the other enantiomer is dissipatively pumped out of this manifold. Our strategy can be extended to systems involving rotational states with even higher angular momenta.

The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems. In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let $ζ_p$ be a primitive $p$-th root of unity, let $π=ζ_p-1$, and write $q=p^t$ and $L=t(p-1)$. We work over $R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)$, where the isomorphism follows from the total ramification identity $(p)=(π)^{p-1}$. We exploit the resulting $π$-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo $π^{L},π^{L-1},\ldots,π$. For every fixed prime $p$ and modulus $q=p^t$, our algorithm solves the CCP in time and sample complexity $2^{O_p(\log n\log q)}$, using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when $q=\text{poly}(n)$. This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting. However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.

Models of quantum systems faithfully map system parameters to observations, but the inverse problem of parameter inference from measurement data presents a fundamental challenge: computationally intractable likelihoods due to an exponentially large Hilbert space. Here, we introduce simulation-based quantum system inference, a unified, likelihood-free framework that learns parameter posteriors directly from classical simulation data. The central idea is to pair polynomial-cost classical simulators, such as Pauli propagation and tensor networks, with normalizing flows or other neural density estimators for accurate, reusable inference. A single model, trained once, maps any new measurement record to its posterior in one forward pass---turning per-experiment inference into a fixed, up-front cost. We numerically demonstrate the framework's versatility across Pauli noise learning, quantum error mitigation, quantum state tomography, and Hamiltonian learning, with examples involving 81-qubit shallow circuits and 735-parameter inference. In each case, the approach yields accurate estimates of identifiable parameters, while posterior uncertainty provides additional diagnostics of non-identifiability and indicates where further characterization is needed. Our framework reduces data-acquisition requirements in quantum experiments and accelerates parameter inference, providing a practical route to characterizing and improving large-scale quantum systems.