Quantum algorithms for linear algebra that access a matrix A through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to A, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm ρ=∥A∥F/∥A∥ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use O(ρ) queries, whereas the best dequantized algorithms use O(ρ4). We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant κ0>1, we construct dense linear systems with condition number at most κ0 for which sampling from the solution within a sufficiently small constant total variation distance requires Ω(ρ4/logρ) classical queries but only Θ(ρ) quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.
We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of k-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given k Boolean functions f1,…,fk:F2n→{−1,1}, the goal is to estimate Tk=N−1Tr(Df1H⊗n⋯DfkH⊗n), where Dfi=diag(fi(x):x∈F2n), H is the Hadamard gate, and N=2n. This normalized-trace problem can be solved with k quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of Ω(N1−2/k).
We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even k≥4, we prove a tight bound of Θk(N1−2/k) for constant additive error. For odd k≥5, we obtain a lower bound of Ωk(N1−2/(k−1)) and an upper bound of Ok(N1−2/k). Surprisingly, k=3 admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the k-cycle, leading to the exponent 1−1/⌊k/2⌋, rather than the previously conjectured 1−2/k, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of Ω(N1/4) for every k≥4.
Although formally close to k-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.
Almost-quantum correlations form the 1+AB level of the Navascués--Pironio--Acín hierarchy. They strictly contain the quantum set, are characterized by a single semidefinite program, arise in Sorkin's quantum measure theory, and satisfy several principles proposed to single out quantum theory. We show that they are nevertheless unboundedly stronger than quantum correlations in a zero-error communication task. Alice and Bob receive labels s,t∈[N], N≥3; after one bit from Alice, Bob must decide whether s=t, never erring but allowed to abstain. For every model of quantum correlations, from finite-dimensional tensor products to commuting operators, the optimal worst-case probability of a conclusive answer is exactly 1/N, the value attained with shared randomness, so the bound does not depend on the resolution of Tsirelson's problem. An explicit family of almost-quantum correlations attains 1/19 for every N. For certificates of equality from binary-outcome boxes, we solve the underlying semidefinite programs in closed form. The almost-quantum optimum equals N2/(17N2−80N+64) for N≥8 and tends to 1/17. The first level of the hierarchy, which coincides with the set singled out by macroscopic locality, attains N/[8(N−2)], which tends to 1/8; its optimal boxes lie outside the almost-quantum set for every N≥5. For longer messages, entanglement saves at most one bit over shared randomness, whereas almost-quantum correlations reduce the one-way zero-error cost of deciding equality of n-bit strings from n bits to at most 13. The quantum bound also yields a linear witness of post-quantumness on a face of the nonsignalling polytope.
Information causality (IC) posits that communicating m classical bits cannot give the receiver access to more than m bits of information about the sender's independent data. Although IC holds in quantum theory and excludes a broad class of supra-quantum correlations, its validity for the almost-quantum set has remained open. This semidefinite relaxation of the quantum set satisfies nontrivial communication complexity, no advantage for non-local computation, macroscopic locality, local orthogonality, and numerical evidence has suggested that it may also satisfy IC. Here we show that almost-quantum correlations violate IC, and do so without bound. Unlike earlier violations of IC, which rely on biased guesses, ours is driven by zero-error certificates: each is rare but never wrong, carries information linear in its probability, and vouches for many of the sender's bits at once. This establishes a sharp dichotomy: either IC is a valid physical principle that excludes these correlations, or any nonsignalling theory realizing them admits no mutual information obeying consistency, data processing and the chain rule. In the latter case, we discuss why the chain rule is the natural property to relinquish, and how this possibility relates to histories-based formulations and to locality defined relative to the state rather than presupposed in a fixed spacetime.
Nonstabilizerness, commonly referred to as magic, is essential for universal quantum computation. Yet, for pure n-qubit states this property is directly linked to the hardness of direct fidelity estimation. We propose a scheme to bound the fidelity on non-stabilizer states by choosing operators with low measurement overhead and using parallel local Pauli measurements to estimate compatible observables. We selectively measure operators that share a permutational symmetry without imposing any assumption on the physical system. This selection reduces the optimization to a linear program with only O(n) variables for bounding fidelity. Our methods can be extended to bound nonlinear quantities like the purity via convex quadratic programs. For hypergraph states that can exhibit extensive nonstabilizerness, we demonstrate for up to n=500 qubits that our framework substantially reduces the measurement overhead under both local and global depolarizing noise. These results show that symmetry induced by measurement selection reduces both measurement and computational costs, enabling scalable characterization of magic resources in quantum computing and quantum networks.
We present a real-time FPGA decoder for a high-rate [[512,174,8]] 3D product qLDPC code. We construct a circuit-level detector-error model for a compact syndrome-extraction schedule and propose a small parallel ensemble of row-wise serial min-sum decoders with cumulative memory. The decoder matches BP+OSD-CS10 accuracy with one core and Relay-BP accuracy with three cores. The FPGA implementation meets the latency budget of neutral-atom and trapped-ion systems. An ASIC implementation would improve the latency, enabling real time decoding even for superconducting systems. At a physical error rate of p=10−3, three FPGA devices decode 174 logical qubits with a logical error rate of 5×10−7 and effective distance 6. For p=10−4, and assuming the number of BP iterations is capped to 30, the decoder's average latency is 5.1\textmu s and its worst-case latency is 97.9\textmu s.
We study channel interconversion under non-signalling superchannels, where the asymptotic conversion rate is given by the ratio of the channel capacities. Our main result determines the second-order expansion of the optimal target length. Namely, when each channel has a single capacity-achieving dispersion, the coefficient is given by the inverse sesquinormal distribution, with parameters determined by the capacities and dispersions. The result extends state-dichotomy theory to channels: one superchannel approximates the target uniformly over inputs and maps every reference channel whose output is independent of its input to another such channel. As in state dichotomies, there are finite-error resonances where the second-order term vanishes, leaving an O(logn) remainder. Crucially, our new characterization cannot be obtained by concatenating channel coding and simulation protocols [Cao {\it et al.}~IEEE Trans.~Inf.~Theory (2024)]. Instead, the proof combines comparisons of binary hypothesis testing experiments with uniform Gaussian estimates and a construction that uses symmetry within type classes to satisfy the non-signalling constraints. Shared randomness assistance already suffices at first order, but we show that its second-order behaviour can differ strictly from the non-signalling case.
Pure-state quantum phases are defined through finite-depth local unitary connections. This concept of phases has recently been generalized to mixed states in terms of locally reversible channels. In this work, we establish a fundamental relation between mixed-state phases and pure-state phases. We show that a locally reversible channel between mixed states can be lifted to a local isometry between their canonical purifications; thus, if two mixed states are in the same phase, then their canonical purifications are in the same pure-state phase. Furthermore, an explicit construction of the lifting isometry is given by ``half'' of the Petz recovery map, suggesting that the Petz recovery map \emph{without rotation} is enough to connect mixed state phases. We illustrate our results with two examples: toric code under bit flip noise and Chern insulator under fermion number noise.
We introduce GraphMP, a learning-based message-passing decoder for quantum low-density parity-check codes that transfers without fine-tuning across code families, code sizes, physical error rates, and noise models. GraphMP uses local message passing to keep computation scalable as the decoding graph grows. Guided by its predictions, beam search progressively refines candidate error patterns, trading additional decoding time for lower logical error rates. We develop the decoder model factory as a paradigm for training successive models on experience generated by earlier models during decoding. Model-guided search supplies verified trajectories for knowledge distillation, folding computation spent on decoding into reusable training data. Repeated collection and distillation improve the decoder across generations and adapt its strategy as the noise changes. These results motivate a coupled quantum--classical architecture with two interacting cycles: rapid decoding protects quantum information, while slower learning renews the models from operating experience. The long-term vision is a scalable decoder model factory that produces high-performance, low-latency decoders and continually adapts them to evolving quantum hardware.
Determining whether every trajectory of the linear system x˙=Ax converges to zero (or, equivalently, whether A is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix A∈Cn×n is Hurwitz stable, given an exact normalized block-encoding of A. The query complexity is characterized in terms of the system dimension n and a supplied lower bound 0<ν≤ωA on the imaginary-axis distance ωA:=mint∈Rσmin(A−itI), where σmin(A) is the smallest singular value of A. We prove a query-complexity lower bound of Ω(n/ν), which holds even when A is restricted to be real and diagonal. For general matrices with nonzero ωA, we encode an approximation of the right-half-plane spectral projector sign+(A):=(I+sign(A))/2 as a block of a matrix inverse, where A is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a (β,b,1/(4n))-block-encoded projector matrix (like sign+(A)) is zero or not; for constant success probability, it has complexity Θ(βn). When the zero test is applied to specific approximations of sign+(A), this yields an upper bound of O(nν−2log(n/ν)) queries in the general case, and O(nν−1logn) when A is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.
Quantifying non-Gaussianity is essential for assessing the computational power of bosonic quantum systems. We introduce a framework to witness and quantify non-Gaussianity from displaced parity measurements, and we directly apply it to experimental data obtained with superconducting cavities. Our method estimates fidelities with target pure states from the displaced parity measurements, enabling certification of non-Gaussianity via the stellar rank. We further introduce refined witnesses computed by measuring the value of the Wigner function at a few points, providing efficient certification tools outperforming existing ones. Applying these techniques to Fock, binomial, cat, and GKP experimental data, we rigorously certify non-Gaussian resources and establish a stellar rank of 8 for a GKP state, setting a new benchmark across all quantum platforms. Our methods enable a rigorous quantification of non-Gaussian quantum resources directly applicable to superconducting devices.
We introduce FaultScope, a classical simulator for quantum error correction circuits, implemented in Rust with a Python interface. FaultScope estimates logical error rates and their derivatives with respect to component error rates from the same sampled and decoded shots, without modifying or differentiating through the decoder. These derivatives enable error attribution to individual noisy components, helping identify noise hotspots for targeted noise reduction. FaultScope supports forward simulation of error propagation through circuits and direct sampling of detector and logical observable outcomes from detector error models. In our noiseless and noisy benchmarks, FaultScope has the lowest runtime among the tested simulators at every size. Computing all derivatives adds only 0.33--0.97\% to the runtime of logical error rate estimation across five repetition code sizes with 7--2047 error locations. FaultScope can be used to benchmark large-scale quantum error correction schemes and guide targeted noise reduction efficiently, thereby facilitating the design and optimization of fault-tolerant quantum computing architectures.
Probabilistic and destructive Bell-measurements, also known as fusions, constitute a fundamental primitive for photonic quantum technologies. These operations rely only on pairwise photonic interference, whereas the computational power of photonic quantum systems originates from many-body interference. Here, we introduce a family of high-efficiency linear-optical GHZ measurements based on four-mode interferometers and show that incorporating many-body interference into this ubiquitous primitive leads to more efficient entangling operations. For the four-photon case, the success probability is 9/32, and adaptive variants ensure that unsuccessful events project onto useful stabilizer states. We further show that the approach naturally generalizes to larger GHZ measurements, yielding an exponentially higher success probability than previous linear-optical schemes. Finally, we demonstrate practical advantages for graph-state resource generation, entanglement distribution between remote spin-photon interfaces, and fusion-based quantum computing. Our results establish high-efficiency many-body measurements as a new primitive for scalable photonic quantum information processing.
We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest.
Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget.
In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.
Quantum state smoothing is an estimation technique that uses past and future measurement information obtained from a continuous-in-time measurement record to reconstruct the state of an open quantum system. Recently, there has been a new approach to quantum state smoothing based on quantum retrodiction known as the Petz-Fuchs smoothed state. Here I prove that this Petz-Fuchs smoothed state majorizes all other smoothed states that only depend on the filtered state (the operator conditioned on the past measurement record) and the retrofiltered effect (the operator describing the future measurement record). To do this, I characterize the set of all possible smoothed states satisfying this condition.
We investigate the dynamics of quantum systems whose evolution is governed by linear generators of fixed unitarily invariant norm. For this broad class of evolutions, we derive a universal time-optimal generator of the dynamics converting one given state into another. It provides a time-optimal non-Hermitian Hamiltonian for pure state conversion. We then use this general result to derive quantum speed limits for mixed-state evolutions governed by Lindbladians and non-Hermitian Hamiltonians. Our findings follow from the geometric properties of the group GL(n,C), in particular the geodesic distance. The derived bounds hold for an arbitrary system size n, depend only on the norms of the evolution generator and the initial and final states, and do not require performing any time-averaging.
Device-independent conference key agreement (DI-CKA) enables N>2 distant parties to establish a common secret key without detailed characterization of the source or measurement devices. Many existing protocols rely on full-body Bell correlators, whose measurement can be demanding for a large number of parties. Here, we show that two-body correlators alone suffice for DI-CKA using balanced Dicke states for every even N≥4. We construct two-body Bell inequalities and derive a tight analytical lower bound on the conditional von Neumann entropy by comparing their Bell operators with those of asymmetric Clauser-Horne-Shimony-Holt inequalities. In the ideal setting, certified key rates can approach 1−h[(N−2)/(4(N−1))], where h is the binary entropy function. This rate remains bounded away from zero as N→∞, tending to 1−h(1/4)≈0.189 bits per key-generation round. We show that the honest implementation of our protocol is invariant under collective phase noise. Moreover, a complementary full-body Bell construction certifies positive conference-key rates from correlations arbitrarily close to the local set.
We introduce hypergraph cycle enumeration (HCE), a simple spectral framework for detecting and recovering planted signals in noisy hypergraph inference problems. We study HCE on one representative problem from this class, namely planted noisy k-XOR, also known as sparse Learning Parity with Noise (LPN). Both theoretically and empirically, HCE achieves comparable recovery behavior to Kikuchi method, matching Kikuchi hierarchy. We identify parameter regimes where HCE outperforms Kikuchi method, showing that neither algorithm is universally better. We also show a subquadratic quantum speedup for HCE by replacing one of the algorithm's steps with a quantum walk. Our classical and quantum algorithms do not refute the quartic quantum speedup of quantum Kikuchi method, which remains valid for the practically relevant regime of large size and high noise strength.
Despite quantum machine learning being an active topic of research, demonstrations of algorithms run on quantum hardware beating classical methods remain rare. In this work, we demonstrate a significant performance gap using a projected quantum kernel for n=15,30 and 45 qubits over classical methods on an engineered classification problem, and show reproducibility of the results over different quantum processor units. We also demonstrate how error mitigation can widen this gap, both by improving hardware performance but also by increasing the classical difficulty, with different techniques contributing unequally to these phenomena. This work provides strong evidence that superior empirical performance of quantum hardware over all classical techniques is an achievable goal in quantum machine learning, albeit for an artificial problem. However, as with any application relying on observables, beating state-of-the-art simulation methods remains the primary challenge, as our matrix product state results here show.
We show that reversible in-place quantum addition modulo 2n−1 can be implemented in constant Toffoli depth using O(n) space, provided that the variables are encoded in a certain non-standard form. Using measurement-based uncomputation, the Toffoli depth can be reduced to one. We also present space-depth tradeoffs and an application to programmable rotations.