Papers

Quantum information complexity (QIC), introduced by Touchette [Touchette, STOC 2015], has been shown to be one of the most powerful methods for proving quantum communication complexity and has also been shown to be equal to amortized quantum communication complexity. Unfortunately, QIC is generally hard to analyze because it is a sum of quantum conditional mutual information terms, which are difficult to estimate. In this work, we introduce a new variational approach, the information potential, for analyzing QIC and proving quantum communication lower bounds inspired by the resolvent representation for quantum relative entropy. This approach connects the QIC of individual messages to a quadratic form, making it more amenable and thus enables us to bound the cumulative positive increments of the potential throughout an interactive quantum protocol by its QIC. Lower bounds on the growth of the potential therefore translate into lower bounds on both QIC and quantum communication complexity. As an application, we give an optimal $\Omega(1/r)$ lower bound on the QIC of the two-bit $\mathsf{AND}$ function as well as an optimal $\Omega(n/r)$ lower bound on the quantum communication complexity of $r$-round Set-Disjointness, answering an open problem in~[Braverman, Garg, Ko, Mao, Touchette FOCS 2015]. Moreover, we further prove a direct-sum theorem for bounded-round quantum communication complexity of Set Disjointness. With the tight bound on the QIC of $\mathsf{AND}$ function, we further establish a nearly tight tradeoff for the asymmetric quantum communication complexity of $\mathsf{Set} \mathsf{Disjointness}$: $(q_A+1)(q_B+1)=\Omega(n)$, where $q_A$ and $q_B$ denote the total numbers of qubits sent by Alice and Bob, respectively.

A recent work studied quantum two-prover one-round proof systems $\mathsf{MIP}^{\psi}[\text{poly},O(1)]$. It showed that when $\psi$ is a noisy EPR state with quantum maximal correlation $\rho_{\max}(\psi)<1$, the resulting complexity class is equivalent to $\mathsf{NEXP}=\mathsf{MIP}$. In contrast, $\mathsf{MIP}^{\text{EPR}}[\text{poly},O(1)]=\mathsf{RE}$. Not all noise, however, decreases quantum maximal correlation. A basic example is dephasing noise: a dephased EPR pair retain quantum maximal correlation $1$. In this work, we remove the constant-answer restriction and establish a complete dichotomy for $\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]$, where the provers share arbitrarily many copies of EPR pairs subject to unital noise. Equivalently, let $\psi$ be a fixed two-qubit state with maximally mixed marginals. We prove that \[\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]=\mathsf{MIP} =\mathsf{NEXP},~\text{if $\psi$ is separable or $\rho_{\max}(\psi)<1$};\]\[\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]=\mathsf{MIP}^{\psi}[\text{poly},O(1)]=\mathsf{RE},\text{if $\psi$ is entangled and $\rho_{\max}(\psi)=1$.}\] Beyond the complexity classification, our proof develops two techniques that may be useful more broadly in quantum information and quantum complexity. First, we introduce a positivity-preserving low-degree approximation framework for quantum measurements: instead of truncating positive operators directly in the Pauli basis, we approximate suitable square-root factorizations, simultaneously achieving low Pauli degree, positivity, and global control over an entire POVM. Second, we develop a new dimension-reduction method, called Pauli folding, for low-degree positive operators. Its key ingredient is an almost-multiplicativity theorem for randomized Pauli hashing, which allows noncommutative products, positivity, and normalization to survive compression with controlled error.

Quantum algorithms and quantum hardware are advancing towards a promising paradigm for scientific applications. However, translating domain-specific problems into executable hybrid quantum-classical workflows remains a significant barrier for application researchers due to the required expertise in quantum algorithms, nuances in quantum programming, and hardware-aware system integration. At the same time, AI and primarily LLM based agents are increasingly capable of interpreting natural-language intent, reasoning over complex workflows, and translating high-level objectives into executable code and building computational pipelines. In this work, we introduce SQD Agent, an LLM-based agentic framework that translates natural-language user intent into executable workflows for Quantum Chemistry applications where algorithms from the Sample-Based Quantum Diagonalization (SQD) family are used. By automating this translation, SQD Agent reduces the level of human expertise and configuration overhead required, thereby simplifying experimentation in hybrid quantum-classical settings for application researchers new to quantum. SQD Agent adopts a modular and extensible architecture that supports seamless integration of heterogeneous quantum backends, classical solvers, and workflow components, ensuring adaptability to rapidly evolving quantum ecosystems. The framework further incorporates interactive capabilities for on-demand profiling, bottleneck analysis, resource optimization, intelligent result caching, and convergence visualization. Key features include quantum chemistry experiments, error mitigation on real quantum hardware, together with analysis of candidate mitigation schemes in terms of their potential error-recovery behavior and computational budget, helping users understand their practical trade-offs and decide which strategies to explore in subsequent experiments.

Nonlinear transformations are important in quantum machine learning and other quantum numerical applications, which can be reduced to the implementation of element-wise polynomials through polynomial approximation. Existing works establish the feasibility of transformations and improve query or auxiliary-space efficiency, but circuit depth remains linear in scale with degree. In this work, we develop a resource-tunable quantum framework that decomposes a $(2^d-1)$-degree polynomial into $m$ lower-degree factors, with $m$ controlling the degree of parallelism. By varying $m$ from $1$ to $2^d-1$, the framework provides a trade-off among query complexity, additional gate complexity, ancilla count, and normalization, ranging from a binary-tree implementation to a $\mathcal{O}(n+d)$-depth construction with highly parallel oracle queries that match the query lower bound. The effects of polynomial approximation and implementation errors are further analyzed. We demonstrate the framework for nonlinear activation functions such as sigmoid and tanh, as well as pixel-wise image transformations.

In an adiabatic evolution, the wave function follows the path of ground states $|\Phi_0(s)\rangle$ of a Hamiltonian $H(s)$ as $s$ is tuned from $0$ to $1$. The geometry of this adiabatic path is described by quantities such as its length $L=\int_0^1 \|\partial_s |\Phi_0(s)\rangle\|\,ds$ and its total curvature $K$. This geometry affects the evolution time $T$. For instance, $T$ is at least of order $L/\Delta_*$, where $\Delta_*$ is the minimum energy gap over $s\in[0,1]$. The traditional approach gives $L=O(\Delta_*^{-1/2})$ and $K=O(\Delta_*^{-1})$, which are loose in many cases. We improve these bounds by using $\mu_<(\gamma)$, the width of the region in $s$ on which the gap is below $\gamma$. The gap profile is in width class $p$ when $\mu_<(\gamma)$ falls at least as fast as $\gamma^{1/p}$. A typical avoided crossing is in width class $p=1$, which gives $L=O(\sqrt{\log \Delta_*^{-1}})$ and $K=O(\log \Delta_*^{-1})$. A profile in width class $p>1$ gives power laws with exponents $(p-1)/(2p)$ for $L$ and $(p-1)/p$ for $K$. The width class also bounds the evolution time. At $p=1$ we have $T=O(\Delta_*^{-2})$ with a schedule that advances $s$ at a constant rate, and $T=O(\Delta_*^{-1})$ up to a polylogarithmic correction with a schedule that traverses the path at a constant geometric speed. The bounds on $L$ hold for any twice continuously differentiable $H(s)$, and the bounds on $K$ for affine $H(s)$. We also prove the tightness of scaling of $L$ in $\Delta_*$ for every integer $p\ge1$, and the scaling of $K$ at $p=1$. We demonstrate the bounds on the adiabatic Grover search, the XXZ spin chain, and molecular electronic Hamiltonians.

We give collective tomography protocols for quantum states and channels with known symmetries, using random purification and dilation to reduce learning to pure-state estimation. For states commuting with a compact-group representation with multiplicities $m_\lambda$, the optimal copy complexity is $\Theta((\sum_\lambda m_\lambda^2+\log\eta^{-1})/\varepsilon^2)$ for sufficiently small trace-distance error $\varepsilon$ and failure probability $\eta$ for the nontrivial case $\sum_\lambda m_\lambda^2>1$. For $G$-covariant channels with finite-dimensional unitary representations of a compact group $G$, parallel $\widetilde{O}(D_G/\varepsilon^2)$ queries achieve a diamond-distance error $\varepsilon $ at fixed success probability $2/3$, where $D_G$ counts the real parameters of covariant Choi operators before imposing trace preservation. For permutation-covariant channels on $k$ qudits of fixed local dimension $d$, at sufficiently small fixed error and fixed success probability $2/3$, we obtain the optimal query scalings $\Theta_d(k^{d^4-1})$ for diamond distance and $\Theta_d(k^{d^4-d^2})$ for Choi trace distance. Furthermore, we resolve an open problem in quantum tomography of constructing efficient quantum circuits that approximate the Hayashi measurement for optimal pure-state estimation. We encode states in the symmetric subspace into bosonic occupation modes, realize the measurement by heterodyne detection and normalization, and approximate this procedure on qubits using the quantum Hermite transform. Combined with our symmetry-compatible purification and dilation circuits, this yields query-optimal and gate-efficient learners of permutation-covariant states and channels with gate complexity $O_d(\mathrm{poly}(k,\varepsilon^{-1},\log\eta^{-1}))$.

Characterizing entanglement in quantum materials through experimentally accessible observables remains a central challenge. Quantum Fisher information associated with sums of one-site spin operators provides one route by linking entanglement to measurable magnetic response functions. Extending this approach to local composite observables requires new entanglement bounds. Here we establish a rigorous bound for the total nearest-neighbour vector chirality of periodic spin-$1/2$ chains with an even number of sites. The quantum Fisher information per spin cannot exceed $k+1$ for any $k$-producible state, so exceeding this bound certifies entanglement depth of at least $k+1$. Combining infinite density-matrix renormalization group and thermal pure quantum-state calculations, we demonstrate multipartite entanglement encoded in vector-chiral correlations at zero and finite temperatures in an extended $J_1$-$J_2$ XXZ chain. The spin-current coupling between vector chirality and electric polarization offers, in principle, access to this witness through dielectric loss spectroscopy in multiferroic magnets, extending entanglement diagnostics beyond dipolar spin correlations.

Position verification, introduced by Chandran et al. (SIAM J. Computing 2014), allows verifiers to test a prover's claimed position by an interactive protocol. Classical position verification is impossible. Even for Quantum Position Verification (QPV), there always exists an LOCC (Local Operations and Classical Communication) attack if the adversary can hold an exponentially large amount of preshared entanglement. Somewhat surprisingly, we show that we can circumvent this barrier in the idealized continuous-time model, where time is represented by a real-valued parameter and challenge messages can be sent at a time sampled uniformly from a real interval. In this model, we give a BB84-based protocol that remains secure against any finite coalition of LOCC adversaries with arbitrary finite (possibly exponential) quantum storage and entanglement. Our construction can also be instantiated in the discrete-time model. Even though the previous impossibility results apply, we are able to obtain an information-theoretic QPV protocol in which the honest parties' total resources (communication and storage) can be significantly smaller than the adversarial resource bound. In fact, we can achieve any desired polynomial gap between honest parties and adversarial resources. To our knowledge, all previous protocols in the literature required resources of the honest parties to be at least as large as the adversarial entanglement. Interestingly, the resource gap between the honest and adversarial party resources in our protocol depends on how precisely time can be measured. As the precision of the best-known clock improves with further research, the resource gap in our protocol keeps increasing. In particular, the adversarial resource bound keeps increasing while the honest parties' resources remain largely the same. We call this the "I sleep, you work" paradigm.

Random circuit sampling is a leading approach to demonstrating quantum computational advantage, but benchmarking noisy implementations through linear cross-entropy requires costly calculations of ideal output probabilities. We propose a metrological benchmark based on the response to controlled perturbations, characterized by quantum Fisher information (QFI). A relation between QFI and out-of-time-order correlators enables protocols with local or global control. For Haar-random circuits, the average QFI approaches its maximal value in the local protocol and grows linearly with the number of qubits under collective control. In contrast, Clifford circuits yield zero QFI despite extensive operator spreading, showing that the response probes dynamical properties beyond spreading alone. A butterfly protocol further uses system size to enhance sensitivity, yielding a mean inverse sensitivity proportional to the number of qubits with single-qubit readout. Its fluctuations distinguish the Haar and Clifford ensembles despite their identical mean responses. For noisy implementations, we derive an exact relation between the noisy and ideal QFI within a global white-noise model, providing a quantitative reference for the degradation of the benchmark. These protocols enable metrological benchmarking of noisy random quantum circuits without computing ideal output probabilities.

Radchenko and Wheeler (RW) recently proved a finite pentagon relation for real quadratic special values of the modular quantum dilogarithm and used it to establish the rank-$1$ twisted convolution identity conjectured by the current authors. RW gave an explicit argument in the principal case and remarked that their proof holds for all rank-$1$ admissible tuples. We extend their proof to all rank-$r$ admissible tuples and provide an explicit dictionary between the modular quantum dilogarithm and the Shintani-Faddeev modular cocycle conventions in the respective papers. Thus, we establish that, if $d,r$ are positive integers such that $r<\frac{d-1}{2}$ and $\frac{d^2-1}{r(d-r)} \in \mathbb{Z}$, then there exist ghost $r$-SICs: i.e., configurations of $d^2$ rank-$r$ subspaces in $\mathbb{C}^d$ that satisfy a non-Hermitian equichordal condition. Under the Stark conjecture, these configurations are Galois conjugate to Hermitian equichordal configurations called $r$-SICs (or rank-$r$ SIC-POVMs).

Gausslet orbitals on a cubic lattice, introduced in [Steven R. White, J. Chem. Phys. 147, 244102 (2017)], represent a localized, smooth, and systematically refineable basis set featuring a "diagonal" approximability of the electron repulsion integral tensor. The present work develops efficient algorithms for evaluating overlap integrals required for electronic-structure simulations using these Gausslets, specifically the kinetic, nuclear, and electron repulsion integrals (both with and without the diagonal approximation). Computational efficiency improvements rest on the exploitation of translation, permutation, and octahedral symmetries, a reordering and precomputation of nested sums, as well as an early truncation of small coefficients. Our algorithms reduce the number of electron repulsion integrals on a $5 \times 5 \times 5$ grid from $125^4 = 244140625$ to $138187$ due to symmetries, and achieve a wall-clock runtime for evaluating the remaining integrals with a truncation tolerance of $10^{-5}$ in under 1 second on a laptop computer. We apply the developed methodology to compute the ground state of the hydrogen atom and molecule as a demonstration.

Fingerprint recognition is a widely deployed biometric, but supervised training requires large labeled enrollment sets. Self-supervised learning (SSL) removes this requirement, and hybrid quantum-classical models have been proposed to enrich the learned representations. Prior quantum SSL studies consider a single contrastive objective, so it is unclear whether reported benefits depend on the objective or can be attributed to the quantum circuit. We insert the QuFeX quantum feature-extraction module into three SSL frameworks, the contrastive SimCLR and MoCo v2 and the non-contrastive BYOL, and compare each hybrid with its classical counterpart at matched representation width (8 features, equal to 8 qubits) on the SOCOFing fingerprint dataset, with a CIFAR-10 control, using k-nearest-neighbor identification on encoder features. In single-run experiments the hybrid scores clearly higher for both contrastive objectives, whereas for BYOL a multi-seed analysis shows no reliable difference, suggesting that any benefit depends on the SSL objective. A hardware-efficient circuit (QNet) does not show the same gain. We examine whether the gains can be attributed to the quantum circuit, considering circuit architecture, trainable parameter count, nonlinearity, and the classical simulability of 8-qubit circuits.

Nonlinear partial differential equations (PDEs) underpin computational fluid dynamics, yet resolving nonlinear transport on fine grids remains computationally demanding. Quantum linear-evolution algorithms offer a possible route to large-scale simulation but cannot directly propagate nonlinear coupling. Here we develop a Frozen–Oseen quantum homotopy method (FOQHAM) framework that links transport-aware auxiliary-operator selection to the size of the resulting linear representation. We freeze the full Fréchet derivative at a prescribed flow profile, retaining transport and profile-gradient coupling and close each prescribed finite-order homotopy hierarchy as a fixed affine linear system by product lifting. We formulate its propagation through Linear Combinations of Hamiltonian Simulations (LCHS), without outer homotopy iterations or profile updates. For spatially semidiscrete equations, we establish local approximation bounds and exact closure of the finite-order hierarchy. Classical tests on Burgers, Korteweg–de Vries, Zakharov–Kuznetsov, and one- and two-dimensional isothermal compressible Navier–Stokes equations provide numerical evidence of accurate non-iterative approximations in the tested regimes. The framework thus connects nonlinear PDE approximation to quantum linear evolution and offers a conditional path toward quantum acceleration.

We characterize bound entanglement in bipartite qutrit systems by combining the Positive Partial Transpose (PPT) criterion with a structural, non-completely positive map. Focusing on a comprehensive three-parameter bipartite qutrit family $\rho_{a,b,c}$, we present an exact analytical and geometric partitioning of the physical state space simplex. We derive the closed-form quadratic boundary governing the leaf-like PPT region $(a^2+ab+b^2-b \leq 0)$ over the domain $0 < a \leq \frac{1}{3}$, and identify the exact linear threshold $(a > c)$ that characterizes the PPT bound entangled sub-region. This family strictly generalizes the well-known Horodecki bound entangled states, which appear as a single slice of the three-dimensional leaf. Applying the structural map to this decomposition, we show that it certifies bound entanglement throughout the entire threshold region, accounting for $14.76\%$ of the total PPT leaf area.

Consider two orthonormal bases of a bipartite Hilbert space such that states in one basis are weakly entangled and states in the other are strongly entangled. We establish a quantitative version of the following uncertainty principle: every state that is localized in one basis must be delocalized in the other. More specifically, we lower bound the sum of the Shannon entropies of any state's coefficient distributions in the two bases by the difference between the entanglement Rényi entropies of their basis states. The result follows from new lower and upper bounds on the entanglement of superpositions that may be of independent interest. As an application, our result limits the power of weakly-entangled states in representing ground states of Hamiltonians with strongly-entangled energy eigenstates. We illustrate this application numerically for the Sachdev-Ye-Kitaev model.

Faulty syndrome measurements can corrupt an otherwise correct quantum-error correction step. Bivariate bicycle (BB) codes contain dependent stabilizer checks, so every valid syndrome obeys additional parity constraints, or metachecks. We study how far this built-in redundancy can identify measurement faults and when the remaining ambiguity is unavoidable, while separately checking the code's logical structure. A logical decomposition is used as a preliminary safety check: it identifies a $k/2$-dimensional annihilator subspace and a $k/2$-dimensional colon quotient, and the minimum-weight logical need not be visible from the annihilator side alone. On the measurement side, translation symmetry partitions syndrome locations into classes that carry identical metacheck information. This gives an exact characterization of the leading single-fault ambiguity, a bound on how many fault locations can be distinguished, and a family-level repair limit when the encoded dimension stays bounded while the block length grows. Under a static-data assumption, the same calculation gives the minimum number of checks that must be remeasured to remove every single-fault ambiguity. Exact finite-code calculations illustrate both regimes: all single measurement faults are distinguishable in a 72-qubit BB code, whereas the 144-qubit Gross code merges its 72 syndrome locations into 36 indistinguishable pairs. In a 108-qubit example, one logical component first appears at weight 12 while the other contains a weight-10 logical. Sustained phenomenological experiments show that joint data–measurement decoding is more robust than a separated repair stage on the more ambiguous codes. The resulting tests apply to general two-block BB codes, including non-coprime periods and repeated-root cases.

Toroidal discrete Wigner functions (DWFs) for finite-dimensional systems are non-unique. We completely parameterize and topologically classify the labeled single-qudit ${d\times d}$ representations whose phase-point operators are Hermitian, unit-trace, Hilbert–Schmidt orthogonal, and Weyl–Heisenberg covariant, determining the independent parameter freedom in every dimension. Our previously established stencil theorem expresses this family as descents of a doubled ${2d\times2d}$ parent Wigner representation. Here, we solve its projected-stencil admissibility conditions explicitly to obtain the full parameter space of this family. In the symplectic-Fourier representation, admissibility fixes the modulus, leaving phase data on a ${d\times d}$ base cell satisfying a parity-dependent twisted-oddness relation. This gives the parameter space ${(S^1)^{(d^2-1)/2}}$ for odd ${d}$ and ${(S^1)^{(d^2-4)/2}\times\mathbb{Z}_{2}^{3}}$ for even ${d}$. Canonical horizontal and vertical marginals reduce these spaces to ${(S^1)^{(d-1)^2/2}}$ and ${(S^1)^{d\,(d-2)/2}\times\mathbb{Z}_{2}}$, respectively. The same phase data parameterize validity-preserving rephasings of the doubled Weyl–Heisenberg displacement operators. Requiring these operators to have order dividing the Hilbert-space dimension ${d}$ replaces each ${S^1}$ factor by a discrete ${\mathbb{Z}_{d}}$ factor. The associated symplectic-Fourier characteristic functions encode the same operator information, with pointwise magnitudes independent of the valid stencil convention and hence providing convention-independent information about the represented operator within this family. This classification separates the freedom intrinsic to DWF validity from that selected by marginal and displacement-algebra requirements and makes explicit the structural distinction between odd and even dimensions.

We study the problem of property testing quantum states: given a pure state $|\psi\rangle$ that either (A) belongs to some class $C$ of pure states, or (B) is $\varepsilon$-far in trace distance from all states in $C$, determine which is the case with high probability. It is known that there exists classes $C$ for which the sample complexity of property testing necessarily scales with the size of the system. In this work, we identify classes for which testing only requires a size-independent number of samples. We prove a tight sample complexity of $\Theta(1/\varepsilon^2)$ for the property testing of five important classes of Gaussian quantum states: 1) Fermionic Gaussian states, 2) Slater determinants, 3) bosonic Gaussian states, 4) zero-mean bosonic Gaussian states, and 5) bosonic coherent states. While property testers for some of these classes have been studied previously, those analyses only gave upper bounds scaling polynomially in the number of modes. In each case, our tester is the projection onto the “top” irrep of two or three copies. We get to constant sample complexity by lower bounding how quickly the rejection probability increases with distance from the class; the main technical component involves bounding the spectral gap of symmetric extension of the test projector. We then establish optimality by proving matching lower bounds based on binary state discrimination for each class. Our testers and optimality claims also extend to the tolerant setting, wherein $\psi$ may be $O(\varepsilon)$-close to $C$ in case (A), rather than lying exactly inside.

Compiling a continuous gate set to a discrete universal gate set generally incurs an overhead. A circuit composed of $G$ arbitrary one- and two-qubit gates can be $\epsilon$-approximated by a sequence of gates from $\{H,T,\mathrm{CNOT}\}$ by replacing each original gate by a sequence of $O(\log(G/\epsilon))$ elementary gates. We show that this overhead can be avoided using adaptivity for polynomial-sized circuits with inverse-polynomial target error, which is optimal.

Engineering dissipation has emerged as a powerful strategy for controlling quantum many-body dynamics, complementing purely coherent control for state preparation. However, finite-time driving across a quantum critical point generates nonadiabatic excitations and coherences, and existing dissipation-engineering approaches have largely characterized how a fixed environment modifies critical dynamics rather than actively steering a system toward a prescribed thermal trajectory. Here we develop a Markovian dissipative framework for finite-time thermal-state tracking based on engineered population currents with non-negative transition rates, and apply it to the transverse-field Ising model driven across its quantum critical point. Compared with unitary dynamics and a natural thermal bath, the engineered dynamics strongly suppresses thermal excitation deviations and provides additional control over coherence damping through a free common current $Q_k$, while exhibiting a substantially steeper residual scaling, $\delta n_{\mathrm{ex}}^{\mathrm{th}}\sim(v/v_{\mathrm{ch}})^2$, than the Kibble–Zurek behavior recovered for unitary evolution. These results point toward engineered dissipation as a route for controlling thermal-state preparation in driven quantum critical systems.

Nonlinear exceptional points (NEPs) were proposed to circumvent the noise–responsivity cancellation that limits linear exceptional-point sensors. At an NEP, the stationary frequency response can be singular while the Hamiltonian Petermann factor remains finite, suggesting a genuine signal-to-noise ratio (SNR) enhancement. Yet recent model-specific analyses of nonlinear fluctuations have reached conflicting conclusions. We prove that any singular stationary frequency response requires a fixed-point bifurcation of the nonlinear dynamics. In local fluctuation regimes, the singularities in responsivity and long-time frequency uncertainty are both set by the critical relaxation rate, leading to exact cancellation in the SNR and precluding any divergent enhancement. Furthermore, we derive a path-information bound that applies across both local and nonlinear fluctuation regimes and places a finite ceiling on the long-time SNR enhancement. Notably, this upper bound is attainable in the local fluctuation regime, implying that frequency readout under such parameter settings is information-optimal.

Broadening the study of quantum optimization algorithms from binary to $k$-element alphabets has been shown to open new avenues for potential quantum advantage. A quantum advantage claim for approximate optimization requires showing that, under the same assumptions, an efficient quantum algorithm provably achieves a better performance than can be proven for the best known efficient classical algorithms. We study local classical and quantum algorithms for Max-$k$-Cut on $d$-regular graphs of girth $g$. We advance classical algorithms for this problem by developing a local vector algorithm based on the explicit vector construction of Thompson, Parekh, and Marwaha (TPM). Our algorithm gives the best provable cut fraction guarantee among known efficient classical algorithms on regular graphs for $k\geq3$. To evaluate the performance of QAOA under identical assumptions of girth and regularity, we develop tensor network techniques for general $d$ and $k \geq 2$. In addition, using an equivalence to a coupled qudit–boson system, we compute the QAOA performance in the infinite-degree limit. Together, these techniques give provable guarantees on QAOA performance on large graphs. Despite the improvements we introduce to the classical algorithm, QAOA achieves a better cut fraction guarantee for depths $p\geq 9$, corresponding to girth $g\geq 20$, for both finite- and infinite-degree regimes. Thus, we obtain an apparent quantum advantage from applying QAOA to the Max-$k$-Cut problem.

The rapidly growing landscape of quantum error-correction (QEC) protocols has produced a wealth of numerical data, but comparatively few heuristics for understanding and predicting their performance. Here, we develop a simple entropy-based proxy that predicts the thresholds of a variety of QEC protocols, ranging from the code-capacity setting of Clifford-deformed surface codes with biased Pauli or erasure noise to the circuit-level noise model of the surface or color codes with flag qubits. Our proxy estimates the threshold by locally comparing the noise entropy with the error information gained via stabilizer measurements (or spacetime detectors and flag outcomes in the circuit-level settings). Despite neglecting correlations between stabilizer outcomes and the contribution from code degeneracy, the proxy captures the main trends across diverse settings and yields threshold estimates in good agreement with numerical results. Our work develops much-needed phenomenology that enables simple back-of-the-envelope estimates of QEC performance, recovering and providing an explanation for the results of computationally intensive detailed simulations.

Recent work by Wills constructed codes with constant rate and transversal $T$. Extending this line of work, we construct asymptotically good CSS codes with fully addressable transversal $T$, permitting selective control over which logical qubits receive a $T$ gate. We also give Pauli-LDPC codes with transversal $T$ and growing distance at vanishing rate; and a protected-subsystem construction with fully addressable transversal $T$, constant protected rate, distance $\Omega(\sqrt n)$, and sparse (non-Pauli) checks. More generally, we obtain asymptotically good binary codes with full transversal addressability for every fixed finite-order one-qubit gate, retaining CSS realizations for dyadic phase gates such as $\sqrt T$ and using generally nonadditive codes for rotations such as $R_z(\pi/7)$. The remaining challenge is to construct asymptotically good Pauli-LDPC codes with fully addressable transversal non-Clifford one-qubit gates.

Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn [CRYPTO 2024], are classical error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings. We initiate the study of quantum analogues of PRCs. We define quantum pseudorandom error-correcting codes (QPRCs). Assuming that Learning Parity with Noise (LPN) is hard for $2^{O(\sqrt{n})}$-time quantum algorithms, we construct QPRCs whose encodings are indistinguishable from Haar-random isometries. We call these pseudorandom isometric error-correcting codes (PRICs), and our construction is robust to all $o(n \frac{\log \log n}{\log n})$-local quantum noise, where $n$ is the number of physical qubits. Under the same assumption, we also construct QPRCs whose encodings are indistinguishable from the completely depolarizing channel and that are robust to all $\alpha n$-local quantum noise for some constant $\alpha>0$. The latter QPRCs give a direct quantum analogue of classical PRCs. To construct PRICs, we develop two technical ingredients of independent interest. First, we introduce a new classical cryptographic primitive which we call pseudorandom functional error-correcting codes (PRFCs) and construct them under the same LPN assumption. Second, we develop a new efficient decoding procedure within the codeword-stabilized (CWS) framework introduced in [Cross, Smith, Smolin, and Zeng, IEEE ISIT 2008], which is a generic framework for constructing quantum error-correcting codes by combining (possibly nonlinear) classical error-correcting codes and graphs. This resolves the open problem of finding a general method for efficiently decoding such CWS codes based on nonlinear classical codes, raised in [Li, Dumer, Grassl, and Pryadko, Physical Review A 2010].

It is well-known that thermalization breaks down in presence of an extensive number of symmetries or conservation laws that are mutually compatible or commuting with each other. We ask here how an extensive number of mutually incompatible local symmetries govern eigenstate thermalization (ETH). We will investigate this through models within the class of bond-dependent $\mathbb{Z}_2$-symmetric quantum spin-$\frac{1}{2}$ Hamiltonians that naturally admit this structure. This leads to exponentially large degeneracies in the spectrum governed by the incompatible symmetry structure. Here, using spectral diagnostics, we show that non-integrability can survive despite extensively many conserved quantities when they are incompatible. Furthermore, we show that ETH behavior persists deep into the many-body spectral edge due to this structure. In other words, incompatible local symmetries enable a mechanism to obtain enough thermodynamic entropy at low excitation energy densities to make ETH operational or predictive near the ground state.

The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in $\mathsf{NP}$ for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\mathsf{QMA}$-complete. CLH is complete for the complexity class $\mathsf{QIMA}$, defined through quantum verifiers whose local gates commute. Therefore, CLH is $\mathsf{QMA}$-complete if and only if $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.

The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate (the ratio of min-entropy to bitlength) is ~ 1. However, existing protocols for certified randomness either produce weakly random strings with rate o(1), or they require a trusted random seed. We show how to certify randomness with the optimal rate ~ 1 without requiring any trusted randomness from the verifier. Our protocol is secure unconditionally in the quantum random oracle model (QROM). This improves the result of Coladangelo et al., who certified weakly random strings unconditionally in the QROM, and answers a question posed by Aaronson and Hung. We also define and construct a proof of conditional min-entropy, which certifies optimal min-entropy even conditioned on an adversarially chosen transcript. We show an application of this primitive to randomness beacons, where each pulse should have high min-entropy conditioned on all previous messages.

We numerically investigate frequency-comb generation in an electrically pumped vertical-cavity surface-emitting laser coupled to two mechanical modes of a suspended mirror. Displacement-dependent cavity loss and radiation-pressure feedback couple the mechanical motion to the carrier and photon densities, producing harmonics and combination-frequency components in the photon-density spectrum. Mechanical quality factors primarily control the intensity of comb lines, whereas resonance frequencies determine their spectral distribution. The initial mechanical amplitudes influence the threshold current and relative spectral intensities, with the simultaneous excitation of both modes yielding a broader set of observable components. These results establish the dependence of the calculated comb structure on mechanical dissipation, resonance frequencies, and initial conditions in an active optomechanical cavity.

We introduce a quantum-echo Markov process for combinatorial optimization. Quantum dynamics based on quantum annealing (QA) or the quantum approximate optimization algorithm (QAOA) is used to engineer the transition kernel. Increasing the annealing time in QA or the number of layers in QAOA enables transitions to explore distant configurations while suppressing large energy changes. The Hamming-space delocalization originates from operator spreading, whereas the energy-space localization arises from a dynamically generated correlation. For optimization, we propose quantum-echo local optimization with and without greedy descent. We find that its performance is governed by the interplay between Hamming-space nonlocality and energy-space locality, and that excessive energy-space localization can degrade optimization performance. Incorporating greedy descent substantially improves the performance, highlighting the complementary roles of quantum dynamics for exploration and greedy descent for exploitation. These results establish quantum-echo dynamics as a framework for engineering structured transition kernels and provide a route to using finite-resource quantum many-body dynamics as a computational primitive for iterative optimization.