When a Quantum Policy Is Hard to Sample but Easy to Use

One quantum distribution, many possible decisions

An instantaneous quantum polynomial-time (IQP) circuit with n qubits can produce a distribution over 2ⁿ bit strings. A reinforcement-learning environment, however, may offer only a handful of actions. A classical decoder groups many strings under each action, and the probability of an action is the sum of the probabilities of its strings. That grouping is not a neutral interface: it changes what the policy can learn and what a classical computer may calculate.

André Sequeira’s November 2026 preprint asks how to choose decoders that avoid vanishing policy variation at random initialization without confusing that property with either successful learning or computational hardness. The paper studies parameterized IQP policies and repeated circuits that alternate commuting layers; its exact IQP variance results should not be transferred wholesale to those more general circuits.

A decoder leaves a mathematical fingerprint

The paper expresses each action’s measurement rule as a sum of Pauli observables—operators that track patterns of agreement and disagreement among measured bits. Each observable’s coefficient is set by the decoder. With independently uniform circuit angles, the variance of an IQP policy probability can be written as a sum of squared coefficients, weighted by a factor determined by the binary rank of the circuit generators that affect each observable. When different observables have identical generator signatures, their coefficients must be combined before squaring; they can cancel.

This gives a practical certificate, not a promise of good training: a sufficiently large coefficient attached to a low-rank component can keep an action probability from becoming exponentially concentrated near its average. For a graph-based circuit with local and pairwise interactions, the relevant rank generically equals the size of the observable’s backward interaction neighborhood. Only the neighborhood of that particular component matters; a dense network elsewhere does not automatically erase the certificate. Exceptional circuit angles can shrink the realized neighborhood. The conclusion concerns initial policy probabilities, not every gradient, return, or optimization trajectory.

The paper’s proposed majority–modulo decoder divides measured bits into blocks, takes a majority vote in each block, then maps the resulting code to an action. Majority has many high-weight correlations in its exact Pauli expansion, but also retains small, useful low-weight terms. In the odd, equal-block construction, those terms can protect policy variance when their circuit neighborhood is small. Modulo collisions between codes can cancel individual low-weight terms, so the analysis checks which components survive rather than assuming every action keeps the same signal.

Dense does not mean hard—and trainable does not mean better

A long exact Pauli expansion can make direct term-by-term calculation expensive. That alone is not evidence that no efficient classical method exists. For IQP circuits, the paper gives efficient additive estimation for sparse Pauli expansions and for contiguous intervals of bit strings, including action counts that are not powers of two. Its majority construction falls outside those particular sufficient conditions because its exact expansion is exponentially large; the author explicitly leaves open whether approximate or more direct estimators can simulate it efficiently.

Experiments test these claims at finite sizes. On graph-IQP paths, rings and random cubic graphs, observed initialization variances agree with predictions derived from the decoder’s Pauli structure. In controlled ten-qubit CartPole comparisons, majority obtained higher held-out returns than the tested parity and local-readout policies, but did not outperform the matched classical multilayer perceptron significantly. Gradient diagnostics found increasing relative participation from higher-weight sectors in one ten-qubit experiment; they do not show that those sectors caused the return difference.

A separate 21-qubit, connected block-chain policy was simulated by an exact tensor-network method and compared with a tested pool of multilayer perceptrons. Under its task-oriented initialization, it reached the study’s CartPole threshold sooner in episode count than those models. But that circuit admits efficient classical simulation, and the comparison is not a quantum advantage. In a follow-up using uniform initialization, the policy’s episode-efficiency ordering reversed against the 135-parameter perceptron. The preprint’s central distinction is therefore consequential: a decoder can preserve initial variation, yet neither that guarantee nor a large quantum output space establishes better learning or a classical simulation barrier.

What remains uncertain

These are finite simulation studies, not experiments on quantum hardware or demonstrations of asymptotic learning performance. The variance theorems rely on specified random initializations; task-oriented initializations can behave differently. The CartPole results compare selected architectures and training budgets, not every classical policy. And the exponential exact support of majority rules out direct enumeration of that expansion—not efficient simulation by all possible algorithms. The work offers a way to reason about these separate questions, rather than a claim that quantum policies are generally harder or better.