Papers

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.

We distill Kokoro-82M, a widely used open text-to-speech model with 54 voices, into Paradee, an 8.07M-parameter model that speaks one of them. Paradee keeps Kokoro's architecture with much narrower layers, and each of its two halves is trained separately against the frozen teacher. It has 10x fewer parameters and needs 15x less compute. We first synthesize a corpus with the teacher and keep its durations, pitch, energy and phoneme features. We then train a small text side to predict these values, and a small decoder to turn the teacher's saved values into the teacher's audio, first with spectral losses and then adversarially. Finally, we connect the two halves and quantize the weights to int8. It needs no alignment learning and no joint training, and it runs on one laptop. Stored in int8, Paradee is 8.5 MB, runs 25x faster than real time on one CPU thread, and scores 4.41 on UTMOS against the teacher's 4.52. The student initially kept a slight buzz, which we trace to the phase of voiced speech between 2 and 8 kHz. A phase-locking filter applied after synthesis removes most of it, with no training and no extra parameters. Code, model files and audio samples are at https://github.com/sahilmahendrakar/paradee

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.

World models learn to predict how their environment will evolve, making them an important foundation for general-purpose robotic control. Yet world action models depend on camera inputs whose manipulation can corrupt the visual representations used across tasks and action policies. Existing attacks on these models optimize against the victim's actions or predicted futures and therefore require access to target-model outputs. In this paper, we propose an attack, TAPDreamer, against world action models that instead uses a public encoder alone to construct a fixed local perturbation that transfers across tasks and action architectures. TAPDreamer requires no target-policy queries. Our key insight is that interactions between patch-induced changes in attention weights and value vectors broadcast a nearly identical representation shift far beyond the patch footprint, and this shift remains stable across task observations. Guided by this insight, TAPDreamer uses six frames from one source task to maximize the global L1 distance between clean and patched encoder representations. In closed-loop evaluation, one frozen patch per benchmark, covering about 6.5% of the input, reduces FastWAM's success rate from 97.7% to 0.0% across 40 LIBERO tasks and from 90.86% to 0.0% across 50 RoboTwin tasks; matched random patches retain 81.5% and 79.2% success. The same patches reduce success to 1.45% and 1.00% on two DreamWAM configurations and to 10.60% on Motus. These results show that protecting downstream action generation alone is insufficient: defenses for world action models must also secure shared visual encoders against persistent local perturbations.

Recent progress in 3D foundation models has enabled rapid 3D reconstruction and camera calibration by leveraging learned 3D priors from vast amount of spatial data. However, the all-to-all global attention design leads to quadratic complexity and limits long-sequence inference; unconstrained cross-view interactions also can propagate unreliable evidence from occluded or visually similar but geometrically distant views. In this paper, We introduce a Masked Geometric Encoder (MGE), which promotes the learning of robust geometric representations under incomplete cross-view context. During training, MGE strategically drops frame tokens from global attention and distills from a pretrained full-context teacher model. This allows the model to learn an intrinsically richer per-frame representation while providing sufficient intermediate supervision to avoid performance degradation. Through extensive experiments, we show that MGE leads to much stronger performance under occlusion and doppelganger views while retaining high performance on standard benchmarks. Such a richer frame representation also leads to more effective token reduction during inference. To this end, we develop a novel Anchor-Guided Adaptive token merging technique that preserves representative anchor frames while jointly merging redundant tokens from the remaining views. Compared to other efficient inference approaches, we can achieve inference speedup while consistently maintaining higher reconstruction quality, particularly in limited-view settings.

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.

Causal representation learning (CRL) is the process of recovering causally-related latent variables from high-dimensional observations. As a label-free inference method, CRL is particularly attractive for applications where data labels are unavailable or impractical to obtain. While there has been significant progress in understanding the identifiability guarantees of CRL, such guarantees often hold under highly stylized assumptions, which temper the direct application to real-world problems. This paper has a two-fold objective for interventional CRL. First, it establishes identifiability guarantees for substantially weaker interventional assumptions, resulting in block disentanglement of the causal variables, where the block structure depends on the realistically available intervention mechanisms. Secondly, the block disentanglement framework is used for embodied visual state estimation, in which the objective is to recover the latent physical variables of a robotic system directly from visual data (images and videos) without labeled data. These two components are critically complementary. The block disentanglement theory delineates identifiability guarantees under weakened assumptions, and the application demonstrates that the resulting objective remains effective in a controlled embodied setting despite further assumption violations, providing a theory-to-practice bridge needed to translate the promise of label-free CRL into practical problems.

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 settle the long-standing Godbersen conjecture that the mixed volume of a convex body of fixed positive volume with its reflection about the origin is maximized precisely by simplices. For the proof, we establish a new characterization of simplices by a natural incidence relation on the face lattice. Moreover, we establish a higher-order generalization of the Godbersen inequality and show that simplices are the only nontrivial equality cases, confirming a conjecture of Schneider from 2000.

Long-horizon planning with latent world models requires reasoning across timescales and levels of abstraction. Existing task-agnostic JEPA world models predict and plan in a single latent space, often at a single timescale. We introduce H-JEPA, an end-to-end recipe for training a hierarchy of action-conditioned JEPAs in which each level predicts farther ahead in its own learned latent space. Planning proceeds top-down: the top level optimizes progress toward the goal, and each level's predictions become subgoals for the planner below it. When factors in the data evolve at separated timescales, higher levels discard fast, unpredictable detail and retain slower task-relevant state. Across four simulated navigation and manipulation environments, hierarchical planning improves over a flat JEPA; on Visual AntMaze, a three-level hierarchy raises success from 18% to 73% using less planner compute. Ablations attribute these gains to both temporal decomposition and higher-level goal representations. With inverse-dynamics supervision, the approach extends to diverse real-robot videos from DROID, where hierarchy improves offline planning fidelity at lower planner compute.

A language model can give a correct answer more probability than any single incorrect answer and still usually sample an incorrect one, because the incorrect answers together hold more probability. The power distribution raises each complete answer's probability to a power above one and renormalizes, shifting probability toward answers the model finds most likely (sharpening). Sampling from it improves reasoning without changing parameters, but needs many scored candidates per query. We show that a model can instead be trained to produce such answers in one generation. On-policy power distillation (OPPD) runs a sequential Monte Carlo sampler in which the model being trained generates candidates and a frozen teacher's power distribution weights them; the same probabilities weight each answer in a maximum-likelihood update. Training raises single-generation accuracy by up to 23.0 points on MATH500 and 27.3 on GSM8K over the untrained model at the same temperature, and one generation scores 2.4 and 3.5 points above published power sampling with 64 candidates, recovering 94 percent of the gain that 16 candidates give the untrained model. For context, against GRPO trained with verified rewards from the same checkpoint and budget, OPPD scores 3.8, 4.0 and 5.4 points higher on MATH500, GSM8K and AIME using no reference answers; the two are complementary, and OPPD applied after GRPO adds up to 9.3 points. Trained only on mathematics, OPPD raises HumanEval accuracy by up to 5.3 points. One loss coefficient moves the sharpening exponent the model absorbs between 1.19 and 2.02, against 1.14 for ordinary on-policy distillation, and it rises mostly on the model's own answers. Gains hold across model families and sizes, including a model already trained with verified rewards, where lowering the temperature gives nothing and OPPD adds 4.4 points on MATH500. Code: https://github.com/ArminAzizi98/OPPD.

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.

Descriptive set theorists often refer to elements of the Baire space, $\mathcal{N} = {}^\omega\omega$, as “reals.” In this expository article, we present mathematical justification for this practice and highlight the advantages of working with $\mathcal{N}$ over $\mathbb{R}$ in the context of descriptive set theory.

Sparse attention is a primary approach to reducing the latency of diffusion transformers in long-sequence generation tasks, such as video and high-resolution 3D asset generation. However, existing methods can degrade generation quality and fidelity at high sparsity levels. Through controlled oracle comparisons, we trace this degradation to three sources: constraints imposed by token grouping, inaccurate interaction selection, and the attention contributions lost when tokens are discarded. Guided by this analysis, we propose Meta-Cached Sparse Attention (MC-Sparse), a training-free framework that selects individual key-value (KV) tokens while organizing similar queries into tile-aligned groups for efficient GPU execution. MC-Sparse caches metadata comprising query groups, KV indices selected using exact attention probabilities, and residuals between dense and sparse attention outputs, and reuses them across subsequent denoising steps. Across video and 3D generation models, MC-Sparse achieves higher fidelity to dense-attention outputs and larger denoising speedups than existing sparse-attention baselines, without visible quality degradation. Relative to dense attention, it delivers a $1.80\times$ denoising speedup on Minimax-H3-Base and a $2.32\times$ speedup on 3D asset generation, both with negligible quality loss.

Let $\Bbbk$ be an algebraically closed field of characteristic zero and let $f$ be a nonconstant polynomial in finitely many freely noncommuting variables. We prove the asymptotic Makar-Limanov rank conjecture, namely that the normalized rank of a value of $f$ can be made arbitrarily small by choosing matrices over $\Bbbk$ of finite size.

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.

For $\kappa>1$, a directed graph is $\kappa$-conditioned if it is $\kappa$-mixing and its stationary distribution is approximated by the uniform distribution within a factor of $\kappa$. We present a deterministic algorithm that approximates the stationary distribution of a $\kappa$-conditioned graph to inverse polynomial relative error in $O((\log n + \log^2 \kappa) \log \log n)$ space. In the regime $\kappa = \exp(\Theta(\log^\alpha n))$ for any $\alpha \in (0, 2/3)$, our result improves the best-known $O(\log n \sqrt{\log \kappa} / \sqrt{\log \log n})$ space bound for approximating $\kappa$-step random walks in general directed graphs by [Hoza, RANDOM 2021]. We release this preliminary version due to recent rumors of LLM-based progress on related problems and uncertainty about when those results may appear. Further implementation details will be provided in a subsequent version.

We introduce Round-Trip KNN Clustering (RTKNNC), a graph-based method for finding cluster structure at several neighbourhood scales without requiring the number of clusters in advance. Unlike approaches that first make a $k$-nearest-neighbour (KNN) graph undirected, RTKNNC keeps both directions of the neighbour relation: which points a given point selects and which points select it. Incoming selections are treated as weighted votes that help decide which local connections remain visible during a recursive forward-and-reverse traversal. Repeating the procedure for increasing $K$ reveals how groups persist or merge as the neighbourhood scale grows; for the reference inverse-square model before structural refinement, clusters can merge but do not split. Because graph connectivity can occasionally join distinct groups through a sparse bridge or a small region of overlap, we add an optional label-free refinement. It first tests whether an already formed component is better described by two or three Gaussian subpopulations, and accepts a subdivision only when the proposed groups are large enough and consistent with the visible KNN graph. Across eight synthetic datasets and $K=2,\ldots,16$, independent C and Python implementations produced identical partitions in all 120 reference runs. Refinement increased adjusted Rand index from $0.7817$ to $0.9627$ on a variable-density benchmark and from $0.8083$ to $0.9853$ on a sparse-bridge benchmark. Comparisons with seven external clustering methods show competitive performance while preserving a label-free cluster-construction process.

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.

The unprecedented computational scale of modern artificial intelligence depends on complex, multi-billion-transistor Systems-on-Chip, yet the workflows that verify these chips remain stubbornly manual. Although Large Language Models (LLMs) have made rapid inroads into Electronic Design Automation (EDA), approximately 74.6% of existing studies target static Register-Transfer Level (RTL) code generation, leaving post-simulation verification and interactive waveform debugging largely untouched. We introduce Back-to-the-Future (BTTF), an end-to-end agentic framework that closes this infrastructural gap. BTTF distills massive, unstructured simulation dumps into a normalized relational SQLite database and couples it with a collaborative multi-agent orchestration engine that translates natural-language verification queries into schema-aware SQL while correlating signal anomalies with versioned RTL repositories. Across a 150-query benchmark, BTTF attains 95.33% execution accuracy, charting a practical path toward autonomous EDA verification.