Papers

Recently, the BRICS countries created a promising astronomy consortium (https://www.bricsastronomy.org/), which was joined last year by some emerging countries, including two African countries, namely: Egypt and Ethiopia. Certainly, other African countries will join BRICS+ in the years to come. Thus, by pooling their efforts, emerging countries (BRICS+) are sure to quickly catch up with their technological delay in the field of astronomy, particularly through ambitious and large-scale projects. Chile, due to the exceptional climatic conditions of its North, is recognized as the world capital of astronomy where all the largest consortia have settled there and applied all their know-how. The official launch of BRICS (and then its expansion to other countries; BRICS+) is welcomed as an excellent opportunity to think big in the development of astronomy. China has shown great determination in being the first country in the South to establish astronomical facilities in Chile, thus opening a possible opportunity for BRICS+ astronomers. Ambitious astronomical instrumentation is essential for the future of Astronomy and Astrophysics. Access to existing facilities is becoming more and more difficult because of saturation. Existing programs like the VLT-I/ELT and their instruments necessitated decades of collaboration between international institutions. It is therefore necessary for the BRICS+ astronomical community to collaborate together on ambitious projects without wasting time in order to offer a new pole with new opportunities for the researchers. This pole (BRICS-SO), in addition to attracting highly qualified people, will also help train new generations in all our countries, and encourage exchanges and collaborations.

Quantum batteries store energy in nonequilibrium quantum states. The ergotropy sets the work extractable by an arbitrary global unitary, but a device usually exchanges energy through a single local port. It remains unclear how much stored work such a port can deliver, and whether topological edge modes help. We study a dimerized spin chain of Su-Schrieffer-Heeger (SSH) type. Excited two-level ancillas charge it at one end by repeated collisions, and an initially empty two-level load discharges it at the same site. An exact free-fermion mapping yields a bound on the load work for all number-conserving quadratic extraction protocols. The load gains extractable work only if a single-particle mode of the battery holds more than half an excitation. Resonant charging fills the topological edge mode above this threshold. A single boundary pulse then delivers 98.6% of the maximal load work allowed by the bound for representative parameters. Under the same six-collision controls, the trivial-phase load remains passive. Within the protocol that selects the load pulse for maximum delivered work, cycle power peaks at a finite collision number while delivered work continues to increase over the scanned range. Over the tested range, the advantage survives hopping disorder, which preserves chiral symmetry. On-site disorder breaks this symmetry and leaves a finite fraction of loads passive. Topology thus supplies a localized access channel, while spectral matching and symmetry decide whether stored energy becomes usable local work.

Braiding and fusing anyons are fundamental to topological quantum computation, yet existing circuit protocols often employ ancillas and measurements. We determine the minimal circuit resources for performing such anyon operations in quantum double models of generic finite groups. Our approach braids anyons through a sequential unitary circuit without ancillas. Intuitively, this is obtained by deforming the underlying graph on which the anyons live. More generally, we introduce graph rewiring, a diagrammatic calculus that assigns a geometric interpretation to individual two-qudit gates and tracks their action on stabilizers. For fusion, we prove a general no-go theorem excluding purely unitary protocols for fusing unknown anyon types without introducing ancillas. Remarkably, we show such "input-agnostic" fusion is enabled by simply using a qudit reset. Hence, contrary to folklore, ancilla resources are not needed to braid or fuse non-Abelian anyons (non-Abelions). This work has implications in experimental efforts in error correction: our fusion protocol highlights reset as an underutilized primitive for error correction without the spacetime-overhead of ancillas and measurements.

The measures of distance frequently used in quantum information, such as trace distance or fidelity-based purified distance, are the smallest extensions of the corresponding distance measures in classical information theory. However, this way of extending classical distances is not unique, and a whole spectrum of other extensions can be defined. Here we study the question of how quantum information processing tasks are affected by a change of the error metrics to the maximal extensions of the classical distance measures, imposing more demanding error requirements on operational tasks. We find that the performance of some tasks, such as channel coding or quantum resource distillation, is not affected whatsoever by this change. However, for other tasks such as channel simulation and quantum resource dilution, we show that the rates are now given not by functions of the standard (Umegaki) quantum relative entropy, but ones based on the Belavkin-Staszewski relative entropy. Our results connect the Belavkin-Staszewski relative entropy with operational tasks and reveal that known reversibility results in quantum information, including the reverse Shannon theorem and the asymptotic reversibility of quantum resource transformations, no longer hold under maximal distance measures.

We test Refracted Gravity (RG), a phenomenological modified gravity model that modifies the Poisson equation by introducing an effective gravitational permittivity $\epsilon(\rho_{\rm bar})$ which depends on the baryonic matter density $\rho_{\rm bar}$ and mimics the behaviour of dark matter in cosmic structures. We perform a kinematical analysis of member galaxies for a sample of 74 galaxy clusters, compiled from the Cluster Infall Regions in the Sloan Digital Sky Survey (CIRS). We stack the clusters in three bins of increasing velocity dispersion to mitigate the effects of systematic errors induced by deviations from dynamical equilibrium and from the assumption of spherical symmetry. By means of the MG-MAMPOSSt code, we reconstruct the gravitational potential in RG and infer the model parameters jointly with the gas and stellar mass-profile parameters, adopting broad, physically informed priors on the baryonic components. The estimates of the main parameter in Refracted Gravity, the vacuum permittivity $\epsilon_0$, range from $0.04$ to $0.37$, across the three main stacks, depending on the model adopted for the hot gas component. The constraints are mutually compatible within the quoted uncertainties and overlap with previous cluster-scale estimates. The agreement becomes less sensitive to gas parametrisation when selecting the less-disturbed clusters for building the stacks. These results characterize the sensitivity of cluster-scale RG constraints to baryonic modelling and sample selection

We investigate converse bounds on the average decoding error probability in finite-blocklength classical-quantum channel coding. We first present a lower bound for multiple quantum hypothesis testing in terms of pairwise trace distances and derive a corresponding fidelity bound. We then obtain a spectrum-based converse that depends only on the a priori probabilities and spectra of the states. We show that the converse bound remains tight for the quantum depolarizing channel under suitable conditions. For codes with product-state outputs, this converse takes an explicit form involving products of output-state eigenvalues. We apply it to binary codes over the quantum amplitude damping channel using the input states $\vert+\rangle$ and $\vert-\rangle$. For this setting, we also discuss a normal approximation to the spectrum-based converse in the large blocklength regime. In all numerical examples considered, the spectrum-based converse is tighter than the other converse bounds at low noise levels.

Programmable metasurfaces—arrays of elements whose electromagnetic response can be tuned electronically—can process signals as a wave propagates through or reflects off them, a paradigm known as wave-domain analog computing. The design strategy is typically indirect: the surface is fitted to a prescribed linear operator, such as a discrete Fourier transform, and the result is read from output power measurements. Using direction-of-arrival (DoA) estimation as a canonical benchmark, we study what this indirection costs across analog computing topologies, namely reflective reconfigurable intelligent surfaces (RIS), beyond-diagonal RIS (BD-RIS), and stacked intelligent metasurfaces (SIM). We first derive Cramér–Rao bounds for the complete physical estimation chain, including one that accounts for output detectors measuring only intensity. We then formulate a goal-oriented alternative where the surfaces are trained directly through the deployed readout, with no operator target. We observe that goal-oriented training lets sparsely connected or shallower surfaces reach the task performance of their more complex operator-fitted counterparts—despite nearly identical Fisher information—and that the advantage persists under coarsely quantized (1–3 bit) control. From 16 to 64 elements, the depth saving persists, while the connectivity a beyond-diagonal RIS needs grows with the aperture. Under tuner and per-layer loss, the goal-oriented designs keep their advantage.

An important question in quantum information theory asks whether every gate in the Clifford hierarchy is semi-Clifford or not, as such gates admit resource-efficient implementations via gate teleportation. Extending recent results for prime dimensions~\cite{silva_clifford_2025}, we prove that every hierarchy gate on a single qudit of dimension \(d\) is semi-Clifford, if and only if \(d\) is square-free. In composite dimensions, \(\mathbb{Z}_d^2\) is a symplectic module rather than a vector space, motivating a distinction between four types of gates. Semi-Clifford gates ($\mathcal{SC}$) are the ones that become diagonal under left and right multiplication by Clifford gates, while a broader class $\mathcal{N}$ admits a permutation diagonal form, under left and right multiplication by Cliffords. Lagrangian semi-Clifford gates ($\mathcal{LSC}$) conjugate some maximal abelian Pauli subgroup to another, whereas generalized semi-Clifford gates ($\mathcal{GSC}$) map some maximal abelian Pauli subalgebra to another under conjugation. In square-free dimensions, we have \(\mathcal{SC}=\mathcal{LSC}\) and \(\mathcal{N}=\mathcal{GSC}\), but when \(d\) is not square-free, these equivalences can fail, as Lagrangian submodules can become non-free. We also show that every third-level gate of the one-qudit Clifford hierarchy is a generalized semi-Clifford in arbitrary dimensions.

Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting $Q(f\circ g)=\Theta(Q(f)Q(g))$ for all Boolean functions $f$ and $g$; a direct sum theorem asserting that computing $k$ copies of a function (or search problem) costs $\Omega(k)$ times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires $\Omega(k)$ times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution $\mu$ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing $k$ copies of $f$ when the input comes from the product distribution $\mu^k$ instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new “multiplicative” variant of the $\gamma_2$ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new “Shaltiel-free” measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.

We determine the two-way quantum, entanglement-distribution, private, and secret-key capacities of the pure-loss bosonic channel under an unconditional mean transmitted-photon-number constraint. For transmissivity $\eta$ and mean photon number $N$, all four capacities coincide and are given by $g(N)-g((1-\eta)N)$, where $g$ is the entropy of a thermal mode. This resolves the longstanding energy-constrained capacity problem by establishing the optimality of the reverse-coherent-information rate introduced in 2009. Our central tool is sector teleportation simulation, which we develop specifically to transfer the input-energy constraint to the shared entanglement resource, thereby preserving the constraint throughout converse arguments for general adaptive protocols. For every $N>0$, we further show that the corresponding strong-converse thresholds coincide with the unconstrained value $-\log_2(1-\eta)$. For parallel protocols with a hard total-photon-number cutoff, the same energy-constrained capacity formula instead satisfies an exponential strong converse. As an extension, we determine the energy-constrained two-way capacities of the quantum-limited amplifier, showing that classical assistance does not improve its unassisted quantum and private rates. Together, these results establish a unified finite-energy framework for adaptive bosonic communication and reveal how energy constraints fundamentally reshape both attainable rates and converse bounds.

Magic state cultivation is a promising method for preparing high-fidelity non-Clifford resource states - a central component of fault-tolerant quantum computing - with low spacetime overhead. In benchmarking cultivation, existing resource estimates assume access to noiseless transversal measurement of the output magic state to allow for postselection during the final escape stage of the cultivation process. However, such measurements would destroy the magic state and are therefore unavailable during computation. We develop an open-boundary postselection method, Caliper, that uses only nondestructive mid-circuit syndrome information and substantially outperforms existing methods operating under these constraints. In some regimes, our postselection method uniquely recovers the resource efficiency of prior estimates. However, in other cases, we observe a tradeoff. At spacetime costs reported in previous works, the achievable logical error rates can be orders of magnitude higher, and recovering the reported logical error rate requires substantially larger codes and longer escape stages. Our results highlight how practical considerations involving mid-circuit postselection can impact the design and performance of magic state cultivation protocols.

We identify a barrier that helps explain why proving stronger quantum state-preparation lower bounds has been so difficult. In particular, we establish a quantum analogue of the Razborov-Rudich natural proofs barrier for state-preparation lower bounds. We call a property of quantum states natural if it holds for a sufficiently large fraction of Haar-random states and can be efficiently tested when given all of the state's amplitudes. Under a standard cryptographic assumption, we show that no natural property can prove superpolynomial state-preparation lower bounds even against a fixed level of the Magic Hierarchy. We show that several existing state-preparation lower-bound techniques are natural in our sense, including arguments based on approximate degree, not being a unique ground state of a local Hamiltonian, and mutual information.

Efficient fault-tolerant quantum computing architectures benefit from low-weight logical operators. However, reported canonical bases for high-rate, high-distance codes can be several times heavier than the code distance, and fundamental obstructions can prevent minimum-weight logical operators from forming a complete canonical basis. To address this issue, we develop design principles for group-valued quantum error-correcting codes with low-weight full regular canonical logical bases, generated by translating a set of seed operators. We introduce frame width $f$, the smallest weight cutoff that permits a complete canonical logical basis, as an additional code parameter alongside distance $d$ and check weight $w$. Cataloguing these parameters together with explicit logical bases can inform resource estimates and the compilation of fault-tolerant logical operations. First, we identify a structural obstruction: for fully populated binary monomial CSS checks over a group of odd order, full regularity forces distance two, while for groups of power-of-two order, full row rank of both check matrices after replacing every group element by $1$ guarantees full regularity. Second, we demonstrate our principles through explicit high-rate lifted-product (LP) and pair-partition (PP) codes: an $[[1088,128,22]]$ LP code with $f=22$ and an $[[1024,256,24]]$ PP code with $f \leq 27$, both at $w=10$. At $w=11$, our PP constructions attain either $d=25$ with $f \leq 27$ or $d=24$ with the proved optimum $f=25$, demonstrating both a tradeoff among these parameters and a strict separation between distance and frame width. Finally, we propose a method combining symmetry reduction and stabilizer-based pruning for exhaustive distance certification, and use it to efficiently establish exact distances for LP examples with more than a thousand qubits.

We prove that every pure state of stabilizer rank at most $k$ has stabilizer extent at most $2^{O(\sqrt{k\log(k+1)})}$, and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-$k$ operators. This implies stabilizer fidelity at least $2^{-O(\sqrt{k\log(k+1)})}$, resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an $\Omega(n^2/\log n)$ lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of $T$-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states. As a consequence of the Clifford rank–norm inequality, we obtain an $\Omega(n^2/\log n)$ lower bound for exact representations of $n$-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank $O((\log n)^2/\log\log n)$, respectively, a $\log n$ improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most $k$, with $poly(n)2^{O(\sqrt{k\log(k+1)})}$ time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.

We study the spectral gap of recently discovered families of KMS-detailed-balanced Gibbs-sampler Lindbladians for the mean-field Heisenberg model on $n$ spins. We show that the spectral gaps of these natural families of Lindbladians admit the same phase diagram: the gap is constant above the critical temperature (i.e., in the disordered phase), scales as $1/\sqrt{n}$ at the critical temperature, and as $1/n$ below the critical temperature (i.e., in the ordered phase). Our result builds on and extends the recent work of Basso et al.~(2026) which characterized this phase diagram for the GNS-detailed-balanced Davies generator, but only partially resolved the gap scaling at the critical temperature.

On-device machine learning is increasingly important in applications where extreme data rates or resource constraints make centralized processing infeasible. Logic neural networks (LNNs), which directly learn Boolean logic instead of conventional arithmetic operations, have recently emerged as a state-of-the-art approach for efficient inference and are particularly well suited for deployment in custom silicon. However, hard-wired solutions are typically optimized for narrowly defined tasks and lack the ability to adapt to changing data distributions. Next-generation pixel detectors in particle physics present a particularly challenging use case: their high granularity and readout frequency generate data rates that cannot be centrally processed, while stringent space and power constraints necessitate highly efficient on-chip inference. Moreover, radiation damage progressively alters detector response, requiring models that can be re-trained and reconfigured after deployment. In this work, we evaluate LNNs for on-chip inference in pixel detectors. We show that their superior resource efficiency may enable a step change in model capability, making more complex architectures feasible within the available hardware budget. LNNs also provide increased robustness against radiation-induced random bit flips. Finally, we present novel work on reconfigurable LNNs, enabling models to adapt to changing operating conditions after deployment.

We study a Continuous-Variable Quantum Approximate Optimization Algorithm (CV-QAOA) for high-dimensional continuous optimization. Our formulation extends an earlier CV-QAOA proposal with a variationally optimized initial state and recovers the convergence guarantees of Quantum Hamiltonian Descent (QHD) in the high-depth limit. We prove rigorous performance guarantees of CV-QAOA on several families of cost functions. First, we show $d$-step CV-QAOA minimizes any $d$-dimensional strictly convex quadratic function with $2d$ quantum queries to the cost function. We then analyze a family of nonconvex "Rotated Double Well" (RDW) functions with $2^d$ local minima introduced by arXiv:2311.00811. While prior work showed QHD reaches its global minimum with $\tilde O(d^3)$ queries, we prove that 1-step CV-QAOA solves RDW with just two quantum queries. Although general-purpose classical solvers need superpolynomial time for RDW and structure-awareness can reduce the cost to polynomial time, we show that the 1-step CV-QAOA protocol can be efficiently dequantized, and that a gradient-aligned line search succeeds with $O(d)$ queries, nearly matching the information-theoretic $\Omega(d/\log d)$ query lower bound. To move beyond the dequantizable regime, we introduce a “Rotated Square Well” (RSW) problem, whose globally flat landscape suppresses useful local gradient information. For this family, we show that an adiabatic evolution simulated by CV-QAOA can reach the global minimum using $d^{o(1)}$ queries. On the other hand, any classical algorithm that learn the hidden rotation in RSW provably requires $\Omega(d^2/\log d)$ queries, a bound we nearly match with an explicit $\Theta(d^2\log d)$-query classical algorithm.Numerical simulations on deflected corrugated spring and Easom functions illustrate the promising performance of CV-QAOA on more general problems.

Publicly accessible fault-tolerant quantum computers must preserve scientific utility while limiting cryptanalytic power. We propose the restricted model of computation, 1/2BQP_1: a quantum server provides random computational-basis inputs, revealed only after execution, and one designated output bit. This interface permits arbitrary circuits and system sizes. We conjecture that a classical client making polynomially many adaptive requests cannot efficiently factor RSA moduli. The model subsumes the well-known one-clean-qubit model DQC1, retaining its applications to infinite-temperature multi-time correlations, out-of-time-order correlators, and suitably normalized partition functions. We propose a candidate for separating 1/2BQP_1 from DQC1 based on testing classical predictions of quantum spin dynamics. We argue security in two steps. First, we show that one-bit readout makes the quantum stages of standard factoring algorithms classically simulable, even when their preparation and postprocessing are redesigned within a broad family around a single arithmetic-oracle call. This covers the quantum stages of Shor, Ekera-Hastad, Kitaev, and Regev factoring constructions. Second, we examine the workaround of coherently implementing rational reconstruction to release a factor bit. Random inputs obstruct this straightforward attack: known techniques accommodate logarithmic-depth classical circuits, but rational reconstruction has resisted such parallelization for decades. Therefore, we show that security of our protocol is built on not only classical hardness for factoring, but also conjectured circuit lowerbounds for rational reconstruction.

We show that every intermediate state of a broad class of non-Clifford quantum error-correction circuits is a third-order phase-polynomial state, even under stochastic Pauli noise. The class includes magic state distillation and cultivation, code switching and gauge fixing, transversal non-Clifford gates with syndrome extraction, and injection of diagonal magic states. Third-order phase-polynomial states strictly generalize stabilizer states, and we prove that they are exactly the stabilizer states of the diagonal-Clifford-and-Pauli (DCP) stabilizer formalism that we introduce. We characterize these states and show that their representations can be updated in polynomial time. This yields an exact polynomial-time simulation algorithm for these circuits and, more broadly, a framework for reasoning about their internal states and about magic states in general. We provide an open-source implementation, merlin, and benchmark it against existing non-Clifford simulators on distillation, cultivation, and code switching circuits. The benchmarks demonstrate improved runtime and memory scaling as the number of logical outputs grows in Bravyi-Haah distillation, and simulation of a code switching circuit beyond the reach of all other tested simulators.

We study agnostic tomography of pure bosonic Gaussian states: given copies of an arbitrary $n$-mode bosonic state $\rho$, the goal is to output a pure Gaussian state whose infidelity with $\rho$ is at most $\mathrm{opt} + \epsilon$, where $\mathrm{opt}$ is the minimum infidelity achievable by any pure Gaussian state. We give efficient protocols achieving this in both the high and low fidelity regimes. When $\mathrm{opt}$ is below some universal constant, our protocol has runtime and copy complexity which is strongly polynomial in $n, 1/\epsilon$ and $\log \log E$, where $E$ is the energy of the closest pure Gaussian state. For arbitrary $\mathrm{opt}$, our protocol uses $(n+1)^{\mathrm{poly}(1/\epsilon)} \mathrm{poly}\left(1+\log\log(E)\right)$ copies and runtime. As a corollary, we obtain the first truly tolerant Gaussianity testing protocol for distinguishing whether $\mathrm{opt} > c + \epsilon$ or $\mathrm{opt} < c - \epsilon$, for any threshold $c\in(0,1)$. We also prove $\mathrm{poly}(n,1/\epsilon)$ runtime is impossible, unless $\mathrm{NP}\subseteq\mathrm{BQP}$. Our protocols follow a shared paradigm: first, we iteratively use general Gaussian measurements combined with techniques from classical robust statistics to obtain a good warm start estimate, then we leverage non-Gaussian measurements to refine this warm start using convex and non-convex optimization methods. Interestingly, we prove that non-Gaussian measurements are necessary to match the strong agnostic guarantees we obtain, and in fact these guarantees are provably superior to what is possible for robustly estimating classical Gaussians.

We consider the problem of quantum 1-PCA: given copies of an unknown $n$-qubit mixed state, recover a classical description of its leading eigenvector. Our goal is to do so using non-adaptive and single-qubit measurements. For an $n$-qubit state with top eigenvalue $\lambda$ and spectral gap at least $\Delta > 0$, we give an algorithm that recovers the leading eigenvector to fidelity at least $1 - \varepsilon$ with high probability using $\tilde{O}\left( {2^n \cdot \eta^2} / {\Delta^3 \varepsilon^3}\right)$ copies and $\tilde{O}((2^n/\Delta \varepsilon) \cdot \operatorname{poly}(\eta/\Delta\varepsilon))$ time, where $\eta = \max (1 - \lambda, \varepsilon)$. All of our measurements are non-adaptively chosen, and performed in single-qubit Pauli bases. When the spectral gap is constant and the desired accuracy is comparable to the noise level, i.e. $\varepsilon = \Omega (\eta)$, our runtime and copy complexity become $\tilde{O} (2^n / \varepsilon)$. This generalizes the guarantees of Grewal et al. [arXiv:2601.04444], who achieved similar rates, but under the assumption $\eta = 0$, i.e., that the state was pure. Our results show that the same rates hold in the presence of state misspecification, up to polylogarithmic factors. From a technical perspective, our algorithm works by recursively constructing low-dimensional subspaces that approximately preserve the target eigenvector. To achieve nearly linear runtime dependence on the dimension of the Hilbert space, we develop a novel structured Pauli sampling scheme that enables fast batched computation of exponentially many projected Pauli matrices.

The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics. It is highly quantum: Gaussian states are far from the thermal state (Hastings and O'Donnell, STOC'22) and representing the thermal state requires large polynomial-size quantum circuits (Anschuetz et al., QIP'25). Very recently, it was nonetheless proven that classical algorithms can estimate local thermal expectations at sufficiently high temperature in quasipolynomial time (Zlokapa, FOCS'26). We show that classical algorithms can in fact estimate local observables at all constant temperatures in polynomial time. Our techniques also extend straightforwardly to classical systems: we resolve an open question about computing thermal expectations of a classical spin glass up to its phase transition (Bencs et al., STOC'26). Our proof develops a fully rigorous quantum cavity method. Due to the success of the classical cavity method in optimization, sampling, inference and learning, we expect the quantum cavity method to find further applications of independent interest. As an example, we give a quantum algorithm that learns SYK Hamiltonians from the Gibbs state at any constant temperature with polynomial time and sample complexity.

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $\epsilon$ requires $\Theta(\frac{1}{q \epsilon^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $\epsilon$ requires $\Theta(\frac{p(1-p)}{q \epsilon^2})$ queries; (iii) Search among $N$ items requires $\Theta(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $\Theta(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

Nonlocal games offer a conceptually clear way to reason about Bell nonlocality. However, we show that as originally defined, and most commonly used, i.e. with a deterministic predicate, they cannot be complete witnesses of nonlocality. Concretely, we prove the existence of nonlocal behaviours which do not violate any such nonlocal game. Furthermore, we also show that quantum mechanics can produce these game-classical nonlocal behaviours. We prove that this phenomenon exists in every bipartite scenario $(X,Y,A,B)$ with $X,Y\geq2$ and $A,B\geq4$.

Machine-learning emulators of chaotic and stochastic systems are usually validated on forecast skill and long-run statistics. Neither certifies that an emulator responds correctly to forcing, the property that projection and attribution studies rely on. Linear response theory makes this testable: the forced response follows from unperturbed correlations through a generalized fluctuation-dissipation relation, and decomposes over the stochastic Ruelle-Pollicott resonances of the Koopman generator. Building on the Koopmanism Response framework, we turn this into a calibrated, mode-resolved test for learned surrogates: each surrogate rollout passes or fails each check, and failure rates are compared with those of independent realizations of the true system. On stochastic Lorenz-63, a three-variable toy model, we evaluate SINDy, an MLP, a reservoir computer, a neural ODE and a neural SDE with learned diffusion, over up to 80 rollouts each. A sparse-regression model with the correct library passes every check at rates consistent with the true system. Invariant-statistics fidelity and response fidelity dissociate in both directions: a quarter of reservoir-computer rollouts pass every invariant-statistics check and match the static susceptibility $\chi(0)$, yet misrepresent the slow relaxation modes, while the neural ODE and SDE rarely meet the invariant-statistics floor but recover those modes in three quarters of rollouts. As expected of a time-integrated quantity dominated here by fast relaxation, $\chi(0)$ does not separate these cases. For a fixed network, the training formulation (one-step drift, flow map, or multi-step through the integrator) decides which of these properties it gets right.

We use an instanton-based analysis to show that Path Integral Stochastic Gradient Descent (PISGD), a classical optimization algorithm instantiated from path integral Monte Carlo (PIMC), can inherit the quantum tunneling mechanism. Quantum tunneling is the phenomenon in which a quantum particle passes through a potential barrier that a classical trajectory cannot cross in the same way. This mechanism can contribute to the performance of quantum optimization algorithms, since a common bottleneck in optimization is that the solution becomes trapped in a local minimum, separated from better solutions by a potential barrier. Classical noise-driven optimizers, such as stochastic gradient descent (SGD), have escape times that scale exponentially with the potential barrier height. For quantum tunneling, the escape time is instead exponential in the bounce action, which equals twice the Agmon distance between the two basins. When the barrier is tall but thin, quantum tunneling can allow escaping local minima faster than such classical methods. Remarkably, this scaling is not exclusive to algorithms with genuine quantum dynamics. For PISGD applied to classical nonconvex global optimization, we adapt Kramers' escape-rate theory to path space and obtain the same exponential scaling as quantum tunneling, in terms of the bounce action rather than the barrier height. We confirm this scaling numerically by implementing PISGD for both separable and nonseparable potentials. That said, PISGD retains only incoherent tunneling, since coherence among multiple tunneling paths is absent. Our analysis therefore does not rule out a potential quantum advantage for quantum-tunneling-based algorithms over classical ones in general.

Bosonic and fermionic Gaussian quantum states are families of quantum states that play a central role in quantum physics and quantum information processing. We study the problem of testing whether a given state is either Gaussian, or has bounded overlap with any Gaussian state. Previous analyses of this testing problem led to tests that require a number of copies of the state that scales with the number of modes (the system size). In this work we show that a constant number of copies of the state suffices. We derive these results based on the symmetries of identical copies of Gaussian states, and by bounding the distance to the set of Gaussian states through a gradient flow and a spectral bound studied previously for the Kac random walk on a sphere.

We propose a four-level scheme for generating a uniform imaginary magnetic field for ultracold atoms using Raman coupling and state-dependent particle losses. Eliminating two lossy auxiliary states and subsequently projecting onto one of the two remaining Raman-dressed atomic states, we find that the atomic motion is affected by an imaginary vector potential which is engineered to have a constant curl corresponding to a spatially uniform imaginary synthetic magnetic field. We analytically derive the Gaussian wavepacket dynamics for atoms in such a synthetic magnetic field and study the width-dependent transport, unlike motion in a uniform real magnetic field. We find numerical agreement between the two-level non-Hermitian Hamiltonian and the adiabatic projection description, confirming the applicability of the latter adiabatic approach.

Recent work has shown that syndrome information obtained during error-corrected quantum computation can be utilized for logical error mitigation (LEM), yielding exponential reductions in runtime overhead compared to "external” LEM methods, which do not make use of syndrome data. However, these syndrome-aware LEM methods (SALEM) generally require adaptive circuit operations based on real-time processing of syndromes. Here, we introduce syndrome-based offline logical error mitigation (SOLEM), a framework that utilizes syndrome data entirely in post-processing, without any modification to the given error-corrected circuit. In this sense, SOLEM is "built into” error-corrected circuits, and is in fact simpler to implement than external LEM protocols. The basic idea of SOLEM is to use naturally occurring syndrome-conditioned logical error channels in place of deliberate circuit modifications. We develop unbiased and heuristic estimators within this framework, including offline logical versions of probabilistic error cancellation (PEC) and zero-noise extrapolation (ZNE), as well as a global-regression estimator. SOLEM's fully offline nature leads to three significant advantages. First, SOLEM can post-process syndromes with a more powerful decoder than the one used in real time. Second, multiple estimators can be constructed from the same measured data and optimized using empirical statistical errors and related performance metrics. Third, logical error characterization is needed only in post-processing, allowing characterization data to be collected during circuit execution and reducing sensitivity to hardware drift. Remarkably, SOLEM estimators can achieve these advantages while attaining a runtime overhead which is exponentially lower than that of external LEM and is comparable to that of corresponding SALEM estimators.

Elastic scattering can generate entanglement and non-local magic between the spins of the two outgoing particles. The amount of entanglement and magic produced is encoded in the S-matrix; a unitary quantum gate that acts on the joint Hilbert space of the two spin-J particles. Previous work derived the entanglement power in terms of the scattering phase shifts for rotationally invariant S-matrices with J=1/2,1,3/2. In this paper, a closed form solution is derived for all J. We further prove that a broad class of non-local quantum resources depend to leading order only on the squared projective Hilbert-Schmidt distance from the nearest non-entangling gate. This holds for the entanglement power and non-local magic power, and the choice of resource simply changes the overall normalization. This universality establishes a common geometric origin for the leading resource-generating capacity of scattering, independent of the details of the interaction.