Abstract An established exponential Bernoulli race samples exact softmax labels from residual quantum overlaps under an ideal independent-measurement model. We derive its early-stopped shot cost and prove that nested classical projections monotonically reduce expected costs and computable bounds. A first-proposal coupling gives an unbiased value estimator, with a coefficient computed from score envelopes that guarantees no variance increase over ordinary averaging. Tests use 192 pretrained-model attention rows with contexts up to 512 tokens. Retaining 32 of 64 coordinates reduces the primary median expected shots per label from 1.72 × 10 5 to 2.81. No hardware speedup is established.
Abstract An established exponential Bernoulli race samples exact softmax labels from residual quantum overlaps under an ideal independent-measurement model. We derive its early-stopped shot cost and prove that nested classical projections monotonically reduce expected costs and computable bounds. A first-proposal coupling gives an unbiased value estimator, with a coefficient computed from score envelopes that guarantees no variance increase over ordinary averaging. Tests use 192 pretrained-model attention rows with contexts up to 512 tokens. Retaining 32 of 64 coordinates reduces the primary median expected shots per label from 1.72 × 10 5 to 2.81. No hardware speedup is established.
The attention mechanism forms the foundation of many modern AI models such as the Transformer. In one subclass of problems where attention is used, inputs and outputs are bound to the probability simplex so that all outputs sum to one. In this setting, softmax attention admits an exact, component-by-component quantum realization. Attention scores are Hadamard-test statistics on block-encoded projections of amplitude-encoded inputs. The exponential softmax is the interior of a cosine-squared family generated by Born-rule measurement under an exact bijection, whose boundary expresses sparse attention with exact zeros at finite parameter values. The softmax temperature is a repetition count where post-selected measurement rounds realize discretized inverse temperature exactly. Value aggregation is a deterministic column-loading channel that dilates the column-stochastic value matrix. The gated residual is the preparation angle of a single ancilla, with the additive identity at a mixing angle of π/2. Every learnable parameter is a rotation-gate angle. The composed layer is exact in the infinite-shot limit with one measure-and-reload step per attention score; a fully-coherent variant is ε-approximate via quantum singular value transformation in the infinite depth limit. The algebraic core is machine-checked in Lean 4.
Quantum kernel estimation on near-term hardware is shot-budgeted: every entry of the kernel Gram matrix is a Bernoulli expectation that must be sampled with a finite number of circuit executions. Recent work on quantum kernel classification has shown that allocating shots non-uniformly across kernel entries, weighted by their downstream task sensitivity, can reduce the shot budget required to reach a target accuracy. We extend this idea to Gaussian process (GP) regression, a setting whose downstream quantities (full-spectrum posterior variance, log-determinant, marginal likelihood) couple to kernel error more tightly than the sign-only outputs of classification. We derive three closed-form pair-level sensitivities predictive coupling ∣αiαj∣, leave-one-out residual, and marginal-likelihood gradient and plug them into a Neyman-style minimum-variance allocation rule. To prevent catastrophic over-concentration when the warm-up sensitivity estimate is itself noisy, we add a high uniform coverage floor justified by a Frobenius lower bound on the missing-entry perturbation. On four UCI benchmarks and two synthetic RBF + Bernoulli controlled studies, the resulting allocator delivers 10--21% test-RMSE improvement over uniform allocation across the moderate-budget regime. The gain transfers (i) to genuine ZZ and Pauli-Z quantum kernels on quantum-natural data (−13--15% at low budget, p<0.05 paired) and (ii) to four downstream tasks (Bayesian quadrature, heteroscedastic regression, hyperparameter learning, multi-output Cokriging). On UCI features embedded into a ZZ kernel the gain disappears, consistent with the exponential-concentration regime where shot allocation has nothing to exploit.
When does a noisy quantum sampler yield an end-to-end polynomial-time optimization algorithm with performance guarantees? Building on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA, we show that inverse-polynomial ideal probability on the optimal set, together with independent sampling, polynomial-time feasibility repair, and scoring, produces an exact-hit fully polynomial randomized approximation scheme, which we call an FPRASq.
This guarantee survives device noise within an instance-dependent window. For effective circuit depth linear in the product of layer count and problem size, preserving an inverse-depth fraction of the ideal optimal mass increases the required shot complexity by one power of the problem size. Beyond this window, deterministic repair guarantees feasibility and provides an instance-dependent approximation guarantee whenever the induced objective inflation is controlled.
The resulting NP-HQ algorithm fits the Chen-Cotler-Huang-Li oracle model. On any NP-hard kernel-admissible promise family, reproducing its inverse-polynomial optimal overlap with a polynomial-time classical sampler would imply that NP is contained in BPP, even with identical repair and perfect access to the constraint structure. Thus, the separation lies in generating the sampling distribution.
We further introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical post-processing cost by one power of the problem size. Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables and match or improve every tested QOptlib reference tour.
We consider the problem of learning expectation values of particle-preserving operators with respect to an unknown η-particle n-mode fermionic state via classical shadows. Our main application is to estimating overlaps with arbitrary Slater determinant states: While it is known that such overlaps can, in the average case, be learnt to a fixed additive precision with a constant number of samples, the best-known worst case bound is O(nlogn); here we improve this to O(ηlogη), achieving a mode-independent sample cost. Our procedure is also computationally efficient, requiring only classical post-processing which for a generic dense orbital runs in time O(nη2). For the task of estimating the expectation value of a general particle-preserving quadratic fermionic observable h, we prove a sample complexity bound of O(η∥h0∥22), where h0 is the traceless component of h; the associated classical post-processing scales as O(n2η). Finally, we discuss implementation of the required randomization: in a first-quantized encoding, approximate unitary designs give circuit depths polylogarithmic in the number of modes, contrasting with linear-depth requirements for nearest-neighbor second-quantized matchgate implementations. On the technical side, our proof reduces the extremal shadow variance to harmonic analysis on the AIII symmetric space U(n)/(U(η)×U(n−η)) and evaluates the resulting integral using techniques from the theories of Jacobi ensembles and orthogonal polynomials, in a calculation which may be of independent interest.
Softmax self-attention costs O(T^2) in the sequence length T because the exponential kernel has no finite-dimensional feature map, so linear-time variants approximate it. We observe that Born-rule attention, whose weights are quantum-measurement probabilities a_kj ∝ |<Q_k, K_j>|^2 over complex queries and keys, is an exact finite kernel with the rank-one density-matrix feature map ρ_x = x x†, since |<Q_k, K_j>|^2 = tr(ρ_Qk ρ_Kj). As the complex degree-two case of polynomial-kernel linear attention it admits an exact O(T d^2) causal recurrence and constant-state decoding (d^2 (d_v + 1) reals per head, with d_v the real value width, independent of T), and it keeps rotary positions exactly. For GPT-2's head geometry (64 real channels paired into d = 32 complex) the feature dimension is d^2 = 1024. Measured on an A100, compiled constant-state decoding runs from 6.4 MB per layer at 0.12 ms per token at any length, against a 3.2 GB FlashAttention-2 cache at 2.26 ms per token at 1M tokens; unfused prefill overtakes FlashAttention-2 between 64k and 128k tokens (11x at 1M), and a fused form (Triton feature lift plus a chunkwise linear-attention kernel) between 16k and 32k (4x at 128k), reaching training parity at 64k. The linear and quadratic forms are two implementations of one operator; whether that operator matches softmax is a separate modeling question, answered here only at small scale: the p = 1 operator bolted into a real-valued GPT trails softmax by 0.12 nats at context 1k and 0.77 at 16k (attention dilution; a decay kept exactly in the d^2 state restores the 0.12 gap at 16k, and p = 2 sharpening with decay recovers 74% of the 1k gap), whereas inside a fully complex residual stream it matches softmax at 1k and keeps a quarter of the real-stream gap at 4k; gated linear attention beats both there. At 128k context on PG-19 the variable that matters is forgetting: plain Born dilutes, Born with a fixed decay carried in its state is 0.32 nats ahead of softmax and within 0.04 of gated linear attention, which stays 1.8x faster. Streamed with their constant state over the PG-19 test partition in 5M-byte windows, two 4M-complex-parameter byte models of the source framework score 1.66 (linear Born with decay) and 1.70 (gated) bits per byte, where a 350M-parameter hierarchical Mamba–Transformer stack built for that window reports 2.45. Preprint, October 2026. Also submitted to arXiv (identifier to be added on announcement). Code: the CNet framework, https://github.com/crasmarum/CNet .
Quantum-classical auxiliary-field quantum Monte Carlo (QC-AFQMC) is a promising route to using quantum computers for strongly correlated electronic structure problems, but its scalability is limited by a classical post-processing bottleneck: the measured quantum trial state must be used to evaluate overlaps, force biases, and local energies for many walkers throughout the AFQMC propagation. Existing matchgate-shadow approaches avoid the exponential cost of generic classical shadows, but their post-processing remains expensive for large systems. In this work, we show that particle-number-preserving fermionic shadows, implemented as orbital-rotation shadows, are able to drastically reduce QC-AFQMC post-processing costs. We derive efficient estimators for overlaps and their derivatives, giving O(N3) scaling for overlaps and force biases and O(N4) scaling for local energies per shadow and walker and with O(N) Cholesky vector. For fixed normalized target determinants, we also prove that the overlap estimator is unbiased with variance upper bounded by O(η), where η is the particle number, yielding a sufficient budget of O(η/ε2) ideal independent measurements for additive overlap error ε. We combine these estimators with a novel virtual-correlation-energy treatment and a GPU implementation and demonstrate QC-AFQMC using orbital-rotation shadows. Performance projections for π-conjugated molecules up to pentacene with a (22e, 22o) active space and 356 total orbitals show that the full classical post-processing workflow can be completed in slightly more than two days on 8×A100 graphics processing units (GPUs). These results significantly reduce classical post-processing costs for QC-AFQMC and motivate further improvements in preparation and measurement of the trial state on quantum hardware.