Exact softmax sampling from residual quantum overlaps
Compute part of an attention score classically, then sample the remainder. This study shows how the split changes measurement cost while preserving the ideal softmax distribution.
Split the score. Keep the distribution.
Classical work + residual measurements
Measure only what remains.
Keep part of the attention score in a classical projection. Use overlap measurements to sample the residual without changing the ideal target distribution.
Primary experiment · 96 attention rows · Calibration basis
Ranks 0, 16, and 32 show reported shot expectations; rank 64 is the exact classical endpoint. The ideal independent-measurement model preserves the softmax law. These are measurement costs, not measured hardware speedups. Source: the Quantum Information Processing manuscript.
What the study shows.
Keep the target distribution.
The classical projection and sampled residual sum to the original attention score. Under the ideal independent-measurement model, accepted labels follow the exact softmax law.
Spend fewer measurements.
On the 96 primary attention rows, retaining 32 of 64 coordinates reduces median expected shots per label from 172,000 to 2.81. This is a measurement-resource result.
Reuse the first proposal.
A first-proposal coupling gives an unbiased value estimator. An envelope-based coefficient guarantees no variance increase over ordinary averaging under the stated assumptions.
Scope & details.
The measurements are simulated independent outcomes with ideal circuit marginals. No physical quantum-hardware speedup or downstream model improvement is established; the local runtime comparison favors exact classical attention.
Read the 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⁵ to 2.81. No hardware speedup is established.
Citation
@unpublished{lex2026sampling,
title={Exact softmax sampling from residual quantum overlaps},
author={Lex, Vikram},
year={2026},
note={Manuscript under review at Quantum Information Processing}
}