Papers

We study discrete-time quantum trajectories of a finite-dimensional system in a disordered environment, where the instrument applied at each step is determined by an invertible measure-preserving dynamical system. For general quantum instruments on a standard Borel outcome space, we construct the quenched probability law on sequences of measurement outcomes for a fixed realization of the disorder and a given initial state. Under a quenched Doeblin condition with a uniform deterministic minorization constant and an environment-dependent minorizing probability measure, we establish the existence and uniqueness of an equivariant family of random posterior laws and identify its barycenter as the unique dynamically stationary state for the associated non-selective channel cocycle. If the environment is ergodic, we prove a pathwise ergodic theorem valid for every measurable choice of initial state: for almost every realization of the disorder, time averages of posterior states converge almost surely under the corresponding quenched law to the disorder average of the unique dynamically stationary state. For an ergodic environment, we establish quenched variance asymptotics and, when the asymptotic variance is positive, a central limit theorem and standardized Berry–Esseen bounds for additive functionals generated by bounded measurable real-valued functions of the environment and posterior state. These results hold for every measurable initial state and almost every disorder realization. We then show that the stationary annealed joint process of instruments and posterior states inherits the $\alpha$-mixing of the instrument process, up to an exponentially decaying term. Finally, we provide classes of examples involving perfect and imperfect measurements, including models with continuous or finite outcome spaces, that satisfy the standing Doeblin condition.

Classical shadows allow the prediction of many quantum-state properties from measurement data, but their efficiency strongly depends on the underlying measurement ensemble. We introduce selective GHZ measurement (SGM) shadows, which perform Greenberger-Horne-Zeilinger (GHZ)-basis measurements on randomly selected subsets of qubits and computational-basis measurements on their complement. The corresponding quantum circuits are practically feasible, with their number of CNOT gates scaling linearly with the number of qubits. This is in stark contrast to global Clifford circuits, which are generally difficult to implement. Varying the subset distribution allows tuning the SGM shadow protocol for different classes of observables with prescribed X/Y support, allowing us to outperform local Pauli as well as global Clifford shadows in certain scenarios. We determine the exact shadow channel and its inverse for arbitrary subset distributions and prove an explicit bound on the shadow norm using methods from discrete Fourier analysis and Markov semigroup theory. For natural choices of subset distributions, this gives a polynomial scaling for observables with fixed X/Y-locality. Numerical simulations of up to 50 qubits support the predicted improvements for nonlocal observables and long-range systems, and demonstrate the practical benefits of our protocol's generality by showing how the subset distributions can be tailored to settings such as fermionic modes under the Jordan-Wigner transformation.

Estimating time-accumulated observables, or dense outputs, is central to extracting classical information from quantum simulations. Whereas most quantum-simulation algorithms aim to reproduce a final state or a single-time expectation value, many applications require the integrated signal $J_H(O)=\int_0^T \langle \psi(t)|O(t)|\psi(t)\rangle\,dt$. Previous Hamiltonian-simulation-based dense-output algorithms have query costs that depend on the norm of the full Hamiltonian, which can grow with system size. However, one can naturally optimize the simulation algorithm when the system structure is known. Consequently, we develop a locality-based truncation framework for the dense-output problem on lattice Hamiltonians. By truncating the Hamiltonian and tightening the resulting error with Lieb-Robinson bounds, we show that a local simulation can recover the dense output. We bound the quantum simulation error from spatial truncation and translate it into local-simulation query bounds. Our analysis includes free and interacting systems for both fermions and bosons, as well as open quantum systems governed by Lindbladians. The improvement from our truncation algorithm varies from constant to unbounded as the system size grows. We also give example applications and conduct relevant numerical experiments to support our findings.

We introduce quantum tilted walks, a quantum algorithmic framework for solving exact combinatorial optimization problems. The framework applies an average of powers of a tilted Hamiltonian that biases the discriminant matrix of a base Markov chain (mixer) with the objective function. Our starting point is quantum short-path algorithms, which prepare the ground state of such a Hamiltonian and obtain super-quadratic speedups over exhaustive search for certain combinatorial optimization problems. Recently, Le Gall and Tamaki~(arXiv:2604.12131) developed a classical conditioning-and-search algorithm for weighted MAX-E$k$-LIN2 and weighted MAX-$k$-CSP. Under the same assumptions, their algorithm is only sub-quadratically slower than quantum short-path algorithms. Consequently, existing short-path algorithms do not establish a super-quadratic speedup over this stronger classical baseline. For maximization problems, we give conditions under which tilted walks increase the amplitude on the target state with high objective value when initialized from a starting state with lower objective value. This framework captures conditioning-and-search and yields super-quadratic speedups over it for the same problems. While our framework recovers quantum short-path algorithms as a special case, it neither requires ground-state preparation nor initialization in the ground state of the base mixer. We demonstrate these advantages on a synthetic optimization problem for which tilted walks achieve a super-quadratic speedup whereas the short-path algorithms do not.

We present a universal entanglement distillation protocol that asymptotically achieves the distillable entanglement of any unknown bipartite state in a fixed finite dimension. That is, its ebit yield attains every rate below the optimum that would be available if the state were known, with vanishing trace-distance error. Our approach combines tomography by local operations and classical communication with an adaptive distillation routine, using a local robustness lemma to control finite-sample estimation errors. We also characterize worst-case distillation from a family of states: the optimal uniform rate is the minimum distillable entanglement on the family's closure. These results show that ignorance of the state need not incur an asymptotic rate penalty.

Molecular quantum dynamics simulations that treat both electrons and nuclei quantum mechanically are crucial for predicting chemical reactions. With classical computation, a full wave-function representation of both types of particles requires resources that grow exponentially with their number. Oscillator-qubit processors, including trapped-ion and circuit QED devices, represent electronic states with qubits and nuclear vibrations with oscillators. Their native operations produce linear vibronic interactions, from which programmable anharmonic interactions can be built. Product-formula approaches build the corresponding phase gates by repeating small noncommuting phase steps, and quantum signal processing (QSP) approaches approximate each gate directly with a Fourier series. Simulations apply many such gates in sequence, so accumulated cost and error limit how long the dynamics can be followed. We propose near-optimal quantum primitives for molecular quantum dynamics simulation, covering the representations of both types of particles and their interactions. We synthesize nonlinear and multimode bosonic phase gates using generalized Jacobi-Anger (GJA) expansions within QSP, with a cost that grows near-optimally in both interaction strength and precision. Our interaction model and gate synthesis each have their own accuracy setting. Chosen together, these settings make our multimode benchmark circuits about one-third shorter than those of the previous direct QSP approach. We then simulate energy exchange between the stretching and bending vibrations of a simplified carbon dioxide model. With circuit-QED noise, a short simulation narrowly misses our accuracy criteria at qubit and oscillator lifetimes near 2 ms and 5 ms. These lifetimes mark a concrete checkpoint on the way to simulating anharmonic multimode molecular quantum dynamics on near-term oscillator-qubit processors.

Linear combination of unitaries (LCU) is a fundamental primitive in quantum algorithms, whose cost is typically governed by the most expensive unitary appearing in the combination. We develop a transducer-based LCU framework that reduces this worst-case dependence to a weighted average query complexity, when the constituent unitaries share access to a common set of primitive oracles. Consider $A=\sum_j c_j U_j$, where $c_j>0$ and each unitary $U_j$ can be implemented using $C_j$ primitive queries. Given an upper bound $a\geq \|A\|$, our algorithm implements a block-encoding of $A/\alpha$ with rescaling factor $\alpha=\mathcal{O}(a)$, using $\widetilde{\mathcal{O}} (C_{\max}+\overline{C} {\lambda}/{a} )$ primitive queries, where $\lambda=\sum_j c_j$, $C_{\max}=\max_j C_j$, and $\overline{C}= {\sum_j c_j C_j}/{\lambda}$. By comparison, the standard LCU construction requires $\widetilde{\mathcal{O}} (C_{\max} {\lambda}/{a} )$ primitive queries. The improvement can therefore be substantial when costly unitaries have small weights and $\lambda/a$ is large. As applications, we obtain improved block-encodings of sparse matrices, leading to quantum algorithms for sparse Hamiltonian simulation and quantum linear systems with near-optimal query complexity up to polylogarithmic factors in all relevant parameters. Our main technique is the transducer framework developed by Belovs, Jeffery, and Yolcu [Quantum, 8:1444 (2024)]. Here we develop a complementary operator-level theory tailored to block-encodings. We identify the resolvent norm $K$ as a key complexity measure for transducer implementation besides the existing catalyst complexity. We show that the transducer action can be converted into an $\epsilon$-approximate block-encoding using only $\mathcal{O}\left(K \log(1/\epsilon)\right)$ queries to the transducer, improving the precision dependence from polynomial to logarithmic.

We establish a no-go theorem for a broad class of quantum algorithms for the dihedral coset problem (DCP). We consider the Fourier-sampling and subset-sum-measurement template proposed by Regev (SIAM Journal on Computing, 2004), which is one of the main approaches to solving DCP. Suppose that, after measuring the lower $n-1$ bits of the subset sum, the algorithm discards any $\omega(\log n)$ bits from each of the Fourier labels. Then we prove that the algorithm cannot succeed in solving DCP. This shows that any algorithm following this template must make extensive use of the Fourier labels, and thus serves as a useful guide for developing algorithms for DCP. As a main application, we show that the recent algorithm by Simon (IACR ePrint:2026/1591, August 11 2026) does not solve DCP. We show that after the subset-sum measurement, this algorithm can be implemented (up to exponentially-small error) using only the most-significant third of the Fourier labels, and is therefore subject to our general no-go theorem. To help with verifiability, we release Lean 4 code for our results.

The bosonic quantum entropy power inequality bounds the entropy of a beam-splitter output in terms of the input entropies. We determine its complete equality class among independent inputs of finite mean photon number: for any number of modes and any transmissivity strictly between zero and one, equality in either the linear or the exponential form holds if and only if the inputs are Gaussian with the same covariance matrix, allowing arbitrary displacements. The main step shows that equality for one output forces the two outputs to be independent: a thermal auxiliary converts equality into preservation of mutual information by a fixed noisy channel, and a two-outcome instrument shows that preservation of mutual information requires a product state with the reference. The quantum Darmois–Skitovich theorem then gives Gaussianity, while a central-limit argument reduces exponential equality to linear equality.

We develop a theory of exact transmission of finite-dimensional $C^*$-algebras through quantum channels. These algebras describe hybrid classical-quantum information, allowing the dimension of the quantum system to depend on the classical message. Allowing arbitrary encodings and decodings yields a transmission set of algebra types, ordered by embedding, that unifies zero-error information theory with operator-algebraic error correction. We ask if this set admits a dominating algebra into which every transmittable algebra embeds. Our central finding is that domination can fail even in small dimensions. In its absence, several incomparable maximal algebras can describe different optimal uses of the same channel, forcing the user to select one depending on the operational task and the type of information to be preserved. We introduce hybrid capacities that reconstruct the only possible dominating algebra type and present a complete finite characterization of domination using minimal forbidden algebra types. We identify dominating algebras for channels whose operator systems are graph-isomorphic to $*$-algebras, including highly divisible channels, and for channels with zero one-shot zero-error quantum capacity. Under tensor products, we prove that joint coding can produce new algebra types, giving an algebraic analogue of superadditivity from Shannon theory. Domination can fail for the joint use of two channels, even when both channels separately admit dominating algebras. Finally, we construct a channel whose $n$-fold tensor powers have doubly exponentially many maximal algebra types, attaining the largest possible growth scaling for finite-dimensional channels. Consequently, new transmittable algebra types appear at arbitrarily large block-lengths for this channel, so its full transmission structure cannot be generated from any finite collection of bounded-block-length codes.

We consider quantum devices restricted to local operations in 2D and subject to local stochastic noise below a constant threshold. We show that such circuits are computationally more powerful than AC0-circuits, i.e., noise-free, geometrically-unconstrained constant-depth classical circuits with unbounded fan-in AND, OR and NOT gates. To this end, we exhibit a computational problem with the following properties: (i) Any instance of the problem is correctly solved with high probability by a certain geometrically 2D-local quantum circuit even if the latter is imperfectly implemented, but (ii) any polynomial-size AC0-circuit fails to solve certain instances of the problem with constant probability. To our knowledge, this isthe first complexity-theoretic separation which applies to planar quantum devices, incorporates noise-resilience and is unconditional, i.e., does not rely on complexity-theoretic assumptions. This brings the experimental demonstration of an unconditional quantum advantage closer to experimental realities.

Finite-bandwidth reservoir engineering can suppress unwanted transitions in a quantum thermal machine, but a physical filter also introduces a finite response time. We study this competition in a continuous three-level heat engine whose hot environment couples parasitically to the cold transition. The corresponding three-state rate network is solved exactly, showing that the parasitic transition produces a hot-to-cold thermodynamic short circuit and yielding a closed threshold for the loss of positive-power operation. We then retain a damped auxiliary mode explicitly as a physical spectral filter. Its Lorentzian response suppresses the detuned parasitic transition, whereas excessive narrowing limits the useful energy throughput. Independent local-GKSL and nonsecular Bloch–Redfield calculations both recover the no-leak Markovian engine in the weak-coupling limit and predict a finite maximum-power bandwidth, although its precise location is model dependent. A frequency-resolved Lorentzian-rate reduction, by contrast, has no interior optimum. The resulting design principle is that spectral selectivity can protect the useful thermodynamic cycle, but a real filter cannot be narrowed without a dynamical throughput cost.

Decoded Quantum Interferometry (DQI) reduces optimization problems with two-variable constraints to decoding cycle codes. For one such problem, namely MaxCut, prior work showed that DQI achieves a nontrivial satisfaction fraction guarantee only on linear-girth graphs, for which MaxCut is classically easy. However, these no-go results rely on minimum distance assumptions that do not represent true decodability thresholds for common noise channels, thus underestimating actual DQI performance. To estimate the true performance, we derive DQI satisfaction guarantees in the presence of imperfect decoding for fixed instances and generalize prior results for random instances. We then study homological cycle codes over arbitrary finite fields, and show that minimum-weight decoding is NP-hard for every field of size $q>2$, in contrast with known results for binary cycle codes. On the Linial–Simkin ensemble of regular graphs with logarithmic girth, we prove maximum-likelihood recovery bounds and a strong converse for a family of non-uniform additive noise channels. Moreover, LP decoders provide polynomial-time recovery of a positive fraction of randomly located errors with arbitrary values. These results allow us to prove upper and lower bounds on the approximate optima achievable by DQI when restricted to classical decoders. These bounds rule out quantum advantage in the regimes we analyze but also identify a family of regular Max-$k$-Cut instances on which DQI efficiently achieves a nontrivial satisfaction fraction guarantee.

The interconversion among different quantum resources has attracted considerable attention, exemplified by the tradeoff between coherence and entanglement. However, the relationship between local and global quantum resources remains largely unexplored. Here, we propose and experimentally demonstrate a local global tradeoff in quantum resources, quantified respectively by the local maximum coherence and the quantum mutual information. Our experiments show that the sum of the local maximum coherence and the quantum mutual information is bounded by a definitive upper limit. These results not only establish a fundamental tradeoff inequality, but also provide direct experimental evidence of the complementarity between local and global quantum resources. Moreover, our findings reveal an important constraint in quantum networks: the local quantum resources available at individual nodes and the global quantum resources of the network are mutually exclusive, implying that enhancing one necessarily limits the other.

Measures of non-stabilizerness (“magic”) of a quantum evolution quantify how hard it is to simulate on a classical computer. A natural question is how to extract information about magic from physical correlators, for example at finite temperature or in the ground state. In this paper we show how to measure magic using out-of-time-order correlators evaluated in an arbitrary state. For every full-rank state, and in particular for every Gibbs state, the resulting quantity vanishes if and only if the evolution is Clifford. We establish its basic properties, relate it to the stabilizer entropy of the Choi state, and prove that, even with a single fixed probe operator, it gives a lower bound on the number of $T$ gates needed to implement the dynamics in any circuit architecture.

Continuous measurements simultaneously reveal and modify the dynamics of a quantum system. In this work we consider the tunneling motion of particles between the sites of a one-dimensional lattice. We investigate how weak continuous probing of the occupation of a single lattice site induces entanglement and selects definite values for system properties such as wave function parity and permutation symmetry. Our simulations show how continuous measurement can steer systems of two and three particles, with no prior permutation symmetry, into stable bosonic, fermionic and parastatistical symmetry sectors.

The goal of quantum metrology is to estimate an unknown parameter with better-than-classical precision and, ideally, to attain Heisenberg scaling. In realistic settings, however, noise can substantially reduce this advantage and, in many cases, restore standard-quantum-limit-like performance. Preserving the quantum enhancement therefore requires noise-robust strategies, which can be implemented using quantum error correction. In this work, we develop and analyze a quantum-metrology protocol based on Calderbank-Shor-Steane (CSS) codes. The main result is that, for noise perpendicular to the sensing Hamiltonian, discrete-time error correction preserves Heisenberg-like temporal scaling over a finite interrogation-time window whose duration depends on the correction frequency. It is further shown that recovery applied only after the sensing evolution provides no metrological advantage over the corresponding uncorrected noisy protocol in the setup considered here. An analytical framework is developed for arbitrary CSS codes and applied to the Steane and Shor codes, for which the discrete-time corrected dynamics, the Heisenberg-like-to-SQL-like crossover, and the optimal interrogation time are determined and numerically analysed.

Quantum Random Access Memory (qRAM) is a critical component for achieving quantum advantage in algorithms ranging from database search to quantum machine learning. In a recently introduced model [arXiv:2508.02855], we proposed a resource-efficient qRAM architecture based on discrete-time quantum walkers. This article serves as a comprehensive technical follow-up, providing the full mathematical derivations, detailed protocol specifications, and in-depth resource analysis. Moreover, we extend the original proposal with novel techniques for the purpose of making the qRAM implementation more realistic. Our model resolves the primary drawbacks of leading qRAM proposals: it avoids the exponential number of active nodes $\mathcal{O}(2^n)$ required by the "Bucket Brigade" architecture by employing a number of quantum walkers that scales linearly with the address and message sizes, $n$ and $m$, respectively. Simultaneously, it overcomes the spatial bottlenecks of previous quantum-walker schemes by eliminating the need for multiple parallel trees. We propose two algorithmic paradigms: the long- and the short-range approaches, which differ by the length of interaction of the main routing gates employed in the qRAM. We formalize the routing, message-copy, and walker retrieval phases for both variants and we show how, while the long-range scheme employs controlled gates having a multitude of target systems, the short-range approach decomposes these interactions into sequences of 2- and 3-body local gates, which improves the architecture's feasibility for near-term experimental implementation. Finally, our comprehensive resource analysis confirms that the short-range approach achieves the optimal $\mathcal{O}(n+m)$ circuit depth. Within these two paradigms, we explore the potential of different types of quantum walkers, namely bosons, dual-rail qubits and four-level qudits.

Planar parity-preserving tensor networks (ppTNs) admit a fermionic formulation in which the Gaussian, efficiently contractible limit is deformed by local interactions. We investigate how many-body methods can be used to analyze such contractions in a minimal two-parameter ppTN. Its contraction is simultaneously an interacting fermionic partition function, a loop gas, a deformed toric-code norm, and a quartic Ising model, allowing the same phase diagram to be approached with complementary tools. At its center lies a `topological island', characterized beyond the Gaussian limit by a boundary-twist $\mathbb Z_2$ indicator that reduces to Chern-number parity and admits a loop-winding interpretation under duality. Fermionic perturbation theory predicts the interacting phase boundaries, tensor-network numerics establish their critical behavior, and the loop and spin descriptions reveal a self-dual line with a $c=1$ four-state-Potts multicritical fixed point.

We present a learning task for quantum channels that exhibits an exponential separation in query complexity (in terms of the number of qubits) between two access models: i) black-box channel access and ii) access to a Stinespring dilation unitary of the channel along with its inverse. We consider the task of learning how close the unknown channel is to the set of unitary channels. This is characterized by the optimal average gate fidelity (OAGF), defined as the average gate fidelity maximized over all unitary channels. For constant Kraus rank and a dilation environment of dimension $\operatorname{polylog}(d)$, we provide an algorithm that estimates the OAGF to fixed additive accuracy using $\operatorname{polylog}(d)$ queries to the Stinespring dilation unitary and its inverse. In contradistinction, under the black-box access model, this estimation requires at least $\Omega(\sqrt{d})$ queries, even for channels of constant Kraus rank and constant additive accuracy. As a corollary, we rule out a universal simulator that uses only $\operatorname{poly}(\log d,q)$ queries to the unknown channel to approximate the output of arbitrary $q$-query algorithms with access to a randomly-sampled Stinespring dilation unitary and its inverse, even to sufficiently small constant error. These results demonstrate that access to the system-environment joint evolution and its inverse can provide an exponential advantage in estimating an intrinsic property of a quantum channel.

Approximate unitary designs reproduce the statistics of Haar-random unitaries to a given order and accuracy. Recent constructions realize such designs with logarithmic-depth circuits, enabling shallow measurement protocols for various quantum state-learning tasks while preserving performance. These results raise the question of whether approximate designs can replace exact designs more generally. We show that even exponentially small design error need not preserve the learning guarantees of exact designs. This motivates deriving learning guarantees directly from the measurement circuit structure. For observable estimation with classical shadows, we prove that logarithmic-depth two-layer Clifford circuits yield an unbiased estimator matching the global Clifford variance scaling for every state and Hermitian observable. Beyond observable estimation, this bound allows shallow measurements to retain global Clifford guarantees for other tasks, including setting-efficient tomography, mixed-state metrology, and stabilizer structure learning. We complement these statistical guarantees with a compact, exact tensor-network representation of the inverse shadow channel. When measurement bases are reused, approximate unitary designs of arbitrarily high order need not uniformly match the Haar variance in the many-shot limit. For the all-to-all random two-local circuits considered, doing so requires nearly linear depth. Together, our results reveal the capabilities and limitations of shallow quantum state learning, highlighting the distinction between approximating Haar randomness and reproducing its learning guarantees.

The Scrooge ensemble associated with a density matrix $\rho$ is the maximally random ensemble whose average density matrix is $\rho$. It has attracted growing interest for its applications to quantum many-body dynamics and quantum information. The intrinsic statistical properties of the Scrooge ensembles are encoded in their higher-order moments, yet they are nontrivial to analyze and prepare for they feature a non-polynomial Haar integrand, blocking direct use of Haar integration machinery. Existing physical mechanisms to sample multiple copies of states from the Scrooge ensembles, meanwhile, typically require costly postselection, rendering them inefficient for large system size. In this work, we develop efficient and accurate methods for analyzing and implementing Scrooge moments. We first introduce a polynomial approximation to the Scrooge $k$-th moments whose error is tunable down to a threshold that improves from inverse polynomial to exponential in $1/||\rho||_\infty$ over previous results. Building on our approximation, we then give the first efficient quantum algorithm that estimates observable expectation values using $\widetilde{\mathcal{O}}(k^3/\epsilon^5)$ copies of $\rho$ for any target error $\epsilon$ above this threshold. We further provide a construction of a block encoding of the Scrooge $k$-th moment when the preparation circuit of $\rho$ is known. Of independent interest could be a key subroutine in our algorithms, which efficiently implements projection onto the $k$-fold symmetric subspace for $\rho^{\otimes k}$ using $\mathcal{O}(k^3/\epsilon^2)$ samples of $\rho$, avoiding the naive $k!$ postselection cost of such a projection. These results provide new tools for both the theoretical analysis and practical prediction of properties of Scrooge ensembles, with potential applications to quantum many-body dynamics and quantum information processing.

Stabiliser path finding (SPF) has previously been introduced as a method to localise logical information in a stabiliser code undergoing loss onto a single pre-specified target qubit, using only one round of single-qubit measurements. When working with limited resources and flying qubits, this fast read-out of logical information is a helpful tool for fault-tolerant communication. In this work, we provide a broad analytical and computational study of localisation via SPF. We introduce $g$-SPF, where the task is to localise the logical information onto a set of at most $g$ unspecified target qubits. Through analytical arguments based on percolation theory and the disjointness of stabiliser codes, we prove that for i.i.d. qubit loss with probability $p<1/2$ and sufficiently large planar surface codes, localisation via $g$-SPF for constant $g$ succeeds with a probability converging to one, which establishes a localisation threshold. Furthermore, we propose and implement two algorithms to solve SPF. The first is exact and formulates SPF as an integer linear program, whereas the second is heuristic and formulates SPF as a decoding problem. We validate both algorithms by numerically reproducing the localisation threshold for the surface code and demonstrate that the heuristic algorithm is considerably faster. Our work significantly reduces the time required to solve SPF compared to current state-of-the-art algorithms, allowing us to study localisation in substantially larger stabiliser codes than previously considered in the literature. Together, these theoretical and computational results open the door to various applications, such as fault-tolerant teleportation and efficient logical fusion.

We study the quantum query complexity of computing a semigroup product $x_1\cdots x_n$, when one query reveals one input element and the multiplication table is given. For a finite aperiodic semigroup of size $N-1$, the argument of Aaronson, Grier, and Schaeffer gives an upper bound of $\sqrt n\,(N\log(nN+2))^{O(N)}$ queries. To obtain query bounds that reflect algebraic structure, we study the product breadth $\beta$: the smallest bound such that every input word has a subsequence of at most $\beta$ letters with the same product. For nontrivial finite commutative aperiodic monoids, the bounded-error quantum query complexity is $\Theta(\min\{n,\sqrt{n\beta}\})$, and is thus characterized by product breadth. We further show that if such a monoid $M$ has aperiodicity index $k$ (the least positive integer satisfying $x^k=x^{k+1}$ for every $x\in M$), then $\beta=O(k\log(|M|+1)\log\log(|M|+2))$. For monoids with a stable partial order in which the identity is the minimum element, we prove that the bounded-error quantum query complexity is at most $\sqrt{n+1}((\beta+2)\log(n+2))^{O(\log(\beta+2))}$. For arbitrary finite aperiodic semigroups of order $N-1$, we improve the bound of Aaronson, Grier, and Schaeffer, obtaining a bounded-error quantum query complexity of at most \[ \min\left\{n,\sqrt n\, \log^{O((N\log(N+2))^{1/3})}(n+2)\right\}. \] The dependence on semigroup size is nearly tight: the bounded-depth Dyck lower bound of Ambainis et al. yields aperiodic monoids requiring $\sqrt n\,2^{\Omega(N^{1/3})}$ quantum queries in the relevant parameter range.

Preparing logical codewords with a single round of noisy syndrome measurements can reduce the time overhead of fault-tolerant quantum computation. It remains unclear which structural properties of the code suffice to guarantee a threshold for single-shot state preparation. Here we prove that linear confinement suffices for a nonzero single-shot state-preparation threshold for CSS quantum low-density parity-check codes, in contrast to the common belief that soundness is necessary. When the distance is at least logarithmic, we prove that below nonzero local stochastic readout and data error thresholds, the logical error probability after a formal ideal final recovery is exponentially small and approaches zero when the code size approaches infinity. Under the stronger assumption of linear soundness, we show that the residual data error of the preparation protocol is local stochastic, directly allowing composition with other fault-tolerant gadgets. To investigate single-shot state-preparation threshold beyond the above assumptions, we further develop a statistical mechanical mapping that expresses the final logical error rate in terms of a classical partition function. We perform Monte Carlo simulations of this model for the three-dimensional toric code. The numerical results suggest that sublinear soundness can also support a single-shot state-preparation threshold.

We present a comprehensive review of quantum approaches for solving partial differential equations (PDEs) arising in computational fluid dynamics (CFD). We examine fully quantum approaches, including quantum linear system algorithms (QLSAs), ranging from the Harrow–Hassidim–Lloyd (HHL) algorithm to quantum singular value transformation (QSVT), Hamiltonian simulation, and quantum lattice Boltzmann methods (QLBMs), while emphasizing hybrid quantum–classical approaches, including quantum physics-informed neural networks (QPINNs) and amplitude-encoded variational PDE solvers. We focus on hardware-agnostic algorithms compatible with present noisy processors and emerging fault-tolerant architectures. For each framework, we analyze the mathematical formulation, algorithmic structure, and principal limitations. We also examine tensor-network (TN) representations, since CFD fields, differential operators, and geometrical information can often be encoded efficiently in low-rank form. The TN formalism bridges CFD discretizations and quantum states, operators, and circuits, enabling compact representations to be translated into tensor-programmable variational quantum algorithms (TP-VQAs). We further review benchmark problems, including Poisson, reaction, diffusion, and nonlinear model equations, and assess how well quantum algorithms capture key features of fluid dynamics. Our analysis highlights that potential quantum advantage is highly problem dependent and governed by condition number, representational complexity, state preparation, and measurement constraints. We outline capabilities, limitations, and challenges toward scalable quantum algorithms for CFD.

Haah's 3D cubic code was introduced as a candidate for a self-correcting quantum memory in three dimensions, using the absence of string logical operators to obstruct thermal errors. It has been a long-standing open question whether it is a self-correcting quantum memory. Even though the memory time was explored numerically, no analytical upper bound was known. Here, we settle this question rigorously and show that the cubic code thermalizes rapidly at every positive temperature. Our proof relies on the framework of [Commun. Math. Phys. 407, 195 (2026)] to turn a decay-of-correlations condition into a modified logarithmic Sobolev inequality for the Davies generator. To the best of our knowledge, this is the first analytic proof of rapid mixing for all positive temperatures for any fracton code.

Confocal microscopy provides optical sectioning for three-dimensional imaging but conventionally relies on point-by-point scanning and physical pinholes, limiting imaging speed. Here, we demonstrate that confocal sectioning can instead arise directly from quantum measurement, using spatial correlations in entangled biphoton states. Spatially resolved coincidence measurements in a widefield imaging system suppress contributions from out-of-focus planes, producing optical sectioning in parallel across the whole field of view without physical pinholes or mechanical scanning. In addition, this quantum approach obtains an axial response that, as a result of position-momentum entanglement, is $\sqrt{2}$-times narrower than that of classical confocal imaging. Our work establishes biphoton correlations as a mechanism for improved confocal imaging and enables parallel, pinhole-free optical sectioning without mechanical scanning.

We study scaling law of variational quantum algorithms by large-scale numerical experiments on combinatorial optimizations. On experiments up to n = 5000 qubits with O( log(n)) circuit depth with a classically simulable ansatz, the converged energies consistently differ by no more than 0.5% from the optimal or reference energies reported in the benchmarks.

Quantum process tomography (QPT) protocols are often designed by lifting quantum state tomography (QST) protocols through the Choi-Jamiolkowski isomorphism, at the cost of an extra step enforcing the trace-preserving (TP) constraint. Existing approaches fall into two classes. The folklore partial normalization, which sandwiches the density estimate between inverse square roots of its input marginal, has a closed form but is used as a heuristic, its only analyses being asymptotic and losing a factor polynomial in the dimension. Projection-based methods are principled but have no closed forms and scale poorly with dimension. We resolve this dichotomy by showing that the partial normalization is the exact projection onto the Choi states of quantum channels in fidelity (equivalently in Bures or purified distance). Consequently, any QST algorithm with guarantees in fidelity lifts to a QPT algorithm that inherits its sample complexity, through a single closed-form congruence that preserves the Choi rank and is computed in Kraus form without any eigendecomposition of Choi dimension. We lift two single-copy protocols and prove that the non-adaptive one (Fidelity Projected Least Squares) recovers the Choi rank and reaches infidelity $\varepsilon$ from a number of channel uses proportional to $1/\varepsilon$. Numerically, for channels of low Choi rank, it improves on the state-of-the-art projected least squares in accuracy, and by orders of magnitude in the time and memory of the TP-regularization step and of the returned estimate.