Quantum 9, 1919 (2025). https://doi.org/10.22331/q-2025-11-20-1919 Sequential methods for quantum hypothesis testing offer significant advantages over fixed-length approaches, which rely on a predefined number of state copies. Despite their potential, these methods remain underexplored for unambiguous discrimination. In this work, we derive performance bounds for such methods when applied to the discrimination of a set of pure states. The performance is evaluated based on the expected number of copies required. We establish a lower bound applicable to any sequential method and an upper bound on the optimal sequential method. The upper bound is derived using a novel and simple non-adaptive method. Importantly, the gap between these bounds is minimal, scaling logarithmically with the number of distinct states.

Quantum 9, 1918 (2025). https://doi.org/10.22331/q-2025-11-20-1918 The spectral variant of the quantum marginal problem asks: Given prescribed spectra for a set of overlapping quantum marginals, does there exist a compatible joint state? The main idea of this work is a symmetry-reduced semidefinite programming hierarchy that detects when no such joint state exists. The hierarchy is complete, in the sense that it detects every incompatible set of spectra. The refutations it provides are dimension-free, certifying incompatibility in all local dimensions. The hierarchy also applies to the sums of Hermitian matrices problem, the compatibility of local unitary invariants, for certifying vanishing Kronecker coefficients, and to optimize over equivariant state polynomials.

Quantum 9, 1917 (2025). https://doi.org/10.22331/q-2025-11-20-1917 We study a qDRIFT-type randomized method to simulate Lindblad dynamics by decomposing its generator into an ensemble of Lindbladians, $\mathcal{L} = \sum_{a \in \mathcal{A}} \mathcal{L}_a$, where each $\mathcal{L}_a$ comprises a simple Hamiltonian and a single jump operator. Assuming an efficient quantum simulation is available for the Lindblad evolution $e^{t\mathcal{L}_a}$, we implement $e^{t\mathcal{L}_a}$ for a randomly sampled $\mathcal{L}_a$ at each time step according to a probability distribution $\mu$ over the ensemble $\\{\mathcal{L}_a\\}_{a \in \mathcal{A}}$. This randomized strategy reduces the quantum cost of simulating Lindblad dynamics, particularly in quantum many-body systems with a large or even infinite number of jump operators. Our contributions are two-fold. First, we provide a detailed convergence analysis of the proposed randomized method, covering both average and typical algorithmic realizations. This analysis extends the known results for the random product formula from closed systems to open systems, ensuring rigorous performance guarantees. Second, based on the random product approximation, we derive a new quantum Gibbs sampler algorithm that utilizes jump operators sampled from a Clifford-random circuit. This generator (i) can be efficiently implemented using our randomized algorithm, and (ii) exhibits a spectral gap lower bound that depends on the spectrum of the Hamiltonian. Our results present a new instance of a class of Hamiltonians for which the thermal states can be efficiently prepared using a quantum Gibbs sampling algorithm. A talk at Simons Institute

Quantum 9, 1916 (2025). https://doi.org/10.22331/q-2025-11-20-1916 To better understand quantum computation we can search for its limits or no-gos, especially if analogous limits do not appear in classical computation. Classical computation easily implements and extensively employs the addition of two bit strings, so here we study 'quantum addition': the superposition of two quantum states. We prove the impossibility of superposing two unknown states, no matter how many samples of each state are available. The proof uses topology; a quantum algorithm of any sample complexity corresponds to a continuous function, but the function required by the superposition task cannot be continuous by topological arguments. Our result for the first time quantifies the approximation error and the sample complexity $N$ of the superposition task, and it is tight. We present a trivial algorithm with a large approximation error and $N=1$, and the matching impossibility of any smaller approximation error for any $N$. Consequently, our results limit state tomography as a useful subroutine for the superposition. State tomography is useful only in a model that tolerates randomness in the superposed state. The optimal protocol in this random model remains open.

Quantum 9, 1915 (2025). https://doi.org/10.22331/q-2025-11-17-1915 Loop-based boson samplers interfere photons in the time degree of freedom using a sequence of delay lines. Since they require few hardware components while also allowing for long-range entanglement, they are strong candidates for demonstrating quantum advantage beyond the reach of classical emulation. We propose a method to exploit this loop-based structure to more efficiently classically sample from such systems. Our algorithm exploits a causal-cone argument to decompose the circuit into smaller effective components that can each be simulated sequentially by calling a state vector simulator as a subroutine. To quantify the complexity of our approach, we develop a new lattice path formalism that allows us to efficiently characterize the state space that must be tracked during the simulation. In addition, we develop a heuristic method that allows us to predict the expected average and worst-case memory requirements of running these simulations. We use these methods to compare the simulation complexity of different families of loop-based interferometers, allowing us to quantify the potential for quantum advantage of single-photon Boson Sampling in loop-based architectures.

Quantum 9, 1914 (2025). https://doi.org/10.22331/q-2025-11-17-1914 An important class of fermionic observables, relevant in tasks such as fermionic partial tomography and estimating energy levels of chemical Hamiltonians, are the binary measurements obtained from the product of anti-commuting Majorana operators. In this work, we investigate efficient estimation strategies of these observables based on a joint measurement which, after classical post-processing, yields all sufficiently unsharp (noisy) Majorana observables of even-degree. By exploiting the symmetry properties of the Majorana observables, as described by the braid group, we show that the incompatibility robustness, i.e., the minimal classical noise necessary for joint measurability, relates to the spectral properties of the Sachdev-Ye-Kitaev (SYK) model. In particular, we show that for an $n$ mode fermionic system, the incompatibility robustness of all degree-$2k$ Majorana observables satisfies $\Theta(n^{-k/2})$ for $k\leq 5$. Furthermore, we present a joint measurement scheme achieving the asymptotically optimal noise, implemented by a small number of fermionic Gaussian unitaries and sampling from the set of all Majorana monomials. Our joint measurement, which can be performed via a randomization over projective measurements, provides rigorous performance guarantees for estimating fermionic observables comparable with fermionic classical shadows.

Quantum 9, 1913 (2025). https://doi.org/10.22331/q-2025-11-17-1913 In this work, we develop a graphical calculus for multi-qudit computations with generalized Clifford algebras, building off the algebraic framework developed in our prior work. We build our graphical calculus out of a fixed set of graphical primitives defined by algebraic expressions constructed out of elements of a given generalized Clifford algebra, a graphical primitive corresponding to the ground state, and also graphical primitives corresponding to projections onto the ground state of each qudit. We establish many properties of the graphical calculus using purely algebraic methods, including a novel algebraic proof of a Yang-Baxter equation and a construction of a corresponding braid group representation. Our algebraic proof, which applies to arbitrary qudit dimension, also enables a resolution of an open problem of Cobanera and Ortiz on the construction of self-dual braid group representations for even qudit dimension. We also derive several new identities for the braid elements, which are key to our proofs. Furthermore, we demonstrate that in many cases, the verification of involved vector identities can be reduced to the combinatorial application of two basic vector identities. Additionally, in terms of quantum computation, we demonstrate that it is feasible to envision implementing the braid operators for quantum computation, by showing that they are 2-local operators. In fact, these braid elements are almost Clifford gates, for they normalize the generalized Pauli group up to an extra factor $\zeta$, which is an appropriate square root of a primitive root of unity.

Quantum 9, 1912 (2025). https://doi.org/10.22331/q-2025-11-17-1912 Recent experimental progress in controlling open quantum systems enables the pursuit of mixed-state nonequilibrium quantum phases. We investigate whether open quantum systems hosting mixed-state symmetry-protected topological states as steady states retain this property under symmetric perturbations. Focusing on the $\textit{decohered cluster state}$ – a mixed-state symmetry-protected topological state protected by a combined strong and weak symmetry – we construct a parent Lindbladian that hosts it as a steady state. This Lindbladian can be mapped onto exactly solvable reaction-diffusion dynamics, even in the presence of certain perturbations, allowing us to solve the parent Lindbladian in detail and reveal previously-unknown steady states. Using both analytical and numerical methods, we find that typical symmetric perturbations cause strong-to-weak spontaneous symmetry breaking at arbitrarily small perturbations, destabilize the steady-state mixed-state symmetry-protected topological order. However, when perturbations introduce only weak symmetry defects, the steady-state mixed-state symmetry-protected topological order remains stable. Additionally, we construct a quantum channel which replicates the essential physics of the Lindbladian and can be efficiently simulated using only Clifford gates, Pauli measurements, and feedback.

Quantum 9, 1911 (2025). https://doi.org/10.22331/q-2025-11-17-1911 Quantum networks are important for quantum communication, enabling tasks such as quantum teleportation, quantum key distribution, quantum sensing, and quantum error correction, often utilizing graph states, a specific class of multipartite entangled states that can be represented by graphs. We propose a novel approach for distributing graph states across a quantum network. We show that the distribution of graph states can be characterized by a system of subgraph complementations, which we also relate to the minimum rank of the underlying graph and the degree of entanglement quantified by the Schmidt-rank of the quantum state. We analyze resource usage for our algorithm and show that it improves on the number of qubits, bits for classical communication, and EPR pairs utilized, as compared to prior work. In fact, the number of local operations and resource consumption for our approach scales linearly in the number of vertices. This produces a quadratic improvement in completion time for several classes of graph states represented by dense graphs, which translates into an exponential improvement by allowing parallelization of gate operations. This leads to improved fidelities in the presence of noisy operations, as we show through simulation in the presence of noisy operations. We classify common classes of graph states, along with their optimal distribution time using subgraph complementations. We find a sequence of subgraph complementation operations to distribute an arbitrary graph state which we conjecture is close to the optimal sequence, and establish upper bounds on distribution time along with providing approximate greedy algorithms.

Quantum 9, 1910 (2025). https://doi.org/10.22331/q-2025-11-14-1910 Consider an open quantum system with (discrete-time) Markovian dynamics. Our task is to store information in the system in such a way that it can be retrieved perfectly, even after the system is left to evolve for an arbitrarily long time. We show that this is impossible for classical (resp. quantum) information precisely when the dynamics is mixing (resp. asymptotically entanglement breaking). Furthermore, we provide tight universal upper bounds on the minimum time after which any such dynamics 'scrambles' the encoded information beyond the point of perfect retrieval. On the other hand, for dynamics that are not of this kind, we show that information must be encoded inside the peripheral space associated with the dynamics in order for it to be perfectly recoverable at any time in the future. This allows us to derive explicit formulas for the maximum amount of information that can be protected from noise in terms of the structure of the peripheral space of the dynamics.

Quantum 9, 1909 (2025). https://doi.org/10.22331/q-2025-11-14-1909 Zero-noise extrapolation (ZNE) is a widely used quantum error mitigation technique that artificially amplifies circuit noise and then extrapolates the results to the noise-free circuit. A common ZNE approach is Richardson extrapolation, which relies on polynomial interpolation. Despite its simplicity, efficient implementations of Richardson extrapolation face several challenges, including approximation errors from the non-polynomial behavior of noise channels, overfitting due to polynomial interpolation, and exponentially amplified measurement noise. This paper provides a comprehensive analysis of these challenges, presenting bias and variance bounds that quantify approximation errors. Additionally, for any precision $\varepsilon$, our results offer an estimate of the necessary sample complexity. We further extend the analysis to polynomial least squares-based extrapolation, which mitigates measurement noise and avoids overfitting. Finally, we propose a strategy for simultaneously mitigating circuit and algorithmic errors in the Trotter-Suzuki algorithm by jointly scaling the time step size and the noise level. This strategy provides a practical tool to enhance the reliability of near-term quantum computations. We support our theoretical findings with numerical experiments.

Quantum 9, 1908 (2025). https://doi.org/10.22331/q-2025-11-06-1908 We show that all reduced states of nonproduct symmetric Dicke states of arbitrary number of qudits are genuinely multipartite entangled, and of nonpositive partial transpose with respect to any subsystem.

Quantum 9, 1907 (2025). https://doi.org/10.22331/q-2025-11-06-1907 We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and $O(\log n)$ non-Clifford gates. Specifically, for an $n$-qubit state $|\psi\rangle$ prepared with at most $t$ non-Clifford gates, our algorithms use $\mathsf{poly}(n,2^t,1/\varepsilon)$ time and copies of $|\psi\rangle$ to learn $|\psi\rangle$ to trace distance at most $\varepsilon$. The first algorithm for this task is more efficient, but requires entangled measurements across two copies of $|\psi\rangle$. The second algorithm uses only single-copy measurements at the cost of polynomial factors in runtime and sample complexity. Our algorithms more generally learn any state with sufficiently large stabilizer dimension, where a quantum state has stabilizer dimension $k$ if it is stabilized by an abelian group of $2^k$ Pauli operators. We also develop an efficient property testing algorithm for stabilizer dimension, which may be of independent interest.

Quantum 9, 1906 (2025). https://doi.org/10.22331/q-2025-11-06-1906 We present Noise-Directed Adaptive Remapping (NDAR), a heuristic algorithm for approximately solving binary optimization problems by leveraging certain types of noise. We consider access to a noisy quantum processor with dynamics that features a global attractor state. In a standard setting, such noise can be detrimental to the quantum optimization performance. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that transforms the noise attractor into higher-quality solutions. The transformation effectively changes the attractor into a higher-quality solution of the Hamiltonian based on the results of the previous step. The end result is that noise aids variational optimization, as opposed to hindering it. We present an improved Quantum Approximate Optimization Algorithm (QAOA) runs in experiments on Rigetti's quantum device. We report approximation ratios $0.9$-$0.96$ for random, fully connected graphs on $n=82$ qubits, using only depth $p=1$ QAOA with NDAR. This compares to $0.34$-$0.51$ for standard $p=1$ QAOA with the same number of function calls. #### For additional material see posts on X on this paper and Noise-Directed Adaptive Remapping.

Quantum 9, 1905 (2025). https://doi.org/10.22331/q-2025-11-06-1905 Quantum error-correcting codes, such as subspace, subsystem, and Floquet codes, are typically constructed within the stabilizer formalism, which does not fully capture the idea of fault tolerance needed for practical quantum computing applications. In this work, we explore the remarkably powerful formalism of detector error models, which fully captures fault-tolerance at the circuit level. We introduce the detector error model formalism in a pedagogical manner and provide several examples. Additionally, we apply the formalism to three different levels of abstraction in the engineering cycle of fault-tolerant circuit designs: finding robust syndrome extraction circuits, identifying efficient measurement schedules, and constructing fault-tolerant procedures. We enhance the surface code's resistance to measurement errors, devise short measurement schedules for color codes, and implement a more efficient fault-tolerant method for measuring logical operators.

Quantum 9, 1904 (2025). https://doi.org/10.22331/q-2025-11-06-1904 Relaxing the postulates of an axiomatic theory is a natural way to find more general theories, and historically, the discovery of non-Euclidean geometry is a famous example of this procedure. Here, we use this way to extend quantum mechanics by ignoring the $heart$ of Heisenberg's quantum mechanics – We do not assume the existence of a position operator that satisfies the Heisenberg commutation relation, $[\hat x,\hat p]=i\hbar$. The remaining axioms of quantum theory, besides Galilean symmetry, lead to a more general quantum theory with a free parameter $l_0$ of length dimension, such that as $l_0 \to 0$ the theory reduces to standard quantum theory. Perhaps surprisingly, this non-Heisenberg quantum theory, without a priori assumption of the non-commutation relation, leads to a modified Heisenberg uncertainty relation, $\Delta x \Delta p\geq \sqrt{\hbar^2/4+l_0^2(\Delta p)^2}$, which ensures the existence of a minimal position uncertainty, $l_0$, as expected from various quantum gravity studies. By comparing the results of this framework with some observed data, which includes the first longitudinal normal modes of the bar gravitational wave detector AURIGA and the $1S-2S$ transition in the hydrogen atom, we obtain upper bounds on the $l_0$.

Quantum 9, 1903 (2025). https://doi.org/10.22331/q-2025-11-06-1903 The Quantum Approximate Optimisation Algorithm (QAOA) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While QAOA targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood. By introducing means of efficiently and accurately approximating the QAOA optimisation landscape from solution space structures, we derive a new algorithmic variant of unit-depth QAOA for two-level Hamiltonians (including all problems in NP): Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth QAOA for key combinatorial problems, despite reduced computational effort. Our approach is based on proving a long-standing conjecture regarding instance-independent structures in QAOA. By ensuring generality, we link existing empirical observations on QAOA parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation.

Quantum 9, 1902 (2025). https://doi.org/10.22331/q-2025-10-31-1902 Quantum entanglement is a fundamental feature of quantum mechanics, yet certain entangled states that are unsteerable can be classically simulated in steering scenarios, making them unable to exhibit quantum steering. Despite their significance, a systematic comparison of such entangled states has not been explored. In this work, we quantify the resource content of unsteerable quantum states in terms of the amount of shared randomness required to simulate the assemblages they generate in the steering scenario. We rigorously demonstrate that the simulation cost is unbounded even for certain unsteerable two-qubit states. Moreover, the simulation cost of entangled two-qubit states is always strictly larger than that for any separable state. A significant portion of our results rests on the relationship between the simulation cost of two-qubit Werner states and that of noisy spin measurements. Using noisy spin measurements as our central example, we also investigate the minimum number of outcomes a parent measurement requires to simulate a given set of compatible measurements. Although certain continuous measurement families admit a finite-outcome parent measurement, we identify scenarios where the simulation cost is unbounded. Our results establish previously unknown lower bounds and upper bounds on the shared randomness simulation cost, supported by connections between the simulation cost of noisy spin measurements and various geometric inequalities, including ones from the zonotope approximation problem in Banach space theory.

Quantum 9, 1901 (2025). https://doi.org/10.22331/q-2025-10-31-1901 Several quantum and classical Monte Carlo algorithms for Betti Number Estimation (BNE) on clique complexes have recently been proposed, though it is unclear how their performances compare. We review these algorithms, emphasising their common Monte Carlo structure within a new modular framework. We derive upper bounds for the number of samples needed to reach a given level of precision, and use them to compare these algorithms. By recombining the different modules, we create a new quantum algorithm with an exponentially-improved dependence in the sample complexity. We run classical simulations to verify convergence within the theoretical bounds and observe the predicted exponential separation, even though empirical convergence occurs substantially earlier than the conservative theoretical bounds.

Quantum 9, 1900 (2025). https://doi.org/10.22331/q-2025-10-31-1900 We introduce the fermionic satisfiability problem, Fermionic $k$-SAT: this is the problem of deciding whether there is a fermionic state in the null-space of a collection of fermionic, parity-conserving, projectors on $n$ fermionic modes, where each fermionic projector involves at most $k$ fermionic modes. We prove that this problem can be solved efficiently classically for $k=2$. In addition, we show that deciding whether there exists a satisfying assignment with a given fixed particle number parity can also be done efficiently classically for Fermionic 2-SAT: this problem is a quantum-fermionic extension of asking whether a classical 2-SAT problem has a solution with a given Hamming weight parity. We also prove that deciding whether there exists a satisfying assignment for particle-number-conserving Fermionic 2-SAT for some given particle number is NP-complete. Complementary to this, we show that Fermionic 9-SAT is QMA$_1$-hard.

Quantum 9, 1899 (2025). https://doi.org/10.22331/q-2025-10-29-1899 We investigate multi-mode GKP (Gottesman–Kitaev–Preskill) quantum error-correcting codes from a geometric perspective. First, we construct their moduli space as a quotient of groups and exhibit it as a fiber bundle over the moduli space of symplectically integral lattices. We then establish the Gottesman–Zhang conjecture for logical GKP Clifford operations, showing that all such gates arise from parallel transport with respect to a flat connection on this space. Specifically, non-trivial Clifford operations correspond to topologically non-contractible paths on the space of GKP codes, while logical identity operations correspond to contractible paths.

Quantum 9, 1898 (2025). https://doi.org/10.22331/q-2025-10-29-1898 We present Learning-Driven Annealing (LDA), a framework that links individual quantum annealing evolutions into a global solution strategy to mitigate hardware constraints such as short annealing times and integrated control errors. Unlike other iterative methods, LDA does not tune the annealing procedure (e.g. annealing time or annealing schedule), but instead learns about the problem structure to adaptively modify the problem Hamiltonian. By deforming the instantaneous energy spectrum, LDA suppresses transitions into high-energy states and focuses the evolution into low-energy regions of the Hilbert space. We demonstrate the efficacy of LDA by developing a hybrid quantum-classical solver for large-scale spin glasses. The hybrid solver is based on a comprehensive study of the internal structure of spin glasses, outperforming other quantum and classical algorithms (e.g., reverse annealing, cyclic annealing, simulated annealing, Gurobi, Toshiba's SBM, VeloxQ and D-Wave hybrid) on 5580-qubit problem instances in both runtime and lowest energy. LDA is a step towards practical quantum computation that enables today's quantum devices to compete with classical solvers.

Quantum 9, 1897 (2025). https://doi.org/10.22331/q-2025-10-28-1897 Quantum error correction plays a prominent role in the realization of quantum computation, and quantum low-density parity-check (qLDPC) codes are believed to be practically useful stabilizer codes. While qLDPC codes are defined to have constant weight parity-checks, the weight of these parity checks could be large constants that make implementing these codes challenging. Large constants can also result in long syndrome extraction times and bad error propagation that can impact error correction performance. Hastings recently introduced weight reduction techniques for qLDPC codes that reduce the weight of the parity checks as well as the maximum number of checks that acts on any data qubit. However, the fault tolerance of these techniques remains an open question. In this paper, we analyze the effective distance of the weight-reduced code when single-ancilla syndrome extraction circuits are considered for error correction. We prove that there exists single-ancilla syndrome extraction circuits that largely preserve the effective distance of the weight-reduced qLDPC codes. In addition, we also show that the distance balancing technique introduced by Evra et al. [17] preserves effective distance. As a corollary, our result shows that higher-dimensional hypergraph product (HGP) codes, also known as homological product codes corresponding to the product of 1-complexes, have no troublesome hook errors when using any single-ancilla syndrome extraction circuit.

Quantum 9, 1896 (2025). https://doi.org/10.22331/q-2025-10-28-1896 We investigate the dependence of physical observable of open quantum systems with Bosonic bath on the bath correlation function. We provide an error estimate of the difference of physical observable induced by the variation of bath correlation function, based on diagrammatic and combinatorial arguments. This gives a mathematically rigorous justification of the result in [6].

Quantum 9, 1895 (2025). https://doi.org/10.22331/q-2025-10-28-1895 A path for efficient classical simulation of the DQC1 circuit that estimates the trace of an implementable unitary under the zero discord condition [17] is presented. This result reinforces the status of non-classical correlations quantified by quantum discord and related measures as the key resource enabling exponential speedups in mixed state quantum computation.