Peer Revenue Returns subject to peer review

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

All of arXiv

Monday 5 October

Quantum Physics

Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem

We study the one-way communication complexity of the $f$-Boolean Hidden Partition problem. Here, Alice is given an $n$-bit string and Bob is given $\Omega(n)$ disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of $f$ on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where $f$ is the parity function. We establish classical and quantum communication bounds for $f$-Boolean Hidden Partition in terms of the sign degree $d$ of $f$, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when $d \le 1$ and quantum protocols when $d \le 2$, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every $f$ of sign degree $d \ge 2$, the randomized classical communication complexity of this problem is $\Theta(n^{1-1/d})$ while its quantum communication complexity lies between $\Omega(n^{1-2/d})$ and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions $f$ admitting polynomial quantum advantage as those for which $d \ge 2$, with a new infinite family of exponential separations given by the case $d = 2$.
Read the full abstract

All authors Mark Bun, Joao F. Doriguello, John Kallaugher, Nadezhda Voronova

Probability

Large corank of dense random regular digraphs

Let $1\le k\le n$ and let $A$ be the adjacency matrix of a uniformly random $d$-regular directed graph on $n$ vertices. Suppose that $\lambda n\le d \le (1-\lambda)n$ for a fixed $0<\lambda\le 1/2$. We show that there exists $c_{\lambda}>0$ depending only on $\lambda$ such that $$ \mathbb{P}[\operatorname{rank}(A)\le n-k]\le 2e^{-c_{\lambda} kn}. $$ This gives a large corank extension of the exponential singularity bound of Jain, Sah, and Sawhney.
Read the full abstract

Quantum Physics

Computational entanglement distillation beyond pure states: efficient protocols and fundamental limitations

The information-theoretic approach to entanglement typically relies on arbitrarily many input copies and unboundedly complex operations; however, the available resources are constrained in reality. This motivates the study of entanglement theory with limited resources. One of its central questions is which quantities characterize entanglement manipulations, and so far, only the idealized case of pure states has been well explored. In this work, we address entanglement distillation from mixed states and identify the Rényi coherent information as the quantity determining the optimal rate in the worst case under two distinct resource constraints. We first characterize the sample-efficient regime, in which unbounded computational power is allowed. Our universal protocol achieves this rate without knowledge of the input state under certain polynomial rank constraints. This rate is optimal among universal protocols: we construct states whose distillable entanglement is nearly extensive, yet from which no universal sample-efficient protocol attains a rate above their Rényi coherent information. We then push this characterization to the computationally efficient frontier: the same bound holds for any efficient protocol even when the input state is known, and another universal protocol achieves this rate efficiently under additional polynomial constraints on the marginal ranks. Overall, our results give the Rényi coherent information a novel operational meaning in two computational settings: universal distillation with limited copies and efficient distillation even with knowledge of the input state.
Read the full abstract

All authors Takeru Utsumi, Jacopo Rizzo, Ryuji Takagi, Lorenzo Leone

Quantum Physics

Quantum-optimized phase closure for robust interferometric imaging

Closure phase enables imaging with ground-based interferometric arrays by canceling telescope-dependent phase errors due to atmospheric fluctuations. It can be obtained by measuring fringe phases on individual baselines forming a triangle and summing them. We show that closure phases can be measured more accurately with fewer photons by performing joint measurements on multiple photons. We first establish that at least three photons from the same atmospheric temporal phase-stability window are required for closure-phase information to survive the unknown telescope-dependent phase noise, and show that joint three-photon measurements already provide an advantage over single-photon measurements in the minimal three-telescope setting. We then turn to large arrays and consider estimating all bispectra—complex quantities whose phases are the closure phases—under a global mean-square error criterion. Although an $m$-telescope array contains $\Theta(m^2)$ independent triangle bispectra, we show that physical constraints on the visibilities make the total information content grow only nearly linearly with $m$ at fixed accuracy. Exploiting this structure, we construct an efficient protocol using at most three-photon joint measurements with photon cost $\tilde{O}(m)$, whereas any sequential single-photon protocol requires $\Omega(m^2)$ photons. When the number of detected photons per temporal stability window scales linearly with the array size, this allows the required exposure time to remain independent of $m$ up to logarithmic factors. We further analyze the complementary high-precision regime using multiparameter quantum metrology and find a similar advantage for collective measurements. Overall, our results show that quantum information processing techniques can substantially improve the sensitivity and robustness of optical interferometry.
Read the full abstract

All authors Zhenning Liu, Emil T. Khabiboulline, Lorcan O. Conlon, Brittany McClinton, Aqil Sajjad, Saikat Guha, Jayadev Rajagopal, Alexey V. Gorshkov, Daniel Gottesman, Stephen T. Ridgway

Numerical Analysis

On the Growth Factor of Random Matrices

Gaussian elimination is the oldest and most popular method for solving a linear system. Its numerical stability for a given matrix is controlled by the growth factor, a measure of how large entries can become during elimination. In this work, we prove a number of new results regarding the growth factor of random matrices. First, we provide tight estimates for the growth factor of a matrix preconditioned by a Haar orthogonal matrix without pivoting and characterize the asymptotic distribution of the growth factor of Gaussian matrices without pivoting. Second, and most notably, we prove that the growth factor of an $n \times n$ Gaussian matrix under partial pivoting is rarely much larger than $\sqrt{n}$, resolving an old conjecture of Nick Trefethen. The same techniques used to prove this conjecture also provide an improved smoothed analysis of the growth factor under partial pivoting.
Read the full abstract

High Energy Physics (Experiment)

How to scale your HEP ML models: A recipe for robust architecture comparisons at scale

Much of the recent progress in machine learning domains such as language models has come from scaling laws that predict performance as a function of training effort. In high-energy physics (HEP) similar behavior has now been observed. To aid further study, we present a systematic procedure to derive robust scaling laws and compare design choices on the relevant budget axes for HEP tasks. We first validate the full scaling trajectory on toy problems and then apply the procedure to multi-task transformers on the ~11 billion-jet ATLAS JetSet2 dataset, in both the compute- and data-constrained regimes. For the latter, we predict, to the best of our knowledge for the first time, the jointly optimal model size, training horizon, learning rate and batch size under early stopping. At compute-optimal scaling, we recover a near-equal $\sqrt{C}$ dependence of model and dataset size, and find that auxiliary objectives lower the primary jet-classification loss at equal compute budget. Expanding the inputs toward lower-level data systematically lowers the loss while leaving the scaling exponent nearly unchanged. The onset of the power-law regime is itself set by scale: below a threshold in dataset size the loss carries little information about high-compute scaling, underscoring the value of large, high-quality full-simulation datasets as a foundation for scaling studies and the development of foundation models in HEP.
Read the full abstract

All authors Matthias Vigl, Nikita Pond, Jackson Barr, Alexander Froch, Dan Guest, Nicole Hartman, Michael Kagan, Lukas Heinrich

Data Structures and Algorithms

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial size in $O(n^{1.9992})$ time and APSP on directed $n$-vertex graphs with polynomially bounded integer weights in $O(n^{2.9995})$ time. This refutes the $3$SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the $3$SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight $k$-Clique hypotheses, and the three rectangular hinted Online Matrix–Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems. All of these results follow from a single new algorithm for thin matrix products. Let $X$ be an $N\times D$ integer matrix and $Y$ a $D\times N$ integer matrix with $D\le N^{1/18}$, and let $W$ be any set of at most $N^2/\sqrt D$ positions. We compute the entries $(XY)[I,J]$, $(I,J)\in W$, in $O(N^2/D^{0.063})$ operations, which is polynomially less than the time needed to write down $XY$ or to compute $N^2/\sqrt D$ inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schönhage, to perform only the operations needed for the entries in $W$, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have $n$ vertices but one part has $n^{\varepsilon}$ vertices for $\varepsilon<0.12$. By known reductions, Exact Triangle, and hence $3$SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of $XY$, not known in advance.
Read the full abstract

Computation and Language

T-Search: An Open Agentic Retriever and Playground for Hard Multi-Step Search

We present T-Search, an open-weight agentic retriever for hard multi-step search. Given a question and a search tool over a fixed corpus, it runs a bounded multi-round search and returns a ranked list of evidence chunks with short justifications, leaving answer generation to a downstream model, so backend and generator can be swapped without retraining. T-Search is built on Qwen3.6-35B-A3B and trained on adversarially filtered synthetic search tasks with round-sliced supervised fine-tuning followed by GSPO on a recall reward. Averaged over seven English and Russian benchmarks with gold evidence annotations, it reaches 56.0 Recall@10 with one rollout, 14.4 points above its base, and 61.3 with three fused rollouts, outperforming larger open models. We release the model, harness, live demo, and three benchmarks, including TRuST, the first native-Russian hard-search benchmark.
Read the full abstract

All authors Olga Tsymboi, Ramil Latypov, Aleksandr Medvedev, Danil Taranets, Dmitrii Stoianov, Nikita Gulyakov, Gleb Alektorov, Anatolii Potapov

Quantum Physics

Pretty good shadow tomography

We give a shadow tomography algorithm that uses $O(\log(m) \log(m/\delta) / \varepsilon^2)$ copies of the input state. Specifically, given a quantum state $\rho$ and observables $O_1,\ldots,O_m$, the algorithm outputs estimates of $\mathrm{tr}(O_i\rho)$ for all $i\in[m]$ that are all accurate to within $\pm\varepsilon$, except with probability at most $\delta$. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on $O(\log(m)/\varepsilon^2)$ copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining $\log(m)$ factor separating the complexity of the quantum problem from its classical counterpart.
Read the full abstract

All authors Sabee Grewal, Angelos Pelecanos, Jack Spilecki, Ewin Tang, John Wright

Solar and Stellar Astrophysics

Production of White Dwarf Debris Disks from Planetary Collisions and Poynting-Robertson Drag

This paper explores the production of debris disks around white dwarfs, which are observed to experience frequent pollution events. In this scenario, planetary collisions occur just outside the surface of a highly evolved AGB star, after the end of its mass loss phase, as it starts its transition into a white dwarf. The collisions vaporize a fraction of the planetary material, which subsequently expands, cools, nucleates droplets, and condenses into rocky bodies with characteristic size of order $s\sim1$ cm. The rocky debris disk evolves through the action of Poynting-Robertson drag, driven by the stellar luminosity, which is initially large but steadily decreases with time. This scenario provides an alternate channel for delivering rocky material to the immediate vicinity of a white dwarf.
Read the full abstract

Quantum Physics

Informed Trading model with quantum walks

The seminal Kyle model offers a framework to understand the price impact of an informed trader in a market model for a single asset. We study variants in which the asset's future value is modeled by a classical random walk and by a continuous-time quantum walk, respectively. With these assumptions, we analytically approximate and numerically identify the market equilibrium between risk-neutral market maker and informed trader. In the classical equilibrium, the informed trader possesses a linear strategy, whereas the market maker's pricing rule resembles a logistic curve. The informed trader's profit is also identified to grow sub-linearly with time t. In the quantum equilibrium, the informed trader's strategy forms multiple clusters and the pricing rule exhibits multiple jumps correspondingly. Despite the increasing non-linearity of the equilibrium, the informed trader's profit grows linearly with time t.
Read the full abstract

Computation and Language

IdeaLens: Detecting AI Ideas in Long-form Writing

While modern AI detectors identify who wrote the words, emerging policies on AI use increasingly hinge on a different question: who came up with the ideas? We introduce IdeaLens, a detector that identifies whether a document's ideas came from a human or AI (idea provenance), regardless of who wrote its words. To focus IdeaLens on ideas rather than prose, we represent documents as outlines: lists of items that each pair a discourse role with a brief, paraphrased description of the content, minimizing word-level overlap with the raw text. We train IdeaLens on 1M FineWeb documents with silver labels from Pangram, a prose provenance detector. Since the outlines are largely stripped of surface-level information, the labels must be fit mainly through the ideas. In a controlled study, IdeaLens's AI flag rate drops from 95% to 7% as models write from increasingly detailed human plans, while Pangram 4 still flags 92%; from AI-derived plans, IdeaLens stays above 96%. Conversely, on a new dataset of 50 stories that human authors wrote from AI-generated plans, IdeaLens flags 68% of the stories as AI, compared to 8% for Pangram 4. On a comprehensive suite of 19 existing detection benchmarks, we show that IdeaLens maintains strong detection rates at low false positive rates, suggesting that ideas themselves provide a powerful discriminative signal, and its performance holds across domains, formats, and languages. Finally, we examine 90K predictions from IdeaLens to characterize systematic differences between human and AI ideation. We release our models and labeled datasets to facilitate future research on idea provenance detection.
Read the full abstract

All authors Rishanth Rajendhran, Minjoon Choi, Jenna Russell, Ramya Namuduri, Deniz Bölöni-Turgut, Marzena Karpinska, John Wieting, Mohit Iyyer

Multiagent Systems

On Learning Optimal Corners in Orthogonal Partially Observable Cooperative Guard Art Galleries

The CADENCE algorithm solves the Partially Observable Cooperative Guard Art Gallery Problem (POCGAGP) with formal coverage and connectivity guarantees, but leaves unspecified which valid corner each agent should be deployed to, a choice that strongly affects efficiency. We introduce two learned corner-selection heuristics that preserve these guarantees: a CNN scoring candidates on a grid encoding, and a GATv2 network trained with Deep Q-Learning (DQN) on a visibility graph. Across 7,500 runs on random orthogonal environments (50x50 to 250x250), our heuristics outperform baseline CADENCE in both steps to full coverage and peak agent count, with gains growing with scale, and improve on Incremental Self-Deployment (ISDA) baselines in agent utilization while providing guarantees ISDA lacks. Learned corner selection thus improves CADENCE in speed and agent utilization at no cost to its formal properties.
Read the full abstract

General Relativity and Quantum Cosmology

Puncture Evolution with Physics-Informed Neural Networks

We investigate the application of physics-informed neural networks (PINNs) to solve the vacuum Einstein equations in spherical symmetry. Our neural network architecture is designed to solve the 1+1D moving-puncture evolution, by minimizing a loss that combines a data term, the Ricci tensor of the reconstructed spacetime, and the moving-puncture gauge conditions. It represents the lapse, the shift and the Z4c conformal variables $\chi$ and $\widetilde{\gamma}_{rr}$, which remain regular at the puncture. We consider the evolution of a single, non-spinning black-hole in the puncture gauge and show that PINNs can interpolate numerical relativity (NR) data, predict its evolution, and reconstruct spacetime in regions where no data is provided. As an interpolant, the network provides a compact, differentiable representation of the NR data. Given only early-time and outer-boundary data, it evolves the puncture forward in time and reproduces the main features of the NR solution. Given only exterior data and no gauge condition, an ill-posed inverse problem, it recovers the interior of a Schwarzschild spacetime in coordinates of its own choosing, which we verify by learning the coordinate transformation to the Kerr–Schild form. Finally, we assess the strengths and limitations of PINNs for NR and outline their prospects for future applications.
Read the full abstract

All authors Estuti Shukla, Ashwin Suriyanarayanan, David Radice, Romit Maulik, Sebastiano Bernuzzi

Quantum Physics

Engineering logical gates with irrep surface codes

Fault-tolerant quantum computation can incur a substantial resource cost when a desired logical operation must be constructed from a restricted set of logical primitives. To make such operations directly available, we introduce irrep surface codes (ISCs), two-dimensional topological quantum error-correcting codes engineered to transversally implement a prescribed set of logical gates. The target logical gates only need to satisfy two conditions: (i) they generate a finite group, which, up to global phases, is forced by the Eastin-Knill theorem, and (ii) they are irreducible, meaning that any operator commuting with the set of gates must be proportional to the identity. This accommodates arbitrary finite groups of diagonal gates and arbitrary reversible classical gates, since each can be embedded into a larger irreducible finite group of gates. It also enables logical gates outside every finite level of the Clifford hierarchy. To incorporate these operations into surface-code computations, we further develop lattice-surgery protocols to transfer the encoded information between surface codes and ISCs obeying one of two sufficient conditions. Together, these results establish a systematic method for tailoring topological codes to desired logical operations and integrating them into conventional computations.
Read the full abstract

All authors Yabo Li, Zijian Song, Vieri Mattei, Naren Manjunath, Apoorv Tiwari, Tyler D. Ellison

Statistics Applications

How Low Can You Go? Validating Administrative Union Records for Substate Estimates of US Union Membership

Unions are important economic and political actors at the local level, but the primary source on US union membership, the Current Population Survey (CPS), is unreliable below the state level. Researchers have therefore turned to union-reported membership in federal "LM" filings, geolocating unions and aggregating their reported membership to estimate union density for counties, commuting zones, and congressional districts. We ask whether this practice is sound. We develop and defend multilevel regression with poststratification (MrP) on the CPS as a benchmark, then validate LM-based estimates against it from the state level down. LM, CPS, and MrP are highly correlated at the state level, but this correlation is roughly halved at the congressional-district, commuting-zone, and county levels. The breakdown is driven in part by reporting "lumpiness," which produces improbable values, including union densities exceeding 100%. Missing public sector union members explains only a small part of this divergence. These issues are substantively consequential: in a standard commuting-zone "China shock" regression, swapping density measures changes the import-exposure coefficient enough to alter its magnitude, significance, and sign. We conclude that LM records remain a rich resource for studying unions as organizations, but aggregating LM-reported membership is not a reliable way to measure union density at fine geographic resolution.
Read the full abstract

Game Theory

The Hardness of Dominant Strategy Mechanism Design, Revisited

We study the communication complexity of dominant-strategy incentive-compatible (DSIC) mechanisms for combinatorial auctions. For $\gamma \in [\log m, m]$, let $\mathsf{DSIC_{GEN}}(m, \gamma)$, $\mathsf{DSIC_{XOS}}(m, \gamma)$, and $\mathsf{DSIC_{GS}}(m, \gamma)$ denote the best approximation ratio attainable by a deterministic, individually rational, no-negative-transfers, DSIC mechanism using at most $2^\gamma$ communication over $m$ items, for general monotone, XOS, and gross substitutes (GS) valuations, respectively. We give a unified proof that shows $\mathsf{DSIC_{GEN}}(m, \gamma) = \Omega(m/\gamma)$, $\mathsf{DSIC_{XOS}}(m, \gamma) = \Omega((m/\gamma)^{1/5})$, and $\mathsf{DSIC_{GS}}(m, \gamma) = \Omega((m/\gamma)^{1/7})$. The GS lower bound answers an open question of~\cite{DobzinskiRV22}: although poly-communication welfare maximization for GS valuations admits a poly-communication deterministic truthful mechanism via VCG, no good approximation is possible in poly-communication for deterministic DSIC mechanisms. Additionally, the general lower bound establishes that $\mathsf{DSIC_{GEN}}(m, \gamma) = \Theta(m/\gamma)$ due to the deterministic DSIC $O(m/\gamma)$-approximation of~\cite{QiuW24}. We also obtain several results in the two-bidder setting. We show that attaining a $1.0001$-approximation for two weighted matroid-rank valuations (a subclass of GS) with a universally DSIC mechanism requires exponential communication. On the other hand, we give a poly-communication $(1+\sqrt{5})/2 \approx 1.618$-approximation for two submodular bidders using a universally DSIC mechanism. Prior to this work, it was not known whether even a poly-communication universally truthful mechanism could beat a $2$-approximation for two submodular valuations, nor whether a poly-communication universally DSIC mechanism could beat a $2$-approximation for two weighted matroid rank valuations.
Read the full abstract

High Energy Physics (Theory)

de Sitter Wavefunction from Quadrangular Polylogarithms: Polygon Graphs

We present an explicit formula for the $n$-gon graph contribution to the integrand of the cosmological wavefunction for conformally coupled $\phi^3$ theory in de Sitter space. Our result relies on the fact that its symbol satisfies total compatibility with respect to the $B_{2n-1}$ cluster algebra. We introduce $B$-type quadrangular polylogarithms, constructed from centrally symmetric quadrangulations of a $4n$-gon, and show that the $n$-gon wavefunction coefficient is expressed by a natural weight-$n$ function of this class. We prove our formula by directly relating the recursive differential equation satisfied by these wavefunction coefficients to a recursive coproduct formula for $B$-type quadrangular polylogarithms, with the remaining additive constant fixed by the soft limit.
Read the full abstract

All authors Livia Ferro, Tomasz Lukowski, Shruti Paranjape, Lecheng Ren, Marcus Spradlin, Anastasia Volovich, He-Chen Weng, Yao-Qi Zhang

Operator Algebras

Quantum integrals (With an Appendix on the solution to Haagerup's weight problem)

We solve two long outstanding problems here. We first solve in ZFC a problem that the first author and Weaver posed ten years ago: a state on a von Neumann algebra is countably additive on orthogonal projections if and only if it is sequentially weak* continuous, equivalently, sequentially normal. Such states may be considered the quantum (countably additive) probability measures, or rather their extension to a noncommutative integral. The principal tools are known ideas from direct integral theory from the 1970s. Indeed we prove a disintegration theorem for states on products of sigma-finite von Neumann algebras. We give several applications. For example we give a new variant of Gleason theorem, extending countably additive probability measures on projections to sequentially weak* continuous states when the algebra has no type $I_2$ direct summand. We also establish normality and sequential normality criteria for weights, and give several other applications of our main result to weights. In forthcoming work we consider many applications to `quantum measure and integration theory', such as variants of Lebesgue's dominated convergence theorem for von Neumann algebras. The analytic tools and product-quotient construction developed here are used to prove in an Appendix by the first author that normality and sequential normality of arbitrary weights are determined by their restrictions to abelian von Neumann subalgebras, resolving Haagerup's Problem 1.11. (This may be moved to a companion paper.) That is, normality of weights is commutatively determined.
Read the full abstract

Numerical Analysis

Singular parameters and missing limits in neural PDE solvers

Neural solvers for partial differential equations (PDEs) can approach an accurate solution while their parameters grow without bound. In such cases, the limiting solution may have no finite representation in the chosen model, leaving the best loss unattained. Our analysis connects missing limits in deep neural tanh- networks to unbounded hidden parameters or increasingly redundant neurons. For a class of models built from translated kernels, we describe the missing functions and recover them by adding kernel derivatives to the model. This completion makes the best approximation attainable under standard assumptions. Numerical studies follow the associated parameter growth and explore how completion affects PDE optimization.
Read the full abstract

Quantum Physics

Fast convergence of propagation algorithms for open quantum systems

We establish general conditions for the rapid convergence of propagation algorithms for computing expectation values of local observables in quantum many-body systems, covering both spin and fermionic systems. Our results apply to evolutions that are sufficiently contractive, providing a general mechanism by which contractivity controls the growth generated by local interactions and enables efficient classical simulation. As a first application, we consider noisy time evolution generated by local Hamiltonians on arbitrary interaction graphs. We show that the dynamics can be efficiently simulated when the noise strength $\lambda$ is sufficiently large compared to the degree of the interaction graph. More generally, for systems with an interaction strength $u$, our bounds determine a time horizon $t_{\text{max}}$ as a function of the interaction strength $u$, the noise strength $\lambda$, and the interaction structure below which the algorithm is efficient. In the noiseless limit, $\lambda=0$, our analysis extends the efficiently simulable time scale from $\log(1/u)$ proved in Facelli, Fawzi, and Fawzi (2026) to $t_{\text{max}} \sim 1/u$ matching the recent improvement by Zhao, Marvian and Tong (2026). As a second application, we apply the same framework to the computation of local observables in Gibbs states of local Hamiltonians. We consider a pseudo-Lindbladian whose steady state is the Gibbs state and show that, at sufficiently high temperature, its propagation algorithm converges rapidly. In particular, for weakly-interacting systems with interaction strength $u$, our result applies up to inverse temperatures $\beta\sim\log(1/u)$.
Read the full abstract

All authors Giorgio Facelli, Hamza Fawzi, Omar Fawzi, Cambyse Rouzé, Sam Slezak, Daniel Stilck França

Quantum Physics

Complexity separations for optimal matchgate-Clifford synthesis

Clifford and matchgate circuits are canonical families of classically simulable quantum circuits. Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis. Its adjoint action is isomorphic to the group of unit-determinant signed permutations of $2n$ Majorana modes, and we study optimal exact synthesis in this group. That is, given a target unitary and a gate set, output an $n$-qubit circuit implementing the target using the fewest operations. We show that the complexity of this problem strongly depends on the gate set. In particular, we study gate sets consisting of Majorana braids with different connectivity graphs. For path and complete graphs, we prove that the problem is classically solvable in $\mathcal{O}\left(n^2\right)$ time, and we provide explicit gate-optimal compilers. In addition, we prove that when the connectivity graph is a tree, the decision version of the optimal synthesis problem becomes NP-complete. Finally, we benchmark our optimal compiler on chains of up to $n=80$ qubits against those of Qiskit and Tket, obtaining circuits with constant factor improvements $\times2.57$ and $\times2.28$ in the total number of gates, respectively.
Read the full abstract

Quantum Physics

Fermions and the Tsirelson Problem in Real Quantum Theory

In a previous work, we showed that real quantum theory (RQT) cannot be experimentally distinguished from ordinary quantum theory (QT). In this paper, we investigate whether this indistinguishability survives two natural extensions of the setting: allowing separated measurements to be represented by commuting rather than tensor-product observables, and imposing superselection rules, as in fermionic information theory. We show that it does in both cases. Our first result is a positive answer to the Tsirelson problem in RQT: commuting and tensor-product measurements generate the same finite-dimensional correlations. This is surprisingly not a trivial consequence of the standard complex proof, as it does not carry over to the reals. The proof obstruction becomes particularly relevant in the presence of superselection rules, which is why we first establish the equivalence in RQT before extending the framework to superselected RQT. Our second result is a local, real quantum formulation of superselected theories. We extend the RQT framework to accommodate a representation of superselection over the reals and show, in particular, that it admits a fermionic version whose predictions are experimentally indistinguishable from those of fermionic information theory. More generally, the construction extends to all superselected QTs.
Read the full abstract

Analysis of PDEs

Fractional Calderón problem with a potential

We prove that the knowledge of local Cauchy data for a fractional Schrödinger equation on a smooth closed and connected Riemannian manifold of dimension at least two determines the manifold, its metric, and a smooth complex- valued potential, up to an isometry fixing the observation set. The observation set may be any nonempty open subset and no further geometric assumptions are required. The proof uses functional calculus identities to recover the local action of the resolvent of the Laplace-Beltrami operator.
Read the full abstract

Artificial Intelligence

Conditional Rank Allocation for Taxonomy-Aware Medical Language Model Adaptation

Medical question answering spans specialties and clinical operations that may benefit from different adaptation directions. We propose ARBOR, a parameter-efficient method that selects rank-one components from a shared low-rank basis for each question. An additive gate combines question representations, specialty tags, operation tags, and their interaction; a learned coefficient scales the adapter residual. An illustrative separation under orthogonal, equiprobable subtasks shows how conditional selection can avoid an approximation floor faced by a fixed update with the same active rank. This result motivates the design without asserting a corresponding bound for medical corpora. On Qwen3-8B across CMB, CMExam, MedQA, and MedMCQA, five-seed experiments yield 69.69% mean accuracy across benchmarks, exceeding LoRA r16 and MoELoRA by 1.26 and 1.30 percentage points, respectively. The reported advantage over LoRA r16 increases from 0.08 to 1.94 points as training expands from one to seven specialties. Tag perturbations and atom masking support the usefulness of clinical routing, while atom clusters align with the supplied specialty labels (adjusted Rand index 0.62). Calibration, transfer, and measured costs further characterize the method. These findings support structured conditional adaptation for medical QA, while leaving clinical safety and broader deployment untested.
Read the full abstract

All authors Guangyuan Dong, Ziwei Hong, Xuehao Zhou, Zidong Yu, Bingchen Liu, Kehan Liu, Chuang Liu, Rong Fu, Yuchao Hou

Quantum Physics

Hypercontractivity and entropy decay for infinite-dimensional quantum Gibbs samplers

We derive rates of exponential relative-entropy decay for a broad class of infinite-dimensional quantum Gibbs samplers. A key technical ingredient is a perturbative stability theory for hypercontractive estimates and logarithmic Sobolev inequalities. For suitably chosen dissipative couplings, we obtain exponential entropy decay for full multimode Bose-Hubbard samplers with arbitrary hopping and repulsive density interactions. For harmonically confined quantum Coulomb gases and molecular systems, we prove exponential entropy decay for every fixed finite-rank low-energy truncation of the interaction. Finally, we exhibit a periodic charging model with a positive spectral gap but no finite-time $L^2$-to-$L^p$ bound for any $p>2$.
Read the full abstract

Strongly Correlated Electrons

Unraveling Fermi liquid charge and heat transport in RuO$_{2}$

RuO$_2$ is a multi-orbital Fermi liquid for which an array of complementary experimental measurements has recently become available, making it a stringent testbed for quantitative many-body electronic structure theory. Using realistic dynamical mean-field calculations, we compute the spectroscopic and transport properties of RuO$_2$ in the paramagnetic state. We identify RuO$_2$ as a moderately correlated Fermi liquid and obtain (semi-)quantitative agreement with experiment for its optical conductivity, electrical resistivity, and thermopower. This broad agreement across complementary observables establishes a “precision” many-body description of RuO$_2$ and allows remaining discrepancies to be identified as meaningful tests of the theory. In particular, the calculated electronic thermal resistivity significantly undershoots the experimentally inferred low-temperature thermal resistivity, raising an important puzzle concerning the relative relaxation of charge and heat currents in the Fermi liquid regime. We explore low-temperature electron-phonon scattering as a possible mechanism for resolving this discrepancy, while a fully quantitative description remains an open problem. More broadly, our results demonstrate the power of combining precision DFT+DMFT calculations with complementary experimental probes to build and critically test quantitative descriptions of correlated quantum materials.
Read the full abstract

All authors Harrison LaBollita, Fabian B. Kugler, Antoine Georges, Cyrus E. Dreyer

Graphics

Real-time Rendering of Pre-integrated Neural Emitters

Direct illumination from non-trivial emitters with occluding housing, high-polygon emissive meshes, spatially varying emission, or deformable assemblies is a persistent bottleneck in real-time rendering. Current real-time solutions either rely on simplified analytical representations or fall back to runtime sampling. Analytical methods are restricted to simple emitter geometry, pure sampling-based estimators need high sampling budgets to be noise-free, and proxy representations still require runtime integration over outgoing radiance around the emitter. We present Neural Emission Fields (NEF), a representation that eliminates runtime integration by precomputing the illumination in the volume around the emitter. This neural field is parameterized by position, normal, view direction, and material parameters. Using a two-headed diffuse/glossy architecture, it yields noise-free unoccluded direct illumination from a single network evaluation per shading point. Because training is performed in the emitter's local frame, a trained NEF acts as a portable lighting asset reusable across scenes under rigid transforms. Internal interreflections, self-occlusion, spatially varying emission, and deformations are absorbed into the learned representation at zero additional runtime cost.
Read the full abstract

All authors Arno Coomans, Floor Verhoeven, Edoardo A. Dominici, Markus Steinberger

Operator Algebras

Ranks of operators and pureness of C*-algebras

For simple, nonelementary C*-algebras, we show uniform density of functions realized as ranks of operators. It follows that strict comparison by traces forces almost divisibility, and hence pureness. As an application, we show that strict comparison implies $\mathcal{Z}$-stability for separable, simple, nonelementary C*-algebras with locally finite nuclear dimension. In particular, the Toms–Winter conjecture holds for approximately subhomogeneous C*-algebras. More generally, we obtain uniform density of ranks for C*-algebras with the Global Glimm Property. Consequently, an exact C*-algebra is pure if and only if it has strict comparison together with the Global Glimm Property.
Read the full abstract

Quantum Physics

A classical oracle separation between QMA and QMA(2)

We exhibit a classical oracle relative to which QMA \neq QMA(2). The separation is based on a separable Hamiltonian problem defined by signed edge constraints on a graph. The YES instances have zero-energy product states, while the NO instances, constructed using the antisymmetric subspace, have entangled zero-energy states but no low-energy product states. For the QMA lower bound, we use compressed-oracle techniques to track the information learned by a quantum computation making few queries to a YES instance. The key step is to map the resulting superpositions of partial oracle records to the NO family without significantly changing the verifier's behavior.
Read the full abstract