Accepted Papers

Abstract: Quantum learning encounters fundamental challenges when estimating non-linear properties, owing to the inherent linearity of quantum mechanics. Although recent advances in single-copy randomized measurement protocols have achieved optimal sample complexity for specific tasks like state purity estimation, generalizing these protocols to estimate broader classes of non-linear properties without sacrificing optimality remains an open problem. In this work, we introduce the observable-driven randomized measurement (ORM) protocol enabling the estimation of Tr(Oρ^2) for an arbitrary observable O---an essential quantity in quantum computing and many-body physics. We establish an upper bound for ORM's sample complexity and show its optimality for observables with a large trace-norm, including Pauli and local observables, closing a gap in the literature. For these observables, ORM admits an efficient implementation with Clifford circuits. Numerical experiments validate that ORM requires substantially fewer state samples to achieve the same precision compared to classical shadows. Additionally, we introduce a braiding randomized measurement protocol for multiple low-rank non-linear observables, reducing circuit complexities in practical applications.

Abstract: We prove that the linearity and positivity of quantum mechanics impose general restrictions on quantum purification, unveiling a new fundamental limitation of quantum information processing. In particular, no quantum operation can transform a finite number of copies of an unknown quantum state or channel into a pure state or channel that depends on the input, thereby ruling out an important form of universal purification in both static and dynamical settings. Relaxing the requirement of exact pure output, we further extend our result to establish quantitative sample complexity bounds for approximate purification, independent of any task details or operational constraints. To illustrate the practical consequences of this principle, we examine the task of approximately preparing pure dilation and, for the first time, prove an exponential lower bound on the required sample complexity.

Abstract: We introduce a mixed-state magic criterion, the Triangle Criterion, which plays a role for magic analogous to the Positive Partial Transposition (PPT) criterion for entanglement: it combines strong detection capability, a clear geometric interpretation, and an operational link to magic distillation. Using this criterion, we uncover several new features of multi-qubit magic distillation and detection. We prove that genuinely multi-qubit magic distillation protocols are strictly more powerful than all single-qubit schemes by showing that the Triangle Criterion is not stable under tensor products, in sharp contrast to the PPT criterion. Moreover, we show that, with overwhelming probability, multi-qubit magic states with relatively low rank cannot be distilled by any single-qubit distillation protocol. We derive an upper bound on the minimal purity of magic states, which is conjectured to be tight with both numerical and constructive evidences. Using this minimal-purity result, we predict the existence of unfaithful magic states, namely states that cannot be detected by any fidelity-based magic witness, and reveal fundamental limitations of mixed-state magic detection in any single-copy scheme.

Abstract: We present two deterministic compilation algorithms for single-qutrit unitaries with $\mathcal{O}(\log \frac{1}{\varepsilon})$ gate depth. Each algorithm selects a nearby approximation to the target unitary and then exactly synthesizes the approximation over the Clifford + $\mathbf{R}$ basis. The first algorithm exhaustively searches over the group; while the second algorithm searches only for Householder reflections. The exhaustive search algorithm yields an average $\mathbf{R}$ count of $\yintm + \slopem \log_{10}(1 / \varepsilon)$, albeit with a time complexity of $\mathcal{O}(\varepsilon^{\pgfmathprintnumber[fixed,precision=2]{\fullcomplexity}})$. The Householder search algorithm results in a larger average $\mathbf{R}$ count of $\yint + \slope \log_{10}(1 / \varepsilon)$ at a reduced time complexity of $\mathcal{O}(\varepsilon^{\pgfmathprintnumber[fixed,precision=2]{\householdercomplexity}})$, greatly extending the reach in $\varepsilon$. These costs correspond asymptotically to 35\% and 69\% more non-Clifford gates compared to synthesizing the same unitary with two qubits. Such initial results are encouraging for using the $\mathbf{R}$ gate as the non-transversal gate for qutrit-based computation.

Abstract: We introduce magic-augmented Clifford circuits -- architectures in which Clifford circuits are preceded and/or followed by constant-depth circuits of non-Clifford (``magic") gates -- as a resource-efficient way to realize approximate $k$-designs, with reduced circuit depth and usage of magic. We prove that shallow Clifford circuits, when augmented with constant-depth circuits of magic gates, can generate approximate unitary and state $k$-designs with $\epsilon$ relative error. The total circuit depth for these constructions on $N$ qubits is $O(\log (N/\epsilon)) +2^{O(k\log k)}$ in one dimension and $O(\log\log(N/\epsilon))+2^{O(k\log k)}$ in all-to-all circuits using ancillas, which improves upon previous results for small $k \geq 4$. Furthermore, our construction of relative-error state $k$-designs only involves states with strictly local magic. The required number of magic gates is parametrically reduced when considering $k$-designs with bounded additive error. As an example, we show that shallow Clifford circuits followed by $O(k^2)$ single-qubit magic gates, independent of system size, can generate an additive-error state $k$-design in optimal depth. We develop a classical statistical mechanics description of our random circuit architectures, which provides a quantitative understanding of the required depth and number of magic gates for additive-error state $k$-designs. We also prove no-go theorems for various architectures to generate designs with bounded relative error.

Abstract: The conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results: \begin{itemize} \item We prove a $\Omega(\log \R_{0,A\rightarrow B}(f)+\log \R_{0,B\rightarrow A}(f))$ lower bound on quantum CDS where $\R_{0,A\rightarrow B}(f)$ is the classical one-way communication complexity with perfect correctness. \item We prove a lower bound on quantum CDS in terms of two round, public coin, two-prover interactive proofs. \item For perfectly correct CDS, we give a separation for a promise version of the not-equals function, showing a quantum upper bound of $O(\log n)$ and classical lower bound of $\Omega(n)$. \item We give a logarithmic upper bound for quantum CDS on forrelation, while the best known classical algorithm is linear. We interpret this as preliminary evidence that classical and quantum CDS are separated even with correctness and security error allowed. \end{itemize} We also give a separation for classical and quantum private simultaneous message passing for a partial function, improving on an earlier relational separation. Our results use novel combinations of techniques from non-local quantum computation and communication complexity.

Abstract: Motivated by recent advances in digital quantum simulation and the overall prospect of solving correlated many-electron problems using quantum algorithms, we design a gate-based quantum circuit that emulates the dynamics of the Kondo impurity model. We numerically determine the impurity magnetization, entanglement between impurity and fermionic sites, and energy as a function of time (i.e., circuit depth) for various initial states and find universal long-time dynamics. We complement the numerical simulations for moderate system size with an asymptotically exact analytical solution that is effective in the limit of large system sizes and for starting states corresponding to a filled Fermi sea. This work opens up the perspective of studying the dynamics of electronic quantum many-body states on quantum chips of the NISQ era.

Abstract: Simulating noiseless quantum dynamics classically faces a fundamental dilemma: tensor-network methods become inefficient as entanglement saturates, while Pauli-truncation approaches typically rely on noise or randomness. To close the gap, we propose the Low-weight Pauli Dynamics (LPD) algorithm that efficiently approximates local observables for short-time dynamics in the absence of noise. We prove that the truncation error admits an average-case bound without assuming randomness, provided that the state is sufficiently entangled. Counterintuitively, entanglement--usually an obstacle for classical simulation--alleviates classical simulation error. We further show that such entangled states can be generated either by tensor-network classical simulation or near-term quantum devices. Therefore, our results establish a rigorous synergy between existing classical simulation methods and provide a complementary route to quantum simulation that reduces circuit depth for long-time dynamics, thereby extending the accessible regime of quantum dynamics.

Abstract: Quantum low-density parity check (qLDPC) codes are among the leading candidates to realize error-corrected quantum memories with low qubit overhead. Potentially high encoding rates and large distance relative to their block size make them appealing for practical suppression of noise in near-term quantum computers. In addition to increased qubit-connectivity requirements compared to more conventional topological quantum error correcting codes, qLDPC codes remain notoriously hard to compute with. In this work, we introduce a construction to implement all Clifford quantum gate operations on the recently introduced lift-connected surface (LCS) codes. These codes can be implemented in a 3D-local architecture and achieve asymptotic scaling $[[n, O(n^{1/3}), O(n^{1/3})]]$. In particular, LCS codes realize favorable instances with small numbers of qubits: For the [[15,3,3]] LCS code, we provide deterministic fault-tolerant (FT) circuits of the logical gate set {H, S, CNOT} based on flag qubits. By adding a procedure for FT magic state preparation, we show quantitatively how to realize an FT universal gate set in d=3 LCS codes. Numerical simulations indicate that our gate constructions can attain pseudothresholds in the range $p_th = 4.8 x 10^{-3} - 1.2 x 10^{-2}$ for circuit-level noise. The schemes use a moderate number of qubits and are therefore feasible for near-term experiments, facilitating progress for fault-tolerant error corrected logic in high-rate qLPDC codes.

Abstract: Classical error-correcting codes are powerful but incompatible with quantum noise, which includes both bit-flips and phase-flips. We introduce Hadamard-based Virtual Error Correction (H-VEC), a protocol that empowers any classical bit-flip code to correct arbitrary Pauli noise with the addition of only a single ancilla qubit and two layers of controlled-Hadamard gates. Through classical post-processing, H-VEC virtually filters the error channel, projecting the noise into pure Y-type errors that are subsequently corrected using the classical code's native decoding algorithm. We demonstrate this by applying H-VEC to the classical repetition code. Under a code-capacity noise model, the resulting protocol not only provides full quantum protection but also achieves an exponentially stronger error suppression (in distance) than the original classical code. The improvements over the surface code are even more pronounced, while using far fewer qubits, simpler checks, and straightforward decoding. There are some limitations to the technique, most notably that H-VEC introduces a sampling overhead due to its post-processing nature. Nonetheless, it represents a fundamentally novel hybrid quantum error correction and mitigation framework that redefines the trade-offs between physical hardware requirements and classical processing for error suppression.

Abstract: The Berry phase is a fundamental quantity for classifying topological phases of matter. We present a new quantum algorithm for Berry phase estimation (BPE) that is both more general than previously known approaches and comes with a rigorous polynomial-time performance guarantee. Moreover, we provide a new circuit-to-Hamiltonian construction that results in a closed loop of parameterized Hamiltonians. Building on these, we prove that a BPE formulation is \BQP-complete when given a guiding state with large overlap with the ground state. This shows the first complexity-theoretic evidence of an exponential quantum speedup for quantum-computational approaches to studying topological phases of matter. We also establish several complexity-theoretic results for BPE, including \textsf{dUQMA}-completeness, \(\mathsf{P}^{\mathsf{dUQMA}[\log]}\)-hardness, and containment in \(\mathsf{P}^{\mathsf{PGQMA}[\log]}\), depending on the BPE setting. Here, \textsf{dUQMA} is a variant of the unique-witness class \textsf{UQMA} that we introduce and remarkably, this \textsf{dUQMA}-complete BPE variant appears to be the first natural problem known to lie in \textsf{UQMA} \(\cap\) \textsf{co-UQMA}.

Abstract: We investigate the computational hardness of estimating the quantum α-Rényi entropy SˆR_α(ρ) = ln Tr(ρˆα)/(1−α) and the quantum q-Tsallis entropy SˆT_q(ρ) = 1−Tr(ρˆq)/(q−1) , both converging to the von Neumann entropy as the order approaches 1. The promise problems Quantum α-Rényi Entropy Approximation (RényiQEA_α) and Quantum q-Tsallis Entropy Approximation (TsallisQEA_q) ask whether SˆR_α(ρ) or SˆT_q(ρ), respectively, is at least τ_Y or at most τ_N, where τ_Y−τ_N is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 1) and some cases of the quantum q-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real orders, the rank-2 variants Rank2RényiQEA_α and Rank2TsallisQEA_q are BQP-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), our results imply: - For all real order α>0 and 0 <q≤1, LowRankRényiQEA_α and LowRankTsallisQEA_q are BQP-complete, where both are restricted versions of RényiQEA_α and TsallisQEA_q with ρ of polynomial rank. - For all real order q>1, TsallisQEA_q is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the α-Rényi or q-Tsallis binary entropies at different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.

Abstract: Noisy intermediate-scale quantum (NISQ) devices pave the way to implement quantum algorithms that exhibit supremacy over their classical counterparts. Due to the intrinsic noise and decoherence in the physical system, NISQ computations are naturally modeled as large-size but low-depth quantum circuits. Practically, to execute such quantum circuits, we need to pass commands to a programmable quantum computer. Existing programming approaches, dedicated to generic unitary transformations, are inefficient in terms of the computational resources under the low-depth assumption and remain far from satisfactory. As such, to realize NISQ algorithms, it is crucial to find an efficient way to program low-depth circuits as the qubit number $N$ increases. Here, we investigate the gate complexity and the size of quantum memory (known as the program cost) required to program low-depth brickwork circuits. We unveil a $\sim N \poly \log N$ worst-case program cost of universal programming of low-depth brickwork circuits in the large $N$ regime, which is a tight characterization. Moreover, we analyze the trade-off between the cost of describing the layout of local gates and the cost of programming them to the targeted unitaries via the light-cone argument. Our findings suggest that faithful gate-wise programming is optimal in the low-depth regime.

Abstract: The energy cost of erasing quantum states depends on our knowledge of the states. We show that learning algorithms can acquire such knowledge to erase many copies of an unknown state at the optimal energy cost. This is proved by showing that learning can be made fully reversible and has no fundamental energy cost itself. With simple counting arguments, we relate the energy cost of erasing quantum states to their complexity, entanglement, and magic. We further show that the constructed erasure protocol is computationally efficient when learning is efficient. Conversely, under standard cryptographic assumptions, we prove that the optimal energy cost cannot be achieved efficiently in general. These results also enable efficient work extraction based on learning. Together, our results establish a concrete connection between quantum learning theory and thermodynamics, highlighting the physical significance of learning processes and enabling provably-efficient learning-based protocols for thermodynamic tasks.

Abstract: Quantum simulation of fermionic systems is a leading application of quantum computers. One promising approach is to represent fermions with qubits via fermion-to-qubit mappings. In this work, we present high-distance fermion-to-qubit stabilizer codes for simulating 2D and 3D fermionic systems. These codes achieve arbitrarily large code distances while keeping stabilizer weights constant. They also preserve locality by mapping local fermionic operators to local qubit operators at any fixed distance. Notably, our 3D construction is the first to simultaneously achieve high distance, constant stabilizer weights, and locality preservation. Our construction is based on concatenating a small-distance 2D or 3D fermion-to-qubit code with a high-distance fermionic color code. Together, these features provide a robust and scalable pathway to quantum simulation of fermionic systems.

Abstract: We construct an explicit transition matrix that exactly describes stabilizer-code dynamics under circuit-level stochastic Pauli noise. The matrix is expressed in a code-adapted basis that captures probability flow between logical and error states. For quantum error detection (QED), we incorporate post-selection by aggregating rejected outcomes into an absorbing state, so that a single transition matrix represents a full clock cycle of gates, syndrome extraction, and post-selection. Additionally, we characterize when protocol symmetries permit exact lumping to simpler, more interpretable models. The transition matrix framework enables direct application of classical stochastic-matrix techniques to analyze multi-cycle QED protocols. First, we prove that emergent logical non-Markovianity originates from QED-check imperfections at leading order, and quantify the accepted leakage injection that causes it. Second, we express leading-order QED efficiency as a function of check frequency in terms of physically meaningful parameters, and prove that less frequent checks improve efficiency in the perturbative regime. More broadly, the transition-matrix formalism provides both an analytical foundation for QED analysis and an interpretable tool for understanding code behavior under realistic noise.

Abstract: In this work, we investigate the incompatibility of random quantum measurements. Most previous work has focused on characterizing the maximal amount of white noise that any fixed number of incompatible measurements with a fixed number of outcomes in a fixed dimension can tolerate before becoming compatible. This can be used to quantify the maximal amount of incompatibility available in such systems. The present article investigates the incompatibility of several classes of random measurements, i.e., the generic amount of incompatibility available. In particular, we show that for an appropriate choice of parameters, both random dichotomic projective measurements and random basis measurements are close to being maximally incompatible. We use the technique of incompatibility witnesses to certify incompatibility and combine it with tools from random matrices and free probability.

Abstract: As quantum computing machines move towards the utility regime, it is essential that users are able to verify their delegated quantum computations with security guarantees that are (i) robust to noise, (ii) composable with other secure protocols, and (iii) exponentially stronger as the number of resources dedicated to security increases. Previous works that achieve these guarantees and provide modularity necessary to optimization of protocols to real-world hardware are most often expressed in the Measurement-Based Quantum Computation (MBQC) model. This leaves architectures based on the circuit model -- in particular those using the Magic State Injection (MSI) -- with fewer options to verify their computations or with the need to compile their circuits in MBQC leading to overheads. This paper introduces a family of noise robust, composable and efficient verification protocols for Clifford + MSI circuits that are secure against arbitrary malicious behavior. This family contains the verification protocol of Broadbent (ToC, 2018), extends its security guarantees while also bridging the modularity gap between MBQC and circuit-based protocols, and reducing quantum communication costs. As a result, it opens the prospect of rapid implementation for near-term quantum devices. Our technique is based on a refined notion of blindness, called magic-blindness, which hides only the injected magic states -- the sole source of non-Clifford computational power. This enables verification by randomly interleaving computation rounds with classically simulable, magic-free test rounds, leading to a trap-based framework for verification. As a result, circuit-based quantum verification attains the same level of security and robustness previously known only in MBQC. It also optimizes the quantum communication cost as transmitted qubits are required only at the locations of state injection.

Abstract: The indistinguishability of many bosons undergoing passive linear transformations followed by number basis measurements is fully characterized by the visible state of the bosons. However, measuring all the parameters in the visible state is experimentally demanding. In this work, we seek to perform partial characterization of the visible state by measuring properties of it that are available after randomization. First we study the case where the occupied visible modes are randomly permuted, and second we study the case where Haar random linear optical unitaries are applied. In each case, we find that the generalized bunching probability -- which is the probability that all the input bosons arrive in a given subset of the output modes -- obeys monotonicity with respect to some partial order of distinguishability of the input bosons. As an intermediate result, we show that Lieb's permanental-dominance conjecture for immanants is equivalent to the following statement: for states that are invariant under permutations of the occupied visible modes, the generalized bunching probability is maximized when the bosons are perfectly indistinguishable. We also prove that a consequence of the monotonicity of the generalized bunching probability after Haar averaging is that this average is maximized when the bosons are perfectly indistinguishable. Finally, we discuss applications of our results to thermometry of cold-atom systems.

Abstract: Quantum algorithms promise transformative speedups, yet their practical impact is often limited by prohibitively deep circuits, with two recurring sources of depth: costly preparation of structured input states and the execution of subroutines based on truncated series approximations. We introduce a unified, resource-efficient paradigm that uses classical randomness as an algorithmic primitive to improve accuracy–depth trade-offs. For realistic states with hierarchical amplitude structure, we propose a randomized state-preparation protocol that probabilistically amplifies small amplitudes using ensembles of low-complexity circuits, reducing the number of amplitudes that must be encoded and achieving up to 99% reductions in CNOT and T-gate counts in simulations on LiH wavefunctions and power-law decay states. Target quantum algorithms, we develop Randomized Truncated Series, a generic acceleration principle for any quantum algorithm built from truncated series, which quadratically suppresses truncation error while enabling continuous tuning of the effective truncation order via random mixing of shallow circuits. Together, these results broaden the regime where end-to-end quantum advantage is feasible on near-term and early fault-tolerant hardware.

Abstract: We show the existence of an MA-complete homology problem for a certain subclass of simplicial complexes. The problem is defined through a new concept of orientability of simplicial complexes that we call a ``uniform orientable filtration'', which is related to sign-problem freeness in homology. The containment in MA is achieved through the design of new, higher-order random walks on simplicial complexes associated with the filtration. For the MA-hardness, we design a new gadget with which we can reduce from an MA-hard stoquastic satisfiability problem. Therefore, our result provides the first natural MA-complete problem for higher-order random walks on simplicial complexes, combining the concepts of topology, persistent homology, and quantum computing.

Abstract: The complexity class Quantum Statistical Zero-Knowledge (𝖰𝖲𝖹𝖪), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound 𝖰𝖨𝖯(𝟤)∩co-𝖰𝖨𝖯(𝟤), which was simplified following the inclusion 𝖰𝖨𝖯(𝟤)⊆𝖯𝖲𝖯𝖠𝖢𝖤 established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, 𝖰𝖨𝖯(𝟤) denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and co-𝖰𝖨𝖯(𝟤) denotes the complement of 𝖰𝖨𝖯(𝟤). We slightly improve this upper bound to 𝖰𝖨𝖯(𝟤)∩co-𝖰𝖨𝖯(𝟤) with a quantum linear-space honest prover. A similar improvement also applies to the upper bound for the non-interactive variant 𝖭𝖨𝖰𝖲𝖹𝖪. Our main techniques are an algorithmic version of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).

Abstract: Quantum information processing is limited, in practice, to efficiently implementable operations. This motivates the study of quantum divergences and entropies that preserve their operational meaning while faithfully capturing computational constraints. In this joint submission, we introduce a mathematical framework for computational quantum information theory from which computational divergences and established computational entropies naturally arise. Within this framework, we define a computational max-divergence and computational measured Rényi divergences. We relate these quantities to efficient hypothesis testing and use them to analyze computational resource theories such as entanglement. We further connect the new computational max-divergence to the previously established computational min-entropy and computational hypothesis testing relative entropy. In particular, we show that the computational max-divergence serves as a parent quantity for the computational min-entropy, thereby endowing the computational max-divergence with an operational meaning. Moreover, we prove that the computational hypothesis testing relative entropy is approximately characterized by a smoothed version of the computational max-divergence. Together, these results extend well-known information-theoretic relationships to the computational setting and unify several operationally-motivated computational quantities.

Abstract: Flow models are a cornerstone of modern machine learning. They are generative models that progressively transform probability distributions according to learned dynamics. Specifically, they learn a continuous-time Markov process that efficiently maps samples from a simple source distribution into samples from a complex target distribution. We show that these models are naturally related to the Schrödinger equation, for an unusual Hamiltonian on continuous variables. Moreover, we prove that the dynamics generated by this Hamiltonian can be efficiently simulated on a quantum computer. Together, these results give a quantum algorithm for preparing coherent encodings (a.k.a., qsamples) for a vast family of probability distributions—namely, those expressible by flow models—by reducing the task to an existing classical learning problem, plus Hamiltonian simulation. For statistical problems defined by flow models, such as mean estimation and property testing, this enables the use of quantum algorithms tailored to qsamples, which may offer advantages over classical algorithms based only on samples from a flow model. More broadly, these results reveal a close connection between state-of-the-art machine learning models, such as flow matching and diffusion models, and one of the main expected capabilities of quantum computers: simulating quantum dynamics.

Abstract: We study the performance of Decoded Quantum Interferometry (DQI) on typical instances of MAX-k-XOR-SAT when the transpose of the constraint matrix is drawn from a standard ensemble of LDPC parity check matrices. We prove that if the decoding step of DQI corrects up to the best known efficient decoding threshold for LDPC codes, then DQI is obstructed by a topological feature of the near-optimal space of solutions known as the overlap gap property (OGP). As the OGP is widely conjectured to exactly characterize the asymptotic performance of state-of-the-art classical algorithms, this result suggests that DQI has no quantum advantage in optimizing unstructured MAX-k-XOR-SAT instances for large k without significant asymptotic advances in efficient LDPC decoders. We also give numerical evidence supporting this conjecture by showing that approximate message passing (AMP)—a classical algorithm conjectured to saturate the OGP threshold—outperforms DQI on a related ensemble of MAX-k-XOR-SAT instances. Finally, we prove that depth-1 QAOA outperforms DQI at sufficiently large k under the same decoding threshold assumption. Our result follows by showing that DQI is approximately Lipschitz under the quantum Wasserstein metric over many standard ensembles of codes. We then prove that MAX-k-XOR-SAT exhibits both an OGP and a related topological obstruction known as the chaos property; this is the first known OGP threshold for MAX-k-XOR-SAT at fixed k, which may be of independent interest. Finally, we prove that both of these topological properties inhibit approximately Lipschitz algorithms such as DQI from optimizing MAX-k-XOR-SAT to large approximation ratio with substantial probability.

Abstract: We present a machine learning framework to study the dynamics of entropy vectors and quantum resources, including entanglement and magic, focusing on violations of entropy inequalities. Using a reinforcement learning agent formulated as a Markov decision process, we identify quantum circuits that optimally navigate the entropy vector space to generate violations of Ingleton's inequality. We complement this approach with a classical optimization algorithm to produce arbitrary numbers of Ingleton-violating states, with tunable degrees of violation, and empirically determine the maximal attainable violation for Ingleton's inequality. Our analysis reveals characteristic patterns of quantum resources that accompany Ingleton violation. A comprehensive statistical analysis shows that Ingleton-violating states occupy sharply-defined, isolated regions of the Hilbert space, and are extremely rare. Together, these results establish a unified computational toolkit for studying entropy vector dynamics, tracking quantum resource evolution, and engineering circuits with controlled information-theoretic features.

Abstract: Practical implementation of quantum error correction is currently limited by near-term quantum hardware. In contrast, quantum error mitigation has demonstrated strong promise for improving the performance of noisy quantum circuits without the requirement of full fault tolerance. In this work, we develop a hybrid error suppression protocol that integrates Pauli twirling, probabilistic error cancellation, and the [[n,n−2,2]] quantum error detecting code. In addition, to reduce overhead from error mitigation components of our method, we modify Pauli twirling by lowering the number of Pauli operators in the twirling set, and apply probabilistic error cancellation at the end of the encoded circuit to remove undetectable errors. Finally, we demonstrate our protocol on a non-Clifford variational quantum eigensolver circuit that estimates the ground state energy of $H_2$ using both qiskit AerSimulator and the IBM quantum processor ibm brussels.

Abstract: The monogamy of mutual information (MMI) is a quantum entropy inequality that enforces the non-positivity of tripartite information. We investigate the failure of MMI in graph states as a forbidden-subgraph phenomenon, conjecturing that every MMI-violating graph state is local-Clifford equivalent to one whose graph contains a four-star subgraph. We construct a family of star-like graphs whose states fail a specific class of MMI instances, and extend this analysis to general star topologies. Deriving adjacency matrix constraints that fix the MMI evaluation for these instances and interpreting them physically, we prove the forbidden-subgraph conjecture for this family of graphs. Finally, through an exhaustive search over graph representatives for all 8-qubit stabilizer entropy vectors, we establish that MMI failure is not reducible to the cases within our scope.

Abstract: Characterizing increasingly complex quantum systems is a central task in quantum information science, yet experimental costs often scale prohibitively with system size. Certifying key properties---such as entanglement, circuit complexity, and quantum magic---using simple local measurements is highly desirable but challenging. In this work, we introduce a highly general certification framework based on a physical phenomenon that we call localizable quantumness: for generic many-body states, essential quantum properties are robustly preserved within the projected ensembles on small subsystems after performing local projective measurements on the rest of the system. Leveraging this insight, we develop certification protocols that certify global properties by witnessing them on a small, accessible subsystem. Our method dramatically reduces experimental cost by relying solely on local Pauli measurements, while achieving constant sample complexity, constant-level robustness, and soundness for mixed states---exponentially improving the sample complexity and overcoming major limitations of previous methods. We further present a random-basis variant to certify state fidelity, with numerical evidence strongly suggesting it maintains constant sample complexity and robustness for generic states, representing a substantial improvement over existing methods. Our results provide a practical, scalable toolkit for certifying large-scale quantum processors and offer a novel lens for understanding complex many-body quantum systems.

Abstract: Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).

Abstract: We present a framework where the inherent physical imperfections of Gottesman-Kitaev-Preskill (GKP) states—specifically the finite-energy envelopes required for normalizability—are harnessed as a resource for universal quantum computation. Contrary to the standard view that treats the finite squeezing of GKP states solely as a source of error to be corrected, we demonstrate that ``Fock damping'' enables the implementation of non-Clifford gates using only Gaussian operations and homodyne detection. We prove a dichotomy: while ideal (infinite energy) stabilizer GKP states are restricted to Clifford operations under Gaussian operation and measurement, realistic (finite energy) states allow for projection onto non-Pauli eigenstates, including magic states. At experimentally realistic squeezing levels, our protocol yields magic states with fidelities sufficient for distillation with success probabilities exceeding 40\%. This resolves an open question regarding the universality of realistic GKP circuits without requiring auxiliary vacuum modes or resource greedy GKP error correction.

Abstract: Determining and verifying an object's position is a fundamental task with broad practical relevance. We propose a secure quantum ranging protocol that combines quantum ranging with quantum position verification (QPV). Our method achieves Heisenberg-limited precision in position estimation while simultaneously detecting potential cheaters. Two verifiers each send out a state that is entangled in frequency space within a single optical mode. An honest prover only needs to perform simple beam-splitter operations, whereas cheaters are allowed to use arbitrary linear optical operations, one ancillary mode, and perfect quantum memories—though without access to entanglement. Our approach considers a previously unstudied security aspect to quantum ranging. It also provides a framework to quantify the precision with which a prover's position can be verified in QPV, which previously has been assumed to be infinite. We further discuss the near-term experimental implementation of our scheme and propose how a better-than-classical advantage can be observed using existing photonic technologies.

Abstract: Imaging thermal sources naturally yields Gaussian states at the receiver, raising the question of whether Gaussian measurements can perform optimally in quantum imaging. In this work, we establish no-go theorems on the performance of Gaussian measurements for imaging thermal sources in the limit of mean photon number per temporal mode $\epsilon \to 0$ or source size $L \to 0$. We show that non-Gaussian measurements can outperform any Gaussian measurement in the scaling of the estimation variance with $\epsilon$ (or $L$). We also present several examples to illustrate the no-go results.

Abstract: Efficient simulation of quantum dynamics with time-dependent Hamiltonians is important not only for time-varying systems but also for time-independent Hamiltonians in the interaction picture. Such simulations are more challenging than their time-independent counterparts due to the complexity introduced by time ordering. Existing algorithms that aim to capture commutator-based scaling either exhibit polynomial cost dependence on the Hamiltonian’s time derivatives or are limited to low-order accuracy. In this work, we establish the general commutator-scaling error bounds for the truncated Magnus expansion at arbitrary order, where only Hamiltonian terms appear in the nested commutators, with no time derivatives involved. Building on this analysis, we design a high-order quantum algorithm with explicit circuit constructions. The algorithm achieves cost scaling with the commutator structure in the high-precision regime and depends only logarithmically on the Hamiltonian’s time variation, making it efficient for general time-dependent settings, including the interaction picture.

Abstract: Recent advances in quantum error-correction (QEC) have shown that it is often beneficial to understand fault-tolerance as a dynamical process, a circuit with redundant measurements that help correct errors, rather than as a static code equipped with a syndrome extraction circuit. Spacetime codes have emerged as a natural framework to understand error correction at the circuit level while leveraging the traditional QEC toolbox. Here, we introduce a framework based on chain complexes and chain maps to model spacetime codes and transformations between them. We show that stabilizer codes, quantum circuits, and decoding problems can all be described using chain complexes, and that the equivalence of two spacetime codes can be characterized by specific maps between chain complexes, the fault-tolerant maps, that preserve the number of encoded qubits, fault distance, and minimum-weight decoding problem. As an application of this framework, we extend the foliated cluster state construction from stabilizer codes to any spacetime code, showing that any Clifford circuit can be transformed into a measurement-based protocol with the same fault-tolerant properties. To this protocol, we associate a chain complex which encodes the underlying decoding problem, generalizing previous cluster state complex constructions. Our method enables the construction of cluster states from non-CSS, subsystem, and Floquet codes, as well as from logical Clifford operations on a given code.

Abstract: We present a universal framework for simulating $N$-dimensional linear It\^o stochastic differential equations (SDEs) on quantum computers with additive or multiplicative noises. Building on a unitary dilation technique, we establish a rigorous correspondence between the general linear SDE \[ dX_t = A(t) X_t\,dt + \sum_{j=1}^J B_j(t)X_t\,dW_t^j \] and a Stochastic Schr\"odinger Equation (SSE) on a dilated Hilbert space. Crucially, this embedding is pathwise exact: the classical solution is recovered as a projection of the dilated quantum state for each fixed noise realization. We demonstrate that the resulting SSE is {naturally implementable} on digital quantum processors, where the stochastic Wiener increments correspond directly to measurement outcomes of ancillary qubits. Exploiting this physical mapping, we develop two algorithmic strategies: (1) a trajectory-based approach that uses sequential weak measurements to realize efficient stochastic integrators, including a second-order scheme, and (2) an ensemble-based approach that maps moment evolution to a deterministic Lindblad quantum master equation, enabling simulation without Monte Carlo sampling. We provide error bounds based on a stochastic light-cone analysis and validate the framework with numerical simulations.

Abstract: Accurate calculation of spin-state energy gaps is central to spin chemistry. The novel Quantum Phase Difference Estimation (QPDE) algorithm enables direct computation of energy gaps on a quantum computer. However, the required quantum circuits are typically too deep for noisy intermediate-scale quantum (NISQ) devices. In this study, as an initial step toward practical calculations for strongly correlated molecular multi-spin systems,we applied QPDE to two- and three-spin Heisenberg Hamiltonians with various geometries and coupling strengths, including symmetric, asymmetric, spin-frustrated and non-frustrated configurations. We found that the quantum circuit for the time-evolution operator achieves constant depth due to its matchgate-like structure, making it well-suited for NISQ implementation. Proof-of-principle hardware demonstrations using an IBM quantum processor yielded 85–93% accuracy in determining spin-state energy gaps.

Abstract: We establish tight connections between entanglement entropy and the approximation error in Trotter-Suzuki product formulas for Hamiltonian simulation. For systems governed by local Hamiltonians with bounded entanglement entropy $\Smax$, we prove that the first-order Trotter error scales as $\BigO(t^2 \Smax \polylog(n)/r)$ rather than the worst-case $\BigO(t^2 n/r)$, where $n$ is the system size and $r$ is the number of Trotter steps. This yields an exponential improvement for area-law entangled systems where $\Smax = \BigO(\log n)$. We further establish a separation result showing that volume-law entangled systems fundamentally require $\Omega(\sqrt{n})$ more Trotter steps than area-law systems to achieve the same precision. Our analysis combines Lieb-Robinson bounds, tensor network methods, and novel commutator-entropy inequalities.

Abstract: We demonstrate that in quantum many-body systems, local arrows of time can differ from the global time $t$ induced by Hamiltonian evolution. That is, within a quantum many-body system, the flow of time can be relative to each observer or by proxy each local subsystem. We provide a definition of local arrows of time in quantum many-body systems, and explain their relation to spacetime quantum entropies. Then we give a variety of numerical and analytical examples which explore different ways in which local arrows of time can manifest in quantum many-body dynamics, including exotic arrows of time arising from quantum thermalization and quantum error correction. We find that even in standard Hamiltonian dynamics, the arrow of time is not strictly temporal; it develops spatial components that deviate from the local entropy gradient.

Abstract: The potential of quantum computers to outperform classical ones in practically useful tasks remains challenging in the near term due to scaling limitations and high error rates of current quantum hardware. While quantum error correction (QEC) offers a clear path towards fault tolerance, overcoming the scalability issues will take time. Early applications will likely rely on QEC combined with quantum error mitigation (QEM). We introduce a QEM scheme against both compilation errors and logical-gate noise that is circuit-, QEC code-, and compiler-agnostic. The scheme builds on quasi-probability methods and uses information about the circuit's gates' compilations to attain an unbiased estimation of noiseless expectation values incurring a constant sample-complexity overhead. Moreover, it features maximal circuit size and code distance both independent of the target precision, in contrast to strategies based on QEC alone. We formulate the mitigation procedure as a linear program, demonstrate its efficacy through numerical simulations, and illustrate it for estimating the Jones polynomials of knots. Our method significantly reduces quantum resource requirements for high-precision estimations, offering a practical route towards fault-tolerant quantum computation with precision-independent overheads for fixed circuit complexity and code distance.

Abstract: Fine-grained spectral properties of quantum Hamiltonians, including both eigenvalues and their multiplicities, provide useful information for characterizing many-body quantum systems as well as for understanding phenomena such as topological order. Extracting such information with small additive error is BQP-complete in the worst case. In this work, we introduce QFAMES (Quantum Filtering and Analysis of Multiplicities in Eigenvalue Spectra), a quantum algorithm that efficiently identifies clusters of closely spaced dominant eigenvalues and determines their multiplicities under physically motivated assumptions, which allows us to bypass worst-case complexity barriers. QFAMES also enables the estimation of observable expectation values within targeted energy clusters, providing a powerful tool for studying quantum phase transitions and other physical properties. We validate the effectiveness of QFAMES through numerical demonstrations, including its applications to characterizing quantum phases in the transverse-field Ising model and estimating the ground-state degeneracy of a topologically ordered phase in the two-dimensional toric code model. We also generalize QFAMES to the setting of mixed initial states. Our approach offers rigorous theoretical guarantees and significant advantages over existing subspace-based quantum spectral analysis methods, particularly in terms of the sample complexity and the ability to resolve degeneracies.

Abstract: Non-classical quantum correlations underpin both the foundations of quantum mechanics and modern quantum technologies. Among them, Bell nonlocality is a central example. For bipartite Bell inequalities, nonlocal correlations obey strict monogamy: a violation of one inequality precludes violations of other inequalities on the overlapping subsystems. In the multipartite setting, however, Bell nonlocality becomes inherently polygamous. This was previously shown for subsystems obtained by removing a single particle from an $N$-partite system. Here, we generalize this result to arbitrary $(N-k)$-partite subsystems with $k>0$. We demonstrate that a single $N$-qubit state can violate all $\binom{N}{k}$ relevant Bell inequalities simultaneously. We further construct an $N$-qubit Bell inequality, obtained by symmetrizing the $(N-k)$-qubit ones, that is maximally violated by states exhibiting this generalized polygamy. We compare these violations with those achievable by GHZ states and show that polygamy offers an advantage in multipartite scenarios, providing new insights into scalable certification of non-classicality in quantum devices. Our analysis relies on symmetry properties of the MABK inequalities. Finally, we show that this behavior can occur across multiple subsystem sizes, a phenomenon we call hyper-polygamy. These structures reveal the remarkable abundance of nonlocality present in multipartite quantum states and offer perspectives for their applications in quantum technologies.

Abstract: Measuring global quantum properties—such as the fidelity to complex multipartite states—is an essential yet experimentally challenging task. Classical shadow estimation offers favorable sample complexity but typically relies on deep circuits difficult to realize on current platforms. We propose the robust phase shadow (RPS), a framework based on random circuits with controlled-𝑍 as the unique entangling gate type, tailored to architectures like trapped ions and neutral atoms. everaging tensor diagrammatic reasoning, we show that RPS matches the performance of Clifford-based methods. Importantly, our approach supports a noise-robust extension via classical post-processing, enabling reliable estimation under arbitrary gate-dependent Pauli noise where existing techniques fail. Additionally, we design an efficient post-processing algorithm resolving computational bottlenecks. Our results provide a scalable route for estimating global properties in noisy quantum systems.

Abstract: We present a general framework for applying linear quantum error mitigation (QEM) techniques directly to physical qubits within a logical qubit to suppress logical errors. By exploiting the linearity of quantum error correction (QEC), we demonstrate that any linear QEM method—including probabilistic error cancellation (PEC), zero-noise extrapolation (ZNE), and symmetry verification—can be integrated into the physical layer without requiring modifications to the subsequent QEC decoder. Applying this framework to memory experiments using PEC, we analytically prove and numerically verify that the leading-order contribution to the logical error can be removed, increasing the effective code distance by 2. Our simulations on repetition and rotated surface codes show that a distance-3 code with physical-level PEC achieves logical error rates lower than or similar to a distance-5 unmitigated code while using 40% and 64% fewer qubits, respectively. These results establish physical-level QEM as a widely compatible and resource-efficient strategy for enhancing logical performance in early fault-tolerant architectures.

Abstract: Analyzing the impact of noise is of fundamental importance to understand the advantages provided by quantum systems. While the classical simulability of noisy discrete-variable systems is increasingly well understood, noisy bosonic circuits are more challenging to simulate and analyze. Here, we address this gap by introducing the displacement propagation algorithm, a continuous-variable analogue of Pauli propagation for simulating noisy bosonic circuits. By exploring the interplay of noise and quantum resources, we identify several computational phase transitions, revealing regimes where even modest noise levels render bosonic circuits efficiently classically simulable. In particular, our analysis reveals a surprising phenomenon: computational resources usually associated with bosonic quantum advantage, namely non-Gaussianity and symplectic coherence, can make the system easier to classically simulate in presence of noise.

Abstract: Efficient simulation of many-body quantum systems is central to advances in physics, chemistry, and quantum computing, with a key question being whether the simulation cost scales polynomially with the system size. In this work, we analyze many-body quantum systems with Coulomb interactions, which are fundamental to electronic and molecular systems. We prove that Trotterization for such unbounded Hamiltonians achieves a $1/4$-order convergence rate, with explicit polynomial dependence on the number of particles. The result holds for all initial wavefunctions in the domain of the Hamiltonian, and the $1/4$-order convergence rate is optimal, as previous work has numerically demonstrated that it can be saturated by a specific initial ground state. The main challenges arise from the many-body structure and the singular nature of the Coulomb potential. Our proof strategy differs from prior state-of-the-art Trotter analyses, addressing both difficulties in a unified framework. Our analysis treats the Coulomb potential as an unbounded operator without modification or regularization, and does not rely on spatial discretization, making it compatible with both first- and second-quantized circuit constructions.

Abstract: We study the dimension of the manifold of quantum states (called orbit) that a given quantum state of light can reach under the dynamics of linear or Gaussian optics. That is, we investigate how many directions in the Hilbert space a given state can explore under these sub-universal regimes. We find that these orbit dimensions reveal fundamental insights into the structure of attainable state spaces (e.g. boson bunching does not increase the number of accessible directions) with multi-faceted consequences. By showcasing a simple way to compute this topological quantity, we reveal how it can alone yield no-go results for some transformations. Our framework is provably applicable in both Fock representations and some phase-space representations like the Wigner and stellar representations. We study genericity and robustness properties of orbit dimensions, and propose strategies to probe them using homodyne/heterodyne measurements on pure states, or photon counters on two copies of general states. We also highlight how under Gaussian unitaries, orbit dimensions witness non-Gaussianity. Lastly, we rigorously establish implications of orbit dimensions for the number of directions that a bosonic variational circuit can explore in state space. Our approach sheds new light on the structure of reachable states in quantum optics, which can help practitioners understand limitations and sources of expressivity or non-Gaussianity in optical experiments.

Abstract: We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a result of Kempe, Regev, and Toner (FOCS'08). On the other hand, our result aligns with the RE-hardness of the quantum label cover problem, which follows from the celebrated MIP*=RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21). Additionally, we show that the quantum oracularized smooth label cover problem is RE-hard. Our second result fits with the alternative quantum unique games conjecture recently proposed by Mousavi and Spirig (ITCS'25) on the RE-hardness of the quantum oracularized unique label cover problem. Our proof techniques include a quantum version of Feige's reduction from 3SAT to 3SAT5 (STOC'96) for BCSMIP*-protocols, which may be of independent interest.

Abstract: Distinguishing quantum states and channels lies at the core of quantum information processing. Quantum hypothesis testing and channel discrimination have been traditionally studied in the asymptotic setting, assuming access to an infinite number of samples of data or channel uses. However, in practice, finite resources are the regime of interest and demand a non-asymptotic approach. In this work, we study the non-asymptotic regime of the discrimination setting to obtain the optimal sample complexity for the task of the binary state discrimination problem, where our lower and upper bounds differ only by a constant factor of four. We also extend the non-asymptotic study (finite channel uses n) of channel discrimination and determine the optimal query complexity for discrimination of classical–quantum channels, thus also solving this dynamical generalization of the sample complexity question.

Abstract: The exploration of tomography of bosonic Gaussian states is presumably as old as quantum optics, but only recently, their precise and rigorous study have been moving into the focus of attention, motivated by technological developments. In this work, we present an efficient and experimentally feasible Gaussian state tomography algorithm with provable recovery trace-distance guarantees, whose sample complexity depends only on the number of modes, and---remarkably---is independent of the state's photon number or energy, up to doubly logarithmic factors. Our algorithm yields a doubly-exponential improvement over existing methods, and it employs operations that are readily accessible in experimental settings: the preparation of an auxiliary squeezed vacuum, passive Gaussian unitaries, and homodyne detection. At its core lies an adaptive strategy that systematically reduces the total squeezing of the system, enabling efficient tomography. Quite surprisingly, this proves that estimating a Gaussian state in trace distance is generally more efficient than directly estimating its covariance matrix. Our algorithm is particularly well-suited for applications in quantum metrology and sensing, where highly squeezed---and hence high-energy---states are commonly employed. As a further contribution, we establish improved sample complexity bounds for standard heterodyne tomography, equipping this widely used protocol with rigorous trace-norm guarantees.

Abstract: Quantum low-density parity-check (qLDPC) codes can be implemented by measuring only low-weight checks, making them compatible with noisy quantum hardware and central to the quest to build noise-resilient quantum computers. A fundamental open question is how constraints on check weight limit the achievable parameters of qLDPC codes. Here, we study stabilizer and subsystem codes with constrained check weight, combining analytical arguments with numerical optimization to establish strong upper bounds on their parameters. We show that stabilizer codes with checks of weight at most three cannot have nontrivial distance. We also prove tight tradeoffs between rate and distance for broad families of CSS stabilizer and subsystem codes with checks of weight at most four and two, respectively. Notably, our bounds are applicable to general qLDPC codes, as they rely only on check-weight constraints without assuming geometric locality or special graph connectivity. In the finite-size regime, we derive numerical upper bounds using linear programming techniques and identify explicit code constructions that approach these limits, delineating the landscape of practically relevant qLDPC codes with tens or hundreds of physical qubits.

Abstract: Quantum error mitigation is a critical technology for extracting reliable computations from noisy quantum processors, proving itself essential not only in the near term but also as a valuable supplement to fully fault-tolerant systems in the future. However, its practical implementation is hampered by two major challenges: the expansive cost of sampling from quantum circuits and the reliance on unrealistic assumptions, such as gate-independent noise. Here, we introduce Classical Noise Inversion (CNI), a framework that fundamentally bypasses these crucial limitations and is well-suited for various quantum applications. CNI effectively inverts the accumulated noise entirely during classical post-processing, thereby eliminating the need for costly quantum circuit sampling and remaining effective under the realistic condition of gate-dependent noise. Apart from CNI, we introduce noise compression, which groups noise components with equivalent effects on measurement outcomes, achieving the optimal overhead for error mitigation. We integrate CNI with the framework of shadow estimation to create a robust protocol for learning quantum properties under general noise. Our analysis and numerical simulations demonstrate that this approach substantially reduces statistical variance while providing unbiased estimates in practical situations where previous methods fail. By transforming a key quantum overhead into a manageable classical cost, CNI opens a promising pathway towards scalable and practical quantum applications.

Abstract: Accurately computing the free energies of biological processes is a cornerstone of computer-aided drug design, but it is a daunting task. The need to sample vast conformational spaces and account for entropic contributions makes the estimation of binding free energies very expensive. While classical methods, such as thermodynamic integration and alchemical free energy calculations, have significantly contributed to reducing computational costs, they still face limitations in terms of efficiency and scalability. We tackle this through a quantum algorithm for the estimation of free energy differences by adapting the existing Liouvillian approach and introducing several key algorithmic improvements. We directly implement the Liouvillian operator and provide an efficient description of electronic forces acting on both nuclear and electronic particles on the quantum ground state potential energy surface. This leads to super-polynomial runtime scaling improvements in the precision of our Liouvillian simulation approach and quadratic improvements in the scaling with the number of particles relative to prior quantum algorithms. Second, our algorithm calculates free energy differences via a fully quantum implementation of thermodynamic integration and alchemy, thereby foregoing expensive entropy estimation subroutines used in prior works. Our results open new avenues towards the application of quantum computers in drug discovery.

Abstract: Starting from a microscopic description of weak system-bath interactions, we derive from first principles a quantum master equation that does not rely on the well-known rotating wave approximation. This includes generic many-body systems, with Hamiltonians with vanishingly small energy spacings that forbid that approximation. The equation satisfies a general form of detailed balance, called KMS, which ensures exact convergence to the many-body Gibbs state. Unlike the more common notion of GNS detailed balance, this notion is compatible with the absence of the rotating wave approximation. We show that the resulting Lindbladian dynamics not only reproduces the thermal equilibrium point up to a small renormalization of the system Hamiltonian, but it also approximates the true system evolution with an error that grows at most linearly in time, giving an exponential improvement upon previous estimates. This master equation has quasi-local jump operators, can be efficiently simulated on a quantum computer, and reduces to the usual Davies dynamics in the limit of a coarse-graining time much larger than the inverse of the smallest frequency difference. With it, we provide a rigorous model of many-body thermalization relevant to both open quantum systems and quantum algorithms.

Abstract: Cardinality-constrained binary optimization is a fundamental computational primitive with broad applications in machine learning, finance, and scientific computing. In this work, we introduce a Grover-based quantum algorithm that exploits the structure of the fixed-cardinality feasible subspace under a natural promise on solution existence. For quadratic objectives, our approach achieves $\mathcal{O}\left(\sqrt{\frac{\binom{n}{k}}{{M}}}\right)$ Grover rotations for any fixed cardinality $k$ and degeneracy of the optima $M$, yielding an exponential reduction in the number of Grover iterations compared with unstructured search over $\{0,1\}^n$. Building on this result, we develop a hybrid classical--quantum framework based on the alternating direction method of multipliers (ADMM) algorithm. The proposed framework is guaranteed to output an $\epsilon$-approximate solution with a consistency tolerance $\epsilon + \delta$ using at most $ \mathcal{O}\left(\sqrt{\binom{n}{k}}\frac{n^{6}k^{3/2} }{ \sqrt{M}\epsilon^2 \delta }\right)$ queries to a quadratic oracle, together with $\mathcal{O}\left(\frac{n^{6}k^{3/2}}{\epsilon^2\delta}\right)$ classical overhead. Overall, our method suggests a practical use of quantum resources and demonstrates an exponential improvements over existing Grover-based approaches in certain parameter regimes, thereby paving the way toward quantum advantage in constrained binary optimization.

Abstract: We study the distinguishability of quantum states under local operations with classical communication (LOCC), separable, and positive-partial-transpose (PPT) measurements, focusing on \emph{locally diagonal orthogonally invariant} (LDOI) states---those invariant under local diagonal orthogonal twirling. This class includes many important families such as Werner states, isotropic states, X-states, and Dicke states. We show that optimal PPT and separable measurements for distinguishing LDOI states can always be taken to be LDOI, and the LOCC supremum can be approached by LDOI LOCC POVMs, enabling a dimensional reduction from $n^4$ to $O(n^2)$ in the associated optimization problems. We establish efficiently computable bounds on the distinguishability of orthonormal LDOI bases and prove that for a broad class of such bases---including all two-qubit cases---the LOCC supremum equals the PPT and separable optima. More generally, we show the gap between PPT and LOCC distinguishability is at most $(n-2)/(2n^2)$ for local dimension $n$.

Abstract: We propose a decoder for quantum low density parity check (LDPC) codes based on a beam search heuristic guided by belief propagation (BP). Our beam search decoder applies to all quantum LDPC codes and achieves different speed-accuracy tradeoffs by tuning its parameters such as the beam width. We perform numerical simulations under circuit level noise for the $[[144, 12, 12]]$ bivariate bicycle (BB) code at noise rate $p=10^{-3}$ to estimate the logical error rate and the 99.9 percentile runtime and we compare with the BP-OSD decoder which has been the default quantum LDPC decoder for the past six years. A variant of our beam search decoder with a beam width of 64 achieves a $17\times$ reduction in logical error rate. With a beam width of 8, we reach the same logical error rate as BP-OSD with a $26.2\times$ reduction in the 99.9 percentile runtime. We identify the beam search decoder with beam width of 32 as a promising candidate for trapped ion architectures because it achieves a $5.6\times$ reduction in logical error rate with a 99.9 percentile runtime per syndrome extraction round below 1ms at $p=5 \times 10^{-4}$. Remarkably, this is achieved in software on a single core, without any parallelization or specialized hardware (FPGA, ASIC), suggesting one might only need three 32-core CPUs to decode a trapped ion quantum computer with 1000 logical qubits.

Abstract: Cryptographic verification is essential for establishing trust in quantum-computing-as-a-service. However, a fundamental gap exists in the current verification landscape: existing efficient protocols are largely restricted to decision problems where correctness is boosted by classical majority voting. This excludes observable estimation, the statistical task underpinning nearly all near-term quantum advantage applications. For such tasks, current verification techniques face a prohibitive trade-off: either weak security guarantees or massive space overhead that exceeds the capacity of near-term hardware. To resolve this, we introduce the Secure Delegated Observable Estimation (SDOE) ideal resource, the first formal cryptographic framework for trustworthy expectation-value estimation within Abstract Cryptography. We then present the Verifiable Blind Observable Estimation (VBOE) protocol, which efficiently constructs this resource. VBOE circumvents the limitations inherent in prior methodologies by enabling the sequential collection of samples with negligible security error, requiring zero extra qubit overhead. By directly averaging computation rounds in classical post-processing, our protocol provides the only known path to rigorous, composable verification for the most common class of near-term quantum-classical hybrid algorithms. This work bridges foundational cryptographic theory with practical quantum tasks, enabling the certification of quantum utility on current and near-future devices.

Abstract: Qudits offer the potential for low-overhead magic state distillation, although previous results for asymptotically good codes have required qudit dimension $q\gg 100$ or code length $\mathcal{N}\gg 100$. These parameters far exceed experimental demonstrations of qudit platforms, and thus motivate the search for better codes. Using a novel lifting procedure, we construct the first family of good triorthogonal codes on the $\mathbb{F}_{2^{2m}}$ alphabet with $m \geq 3$ that lies above the Tsfasman-Vladut-Zink bound. These codes yield a family of asymptotically good quantum codes with transversal CCZ gates, enabling constant space overhead magic state distillation with qudit dimension as small as $q=64$. Further, we identify a promising code with parameters $[[42,14,6]]_{64}$. Finally, we show that a distilled $\ket{CCZ}_{2^{2m}}$ can be reduced to a $\ket{CCZ}_{2^n}$ state for arbitrary $n$ with a constant-depth Clifford circuit of at most 9 computational basis measurements, 12 single-qudit and 9 two-qudit Clifford gates.

Abstract: Control is a fundamental concept in quantum and reversible computational models. It enables the conditional application of a transformation to a system, depending on the state of another system. We introduce a general framework for diagrammatic reasoning featuring control as a constructor. To this end, we provide an elementary axiomatisation of control functors, extending the standard formalism of props to controlled props. As an application, we show that controlled props facilitate diagrammatic reasoning for quantum circuits by introducing a simple and complete set of relations involving at most three qubits, whereas in the standard prop setting any complete axiomatisation necessarily requires relations acting on arbitrarily many qubits.

Abstract: We investigate $(k_1,k_2)$-extendibility of fermionic Gaussian states, a property central to quantum correlations and approximations of separability. We show that these states are $(k_1,k_2)$-extendible if and only if they admit a fermionic Gaussian extension, yielding a complete covariance-matrix characterization and a simple semidefinite program (SDP) whose size scales linearly with the number of modes. This provides necessary conditions for arbitrary fermionic states and is sufficient within the Gaussian setting. Our main result is a finite de Finetti--type theorem: we derive trace-norm bounds between $(k_1,k_2)$-extendible fermionic Gaussian states and separable states, improving previous exponential scaling to linear in the number of modes, with complementary relative entropy and squashed entanglement bounds. For two modes, upper and lower bounds match at order $1/\sqrt{k_1 k_2}$. Extendibility also provides operational support for one of the different notions of separability in fermionic systems. Finally, for fermionic Gaussian channels, we provide an SDP criterion for anti-degradability and show that entanglement-breaking channels coincide with replacement channels, implying no nontrivial entanglement-breaking fermionic Gaussian channels exist.

Abstract: Non-Gaussianity is a key resource for achieving quantum advantages in bosonic platforms. Here, we investigate the symplectic rank: a novel non-Gaussianity monotone that satisfies remarkable operational and resource-theoretic properties. Mathematically, the symplectic rank of a pure state is the number of symplectic eigenvalues of the covariance matrix that are strictly larger than the ones of the vacuum. Operationally, it (i) is easy to compute, (ii) emerges as the smallest number of modes onto which all the non-Gaussianity can be compressed via Gaussian unitaries, (iii) lower bounds the non-Gaussian gate complexity of state preparation independently of the gate set, (iv) governs the sample complexity of quantum tomography, and (v) bounds the computational complexity of bosonic circuits. Crucially, the symplectic rank is non-increasing under post-selected Gaussian operations, leading to strictly stronger no-go theorems for Gaussian conversion than those previously known. Remarkably, this allows us to show that the resource theory of non-Gaussianity is irreversible under exact Gaussian operations. Finally, we show that the symplectic rank is a robust non-Gaussian measure, explaining how to witness it in experiments and how to exploit it to meaningfully benchmark different bosonic platforms. In doing so, we derive lower bounds on the trace distance (resp. total variation distance) between arbitrary states (resp. classical probability distributions) in terms of the norm distance between their covariance matrices, which may be of independent interest.

Abstract: Bosonic quantum communication has extensively been analysed in the asymptotic setting, assuming infinite channel uses and vanishing communication errors. Comparatively fewer detailed analyses are available in the non-asymptotic setting, which addresses a more precise, quantitative evaluation of the optimal communication rate: how many uses of a bosonic Gaussian channel are required to transmit $k$ qubits, distil $k$ Bell pairs, or generate $k$ secret-key bits, within a given error tolerance $\varepsilon$? In this work, we address this question by finding easily computable lower bounds on the non-asymptotic capacities of Gaussian channels, and we provide explicit evaluations for the pure loss channel, for the pure amplifier channel and for a non-Markovian noise that generalizes the pure loss channel, introduced in [IEEE Transactions on Information Theory 70, 8844–8869 (2024]. To derive our results, we develop new tools of independent interest. In particular, we find a stringent bound on the probability $P_{>N}$ that a Gaussian state has more than $N$ photons, demonstrating that $P_{>N}$ decreases exponentially with $N$. Furthermore, we design the first algorithm capable of computing the trace distance between two Gaussian states up to a fixed precision. To address the non-Markovian case, we also prove properties of singular values of Toeplitz matrices, providing an error bound on the convergence rate of the celebrated Avram–Parter’s theorem, which we regard as a new tool of independent interest for the field of quantum information theory and matrix analysis.

Abstract: Determining the Hamiltonian of a quantum system is essential for understanding its dynamics and validating its behavior. Hamiltonian learning provides a data-driven approach to reconstruct the generator of the dynamics from measurements on the evolved system. Among its applications, it is particularly important for benchmarking and characterizing quantum hardware, such as quantum computers and simulators. However, as these devices grow in size and complexity, this task becomes increasingly challenging. To address this, we propose a scalable and experimentally friendly Hamiltonian learning protocol for Hamiltonian operators made of local interactions. It leverages the quantum Zeno effect as a reshaping tool to localize the system's dynamics and then applies quantum process tomography to learn the coefficients of a local subset of the Hamiltonian acting on selected qubits. Unlike existing approaches, our method does not require complex state preparations and uses experimentally accessible, coherence-preserving operations. We derive theoretical performance guarantees and demonstrate the feasibility of our protocol both with numerical simulations and through an experimental implementation on IBM’s superconducting quantum hardware, successfully learning the coefficients of a 109-qubit Hamiltonian.

Abstract: Finite-size general security proofs for QKD based on Rényi entropies offer more flexible and provide tighter bounds on the secret key rate than traditional formulations based on the von Neumann entropy. However, deploying them requires minimizing the conditional Rényi entropy, a difficult optimization problem that has commonly been tackled using ad-hoc techniques based on the Frank-Wolfe algorithm, which are unstable and can only handle particular cases. In this work, we introduce a method based on non-symmetric conic optimization for solving this problem. Our technique is fast, reliable, and completely general. We illustrate its performance on several protocols, whose results represent an improvement over the state of the art.

Abstract: We revisit the problem of learning fermionic linear optics (FLO), also known as fermionic Gaussian unitaries. Given black-box query access to an unknown FLO, previous proposals required $\widetilde{\mathcal{O}}(n^5 / \varepsilon^2)$ queries, where $n$ is the system size and $\varepsilon$ is the error in diamond distance. These algorithms also use unphysical operations (i.e., violating fermionic superselection rules) and/or $n$ auxiliary modes to prepare Choi states of the FLO. In this work, we establish efficient and experimentally friendly protocols that obey superselection, use minimal ancilla (at most $1$ extra mode), and exhibit improved dependence on both parameters $n$ and $\varepsilon$. For arbitrary FLOs our algorithm makes at most $\widetilde{\mathcal{O}}(n^4 / \varepsilon)$ queries, while for number-conserving unitaries (called passive FLOs) we show that $\mathcal{O}(n^3 / \varepsilon)$ queries suffice. This marks the first FLO learning algorithm that attains Heisenberg scaling in precision. As a side result, we also demonstrate an improved copy complexity of $\widetilde{\mathcal{O}}(n \eta^2 / \varepsilon^2)$ for time-efficient state tomography of $\eta$-particle Slater determinants in $\varepsilon$ trace distance, which may be of independent interest.

Abstract: Commutativity gadgets allow NP-hardness proofs for classical constraint satisfaction problems (CSPs) to be carried over to undecidability proofs for the corresponding entangled CSPs. This has been done, for instance, for NP-complete boolean CSPs and 3-colouring in the work of Culf and Mastel. For many CSPs over larger alphabets, including $k$-colouring when $k \geq 4$, it is not known whether or not commutativity gadgets exist, or if the entangled CSP is decidable. In this paper, we study commutativity gadgets and prove the first known obstruction to their existence. We do this by extending the definition of the quantum automorphism group of a graph to the quantum endomorphism monoid of a CSP, and showing that a CSP with non-classical quantum endomorphism monoid does not admit a commutativity gadget. In particular, this shows that no commutativity gadget exists for $k$-colouring when $k \geq 4$. However, we construct a commutativity gadget for an alternate way of presenting $k$-colouring as a nonlocal game, the oracular setting. Furthermore, we prove an easy to check sufficient condition for the quantum endomorphism monoid to be non-classical, extending a result of Schmidt for the quantum automorphism group of a graph, and use this to give examples of CSPs that do not admit a commutativity gadget. We also show that existence of commutativity gadgets and oracular commutativity gadgets is equivalent for graphs with no four-cycle; and that the odd cycles and the odd graphs have a commutative quantum endomorphism monoid, leaving open the possibility that they might admit a commutativity gadget.

Abstract: We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms and serves as the foundation for new ones. Existing implementations of QSVT rely on block encoding, incurring an intrinsic $O(\log L)$ ancilla overhead and circuit depth $\widetilde{O}(L d\lambda )$ for polynomial transformations of a Hamiltonian $H=\sum_{k=1}^L H_k$, where $d$ is the polynomial degree and $\lambda=\sum_{k}\|H_k\|$. We introduce a simple yet powerful approach that utilizes only basic Hamiltonian simulation techniques, namely, Trotter methods, to: (i) eliminate the need for block encoding, (ii) reduce the ancilla overhead to only a single qubit, and (iii) still maintain near-optimal complexity. Our method achieves a circuit depth of $\widetilde{O}(L(d\lambda_{\mathrm{comm}})^{1+o(1)})$, without requiring any complicated multi-qubit controlled gates. Moreover, $\lambda_{\mathrm{comm}}$ depends on the nested commutators of the terms of $H$ and can be substantially smaller than $\lambda$ for many physically relevant Hamiltonians, a feature absent in standard QSVT. To achieve these results, we make use of Richardson extrapolation in a novel way, systematically eliminating errors in any interleaved sequence of arbitrary unitaries and Hamiltonian evolution operators, thereby establishing a general framework that encompasses QSVT but is more broadly applicable. We further design two randomized algorithms for QSVT in settings with only sampling access to the Hamiltonian terms. The first is a direct randomization of standard QSVT, while the second integrates qDRIFT within our interleaved-circuit architecture. Both achieve a complexity quadratic in $d$, which we establish as a lower bound for any randomized method implementing polynomial transformations in this model. Finally, as applications, we develop end-to-end quantum algorithms for solving linear systems and estimating ground state properties of Hamiltonians, both achieving near-optimal complexity without relying on oracular access. Overall, our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance, with implications for both near-term and fault-tolerant quantum computing.

Abstract: Circuit knitting/cutting is a family of techniques that enables large quantum computations on limited-size quantum devices by decomposing a target circuit into smaller subcircuits. However, it typically incurs a measurement overhead exponential in the number of cut locations, and this scaling has long been believed to be fundamentally unavoidable. In this work, we show that such an exponential scaling is not universal: it can be circumvented for tree-structured quantum circuits via concatenated quantum tomography protocols. We first consider the task of estimating the expectation value of an observable within additive error $\epsilon$ for a tree-structured circuit with tree depth 1, maximum branching factor $R$, and bond dimension at most $d$ on each edge. Our approach uses quantum tomography to construct, for each cut edge, a local decomposition that eliminates the rescaling factors in conventional QPD, instead introducing a controllable bias set by the tomography sample size. As a result, we show that $\mathcal{O}(d^3R^3\ln(dR)/\epsilon^2)$ total measurements suffice, including tomography measurements. Next, we extend the tree-depth-1 case to general trees of depth $L\geq2$, and give an algorithm whose total measurement cost $\mathrm{poly}(d,K,1/\epsilon)$ scales polynomially with the number of cuts $K$ for complete multi-ary trees. Finally, we perform an information-theoretic analysis to show that, in a comparable tree-depth-1 setting, conventional circuit-cutting methods require at least $\Omega((d+1)^R/\epsilon^2)$ measurements. This exponential separation in the number of cuts suggests that the improvement is not solely due to the tree restriction, highlighting the essential role of tomography-based construction in reducing measurement overhead in hybrid quantum–classical computations.

Abstract: Entanglement of embezzlement is the process of converting a separable state to an entangled state using only local operations with the help of a large catalyst state. It defies naive intuitions about entanglement as a static resource and demonstrates the subtleties of infinite-dimensional systems. There has been recent studies on approximate embezzlement protocols. This work combines two results regarding exact embezzlement. The first result is explicit protocols for universal embezzlement covering both approximate and exact cases using simple algebraic tools. In the exact case, we achieved the first known exact universal embezzlement protocol. The second result is a self-testing-like property about the structural requirement for the catalyst for embezzlement. In particular, we showed that for a catalyst to embezzle a state exactly, it must contain infinite copies of the embezzled state. This work uses C*-algebra as a model for non-local systems in infinite dimensions instead of the standard commuting operator in Hilbert space model or the von Neumann algebraic model to provide a clean and simple proofs for the resutls.

Abstract: We consider the class of Davies quantum semigroups modelling thermalization for translation-invariant Calderbank-Shor-Steane (CSS) codes in D dimensions, as well as for the two-dimensional Abelian quantum double models. We prove that conditions of Dobrushin-Shlosman-type on the quantum Gibbs state imply a modified logarithmic Sobolev inequality with a constant that is uniform in the system’s size. This is accomplished by generalizing parts of the classical results on thermalization by Stroock, Zegarlinski, Martinelli, and Olivieri to the quantum setting. The results in particular imply the rapid thermalization at any positive temperature for the toric code and Abelian double models in 2D and of the star part of the toric code in 3D, implying a rapid loss of stored quantum information for these models.

Abstract: Quantum dynamic programming (QDP) holds promise for accelerating combinatorial optimization, yet its theoretical speedups often clash with the constraints of real hardware. We identify a fundamental tension: classical dynamic programming requires discriminating between subproblem solutions, a task at odds with the indistinguishability inherent to quantum superposition. We distill four key implementation challenges—step dependency, measurement reliance, subspace-specific thresholding, and recursive oracle expansion—that cause the practical complexity of hybrid QDP algorithms (e.g., Ambainis et al.’s TSP solver) to vastly exceed their theoretical estimates. To bridge this gap, we design efficient quantum state-preparation algorithms for Hamiltonian cycles and permutations, with the latter achieving optimal asymptotic resource overhead. Furthermore, by quantizing classical dynamic programming, we present a practically realizable quantum algorithm for TSP (QDP(search)), and rigorously analyze its complexity under our identified challenges. Combining state preparation with a quantum search that uses a shortcut of the Quantum Fourier Transform, we obtain the QDP(HC) algorithm, which achieves the lowest practical complexity among all currently implementable quantum TSP solvers. This work provides a critical reference for designing implementation-aware quantum algorithms on near-term hardware.

Abstract: Learning the Hamiltonian governing a quantum system is a central task in quantum metrology, sensing, and device characterization. Existing Heisenberg-limited Hamiltonian learning protocols either require multi-qubit operations that are prone to noise, or single-qubit operations whose frequency or strength increases with the desired precision. These two requirements limit the applicability of Hamiltonian learning on near-term quantum platforms. We present a protocol that learns a quantum Hamiltonian with the optimal Heisenberg-limited scaling using only single-qubit control in the form of static fields with strengths that are independent of the target precision. Our protocol is robust against the state preparation and measurement (SPAM) error. By overcoming these limitations, our protocol provides new tools for device characterization and quantum sensing. We demonstrate that our method achieves the Heisenberg-limited scaling through rigorous mathematical proof and numerical experiments. We also prove an information-theoretic lower bound showing that a non-vanishing static field strength is necessary for achieving the Heisenberg limit unless one employs an extensive number of discrete control operations.

Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is constrained by an ansatz that follows a single, fixed evolution path, neglecting the potential computational advantage of coherently superposing multiple trajectories. We introduce a generalized ansatz based on the hybrid quantum walk (HQW), which incorporates a dynamical coin operator to superpose multiple Hamiltoniandriven paths coherently within a single circuit layer. QAOA emerges as a restrictive special case, corresponding to a static Pauli-X coin. Using Pontryagin’s minimum principle, we derive the optimal form of the coin operator, demonstrating that it generally differs from a constant gate. Numerical experiments on Max-Cut and Maximum Independent Set problems show that HQW systematically outperforms QAOA in convergence speed, solution accuracy, and robustness. A dynamical Lie algebra analysis reveals that HQW generates a strictly larger Jordan-Lie algebra, providing an algebraic foundation for its enhanced expressivity. Our work establishes a path-superposition paradigm for quantum optimization, combining optimal control theory with algebraic structure to advance the design of quantum algorithms.

Abstract: We examine the ability of gate-based continuous-variable quantum computers to outperform qubit or discrete-variable quantum computers. Gate-based continuous-variable operations refer to operations constructed using a polynomial sequence of elementary gates from a specific finite set, i.e., those selected from the set of Gaussian operations and cubic phase gates. Our results show that for a fixed energy of the system, there is no superpolynomial computational advantage in using gate-based continuous-variable quantum computers over discrete-variable ones. The proof of this result consists of defining a framework–––of independent interest---that maps quantum circuits between the paradigms of continuous- and discrete-variables. This framework allows us to conclude that a realistic gate-based model of continuous-variable quantum computers, consisting of states and operations that have a total energy that is polynomial in the number of modes, can be simulated efficiently using discrete-variable devices. We utilize the stabilizer subsystem decomposition [Shaw et al., PRX Quantum 5, 010331] to map continuous-variable states to discrete-variable counterparts, which allows us to find the error of approximating continuous-variable quantum computers with discrete-variable ones in terms of the energy of the continuous-variable system and the dimension of the corresponding encoding qudits.

Abstract: Classically simulating circuits with bosonic codes is challenging due to the prohibitive cost of simulating quantum systems with many, possibly infinite, energy levels. We propose an algorithm to simulate circuits with encoded Gottesman-Kitaev-Preskill (GKP) states, specifically for odd-dimensional encoded qudits. Our approach is tailored to be especially effective in the most challenging but practically relevant regime, where the codeword states exhibit high (but finite) squeezing. Our algorithm leverages the Zak-Gross Wigner function introduced by J. Davis et al. [arXiv:2407.18394], which represents infinitely squeezed encoded stabilizer states positively. The runtime of the algorithm scales with the negativity of the Wigner function, allowing for efficient simulation of certain large-scale circuits — namely, input stabilizer GKP states undergoing generalized GKP-encoded Clifford operations followed by modular measurements — with a high degree of squeezing. For stabilizer GKP states exhibiting 12 dB of squeezing, our algorithm can simulate circuits with up to 1,000 modes with less than double the number of samples required for a single input mode, in stark contrast to existing simulators. Therefore this approach holds significant potential for benchmarking early implementations of quantum computing architectures utilizing bosonic codes.

Abstract: In classical information theory, the Doeblin coefficient of a classical channel provides an efficiently computable upper bound on the total-variation contraction coefficient of the channel, leading to what is known as a strong data-processing inequality. Here, we investigate quantum Doeblin coefficients as a generalization of the classical concept. In particular, we define various new quantum Doeblin coefficients, one of which has several desirable properties, including concatenation and multiplicativity, in addition to being efficiently computable. We also develop various interpretations of two of the quantum Doeblin coefficients, including representations as minimal singlet fractions, exclusion values, reverse max-mutual and oveloH informations, reverse robustnesses, and hypothesis testing reverse mutual and oveloH informations. Our interpretations of quantum Doeblin coefficients as either entanglement-assisted or unassisted exclusion values are particularly appealing, indicating that they are proportional to the best possible error probabilities one could achieve in state-exclusion tasks by making use of the channel. We also outline various applications of quantum Doeblin coefficients, ranging from limitations on quantum machine learning algorithms that use parameterized quantum circuits (noise-induced barren plateaus), on error mitigation protocols, on the sample complexity of noisy quantum hypothesis testing, and on mixing, distinguishability, and decoupling times of time-varying channels. All of these applications make use of the fact that quantum Doeblin coefficients appear in upper bounds on various trace-distance contraction coefficients of a channel. Furthermore, in all of these applications, our analysis using Doeblin coefficients provides improvements of various kinds over contributions from prior literature, both in terms of generality and being efficiently computable.

Abstract: The main bottleneck for distributed quantum computing is the rate at which entanglement is produced between quantum processing units (QPUs). In this work, we prove that multiple QPUs connected through slow interconnects can outperform a monolithic architecture made with a single QPU. We present a distributed version of Clifford noise reduction (CliNR), a partial error correction scheme, and show that it outperforms a monolithic version of CliNR. Distributed CliNR has lower depth and lower logical error rates than monolithic CliNR even when the interconnects are slow. In simulations we show that  the advantage persists with interconnects that are five times slower than two qubit gates. We also prove a sufficient condition for distributed CliNR to outperform monolithic CliNR.  In addition, we present two methods for improving CliNR, allowing lower logical error rates and efficient performance for arbitrary length Clifford circuits. Finally we present results from an experimental implementation of a variant of CliNR on an ion trap quantum computer.  This work is based on three papers that are available on arXiv (see extended abstract).

Abstract: The relative entropy between quantum states quantifies their distinguishability. The estimation of certain relative entropies has been investigated in the literature, e.g., the von Neumann relative entropy and sandwiched R{\'e}nyi relative entropy. In this paper, we present a comprehensive study of the estimation of the quantum Tsallis relative entropy. We show that for any constant $\alpha \in (0, 1)$, the $\alpha$-Tsallis relative entropy between two quantum states of rank $r$ can be estimated with sample complexity $\operatorname{poly}(r)$, which can be made more efficient if we know their state-preparation circuits. As an application, we obtain an approach to tolerant quantum state certification with respect to the quantum Hellinger distance with sample complexity $\widetilde{O}(r^{3.5})$, which \textit{exponentially} outperforms the folklore approach based on quantum state tomography when $r$ is polynomial in the number of qubits. In addition, we show that the quantum state distinguishability problems with respect to the quantum $\alpha$-Tsallis relative entropy and quantum Hellinger distance are $\mathsf{QSZK}$-complete in a certain regime, and they are $\mathsf{BQP}$-complete in the low-rank case.

Abstract: In 2004, Aaronson introduced the complexity class PostBQP~(BQP with postselection) and showed that it is equal to PP. Following their line of work, we introduce two new complexity classes. The first, CorrBQP, is a modification of BQP which has the power to perform correlated measurements, i.e. measurements that output the same value across a partition of registers. The second, MajBQP, augments BQP with the ability to collapse a qubit to its most likely outcome. We exactly characterize the models, showing MajBQP = CorrBQP = BPP^PP = P^PP. This characterization allows us to obtain a derandomization of BPP with respect to a PP oracle. In fact, we show that other metaphysical modifications of BQP, such as CBQP (i.e. BQP with the ability to clone arbitrary quantum states), are also equal to P^PP. We show that CorrBQP is self-low with respect to classical queries. In contrast, if it were self-low under quantum queries, the counting hierarchy (CH) would collapse to P^PP. Furthermore, we introduce a variant of rational degree that lower-bounds the query complexity of P^PP. Lastly, we extend the adversary lower-bounding technique to AdPDQP, BQP with the ability to sample the current state of the algorithm and adapt the computation based on the samples.

Abstract: Gottesman–Kitaev–Preskill (GKP) codes provide a family of promising schemes for encoding discrete quantum information (qudits) into infinite-dimensional bosonic modes based on mathematical lattices. While such codes, when concatenated with discrete-variable codes, are relatively well studied, the decoding problem of native GKP codes has largely remained open due to the computationally hard problems encountered. To address this challenge, we advocate a strategy of co-designing the decoder and the quantum error-correcting code itself by constructing lattices for which decoding is feasible and does not reduce to hard instances. This construction is built on classical low-density lattice codes (LDLCs), a lattice analogue of low-density parity-check codes, here lifted to families of GKP codes. Concretely, we introduce quantum versions of classical LDLCs and study the performance of message-passing decoders—originally developed for LDLCs—when applied to GKP codes with sparse stabilizer generators. We hope that the tools we introduce, along with their analysis, will facilitate future research on the structure and performance of general GKP codes. In this spirit, the source code used to reproduce all results presented here is released as an open-source Julia package.

Abstract: We introduce a Pauli-measurement-based algorithm to certify the Schmidt number of $n$-qubit pure states. Our protocol achieves an average-case sample complexity of $\caO(\mathrm{poly}(n)\chi^2)$, a substantial improvement over the $\caO(2^n \chi)$ worst-case bound. By utilizing local pseudorandom unitaries, we ensure the worst case can be transformed into the average-case with high probability. This work establishes a scalable approach to high-dimensional entanglement certification and introduces a proof framework for random Pauli sampling.

Abstract: A discrete time quantum walk is known to be the single-particle sector of a quantum cellular automaton. For a long time, these models have interested the community for their nice properties such as locality or translation invariance. This work introduces a model of distributed computation for arbitrary graphs inspired by quantum cellular automata. As a by-product, we show how this model can reproduce the dynamic of a quantum walk on graphs. In this context, we inves- tigate the communication cost for two interaction schemes. Finally, we explain how this particular quantum walk can be applied to solve the search problem and present numerical results on different types of topologies.

Abstract: Quantum walks, both discrete and continuous, serve as fundamental tools in quantum information processing with diverse applications. This work introduces a hybrid quantum walk model that integrates the coin mechanism of discrete walks with the Hamiltonian-driven time evolution of continuous walks. Through systematic analysis of probability distributions, standard deviations, and entanglement entropy on fundamental graph structures (2-vertex circles, stars, and lines), we reveal distinctive dynamical characteristics that differentiate our model from conventional quantum walk paradigms. The proposed framework demonstrates unifying capabilities by naturally encompassing existing quantum walk models as special cases. Two significant applications emerge from this hybrid architecture: (1) We develop a novel protocol for perfect state transfer(PST) in general connected graphs, overcoming the limitations of previous graph-specific approaches. A PST on a tree graph has been implemented on a quantum superconducting processor. (2) We devise a quantum algorithm for multiplying $K$ adjacency matrices of $n$-vertex regular graphs with time complexity $O(n^2d_1\cdots d_K)$, outperforming classical matrix multiplication $(O(n^{2.371552}))$ when vertex degrees $d_i$ are bounded. The algorithm's efficacy for triangle counting is experimentally validated through the quantum simulation on PennyLane. These results establish the hybrid quantum walk as a versatile framework bridging discrete and continuous paradigms while enabling practical quantum advantage in graph computation tasks.

Abstract: Simulating electron–phonon interactions on quantum computers remains challenging, with most algorithmic effort focused on Hamiltonian simulation and circuit optimization. In this work, we study the single-electron Holstein model and propose an initial-state ansatz that substantially enhances ground-state overlap in the strong-coupling regime, thereby reducing the number of iterations required in standard quantum phase estimation. We further show that this ansatz can be implemented efficiently and yields an exponential reduction in overall circuit costs relative to conventional initial guesses. Our results highlight the practical value of incorporating physical intuition into initial state preparation for electron–phonon coupled systems.

Abstract: Utility-scale quantum computing requires quantum error correction (QEC) to protect quantum information against noise. Currently, superconducting hardware is a promising candidate for achieving fault tolerance due to its fast gate times and feasible scalability. However, it is often restricted to two-dimensional nearest-neighbour connectivity, which is thought to be incapable of accommodating high-rate quantum low-density parity-check (qLDPC) codes that promise to greatly reduce the number of physical qubits needed to encode logical qubits. In this paper we construct a new family of qLDPC codes, which we call ``Directional Codes'', that outperforms the rotated planar code (RPC) while naturally meeting the connectivity requirements of the widely adopted square-grid, and some even the sparser hexagonal-grid. The key idea is to utilise the iSWAP gate -- a natural native gate for superconducting qubits -- to construct circuits that measure the stabilisers of these qLDPC codes without the need for any long-range connections or an increased degree of connectivity. We numerically evaluate the performance of directional codes, encoding twelve logical qubits, using a common superconducting-inspired circuit-level Pauli noise model. We also compare them to the RPC and to the bivariate bicycle (BB) codes, currently the two most popular quantum LDPC code families. As a concrete example, directional codes outperform the RPC by achieving approximately the same logical error probability at physical error rate $p=10^{-3}$ using only $18.75-25\%$ of the physical qubits at distance up to $8$. Our discovery represents a breakthrough in QEC code design that suggests complex long-range, high-connectivity hardware may not be necessary for low-overhead fault-tolerant quantum computation.

Abstract: Many physical phenomena, including thermalization in open quantum systems and quantum Gibbs sampling, are modeled by Lindbladians approximating a system weakly coupled to a bath. Understanding the convergence speed of these Lindbladians to their steady states is crucial for bounding algorithmic runtimes and thermalization timescales. We study two such families of pro- cesses: one characterizing a repeated-interaction Gibbs sampling algorithm, and another modeling open many-body quantum thermalization. We prove that both converge in polynomial time for sev- eral non-commuting systems, including high-temperature local lattices, weakly interacting fermions, and 1D spin chains. These results demonstrate that simple dissipative quantum algorithms can pre- pare complex Gibbs states and that Lindblad dynamics accurately capture thermal relaxation. Our proofs rely on a novel technical result that extrapolates spectral gap lower bounds from quasi-local Lindbladians to the non-local generators governing these dynamics.

Abstract: Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state rho, while only requiring measurements on logarithmically many copies of rho in the size of P. In this work, we initiate the study of verification of classical shadows, denoted classical shadow validity (CSV), from the perspective of computational complexity, which asks: Given a classical shadow S, how hard is it to verify that S predicts the measurement statistics of a quantum state? We first show that even for the elegantly simple classical shadow protocol of [Huang, Kueng, Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is QMA-complete. This hardness continues to hold for the high-dimensional extension of said protocol due to [Mao, Yi, and Zhu, PRL 2025]. In contrast, we show that for the HKP and MYZ protocols utilizing global Clifford measurements, CSV can be "dequantized'' for low-rank observables, i.e., solved in randomized poly-time with standard sampling assumptions. Finally, we show that CSV for exponentially many observables is complete for a quantum generalization of the second level of the polynomial hierarchy, yielding the first natural complete problem for such a class.

Abstract: The problem of quantum state classification asks how accurately one can identify an unknown quantum state that is promised to be drawn from a known set of pure states. In this work, we introduce the notion of $k$-\emph{learnability}, which captures the ability to identify the correct state using at most $k$ guesses, with zero error. We show that deciding whether a given family of states is $k$-learnable can be solved via semidefinite programming. When there are $n$ states, we present polynomial-time (in $n$) algorithms for determining $k$-learnability for two cases: when $k$ is a fixed constant or the dimension of the states is a fixed constant. When both $k$ and the dimension of the states are part of the input, we prove that there exist succinct certificates placing the problem in NP, and we establish NP-hardness by a reduction from the classical $k$-clique problem. Together, our findings delineate the boundary between efficiently solvable and intractable instances of quantum state classification in the perfect (zero-error) regime.

Abstract: Quantum Key Distribution (QKD) protocols rely on authenticated classical communication. Typical QKD security proofs are carried out in an idealized setting where authentication is assumed to behave honestly: it never aborts, and all classical messages are delivered faithfully with their original timing preserved. Authenticated channels that can be constructed in practice have different properties. Most critically, such channels may abort asymmetrically, such that only the receiving party may detect an authentication failure while the sending party remains unaware. Furthermore, an adversary may delay, reorder, or block classical messages. This discrepancy renders the standard QKD security definition and existing QKD security proofs invalid in the practical authentication setting. In this work we resolve this issue. Our main result is a reduction theorem showing that, under mild and easily satisfied protocol conditions, any QKD protocol proven secure under the honest authentication setting remains secure under a practical authentication setting. This result allows all existing QKD proofs to be retroactively lifted to the practical authentication setting with a minor protocol tweak.

Abstract: We present a rigorous and complete security proof of the decoy-state BB84 quantum key distribution (QKD) protocol. Our analysis aims to achieve a high standard of mathematical rigour and completeness, thereby providing the necessary foundation for certification and standardization efforts. Beyond establishing the security of a specific protocol, this work develops a general and modular framework that can be readily adapted to a broad class of QKD protocols, including both prepare-and-measure and entanglement-based variants. Our framework unifies all major ingredients required for the analysis of realistic QKD protocols, including the analysis of classical authentication and classical processing, source-replacement schemes, finite-size analysis, source maps, squashing maps, and decoy-state techniques. In doing so, this work consolidates a diverse range of techniques scattered across the QKD literature into a unified formalism, representing a general and rigorous treatment of QKD security. Finally, it outlines a clear path towards incorporating practical imperfections within the same framework, thereby laying the groundwork for addressing implementation security in future analysis.

Abstract: Recent developments in the field of variational quantum circuits (VQCs) have shifted the prerequisites for trainability for many barren plateau-free models onto the data encoding state fed into a classically trainable unitary. By strengthening proofs relating to small-angle initialisation, we provide a full circuit model which does not suffer from barren plateaus and is robust against current classical simulation techniques, specifically tensor network contraction and Pauli propagation. We propose this as a quantum generative model amenable towards NISQ devices and quantum-classical hybrid models, raising new questions in the debate regarding usefulness of VQCs.

Abstract: A central question in the study of nonlocal correlations is whether there exists a universal unit of nonlocality, by which any nonsignalling correlation can be obtained using local operations and shared randomness. The Popescu-Rohrlich (PR) box was proposed as a candidate unit, and while it can approximate all bipartite nonsignalling correlations, it is known to be insufficient for reproducing certain multipartite quantum correlations. In particular, there exist tripartite quantum correlations that cannot be simulated using only classical PR boxes. Motivated by the observation that PR boxes are inherently classical in their input-output interface, we study an upgraded resource set that includes classical-quantum PR boxes and tripartite entanglement. We show that there exists a nonlocal game such that even with this quantum generalization, players cannot outperform strategies that use only tripartite quantum states. Consequently, there exist tripartite nonsignalling correlations that remain unattainable under this augmented resource set. This result then extends immediately to the set of bipartite nonsignalling correlations, with classical inputs and outputs, combined with tripartite quantum states.

Abstract: Achieving computational advantage using NISQ devices on practically useful problems is a long standing challenge. We report two papers that experimentally demonstrate a concrete application, namely certified randomness generation, which could be useful for multi-party cryptographic protocols and improving imperfect physical sources of randomness. Both papers involve substantial theoretical contributions to the protocol. We devise a realistic protocol that maximizes practical hardness. The verifier first asks the server to prepare a quantum state using a random circuit and then sends a random measurement basis right before the result must be received. This is repeated for many rounds. We show complexity theoretic evidence for entropy generation and provide improved entropy bounds against adversaries with oracle access to the random circuits. We also construct an end-to-end application of randomness amplification of imperfect sources into nearly perfect randomness, notably achieving everlasting security which uplifts computational security to information theoretic security.

Abstract: Combinatorial optimization is considered a promising class of problems in which quantum computers can show significant advantages. However, problems of practical relevance typically have more variables than current or foreseeable quantum computers have qubits. Here we introduce a divide and conquer approach that partitions the optimization problem into subgraphs that can be represented on smaller quantum processors. We then find all states of the subgraphs that can possibly be part of the solution to the entire problem by determining the cost or energy ranges in which the local subgraph energies of these states must be contained. This allows us to reduce the problem by only considering the subspace spanned by these states. We then recombine the system using a binary encoding for each subgraph with a local energy ordering. This process can be iterated until no further reduction is possible. We also find that the number of necessary qubits can be reduced further when only retaining states in a fraction of the relevant energy range at very little expense in terms of approximation ratio to the global ground state. In numerical simulations, we find that our approach allows us to solve combinatorial optimization problems on weighted random 3-regular graphs with $|\mathcal{V}|=40$ discrete variables on $\sim |\mathcal{V}| / 4$ qubits while retaining a possible approximation ratio of $\sim99.9\%$. We also observe an increasing reduction with larger system sizes.

Abstract: We introduce a general model of stochastically generated matrix product states (MPS) in which the local tensors share a common distribution and form a strictly stationary sequence, without requiring spatial independence. Under natural conditions on the associated transfer operators, we prove the existence of thermodynamic limits of expectation values of local observables and establish almost-sure exponential decay of two-point correlations. In the homogeneous (random translation-invariant) case, for any error tolerance in probability, the two-point function decays exponentially in the distance between the two sites, with a deterministic rate. In the i.i.d.\ case, the exponential decay still holds with a deterministic rate, with the probability approaching one exponentially fast in the distance. For strictly stationary ensembles with decaying spatial dependence, the correlation decay quantitatively reflects the mixing profile: $\rho$–mixing yields polynomial bounds with high probability, while stretched-exponential (resp. exponential) decay in $\rho$ (resp. $\beta$) yields stretched-exponential (resp. exponential) decay of the two-point function, again with correspondingly strong high-probability guarantees. Altogether, the framework unifies and extends recent progress on stationary ergodic ensembles and Gaussian translation-invariant ensembles, providing a transfer-operator route to typical correlation decay in random MPS.

Abstract: Quantum algorithms for binary optimization problems have been subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth $p$ but does not depend on the graph size. Evaluating this formula for Max-$k$-Cut problem for $p\leq 4$, we identify pararegimes ($k=3$ with degree $d \leq 10$ and $k=4$ with $d \leq 40$) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline, we introduce a new heuristic algorithm based on the degree-of-saturation which empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth $p\leq 20$. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.

Abstract: Shallow quantum circuits have attracted increasing attention in recent years, due to the fact that current noisy quantum hardware can only perform faithful quantum computation for a short amount of time. The constant-depth quantum circuits $\mathsf{QAC}^0$, a quantum counterpart of $\mathsf{AC}^0$ circuits, are the polynomial-size and constant-depth quantum circuits composed of only single-qubit unitaries and polynomial-size generalized Toffoli gates. The computational power of $\mathsf{QAC}^0$ has been extensively investigated in recent years. In this paper, we are concerned with $\mathsf{QLC}^0$ circuits, which are linear-size $\mathsf{QAC}^0$ circuits, a quantum counterpart of $\mathsf{LC}^0$. * We show that depth-$d$ $\mathsf{QAC}^0$ circuits working on $n$ input qubits and $a$ ancilla qubits have approximate degree at most $\tilde{O}((n+a)^{1-2^{-d}})$, improving the $\tilde{O}((n+a)^{1-3^{-d}})$ degree upper bound of previous works. Consequently, this directly implies that to compute the parity function, $\mathsf{QAC}^0$ circuits need at least $\tilde{O}(n^{1+2^{-d}})$ circuit size. * We present the first agnostic learning algorithm for $\mathsf{QLC}^0$ channels using subexponential running time and queries. Moreover, we also establish exponential lower bounds on the query complexity of learning $\mathsf{QAC}^0$ channels under both the spectral norm distance of the Choi matrix and the diamond norm distance. * We present a tolerant testing algorithm which determines whether an unknown quantum channel is a $\mathsf{QLC}^0$ channel. This tolerant testing algorithm is based on our agnostic learning algorithm. Our approach leverages low-degree approximations of $\mathsf{QAC}^0$ circuits and Pauli analysis as key technical tools. Collectively, these results advance our understanding of agnostic learning for shallow quantum circuits.

Abstract: We prove the decidability results for a sub-class of local state transformation problems, a fundamental problem in quantum information theory and quantum communication complexity. A local state transformation is specified by two bipartite quantum states $\rho^{AB}$ and $\sigma^{AB}$. Two non-communicating parties, Alice and Bob are provided with unbounded copies of the source state $\rho^{AB}$. The goal is to determine whether they can generate the target state that is arbitrarily close to the target state $\sigma^{AB}$ without communication. Ghazi, Kamath, and Sudan initiated the study of the decidability of the classical counterpart, non-interactive simulation of joint distributions, by introducing a machinery built on the theory of analysis on Boolean functions. With such a machinery, the decidability of non-interactive simulation of joint distributions was fully resolved by subsequent works. However, the decidability of local state transformations remains largely open. Qin and Yao resolved the case where the source state $\rho^{AB}$ is a noisy maximally entangled state. In this work, we show that whenever the source state $\rho^{AB}$ is classical, then local state transformations are decidable. Specifically, given $\delta>0$, the algorithm either outputs local operations that transform the source state to a state that is $\delta$-close to the target state or asserts that such local operations do not exist.

Abstract: The quality of an Trotterized quantum evolution is often characterized using the spectral norm between the exact and Trotter evolutions. This worst-case scenario approach overestimate the error in most cases, which translate in an overestimation of the resources required to perform the evolution with a target accuracy. In this work, we introduce an approach to characterize the quality of a Trotterized evolution for finite-size quantum systems based on the infidelity between the states prepared by the exact evolution and the Trotterized evolution. We relate the fidelity to a phase operator, which is central to this approach and can be constructed using the multivariate Baker-Campbell-Hausdorff formula. We demonstrate the utility of that operator by using its eigenbasis to construct the state which maximizes the Trotter infidelity. That infidelity acts as an exact bound for the infidelity of any state evolved using a Trotterized evolution. We compare the Trotter infidelity to the operator norm distance to get insights on why the later generally overestimate the Trotter error in practice. We then study the infidelity bound in the limits of short evolutions and of a large number of Trotter steps. While we focus on the first-order Trotterization, some results and conclusions directly apply to second order or higher.

Abstract: Erasure recovery is a fundamental aspect of classical data storage, especially in distributed systems where data redundancy and local repair are essential for reliability. Extending these ideas to the quantum domain provides valuable insights for developing robust and scalable quantum memories. In quantum information theory, erasures—where the positions of lost qubits are known—are generally easier to correct than arbitrary errors, which require both detection and correction. This distinction simplifies recovery protocols and enhances fault tolerance. Recent experimental advances have demonstrated that detected quantum errors can be converted into erasures in physical systems such as neutral-atom–based and superconducting qubit architectures, highlighting the practical importance of studying quantum erasure recovery. Quantum locally recoverable codes (QLRCs) have recently gained attention as a framework for achieving efficient quantum storage with local recovery capabilities. Analogous to their classical counterparts, QLRCs allow a lost qubit to be reconstructed using only a small subset of other qubits, thereby reducing the resource and operational overhead in recovery. In this work, we extend the study of QLRCs by considering $(r,\delta)$-QLRCs characterized by locality parameter $r$ and local distance $\delta \geq 2$. We present constructions of both random and explicit $(r,\delta)$-QLRCs, including explicit families based on the quantum Tamo–Barg construction. We also present an efficient decoding algorithm for these quantum Tamo-Barg codes. Furthermore, we introduce quantum \emph{hierarchical} locally recoverable codes (QHLRCs), which extend local recovery to multiple hierarchical levels. For any integer $h\geq 2$, we construct both random and explicit $h$-level QHLRCs—the latter being $h$-level quantum Tamo–Barg codes—and establish a Singleton-like bound for these codes using a CSS framework built from dual-containing classical codes. These results advance the theoretical foundations of quantum erasure recovery and contribute to the design of efficient quantum storage architectures.

Abstract: We present a complete set of rewrite rules for multi-qudit Clifford circuits, where \emph{qudit} denotes a d-level quantum system with d an odd prime. Completeness means that any two Clifford circuits representing the same linear map can be transformed into each other using these rules. In total, there are 19 \emph{Clifford relations}, each involving at most three qudits and admitting an intuitive interpretation. Our approach leverages the isomorphism between the symplectic group $\mathrm{Sp}(2n, \mathbb{Z}_d)$ and the quotient of the Clifford group by the Pauli group. We first derive a complete set of \emph{symplectic relations} for $\mathrm{Sp}(2n, \mathbb{Z}_d)$, and then lift them to Clifford relations by incorporating Pauli corrections. To do this, we introduce a \emph{symplectic normal form} that captures the stabiliser tableau of a Clifford operator and is unique up to Pauli correction. This simplification enables a streamlined derivation of a complete set of 66 relations, which we further compress to 18 symplectic relations. Our computations in $\mathrm{Sp}(2n, \mathbb{Z}_d)$ are formalised in the Agda proof assistant, providing a machine-verified proof of correctness.

Abstract: Approximate quantum error correction (AQEC) provides a versatile framework for both quantum information processing and probing many-body entanglement. We reveal a fundamental tension between the error-correcting power of an AQEC and the hardness of code state preparation. More precisely, through a novel application of the Lov\'asz local lemma, we establish a fundamental trade-off between local indistinguishability and circuit complexity, showing that orthogonal short-range entangled states must be distinguishable via a local operator. These results offer a powerful tool for exploring quantum circuit complexity across diverse settings. As applications, we derive stronger constraints on the complexity of AQEC codes with transversal logical gates and establish strong complexity lower bounds for W state preparation. Our framework also provides a novel perspective for systems with Lieb-Schultz-Mattis type constraints.

Abstract: We study the capacity of a quantum channel for retrocausal communication, where messages are transmitted backward in time, from a sender in the future to a receiver in the past, through a noisy postselected closed timelike curve (P-CTC) mathematically represented by the channel. We completely characterize the one-shot retrocausal quantum and classical capacities, and we show that the corresponding asymptotic capacities are equal to the average and sum, respectively, of the channel's max-information and its regularized Doeblin information. This endows these information measures with a novel operational interpretation. Furthermore, our characterization can be generalized beyond quantum channels to all completely positive maps. This imposes information-theoretic limits on transmitting messages via postselected-teleportation-like mechanisms with arbitrary initial- and final-state boundary conditions, including those considered in various black-hole final-state models.

Abstract: The study of feedback control inspired by Maxwell's demon is central to the understanding of the relationship between thermodynamics and information. In this paper, we establish fundamental lower limits on the work costs of system conversion with quantum feedback, where quantum side information acquired in advance can be fed back to the system coherently by a controller. From two basic operational principles that every physically admissible feedback-control scheme should satisfy, we derive the tightest possible bounds on the single-shot work of formation and extractable work of an arbitrary quantum system given arbitrary quantum side information held by the controller. These bounds are expressed in terms of information measures generalizing both mutual informations and relative entropies. In the asymptotic limit, they lead to a generalized second law of thermodynamics with quantum feedback, featuring a conditional Helmholtz free energy. Our findings provide precise thermodynamic meanings for the negativity of single-shot conditional entropies and resolve an open problem in the axiomatic reconstruction of such conditional entropies.

Abstract: For many information processing tasks, de Finetti-style theorems can often simplify the analysis in worst-case input scenarios for which the task exhibits some permutation-invariance symmetry, as it can allow for a reduction from an analysis on worst-case inputs to that of i.i.d. inputs. If further information is available on the inputs, it might be advantageous to reflect this information in the de Finetti reduction. In our work, we focus on a form of such constraint, based on the type of the input. This allows us to obtain a conceptually simple proof of a new de Finetti reduction for classical probability distributions, derived from elementary properties from the method of types. We apply our constrained de Finetti reduction to the compression of quantum interactive communication protocols with classical inputs, and prove that the prior-free quantum information cost equals the worst-case input amortized quantum communication cost.

Abstract: The traditional framework of quantum metrology commonly assumes unlimited access to resources, overlooking resource constraints in realistic scenarios. As such, the optimal strategies therein can be infeasible in practice. Here, we investigate quantum metrology where the total energy consumption of the probe state preparation, intermediate control operations, and the final measurement is subject to a constraint. We establish a comprehensive theoretical framework for characterizing energy-constrained multi-step quantum processes, based on which we develop a general optimization method for energy-constrained quantum metrology that determines both the optimal precision and the corresponding strategy. Using the method, we determine the ultimate precision limit of energy-constrained phase estimation and identify a novel advantage of quantum superpositions of causal orders in enhancing the energy efficiency of adaptive quantum estimation.

Abstract: We establish new theoretical results demonstrating the efficiency and robustness of system–bath interaction models for quantum thermal and ground state preparation. Unlike prior analyses, which typically relies on the Lindblad limit and require vanishing coupling strengths $o(1)$, we rigorously show that efficient state preparation remains possible far beyond this regime, even when the cumulative coupling strength is $\Theta(1)$. We first prove that even with constant cumulative coupling strength, the induced quantum channel still approximately fixes the target state. For thermal state preparation, we then develop a general perturbative framework that yields end-to-end complexity bounds outside weak coupling, and in particular proves that the mixing time scales as the inverse square of the coupling strength. This framework extends to broad Hamiltonian for which KMS detailed balance Lindbladians are known to mix. These bounds substantially improve upon prior results, and numerical simulations further confirm the robustness of the system–bath interaction framework across both weak and strong coupling regimes.

Abstract: Rare events, though infrequent, can have significant impacts across various domains. We present a quantum algorithm for efficiently sampling rare events from stochastic processes. Our algorithm constructs quantum sample states that superpose only rare events, defined as those occurring with probability below a threshold \(\Delta\). The algorithm consists of three key steps: (1) constructing an amplitude block encoding from the quantum sample state of the original process, (2) implementing quantum singular value transformation of a polynomial approximation of a thresholding function, and (3) performing measurement and post-selection. For sufficiently large sequence lengths, we prove that our algorithm achieves a quadratic speedup over classical methods, requiring only \(\Theta(1/\sqrt{\Delta})\) queries to prepare an even superposition over rare events, compared to the classical \(\mathcal{O}(1/\Delta)\) complexity. We demonstrate our algorithm's effectiveness through numerical simulations on the Dyson-Ising chain, showing successful identification and amplification of rare events while suppressing non-rare events.

Abstract: Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that: 1. Any quantum state $2$-design yields unconditional pseudorandomness against both $\QNC^0$ circuits with arbitrarily many ancillae and $\AC^0\circ\QNC^0$ circuits with nearly linear ancillae. 2. Random phased subspace states, where the phases are picked using a $4$-wise independent function, are unconditionally pseudoentangled against the above circuit classes. 3. Any unitary $2$-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $\QNC^0$ adversaries, even with limited $\AC^0$ postprocessing. Our results stand in stark contrast to the standard guarantee of the $2$-design property, which only ensures that they cannot be distinguished from Haar random ensembles using two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.

Abstract: Density matrix exponentiation (DME) is a general procedure that converts an unknown quantum state into the Hamiltonian evolution. This enables state-dependent operations and can reveal nontrivial properties of the state, among other applications, without full tomography. However, it has been proven that for any physical process, the DME requires $\Theta(1/\varepsilon)$ state copies in error $\varepsilon$. In this work, we go beyond the lower bound and propose a procedure called the \textit{virtual} DME that achieves $\mathcal{O}(\log(1/\varepsilon))$ or $\mathcal{O}(1)$ state copies, by using non-physical processes. Using the virtual DME in place of its conventional counterpart realizes a general-purpose quantum algorithm for property estimation, that achieves \textit{exponential} circuit-depth reductions over existing protocols across tasks including quantum principal component analysis, quantum emulator, calculation of nonlinear functions such as entropy, and linear system solver with quantum precomputation. In such quantum algorithms, the non-physical process for virtual DME can be effectively simulated via simple classical post-processing while retaining a near-unity measurement overhead. We numerically verify this small constant overhead together with the exponential reduction of copy count in the quantum principal component analysis task. The number of state copies used in our algorithm essentially saturates the theoretical lower bound we proved.

Abstract: Deep thermalization refers to the emergence of Haar-like randomness from quantum systems upon partial measurements. As a generalization of quantum thermalization, it is often associated with high complexity and entanglement. Here, we introduce computational deep thermalization and construct the fastest possible dynamics exhibiting it at infinite effective temperature. Our circuit dynamics produce quantum states with low entanglement in polylogarithmic depth that are indistinguishable from Haar random states to any computationally bounded observer. Importantly, the observer is allowed to request many copies of the same residual state obtained from partial projective measurements on the state --- this condition is beyond the standard settings of quantum pseudorandomness, but natural for deep thermalization.

Abstract: We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one-way state generators (OWSGs), digital signature schemes, quantum bit commitments, and private key encryption schemes. We also discuss evidence for these hardness assumptions by analyzing the best-known quantum learning algorithms, as well as proving black-box lower bounds for cloning and learning given state preparation oracles. Our random circuit-based constructions provide concrete instantiations of quantum crypto- graphic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to NISQ-friendly quantum cryp- tography. We discuss noise tolerant versions of our OWSG and digital signature constructions which can potentially be implementable on noisy quantum computers connected by a quantum network. On the other hand, they are still secure against noiseless quantum adversaries, raising the intriguing possibility of a useful implementation of an end-to-end cryptographic protocol on near-term quantum computers. Finally, our explorations suggest that the rich interconnections between learning theory and cryptography in classical theoretical computer science also extend to the quantum setting.

Abstract: Recent experimental progress on platforms with movable qubits motivates more efficient designs of logical operations by leveraging long-range connectivity. In our recent works, we address two bottleneck issues on the rotated surface code (RSC)—the logical S gate and T state preparation—by proposing a transversal logical S gate protocol (for the first time) and a new magic state cultivation (MSC) protocol (achieving an order of magnitude reduction in spacetime cost compared to the original MSC protocol). Both our protocols leverage the dynamics of circuits to perform desired logical operations efficiently. In our S gate protocol, we move beyond traditional schemes where transversal logical gates take place between syndrome extraction (SE) rounds. Instead, we embed our fold-transversal logical operation within a single SE round by leveraging the time dynamics of data and ancilla qubits during SE. In our MSC protocol, we co-design two types of codes—the RP code, a variant of the surface code on RP^2 (a non-orientable surface), and the SRP code, a self-dual CSS code—with compact circuits bridging between them to tightly knit fault-tolerant gadgets together and maintain high end-to-end efficiency. Our protocols, together with transversal CNOT and H gates, constitute a new way that fully leverages long-range connectivity to perform universal logical operations on the RSC.

Abstract: It is well-known that the conditional mutual information of a quantum state is zero if, and only if, the quantum state is a quantum Markov chain. Replacing the Umegaki relative entropy in the definition of the conditional mutual information by the Belavkin-Staszewski (BS) relative entropy, we obtain the BS-conditional mutual information, and we call the states with zero BS-conditional mutual information Belavkin-Staszewski quantum Markov chains. In this article, we establish a correspondence which relates quantum Markov chains and BS-quantum Markov chains. This correspondence allows us to find a recovery map for the BS-entropy in the spirit of the Petz recovery map. Furthermore, we show that, over the set of BS-quantum Markov chains, this correspondence constitutes an entanglement-breaking map. Moreover, we prove a structural decomposition of the Belavkin-Staszewski quantum Markov chains and also study states for which the BS-conditional mutual information is only approximately zero. We subsequently extend the aforementioned correspondence, structural decomposition and recovery map to arbitrary pairs of states and conditional expectations. As an application of the correspondence, we find the first family of states with non-vanishing conditional mutual information for which it decays superexponentially fast with the size of the middle system.

Abstract: We show that if an adaptive Z2-linear measurement-based quantum computing protocol deterministically computes a non-affine Boolean function, then the underlying quantum resource satisfies an inconsistent set of linear equations. This witnesses an algebraic form of strong contextuality generalising Mermin’s All-versus-Nothing arguments. Such algebraic contextuality can be detected cohomologically, resolving an open question posed by Raussendorf, who had established cohomological witnesses of contextuality for non-adaptive protocols, but left the adaptive case open. We prove this result constructively: we model adaptive measurement protocols as ordinary measurements on a scenario of tree-like measurements, and explicitly build the inconsistent equations inductively.

Abstract: In this work, we study a nonlocal game with two questions and three answers per player, which was first considered by Feige in 1991, and show that there is quantum advantage in this game. We prove that the game is a robust self-test for the 3-dimensional maximally entangled state. Furthermore, we show that the game can be seen as the "or" of two games that each do not have quantum advantage. Lastly, we investigate the behavior of the game with respect to parallel repetition in the classical, quantum and non-signalling case and obtain perfect parallel repetition of the non-signalling value if Feige's game is repeated an even amount of times.

Abstract: We study MaxCut on 3-regular graphs of minimum girth g for various g’s. We obtain new lower bounds on the maximum cut achievable in such graphs by analyzing the Quantum Approximate Optimization Algorithm (QAOA). For g ≥ 16, at depth p ≥ 7, the QAOA improves on previously known lower bounds. Our bounds are established through classical numerical analysis of the QAOA’s expected performance. This analysis does not produce the actual cuts but establishes their existence. When implemented on a quantum computer, the QAOA provides an efficient algorithm for finding such cuts, using a constant- depth quantum circuit. To our knowledge, this gives an exponential speedup over the best known classical algorithm guaranteed to achieve cuts of this size on graphs of this girth. Furthermore, our guaranteed cut fractions apply to random instances of large 3-regular graphs since they are effectively large girth for our purposes. We also apply the QAOA to the Maximum Independent Set problem on the same class of graphs.

Abstract: Quantum machine learning can be fast when linear-algebra subroutines are paired with the right data and access models. This paper organizes QML’s leading algorithms mostly under an HHL framework, assembling a side-by-side runtime table and making explicit the conditions that govern real gains: efficient state preparation, sparsity, condition numbers, and readout. We pinpoint where exponential advantages plausibly survive (e.g., quantum-assisted Gaussian process regression with polylog-sparse, well-conditioned kernels, and topological data analysis on engineered complexes), and where advantages shrink to strong polynomial factors, especially under full-vector recovery or dense, ill-conditioned matrices. We also align these claims with quantum-inspired ''dequantized'' methods that narrow several gaps, and we frame payoffs using a quantum-economic lens, highlighting near-term, high-yield workloads and longer-term hardware/data access needs.

Abstract: Classical simulation of quantum systems is fundamental to understanding the boundary between classical and quantum computing. The two leading approaches, tensor networks (TN) and the stabilizer formalism (SF), have traditionally been viewed as distinct, with seemingly disconnected sources of computational hardness. The complexity of TN methods is dictated by entanglement, while SF complexity is governed by the amount of "magic". This leads to a disconnect: states that are simple for one formalism can be maximally complex for the other. For instance, highly entangled stabilizer states are trivial for SF but can be intractable for TN methods. This raises a crucial question: Is there a unified framework or a single indicator that can diagnose the relationship between these two simulation paradigms? In this work, we provide such an indicator, which we term bra-ket entanglement (BKE). We investigate the classical simulation of the general process U OU†, where O can be any operator, from a quantum resource perspective. We show that BKE serves as a crucial diagnostic tool that reveals a deep connection between the resources governing TN and SF. Our central finding is that as the BKE of the initial operator O increases, the simulation resources required by the two approaches transition from being uncorrelated to being highly correlated.

Abstract: We investigate Lindbladian fast-forwarding and its applications to estimating Gibbs state properties. Fast-forwarding refers to the ability to simulate a system of time $t$ using significantly fewer than $t$ queries or circuit depth. While various Hamiltonian systems are known to circumvent the no fast-forwarding theorem, analogous results for dissipative dynamics, governed by Lindbladians, remain largely unexplored. We first present a quantum algorithm for simulating purely dissipative Lindbladians with unitary jump operators, achieving additive query complexity $ \mathcal{O}\left(t + \frac{\log(\varepsilon^{-1})}{\log\log(\varepsilon^{-1})}\right)$ up to error~$\varepsilon$, improving previous algorithms. When the jump operators have certain structures (i.e., block-diagonal Paulis), the algorithm can be modified to achieve exponential fast-forwarding, attaining circuit depth $\mathcal{O}\left(\log\left(t + \frac{\log(\varepsilon^{-1})}{\log\log(\varepsilon^{-1})}\right)\right)$, while preserving query complexity. Using these fast-forwarding techniques, we develop a quantum algorithm for estimating Gibbs state properties of the form $\langle \psi_1 | e^{-\beta(H + I)} | \psi_2 \rangle$, up to additive error $\epsilon$, with $H$ the Hamiltonian and $\beta$ the inverse temperature. For input states exhibiting certain coherence conditions ---e.g.,~$\langle 0|^{\otimes n} e^{-\beta(H + I)} |+\rangle^{\otimes n}$---our method achieves exponential improvement in complexity (measured by circuit depth), $\mathcal{O} (2^{-n/2} \epsilon^{-1} \log \beta ),$ compared to the quantum singular value transformation-based approach, with complexity $\tilde{\mathcal{O}} (\epsilon^{-1} \sqrt{\beta} )$. We show how to apply this exponential improvement to applications such as the ground state overlap testing and amplitude estimation. For general $| \psi_1 \rangle$ and $| \psi_2 \rangle$, we also show how the level of improvement is changed with the coherence resource in $| \psi_1 \rangle$ and $| \psi_2 \rangle$.

Abstract: Quantum effect enables enhanced estimation precision in metrology, with the Heisenberg limit (HL) representing the ultimate limit allowed by quantum mechanics. Although the HL is generally unattainable in the presence of noise, quantum error correction (QEC) can recover the HL in various scenarios. A notable example is estimating a Pauli-$Z$ signal under bit-flip noise using the repetition code, which is both optimal for metrology and robust against noise. However, previous protocols often assume noise affects only the signal accumulation step, while the QEC operations---including state preparation and measurement---are noiseless. To overcome this limitation, we study fault-tolerant quantum metrology where all qubit operations are subject to noise. We focus on estimating a Pauli-$Z$ signal under bit-flip noise, together with state preparation and measurement errors in all QEC operations. We propose a fault-tolerant metrological protocol where a repetition code is prepared via repeated syndrome measurements, followed by a fault-tolerant logical measurement. We demonstrate the existence of an error threshold, below which errors are effectively suppressed and the HL is attained.

Abstract: Evolution in adiabatic quantum computing is famously polynomial-equivalent to evolution in the circuit model of quantum computation. Herein, we are not interested in translating an arbitrary unitary from one model to another, but instead in describing a particular class of evolutions in both models. Specifically, we are interested in when an evolution with quantum signal processing (QSP) is arbitrarily close to a unitary adiabatic evolution, without assuming a small qubit overhead, and when the reverse statement is true. The QSP circuit will be determined by a set of real phase factors, for some given signal operator. The quantum adiabatic evolution will be determined by the scalar functions $\Vec{x}$ used to parameterize $H(\Vec{x}(s))$. We show that in the high-degree and small-signal limit, a class of QSP circuits applied to an eigenstate of $H(0)$ and the result of the adiabatic evolution can be made close, with a direct functional relationship between the adiabatic schedule and the set of phase factors that determine the QSP circuit.

Abstract: Efficient and coherent data retrieval and storage are essential for harnessing quantum algorithms' speedup. Such a fundamental task is addressed by a quantum Random Access Memory (qRAM). Despite their promising scaling properties, current qRAM proposals demand excessive resources and rely on operations beyond the capabilities of current hardware requirements, rendering their practical realization inefficient. We introduce a novel architecture that significantly reduces resource requirements while preserving optimal complexity scaling for quantum queries. Moreover, unlike previous proposals, our algorithm design leverages a simple, repeated operational block based exclusively on local unitary operations and short-range interactions between a limited number of quantum walkers traveling over a single binary tree. This novel approach not only simplifies experimental requirements by reducing the complexity of necessary operations but also enhances the architecture's scalability by ensuring a resource-efficient, modular design that maintains optimal quantum query performance.

Abstract: Simulating open quantum systems is essential for modeling realistic dynamics beyond closed-system Hamiltonian evolution. Such dynamics are described by the Lindblad master equation for Markovian systems and arise in fields ranging from condensed matter and quantum chemistry to quantum optics and noise analysis in quantum devices. Existing algorithms typically rely on sparse-access or linear-combination-of-unitaries input models. We propose an alternative framework, Wave Matrix Lindbladization, inspired by density matrix exponentiation for sample-based Hamiltonian simulation. In this model, Hamiltonians and Lindblad operators are encoded directly into program states, enabling sample-based Lindbladian simulation. We present algorithms for this task, analyze their sample and gate complexities, and demonstrate both efficiency and optimality. We also show that our algorithms achieve better sample complexity than any tomographic strategy for Lindbladian simulation. This further suggests a form of quantum copy-protection, where program states allow Lindbladian simulation without revealing the operators they encode.

Abstract: Fault-tolerant quantum computers use decoders to monitor for errors and find a plausible correction. A decoder may provide a decoder confidence score (DCS) to gauge its success. We adopt a swim distance DCS, computed from the shortest path between syndrome clusters. By contracting tensor networks, we compare its performance under phenomenological noise to the well-known complementary gap and find that both reliably estimate the logical error probability (LEP) in a decoding window. We explore ways to use this to mitigate the LEP in entire logical circuits. For shallow circuits, we just abort if any decoding window produces an exceptionally low DCS: for a distance-13 surface code under circuit-level noise, rejecting a mere 0.1% of possible DCS values improves the entire circuit's LEP by more than 5 orders of magnitude. For larger algorithms comprising up to billions of windows, DCS-based rejection remains effective for enhancing observable estimation. Moreover, one can use the DCS to assign each circuit's output a unique LEP, and use it as a basis for maximum likelihood estimation. This can reduce the effects of noise by an order of magnitude at no quantum cost; methods can be combined for further improvements.

Abstract: Estimating quantum time-series such as the Loschmidt echo $f(t)=\langle\psi|\mathrm{e}^{-\mathrm{i}Ht}|\psi\rangle$ is central to spectroscopy and Hamiltonian analysis. Direct estimation via the Hadamard test requires controlled implementations of $\mathrm{e}^{-\mathrm{i}Ht}$, and the depth of these controlled circuits grows with $t$, making long-time estimation challenging on near-term hardware. Inspired by the classical Phaselift approach to phase retrieval, we introduce Quantum Phaselift, a lifting-based framework that estimates the rank-one matrix $Z = f f^\dagger$ sampled at discrete times instead of $f$ directly. We propose quantum circuits for estimating the entries of $Z$ and prove that measuring only a narrow band of this matrix around the diagonal provides sufficient data for unique signal reconstruction. This reformulation reduces the depth of required controlled circuits to scale with the width of the measured band, rather than with the total evolution time. We then show that generic signals can be recovered from a band of width $O(1)$, providing a substantial savings in controlled operations compared to naïve algorithms. We develop three robust estimators to recover the signal from the noisy measurements of the entries on this narrow band: a block-by-block algebraic estimator, a block-by-block eigenvector estimator, and a least-squares estimator. We rigorously prove exact recovery for all three estimators in the noiseless setting and establish stability guarantees and sample complexity bounds for the block-by-block algebraic estimator in the presence of measurement noise. Finally, we numerically demonstrate that high-quality signal recovery is possible for the 2D Fermi-Hubbard and 2D transverse-field Ising model time-series with more than 100 points using only a few million samples and reasonable post-processing time, making our recovery techniques efficient and effective for near-term implementations.

Abstract: Tamper-resilient cryptography studies how to protect data against adversaries who can physically manipulate codewords before they are decoded. The notion of tamper detection codes formalizes this goal, requiring that any unauthorized modification be detected with high probability. Classical results, starting from Jafargholi and Wichs (TCC 2015), established the existence of such codes against very large families of tampering functions—subject to structural restrictions ruling out identity and constant maps. Recent works of Boddu and Kapshikar (Quantum, 7) and Bergamaschi (Eurocrypt 2024) have extended these ideas to quantum adversaries, but only consider unitary tampering families. In this work, we give the first general treatment of quantum tamper detection against arbitrary quantum maps. We show that Haar-random encoding schemes achieve exponentially small soundness error against any adversarial family whose size, Kraus rank, and entanglement fidelity obey natural constraints, which are direct quantum analogues of the min-entropy and fixed-point restrictions in the classical setting. Our results unify and extend previous work, subsuming both the classical and unitary-only adversarial families. Beyond this, we demonstrate a fundamental separation between classical and quantum tamper detection. Classically, relaxed tamper detection (which allows either rejection or recovery of the original message) cannot protect even against the family of constant functions. This family is of size $2^n$. In contrast, we show that quantum encodings can handle this obstruction, and we conjecture and provide evidence that they may in fact provide relaxed tamper detection and non-malleable security against any family of quantum maps of size up to $2^{2^{\alpha n}}$ for any constant $\alpha <\frac{1}{2}$, leading to our conjecture on the existence of what we call \emph{universal} quantum tamper detection. Taken together, our results provide evidence that quantum tamper detection is strictly more powerful than its classical counterpart.

Abstract: Quantum channel capacities are fundamental to quantum information theory. Their definition, however, does not limit the computational resources of sender and receiver. In this work, we initiate the study of computational quantum capacities. These quantify how much information can be reliably transmitted when imposing the natural requirement that en- and decoding have to be computationally efficient. We focus on the computational two-way quantum capacity and showcase that it is closely related to the computational distillable entanglement of the Choi state of the channel. This connection allows us to show a stark computational capacity separation. Under standard cryptographic assumptions, there exists a quantum channel of polynomial complexity whose computational two-way quantum capacity vanishes while its unbounded counterpart is nearly maximal. More so, we show that there exists a sharp transition in computational quantum capacity from nearly maximal to zero when the channel complexity leaves the polynomial realm. Our results demonstrate that the natural requirement of computational efficiency can radically alter the limits of quantum communication.

Abstract: We present a modular algorithm for learning external potentials in continuous-space free-fermion models including Coulomb potentials. Compared to the lattice-based approaches, the continuum presents new mathematical challenges: the state space is infinite-dimensional and the Hamiltonian contains the Laplacian, which is unbounded in the continuum and produces an unbounded speed of information propagation. Our framework addresses these difficulties through novel optimization methods and information-propagation bounds in combination with a priori regularity assumptions on the external potential. The resulting algorithm provides a unified and robust approach to learn both Coulomb interactions and other classes of physically relevant potentials, like trigonometric polynomials or general smooth functions. One possible application is to learn the charge and position of nuclei and ions distributed in continuous space as in quantum chemistry. Our results thus lay the foundations for a scalable and generalizable toolkit to explore fermionic systems governed by continuous-space interactions. Moreover, we provide numerical evidence supporting the classical post-processing algorithm of our Coulomb algorithm.

Abstract: In the current Noisy Intermediate-Scale Quantum (NISQ) era, noise is widely viewed as a primary obstacle to fault-tolerant quantum computation. In this work, we flip this perspective by demonstrating that noise can be harnessed constructively in key quantum algorithms. First, drawing on the Eigenstate Thermalization Hypothesis, we show that using both classical and quantum simulations that noise generically accelerates Gibbs state preparation. In our model, we find that phase-flip noise, and more generally Haar-random noise, drives localized thermalization that yields speedups of up to a factor of ∼3.5× as compared to noiseless systems. We also show that this induces thermalization in systems that would otherwise fail to do so. Building on this, we further show that intrinsic noise can be selectively leveraged to emulate nonunitary dynamics, enabling efficient simulation of open quantum systems without encoding dissipation into unitary circuits. By preserving physical noise rather than correcting it entirely, we show that this approach reduces qubit and gate overhead and relaxes fidelity requirements on quantum hardware. Taken together, these results establish a paradigm in which noise is harnessed as a computational resource, enabling practical quantum advantages on near-term and future quantum devices.

Abstract: Learning the closest matrix product state (MPS) representation of a quantum state is known to enable useful tools for prediction and analysis of complex quantum systems. In this work, we study the problem of learning MPS in following setting: given many copies of an input MPS, the task is to recover a classical description of the state. The best known polynomial-time algorithm, introduced by [LCLP10, CPF+10], requires linear circuit depth and $O(n^5)$ samples, and has seen no improvement in over a decade. The combination of linear circuit depth and large sample complexity, neither known to be optimal, renders existing algorithms impractical for near-term quantum devices with limited resources. We show a new efficient MPS learning algorithm that runs in $O(\log n)$ depth and has sample complexity $O(n^3)$. Also, we can generalize our algorithm to learn the closest MPS state, in which the input state is not guaranteed to be close to the MPS with a fixed bond dimension. Our algorithms also improve both sample complexity and circuit depth of the previous known algorithm. On the lower bound side, we show that every algorithm must use $\Omega(n)$ copies of the state.

Abstract: Motivated by the limitations of near-term quantum devices, we study nonlocal games in the highnoise regime, where the two players may share arbitrarily many copies of a noisy entangled state. In this regime, existing rigidity theorems are unable to certify any nontrivial quantum structure. We first characterize the maximal quantum winning probabilities of the CHSH game[CHSH69], the Magic Square game[Mer90a], and their 2-out-of-𝑛 variants [CRSV18] as explicit functions of the noise rate. These characterizations enable the construction of device-independent protocols for estimating the underlying noise level. Building on these results, we prove noise-robust rigidity theorems showing that these games ceritify one, two, and n pairs of anticommuting Pauli observables, respectively. To our knowledge, these are the first rigidity results of Pauli measurements that remain sound in the highnoise regime, which has applications in Measurement-Device-Independent (MDI) cryptography and studying the computational power of Multi-prover Interactive Proof System with entanglement and a vanishing completeness-soundness gap (MIP∗0). Our proofs rely on Sum-of-Squares decompositions and Pauli analysis techniques originating from quantum proof systems and quantum learning theory, respectively.

Abstract: With sensitive information encoded in data, it is important to ensure the privacy to those sensitive information while learning useful information about the data. Towards that, quantum versions of differential privacy frameworks have been introduced. Privatizing data often comes with a cost. Meaning that, there are perfectly private mechanisms one could use that may lead to no utility depending on the application. However, privacy-utility tradeoffs in the quantum setting are not extensively studied. In this work, we study optimal privacy-utility tradeoffs for both generic and application-specific utility metrics when privacy is quantified by $(\varepsilon,\delta)$-quantum local differential privacy. As generic measures, we focus on optimizing fidelity and trace distance between the original state and the privatized state, showing that the depolarizing mechanism achieves the optimal utility while obtaining analytical expressions for utility for all privacy parameter regimes. Next, we study a specific application where one needs to learn the expectation of an observable with respect to an input state (property of quantum data), given access to only privatized states. There, we obtain a lower bound on the number of samples of privatized data required to achieve a fixed accuracy guarantee with high probability by utilizing lower bounds on private quantum hypothesis testing. We also obtain private mechanisms that achieve order optimality with respect to the privacy parameters and accuracy parameters, showcasing how the awareness of the task can be utilized to improve the utility in contrast to using mechanisms that optimize generic utility metrics. Furthermore, we show that the number of samples required to privately learn the expectation values scales as $\Theta((\varepsilon \beta)^{-2})$, where $\varepsilon \in (0,1)$ is the privacy parameter and $\beta$ is the accuracy tolerance. We also study a private version of classical shadows, which may be useful for the private estimation of properties of quantum states and processes.

Abstract: We investigate quantum Markov semigroups on bosonic Fock space and identify a broad class of infinite-dimensional dissipative evolutions that exhibit instantaneous Sobolev-regularization. Motivated by stability problems in quantum computation, we show that for certain Lindblad operators that are polynomials of creation and annihilation operators, the resulting dynamics immediately transform any initial state into one with finite expectation in all powers of the number operator. A key application is in the bosonic cat code, where we obtain explicit estimates in the trace norm for the speed of convergence. These estimates sharpen existing perturbative bounds at both short and long times, offering new analytic tools for assessing stability and error suppression in bosonic quantum information processing. For example, we improve the strong exponential convergence of the (shifted) $2$-photon dissipation to its fixed point to the uniform topology.

Abstract: Efficient block encoding of many-body Hamiltonians is a central requirement for quantum algorithms in scientific computing, particularly in the early fault-tolerant era. In this work, we introduce new explicit constructions for block encoding second-quantized Hamiltonians that substantially reduce Clifford+T gate complexity and ancilla overhead. By utilizing a data lookup strategy based on the SWAP architecture for the \sparnew oracle $O_C$, and a direct sampling method for the \ampnew oracle $O_A$ with SELECT-SWAP architecture, we achieve a T count that scales as $\mathcal{\tilde{O}}(\sqrt{L})$ with respect to the number of interaction terms $L$ in general second-quantized Hamiltonians. We also achieve an improved constant factor in the Clifford gate count of our oracle. Furthermore, we design a block encoding that directly targets the $\eta$-particle subspace, thereby reducing the subnormalization factor from $\mathcal{O}(L)$ to $\mathcal{O}(\sqrt{L})$, and improving fault-tolerant efficiency when simulating systems with fixed particle numbers. Building on the block encoding framework developed for general many-body Hamiltonians, we extend our approach to electronic Hamiltonians whose coefficient tensors exhibit translation invariance or possess decaying structures. Our results provide a practical path toward early fault-tolerant quantum simulation of many-body systems, substantially lowering resource overheads compared to previous methods.

Abstract: Fault-tolerant capacities quantify the ability of a quantum channel to reliably transmit information when every component of the encoding and decoding procedure is noisy. Earlier work analyzed achievable communication rates under such noise using fault-tolerant implementations based on concatenated codes with a single logical qubit. In this work, we develop an alternative approach using concatenations of quantum Hamming codes, which offer constant space overhead by encoding many logical qubits simultaneously. We introduce modular techniques for implementing fault-tolerant circuits with quantum input/output interfaces using the concatenated quantum Hamming code. These tools enable an analysis of fault-tolerant entanglement-assisted communication that is not only simpler, but also yields substantially higher achievable communication rates than previous methods, owing to the limited noise correlations in syndrome qubits of high-rate quantum Hamming codes.

Abstract: Quantum learning from remotely accessed and a priori unknown quantum data must address two key challenges: verifying the correctness of data and ensuring the privacy of the learner’s data-collection strategies and resulting conclusions. The covert (verifiable) learning model of Canetti and Karchmer (TCC 2021) provides a framework for endowing classical learning algorithms with such guarantees, protecting against computationally bounded adversaries who observe and tamper with public oracle queries. However, their framework has two drawbacks: it relies on computational hardness assumptions and does not flexibly accommodate richer data-access models, such as quantum ones. In this work, we propose models of covert verifiable learning in quantum learning theory and realize them without computational hardness assumptions for remote data access scenarios motivated by established quantum data advantages. We consider two privacy notions: (i) strategy-covertness, where the eavesdropper does not gain information about the learner's strategy; and (ii) target-covertness, where the eavesdropper does not gain information about the unknown object being learned. We show: - Strategy-covert algorithms for making quantum statistical queries via classical shadows; - Target-covert algorithms for: - learning quadratic functions from public quantum examples and private quantum statistical queries; - Pauli shadow tomography and stabilizer state learning from public multi-copy and private single-copy quantum measurements; - solving Forrelation and Simon's problem from public quantum queries and private classical queries, where the adversary is an i.i.d. ancilla-free eavesdropper. The lattermost results in particular establish that the exponential separation between classical and quantum queries for Forrelation and Simon’s problem survives under covertness constraints. Along the way, we design covert verifiable protocols for quantum data acquisition from public quantum queries which may be of independent interest. Overall, our models and corresponding algorithms demonstrate that quantum advantages are privately and verifiably achievable even with untrusted, remote data.

Abstract: Interacting spin systems in solids underpin a wide range of quantum technologies, from quantum sensors and single-photon sources to spin-defect-based quantum registers and processors. We develop a quantum-computer-aided framework for simulating such devices using a general electron spin resonance Hamiltonian incorporating zero-field splitting, the Zeeman effect, hyperfine interactions, dipole-dipole spin-spin terms, and electron-phonon decoherence. Within this model, we combine Gray-encoded qudit-to-qubit mappings, qubit-wise commuting aggregation, and a multi-reference selected quantum Krylov fast-forwarding (sQKFF) hybrid algorithm to access long-time dynamics while remaining compatible with NISQ and early fault-tolerant hardware constraints. Numerical simulations demonstrate the computation of autocorrelation functions up to ∼ 100 ns, together with microwave absorption spectra and the ℓ1-norm of coherence, achieving 18-30% reductions in gate counts and circuit depth for Trotterized time-evolution circuits compared to unoptimized implementations. Using the nitrogen vacancy center in diamond as a testbed, we benchmark the framework against classical simulations and identify the reference-state selection in sQKFF as the primary factor governing accuracy at fixed hardware cost. This methodology provides a flexible blueprint for using quantum computers to design, compare, and optimize solid-state spin-qubit technologies under experimentally realistic conditions.

Abstract: We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density, generalizing work of El Alaoui, Montanari, and Sellke for Maximum Cut through a connection between random CSPs and mean-field Ising spin glasses. For CSPs with even predicates, the algorithm asymptotically solves a stochastic optimal control problem dual to an extended Parisi variational principle. This gives an optimal fraction of satisfied constraints among algorithms obstructed by the branching overlap gap property of Huang and Sellke, notably including the Quantum Approximate Optimization Algorithm and all quantum circuits on a bounded-degree architecture of up to $\epsilon cdot \log n$ depth.

Abstract: Efficient entanglement distillation is a central task in quantum information science and future quantum networks. At the core of distillation protocols are the quantum error correction and detection schemes which enhance the fidelity of entangled pairs. Conventional protocols focus on digital systems, where good error correction schemes typically require complicated compiled circuits, high-fidelity multi-qubit operations and delicate pulse-level control that impose high demands on near-term hardware. Crucially, the leading physical platforms for quantum networks, trapped ions and neutral atoms, are governed by native many-body Hamiltonians inherently suited for analog, continuous-time evolution. Adopting these natural dynamics is significantly simpler than engineering digital logic via delicate pulse-level control. Motivated by this experimental reality, we seek to leverage the intrinsic analog capabilities for efficient entanglement distillation. In this work, we introduce the Hamiltonian entanglement distillation protocol, which exploits the intrinsic information scrambling generated by random time evolution under native Hamiltonians. We establish a quantitative connection between output fidelity and Out-of-Time-Ordered Correlators, showing that efficient scrambling directly implies good distillation performance. Since generic Hamiltonians are naturally efficient scramblers, the capability for distillation is ubiquitous: almost all Hamiltonians in the Hilbert space suffice for high-fidelity distillation. Numerical simulations of representative Rydberg-atom and trapped-ion systems further confirm that robust performance could be achieved using only short-range interactions and evolution times feasible in current experiments. By avoiding the complexity of digital circuit control, our approach substantially relaxes experimental requirements, providing a scalable route to entanglement engineering on current analog quantum platforms.

Abstract: Quantum theory is in principle compatible with scenarios where physical processes occur in an indefinite order, potentially yielding advantages in a broad range of information processing tasks. However, advantages in communication, the most basic form of information processing, have so far remained controversial and hard to prove. Here we provide a framework for assessing the role of causal order in communication, by comparing different causal structures under the constraint that the allowed operations must not generate signaling from signaling-incapable devices. Using this framework, we establish a clear-cut advantage of indefinite causal order, and, at the same time, we identify a series of fundamental limits to the communication power of causal structures in quantum mechanics. Notably, we find that a special form of indefinite causal order, obtained by coherently controlling the order of two processes, enhances the transmission of classical messages in a one-shot scenario, but no quantum operation with indefinite order can offer advantages over shared entanglement when asymptotically many uses of the same communication device are employed. Overall, our results unveil non-trivial relations between communication, causal order, entanglement, and no-signaling quantum processes.

Abstract: The no-cloning theorem in quantum mechanics has been used as a basis for quantum money constructions, which guarantee unconditionally unforgeable currency. Existing schemes, however, either (i) require long-term quantum memory and quantum communication between the user and the bank in order to verify the validity of a bill or (ii) fail to protect user privacy due to the uniqueness of each bill issued by the bank, which can allow its usage to be tracked. We introduce a construction of single-use quantum money that gives users the ability to detect whether the issuing authority is tracking them, employing an auditing procedure for which we prove unconditional security. The use of our scheme does not require long-term quantum memory or quantum communication from the users themselves since their validation is a purely classical operation, making the protocol relatively practical to deploy. We discuss potential applications beyond money, including anonymous one-time pads and voting.

Abstract: We investigate the notion of untelegraphable encryption (UTE), a quantum encryption primitive that is a special case of uncloneable encryption (UE), where the adversary’s capabilities are restricted to producing purely classical information rather than arbitrary quantum states. We present an unconditionally secure construction of UTE that achieves untelegraphable-indistinguishability security, together with natural multi-ciphertext and bounded collusion-resistant extensions, without requiring any additional assumptions. We also extend this to the unbounded case, assuming pseudo-random unitaries, yielding everlasting security. Furthermore, we derive results on UE using approaches from UTE in the following ways: first, we provide new lower bounds on UTE, which give new lower bounds on UE; second, we prove an asymptotic equivalence between UTE and UE in the regime where the number of adversaries in UE grows. These results suggest that UTE may provide a new path toward achieving a central open problem in the area: indistinguishability security for UE in the plain model.

Abstract: Decoders are a critical component of fault-tolerant quantum computing. They must identify errors based on syndrome measurements to correct quantum states. While finding the optimal correction is NP-hard and thus extremely difficult, approximate decoders with faster runtime often rely on uncontrolled heuristics. In this work, we propose a family of hierarchical quantum decoders with a tunable trade-off between speed and accuracy while retaining guarantees of optimality. We use the Lasserre Sum-of-Squares (SOS) hierarchy from optimization theory to relax the decoding problem. This approach creates a sequence of Semidefinite Programs (SDPs). Lower levels of the hierarchy are faster but approximate, while higher levels are slower but more accurate. We demonstrate that even low levels of this hierarchy significantly outperform standard Linear Programming relaxations. Our results on rotated surface codes and honeycomb color codes show that the SOS decoder approaches the performance of exact decoding. We find that Levels 2 and 3 of our hierarchy perform nearly as well as the exact solver. We analyze the convergence using rank-loop criteria and compare the method against other relaxation schemes. This work bridges the gap between fast heuristics and rigorous optimal decoding.

Abstract: Amplitude estimation, in its original form, is formulated as phase estimation upon the amplification walk operator. Since its introduction, subsequent improvements made to the algorithm have removed the use of phase estimation and introduced low-depth variants that trade speedup factors with circuit depth. In this paper, we formalize amplitude estimation as a phase difference estimation problem solvable by ancilla-free phase estimation, and provide two algorithms for both near-Heisenberg-limited and low-depth circuit guarantees inspired by development in early fault-tolerant statistical phase estimation. Our algorithms provide a simpler classical post-processing procedure compared to prior work for both near-Heisenberg-limited and low-depth regimes. Numerical results show that our near-Heisenberg-limited algorithm performs on par with prior work, and our low-depth version supports the query-depth tradeoff in terms of runtime speedups.

Abstract: There exist two types of universality in quantum computation: strict and computational universalities. The former is known to be stronger than the latter. In this presentation, we give a method of transforming from the computational universality with an elementary gate set {H,CCZ} to the strict universality by using a maximally imaginary state |+i>, which is an eigenstate of the Pauli-Y operator. From the viewpoint of resource theory, it would be intriguing whether the maximum imaginarity is necessary for the universality transformation. We show that |+i> is a unique resource state up to free operations. More precisely, we obtain the stronger conclusion that if a given resource state cannot be used for the universality transformation, then the realizable quantum gates are restricted to only orthogonal operators. This implies that by rotating a single-qubit state from the eigenstate |+> of the Pauli-X operator to |+i>, we can observe a kind of phase transition. The first half of our results has been published in PRL 133, 050601 (2024).

Abstract: Molecular dynamics simulations are a central computational methodology in materials design for relating atomic composition to mechanical properties. However, simulating materials with atomic-level resolution on a macroscopic scale is infeasible on current classical hardware, even when using the simplest elastic network models (ENMs) that represent molecular vibrations as a network of coupled oscillators. To address this issue, we introduce Quantum Elastic Network Models (QENMs) and utilize the quantum algorithm of Babbush et al. (PRX, 2023), which offers an exponential advantage when simulating systems of coupled oscillators under some specific conditions and assumptions. Here, we demonstrate how our method enables the efficient simulation of planar materials. As an example, we apply our algorithm to the task of simulating a 2D graphene sheet. We analyze the exact complexity for initial-state preparation, Hamiltonian simulation, and measurement of this material, and provide two real-world applications: heat transfer and the out-of-plane rippling effect. We estimate that an atomistic simulation of a graphene sheet on the centimeter scale, classically requiring hundreds of petabytes of memory and prohibitive runtimes, could be encoded and simulated with as few as ∼160 logical qubits.

Abstract: Solving linear ordinary differential equations (ODE) is one of the most promising applications for quantum computers to demonstrate exponential advantages. The challenge of designing a quantum ODE algorithm is how to embed non-unitary dynamics into intrinsically unitary quantum circuits. In this work, we propose a new quantum algorithm for solving ODEs by harnessing open quantum systems. Specifically, we propose a novel technique called non-diagonal density matrix encoding, which leverages the inherent non-unitary dynamics of Lindbladians to encode general linear ODEs into the non-diagonal blocks of density matrices. This framework enables us to design quantum algorithms with both theoretical simplicity and high performance. Combined with the state-of-the-art quantum Lindbladian simulation algorithms, our algorithm can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters under a plausible input model. We also give applications of our algorithm including the Gibbs state preparations and the partition function estimations.

Abstract: Functional encryption is a powerful cryptographic primitive that enables fine- grained access to encrypted data and underlies numerous applications. Although the ideal security notion for FE—simulation security—has been shown to be impossible in the classical setting, those impossibility results rely on inherently classical arguments. This leaves open the question of whether simulation-secure functional encryption can be achieved in the quantum regime. In this work, we rule out this possibility by showing that the classical impossibility results largely extend to the quantum world. In particular, when the adversary can issue an un- bounded number of challenge messages, we prove an unconditional impossibility, matching the classical barrier. In the case where the adversary may obtain many functional keys, clas- sical arguments only yield impossibility under the assumption of pseudorandom functions; we strengthen this by proving impossibility under the potentially weaker assumption of pseudo- random quantum states. In the same setting, we also establish an alternative impossibility based on public-key encryption. Since public-key encryption is not known to imply pseudo- random quantum states, this provides independent evidence of the barrier. As part of our proofs, we show a novel incompressibility property for pseudorandom states, which may be of independent interest.

Abstract: Embedding the vertices of arbitrary graphs into trees while minimizing some measure of overlap is an important problem with applications in computer science and physics. In this work, we consider the problem of bijectively embedding the vertices of an $n$-vertex graph $G$ into the \emph{leaves} of an $n$-leaf \emph{rooted binary tree} $\mathcal{T}$. The congestion of such an embedding is given by the largest size of the cut induced by the two components obtained by deleting any vertex of $\mathcal{T}$. We show that for any embedding, the congestion lies between $\lambda_2(G)\cdot 2n/9$ and $\lambda_n(G)\cdot n/4$, letting $0=\lambda_1(G)\le \cdots \le \lambda_n(G)$ be the Laplacian eigenvalues of $G$, and there is an embedding for which the congestion is at most $\lambda_n(G)\cdot 2n/9$. Beyond these general bounds, we determine the congestion exactly for hypercubes and lattice graphs, and obtain asymptotically tight bounds for random regular graphs and Erd\H os–R\'enyi graphs. We further introduce an efficient contraction procedure based on spectral ordering and dynamic programming, which produces low-congestion embeddings in practice. Numerical experiments on structured graphs, random graphs, and tensor network representations of quantum circuits validate our theoretical bounds and demonstrate the effectiveness of the proposed method. These results yield new spectral bounds on the memory and time complexity of exact tensor network contraction in terms of the underlying graph structure.

Abstract: We give novel and tighter lifting theorems for security games in the quantum random oracle model (QROM), as well as in Noisy Intermediate-Scale Quantum (NISQ) settings such as the hybrid query model, the noisy oracle and the bounded-depth models. At the core of our main results lies a novel measure-and-reprogram framework that we call coherent reprogramming. This framework gives a tighter lifting theorem for query complexity problems. Secondly, we provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries, as well as a lifting theorem for quantum algo- rithms with access to noisy oracles or bounded quantum depth. At the core of these results lies a novel measure-and-reprogram framework, called hybrid coherent measure-and-reprogramming, tailored specifically for hybrid algorithms. Equipped with both lifting theorems, we are able to prove directly both quantum and NISQ security and complexity results by calculating a single combinatorial quantity, relying solely on classical reasoning. Crucially, we derive the first direct product theorems in the average case, both in the quantum and the hybrid settings— i.e., an enabling tool to determine the hardness of solving multi- instance security games. This allows us to derive in a straightforward manner the hardness of various security games, for example (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.

Abstract: Decoding quantum error-correcting codes is a key challenge in enabling fault-tolerant quantum computation. In the classical setting, linear programming (LP) decoders offer provable performance guarantees and can leverage fast practical optimization algorithms. Although LP decoders have been proposed for quantum codes, their performance and limitations remain relatively underexplored. In this work, we uncover a key limitation of LP decoding for quantum low-density parity-check (LDPC) codes: certain constant-weight error patterns lead to ambiguous fractional solutions that cannot be resolved through independent rounding. To address this issue, we incorporate a post-processing technique known as ordered statistics decoding (OSD), which significantly enhances LP decoding performance in practice. Our results show that LP decoding, when augmented with OSD, can outperform belief propagation with the same post-processing for intermediate code sizes of up to hundreds of qubits. These findings suggest that LP-based decoders, equipped with effective post-processing, offer a promising approach for decoding near-term quantum LDPC codes.

Abstract: Quantum mechanics provides cryptographic primitives whose security is grounded in hardness assumptions independent of those underlying classical cryptography. However, existing proposals require low-noise quantum communication and long-lived quantum memory, capabilities which remain challenging to realize in practice. In this work, we introduce a quantum digital signature scheme that operates with only classical communication, using the classical shadows of states produced by random circuits as public keys. We provide theoretical and numerical evidence supporting the conjectured hardness of learning the private key (the circuit) from the public key (the shadow). A key technical ingredient enabling our scheme is an improved state-certification primitive that achieves higher noise tolerance and lower sample complexity than prior methods. We realize this certification by designing a high-rate error-detecting code tailored to our random-circuit ensemble and experimentally generating shadows for 32-qubit states using circuits with ≥ 80 logical (≥ 582 physical) two-qubit gates, attaining 0.90±0.01 fidelity. With increased number of measurement samples, our hardware-demonstrated primitives realize a proof-of-principle quantum digital signature, demonstrating the near-term feasibility of our scheme.

Abstract: In recent years, the quantum oracle model introduced by Aaronson and Kuperberg (2007) has found a lot of use in showing oracle separations between complexity classes and cryptographic primitives. It is generally assumed that proof techniques that do not relativize with respect to quantum oracles will also not relativize with respect to classical oracles. We show that this is not the case by showing a complexity class containment that relativizes with respect to classical oracles but not with quantum oracles. Specifically, we show that there is a quantum oracle problem that is contained in the class QMA, but not in a class we call polyQCPH. However, with respect to classical oracles, QMA is contained in polyQCPH, because polyQCPH is equal to PSPACE with respect to classical oracles. Our result works for bounded-error complexity classes, thus it resolves an open problem from Aaronson (2009). We also show that the same separation holds relative to a distributional oracle, which is a model introduced by Natarajan and Nirkhe (2024). We believe our findings show the need for some caution when using these non-standard oracle models, particularly when showing separa- tions between quantum and classical resources.

Abstract: We introduce a 0.611-approximation algorithm for Quantum MaxCut (QMC) and a 0.8395-approximation algorithm for the EPR Hamiltonian. A novel ingredient in the QMC approximation is to partially entangle pairs of qubits associated to edges in a matching, while preserving the direction of their single-qubit Bloch vectors. This allows us to interpolate between product states and matching-based states with a tunable parameter. For the EPR Hamiltonian, our improvement comes from a new nonlinear monogamy-of-entanglement bound on star graphs and a refined parameterization of a shallow quantum circuit from previous works. We also prove limitations showing that current methods cannot achieve substantially better approximation ratios, indicating that further progress will require fundamentally new techniques.

Abstract: Analytical and algebraic geometry are valuable tools for dealing with problems involving analytical functions and polynomials. In what we connote as spatial quantum sensing the goal is, given an underlying field and a set of quantum sensors interrogating the field in a set of positions, to find an estimator for some property the field. This property can have multiple forms, be it distinguishing the source of a target signal, or evaluating the field (or a derivative thereof) in an arbitrary position. In this work we also link this problem to the development of networks of quantum sensors, and the role and usefulness of entangling these sensors. We find that the estimators that come out as a solution to the problem are such that a non-local entangled strategy provides maximum precision. We start by working under the assumption of polynomial fields, which relates to the interpolation problem, and then generalize for any signal that is modeled via analytical functions, giving rise to any general least-squares estimator. We discuss the effects of the placement of the sensors in the estimation, namely, how to find well defined, construction error-free placements for the sensors. In the case of interpolation we provide concrete examples and proofs in a $m$-dimensional array of sensors, and discuss necessary and sufficient conditions for the more general cases. We provide clear examples of the possible use-cases and statements, and compare a non-local entangled strategy with the best local strategy for an interpolation problem, showing the benefit in terms of precision in a distributed sensing scenario. This is a key tool for a wide-range of problem in sensing problems, ranging from large-scale such as earth-sized experiments, to local-scale, such has biological experiments.

Abstract: In adversarial settings, where attackers can deliberately and strategically corrupt quantum data, standard quantum error correction reaches its limits. It can only correct up to half the code distance and must output a unique answer. Quantum list decoding offers a promising alternative. By allowing the decoder to output a short list of possible errors, it becomes possible to tolerate far more errors, even under worst-case noise. But two fundamental questions remain: which quantum codes support list decoding, and can we design decoding schemes that are secure against efficient, computationally bounded adversaries? In this work, we answer both. To identify which codes are list-decodable, we provide a generalized version of the Knill-Laflamme conditions. Then, using tools from quantum cryptography, we build an unambiguous list decoding protocol based on pseudorandom unitaries. Our scheme is secure against any quantum polynomial-time adversary, even across multiple decoding attempts, in contrast to previous schemes. Our approach connects coding theory with complexity-based quantum cryptography, paving the way for secure quantum information processing in adversarial settings.

Abstract: Neutral atom quantum computers and to a lesser extent trapped ions may suffer from atom loss. In this work, we investigate the impact of atom loss in long chains of trapped ions. Even though this is a relatively rare event, ion loss in long chains must be addressed because it destabilizes the entire chain resulting in the loss of all the qubits of the chain. We propose a solution to the chain loss problem based on (1) a quantum error correction code distributed over multiple long chains, (2) beacon qubits within each long chain to detect the loss of a chain, and (3) a decoder adapted to correct a combination of circuit faults and erasures after beacon qubits convert chain losses into erasures. We verify the chain loss correction capability of our scheme through circuit level simulations with a distributed $[[72,12,6]]$ BB code with beacon qubits.

Abstract: We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: 1. We exhibit a problem, {Avoid One Encrypted String} (\AOES), whose classical randomized query complexity is O(1) but is maximally hard for pseudo-deterministic quantum algorithms (\Omega(N) query complexity). 2.We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(\log(N)) vs. \Theta(\sqrt{N})), while the randomized query complexity is O(1). Complementing these separations, we show that for any total problem R, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., \D(R) = \tilde O(\psQ(R)^5). On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, k-sum, and graph collision.

Abstract: The homological product is a general-purpose recipe that forges new quantum codes from arbitrary classical or quantum input codes, often providing enhanced error-correcting properties. When the input codes are classical linear codes, it is also known as the hypergraph product. We investigate structured homological product codes that admit logical operations arising from permutation symmetries in their input codes. We present a broad theoretical framework that characterizes the logical operations resulting from these underlying automorphisms. In general, these logical operations can be performed by a combination of physical qubit permutations and a subsystem circuit. In special cases related to symmetries of the input Tanner graphs, logical operations can be performed solely through qubit permutations. We further demonstrate that these "automorphism gadgets" can possess inherent fault-tolerant properties such as effective distance preservation, assuming physical permutations are free. Finally, we survey the literature of classical linear codes with rich automorphism structures and show how various classical code families fit into our framework. Complementary to other fault-tolerant gadgets for homological product codes, our results further advance the search for practical fault tolerance beyond topological codes in platforms capable of long-range connectivity.

Abstract: Quantum state discrimination is a fundamental primitive in quantum information processing, underpinning tasks in quantum communication, sensing, and learning. We study this problem through the lens of semidefinite programming and develop a general dimension-reduction framework for optimal discrimination. Our approach applies to (i) ensembles of pure states (not necessarily linearly independent), (ii) mixed states, and (iii) fully general discrimination settings in which the set of guesses and the reward assigned to each guess--state pair are arbitrary. This formulation encompasses standard minimum-error discrimination, minimum-error exclusion, discrimination with penalties for incorrect guesses, and structured reward models arising in problems such as quantum anomaly detection. We show that the resulting semidefinite program can be reduced from dimension $dL$ to $NL$, where $d$ is the Hilbert space dimension of the states, $N$ is the number of candidate states, and $L$ is the size of the set of possible guesses. Importantly, we further introduce a quantum pre-processing procedure which, given quantum access to the states to be discriminated, efficiently constructs the reduced semidefinite program, enabling our method to operate directly on quantum data. As an application, we characterize optimal identification probabilities for quantum changepoint problems in several regimes, including multiple-changepoint settings that were previously computationally inaccessible.

Abstract: There are many known oracle problems that provably separate BPP and BQP. There are also many kinds of interactive proof systems that have been developed over the last twenty years to make quantum computations done by a BQP machine verifiable by a BPP machine. Sadly, none of these techniques trivially relativize to oracle problems. This leads us to the following question: do these oracle problems also admit an interactive proof between a BQP prover and a BPP verifier, or is the existence of such interactive proof provably impossible? We show that Simon's problem and the Forrelation problem, who were pretty much the only known oracle problems for which the previous question was still unanswered, do admit interactive proofs, under the assumption that the verifier has small and limited quantum capabilities. To do so, we introduce the first ever known interactive proofs with a BQP prover for these problems, as well as their corresponding proofs of security (completeness and soundness).

Abstract: We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While they give provable complexity speedups and they can be apply to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs, which we obtain by adjusting the parameters of these algorithms and combining them with "quantized" classical strategies.

Abstract: We consider quantum realizations of extremal correlations in arbitrary contextuality scenarios and prove that, for all such scenarios, no extremal indeterministic correlation can be achieved using projective quantum measurements, i.e., there exists no quantum state and no set of projective measurements, for any contextuality scenario, that can achieve such correlations. This no-go result follows as a corollary of a more general no-go theorem that holds when POVMs are taken into account. This general no-go theorem entails that no non-trivial quantum realization of an extremal indeterministic correlation exists, i.e., any "quantum" realization must be simulable by classical randomness.

Abstract: In this work, we study the sample complexity of two variants of product testing when restricted to single-copy measurements. In particular, we consider both bipartite product testing (i.e., does there exist at least one non-trivial cut across which the state is product) and multipartite product testing (i.e., is the state fully product across every cut). For the first variant, we prove an exponential lower bound on the sample complexity of any algorithm for this task which utilizes only single-copy measurements. When comparing this with known efficient algorithms that utilize multi-copy measurements, this establishes an exponential separation for this and several related entanglement learning tasks. For the second variant, we prove another sample lower bound that establishes a separation between single- and multi-copy strategies. To obtain our results, we prove a crucial technical lemma that gives a lower bound on the overlap between tensor products of permutation operators acting on subsystems of states that themselves carry a tensor structure. Finally, we provide an algorithm for multipartite product testing using only single-copy, local measurements, and we highlight several interesting open questions arising from this work.

Abstract: The ability to fault-tolerantly prepare cat states, also known as multi-qubit GHZ states, is an important primitive for quantum error correction. It is required for Shor-style syndrome extraction, and can also be used as a subroutine for doing fault-tolerant state preparation of CSS codewords. Existing approaches to fault-tolerant cat state preparations have been found using computationally expensive heuristics involving SAT solving, reinforcement learning or exhaustive analysis. In this paper we constructively find optimal circuits for cat states in a scalable way. In particular, we derive formal lower bounds on the number of CNOT gates required for circuits implementing n-qubit cat-states that do not spread errors of weight at most t for values t = 1, ..., 5. We do this by using fault-equivalent rewrites of ZX-diagrams to reduce it to a problem of characterising certain 3-regular simple graphs. We provide explicit constructions for circuits that match this lower bound for all n and t <= 5. Furthermore, we use SAT solvers to construct circuits for all n <= 50 and t <= 7. We additionally show how to trade CNOT count against depth, in particular allowing us to construct constant-depth fault-tolerant implementations using O(n) ancilla and O(n) CNOT gates.

Abstract: State preparation compilers for quantum computers typically sit at two extremes: general-purpose routines that treat the target as an opaque amplitude vector, and bespoke constructions for a handful of well-known state families. We ask whether a compiler can instead accept simple, structure-aware specifications while providing predictable resource guarantees. We answer this by designing and implementing a quantum state-preparation compiler for regular language states (RLS): uniform superpositions over bitstrings accepted by a regular description, and their complements. Users describe the target state via (i) a finite set of bitstrings, (ii) a regular expression, or (iii) a deterministic finite automaton (DFA), optionally with a complement flag. By translating the input to a DFA, minimizing it, and mapping it to an optimal matrix product state (MPS), the compiler obtains an intermediate representation (IR) that exposes and compresses hidden structure. The efficient DFA representation and minimization offloads expensive linear algebra computation in exchange of simpler automata manipulations. The combination of the regular-language frontend and this IR gives concise specifications not only for RLS but also for their complements that might otherwise require exponentially large state descriptions. This enables state preparation of an RLS or its complement with the same asymptotic resources and compile time, which to our knowledge is not supported by existing compilers. We outline two hardware-aware backends: SeqRLSP, which yields linear-depth, ancilla-free circuits for linear nearest-neighbor architectures via sequential generation, and TreeRLSP, which achieves logarithmic depth on all-to-all connectivity via a tree tensor network. On the theory side, we prove circuit-depth and gate-count bounds that scale with the system size and the maximal Schmidt rank of the target state, and we give compile-time bounds that expose the benefit of the initial DFA representation. We implement the full pipeline and evaluate it on Dicke and W states, random uniform superpositions, and complement states, comparing against general-purpose, sparse-state, and specialized baselines.

Abstract: Quantum simulation is a central application of near-term quantum devices, pursued in both analog and digital architectures. A key challenge for both paradigms is the effect of imperfections and noise on predictive power. In this work, we present a rigorous and physically transparent comparison of the stability of digital and analog quantum simulators under a variety of perturbative noise models. We provide rigorous worst- and average-case error bounds for noisy quantum simulation of local observables. We find that the two paradigms show comparable scaling in the worst case, while exhibiting different forms of enhanced error cancellation on average. We further analyze Gaussian and Brownian noise processes, deriving concentration bounds that capture typical deviations beyond worst-case guarantees. These results provide a unified framework for quantifying the robustness of noisy quantum simulations and identify regimes where digital methods have intrinsic advantages and when we can see similar behavior.

Abstract: Quantum simulators enable the exploration of complex quantum phenomena in condensed-matter systems by reproducing their dynamics on controllable quantum devices. However, experimental constraints often restrict the class of Hamiltonians that can be realized natively. Hamiltonian engineering addresses this limitation by expanding the set of accessible target Hamiltonians from a fixed system Hamiltonian defined by the hardware. We introduce a new framework for fermionic Hamiltonian engineering based on conjugating free evolution under the system Hamiltonian with sequences of experimentally feasible local fermionic unitaries. The required sequences and free-evolution times are obtained efficiently via a linear program. By interleaving system evolution with these local unitaries, our method realizes effective time evolution under a broad class of target Hamiltonians with intrinsic robustness to implementation errors. In particular, we demonstrate that arbitrary complex tunnelling amplitudes can be realized, constrained only by the connectivity of the underlying system Hamiltonian. Our approach mitigates the challenge of uncontrolled heating commonly encountered in Floquet engineering.

Abstract: We study bipartite entanglement statistics in one-dimensional anyon chains, whose Hilbert spaces are constrained by fusion rules of unitary pre-modular categories. Our setup generalizes previous frameworks on symmetry-resolved entanglement entropy for non-abelian Lie group symmetries to the setting of quantum groups. We derive analytical expressions for the average anyonic entanglement entropy and its variance. Surprisingly, despite the constrained Hilbert space structure, the large $L$ expansion has no universal $O(\sqrt{L})$ or $O(1)$ symmetry-type corrections except for a subleading topological correction term that produces a Page curve asymmetry. We further show that the variance decays exponentially with system size, establishing the typicality. Numerical simulations of the integrable and quantum-chaotic golden chain Hamiltonian show that chaotic mid-spectrum eigenstates match the Haar-random predictions, supporting the use of eigenstate entanglement as a diagnostic of quantum chaos. Our results establish the anyonic Page curve as an appropriate chaotic benchmark in topological many-body systems and connect anyonic entanglement to Page-type universality in quantum many-body physics.

Abstract: While many bounds have been proved for partial trace inequalities over the last decades for a large variety of quantities, recent problems in quantum information theory demand sharper bounds. In this work, we study optimal bounds for partial trace quantities in terms of the spectrum; equivalently, we determine the best bounds attainable over unitary orbits of matrices. We solve this question for Schur-convex functionals acting on a single partial trace in terms of eigenvalues for self-adjoint matrices and then we extend these results to singular values of general matrices. We subsequently extend the study to Schur-convex functionals that act on several partial traces simultaneously and present sufficient conditions for sharpness. In cases where closed-form maximizers cannot be identified, we present quadratic programs that yield new computable upper bounds for any Schur-convex functional. We additionally present examples demonstrating improvements over previously known bounds. Finally, we conclude with the study of optimal bounds for an n-qubit system and its subsystems of dimension 2.

Abstract: Quantum Signal Processing (QSP), a framework for implementing matrix-valued polynomials, is a fundamental primitive in various quantum algorithms. Despite its versatility, a potentially underappreciated challenge is that all systematic protocols for implementing QSP rely on post-selection. This can impose prohibitive costs for tasks when amplitude amplification cannot sufficiently improve the success probability. For example, in the context of ground-state preparation, this occurs when using a too poor initial state. In this work, we introduce a new formula for implementing QSP transformations of Hermitian matrices, which requires neither auxiliary qubits nor post-selection. Rather, using approximation to the exact unitary synthesis, we leverage the theory of the double-bracket quantum algorithms to provide a new quantum algorithm for QSP, termed Double-Bracket QSP (DB-QSP). The algorithm requires the energy and energetic variance of the state to be measured at each step and has a recursive structure, which leads to circuit depths that can grow super exponentially with the degree of the polynomial. With these strengths and caveats in mind, DB-QSP should be viewed as complementing the established QSP toolkit. In particular, DB-QSP can deterministically implement low-degree polynomials to "warm start" QSP methods involving post-selection.

Abstract: We reveal the power of Grover’s algorithm from thermodynamic and geometric perspectives by showing that it is a product formula approximation of imaginary-time evolution (ITE), a Riemannian gradient flow on the special unitary group. This viewpoint uncovers three key insights. First, we show that the ITE dynamics trace the shortest path between the initial and the solution states in complex projective space. Second, we prove that the geodesic length of ITE determines the query complexity of Grover’s algorithm. This complexity notably aligns with the known optimal scaling for unstructured search. Lastly, utilizing the geodesic structure of ITE, we construct a quantum signal processing formulation for ITE without post-selection, and derive a new set of angles for the fixed-point search. These results collectively establish a deeper understanding of Grover's algorithm and suggest a potential role for thermodynamics and geometry in quantum algorithm design.

Abstract: Modern quantum devices require high-precision Hamiltonian dynamics, but environmental noise can cause calibrated Hamiltonian parameters to drift over time, necessitating expensive recalibration. Detecting when recalibration is needed is challenging, especially since the very gates required for sophisticated verification protocols may themselves be miscalibrated. While cloud quantum computing services implement heuristic routines for triggering recalibration, the fundamental limits of optimal recalibration have yet to be illuminated. Here we study the recalibration problem by developing efficient Hamiltonian certification and \changepoint{} detection protocols in the \emph{autonomous} setting. In this setting we use only single-qubit gates and measurements and do not use any ancilla qubits, making the protocols robust to the calibration issues for multi-qubit operations they aim to detect. For an unknown $n$-qubit $M$-sparse Hamiltonian $H$, our certification protocol distinguishes whether $\|H - H_0\|_F \geq \epsilon$ or $\|H - H_0\|_F \leq O(\epsilon/\sqrt{n})$ with sample complexity $\mathcal{O}(nM^2\ln(1/\delta)/\epsilon^2)$ and total evolution time $\mathcal{O}(nM\ln(1/\delta)/\epsilon^2)$, where $H_0$ is the target Hamiltonian and $\delta$ bounds the failure probability. The protocol achieves this by evolving random stabilizer product states and performing adaptive single-qubit measurements based on a classically simulable hypothesis state. Extending this to continuous monitoring, we develop an online \changepoint{} detection algorithm using the CUSUM procedure that achieves a detection delay bound of $\mathcal{O}(nM\ln(M\falsealarm{T})/\epsilon^2)$, matching the known asymptotically optimal scaling with respect to false alarm run length $\falsealarm{T}$. Our approach enables quantum devices to autonomously monitor their own calibration status without requiring ancillary systems, entangling operations, or a trusted reference device, and provides maximum-likelihood estimates of \changepoint{} locations to identify and rerun affected computations, offering a practical solution for robust quantum computing with contemporary noisy devices.

Abstract: We investigate the structure of $k$-positivity and Schmidt numbers for classes of linear maps and bipartite quantum states possessing symplectic group symmetry. Specifically, we consider (1) linear maps on $M_d(\mathbb{C})$ which are covariant under conjugation by unitary symplectic matrices $S$, and (2) $d\otimes d$ bipartite states which are invariant under $S\otimes S$ or $S\otimes \overline{S}$ actions, each parametrized by two real variables. We provide a complete characterization of all $k$-positivity and decomposability conditions for these maps and explicitly compute the Schmidt numbers for the corresponding bipartite states. In particular, our analysis yields a broad class of PPT states with Schmidt number $d/2$ and the first explicit constructions of $(d/2-1)$-positive indecomposable linear maps, achieving the best-known bounds. These constructions also allow us to exhibit PPT states with an arbitrarily large gap between the Schmidt number of a state and its partial transpose, improving on previously known examples. Our results thus provide a natural and analytically tractable setting in which both highly positive indecomposability and a high degree of PPT entanglement can be studied in full generality. Finally, we show that the PPT squared conjecture holds true within the classes of PPT linear maps which are either symplectic covariant or conjugate-symplectic covariant.

Abstract: Verification of quantum computations is crucial as experiments advance toward fault-tolerant quantum computing. Yet, no efficient protocol exists for certifying states generated in the Magic-State Injection model -- the foundation of several fault-tolerant quantum computing architectures. Here, we introduce an efficient protocol for certifying Clifford-enhanced Product States, a large class of quantum states obtained by applying an arbitrary Clifford circuit to a product of single-qubit, possibly magic, states. Our protocol only requires single-qubit Pauli measurements together with efficient classical post-processing, and has efficient sample complexity in both the independent (i.i.d.) and adversarial (non-i.i.d.) settings. This fills a key gap between Pauli-based certification schemes for stabilizer or (hyper)graph states and general protocols demanding non-Pauli measurements or classically intractable information about the target state. Our work provides the first efficient, Pauli-only certification protocol for the Magic-State Injection model, leading to practical verification of universal quantum computation under minimal experimental assumptions.

Abstract: We introduce the genuine multipartite Rains entanglement (GMRE) as a measure of genuine multipartite entanglement that can be computed using semi-definite programming. Similar to the Rains relative entropy (its bipartite counterpart), the GMRE is monotone under selective quantum operations that completely preserve the positivity of the partial transpose, implying that it is a multipartite entanglement monotone. As a consequence, we show that the GMRE bounds both the one-shot standard and probabilistic approximate GHZ-distillable entanglement from above. We also develop a generalization of this quantity that incorporates other entropies, including quantum Rényi relative entropies.

Abstract: Quantum transport on structured networks is strongly influenced by interference effects, which can dramatically modify how information propagates through a system. We develop a quantum-information-theoretic framework for scattering on graphs in which a full network of connected scattering sites is treated as a quantum channel linking designated input and output ports. Using the Redheffer star product to construct global scattering matrices from local ones, we identify resonant concatenation, a nonlinear composition rule generated by internal back-reflections. In contrast to ordinary channel concatenation, resonant concatenation can suppress noise and even produce super-activation of the quantum capacity, yielding positive capacity in configurations where each constituent channel individually has zero capacity. We illustrate these effects through models exhibiting resonant-tunneling-enhanced transport. Our approach provides a general methodology for analyzing coherent information flow in quantum graphs, with relevance for quantum communication, control, and simulation in structured environments.

Abstract: A many-body system, whether in contact with a large environment or evolving under complex dynamics, can typically be modeled as occupying the thermal state singled out by Jaynes' maximum entropy principle. Here, we find analogous fundamental principles identifying a noisy quantum channel $\mathcal{T}$ to model the system's dynamics, going beyond the study of its final equilibrium state. Our maximum channel entropy principle states that $\mathcal{T}$ should maximize the channel's entropy, suitably defined, subject to any available macroscopic constraints. These may correlate input and outputs, and may lead to restricted or partial thermalizing dynamics such as thermalization with average energy conservation. This principle is reinforced by an independent extension of the microcanonical derivation of the thermal state to channels, which leads to the same $\mathcal{T}$. Our technical contributions include a derivation of the general mathematical structure of $\mathcal{T}$, a custom postselection theorem relating an arbitrary permutation-invariant channel to nearby i.i.d. channels, as well as novel typicality results for quantum channels for noncommuting constraints and arbitrary input states. We propose a learning algorithm for quantum channels based on the maximum channel entropy principle, demonstrating the broader relevance of $\mathcal{T}$ beyond thermodynamics and complex many-body systems.

Abstract: Inspired by environmental sciences, we develop a framework to quantify the energy needed to generate quantum entanglement via noisy quantum channels, focusing on the hardware-independent, i.e. fundamental cost. Within this framework, we define a measure of the minimal fundamental energy consumption rate per distributed entanglement (expressed in Joule per ebit). We then derive a lower bound on the energy cost of distributing a maximally entangled state via a quantum channel, which yields a quantitative estimate of energy investment per entangled bit for future quantum networks. We thereby show that irreversibility in entanglement theory implies a non-zero energy cost in standard entanglement distribution protocols. We further establish an upper bound on the fundamental energy consumption rate of entanglement distribution by determining the minimal energy required to implement quantum operations via classical control. To this end, we formulate the axioms for an energy cost measure and introduce a Hamiltonian model for classically-controlled quantum operations. The fundamental cost is then defined as the infimum energy over all such Hamiltonian protocols, with or without specific hardware constraints. The study of the energy cost of a quantum operation is general enough to be naturally applicable to quantum computing and is of independent interest. Finally, we evaluate the energy demands of three entanglement distillation protocols for photonic polarization qubits, finding that, due to entanglement irreversibility, their required energy exceeds the fundamental lower bound by many orders of magnitude. The introduced paradigm can be applied to other quantum resources, with appropriate changes depending on their nature.

Abstract: Routing is the task of permuting qubits in such a way that quantum operations can be parallelized maximally, given constraints on the hardware geometry. When simulating fermions in the Jordan-Wigner encoding with qubits, a one-dimensional nearest-neighbor-connected geometry is effectively imposed on the system, independently of the underlying hardware, which means that naively, an O(N) depth routing overhead is incurred. Recently, Maskara et al. [arXiv:2509.08898] demonstrated that this routing overhead can be reduced to O(\log N) by decomposing general fermion routing into O(\log N) interleave permutations of depth O(1), using \Theta(N) ancillary qubits and employing measurements and feedforward. Here, we exhibit an alternative construction that achieves the same asymptotic performance. We also generalize the result in two ways. Firstly, we show that fermion routing can be performed in depth O(\log^2 N) \emph{without} ancillas, measurements, or feedforward. Secondly, we construct efficient mappings with O(\log^2 N) depth between all product-preserving ternary tree fermionic encodings, thereby showing that fermion routing in any such encoding can be done efficiently. While these results assume all-to-all connectivity, they also imply upper bounds for fermion routing in devices with limited connectivity by multiplying the fermion routing depth by the worst-case qubit routing depth.

Abstract: Device-independent (DI) cryptography represents the highest level of security, enabling cryp- tographic primitives to be executed safely on uncharacterized devices. Moreover, with successful proof-of-concept demonstrations in randomness expansion, randomness amplification, and quantum key distribution, the field is steadily advancing toward commercial viability. Critical to this continued progression is the development of tighter finite-size security proofs. In this work, we provide a simple method to obtain tighter finite-size security proofs for protocols based on the CHSH game, which is the nonlocality test used in all of the proof-of-concept experiments. We achieve this by analytically solving key-rate optimization problems based on Rényi entropies, providing a simple method to obtain tighter finite-size key rates.

Abstract: Scaling up the number of qubits available on quantum processors remains technically demanding; it is therefore crucial to clarify the number of qubits required to execute a quantum computation. When circuit compilation techniques such as mid-circuit measurements and delayed input preparation are permitted, the qubit requirement of a given quantum computation can be smaller than that implied by its naive description. However, no general method has been known for characterizing how much such reductions can be achieved. In this work, we characterize lower and upper bounds on the number of qubits required to implement a given quantum computation in terms of the causal structure of the corresponding quantum instrument. We further show that these lower and upper bounds coincide for quantum computations used in entanglement distillation protocols, and thereby obtain optimal space requirements for several well-known entanglement distillation protocols.

Abstract: We investigate the generation of EPR pairs between three observers in a general causally structured setting, where communication occurs via a noisy quantum broadcast channel. The most general quantum codes for this setup take the form of tripartite quantum channels. Since the receivers are constrained by causal ordering, additional temporal relationships naturally emerge between the parties. These causal constraints enforce intrinsic no-signalling conditions on any tripartite operation, ensuring that it constitutes a physically realizable quantum code for a quantum broadcast channel. We analyze these constraints and, more broadly, characterize the most general quantum codes for communication over such channels. We examine the capabilities of codes that are fully no-signalling among the three parties, positive partial transpose (PPT)-preserving, or both, and derive simple semidefinite programs to compute the achievable entanglement fidelity. We then establish a hierarchy of semidefinite programming converse bounds—both weak and strong—for the capacity of quantum broadcast channels for EPR pair generation, in both one-shot and asymptotic regimes. Notably, in the special case of a point-to-point channel, our strong converse bound recovers and strengthens existing results. Finally, we demonstrate how the PPT-preserving codes we develop can be leveraged to construct PPT-preserving entanglement combing schemes, and vice versa.

Abstract: Approximating the dynamics given by a complex many-body Hamiltonian with a simpler effective model lies at the interface of quantum Hamiltonian learning and quantum simulation. In this con- text, quantum generative adversarial networks (QGANs) have been shown to outperform standard Trotter-based approximations. However, their performance is often hindered by training plateaus and local minima that become increasingly severe with system size. To overcome these limitations, we propose an entanglement-assisted learning strategy that couples a single randomly initialized auxiliary qubit to the learning system at an intermediate stage of the training process. The inter- play between randomization and entanglement significantly enhances the learning performance of the protocol.

Abstract: Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} in general but of great practical importance, and it is valuable to identify algorithmic speedups to expand the domain of problems that can be solved in practice. It has proven challenging to identify super-quadratic quantum speedups for ILPs. A primary difficulty is that most classical algorithms that handle ILPs with many constraints are global and exhaustive, whereas quantum frameworks that offer the potential for super-quadratic speedups leverage the local properties of the objective function and feasible set. We address this difficulty by considering quantum algorithms for Gomory's group relaxation, a relaxation of an ILP that is obtained by removing the nonnegativity constraints from variables that are positive in the optimal solution of the linear programming relaxation, while keeping integrality of the decision variables. We present a classical algorithm that is competitive with known alternatives that solves the group relaxation via a local search, and a corresponding quantum algorithm that under reasonable technical conditions offers a super-quadratic speedup. When the group relaxation satisfies a non-degeneracy condition analogous to (albeit stronger than) that found in linear programming, our approach yields an optimal solution to the original integer program. In other cases, the group relaxation can improve downstream branch-and-cut solvers by reducing the integrality gap, a behavior that we numerically show to be typical for some practically interesting ILPs.

Abstract: We extend the findings of (Quantum \textbf{9}, 1887 (2025)), which demonstrated that the discrete adiabatic quantum linear system solver exhibits constant factors approximately 1,200 times smaller in practice than previously estimated by worst-case bounds and about an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352]. In the present work, we introduce a comparison between the adiabatic-based quantum walk method and the more recent ``shortcut'' quantum linear system solver proposed in [arXiv:2406.12086], which also achieves the asymptotically optimal scaling $O(\kappa\log(1/\varepsilon))$, but with a better constant factor guarantee than the quantum walk method, especially when the solution norm is known. Specifically, we conduct a comprehensive numerical analysis contrasting the two methods in two regimes: when the norm of the solution is unknown and when it is known. Our results indicate that in cases where we know \emph{a priori} $\|x\|$, the shortcut method achieves a lower total cost than QW, providing a potential practical application for problems where the norm of the solution is available.

Abstract: Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead. Recent advances have shown that by jointly decoding logical qubits in algorithms composed of transversal gates, the number of syndrome extraction rounds can be reduced by a factor of the code distance d, at the cost of increased classical decoding complexity. Here, we reformulate the problem of decoding transversal circuits by directly decoding relevant logical operator products as they propagate through the circuit. This procedure transforms the decoding task into one closely resembling that of a single-qubit memory propagating through time. The resulting approach leads to fast decoding and reduced problem size while maintaining high performance. Focusing on the surface code, we prove that this method enables fault-tolerant decoding with minimum-weight perfect matching, and benchmark its performance on example circuits including magic state distillation. We find that the threshold is comparable to that of a single-qubit memory, and that the total decoding run time can be, in fact, less than that of conventional lattice surgery. Our approach enables fast correlated decoding, providing a pathway to directly extend single-qubit QEC techniques to transversal algorithms.

Abstract: Achieving quantum advantage in efficiently estimating collective properties of quantum many-body systems remains a fundamental goal in quantum computing. While the quantum gradient estimation (QGE) algorithm has been shown to achieve doubly quantum enhancement in the precision and the number of observables, it remains unclear whether one benefits in practical applications. In this work, we present a generalized framework of the adaptive QGE algorithm, and further propose two variants which enable us to estimate the collective properties of fermionic systems using the smallest cost among existing quantum algorithms. The first method utilizes the symmetry inherent in the target state, and the second method enables estimation in a single-shot manner using the parallel scheme. We show that our proposal offers a quadratic speedup compared with prior QGE algorithms in the task of fermionic partial tomography for systems with limited particle numbers. Furthermore, we provide numerical demonstrations that, for a problem of estimating fermionic 2-RDMs, our proposals improve the number of queries to the target state preparation oracle by a factor of 4.4 for the nitrogenase FeMo cofactor and by a factor of 7.8 for Fermi-Hubbard model of 200 sites in chemical accuracy.

Abstract: We present a symmetry-enabled direct quantum algorithm for computing many-body Green’s functions, a central tool for studying strongly correlated quantum systems. Our protocol relies only on native time evolution and straightforward measurements available on current hardware platforms. By exploiting parity symmetry—satisfied by a broad class of Hamiltonians in condensed matter physics and quantum chemistry, including the Fermi–Hubbard and Heisenberg models—we introduce a tailored quench spectroscopy scheme that recovers both the real and imaginary parts of two-point time correlators, from which Green’s functions can be reconstructed via efficient classical signal analysis. We further develop a tailored quantum Gibbs sampler that prepares parity-resolved (symmetric and antisymmetric) thermal states, enabling finite-temperature applications within the same framework. Finally, we show that the same symmetry-based measurement primitive extends naturally to out-of-time-ordered correlators (OTOCs), providing a practical path toward probing finite-temperature dynamics of strongly correlated quantum systems on near-term and early fault-tolerant quantum hardware.

Abstract: Random thermal states of many-body Hamiltonians underpin studies of thermalization, chaos, and quantum phase transitions, yet their generation remains costly when each Hamiltonian must be prepared individually. We introduce the thermal-drift channel, a measurement-based operation that implements a tunable nonunitary drift along a chosen Pauli term. Based on this channel, we present a measurement-controlled sampling algorithm that generates thermal states together with their Hamiltonian ``labels'' for general physical models. We prove that the total gate count of our algorithm scales cubically with system size, quadratically with inverse temperature, and as the inverse error tolerance to the two-thirds power, with logarithmic dependence on the allowed failure probability. We also show that the induced label distribution approaches a normal distribution reweighted by the thermal partition function, which makes an explicit trade-off between accuracy and effective range. Numerical simulations for a 2D Heisenberg model validate the predicted scaling and distribution. As an application, we compute unfolding-free level-spacing ratio statistics from sampled thermal states of a 2D transverse-field Ising model and observe a crossover toward the Wigner-Dyson prediction, demonstrating a practical and scalable route to chaos diagnostics and random matrix universality studies on near-term quantum hardware.

Abstract: Quantum chaos is commonly assessed through probe-dependent signatures such as spectral statistics, OTOCs, and entanglement growth, which need not coincide. Recently, a dissipative diagnostic of chaos has been proposed, in which an infinitesimal coupling to a bath yields a finite Liouvillian gap in chaotic systems, marking the onset of intrinsic relaxation. This raises a conceptual question: what is the minimal departure from Clifford dynamics needed for this intrinsically relaxing behavior to emerge? In this work, we investigate the dynamics under the Floquet two-qubit Clifford circuit interleaved with a finite density of Haar-random single-site gates, followed by a depolarizing channel with strength γ. For Floquet Clifford circuits built from an iSWAP-class two-qubit gate, our analysis identifies two distinct regimes for the Liouvillian gap in the thermodynamic limit, exemplified by the undoped and fully doped extreme cases. In both regimes, the dissipative diagnostic signals chaotic behavior, differing only in how the gap scales with system size. In the undoped circuit, the gap scales as Δ ∼ γN, whereas in the fully doped circuit it remains finite as N → ∞. We find that the doping density p_h governs the crossover: as p_h → 0, any spatial structure remains undoped-like, whereas for finite p_h certain structures can enter a finite-gap regime. These results are analytically established in the strongly dissipative regime γ ≫ 1 by deriving lower bounds on the gap as a function of p_h and explicit finite-gap constructions, and their extension toward γ → 0 is supported by numerics. Importantly, our analytic treatment depends only on the spatial doping structure, so the same gap scaling persists even when the Haar rotations are independently resampled each Floquet period.

Abstract: Say a collection of $n$-qu$d$it gates $\Gamma$ is \emph{eventually universal} if and only if there exists $N_0 \geq n$ such that for all $N \geq N_0$, one can approximate any $N$-qu$d$it unitary to arbitrary precision by a circuit over $\Gamma$. In this work, we improve the best known upper bound on the smallest $N_0$ with the above property. Our new bound is roughly $d^4n$, where $d$ is the local dimension (the `$d$' in qu$d$it), whereas the previous bound was roughly $d^8n$. For qubits ($d = 2$), our result implies that if an $n$-qubit gate set is eventually universal, then it will exhibit universality when acting on a $16n$ qubit system, as opposed to the previous bound of a $256n$ qubit system. In other words, if adding just $15n$ ancillary qubits to a quantum system (as opposed to the previous bound of $255 n$ ancillary qubits) does not boost a gate set to universality, then no number of ancillary qubits ever will. Our proof relies on the invariants of finite linear groups as well as a classification result for all finite groups that are unitary $2$-designs.

Abstract: We present quantum algorithms for simulating the dynamics of a broad class of classical oscillator systems containing 2^n coupled oscillators (Eg: 2^n masses coupled by springs), including those with time-dependent forces, time- varying stiffness matrices, and weak nonlinear interactions. This generaliza- tion of the Harmonic oscillator simulation algorithm is achieved through an approach that we call “Nonlinear Schrödingerization”, which involves reduction of the dynamical system to a nonlinear Schrödinger equation and then reduced to a time-independent Schrodinger Equation through perturbative techniques. The linearization of the equation is performed using an approach that allows the dynamics of a nonlinear Schrödinger equation to be approximated as a linear Schrödinger equation in a higher dimensional space. This allows Hamiltonian Simulation algorithms to be applied to simulate the dynamics of resulting sys- tem. When the properties of the classical dynamical systems can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in n, and almost linear in evolution time for most dynamical systems. Our work extends the applicability of quan- tum algorithms to simulate the dynamics of non-conservative and nonlinear classical systems, addressing key limitations in previous approaches

Abstract: Commuting Hamiltonians lie at the boundary between classical constraint satisfaction and quantum many-body physics, exhibiting rich quantum structure while remaining more tractable than general noncommuting models. In contrast, physical Hamiltonians are rarely exactly commuting, which naturally motivates the study of \emph{almost commuting} Hamiltonians. Despite their relevance, the implications of approximate commutation are only poorly understood. In this work, we show how to efficiently approximate any almost commuting $2$-local qubit Hamiltonian by a commuting one: we give a locality-preserving ``rounding technique'' that maps any $2$-local Hamiltonian $H=\sum_{i=1}^m h_i$ with $\|[h_i,h_j]\| \leq \eps$ to a nearby Hamiltonian $\hat{H}$ whose terms pair-wise commute, and which is within overall distance $\|H-\hat{H}\| = O(m\,\eps^{1/3})$. As a consequence, we show that $\delta$-approximations to the ground energy for $\eps$-almost commuting $2$-local qubit Hamiltonians lie in $\mathsf{NP}$ when $\delta \gg m\eps^{1/3}$, extending the classical containment well beyond the commuting setting. Finally, we present two applications of our rounding framework: Gibbs sampling and fast Hamiltonian simulation for almost commuting systems.

Abstract: The notions of privacy tests and k-extendible states have both been instrumental in quantum information theory, particularly in understanding the limits of secure communication. In this paper, we determine the maximum probability with which an arbitrary k-extendible state can pass a privacy test, and we prove that it is equal to the maximum fidelity between an arbitrary k-extendible state and the standard maximally entangled state. Our findings, coupled with the resource theory of k-unextendibility, lead to an efficiently computable upper bound on the one-shot, one-way distillable key of a bipartite state, and we prove that it is equal to the best-known efficiently computable upper bound on the one-shot, one-way distillable entanglement. We also establish efficiently computable upper bounds on the one-shot, forward-assisted private capacity of channels. Extending our formalism to the independent and identically distributed setting, we obtain single-letter efficiently computable bounds on the n-shot, one-way distillable key of a state and the n-shot, forward-assisted private capacity of a channel. For some key examples of interest, our bounds are significantly tighter than other known efficiently computable bounds.

Abstract: We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the approximate Maximum Cut, or gap $\mathrm{Max}$-$\mathrm{Cut}$, problem) to $\gamma\text{-}\mathrm{CVP}_p$ for $\gamma = \mathrm{O}(1)$ and finite $p \geq 1$, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from $k$-$\mathrm{SAT}$ to $\mathrm{CVP}_2$. This implies three headline results: (i) Faster algorithms for $\gamma\text{-}\mathrm{CVP}_p$ are also faster algorithms for Max-2-Lin(2) and Max-Cut. Depending on the approximation regime, even a $2^{0.78n}$-time or $2^{0.3n}$-time algorithm would improve upon the state-of-the-art algorithm such as Williams' 2004 algorithm [\textit{Theoretical Computer Science} 2005] or Arora, Barak, and Steurer's 2010 algorithm [$\textit{Journal of the ACM}$ 2015]. This provides evidence that $\gamma\text{-}\mathrm{CVP}_p$ for $\gamma = o(\sqrt{\log n}^\frac{1}{p})$ requires $2^{\delta n}$-time for some specific constant $\delta > 0$, improving upon the previous exponential lower-bound for $\gamma\text{-}\mathrm{CVP}_2$ with $\gamma < 3$ by Bennett, Golovnev, and Stephens-Davidowitz [$\textit{FOCS}$ 2017]. (ii) A new almost $2^{(1/2 + \varepsilon/4\varsigma + o(1)) n}$-time classical algorithm and a new almost $2^{(1/3 + \varepsilon/6\varsigma + o(1)) n}$-time quantum algorithm for $(1-\varepsilon, 1-\varsigma)$-gap Max-Cut. This algorithm is faster than the algorithm of Arora, Barak and Steuer [$\textit{Journal of the ACM}$ 2015], as well as the algorithm of Williams [$\textit{Theoretical Computer Science}$ 2004], % and others and the algorithm of Manurangsi and Trevisan [\textit{APPROX/RANDOM} 2018] when $c_0 \varepsilon < \varsigma < c_1 \varepsilon$ for some constants $c_0, c_1$. (iii) If the Quantum Strong Exponential Time Hypothesis (QSETH) can be used to show a $2^{\delta n}$-time lower-bound for $\mathrm{Max}$-$\mathrm{Cut}$, Max-2-Lin(2), or $\mathrm{CVP}_2$ for any constant $\delta > 0$, it must be via an adaptive quantum reduction unless $\mathrm{NP} \subseteq \mathrm{pr}\text{-}\mathrm{QSZK}$. This illuminates some difficulties in characterizing the hardness of approximate constraint satisfaction problems and shows that the post-quantum security of lattice-based cryptography likely cannot be supported by QSETH. This result builds off of and strengthens the no-go results of Aggarwal and Kumar [$\textit{FOCS}$ 2023], who showed that the classical security of lattice-based cryptography likely cannot be supported by the classical Strong Exponential Time Hypothesis (SETH).

Abstract: We study a counterintuitive property of ‘conditioning’ on the result of measuring a subsystem of a quantum state: such conditioning can boost design quality, at the cost of increased system size. We work in the setting of deep thermalization from many-body physics: starting from a bipartite state on a global system (A,B) drawn from a k-design, we measure subsystem B in the computational basis, keep the outcome and examine the state that remains in subsystem A, approximating the overall ensemble (the ‘projected ensemble') by a k’-design. We ask: how does the design quality change due to this procedure, or how does k’ compare to k? We give the first rigorous example of unitary dynamics generating a state such that, projection at very early (constant) times can boost design randomness. These dynamics are those of quantum chaos, modeled by the evolution of a Hamiltonian drawn from the Gaussian Unitary Ensemble (GUE). We show that, even though a state generated by such dynamics at constant time only forms a k=O(1) design, the projected ensemble is Haar-random (or a k' = infinity design) in the thermodynamic limit (i.e. when the size of subsystem B is infinite). This phenomenon persists even with weaker and more physically realistic assumptions; our results can be appropriately applied to non-GUE Hamiltonians that nevertheless show likely chaotic signatures in their eigenbases. Finally, we show that if the global state is a k-design, with no assumption on how it was generated, the projected ensemble on subsystem A is a k/2 design. This improves upon best prior results on the deep thermalization of designs. Together, our contributions argue for design boosting as a result of chaos and showcase a novel mechanism to generate good designs.

Abstract: The Generalized Quantum Stein's Lemma is a theorem in quantum hypothesis testing that provides an operational meaning to the relative entropy within the context of quantum resource theories. Its original proof was found to have a gap, which led to a search for a corrected proof. We formalize the proof presented in [Hayashi and Yamasaki (2024)] in the Lean interactive theorem prover. This is the most technically demanding theorem in physics with a computer-verified proof to date, building with a variety of intermediate results from topology, analysis, and operator algebra. In the process, we rectified minor imprecisions in [HY24]'s proof that formalization forces us to confront, and refine a more precise definition of quantum resource theory. Formalizing this theorem has ensured that our Lean-QuantumInfo library, which otherwise has begun to encompass a variety of topics from quantum information, includes a robust foundation suitable for a larger collaborative program of formalizing quantum theory more broadly.

Abstract: The motivating question for this work is how to efficiently estimate the expected value of an observable when the system undergoes a small and time-dependent perturbation. When the underlying system is a Markovian open quantum system, well-established quantum regression theorem (QRT) and linear response theory (LRT) are powerful tools for this task; however, QRT and LRT failed to work beyond the Markovian regime. In this paper, we first develop a novel formulation of linear response functions for open quantum systems that extends the standard QRT beyond the Markov limit. In addition, we present efficient quantum algorithms for estimating such response functions whose cost scales poly-logarithmically in the system dimension and $1/\epsilon^{1+o(1)}$ in the target accuracy $\epsilon$. The framework removes the separability (Born-Markov) assumption and offers a pathway to efficient computation of nonequilibrium properties from open quantum systems.

Abstract: Quantum error mitigation is essential for extracting trustworthy results from noisy intermediate-scale quantum (NISQ) processors. Yet, current approaches face a core scalability bottleneck: unbiased methods such as probabilistic error cancellation (PEC) incur exponential sampling overhead, while approximate techniques like zero-noise extrapolation trade accuracy for efficiency. We introduce and experimentally demonstrate MOSAIC (Modular Spatio-temporal Aggregation for Inverted Channels), a scalable quantum error mitigation framework that preserves the unbiasedness of PEC while dramatically reducing sampling costs. MOSAIC partitions a circuit into noise-aligned blocks, learns an effective block noise model using classical variational optimization, and applies quasi-probabilistic inversion once per block instead of after every layer. This blockwise aggregation reduces both sampling overhead and circuit-depth overhead, enabling mitigation far beyond the operating regime of standard PEC. MOSAIC is experimentally validated on IBM’s 156-qubit Heron processors, performing the largest PEC-based mitigation demonstration on hardware to date. As a physically meaningful benchmark, we prepare the critical one-dimensional transverse-field Ising (TFIM) ground state for system sizes up to 50 qubits. We show that MOSAIC can achieve at least one to two orders of magnitude better accuracy than standard PEC under identical sampling budgets. This enables MOSAIC to recover accurate observables for larger system sizes, even when standard PEC fails due to its prohibitive sampling overhead. We also present CUDA-Q–accelerated simulations to validate performance trends under a range of different noise models. These results demonstrate that MOSAIC is not only theoretically scalable but also practically deployable for high-accuracy, large-scale quantum experiments on today’s quantum hardware.

Abstract: Quantum Machine Learning (QML) has become a promising area for real world applications of quantum computers, and near-term methods and their scalability are still important research topics. A consequent amount of efforts has been put into understanding how to avoid Barren Plateaus (BPs), a vanishing gradient phenomenon that prevents the variational algorithms from being trained efficiently. In particular, evidence has recently been shown that the structures that allow us to avoid BP seem to allow classical simulation techniques. In addition, other important questions must be tackled to design near-term quantum algorithms that may offer an advantage. How to ensure that the performance of the algorithms will scale with input size, and how to compare classical and quantum algorithms on different figures of merit for a same use case? Recent works have proposed to use subspace preserving quantum circuits to mimic classical neural network architectures. By restricting the Hilbert space to a subspace of polynomial size with respect to the number of qubits, such architectures are likely to avoid BPs. This comes at the cost of that is, a classical method can perform the same computation in polynomial time. In this work, we propose a paradigm shift: focusing on subspace-preserving methods that aim for a practical polynomial advantage. In particular, we propose to use linear optical circuits that are intrinsically subspace preserving as they conserve the number of particles during the computation. We believe that this approach could be sufficient to create useful QML applications as the generation of Fock states with few particles can be extremely high. In this talk, we will present two recent contributions from our team published in Physical Review Research. [1] and Advanced Photonics [2]. First, we will recall how linear optical circuit are limited in their expressivity due to the photonic homomorphism described by Aaronson and Arkhipov. We propose in [1] a new scheme for near-term photonic quantum devices that allows to increase the expressive power of the quantum models beyond what linear optics can do. This scheme relies upon State Injection (SI), a measurement-based technique that can produce states that are more controllable, and solve learning tasks that are believed to be intractable classically. Then we will show how using [2] how we propose to adapt a subspace preserving Quantum Convolutional Neural Network (QCNN) architecture for linear optic setting with SI adaptivity. We realize a proof-of-concept experiment by employing a cutting-edge single-photon source based on a semiconductor Quantum Dot (QD) , a time-to-spatial demultiplexer, and universal programmable 12-mode and 8-mode interferometers realized with the femtosecond laser-writing technique. The designed PQCNN scheme is tailored to the experimental platform at hand, with the goal of carrying out a binary image classification. As a complement to the experimental investigation, we provide a systematic study on the scaling and complexity of the protocol, by leveraging numerical simulations on larger quantum systems, demonstrating the potential behind the proposed scheme for PQCNNs.

Abstract: We introduce a Convolutional and a measurement based Pooling layer that offer polynomial advantages over their classical analogs. By conserving the subspace preserving structure of the state during the computation, these layers can be assembled to perform complex deep-learning algorithms such as Convolutional Neural Network architectures, while assuring the correct training of the quantum circuit. In particular, those circuits can avoid Barren Plateau by only considering subspaces of polynomial size, limiting the potential running time advantages to polynomial ones. Recent work has pointed out the link between the absence of Barren Plateau and a non-exponential advantage in the near-term QML literature, and we believe that our proposal offers a promising path for useful QML algorithms by optimizing the framework that avoids vanishing gradient phenomena. Our works also deal with an important question that only a few works address due to hardware limitations: how to ensure that a method's performance will scale with the size of the problems? By offering software tools that are tailored for Hamming-Weight preserving algorithms, and by mimicking the behavior of state-of-the-art classical deep-learning layers, we offer a solution that performs well in comparison with classical methods while offering an interesting running time advantage. Our software, that can be accessed through, allowed us to train our model on 10-label classification tasks that are far more complex than usual binary classification tasks used to illustrate QML methods and are commonly used in the classical Machine Learning literature.

Abstract: Quantum Machine Learning Algorithms based on Variational Quantum Circuits (VQCs) are important candidates for useful application of quantum computing. It is known that VQCs are linear models in some feature space of finite dimension. At first sight, if this feature map can be explicitly computed classically, one may wonder what is the interest of searching the best parameters of the quantum circuit instead of performing classically a linear regression on the same feature map, using a so called classical surrogate model schreiber2023classical. Even when the feature space is too large to be computed classically, methods exist to reduce its dimension by random sampling, realizing approximated classical models. At the same time, quantum advantages for learning tasks have been proven in the case of discrete data distributions and cryptography primitives. In this work, we present necessary conditions for a quantum model to avoid such dequantization, and we highlight that this could be only satisfied for high dimensional feature maps. Our study can be applied to any quantum circuits with continuous or discrete inputs, and propose conditions that guarantee a quantum model to remain far from its equivalent classical model. We show that this theory is compatible with previously proven quantum advantages on discrete inputs, and provides examples of advantages for continuous inputs. This separation is connected to large weight vector norm, and we suggest that this can only happen with a high dimensional feature map. Our results demonstrate that it is possible to design quantum models that cannot be classically approximated with good generalization. Finally, we discuss how concentration issues must be considered to design such instances. We expect that our work will be a starting point to design near-term quantum models that avoid dequantization methods by ensuring non-classical convergence properties, and to identify existing quantum models that can be classically approximated.

Abstract: Numerically solving partial differential equations is a ubiquitous computational task with broad applications in many fields of science. Quantum computers can potentially provide high-degree polynomial speed-ups for solving PDEs, however many algorithms simply end with preparing the quantum state encoding the solution in its amplitudes. Trying to access explicit properties of the solution naively with quantum amplitude estimation can subsequently diminish the potential speed-up. In this work, we present a technique for extracting a smooth positive function encoded in the amplitudes of a quantum state, which achieves the Heisenberg limit scaling. We improve upon previous methods by allowing higher dimensional functions, by significantly reducing the quantum complexity with respect to the number of qubits encoding the function, and by removing the dependency on the minimum of the function using preconditioning. Our technique works by sampling the cumulative distribution of the given function, fitting it with Chebyshev polynomials, and subsequently extracting a representation of the whole encoded function. Finally, we trial our method by carrying out small scale numerical simulations.

Abstract: We offer the first operational interpretation of the α-z relative entropies, a measure of distinguishability between two quantum states introduced by Jakšić et al. and Audenaert and Datta. We show that these relative entropies appear when formulating conditions for large-sample or catalytic relative majorization of pairs of flat states and certain generalizations of them. Indeed, we show that such transformations exist if and only if all the α-z relative entropies of the two pairs are ordered. In this setting, the α and z parameters are truly independent from each other. These results also yield an expression for the optimal rate of converting one flat state pair into another. Our methods use real-algebraic techniques involving preordered semirings and certain monotone homomorphisms and derivations on them.

Abstract: Parametrised quantum circuits are a leading model for near-term quantum machine learning, yet it remains difficult to predict—without training on data—how a circuit’s design shapes what it can learn and how trainable it will be. We introduce a data-agnostic representation that maps a broad family of circuits into a single architecture matrix built from a joint harmonic expansion over inputs and parameters. This matrix provides an explicit, interpretable link between circuit structure, the correlations among learnable features, and the geometry of training kernels. We show how correlations between learnable features arise from shared parameter-induced harmonics generated by non-commuting gate–observable interactions during Heisenberg back-propagation, and how these correlations are encoded directly in the architecture matrix. From this perspective, kernel structure and coefficient statistics can be reconstructed analytically from circuit design alone, without reference to a dataset or optimisation trajectory. The resulting framework makes circuit-induced structure explicit, separating architectural effects from data-dependent ones, and provides a principled foundation for analysing and comparing parametrised quantum circuits based on intrinsic, design-level signatures.

Abstract: Transformations of quantum channels, such as the transpose, complex conjugate, and adjoint, are fundamental to quantum information theory. Given access to an unknown channel, a central problem is whether these transformations can be implemented physically with quantum supermaps. While such supermaps are known for unitary operations, the situation for general quantum channels is fundamentally different. In this work, we establish a strict hierarchy of physical realizability for the transposition, complex conjugation, and adjoint transformation of an unknown quantum channel. We present a probabilistic protocol that exactly implements the transpose with a single query. In contrast, we prove no-go theorems showing that neither the complex conjugate nor the adjoint can be implemented by any completely positive supermap, even probabilistically. We then overcome this impossibility by designing a virtual protocol for the complex conjugate based on quasi-probability decomposition, and show its optimality in terms of the diamond norm. As a key application, we propose a protocol to estimate the expectation values resulting from the Petz recovery map of an unknown channel, achieving an improved query complexity compared to existing methods.

Abstract: Quantum computers are believed to provide expo- nential speedups in solving certain classes of opti- mization problems, with the recently introduced Decoded Quantum Interferometry (DQI) frame- work (Jordan et al., 2025) providing a template for discovering novel applications of this form. Since many quantum speedups apply only to discrete problems with algebraic structure, it is of great in- terest to understand when speedups are possible in less structured settings that more closely resemble natural problems. We consider constraint satisfac- tion problems with continuous, unstructured con- straints that are inspired by problems in machine learning. We analyze the performance of a quan- tum algorithm based on DQI that leverages the sparse recovery guarantees of compressed sens- ing. We prove that this approach outperforms certain classical algorithms with provable guar- antees, and suggest regimes where it might also outperform classical heuristic algorithms like sim- ulated annealing. Our work presents a novel way in which the powerful toolkit of continuous sparse recovery algorithms can be used to design novel quantum algorithms.

Abstract: Communication using quantum channels generally requires encoding and decoding on many identical uses of a quantum channel. In practical settings, decoherence may severely limit our ability to do so, potentially rendering each channel use nonidentical. Given $n$ nonidentical channels, we present an entanglement-assisted encoding and decoding strategy that yields a channel with higher entanglement fidelity than all of the $n$ given channels. The strategy is universal, in the sense that the improvement holds regardless of what channels are given, as long as they satisfy mild assumptions on their initial entanglement fidelities. This idea can also be extended to classical channels, where shared randomness between the sender and the receiver allows universal enhancement of the probability of correct transmission. Finally, we prove that such universal improvement is always possible in affine resource theories, which we believe to be an interesting result in its own right.

Abstract: The Quantum Monte Carlo (QMC) method with operator-loop update is a powerful technique that has been extensively used in condensed matter physics. Despite its practical success, no rigorous proof of polynomial-time mixing had been known. In this work, we prove that the operator-loop QMC algorithm applied to all stoquastic (sign-problem free) XY models mixes in time polynomial in the system size and inverse temperature. Our work gives the first polynomial-time algorithm for computing the partition function of all stoquastic XY models. As a consequence, we obtain the first proof that the corresponding ground-state energy estimation problems lie in BPP. Finally, we discuss how operator-loop QMC is empirically known to mix rapidly for an even broader class of stoquastic Hamiltonians, and comment on the physical implications of our proof.

Abstract: Quantum algorithms offer an exponential advantage with respect to the number of dependent variables for solving certain nonlinear ordinary differential equations (ODEs). These algorithms typically begin by transforming the original nonlinear ODE into a higher-dimensional linear ODE using a linearization technique, most commonly Carleman linearization. Existing works restrict their analysis to ODEs where the nonlinearities are polynomial functions of the dependent variables, significantly limiting their applicability. In this work we construct an efficient quantum algorithm for solving ODEs with ‘Fourier’ nonlinear terms. To tackle the Fourier nonlinear term, which is not expressible as a finite sum of polynomials of u, our algorithm employs a generalization of the Carleman linearization technique known as Koopman linearization. We also make other methodological advances towards relaxing the stringent dissipativity condition required for efficient solution extraction and towards integrated readout of classical quantities from the solution state. Our results open avenues to the development of efficient quantum algorithms for a significantly wider class of high-dimensional nonlinear ODEs, thereby broadening the scope of their applications.

Abstract: We study quantum information transmission through noisy multi-time processes, modeled as quantum combs that capture temporal correlations across multiple time steps. We focus on communication tasks in which admissible recovery operations are used to simulate an identity channel in the presence of environmental action over multiple time steps. Within this framework, we define the capacity of a quantum comb as the maximal number of qubits that can be transmitted with a given error. We provideSDP-computable converse bounds on both the maximal rate and error exponent for arbitrary combs. In particular, we introduce multi-time non-signaling and positive partial transpose (PPT) codes and develop a multi-time analogue of the Rains bound. As an application, we analyze the simulation of a temporally correlated depolarizing channel. We also obtain multi-time analogues of hypothesis-testing quantities under restricted multi-time measurements and their associated entropic quantities, which we believe to be of independent interest.

Abstract: The ultimate limits of quantum state discrimination are often thought to be captured by asymptotic bounds that restrict the achievable error probabilities, notably the quantum Chernoff and Hoeffding bounds. Here we study hypothesis testing protocols that are permitted a probability of producing an inconclusive discrimination outcome, and investigate their performance when this probability is suitably constrained. We show that even by allowing an arbitrarily small probability of inconclusiveness, the limits imposed by the quantum Hoeffding and Chernoff bounds can be significantly exceeded. This completely circumvents the conventional trade-offs between error exponents in hypothesis testing while incurring only a vanishingly small overhead over conventional approaches. Such improvements over standard state discrimination are robust and can be obtained even when an exponentially vanishing probability of inconclusive outcomes is demanded. Relaxing the constraints on the inconclusive probability can enable even larger advantages, but this comes at a price. We show a 'strong converse' property of this setting: targeting error exponents beyond those achievable with vanishing inconclusiveness necessarily forces the probability of inconclusive outcomes to converge to one. By exactly quantifying the rate of this convergence, we give a complete characterisation of the trade-offs between error exponents and rates of conclusive outcome probabilities. Overall, our results provide a comprehensive asymptotic picture of how the allowance for inconclusive measurement outcomes reshapes optimal quantum hypothesis testing.

Abstract: With the continuous development of quantum computing, variational quantum autoencoders (VQA) have become an important model in quantum machine learning, widely applied for the compression and representation of quantum data. However, noise remains a significant challenge in practical quantum computing, especially when quantum circuits are run on simulators and real hardware, where noise can substantially affect the quality of quantum states. To address this issue,inspired by variational quantum autoencoders (VQA) and quantum noise suppression techniques, this paper proposes a novel quantum denoising filter architecture. In this architecture, we introduce auxiliary qubits on top of the variational quantum autoencoder to extend the encoding and decoding capabilities. Both the encoder and decoder are implemented using variational quantum circuits (VQC), which are trained to learn efficient representations of quantum data. To effectively mitigate the impact of noise on quantum information, we incorporate Zero Noise Extrapolation (ZNE) for denoising. This approach combines quantum autoencoding with noise mitigation strategies, providing a new solution for quantum information processing. Experimental results demonstrate that the quantum denoising filter is capable of recovering high-fidelity quantum states in various noisy environments, outperforming traditional noise filtering methods.The core innovation of this work lies in the proposal of a unified denoising mechanism that can simultaneously address both coherent and incoherent noise,enabling higher-quality quantum state recovery and improved model robustness.

Abstract: Quantum catalysis enables transformations of quantum states that are otherwise impossible. However, catalyzing transformations of quantum dynamics has remained largely unexplored. In this work, we initiate the study of correlated catalysis in dynamical resource theories and investigate whether resourceful quantum channel can be broadcast to another system. Specifically, we propose two frameworks for broadcasting dynamical resources: output broadcasting and input-output broadcasting. We establish no-go theorems that rule out output broadcasting of non-Gibbs-preserving channels. We also rule out input-output broadcasting of a variety of dynamical resources, including entanglement and coherence. Conversely, we construct general methods for output broadcasting applicable to a wide range of dynamical resource theories, including but not limited to entanglement, coherence, and non-stabilizerness.

Abstract: Lindbladian quantum master equations (LEs) are the most popular descriptions for quantum systems weakly coupled to baths. But, recent works have established that in many situations such Markovian descriptions are fundamentally limited: they cannot simultaneously capture populations and coherences even to the leading-order in system-bath couplings. This can cause violation of fundamental properties like thermalization and continuity equations associated with local conservation laws, even when such properties are expected in the actual setting. This begs the question: given a physical situation, how do we know if there exists an LE that describes it to a desired accuracy? Here we show that, for both equilibrium and non-equilibrium steady states (NESS), this question can be succinctly formulated as a semidefinite program (SDP), a convex optimization technique. If a solution to the SDP can be found to a desired accuracy, then an LE description is possible for the chosen setting. If not, no LE description is fundamentally attainable, showing that a consistent Markovian treatment is impossible even at weak system-bath coupling for that particular setting. Considering few qubit isotropic XXZ-type models coupled to multiple baths, we find that in most parameter regimes, LE description giving accurate populations and coherences to leading-order is unattainable, leading to rigorous no-go results. However, in some cases, LE description having correct populations but inaccurate coherences, and satisfying local conservation laws, is possible over some of the parameter regimes. Our work highlights the power of semidefinite programming in the analysis of physically consistent LEs, thereby, in understanding the limits of Markovian descriptions at weak system-bath couplings.

Abstract: We derive simple and unified closed-form expressions for projections with respect to fidelity (equivalently, Bures and purified distances) onto several sets of interest. These include projecting bipartite PSD matrices onto the set of PSD matrices with a fixed marginal, and projecting ensembles of PSD matrices onto the set of PSD decompositions of a given matrix, with important special cases given by projections onto the set of quantum channels (via the Choi isomorphism) and onto the set of POVMs. We introduce 'prior-channel decompositions' of completely positive (CP) maps, which uniquely decompose any CP map into a prior PSD matrix and a quantum channel. This decomposition generalizes the Choi--Jamiołkowski isomorphism by establishing a bijective correspondence between arbitrary bipartite PSD matrices and channel--state pairs, and we show that it arises naturally from the fidelity projections developed here. As applications, we show that the 'pretty good measurement' is the fidelity projection of an ensemble onto the set of POVMs, and that the Petz recovery map is the projection of a CP map—constructed from a prior state and a forward channel—onto the set of reverse quantum channels, which recasts the well-known identification of the Petz map with quantum Bayes’ rule in information-geometric terms. Our results also provide an information-geometric underpinning of the Leifer--Spekkens quantum state over time [Leifer and Spekkens, Phys. Rev. A 88, 052130 (2013)].

Abstract: The complexity of matrix multiplication is a central topic in computer science. While the focus has traditionally been on exact algorithms, a long line of literature also considers randomized algorithms, which return an approximate solution in faster time. In this work, we adopt a unifying perspective that frames these randomized algorithms in terms of mean estimation. Using it, we first give refined analyses of classical algorithms based on random walks by Cohen-Lewis (`99), and based on sketching by Sarlós (`06) and Drineas-Kannan-Mahoney (`06). We then propose an improvement on Cohen-Lewis that yields a single classical algorithm that is faster than all the other approaches, if we assume no use of (exact) fast matrix multiplication as a subroutine. Second, we demonstrate a quantum speedup on top of these algorithms by using the recent quantum multivariate mean estimation algorithm by Cornelissen-Hamoudi-Jerbi (`22).

Abstract: Fault-tolerant quantum computation (FTQC) requires compiling logical quantum circuits encoded using a quantum error-correcting code into physical operations tailored to specific hardware architectures. Lattice surgery has emerged as a leading method to perform logical computation, initially motivated by superconducting qubit architectures with geometrically local connectivity. However, current lattice surgery techniques are limited due to certain paradigmatic assumptions that are widely regarded as standard. In our works we identify and address two of these limiting paradigms. First, prior work has predominantly focused on the surface code, even though other topological codes offer certain advantages. Second, compilation schemes usually follow a place-and-route paradigm where logical qubits remain fixed in space throughout the computation. We initiate a more flexible line of work that goes beyond both aforementioned paradigms. To address the first, we introduce the concept of a code substrate - a blueprint for realizing quantum error correction with topological quantum codes using lattice surgery. We formulate the problem using two layers of abstraction. The microscopic level specifies how lattice surgery operations are realized using distance-preserving ancilla regions, while the macroscopic level abstracts compilation as a “mapping” and “routing” problem on a coarse-grained routing graph. We exemplify this framework with detailed constructions for the color code and folded surface code. To challenge the second paradigm, we exploit movable logical qubits through teleportation during logical CNOT execution. Building on the color code substrate, we adapt the measurement-based CNOT scheme to incorporate logical qubit teleportations without additional time overhead. This enables data qubits to dynamically change positions during compilation – “mapping” and “routing” are thus not viewed as independent and subsequent steps, as previous methods have in an overly simplified manner. This flexibility has the potential to substantially reduce routed circuit depth. Thus, movable logical qubits can be exploited even when physical qubits remain static, making movement-based compilation applicable not only to trapped ion and neutral atom platforms - where physical qubits are dynamic by design - but also to superconducting architectures. In addition to the conceptual work, we provide a set of open-source tools for the compilation of logical circuits for the color code on GitHub https://github.com/munich-quantum-toolkit/qecc.

Abstract: Quantum memory is a scarce and costly resource, yet little is known about which learning tasks remain feasible under severe memory constraints. We study the problem of computing global properties of quantum sequences when quantum systems must be measured individually, without storing or jointly processing them. In our setting, a bit string \(x \in \{0,1\}^n\) is encoded into an \(n\)-qubit product state \(\ket{\psi_{x_1}} \otimes \cdots \otimes \ket{\psi_{x_n}}\), and the goal is to infer \(f(x) \in \{0,1\}\) from measurements of this quantum encoding. We consider a simple local strategy, which we call the \emph{greedy strategy}, that applies the same optimal single-system measurement independently to each subsystem and then infers \(f(x)\) from the results. Our main result gives a complete characterization of when the greedy strategy is optimal: it achieves the same maximum success probability as an unrestricted global measurement if and only if the target Boolean function is affine (in all but finitely many cases). For general Boolean functions, we establish a universal performance guarantee, showing that the success probability of the greedy strategy is always at least the square of the optimal global success probability, in direct analogy with the Barnum--Knill bound for the pretty good measurement. These results demonstrate that even under extreme memory constraints, simple local measurement strategies can remain provably competitive for learning global properties of quantum sequences.

Abstract: We propose a general framework for analysing the performance of quantum algorithms that consist of performing discrete operations controlled by a Poisson process. This extends our previous work [1]. In particular, we are interested in emulating certain features of adiabatic quantum computation without having to simulate time-dependent Hamiltonian evolution, since this typically causes a significant discretisation cost. We can also Poissonise the discretisation processes themselves. In this way we are able to show that discretisation in the context of adiabatic quantum computing is less costly than the general bounds on the Trotterisation error would imply. In this way we are able to reproduce key results from [2]. The resulting error bounds share many key features with the error bounds in adiabatic quantum computation. And many results are directly applicable. As applications, we show how our framework yields six distinct approaches to both the Grover search problem and the quantum linear systems problem that almost all achieve optimal asymptotic complexity.

Abstract: Estimating nonlinear properties of quantum states, particularly observable-weighted moments $\mathrm{Tr}(\mathcal{O}\rho^k)$, is a central task in quantum information science. In this work, we present a unified framework establishing the optimal sample complexity for this task and a resource-efficient protocol for its implementation. Theoretically, we prove that $\tilde{\Theta}(k)$ samples of an $m$-qubit state $\rho$ are sufficient and necessary to \textit{simultaneously} estimate the full hierarchy of moments $\mathrm{Tr}(\mathcal{O}\rho), \dots, \mathrm{Tr}(\mathcal{O}\rho^k)$. This reveals that estimating the entire hierarchy is asymptotically as efficient as estimating the single highest-order term. To realize this, we introduce a circuit architecture leveraging qubit reuse that requires only $2m+1$ physical qubits and $\mathcal{O}(k)$ depth. This approach achieves the near-optimal sample complexity of $\mathcal{O}(k \log k / \varepsilon^2)$ with significantly reduced hardware overhead. We demonstrate the framework's utility by bounding maximum eigenvalues, performing virtual cooling on the Heisenberg model, and experimentally measuring higher-order Rényi entropies on a superconducting processor.

Abstract: We study PRODSAT-QSAT(k): given rank-one k-local projectors, determine whether a quantum k-SAT instance admits a satisfying product state. We present a CDCL-style refutation framework that searches a finite partition of each qubit’s Bloch sphere while a sound theory solver checks region feasibility using a geometric over-approximation of constraint amplitudes. When the checker proves that no state in a region can satisfy a constraint, it produces a sound conflict clause that blocks that region; accumulated learned clauses can yield a global result of product-state unsatisfiability (UN-PRODSAT). We formalise the problem, prove the soundness of the clause-learning rule, and describe a practical algorithm and implementation.

Abstract: We study the following task: Alice is given a classical description of a rank-k projector P on C^d, and Alice and Bob want to prepare the state P/k on Bob's side using shared entanglement and classical communication. The general form of this task is known as remote state preparation (RSP). We give nearly-matching lower and upper bounds for the entanglement cost and communication cost for RSP of the states P/k. Ours are the first nearly matching upper and lower bounds for RSP of mixed states, and in the special case of pure states, our lower bound outperforms the best previously known lower bound. Our results show that any pure entangled state that can be used to do RSP of these states with o(d) bits of communication, can distill log d ebits of entanglement, and conversely, any state that can distill log d ebits of entanglement can be used to do RSP of these states efficiently. As an application of our results, we give a new entanglement-assisted communication protocol for the equality function that uses 1/2 log n + O(1) many ebits, and O(1) communication.

Abstract: Quadratic Unconstrained Binary Optimization (QUBO) problems are prevalent in various applications and are known to be NP-hard. The seminal work of Goemans and Williamson introduced a semidefinite programming (SDP) relaxation for such problems, solvable in polynomial time that upper bounds the optimal value. Their approach also enables randomized rounding techniques to obtain feasible solutions with provable performance guarantees. In this work, we identify instances of QUBO problems where matrix multiplicative weight methods lead to quantum and quantum-inspired algorithms that approximate the Goemans-Williamson SDP exponentially faster than existing methods, achieving polylogarithmic time complexity relative to the problem dimension. This speedup is attainable under the assumption that the QUBO cost matrix is sparse when expressed as a linear combination of Pauli strings satisfying certain algebraic constraints, and leverages efficient quantum and classical simulation results for quantum Gibbs states. We demonstrate how to verify these conditions efficiently given the decomposition. Additionally, we explore heuristic methods for randomized rounding procedures and extract the energy of a feasible point of the QUBO in polylogarithmic time. While the practical relevance of instances where our methods excel remains to be fully established, we propose heuristic algorithms with broader applicability and identify Kronecker graphs as a promising class for applying our techniques. We conduct numerical experiments to benchmark our methods. Notably, by utilizing tensor network methods, we solve an SDP with $D = 2^{50}$ variables and extract a feasible point which is certifiably within $0.15\%$ of the optimum of the QUBO through our approach on a desktop, reaching dimensions millions of times larger than those handled by existing SDP or QUBO solvers, whether heuristic or rigorous.

Abstract: Distributed quantum computing offers a promising approach to scaling quantum devices by networking multiple quantum processors. We present a quantum state tomography protocol tailored for distributed quantum computers that avoids assuming remote entanglement as a primitive resource. The protocol extends projected least-squares (PLS) tomography based on projective 2-designs to systems composed of multiple quantum processors, using only local operations within each processor and classical communication between nodes. Assuming that each individual quantum processor operates as an early fault-tolerant device, the protocol can be executed using mutually unbiased bases. We derive rigorous, non-asymptotic trace-norm error bounds for the PLS estimator, with explicit exponential dependence on the number of nodes. In addition, we establish certified error bounds for estimating entanglement negativity from the PLS estimator. Numerical simulations for systems of up to six qubits distributed across two devices validate the theoretical error bounds.

Abstract: In the quest for quantum advantage, a central question is under what conditions can classical algorithms achieve a performance comparable to quantum algorithms--a concept known as dequantization. Random Fourier features (RFFs) have demonstrated potential for dequantizing certain quantum neural networks (QNNs) applied to regression tasks, but their applicability to other learning problems and architectures remains unexplored. In this work, we derive bounds on the true risk gap between classical RFF models and quantum models for regression and classification tasks with both QNN and quantum kernel architectures. Furthermore, we provide sufficient conditions under which this gap is small and thus the quantum system can be dequantized via the RFF method. We support our findings with numerical experiments that illustrate the practical dequantization of existing quantum kernel-based methods. Our findings not only broaden the applicability of RFF-dequantization but also enhance the understanding of potential quantum advantages in practical machine-learning tasks.

Abstract: Identifying the interactions and dynamics of open quantum systems is essential for characterizing quantum hardware, designing robust simulation protocols, and developing tailored error-correction approaches. Motivated by this, we study the task of learning an unknown Lindbladian generator — a superoperator that fully specifies both coherent (Hamiltonian) and dissipative dynamics. Prior protocols assume known interaction structure, which can be restrictive when the relevant error mechanisms or control imperfections are not known in advance. In this paper, we present the first efficient protocol for learning sparse Lindbladians without any structural or locality assumptions. Our protocol is ancilla-free and uses only product-state preparations and Pauli-basis measurements, making it compatible with near-term experimental capabilities. Moreover, it achieves a nearly optimal time resolution in the regime where the Lindbladian contains at most polynomially many terms. Together, this provides a systematic route to scalable characterization of open-system quantum dynamics, especially when the error mechanisms of interest are not known in advance.

Abstract: Phase estimation serves as a unifying framework for precision measurements in physics. While protocols using Greenberger-Horne-Zeilinger (GHZ) states can achieve the Heisenberg limit, they require prior knowledge of the Hamiltonian to align the probe's sensitivity axis. This necessity for precise alignment imposes a burden on the state preparation stage, limiting practical applications where the field direction is unknown or fluctuating. In this work, we address this limitation by identifying the symmetric subspace as a source of universal metrological resources. We introduce the concept of universal resource states (URS), a class of probe states capable of achieving Heisenberg-limited precision for any linear collective Hamiltonian, independent of its orientation. Our contribution is the explicit analytical derivation of these states and proving that almost all symmetric states serve as URSs for all linear collective Hamiltonians simultaneously. This reveals the symmetric subspace as an inherent reservoir of universal metrological resources: a single, generic symmetric state suffices for high-precision metrology, enabling state preparation completely decoupled from the Hamiltonian's orientation.

Abstract: In this paper, we provide a complete mathematical theory for the entanglement of mixtures of Dicke states. These quantum states form an important subclass of bosonic states arising in the study of indistinguishable particles. We introduce a tensor-based parametrization where the diagonal entries of these states are encoded as a symmetric tensor, enabling a direct translation between entanglement properties and well-studied convex cones of tensors. Our results bridge multipartite entanglement theory with semialgebraic geometry and the theory of completely positive and copositive tensors. This dictionary maps separability to completely positive tensors, the PPT property to moment tensors, entanglement witnesses to copositive tensors, and decomposable witnesses to sum of squares tensors. Using this framework, we construct explicit PPT entangled states in three or more qutrits, disproving a recent conjecture. We establish that PPT entanglement exists for all multipartite systems with local dimension d ≥ 3 and n ≥ 3 parties. We also show that, for mixtures of Dicke states, the PPT condition with respect to the most balanced bipartition implies all other PPT conditions. We further connect bosonic extendibility of mixtures of Dicke states to the duals of known hierarchies for non-negative polynomials, such as the ones by Reznick and Polya. We thus provide semidefinite programming relaxations for separability and entanglement testing in the Dicke subspace.

Abstract: Low check weight is a practically crucial code property for fault-tolerant quantum computing, which underlies the strong interest in quantum low-density parity-check (qLDPC) codes. Here, we explore the theory of weight-constrained stabilizer codes from various foundational perspectives including the complexity of computing code weight and the explicit boundary of feasible low-weight codes in both theoretical and practical settings. We first prove that calculating the optimal code weight is an $\mathsf{NP}$-hard problem, demonstrating the necessity of establishing bounds for weight that are analytical or efficiently computable. Then we systematically investigate the feasible code parameters with weight constraints. We provide various explicit analytical lower bounds and in particular completely characterize stabilizer codes with weight at most 3, showing that they have distance at most 2 and code rate at most 1/4. A $\sqrt{n}$-distance limit is suggested at weight 4, while good codes exist for constant weight 5. We also develop a powerful linear programming (LP) scheme for setting code parameter bounds with weight constraints, which yields exact optimal weight values for all code parameters with $n\leq 9$. We further refined this constraint from multiple perspectives by considering the generator weight distribution and overlap. In particular, we consider practical architectures and demonstrate how to apply our methods to e.g.~the IBM 127-qubit chip. To benchmark these bounds, we present several finite-size code constructions, including examples generated via reinforcement learning. Our study brings the weight as a crucial parameter into coding theory and provides guidance for code design and utility in practical scenarios.

Abstract: We study the question of how much classical communication is needed when Alice is given a classical description of a quantum state $\ket{\psi}$ for Bob to recover any expectation value $\bra{\psi} M \ket{\psi}$ given an observable $M$ with $M$ Hermitian and $||M||_{\text{op}} \leq 1$. This task, whose study was initiated by Raz (ACM 1999) and more recently investigated by Gosset and Smolin (TQC 2019), can be thought of as a fully classical version of the pure state case of the well-known classical shadows problem in quantum learning theory. We show how the hardness of these two seemingly distinct problems are connected. We first consider the relative error version of the communication question and prove a lower bound of $\Omega(\sqrt{2^{n}}\epsilon^{-2})$ on the one-way randomized classical communication, improving upon an additive error lower bound of $\Omega(\sqrt{2^{n}})$ as shown by Gosset and Smolin. Notably, we show that this lower bound holds not only for the set of all observables but also when restricted to just the class of Pauli observables. This fact implies a $\Omega(\sqrt{2^{n}})$ versus $O(\text{poly}(n))$ separation in the compression size between the relative and additive error settings for non-adaptive Pauli classical shadows with classical memory. Extending this framework, we prove randomized communication lower bounds for other relative error one-way classical communication tasks: an $\Omega(2^{n}\epsilon^{-2})$ lower bound when instead Alice is given an observable and Bob is given a quantum state and they are asked to estimate the expectation value, an $\Omega(\sqrt{n}\epsilon^{-2})$ lower bound when restricted to Paulis, and an $\Omega(\sqrt{2^{n}}\epsilon^{-2})$ lower bound when Alice and Bob are both given quantum states and asked to estimate the inner product.

Abstract: Simulating universal quantum circuits is of fundamental and practical importance for the development of quantum computation. But existing simulators, despite being powerful in their own regimes, are limited for quantum error correction (QEC) tasks like testing the fault-tolerance of a QEC gadget or accurately decoding and computing logical error rates under realistic noise. In this work, we propose a simulator called SyQMA that is especially amenable to QEC-related tasks through several attractive features. SyQMA can represent Clifford circuits with incoherent Pauli noise, coherent Pauli rotations and Pauli measurements, returns expected values and probabilities as analytical functions of the error rates, rotation angles and Pauli measurement outputs, and produces samples from the outcome distribution. For QEC, this simulator can perform maximum likelihood (MLD) decoding to return exact and analytical expressions of the logical error rate in stabiliser and magic state preparations, avoiding the problem of rare-event sampling in Monte Carlo simulations. SyQMA is based on an intuitive extension of stabiliser simulators where every non-Clifford Pauli rotation and incoherent Pauli channel is compactly represented with the addition of a virtual qubit, allowing for the consumption of only polynomial memory. We demonstrate the simulator on the FT preparation of stabiliser and magic states in the Iceberg, Steane, [[15,1,3]], and [[17,1,5]] codes.

Abstract: Verification is a crucial property of many cryptographic functionalities, enabling a verifier to check whether a prover conducted an operation as agreed or deviated from the agreement. Probably the most intuitive technique for verification is the cut-and-choose technique, in which the verifier randomly intertwines test rounds with the output round to verify the honesty of the prover. Although this technique was successfully deployed for some use cases, such as quantum key distribution, its suitability for many other functionalities remains unknown. We consider two central verification tasks — quantum state verification and verifiable delegated quantum computing — and prove inherent trade-offs when verification is implemented solely via cut-and-choose: no protocol can simultaneously achieve high correctness, security, and efficiency; improving any one of these quantities beyond certain bounds necessarily degrades at least one of the others.

Abstract: We study quantum sparse recovery in non-orthogonal, overcomplete dictionaries: given quantum access to a state and a dictionary of vectors, the goal is to approximate the state using as few vectors as possible. We prove that the general problem is NP-hard, ruling out efficient exact algorithms in full generality. To overcome this, we introduce Quantum Orthogonal Matching Pursuit (QOMP), the first quantum analogue of the classical OMP greedy algorithm. QOMP combines quantum subroutines for inner product estimation, maximum finding, and block-encoded projections with an error-resetting design that avoids accumulation across iterations. Under mutual incoherence and well-conditioned sparsity assumptions, QOMP provably recovers the exact support of a $K$-sparse state in polynomial time. As an application, we obtain the first framework for sparse quantum tomography in non-orthogonal dictionaries, achieving query complexity $\widetilde{O}(\sqrt{N}/\epsilon)$ in favorable regimes and reducing tomography to estimating only $K$ coefficients instead of $N$ amplitudes. Beyond tomography, we also analyze QOMP in the QRAM model, where it yields polynomial speedups over classical OMP implementations, and provide a quantum algorithm to estimate the mutual incoherence of a dictionary in $O(\sqrt{m}/\epsilon)$ queries, improving over classical and quantum-inspired methods.

Abstract: Quantum information tasks are often analyzed under varying trust assumptions about the devices involved. The semi-device-independent (SDI) framework offers a balance between needed assumptions and experimental feasibility. In this work, we study the energy-constrained SDI scenario, where the only assumption in a prepare-and-measure setup is an upper bound on the energy of the prepared quantum states. In contrast to previous studies that restricted the preparation and measurement devices to be classically correlated, we show that allowing entanglement strictly enlarges the set of achievable correlations. We identify two operational consequences of this result. The first concerns randomness certification, where we show that allowing the adversary to employ entangled strategies may significantly reduce the amount of certifiable randomness. This includes situations where the amount of randomness drops to zero in the presence of entanglement, while it remains positive when entanglement is excluded. Second, for the task of distinguishing an arbitrary quantum channel from the identity, we show that the known dimension-independent bound on the advantage conferred by entanglement is violated under an energy constraint.

Abstract: Fault-tolerant quantum computers rely on Quantum Error-Correcting Codes (QECCs) to protect information from noise. However, no sin- gle error-correcting code supports a fully transversal and therefore fault-tolerant implementation of all gates required for universal quantum computation. Code switching addresses this limitation by moving quantum information between different codes that, to- gether, support a universal gate set. Unfortunately, each switch is costly—adding time and space overhead and increasing the logical error rate. Minimizing the number of switching operations is, there- fore, essential for quantum computations using code switching. In this work, we study the problem of minimizing the number of code switches required to run a given quantum circuit. We show that this problem can be solved efficiently in polynomial time by reducing it to a minimum-cut instance on a graph derived from the circuit. Our formulation is flexible and can incorporate additional consid- erations, such as reducing depth overhead by preferring switches during idle periods or biasing the compilation to favor one code over another. To the best of our knowledge, this is the first automated approach for compiling and optimizing code-switching-based quan- tum computations at the logical level.

Abstract: Standard quantum state tomography assumes sufficient control of a system to measure an informationally complete set of observables. Dynamical quantum state tomography (DQST) presents an alternative: given a system with known dynamics and a single fixed observable, it almost always suffices to control only the time at which each i.i.d. copy of the system is measured. In this work I present an analogous scheme for tomography of multi-mode Bosonic Gaussian states using a fixed homodyne measurement and only assuming control of the time of measurement. I prove that the scheme enables tomography for all discrete homogenous Gaussian evolutions and Gaussian quantum dynamical semigroups except for a null set, give the specific no-go conditions, and discuss practically relevant scenarios including pure states and unitary evolution.

Abstract: We show new constructions for pseudorandom quantum states (PRS) and pseudorandom function-like quantum state (PRFS) generators satisfying \textbf{scalability}, which means the security parameter can be much larger than the number of qubits, \textbf{quantum accessibility}, which means the adversary can provide quantum input, and \textbf{adaptivity}, which means the adversary can query it adaptively. We present an isometric procedure to prepare quantum states that can be arbitrarily random (i.e., the trace distance from the Haar-random state can be arbitrarily small for the true random case, or the distinguishing advantage can be arbitrarily small for the pseudorandom case). This naturally gives the first construction for scalable, quantum-accessible, and adaptive PRFS assuming quantum-secure one-way functions. Compared to prior PRFS works, we use a stronger definition of quantum accessibility, such that the adversary can be ancilla-assisted, i.e., the input state may not be pure and entangled with other quantum registers. Our PRFS construction implies various primitives, including long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classically-accessible adaptive PRFS [AQY21, AGQY22]. This new construction may be helpful in some simplification of the microcrypt zoo.

Abstract: We develop quantum algorithms for estimating properties of general matrix functions using product formulae, with applications to phase estimation, Green’s function evaluation, and sampling from time-evolved states. The resulting methods exhibit low depth, commutator scaling similar to that found for product formulae, and require only a single ancillary qubit. Our central primitive applies Richardson extrapolation to product formulae. By considering a randomized compilation scheme, we also give a protocol to statistically approximate measurement statistics of quantum states, which extends previous settings beyond observable estimation. We give refined analyses of gate complexities for k-local and power law systems; matrix ensembles with long tails; systems where commutator scaling is only understood up to a fixed order; and settings where there is a prior on input states -- those with fixed Fermion number.

Abstract: A central challenge in quantum many-body physics is to understand how operators evolve in time. Key phenomena like operator growth, transport, and scrambling are most naturally framed in the Heisenberg picture, but classical approaches (e.g., tensor networks or Pauli propagation) run into limits set by entanglement or magic. In the first paper of this joint submission, we develop a general Heisenberg-picture simulation framework for quantum computers based on vectorization and transfer-matrix ideas. This lets us represent time-evolved Heisenberg operators as quantum states in a structure-preserving way, so a wide range of Heisenberg-native tasks can be recast as standard state-based procedures. As a result, we obtain new quantum algorithms for computing many operator diagnostics, including Pauli statistics, OTOCs, superoperator moments, two-point correlators, and operator entanglement/stabilizer entanglement measures. In the second paper, we target the problem of learning many correlators simultaneously. We introduce “shadows of Heisenberg operators,” obtained via randomized measurements with local or global Clifford schemes, enabling simultaneous estimation of broad families of OTOCs or two-point correlators from shared data. We also prove information-theoretic lower bounds for multi-OTOC estimation across different learning models, yielding exponential separations that formalize when and why the vectorized approach provides genuine measurement-efficiency advantages.

Abstract: Learning about quantum states is a fundamental problem in physics and quantum computing. As people are often interested in certain properties of quantum states instead of a complete description, shadow tomography has gained significant attention, where the goal is to learn the expectation values of $M$ observables $O_1, \ldots, O_M$ with $\varepsilon$ accuracy. In near-term devices, however, noise is prevalent and often unexpected. Thus, it is crucial to design algorithms that work well in the worst case. We study the practical single-copy setting and assume $\gamma$-fraction of the \emph{outcomes} can be arbitrarily corrupted by an adversary. We show that all non-adaptive shadow tomography algorithms must incur an error of $\varepsilon=\tilde{\Omega}(\gamma\min\{\sqrt{M}, \sqrt{d}\})$ for some choice of observables, even with unlimited copies. Unfortunately, the classical shadows algorithm by \cite{huang2020predicting} and naive algorithms that directly measure each observable suffer even more. We design an algorithm that achieves an error of $\varepsilon=\tilde{O}(\gamma\max_{i\in[M]}\|O_i\|_{HS})$, which nearly matches our worst-case error lower bound for $M\ge d$ and guarantees better accuracy when the observables have stronger structure. Remarkably, the algorithm only needs $n=\frac{1}{\gamma^2}\log(M/\delta)$ copies to achieve that error with probability at least $1-\delta$, matching the sample complexity of the classical shadows algorithm that achieves the same error without corrupted measurement outcomes. Our algorithm is conceptually simple and easy to implement. Classical simulation for fidelity estimation shows that our algorithm enjoys much stronger robustness than~\cite{huang2020predicting} under adversarial noise. Finally, based on a reduction from full-state tomography to shadow tomography, we prove that for rank $r$ states, both the near-optimal asymptotic error of $\eps=\tilde{O}(\gamma\sqrt{r})$ \emph{and} copy complexity $\tilde{O}(dr^2/\eps^2)=\tilde{O}(dr/\gamma^2)$ can be achieved for adversarially robust state tomography, closing the large gap in \cite{AliakbarpourBCL2025robustquantum} where optimal error can only be achieved using pseudo-polynomial number of copies in $d$.

Abstract: The Quantum Approximate Optimization Algorithm (QAOA) promises quantum advantage on combinatorial optimization, yet consistently fails on sparse random instances like 3-regular MaxCut despite strong performance on dense models. This work proves the failure arises from a topological barrier: the Overlap Gap Property (OGP). We formalize "distributional stability" for local quantum circuits via Wasserstein distance (Theorem 1: shallow QAOA satisfies $W_1(P_\xi, P_{\xi'}) \le O(p\Delta\log\Delta)\cdot k$ for $k$ differing constraints). OGP---well-separated near-optimal solution clusters---makes stability incompatible with success: circuits cannot bridge $\Theta(n)$ Hamming gaps along instance interpolation paths unless $p = \Omega(n/\Delta)$ (Theorem 2). Sparse-dense contrast explains empirics: 3-regular MaxCut exhibits $35%-95%$ OGP gaps (bimodal overlaps); SK lacks OGP (continuous via Parisi RSB). Barren plateau fixes address trainability, not reachability. Experiments ($n=8,10,12$) confirm predicted signatures. Impact: NISQ should target non-OGP problems. Local QAOA needs superlinear depth on sparse NP-hard instances. Provides first unified topological hardness for quantum optimization.

Abstract: Hardy’s non-locality provides a proof of the incompatibility between quantum mechanics and local realism without using Bell inequalities. While this argument has been extensively studied for two- and three-qubit systems, a detailed analysis of the four-qubit case is still lacking. In this work, we investigate Hardy’s non-locality for a four-qubit system within the standard two-setting framework. We explicitly construct the entangled state satisfying the Hardy conditions and determine the measurement settings that maximize the success probability. Furthermore, we extend the analysis to multipartite qubit systems and investigate how the Hardy success probability behaves as the number of qubits increases. The results indicate a monotonic increase of the Hardy success probability for larger multipartite systems.

Abstract: Feynman [1] remarked that the spin–statistics theorem is one of the few principles in physics that can be simply stated yet whose proof requires the full machinery of relativistic quantum field theory. A central implication of this theorem is that fermions cannot be composite bosons. This naturally raises the question: can this fact admit an elementary, non-relativistic proof? Bell’s theorem [2] provides a paradigm for such elementary arguments: under the minimal assumption of causality, it rules out classical (local hidden-variable) explanations of quantum correlations. In particular, it shows that quantum systems such as qubits — carried, for instance, by bosons — cannot be simulated by classical bits, and that bosonic correlations cannot arise from compositions of classical particles. Inspired by this framework, we introduce a fermionic thought experiment whose outcome shows that fermions cannot be composite bosons through reasoning analogous to Bell’s theorem. The thought experiment is formulated in the setting of distributed quantum networks and draws on concepts from distributed computing. Within this framework, we prove the existence of fermionic correlations that admit no local hidden-qubit model and are strictly stronger than Bell nonlocal correlations achievable with qubits. This shows that standard quantum information theory is insufficient to represent information carried by indistinguishable fermions in distributed settings. The assumptions remain minimal: causality is preserved, and the distributed parties have no knowledge of the network topology. Our result therefore provides an information-theoretic, non-relativistic proof of the fundamental fermion–boson distinction implied by the spin–statistics theorem. References: [1] R. P. Feynman, The Character of Physical Law, MIT Press (1965). [2] J. S. Bell, “On the Einstein–Podolsky–Rosen paradox,” Physics (1964).

Abstract: Entanglement is a fascinating feature of the quantum world and serves as a key resource for quantum information processing. While its foundation is well-established in the context of distinguishable particles, the concept of entanglement for identical particles is still subject to misconceptions and controversial views. To settle this issue, we first clarify conclusively that identical particles do not define proper subsystems: the algebra of observables of single particles cannot be faithfully embedded into the one of the total system, resulting inevitably in a violation of the subsystem axioms. Accordingly, no notion of entanglement and more general types of correlation between identical particles exists that is genuine, i.e., valid independent of the underlying quantum state. Yet, there exist specific non-generic wave functions which allow one to label the identical particles through disjoint spatial regions or generally orbital subspaces. As a consequence of our work, the crucial idea of `electron correlation' can only be established ad hoc, without the common operational meaning, as the deviation of a given many-electron wave function from the manifold of mean-field states.

Abstract: Entanglement distillation and entanglement swapping have been extensively researched in the context of perfect quantum memories. However, near-term quantum networks will be fundamentally limited by quantum memories with finite coherence time, resulting in complex choices for the timing and ordering of these operations. In this work, we study entanglement distillation and entanglement swapping at the level of the elementary building blocks of noisy quantum repeater networks, with the goal of isolating the basic tradeoffs induced by memory decoherence. First, we focus on a minimal single-hop setting, where we analytically compare "distill-as-soon-as-possible" and "distill-as-late-as-possible" strategies against a benchmark protocol that simply discards the older entangled state. We find that delaying distillation until the end consistently outperforms the other two strategies. We then extend our analysis to two-hop repeater chains using Monte Carlo simulation. In this setting, we find that entanglement swapping should be performed as soon as possible, while distillation should again be delayed to the end. Together, these results clarify how decoherence reshapes optimal operation timing in quantum networks and provide insight into the basic repeater-level rules that govern larger-scale architectures.

Abstract: Quantum kernel methods (QKMs) offer an appealing framework for machine learning on near-term quantum computers. However, QKMs generically suffer from exponential concentration, requiring an exponential number of measurements to resolve the kernel values, with the exception of trivial (i.e., classically simulable) kernels. Here we propose a QKM that is free of exponential concentration, yet remains hard to simulate classically. Our QKM utilizes the weak ergodicity-breaking many-body dynamics in the Rydberg blockade of coherently driven neutral atom arrays. We demonstrate the fundamental properties of our QKM by analytically solving an approximate toy model of its under pinning quantum dynamics, as well as by extensive numerical simulations on randomly generated datasets. We further show that the proposed kernel exhibits effective learning on real data. The proposed QKM can be implemented in current neutral atom quantum computers.

Abstract: We study the problem of verifying quantum states in restricted-access quantum devices, as commonly encountered in cloud-based quantum computing. In such scenarios, users interact with hardware through limited interfaces, motivating verification approaches that rely only on observed statistics, in the spirit of device-independent and semi-device-independent frameworks. We introduce a black-box model in which the device is treated as an oracle with constrained input-output capabilities. Within this setting, we define a simple and implementation-agnostic statistical test for the certification of bipartite entangled states, specifically Bell states, based solely on measurement outcomes. The test is formulated as a hypothesis test using an error parameter analogous to the Quantum Bit Error Rate (QBER). Our main contribution is the introduction of this test together with its experimental validation under realistic access constraints. We implement the proposed method on a 2-qubit NMR platform and observe a stable baseline error rate of approximately 9%, which we interpret as an empirical noise floor. This value naturally defines a tolerance threshold for detecting statistically significant deviations from ideal behavior. Our results provide a concrete instance of semi-device-independent verification and suggest that noise profiles can be leveraged as practical certification tools in access-constrained quantum systems.

Abstract: Monitoring agricultural crops using satellite imagery is important for biovigilance, early yield prediction, and agricultural management. Quantum Machine Learning (QML) models are gaining traction for image classification, with various quantum-only and hybrid quantum-classical circuits being developed under the hypothesis that quantum data representation is more resilient to noise, inherently present in satellite images. In this work, we evaluate several QML circuits for the classification of five agricultural crops: canola, corn, lentils, orchards, and pasture using a new dataset of 65,000 samples. Each sample consists of 9 features derived from verified single-pixel imagery from Sentinel-1 and Sentinel-2 (10 m² resolution), supplemented with ancillary data (land elevation and slope), all collected in Canada during the 2023 growing season. A total of 6 variation of a 10 qubits quantum circuits (18 to 74 gates, single or two-qubits with/without entanglement) were generated, with a final classical dense layer without bias. The simulations were performed using PyTorch with CUDA Quantum and compared to results obtained using five classical machine learning and deep learning models (Random Forest, Support Vector Machine(SVM), Logistic Regression, a three-layer dense neural network (NN), and a 1D convolutional neural network). We report that although some quantum circuits achieved overall F1-score of 0.91 ± 0.05 and ROC AUC of 0.96 ± 0.03, placing them on par with Logistic Regression (0.91 F1, 0.96 AUC) and 1D-CNN (0.92 F1, 0.97 AUC), their classification results were still below those of Random Forest (0.93 F1, 0.98 AUC), SVM (0.93 F1, 0.97 AUC), and the classical NN (0.95 F1, 0.99 AUC). Addition of three dense layers to the best quantum circuit did augment the performance (0.93 F1, 0.98 AUC), but did not improve on the NN results. In conclusion, these results suggest that hybrid quantum-classical architectures, even with relatively few gates, can approach the performance of established classical methods for agricultural crop classification when paired with sufficient classical post-processing, despite the diversity present in those data.

Abstract: It is unknown whether there exists a classical or quantum algorithm that, for a polynomial equation over $\mathbb{F}_q$, counts its zero set in time polynomial in $\log q$, or even approximates the number of solutions, except in low-dimensional or highly structured cases. In this work, we study quantum algorithms that approximate the number of solutions of Laurent polynomials. For a fixed Laurent polynomial $f$ in $n$ variables with $s$ monomials and full-rank support, which means the augmented exponent matrix has full column rank, we construct a quantum algorithm that, for a given $\varepsilon$, outputs an estimate $\widetilde N^*(f)$ of $N^*(f)$, the number of torus points on the associated toric hypersurface, such that \[ \Pr\Bigl[\bigl|\widetilde N^*(f)-N^*(f)\bigr| \le \varepsilon q^{n-s/2}\Bigr] \ge \tfrac23 \] in time $\mathrm{poly}(\log q,1/\varepsilon)$. To the best of our knowledge, this is the first $\mathrm{poly}(\log q, 1/\varepsilon)$-time quantum algorithm achieving an approximation guarantee beyond the general Lang–Weil scale for a nontrivial class of hypersurfaces over finite fields.

Abstract: While extracting the entanglement spectrum is essential for probing exotic quantum many-body phases, standard tomographic methods are limited by exponential measurement overhead. To overcome this scalability barrier, we propose a hybrid quantum-classical algorithm for the partial singular value decomposition (SVD) of bipartite states, grounded in the canonical form of matrix product states. Our framework extracts the dominant and subdominant Schmidt components via sequential deflation-based optimization. Because finite circuit depths and hardware noise degrade the mutual orthogonality between these sequentially extracted vectors, we introduce an explicit classical orthogonality correction using pseudo-inverses. Acting as an error-filtering mechanism, this post-processing enforces orthogonality to high numerical precision. Consequently, it relaxes the expressivity requirements on the quantum processor, allowing the use of shallow and suboptimal ansatzes. This tolerance for shallow circuits also enables a concurrent, synergistic architecture. The classically tractable evaluation of overlap matrices is offloaded to tensor-network contractions. Concurrently, the quantum processor is dedicated solely to computing cross-terms with the complex target state, facilitated by an auxiliary shallow reference state. This quantum evaluation design bypasses the need for controlled target-state preparations, thereby suppressing the error accumulation from massive gate sequences while maintaining linear signal sensitivity. We benchmarked our deflation-based algorithm on the ground states of one- and two-dimensional Heisenberg models, where it demonstrates improved precision over global single-circuit optimization methods that target the entire spectrum. By structurally decoupling numerical accuracy from the quantum circuit optimization, our framework provides a robust solution for large-scale entanglement spectrum estimation on advanced near-term quantum devices and early fault-tolerant platforms.

Abstract: We study spectral statistics and recurrences in translationally-invariant Clifford circuits built from brickwork layers of two-qubit entangling gates and single-qubit layers. We first analyze strictly Clifford circuits, whose spectra exhibit strong degeneracies rooted in stabilizer dynamics and finite-order structure. We then develop a powerful set of algorithms to compute Pauli operator orbits associating them with minimal polynomials over GF(2). Extending to Clifford+T circuits, we move beyond tableau simulation, compute operator Shannon entropy in the Pauli basis, and perform symmetry-resolved level-spacing analyses. We identify families mappable to free-fermion (TFIM-like) dynamics with Poisson statistics and incommensurate quasienergies, as well as circuits displaying fragmentation, near-integrable behavior, and GOE-like chaos when dihedral symmetry is broken or boundary conditions are modified. Our results provide a unified framework for diagnosing integrability, chaos, and scrambling in structured Clifford and non-Clifford Floquet architectures.

Abstract: Nielsen proposed an upper bound on the complexity, defined as the total number of 1 and 2-qubit gates, of simulating a unitary evolution through a quantum circuit. In this work, we study a bound on this complexity. We provide evidence that the fluctuations of this quantity distinguish between integrable and chaotic systems. For random Hamiltonians with GOE, GUE, or Poisson level statistics, the expected height and variance of the plateau reached by the bound for sufficiently large times are universal regardless of the spectral density and level statistics. However, there is an intermediate time scale (depending on the number of qubits) such that the amplitude of fluctuations, and hence the variance, shows a dependence on the chaotic versus integrable level statistics. Our results are analytical and rely on expressions for the spectral form factor of two-point correlation functions. They corroborate previous numerical observations and heuristic arguments of Craps, De ClercK, Evnin, Hacker, and Pavlov. We also analyze various solvable fermion systems and find similar phenomena.

Abstract: We have shown that a simple optical circuit can be used to correct loss in the higher orders of the cat code, with higher-order cats showing significant improvements over their standard two-component (first-order) counterparts. For a channel with 1 dB of loss, the third-order cat requires 70 times fewer correction stages than a first-order cat, albeit at a 3.6 times increase in the required mean photon-number. This savings in resources requires the ability to generate these many-component states, for which little literature exists. Thus as a follow-up, we have begun developing a Kerr-based technique that transforms coherent states into many-component cat states relevant to our correction scheme.

Abstract: Distributed quantum computing offers a path to scaling beyond the limits of single-chip processors by using either nonlocal teleported CNOT gates or classical circuit-cutting techniques. Circuit cutting is flexible but incurs exponential sampling and post-processing overhead, whereas remote gates avoid this cost but require high-fidelity Bell pairs generated over optical links. Using a physically motivated model of noisy microwave-to-optical transducers, we identify the noise regimes in which remote gates match or exceed the performance of gate cutting for distributed GHZ-state generation. These results establish concrete hardware targets for optical interconnects and support a hybrid approach that combines quantum links with circuit cutting in near-term modular architectures.

Abstract: Two distinct paradigms for quantum functional programming have been developed in the last few years: Quantum Signal Processing (QSP)-based methods, including the Quantum Singular Value Transformation (QSVT) [GSLW19], and methods based on higher-order transformations, such as the Universal Hamiltonian Eigenvalue Transformation (UHET) [OKTM25]. While UHET performs functional transformations of Hamiltonian dynamics, its relationship to QSP-based techniques has remained unclear despite evident structural similarities. In this work, we resolve this gap by establishing a connection between UHET and QSP-based frameworks, specifically, we show that UHET can be interpreted as a (randomised) linearisation of Generalised QSP (GQSP) [MW24]. Building on this result, we introduce a linearised variant of QSVT, which we call Universal Hamiltonian Singular Value Transformation (UHSVT). This algorithm enables a transformation by any sufficiently differentiable function f of any arbitrary matrix A encoded in a block of a Hamiltonian, whose dynamics is accessible as a black box, and it can be performed in a wider range of settings than previous QSVT-based approaches. [GSLW19] A Gilyén, Y Su, G H Low, N Wiebe, STOC, 2019. [OKTM25] T Odake, H Kristjánsson, P Taranto, M Murao, PRR, 2025. [MW24] D Motlagh, N Wiebe, PRX Quantum, 2024.

Abstract: Characterizing and predicting quantum dynamics is essential for the development of robust quantum technologies. However, real-world quantum devices often exhibit temporally correlated noise—non-Markovian effects where errors propagate through time and degrade quantum information processing. In this work, we present a scalable tomographic framework for multi-time quantum processes using the higher-order transformation (process tensor) formulation. Our approach accounts for scenarios where past gate errors non-trivially influence future outcomes. By integrating tensor network learning techniques, as well as shadow tomography, we achieve efficient noise characterization for large-scale quantum systems. This scalable, higher-order framework provides new avenues for accurately simulating and mitigating complex noise in next-generation quantum hardware.

Abstract: Time-dependent Hamiltonian simulation is one of the most important applications of quantum computing, but existing approaches based on Dyson-series or Magnus-expansion constructions can require complicated circuits and large hardware overhead. In this work, we propose a cost-aware variant of continuous-qDrift that incorporates implementation cost into the sampling probabilities through importance sampling. We prove that, under the same diamond-norm error requirement as standard continuous-qDrift, the expected total cost of the cost-weighted algorithm is no larger than that of the original method. To assess practical performance, we numerically simulate a Floquet-driven Rydberg system with multi-body interaction terms and use CNOT counts as the cost metric. The results show that the proposed method achieves a similar error distribution to standard continuous-qDrift while significantly reducing total cost.

Abstract: Quantum topological data analysis is one of the most promising areas for quantum advantage. In particular, the LGZ algorithm is the most basic algorithm for estimating Betti numbers, which are considered to be the essential shape of point clouds. Since LGZ, various quantum algorithms have been proposed, but many of them are based on FTQC and require a large number of quantum resources. In this paper, we propose a QTDA algorithm that does not require ancilla bits using a Hamiltonian based on supersymmetry, which has not been widely used in existing research. In particular, by imposing constraints on the graph, we show that there is always a known 0 eigenvalue and eigenstate in the Hamiltonian, this allows us to use ancilla-free measurement algorithms. Moreover, by using randomization, we reduce the required number of samples.

Abstract: Preparing low-energy eigenstates, such as excited states, in quantum systems is a central challenge. Previous method reduces this to a ground-state preparation problem by modifying the system Hamiltonian using an approximate energy of the target state. However, this approach results in a large Hamiltonian simulation cost. Here, by adding a penalty term based on a system-size-independent conserved quantity, we successfully reduce this cost by a square-root factor. We confirm this through numerical simulations on the transverse-field Ising model and the Hubbard model.

Abstract: Topological data analysis (TDA) extracts global features of data via Betti numbers, but classical computation becomes costly for large simplicial complexes. We propose a scalable quantum TDA algorithm for Betti number estimation based on a block-encoded Dirac operator and logarithmic-depth circuit construction using reconfigurable beam splitter architectures. The method combines shallow Gaussian-Chebyshev spectral filtering with resource-focused complexity analysis. We derive error bounds, estimate gate and qubit requirements, and numerically validate correct Betti number estimation on small instances. Our results indicate that larger instances remain challenging at present but continued progress in quantum hardware may enable increasingly larger problem sizes to become realistic targets in the future.

Abstract: We examine photonic how to implement quantum reservoir computing with stochastic internal states on existing hardware, using a classical simulator imitating Xanadu’s photonic quantum computer, Aurora. The proposed model extracts reservoir features from measurement probabilities and modifies Aurora’s native circuit by introducing probabilistic routing between squeezed coherent and squeezed vacuum states. The framework is supported by the universality of the stochastic reservoir map, which can approximate polynomial and more general continuous functions on compact domains. In benchmark simulations, for MNIST classification with reservoir size 1200, the quantum reservoir achieved 91.4% accuracy, slightly outperforming a same-size classical echo state network. The results also suggest that readout stochasticity can improve generalization by acting as an effective regularizer.

Abstract: Quantum resource theories use distillation protocols to convert less resourceful states into fully resourceful ones. However, these protocols often also generate an additional, unused output—referred to as a residual. We propose a framework for the quantum residual management, in which states discarded after a resource distillation protocol are repurposed as inputs for subsequent quantum information tasks. This approach extends conventional quantum resource theories by incorporating secondary resource extraction from residual states, thereby enhancing overall resource utility. As a concrete example, we investigate the distillation of private randomness from the residual states remaining after quantum key distribution (QKD). More specifically, we quantitatively show that after performing a well-known coherent Devetak-Winter protocol, one can locally extract private randomness from its residual. We further consider the Gottesman-Lo QKD protocol and provide the achievable rate of private randomness from the discarded states that are left after its performance. We also provide a formal framework that highlights a general principle for improving quantum resource utilization across sequential information processing tasks.

Abstract: Understanding the relationship between operational entanglement criteria and the dimensional structure of entanglement remains a central problem in quantum information theory. In this work, we analyze the geometry of states satisfying the reduction criterion in bipartite systems. We prove that, for two-qutrit states, the union of the two reduction-positive cones is contained in the cone of states with Schmidt number at most two. Our proof relies on an explicit dual-cone computation together with structural results on positive maps, similar to the theorem of Yang–Leung–Tang stating that every 2-positive map on the set of all 3×3 complex matrices is decomposable. Our work clarifies the geometric role of the reduction criterion in detecting high-dimensional entanglement.

Abstract: Bridging the gap between practical implementation and rigorous security, semi-device-independent quantum key distribution (QKD) offers a compelling middle ground—requiring minimal trust assumptions while achieving key rates competitive with fully characterized protocols. We investigate two conceptually distinct constraints on the preparation device: the information constraint and restricted distrust. We identify protocols that remain secure under both assumptions and demonstrate their robustness to experimental noise. Notably, the widely used BB84 and B92 protocols fail to provide security under the information constraint. To obtain secure key rates, we showcase a numerical framework combining tracial non-commutative polynomial optimization with entropy relaxation techniques. Our approach extends naturally to broader classes of preparation constraints and QKD protocols.

Abstract: Topological codes often rely on overcomplete parity-check matrices (PCMs) containing redundant metachecks to achieve single-shot error correction. Single-shot error correction is vital for reducing decoding latency and circuit depth, as it allows the decoder to correct both data and measurement errors from a single round of syndrome extraction. The prevailing consensus is that these explicit metachecks are a strict geometric prerequisite for single-shot capabilities. In this work, we investigate the decoding performance of CSS-T codes using both overcomplete PCMs of geometric codes (e.g., 3D color codes) and minimal PCMs of algebraic codes containing only linearly independent rows. By leveraging the heuristic A* search of the Tesseract decoder, we demonstrate that single-shot decoding properties are largely preserved even when using minimal PCMs without metachecks. Furthermore, simulations reveal that under realistic circuit-level depolarizing noise, the Tesseract decoder achieves similar logical accuracy on both overcomplete and minimal PCMs, whereas the minimum-weight-parity-factor (MWPF) decoder exhibits a performance degradation of over two orders of magnitude. These findings suggest a pathway to achieving high-accuracy, single-shot fault tolerance while utilizing significantly shallower and less resource-intensive syndrome extraction circuits.

Abstract: Quantum key distribution (QKD) is the most explored application of quantum information theory. A central problem in entanglement-based QKD (EB-QKD), is whether every entangled state can be used to extract a key. We observe that entanglement is not sufficient for standard practical EB-QKD protocols where the input choices are announced by the parties that want to share a secure key, such as E91 or entanglement-based BB84 type protocols, when even an arbitrarily small amount of leakage of classical side information occurs. We do this by identifying a class of two-qubit isotropic states that are entangled but cannot be used to distil the key under such protocols for any possible measurement by the parties. Counter-intuitively, this gap persists even when the leakage occurs from the "junk" rounds of the protocol, i.e, rounds that cannot be used to generate any key. We then extend this result to arbitrary dimensions and parties by identifying a class of isotropic states that are not useful to extract a secure key under such protocols, even if they are entangled. Finally, we demonstrate that our approach provides a tool to upper-bound the scalability of repeater-based QKD architectures in a protocol-independent manner. Interestingly, we find that allowing for even a tiny noise in the preparation drastically reduces the scalability of the QKD network.

Abstract: The Logical Clifford Synthesis (LCS) framework of Rengaswamy et al.\ (IEEE TQE, 2020) enumerates all physical Clifford circuits realizing a given logical Clifford operator for an $[[m,k]]$ stabilizer code, proving that exactly $2^{r(r+1)/2}$ symplectic solutions exist, where $r = m - k$. This result, however, does not extend to subsystem stabilizer codes, whose gauge group introduces degrees of freedom invisible to stabilizer-only theory. We formulate and solve the LCS problem for $[[m,k,g,d]]$ subsystem codes. Our main result proves that the group $\Hgauge$ of physical symplectic matrices that normalize the gauge group and act trivially on logical qubits splits as a direct product $\Hgauge \cong \Hstab \times \Sp(2g,\Ftwo)$, where $\Hstab$ is the stabilizer-sector group of order $2^{r(r+1)/2}$ with $r = m - k - g$. Consequently, every logical Clifford has exactly $2^{r(r+1)/2} \cdot |\Sp(2g,\Ftwo)|$ distinct physical realizations, exhibiting a product structure that permits independent optimization over stabilizer and gauge degrees of freedom. We supply a complete proof via a splitting of a short exact sequence, an efficient two-phase enumeration algorithm with $O(m^3)$ preprocessing and $O(m^2)$ per solution, and a verification on the $[[4,1,1,2]]$ Bacon–Shor code, recovering all $48$ distinct solutions versus the $8$ predicted by the naïve stabilizer count. We further derive closed-form orbit-size formulas, discuss conditions under which the splitting may fail for certain non-Abelian gauge groups, and outline implications for noise-adaptive compilation on near-term hardware.

Abstract: Interactive verification protocols for quantum computations allow to build trust between a client and a service provider, ensuring the former that the instructed computation was carried out faithfully. They come in two variants, one without quantum communication that requires large overhead on the server side to coherently implement quantum-resistant cryptographic primitives, and one with quantum communication but with repetition as the only overhead on the service provider's side. Given the limited number of available qubits on current machines, only quantum communication-based protocols have yielded proof of concepts. In this work, we show that the repetition overhead of protocols with quantum communication can be further mitigated if one examines the task of operating a quantum machine from the service provider's point of view. Indeed, we show that the test rounds data, whose collection is necessary to provide security, can indeed be recycled to perform continuous monitoring of noise model parameters for the service provider. This exemplifies the versatility of these protocols, whose template can serve multiple purposes and increases the interest in considering their early integration into development roadmaps of quantum machines.

Abstract: The problems on which quantum computers will demonstrably outperform classical computers remains surprisingly unclear. Quantum simulation is one area where an exponential advantage is expected, yet establishing this advantage is not straightforward. Here, we propose a scheme for verifying quantum simulations of nonequilibrium dynamics at scale, based on a special class of quantum many-body scars known as stabilizer scars. Our approach leverages the structure of these states to guarantee efficient fidelity estimation, and our analysis connects the fidelity of classically simulable scar-subspace states to that of typical, non-simulable states.

Abstract: Variational quantum algorithms are limited in practice by the barren plateau (BP) problem, where cost function gradients vanish exponentially with system size. We show that Quantum Signal Processing (QSP) provides a structured variational ansatz that is provably BP-free in a region around the all-zero initialization, for a broad class of observables with eigenvalues bounded away from zero. The BP-free region is an ellipsoid in parameter space characterized precisely via the connection to symmetric QSP and the energy landscape results of Wang, Dong, and Lin (arXiv:2110.04993v2). Contrary to the conjecture of Cerezo et al. (arXiv:2312.09121v2) that BP-free cost functions are classically simulable, we show that the cost functions of general QSP ansatze are classically hard. Finally, we show that the optimization over QSP phases can be reduced to a convex quadratic program over Chebyshev coefficients, solvable classically using measurements on unparametrized quantum circuits. These results establish QSP as a theoretically principled variational ansatz that is simultaneously trainable, classically hard, and efficiently optimizable, opening near-term applications in quantum simulation and sensing.

Abstract: In this work we introduce the quantum springs and sticks (QSS) model, a quantum machine learning model that performs supervised learning with an exponential amount of degrees of freedom. The model is based on the springs and sticks model, a classical mechanical system that uses coupled oscillators and dissipation to perform non-linear regression. We map the dynamics to a time-dependent Hamiltonian, which uses the Caldirola–Kanai parametrization to simulate dissipation through unitary evolution. Then, the solution to the supervised learning problem can be extracted via a spectral decomposition. Finally, we simulate our algorithm on simple regression tasks using time-dependent Trotterization, and compare it to the classical Langevin-dynamics version of such algorithm.

Abstract: We investigate whether classical sum-of-squares (SoS) integrality gaps can be lifted to non-commutative SoS (ncSoS) integrality gaps for local Hamiltonians built from the same underlying constraint structure. Our primary object of study is a family of two-basis Hamiltonians H = H_Z + H_X, where each summand encodes a 3-XOR instance over a different Pauli basis, forming a CSS-type Hamiltonian. This construction provides a natural quantization of Max-3XOR in which the classical hardness of the underlying CSP and the quantum geometry of the code coexist in a single object. We make preliminary progress toward establishing such a lifting. We formulate a noncommutative analogue of Grigoriev's theorem for CSS-type Hamiltonians, and show that such a result would give unconditional algorithmic lower bounds against the NPA hierarchy for a natural class of quantum optimization problems. As a first step, we establish tight bounds on the maximum eigenvalue of H in terms of the number of clauses and the unsatisfiability of the underlying instance. We additionally observe that the Lovász theta function of the conflict graph of H gives a natural SDP upper bound on the maximum eigenvalue, and we have identified the underlying conflict graph as a bipartite induced subgraph of a Johnson-scheme graph. We are making progress toward a concrete bound on the Lovász theta function of this graph, which we expect to provide further insight into the integrality gap. The expander graphs underlying the hard CSP instances in Grigoriev's theorem share key structural properties with the Tanner codes used in recent NLTS constructions. We observe that the two-basis Hamiltonians studied here sit naturally at this intersection, raising the possibility of obtaining NLTS Hamiltonians with additional provable hardness guarantees against efficient classical algorithms.

Abstract: Quantum channels generally reduce the distinguishability of quantum states, thereby constraining information transmission and processing in open quantum systems. While it is known that distinguishability can be partially recovered through suitable post-processing protocols, a systematic characterization of the maximal achievable gain has remained elusive. Here, we establish a general framework to determine and optimize the recovery of distinguishability induced by a quantum channel. We introduce an algorithm that identifies the optimal implementation of a multi-copy distillation protocol and applies efficiently to arbitrary channels. Within this framework, we derive a general upper bound on the attainable distinguishability gain and quantify the performance of the protocol in terms of its tightness relative to this bound. Our results show that weakly non-Markovian dynamics can be operationally promoted to the essentially non-Markovian regime via multi-copy coarse graining, as witnessed by the emergence of information backflow. A detailed analysis reveals a nontrivial trade-off between bound saturation and operational advantage, as well as a strong dependence on both the input ensemble and the number of copies. Taken together, these findings provide a unified and quantitative approach to assess, optimize, and interpret distinguishability recovery in open quantum systems, and establish multi-copy processing as a viable mechanism for activating non-Markovian behavior.

Abstract: Solving Laplacian linear systems Lx = b is central to many problems in network dynamics, including heat diffusion, distributed consensus, opinion formation, and centrality estimation. We study three quantum approaches to this problem: Harrow–Hassidim–Lloyd (HHL), the Variational Quantum Linear Solver (VQLS), and Quantum Singular Value Transformation (QSVT). Using a distributed consensus model on graph Laplacians, we compare these methods on ideal statevector simulation and validate HHL on IBM's ibm_rensselaer backend. Our results show that VQLS achieves the best simulated accuracy on small, well-conditioned instances, with relative l2 error as low as 1.18%, while HHL and QSVT exhibit larger errors under the tested settings. On hardware, HHL reaches 18.96% error after backend-specific parameter tuning, indicating that near-term performance is strongly affected by device noise and circuit depth.

Abstract: We study the information-theoretic properties of the full two-parameter family of quantum channels covariant under the orthogonal group O(d), which we call Brauer channels. This family contains the depolarizing and generalized Werner-Holevo channels as one-parameter subfamilies, and its Choi matrix admits a three-block decomposition via Schur-Weyl duality for O(d). We derive closed-form expressions for the maximum output p-norms of Brauer channels and identify a region where two-copy multiplicativity of these norms fails. We prove that the minimum output Renyi 2-entropy is additive for two copies across the entire CPTP region, extending prior partial results. Using orthogonal covariance, we simplify several classical and quantum capacity upper bounds, including SDP-based, approximate entanglement-breaking, approximate covariance, Rains information, and additive-extension bounds, and compare them across the family of Brauer channels. Finally, we derive a closed-form expression for the coherent information of qudit repetition codes through multiple copies of any Brauer channel. We find that repetition codes exhibit positive coherent information beyond the hashing bound in a broad region of channels that includes the qudit depolarizing channel, demonstrating superadditivity of coherent information for Brauer channels.

Abstract: We introduce a machine-learning-aided tensor network (TN) framework for discovering quantum error-correcting codes (QECCs). By directly representing the code space projector as a 2D TN, our approach captures standard stabilizer formalisms while extending naturally to non-additive codes. We frame QECC discovery as a hybrid optimization problem, using continuous gradient-based methods alongside discrete reinforcement learning to simultaneously optimize tensor weights and network topology. This provides a scalable, automated methodology for exploring novel QECCs.

Abstract: We study the fully generalized Grover's algorithm to find the optimal phase changes for each step of the iteration to maximize gain in probability of observation of the target, and when phase matching is required. We find that classical Grover's algorithm and phase matching remains to be optimal till the target probability gets close 1. If phase matching is enforced, we identify the threshold probability based on the size of the data set where the optimal phase change differs from pi. If phase matching is not enforced, we provide an optimization formula to identify the two phase changes based on the current amplitude vector and the size of the set. To analyze this formula, we approach it from a numerical and analytical perspective, with the analytical perspective focusing on special cases that simplify the optimization and allow for general statements about its behavior. Finally we identify a relationship between the complexity of the amplitude vector and the optimal phase change for both the enforced and non-enforced phase matching assumptions.

Abstract: Graph states admit a clean graph-theoretic classification of local-Clifford equivalence: two graph states are equivalent under tensor products of single-qubit Cliffords if and only if their graphs are related by a sequence of local complementations. Graph states are themselves a special case of graph codes, in which a vertex subset selects a logical qubit encoded across the vertices of the underlying graph. We provide the analog of the local-Clifford story for the single-qubit-encoded case: an explicit graph-theoretic recipe for the action of every logical single-qubit Clifford on the graph-code descriptor and the encoded-state coefficients. Each logical Clifford is implemented at the physical level by a circuit of single-qubit Cliffords alone, with no two-qubit entangling gates. We discuss the calculus, its closure, its physical implementation, and several open directions.

Abstract: We introduce a graphical algebra that streamlines the derivation of causal inequalities, alleviating (some of) the combinatorial explosion inherent in the method of inflation. Our approach is an application of the celebrated theory of flag algebras introduced by Razborov in 2007, which continues to be instrumental in the derivation of an impressive variety of new results in extremal combinatorics. We demonstrate the utility of this framework by providing succinct proofs of bounds on the joint distribution of observable variables for various causal scenarios relevant to quantum networks.

Abstract: We address the characterization of genuine network nonlocal correlations, which remain highly challenging due to the non-convex nature of local correlations even in the distinct triangle scenario with three sources and three observers implementing one four-outcome measurement. We introduce a scalable causally inferred Bayesian learning framework called the Layered Local Hidden Variable Neural Network (Layered LHV-Net) to learn the local statistics in network Bell tests. Using this framework, we identify a new class of measurement settings that exhibit the most robust nonlocality compared to previously known measurements. Remarkably, our study shows that the nonlocality measure becomes non-zero only when the visibility of the shared Bell state exceeds 0.94, surpassing previously reported noise robustness thresholds. Further, we examine correlations where shared states originate from dissimilar sources, finding that nonlocality is observed only if all the involved states are sufficiently entangled. Finally, we analyze a scenario in which the sources are allowed to share classical randomness. We find that nonlocal correlations persist even when the sources share up to 3 units of randomness, whereas a local model reproducing the quantum correlations only becomes possible when 4 units of shared randomness are available. Apart from the results, the work succeeds in showing that quantum-informed machine learning approaches as foundational frameworks can greatly benefit the field of quantum information.

Abstract: In this work, we present a new algorithm for generating quantum circuits that efficiently implement continuous time quantum walks on arbitrary simple sparse graphs. The algorithm, called matching decomposition, works by decomposing a continuous-time quantum walk Hamiltonian into a collection of exactly implementable Hamiltonians corresponding to matchings in the underlying graph followed by a novel graph compression algorithm that merges edges in the graph. Lastly, we convert the walks to a circuit and Trotterize over these components. The dynamics of the walker on each edge in the matching can be implemented in the circuit model as sequences of CX and CRx gates. We do not use Pauli decomposition when implementing walks along each matching. Furthermore, we compare matching decomposition to a standard Pauli-based simulation pipeline and find that matching decomposition consistently yields substantial resource reductions, requiring up to 43% fewer controlled gates and up to 54% shallower circuits than Pauli decomposition across multiple graph families. Finally, we also present examples and theoretical results for when matching decomposition can exactly simulate a continuous-time quantum walk on a graph.

Abstract: Quantum marked vertex search algorithms are known to outperform their classical counterparts, yet their behavior in the presence of disorder remains largely unexplored. Here, we address this gap by studying marked vertex search on disordered random graphs. To introduce disorder, we implement the Rosenzweig–Porter (RP) model, a random matrix ensemble with tunable ergodic, non-ergodic extended, and localized phases, on Erd\H{o}s-R\'enyi graph (ER) graphs. This produces a doubly random system where ER graph connectivity masks which interactions exist, while RP disorder controls their strength. The edge probability $p$ tunes the sparsity of the graph, and the parameter $\gamma_{RP}$ independently controls disorder strength, providing a two-parameter framework to study quantum dynamics on disordered networks. We first establish that the RP phase structure survives under graph constraints. We further derive an analytical estimate for the localization boundary, explicitly capturing localization boundary shifting systematically with $p$ in a manner consistent with an analytical hybridization argument. Using this disordered graph ensemble, we study the marked vertex search problem and find that search performance tracks the underlying quantum phase directly. Counterintuitively, the ergodic phase, despite supporting fast transport, yields lower success probability than the localized phase, which achieves high success probability at the cost of significantly longer search times. These results establish a direct and quantitative link between random matrix phases on graphs and quantum algorithmic performance, and suggest that disorder, rather than being merely an obstacle, can be exploited as a tunable parameter in quantum search protocols.

Abstract: We propose a fully operational framework to estimate the quantum umlaut information utilizing a quantum generative adversarial network. We introduce the measured quantum umlaut information and transform it into a min-max objective function suitable for near-term quantum devices. Crucially, we provide a strict mathematical guarantee, proving that the measured quantum umlaut information serves as an approximate of the exact quantum umlaut information.

Abstract: Understanding the complexity of simulating out-of-equilibrium quantum many-body dynamics is a central challenge in quantum physics. In this work, we study this question in the kicked Ising model through two complementary diagnostics: temporal entanglement (TE), which controls the cost of transverse tensor-network contractions, and non-stabilizerness, quantified by the second stabilizer Rényi entropy. Focusing on the transverse boundary vectors generated in transverse light-cone contraction, we analyze how these quantities scale in proximity to classical limits, the dual-unitary point, and inside the generic non-integrable regimes. Although spatial and temporal entanglement are expected to scale linearly in generic non-integrable and dual unitary settings, our results present a multifaceted perspective. TE scaling is substantially more nuanced than the generic volume-law expectation. Although it vanishes at the classical points, it behaves quite differently around them, demonstrating sub-linear growth or area-law saturation depending on the classical point. It also vanishes at the dual-unitary point, but is restored to volume-law growth by infinitesimal detuning. By contrast, non-stabilizerness shows a much simpler pattern, growing linearly through most of the parameter space, with its main qualitative exception again at dual unitarity, where it also vanishes. Our results have implications for the potential efficiency of transverse folding methods in the kicked Ising model, while also underscoring that complexity is multifaceted and cannot be inferred from one notion alone.

Abstract: The speed of elementary quantum gates sets a limit on the speed at which quantum circuits can be applied and, as a result, the size of the computations that can be performed on a quantum computer. This limitation stems from the fact that present-day quantum hardware systems have finite coherence times that limit the total computation time. The speeds of qubit gates in various hardware settings have been well studied over the past few decades. The recent interest in multi-level quantum systems naturally creates a need for similar investigations of the speeds of multi-level or qudit gates. In this work, we perform an empirical study of the speed limit for the three-level or qutrit CZ gate. Our analysis focuses on a theoretical model for capacitively coupled superconducting transmons but can be extended to other systems. We generate CZ gate protocols using optimal control theory techniques and observe when the fidelity crosses certain thresholds. In addition to the empirical approach, we derive an analytical speed limit for the qutrit CZ gate using traditional quantum speed limit techniques. We compare the speed limits derived using these two different approaches and discuss the gap that remains between them. We also compare the time needed to implement the qutrit CZ gate with its qubit counterpart.

Abstract: Quantum key distribution (QKD) brings the promise of communication with information-theoretic security, but is limited in practice due to its susceptibility to noise, losses, and difficulty in accounting for device imperfections. To address these challenges, we propose a robust high-dimensional (HD) \textit{one-sided} device-independent QKD (1sDI-QKD) protocol whose security is certified \mm{via detection/demonstration of steering}. Motivated by recent demonstrations of steering in high-dimensional systems with enhanced robustness to noise and loss [PhysRevX.12.041023], we present a systematic security analysis of HD 1sDI-QKD protocols leveraging quantum steering to certify security. We analyze the achievable secret key rates for protocols with different measurement configurations and system dimensions, combined with a reverse reconciliation scheme, which leads to significant improvements in secret key rates. Our results demonstrate two main advantages: (i) the protocols offer enhanced robustness of the key rates against noise and loss in comparison to fully device-independent QKD, and (ii) the key rate performance shows favorable scaling with increasing dimensions. Finally, we characterize the noise-loss trade-off, highlighting the feasibility of HD 1sDI-QKD in practical scenarios. We further demonstrate progress towards a proof-of-concept experimental implementation of HD 1sDI-QKD by exploring multi-outcome projective measurements across all mutually unbiased bases up to dimension 11. We observe steering violations demonstrating advantages for QKD up to dimension 7 under the fair-sampling assumption. Finally, we discuss perspectives towards a loophole-free implementation of 1sDI-QKD.