QIP · 2026

We prove by construction that the Bravyi-Poulin-Terhal bound on the spatial density of stabilizer codes does not generalize to stabilizer circuits. To do so, we construct a fault tolerant quantum computer with a coding rate above 5$\%$ and quasi-polylog time overhead, out of a line of qubits with nearest-neighbor connectivity, and prove it has a threshold. The construction is based on modifications to the tower of Hamming codes of Yamasaki and Koashi (Nature Physics, 2024), with operators measured using a variant of Shor’s measurement gadget.

Understanding quantum theory's causal structure stands out as a major matter, since it radically departs from classical notions of causality. We present advances in the research program of causal decompositions, which investigates the existence of an equivalence between the causal and the compositional structures of unitary channels. Our results concern one-dimensional Quantum Cellular Automata (1D QCAs), i.e.\ unitary channels over a line of N quantum systems (with or without periodic boundary conditions) that feature a causality radius r: a given input cannot causally influence outputs at a distance more than r. We prove that, for N ≥ 4r + 1, 1D QCAs all admit causal decompositions: a unitary channel is a 1D QCA if and only if it can be decomposed into a unitary routed circuit of nearest-neighbour interactions, in which its causal structure is compositionally obvious. This provides the first constructive form of 1D QCAs with causality radius one or more, fully elucidating their structure. In addition, we show that this decomposition can be taken to be translation-invariant for the case of translation-invariant QCAs. Our proof of these results makes use of innovative algebraic techniques, leveraging a new framework for capturing partitions into non-factor sub-C* algebras.

We investigate the relationship between partial traces and their dilations for general complex matrices, focusing on two main aspects: the existence of (joint) dilations and norm inequalities relating partial traces and their dilations. Throughout our analysis, we pay particular attention to rank constraints. We find that every pair of matrices of equal size and trace admits dilations of any rank larger than one. We generalize Audenaert's subadditivity inequality to encompass general matrices, multiple tensor factors, and different norms. A central ingredient for this is a novel majorization relation for Kronecker sums. As an application, we extend the interval of Werner states in which they are provably 2-undistillable in any dimension $d\geq 4$. We also prove new Schmidt-number witnesses and k-positive maps.

We present an end-to-end quantum algorithm with provable performance guarantees for simulating a large class of classical nonlinear dynamical systems. The considered dynamical systems are described by stochastic dissipative differential equations with a quadratic nonlinearity satisfying certain sparsity and divergence-free conditions. Our algorithm approximates the expected value of any sparse low-degree polynomial evaluated at the solution of the classical system. The runtime scales poly-logarithmically with the system size and polynomially with the evolution time, inverse error tolerance, and parameters quantifying sparsity, dissipation, and nonlinearity strength. The considered simulation problem is shown to be BQP-complete, providing a strong evidence for a quantum advantage. We benchmark the quantum algorithm via numerical experiments by simulating a vortex flow in the 2D Navier Stokes equation.

Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using $\Theta(\log \log n)$-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of \emph{constant-time} quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class $\mathsf{QAC^0}$. Finally, our results suggest a new approach towards proving that PARITY is not computable in $\mathsf{QAC^0}$, a long-standing question in quantum complexity theory.

The Clifford group plays a central role in quantum information science. It is the building block for many error-correcting schemes and matches the first three moments of the Haar measure over the unitary group—a property that is essential for a broad range of quantum algorithms, with applications in pseudorandomness, learning theory, benchmarking, and entanglement distillation. At the heart of understanding many properties of the Clifford group lies the Clifford commutant: the set of operators that commute with $k$-fold tensor powers of Clifford unitaries. Previous understanding of this commutant has been limited to relatively small values of $k$, constrained by the number of qubits $n$. In this work, we develop a complete theory of the Clifford commutant. Our first result provides an explicit orthogonal basis for the commutant and computes its dimension for arbitrary $n$ and $k$. We also introduce an alternative and easy-to-manipulate basis formed by isotropic sums of Pauli operators. We show that this basis is generated by products of permutations— which generate the unitary group commutant— and at most three other operators. Additionally, we develop a \emph{graphical calculus} allowing a diagrammatic manipulation of elements of this basis. These results enable a wealth of applications: among others, we characterize all \emph{measurable} magic measures and identify optimal strategies for stabilizer property testing, whose success probability also offers an operational interpretation to stabilizer entropies. Finally, we show that these results also generalize to multi-qudit systems with prime local dimension. This submission merges two of our recent works: one presenting a complete theory of the Clifford commutant with applications, and one focused on showcasing a major application to state $k$-design convergence.

Causal modelling frameworks link observable correlations to causal explanations, which is a crucial aspect of science. These models represent causal relationships through directed graphs, with vertices and edges denoting systems and transformations within a theory. Most studies focus on acyclic causal graphs, where well-defined probability rules and powerful graph-theoretic properties like the d-separation theorem apply. However, understanding complex feedback processes and exotic fundamental scenarios with causal loops requires cyclic causal models, where such results do not generally hold. While progress has been made in classical cyclic causal models, challenges remain in uniquely fixing probability distributions and identifying graph-separation properties applicable in general cyclic models. In cyclic quantum scenarios, existing frameworks have focussed on a subset of possible cyclic causal scenarios, with graph-separation properties yet unexplored. This work proposes a framework applicable to all consistent quantum and classical cyclic causal models on finite-dimensional systems. We address these challenges by introducing a robust probability rule and a novel graph-separation property, p-separation, which we prove to be sound and complete for all such models. Our approach maps cyclic causal models to acyclic ones with post-selection, leveraging the post-selected quantum teleportation protocol. We characterize these protocols and their success probabilities along the way. We also establish connections between this formalism and other classical and quantum frameworks to inform a more unified perspective on causality. This provides a foundation for more general cyclic causal discovery algorithms and to systematically extend open problems and techniques from acyclic informational networks (e.g., certification of non-classicality) to cyclic causal structures and networks.

We provide several quantum algorithms for continuous optimization that do not require gradient estimation. Instead, we encode the optimization problem into the dynamics of a physical system and coherently simulate the time evolution. Our first two algorithms can find local optima of a differentiable function $f: \mathbb{R}^N \rightarrow \mathbb{R}$ by simulating either classical or quantum dynamics with friction via a time-dependent Hamiltonian. We show that for the benchmark problem of optimizing a locally quadratic objective function, these methods require a total of $O(N^2\kappa^2/h_x^2\epsilon)$ queries to a phase oracle to find an $\epsilon$-approximate local optimum, where $\kappa$ is the condition number of the Hessian matrix and $h_x$ is the discretization spacing. In contrast, we show that methods based on gradient descent require $O(N^{3/2}(1/\epsilon)^{\kappa \log(3)/4})$ queries. This corresponds to an exponential separation between the query upper bounds for the benchmark problem. Our third algorithm can find the global optimum of $f$ by preparing a classical low-temperature thermal state via simulation of the classical Liouvillian operator associated with the Nosé Hamiltonian. We use results from the quantum thermodynamics literature to bound the thermalization time for the discrete system. Additionally, we analyze barren plateau effects that commonly plague quantum optimization algorithms and observe that our approach is vastly less sensitive to this problem than standard gradient-based optimization. Our results suggests that these dynamical optimization approaches may be far more scalable for future quantum machine learning, optimization and variational experiments than was widely believed.

Quantum computing promises exponential speedups for certain problems, yet fully universal quantum computers remain out of reach and near-term devices are inherently noisy. Motivated by this, we study noisy quantum algorithms and the landscape between BQP and BPP. We build on a powerful technique to differentiate quantum and classical algorithms called the level-$\ell$ Fourier growth (the sum of absolute values of Fourier coefficients of sets of size $\ell$) and show that it can also be used to differentiate quantum algorithms based on the types of resources used. We show that noise acting on a quantum algorithm dampens its Fourier growth in ways intricately linked to the type of noise. Concretely, we study noisy models of quantum computation where highly mixed states are prevalent, namely: DQC_k algorithms, where k qubits are clean and the rest are maximally mixed, and 1/2-BQP algorithms, where the initial state is maximally mixed, but the algorithm is given knowledge of the initial state at the end of the computation. We establish upper bounds on the Fourier growth of DQC_k, 1/2-BQP and BQP algorithms and leverage the differences between these bounds to derive oracle separations between these models. In particular, we show that the 2-Forrelation and 3-Forrelation problems require $N^{\Omega(1)}$ queries in the DQC_1 and 1/2-BQP models respectively. Our results are proved using a new matrix decomposition lemma that might be of independent interest.

We study the complexity of computing the mixed Schatten $\|\Phi\|_{q\to p}$ norms of linear maps $\Phi$ between matrix spaces. When $\Phi$ is completely positive, we show that $\| \Phi \|_{q \to p}$ can be computed efficiently when $q \geq p$. The regime $q \geq p$ is known as the non-hypercontractive regime and is also known to be easy for the mixed vector norms $\ell_{q} \to \ell_{p}$ [Boyd, 1974]. However, even for entanglement-breaking completely-positive trace-preserving maps $\Phi$, we show that computing $\| \Phi \|_{1 \to p}$ is $\NP$-complete when $p>1$. Moving beyond the completely-positive case and considering $\Phi$ to be difference of entanglement breaking completely-positive trace-preserving maps, we prove that computing $\| \Phi \|^+_{1 \to 1}$ is $\NP$-complete. In contrast, for the completely-bounded (cb) case, we describe a polynomial-time algorithm to compute $\|\Phi\|_{cb,1\to p}$ and $\|\Phi\|^+_{cb,1\to p}$ for any linear map $\Phi$ and $p\geq1$.

We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. Our hardness results also hold for deciding if the contraction coefficient is equal to 1. As a consequence, we show that deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.

All-to-all interactions arise naturally in many areas of theoretical physics and across diverse experimental quantum platforms, motivating a systematic study of their information-processing power. Assuming each pair of qubits interacts with $\mathcal{O}(1)$ strength, time-dependent all-to-all Hamiltonians can simulate arbitrary all-to-all quantum circuits, performing quantum computation in time proportional to the circuit depth. In this work, we show that this naive correspondence is far from optimal: all-to-all Hamiltonians can process information on much faster timescales. Our first main result establishes that any two-qubit gate can be simulated by all-to-all Hamiltonians on $N$ qubits in time $\mathrm{O}(1/N)$ (up to factor $N^{\delta}$ with an arbitrarily small constant $\delta>0$), with polynomially small error $1/\mathrm{poly}(N)$. Immediate consequences include: 1) Certain $\mathrm{O}(N)$-qubit unitaries, such as the multiply-controlled Toffoli gate, can be realized in $\mathrm{O}(1/N)$ time. 2) Globally entangled states such as the GHZ and W states of $\mathrm{O}(N)$ qubits can be prepared in $\mathrm{O}(1/N)$ time. 3) Any depth-$D$ circuit on $N_{\rm d}$ qubits can be simulated in arbitrarily short time $T=\mathrm{O}(DN_{\rm d}/N)$, inversely proportional to the space overhead $N/N_{\rm d}$. 4) The existing Lieb-Robinson bound for strong power-law interactions $H_{ij}\sim r_{ij}^{-\gamma}$ in spatial dimension $\mathsf{d}>\gamma$ is tight, requiring time $T=\Omega(N^{\frac{\gamma}{\mathsf{d}}-1})$ for information to propagate. Our second main result shows that any depth-$D$ quantum circuit can be simulated in time $T=\mathrm{O}(D/\sqrt{N})$ with constant space overhead, with error $1/\mathrm{poly}(N)$ for almost all inputs. This “optimistic” simulation may suffice for practical purposes: for instance, building on prior work, we demonstrate that Shor’s factoring algorithm can be implemented by $\mathrm{O}(\sqrt{N})$-time Hamiltonian evolution with constant space overhead. The techniques underlying our results depart fundamentally from the existing literature on parallelizing commuting gates: We rely crucially on non-commuting Hamiltonians and draw on diverse ideas from semiclassical quantum mechanics, (spin) squeezing, Mølmer–Sørensen gates, and spin-wave physics.

We introduce new theoretical mechanisms for quantum speedup in the global optimization of nonconvex functions, broadening the scope of quantum advantage beyond traditional tunneling-based explanations. By establishing a rigorous correspondence between the spectral properties of Schrödinger operators and classical Langevin diffusion, we identify regimes where a real-space adiabatic algorithm (RsAA) can significantly outperform classical stochastic gradient-based methods. Leveraging this connection and novel non-asymptotic versions of well-known semi-classical results, we provide polynomial (in the dimension $d$) runtime bounds for RsAA on rotated block-separable functions, and offer theoretical evidence that black-box classical algorithms require exponential time for optimization in these settings, thereby generalizing and formalizing prior work by Leng et al (arXiv:2311.00811). While we can design certain specialized, structure-aware classical algorithms that can efficiently optimize these functions, we further show that the quantum ground state exhibits remarkable robustness to nontrivial perturbations. Leveraging recent advances in the study of the hypercontractivity of Schr\"{o}dinger operators, we construct new families of nonconvex functions for which RsAA achieves polynomial-time optimization, whereas both off-the-shelf and structure-aware classical algorithms incur exponential computational costs. These results provide new insight into quantum-classical separations in nonconvex optimization and highlight tractable and general pathways to advantage in this setting.

We construct and classify entangled measurements with tetrahedral symmetry as group-covariant orbits of a fiducial state. For this class, localizability follows from the Clifford level of a diagonal phase in the fiducial, yielding an explicit hierarchy and efficient constructions. The framework recovers the two-qubit Elegant Joint Measurement (EJM) uniquely and extends it to multiqubit EJMs with identical local geometry but inequivalent global entanglement classes for n\ge3. A continuous family interpolating between the Bell measurement and the EJM realizes an infinite set of localizable tetrahedral bases.

We derive bounds on general continuous-variable quantum error correcting codes against the displacement noise channel. The bounds limit the distances attainable by codes and also apply in an approximate setting. Our main result is a quantum analogue of the classical Cohn-Elkies bound on sphere packing densities attainable in Euclidean space. We further derive a quantum version of Levenshtein's sphere packing bound and argue that Gottesman--Kitaev--Preskill (GKP) codes based on the $E_8$ and Leech lattices achieve optimal distances. The main technical tool is a continuous-variable version of the quantum MacWilliams identities, which we introduce. The identities relate a pair of weight distributions which can be obtained for any two trace-class operators. General properties of these weight distributions are discussed, along with several examples.

We introduce the notion of polynomial-depth duality transformations, which relates two sets of operator algebras through a conjugation by a poly-depth quantum circuit, and make use of this to construct efficient Gibbs samplers for a variety of interesting quantum Hamiltonians as they are poly-depth dual to classical Hamiltonians. This is for example the case for the 2D toric code, which is demonstrated to be poly-depth dual to two decoupled classical Ising spin chains for any system size, and we give evidence that such dualities hold for a wide class of stabilizer Hamiltonians. Additionally, we extend the above notion of duality to Lindbladians in order to show that mixing times and other quantities such as the spectral gap or the modified logarithmic Sobolev inequality are preserved under duality.

We initiate the study of \emph{quantum agnostic learning} of phase states with respect to a function class $\mathcal{C}\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}$: given copies of an unknown $n$-qubit state $|\psi\rangle$ which has fidelity $\textsf{opt}$ with a phase state $|\phi_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle$ for some $c\in \mathcal{C}$, output $|\phi\rangle$ which has fidelity $|\langle \phi | \psi \rangle|^2 \geq \textsf{opt}-\varepsilon$. To this end, we give agnostic learning protocols for the following classes: \begin{enumerate} \item Size-$t$ decision trees which runs in time $\textsf{poly}(n,t,1/\varepsilon)$. This also implies $k$-juntas can be agnostically learned in time $\textsf{poly}(n,2^k,1/\varepsilon)$. \item $s$-term DNF formulas in near-polynomial time $\textsf{poly}(n,(s/\varepsilon)^{\log \log s/\varepsilon})$. \end{enumerate} Our main technical contribution is a \emph{quantum agnostic boosting} protocol which converts a ``weak'' agnostic learner (which outputs a \emph{parity state} $|\phi\rangle$ such that $|\langle \phi|\psi\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)$) into a ``strong'' learner (which outputs a sum of parity states $|\phi'\rangle$ such that $|\langle \phi'|\psi\rangle|^2\geq \textsf{opt} - \varepsilon$). Using quantum agnostic boosting, we obtain the first ``near'' polynomial-time $n^{O(\log \log n)}$ algorithm for learning $\textsf{poly}(n)$-sized depth-$3$ circuits (consisting of $\textsf{AND}$, $\textsf{OR}$, $\textsf{NOT}$ gates) in the uniform quantum $\textsf{PAC}$ model using quantum examples. Classically, the analogue of efficient learning depth-$3$ circuits (and even depth-$2$ circuits) in the uniform $\textsf{PAC}$ model has been a longstanding open question in computational learning theory. Our work nearly settles this question, when the learner is given quantum examples.

In complexity theory, gap-preserving reductions play a crucial role in studying hardness of approximation and in analyzing the relative complexity of multiprover interactive proof systems. In the quantum setting, multiprover interactive proof systems with entangled provers correspond to gapped promise problems for nonlocal games, and the recent result MIP*=RE shows that these are in general undecidable. However, the relative complexity of problems within MIP* is still not well-understood, as establishing gap-preserving reductions in the quantum setting presents new challenges. In this paper, we introduce a framework to study such reductions and use it to establish MIP*-completeness of the gapped promise problem for the natural class of independent set games. In such a game, the goal is to determine whether a given graph contains an independent set of a specified size. We construct families of independent set games with constant question size for which the gapped promise problem is undecidable. In contrast, the same problem is decidable in polynomial time in the classical setting. To carry out our reduction, we establish a new stability theorem, which could be of independent interest, allowing us to perturb families of almost PVMs to genuine PVMs.

In a recent breakthrough in additive combinatorics, Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) resolved the polynomial Freiman-Ruzsa conjecture. Here, we algorithmize their main result by dequantizing the stabilizer learning algorithm of Chen et al. [QIP'25]

We study the error correcting properties of Haar random codes, in which a $K$-dimensional code space $\bC \subseteq \C^N$ is chosen at random from the Haar distribution. Our main result is that Haar random codes can approximately correct errors up to the quantum Hamming bound, meaning that a set of $m$ Pauli errors can be approximately corrected so long as $mK \ll N$. This is the strongest bound known for any family of quantum error correcting codes (QECs), and continues a line of work showing that approximate QECs can significantly outperform exact QECs [LNCY97,CGS05,BGG24]. Our proof relies on a recent matrix concentration result of Bandeira, Boedihardjo, and van Handel [BBV23].

Despite extensive study, our understanding of quantum Markov chains remains far less complete than that of their classical counterparts. [Temme'13] observed that the Davies Lindbladian, a well-studied model of quantum Markov dynamics, contains an embedded classical Markov generator, raising the natural question of how the convergence properties of the quantum and classical dynamics compare. While [Temme'13] showed that the spectral gap of the Davies Lindbladian can be exponentially smaller than that of the embedded classical generator for certain highly structured Hamiltonians, we show that if the spectrum of the Hamiltonian does not contain long arithmetic progressions, then the two spectral gaps must be comparable. As a consequence, we prove that for a large class of Hamiltonians, including those obtained by perturbing a fixed Hamiltonian with a generic external field, the quantum spectral gap remains within a constant factor of the classical spectral gap. Our result aligns with physical intuition and enables the application of classical Markov chain techniques to the quantum setting. The proof is based on showing that any ``off-diagonal'' eigenvector of the Davies generator can be used to construct an observable which commutes with the Hamiltonian and has a Lindbladian Rayleigh quotient which is comparably small. Thus, a spectral gap for such observables implies a spectral gap for the full Davies generator.

Learning the Hamiltonian underlying a quantum many-body system in thermal equilibrium is a fundamental task in quantum learning theory and experimental sciences. To learn the Gibbs state of local Hamiltonians at any inverse temperature $\beta$, the state-of-the-art provable algorithms fall short of the optimal sample and computational complexity, in sharp contrast with the locality and simplicity in the classical cases. In this work, we present a learning algorithm that learns each local term of an $n$-qubit $D$-dimensional Hamiltonian to an additive error $\epsilon$ with sample complexity $\tilde{O}( \frac{e^{\poly\beta}}{\beta^2\epsilon^2}) \log(n)$. The protocol uses parallelizable local quantum measurements that act within bounded regions of the lattice and near-linear-time classical post-processing. Thus, our complexity is near optimal with respect to $n,\epsilon$ and is polynomially tight with respect to $\beta$. We also give a learning algorithm for Hamiltonians with bounded interaction degree with sample and time complexities of similar scaling on $n$ but worse on $\beta, \epsilon$. At the heart of our algorithm is the interplay between locality, the Kubo-Martin-Schwinger condition, and the operator Fourier transform at arbitrary temperatures.

We present a novel approach to quantizing Markov chains. The approach is based on the Markov chain coupling method, which is frequently used to prove fast mixing. Given a particular coupling, e.g., a grand coupling, we construct a completely positive and trace preserving map. This quantum map has a unique fixed point, which corresponds to the quantum sample (qsample) of the classical Markov chain's stationary distribution. We show that the convergence time of the quantum map is directly related to the coupling time of the Markov chain coupling.

We introduce a basis-restricted variant of the Quantum-k-Sat problem, in which each term in the input Hamiltonian is required to be diagonal in either the standard or Hadamard basis. Our main result is that the Quantum-6-Sat problem with this basis restriction is already QMA1-complete, defined with respect to a natural gateset. Our construction is based on the Feynman-Kitaev circuit-to-Hamiltonian construction, with a modified clock encoding that interleaves two clocks in the standard and Hadamard bases. In light of the central role played by CSS codes and the uncertainty principle in the proof of the NLTS theorem of Anshu, Breuckmann, and Nirkhe (STOC ’23), we hope that the CSS-like structure of our Hamiltonians will make them useful for progress towards a quantum PCP theorem.

Given a Calderbank-Shor-Steane (CSS) code, it is sometimes necessary to modify the code by adding an arbitrary number of physical qubits and parity checks. Motivations may include concatenating codes, embedding low-density parity check (LDPC) codes into finite-dimensional Euclidean space, or reducing the weights of parity checks. During this embedding, it is essential that the modified code possesses an isomorphic set of logical qubits as the original code. However, despite numerous explicit constructions, the conditions of when such a property holds true is not known in general. Therefore, using the language of homological algebra, we provide a unified framework that guarantees a natural isomorphism between the output and input codes. In particular, we explicitly show how previous works fit into our framework.

A long-standing open problem in quantum complexity theory is whether QMA has perfect completeness, i.e. whether any QMA verifier can be made to have completeness $c=1$. Previous constructions have yielded a completeness parameter exponentially close to 1. We improve this to doubly-exponentially close to 1. Additionally, we show that QMA has perfect completeness if one allows the verifier an infinite-dimensional (witness) space. We show that this can be achieved using a gate set which is such that the ability to use an infinite-dimensional space does not increase the computational power of QMA. We also show that when using a finite-dimensional space of polynomially many qubits, a completeness doubly-exponentially close to 1 is optimal among black-box constructions. We show that the soundness can at most be made exponentially small using black-box reductions.

It is shown that every one-dimensional Hamiltonian with short-range interacting spins admits a quantum Gibbs sampler [CKG23] with a system-size independent spectral gap at all finite temperatures. Consequently, their Gibbs states can be prepared in polylogarithmic depth, and satisfy exponential clustering of correlations, generalizing [Ara69].

Markov Chain Monte Carlo (MCMC) methods are an essential tool in classical algorithms design. Especially, the Metropolis sampling algorithm and Glauber dynamics have drastically advanced our understanding of material properties, reaction dynamics, phase transitions, and thermodynamics. Recently, there has been a new wave of quantum MCMC algorithms that draws inspiration from the cooling process in Nature to design continuous-time Quantum Markov chains (i.e., Lindbladians) satisfying (approximate) detailed balance. Nevertheless, the quantum analog of detailed balance, which has been central to classical Markov chain design and analysis, has posed a challenge to quantum algorithms design and has only recently been achieved exactly and (quasi)-locally for an efficiently implementable Lindbladian by [CKG23]. The construction of [CKG23] provably leads to an efficient Gibbs state preparation method in the high-temperature regime. However, proving fast mixing for low temperatures remains an open problem, apart from some (almost) integrable systems. Here we introduce (i) a new continuous-time Lindbladian construction that also leads to quasi-local and detailed-balanced dynamics, and (ii) show that it is fast mixing for high-temperature lattice Hamiltonians. The new construction's major advantage is that it does not increase the number of Kraus operators, which is particularly helpful for numerical studies. We exploit the resulting low Kraus rank through a (iii) novel custom variant of density matrix renormalization group (DMRG) for superoperators to provide numerical evidence for various 1D models (Transverse-field Ising, Heisenberg XXZ) that the Gibbs sampler is mixing fast. We also introduce (iv) new detailed-balanced discrete-time quantum channel variants of all existing continuous-time detailed-balanced Lindbladian construction and (v) show that they are also mixing fast at high-temperatures, and provide some preliminary (vi) resource estimates for their implementation confirming their algorithmic efficiency.

In this work, we show that verifying the order of a finite group given as a black-box is in the complexity class QCMA. This solves an open problem asked by Watrous in 2000 in his seminal paper on quantum proofs and directly implies that the Group Non-Membership problem is also in the class QCMA, which further proves a conjecture proposed by Aaronson and Kuperberg in 2006. Our techniques also give improved quantum upper bounds on the complexity of many other group-theoretical problems, such as group isomorphism in black-box groups.

In their seminal work on quantum circuit complexity, Moore and Nilsson conjectured that unitaries of a deceptively simple form—controlled-unitary "staircases"—require circuits of minimum depth Ω(n). If true, this lower bound would answer a quantum-native analogue of the famous NC ≠ P conjecture. We settle the Moore–Nilsson conjecture in the negative by compressing all circuits in the class to depth O(log n), which is the best possible. The parallelization is exact, ancilla-free, and can be computed in poly(n) time. We also parallelize Moore–Nilsson circuits to the best-possible depth of O(√n) in circuits restricted to 2D connectivity. The main ingredient in these proofs is a blockwise precomputation technique that is in some sense a quantum analogue of the method introduced by Arlazarov, Dinic, Kronrod, and Faradzev in classical dynamic programming, sometimes called the "Four-Russians speedup." We also show that this quantum precomputation technique can be applied to more-general classes of circuits. As examples, we construct both exact and approximate parallelizations which give polynomial depth reductions for cascades of controlled log(n)-qubit unitaries.

The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive features of Zhandry's original compressed function oracle: the purification is a small list of input-output pairs which meaningfully reflect an algorithm's knowledge of the oracle. We then apply this framework to show that the seven-round balanced Feistel construction is a strong quantum PRP, resolving an open question of (Zhandry, 2012). We further re-prove essentially all known quantum query lower bounds in the random permutation model, notably the collision and preimage resistance of both Sponge and Davies-Meyer, hardness of double-sided zero search and sparse predicate search, and give new lower bounds for cycle finding and the one-more problem.

Understanding how fast physical systems can resemble Haar-random unitaries is a fundamental question in physics. Many experiments of interest in quantum gravity and many-body physics, including the butterfly effect in quantum information scrambling and the Hayden-Preskill thought experiment, involve queries to a random unitary~$U$ alongside its inverse~$U^\dagger$, conjugate~$U^*$, and transpose~$U^T$. However, conventional notions of approximate unitary designs and pseudorandom unitaries (PRUs) fail to capture these experiments. In this work, we introduce and construct strong unitary designs and strong PRUs that remain robust under all such queries. Our constructions achieve the optimal circuit depth of $\mathcal{O}(\log n)$ for systems of $n$ qubits. We further show that strong unitary designs can form in circuit depth $\mathcal{O}(\log^2 n)$ in circuits composed of independent two-qubit Haar-random gates, and that strong PRUs can form in circuit depth $\poly(\log n)$ in circuits with no ancilla qubits. Our results provide an operational proof of the fast scrambling conjecture from black hole physics: every observable feature of the fastest scrambling quantum systems reproduces Haar-random behavior at logarithmic times.

Bosonic statistics give rise to remarkable phenomena, from the Hong-Ou-Mandel effect to Bose-Einstein condensation, with applications spanning fundamental science to quantum technologies. Modelling bosonic systems relies heavily on effective descriptions: typically, truncating their infinite-dimensional state space or restricting their dynamics to a simple class of Hamiltonians, such as polynomials of canonical operators. However, many natural bosonic Hamiltonians do not belong to these simple classes, and some quantum effects harnessed by bosonic computers inherently require infinite-dimensional spaces. Can we trust results obtained with such simplifying assumptions to capture real effects? We solve this outstanding problem, showing that these effective descriptions do correctly capture the physics of bosonic systems. Our technical contributions are twofold: first, we prove that any physical bosonic unitary evolution can be accurately approximated by a finite-dimensional unitary evolution; second, we show that any finite-dimensional unitary evolution can be generated exactly by a bosonic Hamiltonian that is a polynomial of canonical operators. Beyond their fundamental significance, our results have implications for classical and quantum simulations of bosonic systems, provide universal methods for engineering bosonic quantum states and Hamiltonians, show that polynomial Hamiltonians generate universal gate sets for quantum computing over bosonic modes, and lead to a bosonic Solovay-Kitaev theorem.

Efficient simulation of a quantum system generally relies on structural properties of the quantum state. Motivated by the recent results by Bakshi et al. on the sudden death of entanglement in high-temperature Gibbs states of quantum spin systems, we study the high-temperature Gibbs states of bounded-degree local fermionic Hamiltonians, which include the special case of geometrically local fermionic systems. We prove that at a sufficiently high temperature that is independent of the system size, the Gibbs state is a probabilistic mixture of fermionic Gaussian states. This forms the basis of an efficient classical algorithm to prepare the Gibbs state by sampling from a distribution of fermionic Gaussian states. As a contrasting example, we show that high-temperature Gibbs states of the Sachdev-Ye-Kitaev (SYK) model are not convex mixtures of Gaussian states.

The problem of coherence distillation asks: given multiple copies of a coherent input state, produce a coherent output state with much less noise (that is, much closer to a pure coherent state), in such a way that the time evolution of the output state matches the time evolution of the input state. We thoroughly address this problem for the case of qubit states. Principally, we compute the distillation channel that is asymptotically optimal in the limit of a large number of input qubit states and compute the resulting infidelity (one minus fidelity) between the output qubit state and the desired pure state. We show that this infidelity is closely related to a resource known as purity of coherence, a quantity obtained from the Right Logarithmic Derivative (RLD) Fisher information metric. We thus demonstrate an operational meaning for purity of coherence as the quantity whose monotonicity on time-translation invariant channels sets the strongest asymptotic bound on the capability of coherence distillation for qubit states. For a special choice of input and output state, we additionally investigate a number of extensions of this primary result. In particular, we present numerical schemes to produce the exact optimal distillation protocol for a fixed value of $N$, extend the computation of the optimal protocol and the minimum infidelity to the $1/N^2$ and $1/N^3$ orders, estimate the amount of purity of coherence that is dissipated by the optimal distillation protocol, and compute the mathematical behavior of the protocol more precisely in the low-noise and high-noise limits.

In the last years, Regev's reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of the decoding problem. Following this line of work, the authors of [JSW+24] have recently come up with a quantum algorithm called ``decoded quantum interferometry'' that is able to solve in polynomial time several optimization problems. They study in particular the Optimal Polynomial Interpolation (OPI) problem, which can be seen as a decoding problem on Reed-Solomon codes. In this work, we provide strong improvements for some instantiations of the OPI problem. The most notable improvements are for the ISIS_\infty problem (originating from lattice-based cryptography) on Reed-Solomon codes but we also study different constraints for OPI. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. Our proof techniques involve the use of a soft decoder for Reed-Solomon codes, namely the decoding algorithm from Koetter and Vardy. In order to be able to use this decoder in the setting of Regev's reduction, we provide a novel generic reduction from a syndrome decoding problem to a coset sampling problem, providing a powerful and simple to use theorem, which generalizes previous work and is of independent interest. We also provide an extensive study of OPI using the Koetter and Vardy algorithm.

We continue the line of work initiated by Kalai et al. (STOC '23), studying "compiled" nonlocal games played between a classical verifier and a single quantum prover, with cryptography simulating the spatial separation between the players. The central open question in this area is to understand the soundness of this compiler against quantum strategies, and apart from results for specific games, all that is known is the recent "qualitative" result of Kulpe et al. (STOC '25) showing that the success probability of a quantum prover in the compiled game is bounded by the game's quantum commuting-operator value in the limit as the cryptographic security parameter goes to infinity. In this work, we make progress towards a quantitative understanding of quantum soundness for general games, by giving a concrete framework to bound the quantum value of compiled nonlocal games. Building on the result of Kulpe et al. together with the notion of "nice" sum-of-squares certificates, introduced by Natarajan and Zhang (FOCS '23) to bound the value of the compiled CHSH game, we extend the niceness framework and construct a hierarchy of semidefinite programs that searches exclusively over nice certificates. We show that this hierarchy converges to the optimal quantum value of the game. Additionally, we present a transformation to make any degree-1 sum-of-squares certificate nice. This approach provides a systematic method to reproduce all known bounds for special classes of games together with Kulpe et al.'s bound for general games from the same framework.

The Sherrington-Kirkpatrick (SK) model serves as a foundational framework for understanding disordered systems. The Quantum Approximate Optimization Algorithm (QAOA) is a quantum optimization algorithm whose performance monotonically improves with its depth $p$. In this work, we introduce a new equivalence between the task of evaluating the energy of QAOA applied to the SK model in the infinite-size limit and the task of simulating a spin-boson system, which we show can be done with modest cost using matrix product states. Using this equivalence, we optimize QAOA parameters and provide numerical evidence that QAOA obtains a $(1-\epsilon)$ approximation to the optimal energy with circuit depth $\mathcal{O}(n/\epsilon^{\infiniteSizeLimitOneOverEta})$ in the average case, with $\varepsilon\lesssim\infiniteSizeLastpError\%$ at $p=\infiniteSizeLastp$. We then use these optimized QAOA parameters to evaluate the QAOA energy for finite-sized instances with up to $30$ qubits and find convergence to the ground state consistent with the infinite-size limit prediction. Our results provide strong numerical evidence that QAOA can efficiently approximate the ground state of the SK model in the average case.

Many fundamental quantities in quantum information processing are instances of quantum divergences - functionals on quantum states that satisfy natural axioms grounded in information-theoretic principles. Recently, a new class of divergences - the f-divergences - has gained prominence in quantum information theory and received operational interpretations, while being long established in the classical setting. Furthermore, Frenkel showed that the Umegaki relative entropy is a special case of a quantum f-divergence for the function f(x) = x log x; building on this, Hirche et al. introduced a parameterized family of f-divergences that, in appropriate regimes, recovers the sandwiched and Petz relative entropies as regularizations. Taken together, these results reveal a tight link between the best-understood quantum divergences - the Umegaki, Petz, and sandwiched relative entropies - on a technical level and the general class of f-divergences, thereby strongly motivating a program that connects f-divergences to concrete quantum information tasks as already started by Cheng et al. In this contribution, we develop a variational formulation that approximates general quantum f-divergences to arbitrary precision. These approximations yield (i) efficient evaluation of the quantum relative entropy of channels and already used as the core numerical method in quantum many body physics and (ii) computation of asymptotic key rates in DIQKD in particular in the scenario of two switches in routed Bell scenarios.

Understanding quantum phases of matter is a fundamental goal in physics. For pure states, the representatives of phases are the ground states of locally interacting Hamiltonians, which are also renormalization fixed points (RFPs). These RFP states are exactly described by tensor networks. Extending this framework to mixed states, matrix product density operators (MPDOs) which are RFPs are believed to encapsulate mixed-state phases of matter in one dimension, where non-trivial topological phases have already been shown to exist. However, to better motivate the physical relevance of those states, and in particular the physical relevance of the recently found non-trivial phases, it remains an open question whether such MPDO RFPs can be realized as steady states of local Lindbladians. In this work, we resolve this question by analytically constructing parent Lindbladians for MPDO RFPs. These Lindbladians are local, frustration-free, and exhibit minimal steady-state degeneracy. Interestingly, we find that parent Lindbladians possess a rich structure that distinguishes them from their Hamiltonian counterparts. In particular, we uncover an intriguing connection between the non-commutativity of the Lindbladian terms and the fact that the corresponding MPDO RFP belongs to a non-trivial phase.

Compiling Bell games under cryptographic assumptions replaces the need for physical separation, allowing nonlocality to be probed with a single untrusted device. While Kalai et al. (STOC'23) showed that this compilation preserves quantum advantages, its quantitative quantum soundness has remained an open problem. We address this gap with two primary contributions. First, we establish the first quantitative quantum soundness bounds for every bipartite compiled Bell game whose optimal quantum strategy is finite-dimensional: any polynomial-time prover's score in the compiled game is negligibly close to the game's ideal quantum value. More generally, for all bipartite games we show that the compiled score cannot significantly exceed the bounds given by a newly formalized convergent sequential Navascués-Pironio-Acín (NPA) hierarchy. Second, we provide a full characterization of this sequential NPA hierarchy, establishing it as a robust numerical tool that is of independent interest. Finally, for games without finite-dimensional optimal strategies, we explore the necessity of NPA approximation error for quantitatively bounding their compiled scores, linking these considerations to the complexity conjecture $\mathrm{MIP}^{\mathrm{co}}=\mathrm{coRE}$ and open challenges such as quantum homomorphic encryption correctness for "weakly commuting" quantum registers.

Non-local games are a powerful tool to distinguish between correlations possible in classical and quantum worlds. Kalai et al. (STOC'23) proposed a compiler that converts multipartite non-local games into interactive protocols with a single prover, relying on cryptographic tools to remove the assumption of physical separation of the players. While quantum completeness and classical soundness of the construction have been established for all multipartite games, quantum soundness is known only in the special case of bipartite games. In this paper, we prove that the Kalai \emph{et al.}'s compiler indeed achieves quantum soundness for all multipartite compiled non-local games, by showing that any correlations that can be generated in the asymptotic case correspond to quantum commuting strategies. Our proof uses techniques from the theory of operator algebras, and relies on a characterisation of sequential operationally no-signalling strategies as quantum commuting operator strategies in the multipartite case, thereby generalising several previous results. On the way, we construct universal C*-algebras of sequential PVMs and prove a new chain rule for Radon-Nikodym derivatives of completely positive maps on C*-algebras which may be of independent interest.

Our capacity to process information depends on the computational power at our disposal. Information theory captures our ability to distinguish states or communicate messages when it is unconstrained with unrivaled beauty and elegance. For computationally bounded observers the situation is quite different -- they can, for example, be fooled to believe that distributions are more random than they actually are. Existing mathematical approaches in computational information theory largely follow the single-shot paradigm that, while being operationally meaningful, also gives complicated statements and is difficult to build intuition for. In our work, we take a new direction in computational quantum information theory that captures the essence of complexity-constrained information theory while retaining the look and feel of the unbounded asymptotic theory. As our foundational quantity, we define the computational relative entropy as the optimal error exponent in asymmetric hypothesis testing when restricted to polynomially many copies and quantum gates, defined in a mathematically rigorous way. Building on this foundation, we prove a computational analogue of Stein's lemma, establish computational versions of fundamental inequalities like Pinsker's bound, and demonstrate a computational smoothing property showing that computationally indistinguishable states yield equivalent information measures. We derive a computational entropy that operationally characterizes optimal compression rates for quantum states under computational limitations and show that our quantities apply to computational entanglement theory, proving a computational version of the Rains bound. Our framework reveals striking separations between computational and unbounded information measures, including quantum-classical gaps that arise from cryptographic assumptions, demonstrating that computational constraints fundamentally alter the information-theoretic landscape and open new research directions at the intersection of quantum information, complexity theory, and cryptography.

The precise quantification of the limits to manipulating quantum resources lies at the core of quantum information theory. However, standard information-theoretic analyses do not consider the actual computational complexity involved in performing certain tasks. Here, we address this issue within the realm of entanglement theory, finding that accounting for computational efficiency substantially changes what can be achieved using entangled resources. We consider two key figures of merit: the computational distillable entanglement and the computational entanglement cost. These measures quantify the optimal rates of entangled bits that can be extracted from or used to dilute many identical copies of n-qubit bipartite pure states, using computationally efficient local operations and classical communication. We demonstrate that computational entanglement measures diverge significantly from their information-theoretic counterparts. While the information-theoretic distillable entanglement is determined by the von Neumann entropy of the reduced state, we show that the min-entropy governs the computationally efficient setting. On the other hand, computationally efficient entanglement dilution requires maximal consumption of entangled bits, even for nearly unentangled states. Furthermore, in the worst-case scenario, even when an efficient description of the state exists and is fully known, one gains no advantage over state-agnostic protocols. Our findings establish sample-complexity bounds for measuring and testing the von Neumann entropy, fundamental limitations on efficient state compression, and efficient local tomography protocols.

We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm that utilizes coherent Bell measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian optimization to classical decoding. For a signed Pauli Hamiltonian $H$ and any degree-$\ell$ polynomial $\calP$, HDQI prepares a purification of the density matrix $$\rho_\calP(H) = \calP^2(H)/\Tr[\calP^2(H)]$$ by solving a combination of two tasks: decoding $\ell$ errors on a classical code defined by $H$, and preparing a pilot state that encodes the anti-commutation structure of $H$. Choosing $\calP(x)$ to approximate $\exp(-\beta x/2)$ yields Gibbs states at inverse temperature $\beta$; other choices of $\calP$ prepare approximate ground states, microcanonical ensembles, and other spectral filters. The decoding problem inherits structural properties of $H$; in particular, local Hamiltonians map to LDPC codes. Preparing the pilot state is always efficient for commuting Hamiltonians, but highly non-trivial for non-commuting Hamiltonians. Nevertheless, we prove that this state admits an efficient matrix product state representation for a class of nearly commuting Pauli Hamiltonians whose anti-commutation graph decomposes into connected components of logarithmic size. We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians -- including the toric code, color code, and Haah's cubic code -- but also develop a matching efficient classical algorithm for this task, thereby delineating the boundary of efficient classical simulation. For a non-commuting semiclassical spin glass and commuting stabilizer code Hamiltonians with quantum defects, HDQI provably prepares Gibbs states up to a constant inverse-temperature threshold using polynomial quantum resources and quasi-polynomial classical preprocessing. These results position HDQI as a versatile new algorithmic primitive, connecting quantum state preparation to classical decoding.

Compiled nonlocal games transfer the power of Bell-type multi-prover tests into a single-device setting by replacing spatial separation with cryptography. Concretely, the KLVY compiler (STOC'23) maps any multi-prover game to an interactive single-prover protocol, using quantum homomorphic encryption. A crucial security property of such compilers is quantum soundness, which ensures a dishonest quantum prover cannot exceed the original game's quantum value. For practical cryptographic implementations, this soundness must be quantitative, providing concrete bounds, rather than merely asymptotic. While quantitative quantum soundness has been established for the KLVY compiler in the bipartite case, it has only been shown asymptotically for multipartite games. This is a significant gap, as multipartite nonlocality exhibits phenomena with no bipartite analogue, and the difficulty of enforcing space-like separation makes single-device compilation especially compelling. This work closes this gap by showing the quantitative quantum soundness of the KLVY compiler for all multipartite nonlocal games. On the way, we introduce an NPA-like hierarchy for quantum instruments and prove its completeness, thereby characterizing correlations from non-signaling sequential strategies. We further develop novel geometric arguments for the decomposition of sequential strategies into their signaling and non-signaling parts, which might be of independent interest.

Quantum information theory, particularly its entropic formulations, has made remarkable strides in characterizing quantum systems and tasks. However, a critical dimension remains underexplored: computational efficiency. While classical computational entropies integrate complexity and feasibility into information measures, analogous concepts have yet to be rigorously developed in the quantum setting. In this joint submission, we advance a quantum computational information theory through two complementary works. The first introduces the quantum computational unpredictability entropy, a natural generalization of the min entropy for classical-quantum states and of the classical unpredictability entropy that quantifies the guessing probability of classical randomness using quantum side information and bounded computational power. The second work extends this to the fully quantum setting by defining fully quantum computational min- and max-entropies. The computational min-entropy generalizes unpredictability entropy and retains essential properties, including data processing, a fully quantum leakage chain rule, and it satisfies a novel purification chain rule. The computational max-entropy is defined via a canonical duality relation and it captures a notion of efficient entanglement distillation under bounded quantum circuits. With the introduction of these computational entropies and their analysis, this work marks a critical step toward a quantum information theory that incorporates computational elements.

The Markov property entails the conditional independence structure inherent in Gibbs distributions for general classical Hamiltonians, a feature that plays a crucial role in inference, mixing time analysis, and algorithm design. However, much less is known about quantum Gibbs states. In this work, we show that for any Hamiltonian with a bounded interaction degree (e.g., D-dimensional lattices), the quantum Gibbs state is locally Markov at arbitrary temperature, meaning there exists a quasi-local recovery map for every local region. Notably, this recovery map is obtained by applying a detailed-balanced Lindbladian with jumps acting on the region. Consequently, we prove that (i) the conditional mutual information (CMI) for a shielded small region decays exponentially with the shielding distance, and (ii) under the assumption of uniform clustering of correlations, Gibbs states of general non-commuting Hamiltonians on $D$-dimensional lattices can be prepared by a quantum circuit of depth $\e^{\mathcal{O}(\log^D(n/\epsilon))}$. Our proofs introduce a regularization scheme for imaginary-time-evolved operators at arbitrarily low temperatures and reveal a connection between the Dirichlet form, a dynamic quantity, and the commutator in the KMS inner product, a static quantity. We believe these tools pave the way for tackling further challenges in quantum thermodynamics and mixing times, particularly in low-temperature regimes.

How could quantum cryptography help us achieve what are not achievable in classical cryptography? In this work we study the classical cryptographic problem that two parties would like to perform secure computations with long outputs. As a basic primitive and example, we first consider the following problem which we call secure function sampling with long outputs: suppose $f:\{0,1\}^n\rightarrow \{0,1\}^m$ is a public, efficient classical function, where $m$ is big; Alice would like to sample $x$ from its domain and sends $f(x)$ to Bob; what Bob knows should be no more than $f(x)$ even if it behaves maliciously. Classical cryptography, like FHE and succinct arguments [Gen09,Kil92,HW15], allows us to achieve this task within communication complexity $O(n+m)$; could we achieve this task with communication complexity independent of $m$? In this work, we first design a quantum cryptographic protocol that achieves secure function sampling with approximate security, within $O(n)$ communication (omitting the dependency on the security parameter and error tolerance). We also prove the classical impossibility using techniques in [HW15], which means that our protocol indeed achieves a type of quantum advantage. Building on the secure function sampling protocol, we further construct protocols for general secure two-party computations [Yao86,GB01] with approximate security, with communication complexity only depending on the input length and the targeted security. In terms of the assumptions, we construct protocols for these problems assuming only the existence of collapsing hash functions [Unr16]; what's more, we also construct a classical-channel protocol for these problems additionally assuming the existence of noisy trapdoor claw-free functions [BCMVV,BKVV].

In a variety of physically relevant settings for learning from quantum data, there is an established recipe for measuring polynomially many copies of that data such that the resulting measurement readouts contain enough information to reconstruct the underlying system. Yet designing protocols that can computationally efficiently extract that information remains largely an art, and there are important cases where we believe this to be impossible, that is, where there is an information-computation gap. While there is a large array of tools in the classical literature for giving evidence for average-case hardness of statistical inference problems, the corresponding tools in the quantum literature are far more limited. One such framework in the classical literature, the low-degree method, makes predictions about hardness of inference problems based on the failure of estimators given by low-degree polynomials. In this work, we extend this framework to the quantum setting and show a number of new information-computation gaps for quantum learning. We establish a general connection between state designs and low-degree hardness. We use this to obtain the first information-computation gaps for learning Gibbs states of random, sparse, non-local Hamiltonians. We also use it to prove hardness for learning random shallow quantum circuit states in a challenging model where states can be measured in adaptively chosen bases. To our knowledge, the ability to model adaptivity within the low-degree framework was open even in classical settings. In addition, we also obtain a low-degree hardness result for quantum error mitigation against strategies with single-qubit measurements. We define a new quantum generalization of the planted biclique problem and identify the threshold at which this problem becomes computationally hard for protocols that perform local measurements. Interestingly, the complexity landscape for this problem shifts when going from local measurements to more entangled single-copy measurements. We show average-case hardness for the ``standard'' variant of Learning Stabilizers with Noise and for agnostically learning product states.

We present a quantum algorithm for simulating the time evolution generated by any bounded, time-dependent operator $-A$ with non-positive logarithmic norm, thereby serving as a natural generalization of the Hamiltonian simulation problem. Our method generalizes the recent Linear-Combination-of-Hamiltonian-Simulation (LCHS) framework. In instances where $A$ is time-independent, we provide a block-encoding of the evolution operator $e^{-At}$ with $\mathcal{O}\big(t\log\frac{1}{\epsilon})$ queries to the block-encoding oracle for $A$. We also show how the normalized evolved state can be prepared with $\mathcal{O}(1/\|e^{-At}\ket{\vec{u}_0}\|)$ queries to the oracle that prepares the normalized initial state $\ket{\vec{u}_0}$. These complexities are optimal in all parameters and improve the error scaling over prior results. Furthermore, we show that any improvement of our approach exceeding a constant factor of approximately 3 is infeasible. For general time-dependent operators $A$, we also prove that a uniform trapezoidal rule on our LCHS construction yields exponential convergence, leading to simplified quantum circuits with improved gate complexity compared to prior nonuniform-quadrature methods.

Magic state distillation enables universal fault-tolerant quantum computation by implementing non-Clifford gates via the preparation of high-fidelity magic states. However, it comes at the cost of substantial logical-level overhead in both space and time. In this work, we propose a very low-cost magic state distillation scheme for biased-noise qubits. By leveraging the noise bias, our scheme enables the preparation of a magic state with a logical error rate of 3×10^(−7), using only 53 qubits and 5.5 error correction rounds, under a noise bias of η ≳ 5×10^6 and a phase-flip noise rate of 0.1%. This reduces the circuit volume by more than one order of magnitude relative to magic state cultivation for unbiased-noise qubits and by more than two orders of magnitude relative to standard magic state distillation. Moreover, our scheme provides three key advantages over previous proposals for biased-noise qubits. First, it only requires nearest-neighbor two-qubit gates on a 2D lattice. Second, the logical fidelity remains nearly identical even at a more modest noise bias of η ≳ 80, at the cost of a slightly increased circuit volume. Third, the scheme remains effective even at high physical phase-flip rates, in contrast to previously proposed approaches whose circuit volume grows exponentially with the error rate. Our construction is based on unfolding the X stabilizer group of the Hadamard 3D quantum Reed-Muller code in 2D, enabling distillation at the physical level rather than the logical level, and is therefore referred to as unfolded distillation.

We give a meta-complexity characterization of EFI pairs, which are considered the “minimal” primitive in quantum cryptography (due to their equivalence to quantum commitments and for being implied by almost all other known quantum cryptographic primitives). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy. The complexity measure that we consider is a smoothed version of the algorithmic entropy notion introduced by Gács [Gác01]. A key technical step in our proof, which may be of independent interest, is to show that the existence of EFI pairs is equivalent to the existence of non-uniform single-copy secure pseudorandom state generators (nu 1-PRS). As a corollary, we get an alternative, arguably simpler, construction of a universal EFI pair.

Discrete and continuous variables oftentimes require different treatments in many learning tasks. Identifying the Hamiltonian governing the evolution of a quantum system is a fundamental task in quantum learning theory. While previous works mostly focused on quantum spin systems, where quantum states can be seen as superpositions of discrete bit-strings, relatively little is known about Hamiltonian learning for continuous-variable quantum systems. In this work we focus on learning the Hamiltonian of a bosonic quantum system, a common type of continuous-variable quantum system. This learning task involves an infinite-dimensional Hilbert space and unbounded operators, making mathematically rigorous treatments challenging. We introduce an analytic framework to study the effects of strong dissipation in such systems, enabling a rigorous analysis of cat qubit stabilization via engineered dissipation. This framework also supports the development of Heisenberg-limited algorithms for learning general bosonic Hamiltonians with higher-order terms of the creation and annihilation operators. Notably, our scheme requires a total Hamiltonian evolution time that scales only logarithmically with the number of modes and inversely with the precision of the reconstructed coefficients. On a theoretical level, we derive a new quantitative adiabatic approximation estimate for general Lindbladian evolutions with unbounded generators. Finally, we discuss possible experimental implementations.

We investigate layer codes, a family of three-dimensional stabilizer codes that can achieve optimal scaling of code parameters and a polynomial energy barrier, as candidates for self-correcting quantum memories. First, we introduce two decoding algorithms for layer codes with provable guarantees for local stochastic and adversarial noise, respectively. We then prove that layer codes are partially self-correcting quantum memories. With memory times scaling exponentially in the linear size of the system, layer codes outperform the previously demonstrated subexponential scaling of the welded solid code. Notably, we argue that partial self-correction without the requirement of efficient decoding is more common than expected, as it arises from a diverging energy barrier. This draws a sharp distinction between partially self-correcting systems, and partially self-correcting memories. Another novel aspect of our work is an analysis of layer codes constructed from random Calderbank–Shor–Steane codes. We show that these random layer codes have optimal scaling (up to logarithmic corrections) of code parameters and a polynomial energy barrier. Finally, we present numerical studies of their memory times and report behavior consistent with partial self-correction.

The efficient implementation of matrix arithmetic operations underpins the speedups of many quantum algorithms. We present a suite of methods to do matrix arithmetics---with the result encoded in the off-diagonal blocks of a Hamiltonian---using Hamiltonian evolutions of input operators. We show how to maintain this Hamiltonian block encoding, so that matrix operations can be composed one after another, and the entire computation takes $\leq 2$ ancilla qubits. We achieve this for matrix multiplication, matrix addition, matrix inversion, Hermitian conjugation, fractional scaling, integer scaling, complex phase scaling, as well as singular value transformation for both odd and even polynomials. We also develop an overlap estimation algorithm to extract classical properties of Hamiltonian block encoded operators, analogous to the well known Hadmard test, at no extra cost of qubit. Our Hamiltonian matrix multiplication uses the Lie group commutator product formula and its higher-order generalizations due to Childs and Wiebe. Our Hamiltonian singular value transformation employs a dominated polynomial approximation, wherein the approximation holds over the domain of interest, while the polynomial is upper bounded by the target function on the entire unit interval. When applied to quantum simulation, our methods inherit the commutator scaling of product formulas, while leveraging the power of matrix arithmetics to reduce the cost of each step. To illustrate this feature, we present a circuit for simulating a class of sum-of-squares Hamiltonians, covering systems studied recently in quantum chemistry. Our simulation attains a commutator scaling in step count, while the gate cost per step remains comparable to that of more advanced algorithms. We achieve this with $1$ ancilla qubit.

Random classical linear codes are widely believed to be hard to decode, exponentially so at constant coding rate. If the rate vanishes asymptotically sufficiently rapidly, slightly sub-exponential decoding algorithms are known. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate—the maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any coding rate, would immediately imply a breakthrough in cryptography. More generally, we also characterize many other complexity-theoretic properties of stabilizer codes. While classical decoding admits a random self-reduction, we prove significant barriers for the existence of random self-reductions in the quantum case. This result follows from new bounds on Clifford entropies and Pauli mixing times, which may be of independent interest. As a complementary result, we demonstrate various other self-reductions which are in fact achievable, such as between search and decision. Our work also demonstrates several ways in which quantum phenomena, such as quantum degeneracy, force several reasonable definitions of stabilizer decoding—all of which are classically identical—to have distinct or non-trivially equivalent complexity.

We ask how quantum correlations can be distributed among many subsystems. To address this, we define entanglement sharing schemes (ESS) where certain pairs of subsystems allow entanglement to be recovered via local operations, while other pairs must not. ESS schemes come in two variants, one where the partner system with which entanglement should be prepared is known, and one where it is not. In the case of known partners, we fully characterize the access structures realizable for ESS when using stabilizer states, and construct efficient schemes for threshold access structures, and give a conjecture for the access structures realizable with general states. In the unknown partner case, we again give a complete characterization in the stabilizer setting, additionally give a complete characterization of the case where there are no restrictions on unauthorized pairs, and we prove a set of necessary conditions on general schemes which we conjecture are also sufficient. Finally, we give an application of the theory of entanglement sharing to resolve an open problem related to the distribution of entanglement in response to time sensitive requests in quantum networks.

Quantum computing and quantum sensing represent two distinct frontiers of quantum information science. In this work, we harness quantum computing to solve a fundamental and practically important sensing problem: the detection of weak oscillating fields with unknown strength and frequency. We present a quantum computing enhanced sensing protocol that outperforms all existing approaches. Furthermore, we prove our approach is optimal by establishing the Grover-Heisenberg limit — a fundamental lower bound on the minimum sensing time. The key idea is to robustly digitize the continuous, analog signal into a discrete operation, which is then integrated into a quantum algorithm. Our metrological gain originates from quantum computation, distinguishing our protocol from conventional sensing approaches. Indeed, we prove that broad classes of protocols based on quantum Fisher information, finite-lifetime quantum memory, or classical signal processing are strictly less powerful. Our protocol is compatible with multiple experimental platforms. We propose and analyze a proof-of-principle experiment using nitrogen-vacancy centers, where meaningful improvements are achievable using current technology. This work establishes quantum computation as a powerful new resource for advancing sensing capabilities.

We present sum-of-squares spectral amplification (SOSSA), a framework for improving quantum simulation relevant to low-energy problems. We show how SOSSA can be applied to problems like energy and phase estimation and provide fast quantum algorithms for these problems that significantly improve over prior art. We analyze the performance of SOSSA on the Sachdev-Ye-Kitaev model, a representative strongly correlated system, and demonstrate asymptotic speedups over generic simulation methods by a factor of the square root of the system size. We then apply SOSSA to electronic structure problems in quantum chemistry, yielding a factor of 4 to 195 speedup over the state of the art in ground-state energy estimation for models of Iron-Sulfur complexes and a CO2-fixation catalyst.

The field of quantum learning theory has advanced rapidly in recent years, at the intersection of quantum information science, statistical learning, and computational complexity. A key task in this area is quantum process tomography, which seeks to learn unitary transformations of quantum states efficiently. Efficient process tomography would be highly valuable: for instance, learning an unknown natural process could enable its efficient implementation and simulation on a quantum computer. However, learning arbitrary unitary operators is generally prohibitively expensive, with several sample- and time-complexity lower bounds showing the task is intractable. Thus, work typically focuses on more structured classes of operators when computational efficiency is desired. Two especially important such classes are bosonic and fermionic Gaussian unitaries. These operators have compact parametrizations, rich algebraic structure, and enough expressiveness to capture many relevant physical processes. As a result, they are ubiquitous in quantum information theory. In this work, we advance the learning theory of bosonic and fermionic unitaries in two ways: (1) We give the first time-efficient algorithm to learn bosonic Gaussian unitaries. The complexity of the algorithm scales polynomially in the number of modes, a total photon number bound (which is critical in defining an energy-constrained distance measure), and a squeezing parameter which captures how much the operator increases the mean energy of a vacuum state. (2) We give a first-of-its-kind algorithm to learn fermionic unitaries prepared with at most t non-Gaussian gates. Our algorithm scales polynomially in the number of modes and exponentially in t, and we argue that this scaling is optimal up to polynomial factors. Both algorithms produce an output whose distance to the input unitary is small in the worst-case (diamond) distance. Our results are organized into two separate manuscripts: one is arXiv:2504.11318 (Mildly-Interacting Fermionic Unitaries are Efficiently Learnable), and the other will be released on arXiv within a month (Efficient Learning of Bosonic Gaussian Unitary Channels).

We show a relation between quantum learning theory and algorithmic hardness. We demonstrate that finding near-ground states of certain sparse disordered quantum systems is average-case hard for Lipschitz quantum algorithms if there exists an efficient, local learning algorithm---such as the classical shadows algorithm---for estimating the energy of a state of the system. A corollary of our result is that many standard quantum algorithms fail to find near-ground states of these systems, including short-time Lindbladian dynamics, short-time quantum annealing, phase estimation, and shallow-depth variational quantum algorithms. Our results are unconditional. To achieve this, we introduce a topological property of quantum systems that we call the quantum overlap gap property (QOGP). This property is only satisfied by systems with an efficient local learning algorithm for the energy. We prove that systems which exhibit this topological property in their low-energy space are intractable for quantum algorithms whose outputs are stable under perturbations to their inputs. We then prove that the QOGP is satisfied for a sparsified variant of the quantum p-spin model, giving the first known algorithmic hardness-of-approximation result for quantum algorithms in finding the ground state of a non-stoquastic, noncommuting quantum system. Our resulting lower bound for quantum algorithms optimizing this model using Lindbladian evolution matches (up to constant factors) the best-known time lower bound for classical Langevin dynamics optimizing classical p-spin models. For this reason we suspect that finding ground states of typical quantum p-spin models using quantum algorithms is, in practice, as intractable as the classical p-spin model is for classical algorithms. Inversely, we show that the Sachdev--Ye--Kitaev (SYK) model does not exhibit the QOGP, consistent with previous evidence that the model is rapidly mixing at low temperatures.

In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A ``trivial'' PoQ is to simply assume an average-case hard problem for classical computers that is easy for quantum computers. However, there is much interest in ``non-trivial'' PoQ that actually rely on quantum hardness assumptions, as these are often a starting point for more sophisticated protocols such as classical verification of quantum computation (CVQC). We show several lower-bounds for the hardness required to achieve non-trivial PoQ, in particular showing that they likely require cryptographic hardness, with different types of cryptographic hardness being required for different variations of non-trivial PoQ. In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ and its various extensions such as CVQC.

The development of quantum codes with good error correction parameters and useful sets of transversal gates is an area of major interest in quantum error correction. Abundant prior works have studied transversal gates which are restricted to acting on all logical qubits simultaneously. In this work, we study codes that support transversal gates which induce addressable logical gates, i.e., the logical gates act only on logical qubits of our choice. As we consider scaling from low-rate to high-rate codes, the study and design of low-overhead, addressable logical operations presents an important problem for both theoretical and practical purposes. In this work, we construct the first quantum codes to support transversally addressable non-Clifford gates. Concretely, given any three logical qubits across one or multiple codeblocks, one can execute the logical CCZ on those qubits via a depth-one physical circuit of CCZ gates. We present a simple, explicit construction based on Reed-Solomon codes that is nearly asymptotically good, and a more involved, asymptotically good construction based on transitive, iso-orthogonal algebraic geometry codes. We go on to develop a powerful theory of quantum codes supporting a rich class of transversally addressable gates in the Clifford hierarchy, going far beyond just the CCZ gate. We call this framework addressable orthogonality, and show that it can be used to construct asymptotically good quantum codes supporting an arbitrary product of multiply-controlled Z gates transversally and addressably, enabling major adaptivity to particular algorithms. Our constructions mark the first quantum codes to support any multi-qubit gate transversally and addressably. Accordingly, our results have major implications for the general addressabilitiy problem in error correction. This is a merged submission based on arXiv:2502.01864 and arXiv:2507.05392.

Prior work of Beverland et al. has shown that any exact Clifford+T implementation of the n-qubit Toffoli gate must use at least n T gates. Here we show how to get away with exponentially fewer T gates, at the cost of incurring a tiny 1/poly(n) error that can be neglected in most practical situations. More precisely, the n-qubit Toffoli gate can be implemented to within error ϵ in the diamond distance by a randomly chosen Clifford+T circuit with at most O(log(1/ϵ)) T gates. We also give a matching Ω(log(1/ϵ)) lower bound that establishes optimality, and we show that any purely unitary implementation achieving even constant error must use Ω(n) T gates. We also extend our sampling technique to implement other Boolean functions. Finally, we describe upper and lower bounds on the T-count of Boolean functions in terms of non-adaptive parity decision tree complexity and its randomized analogue.

A fundamental task in quantum information science is \emph{state certification}: testing whether a lab-prepared $n$-qubit state is close to a given hypothesis state. In this work, we show that \emph{every} pure hypothesis state can be certified using only $O(n^2)$ single-qubit measurements applied to $O(n)$ copies of the lab state. Prior to our work, it was not known whether even subexponentially many single-qubit measurements could suffice to certify arbitrary states. This resolves the main open question of Huang, Preskill, and Soleimanifar (FOCS 2024, QIP 2024). Our algorithm also showcases the power of \emph{adaptive measurements}: within each copy of the lab state, previous measurement outcomes dictate how subsequent qubit measurements are made. We show that the adaptivity is necessary, by proving an exponential lower bound on the number of copies needed for any nonadaptive single-qubit measurement algorithm.

The nonlinear Fourier transform (NLFT) extends the classical Fourier transform by replacing addition with matrix multiplication. While the NLFT on $\mathrm{SU}(1,1)$ has been widely studied, its $\mathrm{SU}(2)$ variant has only recently attracted attention due to emerging applications in quantum signal processing (QSP) and quantum singular value transformation (QSVT). In this paper, we investigate the inverse NLFT on $\mathrm{SU}(2)$ and establish the numerical stability of the layer stripping algorithm for the first time under suitable conditions. Furthermore, we develop a fast and numerically stable algorithm, called inverse nonlinear fast Fourier transform, for performing inverse NLFT with near-linear complexity. This algorithm is applicable to computing phase factors for both QSP and the generalized QSP (GQSP).

We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. As a corollary, there is a boolean constraint system (BCS) nonlocal game for which the value of the Navascués, Pironio, and Acín (NPA) hierarchy does not attain the commuting operator value at any finite level. Our contribution involves establishing a computable mapping from Turing machines to BCS nonlocal games in which the halting property of the machine is encoded as a decision problem for the commuting operator value of the game. Our techniques are algebraic and distinct from those used to establish MIP*=RE. As a first step, we construct a mapping from Turing machines to elements of the tensor product of free algebras, showing that deciding positivity of those elements is coRE-hard. As a second step, we extend this mapping to further realize these elements as game polynomials for BCS games.

We show for the first time that uncloneable encryption exists with no computational assumptions, with security inverse-polynomial in the security parameter. We use properties of a monogamy-of-entanglement game associated with the Haar measure encryption to guarantee that any state that succeeds with high probability cannot be close to maximally-entangled between the referee and either of the players, whence we can apply the decoupling principle to show that either player becomes completely uncorrelated, and therefore cannot win significantly better than random guessing.

When designing quantum circuits for a given unitary, it can be much cheaper to achieve a good approximation on most inputs than on all inputs. In this work we formalize this idea, and propose that such "optimistic quantum circuits" are often sufficient in the context of larger quantum algorithms. For the rare algorithm in which a subroutine needs to be a good approximation on all inputs, we provide a reduction which transforms optimistic circuits into general ones. Applying these ideas, we build an optimistic circuit for the in-place quantum Fourier transform (QFT). Our circuit has depth O(log(n/ϵ)) for tunable error parameter ϵ, uses n total qubits, i.e. no ancillas, is local for input qubits arranged in 1D, and is measurement-free. The circuit's error is bounded by ϵ on all input states except an ϵ-sized fraction of the Hilbert space. The circuit is also rather simple and thus may be practically useful. Combined with recent QFT-based fast arithmetic constructions, the optimistic QFT yields factoring circuits of nearly linear depth using only 2n + O(n/log n) total qubits. Additionally, we apply our reduction technique to yield an approximate QFT with well-controlled error on all inputs; it is the first to achieve the asymptotically optimal depth of O(log (n/ϵ)) with a sublinear number of ancilla qubits. The reduction uses long-range gates but no measurements.

Quantum cryptographic definitions are often sensitive to the number of copies of the cryptographic states received by adversary. Making definitional changes to the number of copies accessible to an adversary can drastically affect various aspects including the computational hardness, feasibility, and applicability of the resulting cryptographic scheme. This phenomenon appears in many places in quantum cryptography, including the notions quantum pseudorandomness and unclonable cryptography. To address this, we present a generic approach to boost single-copy security to multi-copy security and apply this approach to many settings. As a consequence, we obtain the following new results: • One-copy stretch pseudorandom state generators (under mild assumptions) imply the existence of t-copy stretch pseudorandom state generators, for any fixed polynomial t. • One-query pseudorandom unitaries with short keys (under mild assumptions) imply the existence of t-query pseudorandom unitaries with short keys, for any fixed polynomial t. • Assuming indistinguishability obfuscation and other standard cryptographic assumptions, there exist identical-copy secure unclonable primitives such as publickey quantum money and quantum copy-protection.

We introduce the \emph{magic hierarchy}, a quantum circuit model that alternates between arbitrary-sized Clifford circuits and constant-depth circuits with two-qubit gates ($\textsf{QNC}^0$). This model unifies existing circuit models, such as $\QACZF$ and models with adaptive intermediate measurements. Despite its generality, we are able to prove nontrivial lower bounds. We prove new lower bounds in the first level of the hierarchy, showing that certain explicit quantum states cannot be approximately prepared by circuits consisting of a Clifford circuit followed by $\textsf{QNC}^0$. These states include ground states of some topologically ordered Hamiltonians and nonstabilizer quantum codes. Our techniques exploit the rigid structure of stabilizer codes and introduce an infectiousness property: if even a single state in a high distance code can be approximately prepared by one of these circuits, then the entire subspace must lie close to a perturbed stabilizer code. We also show that proving state preparation lower bounds beyond a certain level of the hierarchy would imply \emph{classical} circuit lower bounds beyond the reach of current techniques in complexity theory. More broadly, our techniques go beyond lightcone-based methods and highlight how the magic hierarchy provides a natural framework for connecting circuit complexity, condensed matter, and Hamiltonian complexity.