💻 computer science

Exact softmax sampling from residual quantum overlaps

This paper presents an exact softmax sampling method for residual quantum overlaps that utilizes nested classical projections and a first-proposal coupling to significantly reduce the expected shot cost and variance, as demonstrated on pretrained model attention rows, though it does not establish a hardware speedup.

Original authors: Vikram Lex

Published 2026-09-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Vikram Lex

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of modern artificial intelligence, a specific mechanism called "attention" acts as the brain's way of deciding what information matters most. When a computer reads a sentence, it does not treat every word with equal weight; instead, it learns to focus on the most relevant parts, much like a human reader might skim a page to find the key idea. To do this, the system calculates a score for every possible connection between words, turns those scores into probabilities, and then uses those probabilities to mix together different pieces of information. This process is computationally heavy, requiring vast amounts of calculation to ensure the system picks the right focus. As these systems grow larger, researchers have begun to wonder if the strange laws of quantum physics could help perform these calculations more efficiently, potentially using the unique properties of quantum particles to sample these probabilities directly.

A new study by Vikram Lex of KarLex AI explores exactly this question, but with a crucial twist: it investigates whether a quantum approach can actually sample these probabilities correctly without claiming to be faster than current classical computers. The research focuses on a specific mathematical challenge: how to use a quantum device to pick a single outcome from a complex set of possibilities, where the chance of picking each one depends on an exponential calculation. The author combines a known method for generating random numbers with a technique that splits the problem into two parts: a part that can be calculated easily on a normal computer, and a "residual" part that is small enough to be measured by a quantum device. The goal was to see if this hybrid approach could produce an exact, unbiased result while managing the cost of the measurements required.

The core of the work involves a clever sampling strategy that acts like a series of coin flips. Imagine trying to pick a winner from a large group where the odds are not equal. The method proposed here first calculates a rough estimate of the odds using classical math. Then, for the remaining uncertainty, it uses a quantum interface to perform a series of binary tests. If the tests pass a certain threshold, the system accepts the choice; if they fail, it discards the attempt and tries again. This process is designed to be "exact," meaning that over many trials, the frequency of each outcome matches the true mathematical probability perfectly, without the need for the quantum device to perform a full, complex calculation every time. The study proves that by keeping more of the calculation on the classical side and only measuring the small leftover part, the number of quantum measurements needed drops dramatically.

To test this theory, the researcher used a pre-existing, frozen artificial intelligence model known as BERT, which is a standard tool for understanding language. They did not train a new model or build a new quantum computer. Instead, they took real data from the model's internal calculations and simulated the quantum measurements on a classical computer. The simulation used a specific set of 192 different attention patterns, each involving up to 512 words of context. The team tested how the method performed when they kept different amounts of information on the classical side, ranging from zero to nearly all of the data. The results showed a clear and powerful trend: as they retained more coordinates in the classical calculation, the number of quantum measurements required to get a single correct answer plummeted.

The numbers tell a striking story. When the researchers kept almost no information on the classical side, the simulation predicted that it would take an average of 172,000 quantum measurements to get just one correct label. However, when they retained just half of the available information (32 out of 64 coordinates) on the classical side, that number dropped to an average of only 2.81 measurements. This reduction was not just a lucky fluctuation; the study mathematically proved that adding more classical calculation steps always reduces the expected cost of the quantum measurements. The method also included a way to correct for errors, ensuring that the final answer remained accurate even when the sampling process was stopped early or when the number of measurements was limited.

Despite these impressive reductions in measurement cost, the paper is careful to state what it has not achieved. The author explicitly notes that no actual hardware speedup was established. The study did not run on a physical quantum computer, nor did it prove that this method is faster than the best classical algorithms running on today's supercomputers. The work is a proof of concept for a specific way of splitting a problem between classical and quantum resources, showing that the quantum part can be made very small and efficient. It demonstrates that the theoretical cost of the quantum measurements can be controlled and minimized, but it does not claim to have solved the problem of making quantum attention faster than classical attention in practice.

The study also addresses the reliability of the results. The researchers developed a method to estimate the final answer with a guaranteed level of accuracy, using a technique that compares the accepted samples against the initial proposals. This ensures that the final output is an unbiased estimate of the true value, meaning it is not skewed by the fact that some attempts were rejected. The paper confirms that this control mechanism works without increasing the variance of the result, provided the coefficients are chosen correctly based on the known bounds of the data. This adds a layer of certainty to the sampling process, ensuring that the efficiency gains do not come at the cost of accuracy.

In the end, this research offers a precise map of the trade-offs between classical and quantum computation for a specific type of problem. It shows that by carefully dividing the work, one can reduce the burden on the quantum side to a level where it becomes manageable, even if the total time to solve the problem is not yet faster than existing methods. The findings are grounded in rigorous mathematical proofs and extensive simulations using real-world model data, providing a clear picture of how these hybrid systems behave. While the work does not promise an immediate revolution in speed, it establishes a firm theoretical foundation for how quantum resources might be used to sample complex probabilities with high precision and low measurement cost.

Technical Summary: Exact Softmax Sampling from Residual Quantum Overlaps

Problem Statement
The paper addresses the challenge of sampling exact softmax labels directly from a residual quantum overlap interface without first estimating all scores and applying a classical softmax normalization. Standard approaches that estimate every overlap and then normalize introduce a precision-dependent measurement stage and alter the attention distribution if inputs are normalized without restoring their original norms. The core question is whether an overlap-measurement interface can sample the original softmax law directly and whether the division between classical and quantum resources can be chosen with explicit, provable guarantees.

Methodology
The proposed method combines a classical score projection with an exponential Bernoulli factory (based on Dughmi et al.) to create a "residual-overlap" sampling algorithm.

Residual Decomposition: For a query $q$ and keys $k_j$ , the dot-product score $s_j$ is decomposed into a known classical component $a_j$ (from a projected subspace) and an unknown residual component $c_j \mu_j$ . Here, $c_j$ is a known scale derived from residual norms, and $\mu_j$ is an unknown mean accessible only via independent binary outcomes $X_j \in \{-1, +1\}$ with expectation $\mu_j$ .
Measurement Interface: The unknown $\mu_j$ is accessed via a standard Hadamard test, which yields a Bernoulli outcome with probability $(1+\mu_j)/2$ . This interface assumes independent state preparations and measurements, without variational training or coherent superposition over key indices.
Exponential Bernoulli Race: The algorithm uses an exponential Bernoulli race to sample a label $J$ with probability $p_j = e^{s_j}/Z$ . It proposes a label $j$ from a proposal distribution $\rho_j = e^{u_j}/Z_+$ (where $u_j$ is an upper bound on the score) and accepts it based on a Poisson-distributed number of coin flips. If a negative outcome occurs during the flips, the trial is rejected early, saving measurement resources.
Unbiased Value Estimation with Control Variates: To estimate the value vector $y = \sum p_j v_j$ , the method retains the first proposal $K$ of each rejection cycle alongside the accepted label $J$ . Since $K$ follows a known distribution $\rho$ regardless of acceptance, it serves as a control variate. A deterministic coefficient $\gamma$ , computed from classical score envelopes (lower and upper bounds), is used to weight the correction term, guaranteeing no increase in variance compared to ordinary averaging.

Key Contributions

Exact Sampling Algorithm: An implementation of an exponential Bernoulli race that samples exact softmax labels from residual quantum overlaps under an ideal independent-measurement model.
Resource Analysis: Derivation of the expected shot cost and proposal count, including an "early-stopped" cost analysis that accounts for the rejection of trials before all scheduled measurements are performed.
Monotonicity Theorem: A proof that nested classical orthogonal projections (increasing the dimension $r$ of the retained subspace) monotonically reduce the expected measurement costs and computable upper bounds. At full dimension ( $r=d$ ), the cost drops to zero as the problem becomes purely classical.
Variance-Controlled Estimator: A first-proposal coupling identity and a certified control-variate coefficient. This coefficient is derived from score envelopes without observing the unknown means, ensuring the estimator's mean squared error does not exceed that of ordinary averaging.
Finite-Budget and Noise Guarantees: Analysis of stationary noise in measurement means and the behavior of the algorithm under fixed resource budgets, providing explicit failure conditions and error bounds relative to the ideal distribution.

Experimental Results
The author tested the method on 192 attention rows from a frozen pretrained BERT encoder (AG News and SQuAD datasets) with contexts up to 512 tokens.

Cost Reduction: Retaining 32 of 64 coordinates (rank 32) in a calibration basis reduced the primary median expected shots per label from $1.72 \times 10^5$ (rank 0) to $2.81$. In the original coordinate basis, the cost at rank 32 was 486.04, highlighting the importance of the basis choice.
Completion Rates: At rank 0, only 128 of 768 attempts completed within the budget; at ranks 32 and 56, all attempts completed.
Accuracy: The "controlled" estimator (using the certified coefficient) achieved a lower root mean squared error (RMSE) than ordinary averaging at fully completed ranks (e.g., 0.01494 vs. 0.01668 at rank 32).
Baselines: The method was compared against ordinary averaging, a uniform measurement plug-in estimator, and a classical projection-only approximation. The projection-only method remained competitive, and the controlled estimator generally outperformed ordinary averaging.

Significance and Claims
The paper explicitly states that it does not establish a quantum-classical complexity separation or claim a faster transformer. The algorithm can be executed by an ordinary Bernoulli oracle with the same means; the contribution lies in the specific resource analysis and the construction of an unbiased estimator with variance guarantees for the residual-overlap setting.

The work describes a continuum between overlap sampling and exact classical attention. The primary significance is the provision of explicit resource guarantees (shot costs and bounds) and a method to reduce measurement overhead through classical projections while maintaining exactness in the sampling distribution. The author emphasizes that the results are tested on definition-matched attention traces to validate the theoretical statements, rather than to claim a practical speedup over classical hardware. No hardware speedup is established.

Technical Summary: Exact Softmax Sampling from Residual Quantum Overlaps

More like this