Paper deep dive
Do Quantum AIs Dream in Paths? Path-Integral Slow Thinking through Grover Interference
Xiansheng Cai, Xiu-Hao Deng, Kun Chen
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 9/9/2026, 5:08:49 AM
Summary
This paper proposes a quantum AI framework for 'slow thinking' using discrete path integrals and Grover amplitude amplification to mitigate policy collapse in reinforcement learning. By maintaining reasoning trajectories in superposition and interfering them via Grover iterations, the model preserves exploratory diversity while optimizing for verified rewards. Simulations on a 2x3 sliding puzzle benchmark demonstrate that quantum models (QuCoNet and neural quantum AI) achieve significantly higher held-out accuracy and better scaling with inference budget compared to classical controls.
Entities (7)
Relation Signals (5)
QuCoNet → uses → Grover amplitude amplification
confidence 95% · In our trainable realization, an exact verifier partitions the ensemble into collective accepted and rejected components that interfere under Grover amplitude amplification.
QuCoNet → outperforms → classical controls
confidence 94% · at four rounds with matched circuit applications the two quantum models reach 3.2 and 3.9 times the strongest classical controls.
RLVR → causes → Policy Collapse
confidence 93% · Reinforcement learning with verifiable rewards enables large language models to think slowly, but the same training can induce policy collapse
Grover amplitude amplification → mitigates → Policy Collapse
confidence 92% · These results establish a Grover-based realization of path-integral slow thinking: the interior target preserves exploratory path diversity, and ensemble-level interference converts it into verified performance.
Sliding puzzle → usedforevaluation → QuCoNet
confidence 90% · In exact statevector simulations of a 2x3 sliding puzzle, Grover training reaches accuracy 0.95
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Reinforcement learning with verifiable rewards enables large language models to think slowly, but the same training can induce policy collapse: probability concentrates onto a few successful trajectories and exploratory diversity erodes. We ask whether quantum AI can realize slow thinking differently. We formulate slow thinking as coherent dynamics over reasoning trajectories, a discrete path integral in which action sequences coexist in superposition and recombine before measurement. In our trainable realization, an exact verifier partitions the ensemble into collective accepted and rejected components that interfere under Grover amplitude amplification. A finite Grover evolution is maximized when the pre-amplification success probability lies at an analytically determined value below one, so inference itself defines an interior training target and removes the monotonic pressure toward unit success. In exact statevector simulations of a 2x3 sliding puzzle, Grover training reaches accuracy 0.95 on a 32-question training set at one round, against 0.73 for the strongest classical control. On held-out questions specialization has a cost: an untrained uniform policy read out through the same amplification remains the strongest reference on this solution-dense benchmark, and quantum training preserves far more held-out accuracy than classical training - at four rounds with matched circuit applications the two quantum models reach 3.2 and 3.9 times the strongest classical controls. The number of training questions supported by fixed-size policies trained at each amplification budget also grows faster with the budget than with matched classical repetition. These results establish a Grover-based realization of path-integral slow thinking: the interior target preserves exploratory path diversity, and ensemble-level interference converts it into verified performance.
Tags
Links
- Source: https://arxiv.org/abs/2609.05842v1
- Canonical: https://arxiv.org/abs/2609.05842v1
Trouble viewing inline? Open PDF directly →
Full Text
135,577 characters extracted from source content.
Expand or collapse full text
Do Quantum AIs Dream in Paths? Path-Integral Slow Thinking through Grover Interference Xiansheng Cai Affiliation: Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China Xiu-Hao Deng Affiliation: Shenzhen International Quantum Academy, Shenzhen 518048, China Affiliation: Shenzhen Branch, Hefei National Laboratory, Shenzhen 518048, China Kun Chen Email: chenkun@itp.ac.cn Affiliation: Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China September 5, 2026 Abstract Reinforcement learning with verifiable rewards enables large language models to think slowly through long chains of thought, but the same training can induce policy collapse: probability concentrates onto a few successful trajectories, and exploratory diversity erodes. We ask whether quantum AI can realize slow thinking differently. We formulate slow thinking as coherent dynamics over reasoning trajectories, a discrete path integral in which action sequences coexist in superposition and recombine before measurement. In our trainable realization, an exact verifier partitions the ensemble into collective accepted and rejected components that interfere under Grover amplitude amplification; the working resource is this ensemble-level interference. A finite Grover evolution is maximized when the success probability before amplification lies at an analytically determined value below one, so inference itself defines an interior training target and removes the monotonic pressure toward unit success. In exact statevector simulations of a 2×32× 3 sliding puzzle with interdependent moves, Grover training reaches accuracy 0.950.95 on a 3232-question training set at one round, against 0.730.73 for the strongest classical control. On held-out questions, specialization has a cost: an untrained uniform policy read out through the same amplification remains the strongest reference on this solution-dense benchmark. Quantum training preserves far more held-out accuracy than classical training: at four rounds with matched reasoning-circuit applications, the table-based and neural quantum models reach 3.23.2 and 3.93.9 times the held-out accuracy of the strongest classical controls. For policies of fixed size trained separately at each amplification budget, the number of supported training questions grows faster with the budget than with matched classical repetition. These results establish a Grover-based realization of path-integral slow thinking, in which the interior target set by inference preserves exploratory path diversity and ensemble-level interference converts interior success probabilities into verified performance. I Introduction Recent advances in large language model (LLM) reasoning have been driven in part by chain-of-thought generation [1]. Rather than producing a final answer directly, an LLM generates a sequence of intermediate tokens, with each new token conditioned on the problem and the preceding sequence. A complete reasoning sequence can therefore be viewed as a stochastic trajectory through possible intermediate steps. Because each step admits multiple continuations, increasing the sequence length expands both the depth of the computation and the space of possible reasoning trajectories. This enlarged space allows the model to compose more intermediate operations and thereby reach solutions that are inaccessible to shorter trajectories. Increasing the reasoning horizon at inference—known as test-time scaling—can therefore enable a model to solve harder problems without increasing its number of parameters [2, 3, 4]. Continued progress in coherent quantum information processing raises a natural question: could a quantum AI model acquire an analogous form of slow thinking [5] through quantum dynamical evolution? If so, how would its reasoning differ fundamentally from classical slow thinking, how could such a model be trained, and what computational or learning advantages might coherence provide? The first question has a natural dynamical answer. An LLM defines a statistical distribution over reasoning trajectories, from which each inference run samples one realized trajectory. A quantum model instead propagates amplitudes coherently through multiple reasoning histories and combines them by a path integral before the final measurement. Let x be the input problem, y a possible final answer, and γ=(z1,…,zT)γ=(z_1,…,z_T) a complete sequence of T intermediate reasoning states generated from x, with ztz_t denoting the state at step t. We write γ:x→yγ:x→ y when this trajectory contributes to the final answer y. Schematically, PLLM(y|x) P_LLM(y|x) ∝∑γ:x→ye−ILLM[γ|x], _γ:x→ ye^-I_LLM[γ|x], (1) PQ(y|x) P_Q(y|x) ∝|∑γ:x→yAQ[γ|x]|2. | _γ:x→ yA_Q[γ|x] |^2. Here ILLM[γ|x]I_LLM[γ|x] is the surprisal of a reasoning trajectory, whereas AQ[γ|x]=|AQ[γ|x]|eiSQ[γ|x]/ℏA_Q[γ|x]=|A_Q[γ|x]|e^iS_Q[γ|x]/ is the corresponding quantum trajectory amplitude. The effective phase action SQS_Q is defined modulo 2πℏ2π , and ℏ fixes the unit in which the phase is measured and may be set to one. The proportionality signs suppress normalization and readout-dependent factors. The first expression is a statistical sum: an individual run realizes one trajectory. The second is a path integral over complex amplitudes, in which multiple histories coexist in superposition and can interfere before measurement. Increasing the reasoning horizon enlarges the space of histories in both cases, but only the quantum dynamics can recombine their amplitudes coherently. This distinction suggests that a longer reasoning horizon could enlarge the available reasoning space while interference selects the final answer without first collapsing onto one trajectory. This is not yet an advantage: coherence alone neither selects useful interference nor explains how a model should preserve and exploit a large space of reasoning trajectories. To formulate this problem, we first examine how classical systems convert additional inference time into a search over possible trajectories. AlphaGo provides a canonical state-based realization of this idea. Here a policy is a parameterized rule that assigns probabilities to available actions, whereas a value network estimates the expected future outcome of a state. AlphaGo combined these learned networks with Monte Carlo tree search (MCTS) [6, 7]. Because Go supplies explicit board states, legal actions, and known transitions, MCTS can repeatedly expand a persistent tree, evaluate possible continuations, and propagate their outcomes backward. This construction separates learning from slow thinking: reinforcement learning improves the policy and value networks that guide the search, whereas MCTS converts additional inference-time computation into deeper and broader exploration without changing the network parameters. Reasoning LLMs pursue the same objective under a different constraint. Their effective state is the complete token history rather than a compact, task-defined state with a known transition graph, making persistent tree construction and state reuse substantially more difficult. Modern reasoning models therefore commonly use trajectory-level reinforcement learning with verifiable rewards (RLVR): complete reasoning trajectories are sampled, a verifier scores their final answers, and sequence probabilities are updated without constructing a persistent tree of explicit intermediate states. DeepSeekMath introduced group relative policy optimization (GRPO), a method that estimates each trajectory’s relative advantage from other trajectories sampled for the same problem, without a separately trained value model (often called a critic) [8]. DeepSeek-R1 showed that GRPO-based RLVR can produce long reasoning sequences, self-correction, and strategy changes without labelled intermediate steps [2]. This trajectory-level training is powerful, but it has an intrinsic tendency to improve single-attempt accuracy at the expense of exploratory diversity. Suppose that a model initially possesses two distinct strategies for solving the same problem, each with modest success probability. Early reward fluctuations may favor one strategy. Reinforcement then increases its probability, causing it to be sampled and rewarded still more frequently, while the competing strategy gradually disappears. The resulting model may achieve high single-attempt accuracy by exploiting the dominant strategy, yet lose the diversity required to explore alternative solutions. Additional test-time computation then produces variations of essentially the same reasoning path rather than opening new ones [9, 10, 11]. This phenomenon is known as policy collapse. MCTS controls an analogous loss of exploration through an explicit exploration term: branches with high estimated value are favored, but less-visited branches continue to be sampled. Trajectory-level RLVR has no direct analogue of this node-wise visitation information because it updates a global distribution over complete sequences. Entropy regularization and confidence constraints can slow the collapse [11, 12], but no general mechanism currently combines reliable outcome optimization with sustained diversity of reasoning trajectories. This leaves the training question posed above: can a coherent inference map optimize verified outcomes without erasing the path diversity on which it acts? Figure 1: Coherent inference preserves multiple reasoning trajectories. (a) The table-based quantum concept-network model (QuCoNet) records each move in a fresh auxiliary register, called a which-path register. Measuring these records reduces the reasoning circuit to the corresponding classical Markov chain, whose probabilities are computed exactly; retaining the records coherently prepares all trajectories for Grover amplification in Fig. 4(a) (Supplemental Material). (b),(c) Routing for one training question (training-set size B=32B=32, question-pool seed 11; start, green circle; target, purple star). Nodes are ordered by distance from the start, and edge width gives the success-probability flow through that edge. Single-attempt training concentrates the classical walker on one route. Grover-based training retains a branching ensemble of paths distinguished by orthogonal which-path records at the interior target. The inverse participation ratio (IPR) is the effective number of paths; panel (c) shows a favorable case, while the accuracy-weighted mean IPR is 1.61.6 at q=3q=3, where q counts reasoning-circuit applications. The panels show path weights, not interference between the displayed paths. Existing quantum AI provides important ingredients for this question, but it does not yet realize slow thinking as test-time scaling of a learned reasoning model. Quantum projective-simulation agents use quantum walks to accelerate deliberation over an episodic-memory network [13, 14, 15]; parametrized quantum circuits serve as trainable policies over observed states [16]; and amplitude amplification accelerates inference in trained quantum generative models [17] and reward discovery in episodic reinforcement learning, in theory and in a photonic experiment [18, 19], where the policy being learned remains classical. Closest to our setting, quantum Markov decision processes propagate coherent superpositions of multistep state–action trajectories and amplify those with high returns [20, 21]. These approaches provide important ingredients, but leave unresolved the central question of quantum slow thinking: can a fixed-size learned quantum model turn extra coherent inference computation into greater verified problem-solving capability while avoiding the policy-collapse trade-off of classical trajectory-level RLVR—the concentration of probability on only a few successful reasoning trajectories? In this Article, we formulate quantum slow thinking as a discrete path integral over reasoning trajectories, realized as coherent dynamics in a trainable quantum reasoning network. We realize this framework with coined quantum walks in two forms [22, 23, 24]. The first, QuCoNet, is a table-based quantum extension of the concept-network model (CoNet), an effective network description of multistep reasoning [25, 26]: each problem state carries a directly optimized local unitary that distributes amplitude among the allowed next actions. The second is a neural quantum AI model in which a parameter-sharing network generates this local unitary from the question and the preceding action sequence. In both models, a trainable reasoning circuit θA_θ, with θ denoting the model parameters, prepares a coherent ensemble of action sequences. A verifier separates this ensemble into collective accepted and rejected components, and Grover reflections recombine them [27, 28, 29]. After a finite coherent evolution, the final success probability peaks when the success probability before interference reaches an analytically determined nonunit value. Training toward this interior target, a preferred probability strictly between zero and one, can improve the final result while retaining multiple reasoning paths, thereby mitigating policy collapse in this setting. We train and evaluate both models on a 2×32× 3 sliding puzzle [Fig. 2], a slow-thinking benchmark introduced in Ref. [26], in which solving a question requires a sequence of interdependent moves. The target configuration is supplied, but the model must discover a valid trajectory that reaches it, so an exact verifier can evaluate every candidate trajectory. Generic question answering would instead require a learned verifier or value model to mark candidate outcomes coherently. The trained models retain branching ensembles of reasoning paths [Fig. 1(b),(c)]. For a matched comparison of inference computation, the quantum and classical methods receive the same number of applications of the reasoning circuit: the classical method uses them to sample independent trajectories, whereas the quantum method uses them for state preparation and Grover interference. At four Grover rounds, QuCoNet and the neural quantum AI model achieve respectively 3.23.2 and 3.93.9 times the held-out accuracy of the strongest classical controls, where held-out accuracy is the mean success probability on question–answer pairs that were not used for training. Over the tested range, the number of question–answer pairs supported by a policy of fixed size, trained separately at each budget, also grows faster with the amplification budget (the number of reasoning-circuit applications) than with matched classical repetition. These results establish a trainable, Grover-based realization of path-integral slow thinking, in which the interior target defined by Grover inference preserves multiple reasoning paths while the amplification improves verified performance. In the present framework, quantum dynamics is the trainable reasoning process itself. Running more Grover rounds increases the inference computation per question, and a policy of fixed size trained for a larger round budget supports more question–answer pairs. The training objective is the same quantity computed during inference: the success probability after a chosen number of rounds. Grover interference is therefore not appended after training to a policy optimized for direct measurement: the policy is trained to prepare the trajectory distribution on which its later coherent reasoning will act. The remainder of this Article is organized as follows. Section I develops the statistical-trajectory and path-integral descriptions of classical and quantum reasoning. Section I introduces the sliding-puzzle benchmark and the table-based and neural quantum AI models. Sections IV and V explain RLVR and policy collapse, then construct quantum RLVR through Grover interference and derive its finite-depth training target. Section VI compares the training objectives, held-out performance, path diversity, and scaling with inference depth. Section VII concludes with extensions to learned verifiers and the requirements for physical realization. I Classical and Quantum Reasoning Trajectories Let θ denote the trainable model parameters. For an autoregressive LLM, a reasoning trajectory γ=(z1,…,zT)γ=(z_1,…,z_T) has probability Pθ[γ|x]=∏t=1Tπθ(zt|x,z<t)=e−ILLM[γ|x].P_θ[γ|x]= _t=1^T _θ(z_t|x,z_<t)=e^-I_LLM[γ|x]. (2) Here πθ(zt|x,z<t) _θ(z_t|x,z_<t) is the normalized conditional probability of the next reasoning state, and z<t=(z1,…,zt−1)z_<t=(z_1,…,z_t-1) is the complete prefix. Thus ILLM[γ|x]=−logPθ[γ|x]I_LLM[γ|x]=- P_θ[γ|x] is a dimensionless information action, or trajectory surprisal. Equation (2) makes no Markov approximation: each conditional may depend on the complete prefix. A quantum reasoning circuit associates a complex transition amplitude αθ(zt|x,z<t) _θ(z_t|x,z_<t) with each conditional, so the path amplitude is AQ[γ|x]=∏tαθ(zt|x,z<t)A_Q[γ|x]= _t _θ(z_t|x,z_<t), whose phase is written schematically as SQ[γ|x]/ℏS_Q[γ|x]/ . Let |γ⟩|γ denote the basis state that records the complete trajectory, and let MyM_y be the element of a positive operator-valued measure (POVM) associated with answer y. The answer probability is then PQ(y|x)=∑γ,γ′AQ[γ|x]AQ∗[γ′|x]⟨γ′|My|γ⟩.P_Q(y|x)= _γ,γ A_Q[γ|x]A_Q^*[γ |x] γ |M_y|γ . (3) The γ=γ′γ=γ terms form a classical mixture of histories; nonzero off-diagonal terms permit interference whenever the measurement coherently recombines the corresponding histories. In the Grover realization studied here, fresh which-path records keep individual trajectories orthogonal. No pairwise interference between these records contributes to the success probability or to the path statistics reported below. Instead, the verifier reflection and the reflection about the prepared state act coherently on the collective accepted and rejected components, as described below. I Sliding-Puzzle Benchmark and Quantum Reasoning Models We make the trajectory framework concrete by turning a goal-directed 2×32× 3 sliding puzzle [26] into a finite configuration network [Fig. 2]. Each allowed arrangement of the five numbered tiles and one hole is a node, and each reversible move is an edge. We restrict the hole to the middle column and define three moves: V exchanges the two central cells, whereas L and R carry the hole around the left or right corners through three elementary tile slides. Each complete L or R cycle counts as one action and hence one network edge. Restricting the tile permutation to one parity class produces a 33-regular graph with N=120N=120 nodes and K=3K=3 available actions at every node (construction in the Supplemental Material). A question–answer pair xi=(Qi,Ai)x_i=(Q_i,A_i) is a pair of nodes in this network: QiQ_i is the start configuration and AiA_i is the target configuration, chosen at graph distance 33–66 from QiQ_i. The target AiA_i is supplied to the model; the nontrivial output is an ordered trajectory γi=(a1,…,aT) _i=(a_1,…,a_T) with a prefix that carries the configuration from QiQ_i to AiA_i. We allow at most M=8M=8 actions, and an exact binary verifier accepts a trajectory on its first arrival at AiA_i within this horizon. The four-action example in Fig. 2 makes the slow-thinking character explicit: the answer can be obtained only through a sequence of interdependent actions, not from any single intermediate state. For each question pool, the first B question–answer pairs form the training set and 6464 pairs disjoint from the training set form the held-out set; model snapshots are selected using the training set only. Throughout, accuracy denotes the mean final success probability over the specified set of question–answer pairs. Figure 2: The sliding puzzle as a network benchmark for slow thinking. Top: the three reversible graph moves. V swaps the two central cells; L and R move the hole through the left or right corners using three elementary tile slides. Each complete L or R cycle counts as one action and one edge of the configuration graph. Restricting the hole to the middle column and the tile permutation to one parity class gives N=120N=120 reachable configurations, each with K=3K=3 available actions. Bottom: a question–answer pair specifies start and target nodes in this graph. The target is supplied to the model, whose output is a trajectory connecting the two nodes. The example requires four actions. The verifier accepts on first arrival at the target within the reasoning horizon M=8M=8; the node numbers label graph configurations. This network abstraction is not specific to sliding puzzles. Many multistep tasks can be represented as navigation through an implicit state network: nodes may denote partial mathematical derivations, partial proofs, intermediate programs, or physical configurations, while edges denote valid algebraic transformations, inference rules, code edits, or control actions. Such networks are generally enormous, history dependent, and not explicitly available to the model. They nevertheless share the ingredients isolated here: a starting condition, branching sequences of actions, delayed verification, and potentially many trajectories to the same outcome. The sliding puzzle is therefore a controlled benchmark of AI reasoning: it retains these structural features while providing exact transitions and an exact verifier, so trajectory exploration, policy collapse, and interference can be measured without ambiguity. Figure 3: Slow thinking as a walk on a concept network. Nodes denote coarse-grained concepts, later given an operational definition as effective predictive states, and directed edges denote learnable local transitions. A single hop is a fast System-1 operation [5]. Repeatedly applying the same local dynamics constructs a trajectory from a question Q through intermediate states to an answer, realizing System-2 slow thinking as evolution in time. Red arrows highlight one such trajectory. This state-network view defines the concept-network model (CoNet) [Fig. 3]. CoNet was introduced in the Learning-at-Criticality framework as a minimal dynamical model for studying learning transitions and generalization in LLMs [25]. Its original construction coarse-grained the nearly deterministic, low-entropy token sequences into concept nodes, represented the high-entropy choices between them by learnable links, and assumed Markovian dynamics among the resulting nodes. A reasoning episode was then a walk from a question node to an answer node, with reinforcement learning updating the local transition probabilities. The subsequent work of Ref. [26] applied and extended this framework to explain how RLVR can produce long chains of thought and emergent slow thinking. That analysis associated the onset of slow thinking with an inverse-tree-freezing transition, in which reinforcement stabilizes extended multistep trajectories. It also placed the concept-state construction on an operational footing through predictive state variables (PSVs). Two token histories belong to the same PSV when they induce indistinguishable conditional distributions over future continuations. The resulting equivalence classes are effective states on which the dynamics is Markovian, replacing the earlier coarse-graining assumption with an operational definition. CoNet is therefore not an LLM architecture, but an effective dynamical description of reasoning unfolded in time. Here we use the finite configuration network above as a concrete CoNet and promote its stochastic routing dynamics to coherent quantum dynamics. This extension provides a minimal quantum AI model for studying quantum RLVR. Its table-based realization, QuCoNet, replaces the local probability vector by a trainable 3×33× 3 unitary, called the coin operator. Each step of the resulting coined quantum walk alternates this local redistribution of amplitude with a reversible shift to the selected neighboring state, thereby propagating amplitudes coherently over action sequences [30]. The neural quantum AI model instead uses a parameter-sharing network to generate the coin from the question and the preceding action sequence. This removes the need for a separate parameter table at every node and allows the local quantum dynamics to depend on the complete reasoning prefix. The classical CoNet and both quantum models route weight through intermediate reasoning states; they differ in how the trajectory distribution is represented, evolved, and measured. In either quantum model, each move is recorded in a fresh auxiliary register, called a which-path register [Fig. 1(a)]. The trainable reasoning circuit θA_θ then prepares a coherent superposition |ψi⟩=θ|0⟩| _i =A_θ|0 over all KM=38K^M=3^8 action sequences. Here |0⟩|0 denotes the initialized circuit registers, and the dependence of θA_θ on question xix_i is implicit. Let Pacc,iP_acc,i project onto the trajectories accepted by the verifier for question i. Their total weight before interference is pi(θ)=⟨ψi|Pacc,i|ψi⟩=∑γ∈ΓiaccPθ[γ|xi],p_i(θ)= _i|P_acc,i| _i = _γ∈ _i^accP_θ[γ|x_i], (4) where Γiacc _i^acc is the set of accepted trajectories and Pθ[γ|xi]≡|AQ[γ|xi]|2P_θ[γ|x_i]≡|A_Q[γ|x_i]|^2 is the path weight obtained by measuring the which-path records before amplification. Measuring these records samples the corresponding classical distribution; retaining them coherently allows the accepted and rejected components to be recombined before measurement. In the present study, we evaluate Eq. (4) and its gradients by exact classical enumeration, thereby isolating coherent inference as the quantum resource rather than conflating it with faster training. Full-state propagation in the NKM=120×38=787,320NK^M=120× 3^8=787,320-dimensional Hilbert space of positions and path records independently verifies the coherent circuit construction (Supplemental Material). IV RLVR and Policy Collapse Equation (4) provides the interface between the reasoning model and its training objective. For each training pair i, the parameters θ determine the weights of all reasoning trajectories, the verifier identifies the accepted trajectories, and their total weight gives pi(θ)p_i(θ). Training then differentiates a loss constructed from these success probabilities and updates the same parameters: θ⟶Pθ[γ|xi]⟶pi(θ)⟶ℒ(θ)⟶θ.θ\ \ P_θ[γ|x_i]\ \ p_i(θ)\ \ L(θ)\ \ θ. This procedure applies to all three trainable policies: the transition weights of classical CoNet, the local coin tables of QuCoNet, and the shared parameters of the neural quantum AI model. In our calculations, every pi(θ)p_i(θ) and its gradient are evaluated exactly, so the comparison below differs in the training objective and the subsequent inference dynamics, not in the accuracy of a sampling-based gradient estimate. One widely used practical realization of RLVR is group relative policy optimization (GRPO) [8]. GRPO samples several complete trajectories for the same question and compares each terminal reward with the mean reward of the group. Trajectories scoring above the group mean are made more probable, while those scoring below it are made less probable. The group therefore supplies the reference value without a separately trained value model, or critic. In practical GRPO, this learning signal is estimated from sampled groups of trajectories. Because the present benchmark has a finite trajectory space, we can instead compute the complete sum over trajectories and its gradient exactly. Assigning unit reward to an accepted trajectory and zero to a rejected one makes this sum, pi(θ)p_i(θ), the expected reward of a single inference attempt, so training minimizes ℒRLVR(θ)=−∑ipi(θ).L_RLVR(θ)=- _ip_i(θ). (5) The loss decreases whenever any pip_i increases and therefore pushes every training question toward unit success. It depends only on the total accepted weight and is indifferent to how that weight is divided among distinct successful trajectories. Consequently, it supplies no counterpressure when one successful route grows at the expense of alternatives. This indifference becomes a tendency toward policy collapse when a shared policy with finite capacity must serve many questions. Increasing the probability of an already successful route can improve the reward more easily than maintaining several weakly sampled alternatives. In practical RLVR, sampling adds further positive feedback: routes that succeed early are observed and reinforced more often, whereas competing routes receive fewer updates. Training can therefore obtain high single-attempt accuracy while losing the diversity needed to explore unfamiliar problems. The loss does not mathematically force the policy to place all probability on a single trajectory; rather, it contains no mechanism that protects alternative paths. The collapse observed under exact evaluation in Fig. 4(b) also shows that the effect in our benchmark is not solely a finite-sampling artifact. Classical test-time repetition improves the probability of finding an answer but does not change this training pressure. If each independent attempt succeeds with probability p, at least one of k attempts succeeds with probability Ck(p)=1−(1−p)k,dCkdp=k(1−p)k−1>0.C_k(p)=1-(1-p)^k, dC_kdp=k(1-p)^k-1>0. (6) This success probability is still monotonic in p. Training for repeated sampling therefore continues to favor the largest possible single-attempt success probability and creates no interior point at which the policy should stop concentrating its probability. The same statement applies to adaptive procedures that observe only the final binary verdict of each completed trajectory (Supplemental Material). It does not apply to methods that inspect intermediate states, modify the policy between attempts, or explicitly reward diversity. Within this outcome-only setting, changing a classical policy into a quantum parameterization is insufficient: if the prepared quantum state is measured directly, the measurement samples the same trajectory probabilities and the objective is the same monotonic one. A different training pressure therefore requires a coherent operation that changes the success probability before measurement. V Quantum RLVR through Grover Interference Quantum reinforcement learning has used quantum dynamics in several distinct roles. Quantum projective simulation replaces a stochastic walk through the agent’s episodic memory by a quantum walk, making coherence part of the agent’s internal deliberation before it selects an action [13, 14, 15]. Parametrized quantum circuits instead learn a map from an observed state to an action distribution [16], following earlier quantum reinforcement-learning frameworks [31]. Other algorithms use amplitude estimation or Grover search to accelerate policy evaluation, policy improvement, or inference [32, 17]. Recent quantum Markov decision processes go further by coherently generating multistep state–action trajectories, computing their returns, and amplifying the high-return sector [20, 21]. These works are direct precursors: quantum deliberation, trainable quantum policies, coherent trajectory propagation, and amplitude-amplified selection all existed before the present study. Our distinction is therefore not the mere presence of a quantum policy or a multistep coherent process. We ask whether a learned model of fixed size can convert additional coherent inference time into increased reasoning capacity, in direct analogy with test-time scaling in LLMs. The policy first prepares a superposition of complete reasoning trajectories, which undergoes verifier-controlled Grover evolution before any outcome is measured. The number of Grover rounds is then an inference-time resource: it changes the computation performed at inference rather than the number of trainable parameters. Crucially, the same finite-depth dynamics also defines the training objective. The model is not optimized for the directly measured base probability pi(θ)p_i(θ) and then accelerated by a quantum subroutine; it is optimized for the composite success map G≤q[pi(θ)]G_≤ q[p_i(θ)] that will determine its success at inference. Coherence thus changes both how the model reasons and what trajectory distribution it is trained to represent. This joint dependence of inference and training is what we call quantum slow thinking. The essential step is to postpone measurement until the verifier has acted coherently. Operationally, one inference run begins when the reasoning circuit θA_θ prepares a superposition of complete reasoning trajectories. Each Grover round then performs two operations. First, a coherent verifier applies a minus sign to trajectories whose final outcomes are accepted, without revealing which outcome occurred. Second, the sequence θ†A_θ , then a phase flip about the initial state |0⟩|0 , then θA_θ reflects the state about the prepared superposition. The verifier alone changes no probability; the second reflection converts its phase contrast into amplitude transferred from the rejected sector to the accepted sector. Measurement is performed only after the chosen number of complete rounds. This sequence is Grover amplitude amplification applied to reasoning [27, 28]. For one question, we suppress the index i and decompose the state prepared by θA_θ into collective components in the two orthogonal subspaces, or sectors, accepted and rejected by the verifier, |ψ⟩ |ψ =p|ψacc⟩+1−p|ψrej⟩, = p\,| _acc + 1-p\,| _rej , (7) p p =sin2ϑ,0≤ϑ≤π2, = ^2 , 0≤ ≤ π2, where |ψacc⟩| _acc and |ψrej⟩| _rej are the normalized collective components, and p is the success probability before interference. The verifier reflection Racc=I−2PaccR_acc=I-2P_acc gives the two components opposite phases but does not by itself change their probabilities. Reflection about the prepared state, Rψ=2|ψ⟩⟨ψ|−I=θ(2|0⟩⟨0|−I)θ†R_ψ=2|ψ \! ψ|-I=A_θ(2|0 \! 0|-I)A_θ , converts this phase difference into a redistribution of accepted and rejected weight. Together the two reflections form one Grover round. Which-path records keep individual trajectories orthogonal, while the complete Grover round coherently rotates the collective accepted and rejected components. No pairwise interference between individual path records is required. This is a two-sector coarse graining of the path integral in Eq. (3): all accepted histories form one sector, all rejected histories form the other, and their relative phase becomes observable when the two sectors are coherently recombined. Geometrically, the evolution remains in the two-dimensional plane spanned by |ψacc⟩| _acc and |ψrej⟩| _rej . If the initial accepted amplitude is sinϑ , each complete Grover round rotates the state by 2ϑ2 toward the accepted sector. After r rounds, the accepted amplitude is therefore sin[(2r+1)ϑ] [(2r+1) ]. These r rounds involve q=2r+1q=2r+1 applications of the reasoning circuit θA_θ or its inverse θ†A_θ : one application prepares the state, and each round adds one application in each direction. The final success probability is Gq(p)=sin2(qarcsinp),q=2r+1.G_q(p)= ^2\! (q p ), q=2r+1. (8) Unlike Ck(p)C_k(p), this map is not monotonic. Its first maximum reached from p=0p=0 occurs at the nonunit base probability p∗(q)=sin2(π2q),p∗(3)=14.p^*(q)= ^2\! ( π2q ), p^*(3)= 14. (9) Below this value, increasing p improves the final result; immediately above it, the Grover rotation overshoots and the gradient reverses. The inference dynamics therefore supplies an interior training target rather than pushing p monotonically toward one. Training proceeds exactly as in the classical loop above, except that the verifiable reward is evaluated after coherent inference rather than directly after state preparation. This is the sense in which the procedure is quantum RLVR: the correctness criterion is still a terminal verifier, but quantum dynamics transforms the success probability on which the policy is trained. When at most q applications of the reasoning circuit are available, we stop at the Grover round nearest the first maximum and denote the resulting probability by G≤q(p)G_≤ q(p); the exact rule is given in the Supplemental Material. We then minimize ℒQ(θ)=−∑iG≤q[pi(θ)].L_Q(θ)=- _iG_≤ q\! [p_i(θ) ]. (10) The gradient passes through pi(θ)p_i(θ) to the same table or neural parameters as before. Unlike Eq. (5), however, Eq. (10) trains each question toward p∗(q)p^*(q). The reasoning policy need only place this finite weight on accepted trajectories; the subsequent coherent evolution amplifies it to unit success. Thus the inference dynamics determines both what the model learns and how the learned trajectory weights are converted into an answer. A longer coherent evolution can amplify a smaller initial accepted weight: for small p, Gq(p)=q2p+O(p2)G_q(p)=q^2p+O(p^2). Reaching constant success consequently requires O(1/p)O(1/ p) coherent applications of the reasoning circuit, whereas independent verified sampling requires O(1/p)O(1/p) attempts. Here and below, these are query counts in the small-p limit, rather than total hardware costs. This quadratic relation explains why a longer coherent evolution can support a smaller initial success probability. This scaling also marks the scope of the present mechanism: the interior target follows specifically from Grover interference, coherent access to θA_θ and θ†A_θ , and a verifier that can mark accepted trajectories without measurement. Other coherent inference maps may generate different training objectives. Exact classical evaluation in the present experiments isolates this coupling between training and inference; implementing the same loop on quantum hardware additionally requires coherent evaluation of the verifier and a suitable method for estimating gradients. VI Results VI.1 Grover-based training preserves path diversity We first tested whether training produced the interior success probability predicted by Eq. (9). Under the classical single-attempt objective, the distribution of the pre-amplification success probability pip_i became bimodal. Questions that were learned accumulated near pi=1p_i=1, whereas the remaining questions accumulated near pi=0p_i=0 [Fig. 4(b)]. The same behavior occurred in CoNet and in both quantum models, showing that quantum parameterization alone did not prevent policy collapse. Training with the Grover objective instead produced a peak near the predicted value p∗(q)p^*(q) for every tested inference depth q. Thus the analytic optimum of the Grover dynamics was also a stable target of the training dynamics. To diagnose the training objective, we used the adaptive rule G≤qG_≤ q, which allowed at most q circuit applications and stopped at the Grover round nearest the first maximum for each question. It yielded mean training accuracy above 0.950.95 at every tested q. All held-out comparisons below instead used a fixed-depth protocol that applied the full q circuit operations without question-specific stopping. Applying this fixed depth to the training set reduced its accuracy to 0.770.77 at q=9q=9, because questions with a larger initial pip_i reached their maximum earlier and were then rotated past it (Supplemental Material). The two objectives also produced different ensembles of successful paths. Classical single-attempt training concentrated most of the successful probability on one route [Fig. 1(b)]. Grover-based training retained several routes [Fig. 1(c)]. The accuracy-weighted inverse participation ratio (IPR), which counts the effective number of successful paths, increased from 1.61.6 at q=3q=3 to 5.75.7 at q=9q=9 for B=32B=32 (Supplemental Material). This quantity measures path diversity, not pairwise interference between the recorded paths. The control analysis below traces this retention to the interior target itself: a classical loss trained toward the same target preserves at least as much diversity. Figure 4: Grover-based training produces an interior success target and preserves accuracy at matched inference cost. (a) The classical single-attempt objective increases monotonically with the pre-amplification success probability p. The Grover success probability instead reaches its first maximum at p=p∗(q)p=p^*(q); arrows show the corresponding training directions. (b) Distributions of pip_i for B=32B=32, computed exactly over 3232 question-pool seeds. Classical single-attempt training drives both classical and quantum models toward pi=0p_i=0 or 11, whereas Grover-based training concentrates them near p∗(q)p^*(q). Curves are smoothed histograms of the displayed data. (c) Mean training accuracy versus the number B of training question–answer pairs at q=3q=3. Grover-based training exceeds the best result among 2727 classical controls granted the same three circuit applications, at every tested B. Bands span the minimum and maximum values across question-pool seeds; control definitions and plotting details are given in the Supplemental Material. VI.2 Performance at matched inference cost We compared quantum and classical inference using the same number q of applications of the reasoning circuit A. A quantum inference with r Grover rounds used q=2r+1q=2r+1 applications: one for state preparation and two per round. The matched classical method used the same q applications for q independent trajectories. Thus q counts forward or inverse uses of the reasoning circuit; verifier evaluations and reflections are reported separately in the Supplemental Material. This comparison isolates the inference mechanism; it does not include the hardware costs of reversible computation, trajectory memory, or fault tolerance. The performance difference increased with inference depth [Table 1]. For B=32B=32 and q=9q=9, corresponding to four Grover rounds, table-based QuCoNet reached held-out accuracy 0.4070.407, and the neural quantum AI model reached 0.4960.496. The strongest classical control reached 0.1260.126 at the same inference cost. The two quantum AI models therefore achieved 3.23.2 and 3.93.9 times the held-out accuracy of the classical control. At q=3q=3, QuCoNet remained below the classical control; from q=5q=5 onward both quantum models were higher. Each entry in Table 1 used the same fixed value of q for every question and did not use pip_i to choose when to stop. The increase was a property of training, rather than only of applying a deeper circuit: when models trained at different values of q were evaluated at a common depth, the held-out accuracy still increased with the value of q used during training (Supplemental Material). Table 1: Held-out accuracy at matched inference cost. The learned systems were trained on B=32B=32 question–answer pairs and evaluated with q circuit applications. Entries are means over independent replicas; parentheses give replica-to-replica standard deviations in the last digits. The two quantum-model rows use 3232 replicas. For the tabular models, replicas vary the question pools while fixing the optimization seed; for the neural model, the question-pool and model-initialization seeds vary together. The classical row reports the best result among 2727 classical controls at each q and data split, using 3232 replicas per control. Each quantum model used the same fixed q for every question. The uniform-policy row provides a diversity-preserving reference rather than a learned solution. Complete control definitions and training-set results are given in the Supplemental Material. applications q 3 5 7 9 QuCoNet 0.042(20) 0.147(34) 0.272(39) 0.407(45) neural quantum AI 0.073(17) 0.193(25) 0.340(30) 0.496(43) best classical 0.071(23) 0.091(27) 0.109(24) 0.126(25) uniform policy + Grover 0.077(4) 0.204(9) 0.367(15) 0.544(20) We next asked whether a longer coherent evolution allows a policy of the same size to support more question–answer pairs. Figure 5 summarizes this capacity comparison; its quantitative interpretation follows after the control analysis below. Figure 5: Coherent inference increases the number of question–answer pairs supported by a policy of fixed size trained at each budget. (a) Mean training accuracy versus the number B of training question–answer pairs at matched values of q. Solid curves show Grover-based training and inference; dashed curves show classical best-of-q (the matched protocol using q independent trajectories) training and inference with the same 720720-parameter table-based policy. The dotted line at 0.950.95 defines B0(q)B_0(q) as the largest supported training-set size. Error bars are central 68%68\% bootstrap intervals from 1616 shared question pools. Panel (a) shows q=3,7,13q=3,7,13; all six odd values from q=3q=3 to 1313 are used in panel (b). (b) The extracted B0(q)B_0(q) values and finite-range power-law fits. The coherent result approximately follows 1/p∗(q)1/p^*(q), whereas the classical capacity increases more slowly. Complete sampling and fitting procedures are given in the Supplemental Material. VI.3 Controls isolate joint training and interference At each value of q, the classical reference in Table 1 was the best result among 2727 training and inference controls. These included single-attempt and repeated-sampling objectives, entropy regularization, and controls using the same table-based policy as QuCoNet (Supplemental Material). All of these controls observe only the final verified outcome of complete trajectories, whether estimated from sampled verdicts or computed as its exact expectation (Supplemental Material); classical algorithms that exploit the known transition graph, such as breadth-first search, solve this benchmark exactly and lie outside the access model compared here. At B=32B=32 and q=3q=3, Grover-trained QuCoNet reached training accuracy 0.9530.953, compared with 0.7290.729 for the strongest classical control [Fig. 4(c)]. A control applying Grover amplification only after classical training reached 0.9190.919. Its trained probabilities spread around the interior value instead of concentrating on it, so the single round converted them imperfectly. We also asked whether a classical loss could train the policy directly toward the same numerical target. A capped loss stopped rewarding a question once pip_i exceeded p∗(3)=0.25p^*(3)=0.25, but did not penalize probabilities that moved above the target. After one fixed-depth Grover round, this control reached training accuracy 0.7060.706 (Supplemental Material). A symmetric loss that penalized deviations on both sides of p∗(q)p^*(q) reproduced the held-out accuracies of Grover-based training when it was paired with the same coherent inference. It also preserved at least as much path diversity, with accuracy-weighted IPR 9.39.3 against 5.85.8 at q=9q=9 on shared question pools (Supplemental Material), so the retained diversity follows from the interior target rather than from the Grover form of the loss. Thus classical optimization could reproduce the numerical target, but the final performance still required the quantum amplification associated with that target. For example, three independent samples at p=0.25p=0.25 succeed with probability 0.5780.578, whereas one Grover round reaches unit success. Further controls are reported in the Supplemental Material. The untrained uniform table policy provided a reference for the path diversity removed by training [Table 1, last row]. Followed by Grover amplification, it reached the highest held-out accuracy because it had not specialized to the training questions. However, it performed nearly identically on the training and held-out sets and therefore represented no learned solution. Its success probabilities also lie so deep in the small-p tail that no question reaches its Grover maximum within the tested budgets, so this reference cannot bring any designated question set to the near-unit accuracy that trained policies reach at q=3q=3 (Supplemental Material). At q=9q=9, the trained quantum models retained 7575–91%91\% of this reference accuracy on held-out questions. The strongest matched classical control retained just under a quarter. These comparisons were insensitive to the stopping convention and persisted across the full range of B and on a second random-regular graph family. At B=32B=32, allowing the stopping rule to use pip_i changed the held-out values in Table 1 by less than 0.0120.012. In a size scan, the untrained model’s lead over Grover-trained QuCoNet decreased from 1.7×1.7× at N=120N=120 to within question-pool variation at N=480N=480, while the trained model’s lead over the classical control increased. On the harder distance-77, M=9M=9 questions, the trained neural quantum AI model matched the untrained reference (Supplemental Material). VI.4 Reasoning capacity The smaller target p∗(q)p^*(q) at larger q reduced the pre-amplification success probability required for each training question. We therefore tested whether policies of this fixed size, trained separately at each budget q, could support more question–answer pairs as that budget increased. For each q, we defined B0(q)B_0(q) as the largest training-set size B for which the mean accuracy after adaptive Grover inference (G≤qG_≤ q) remained above 0.950.95 [Fig. 5(a)]. This capacity increased from B0=33B_0=33 at q=3q=3 to B0=450B_0=450 at q=13q=13. It approximately followed 1/p∗(q)1/p^*(q), and a finite-range fit gave B0∝q1.74B_0 q^1.74 [Fig. 5(b)]. The fitted exponent depends on the threshold and on the inference protocol: at a 0.900.90 threshold, where the fixed-depth protocol of Table 1 also yields a complete ladder, the adaptive and fixed-depth exponents are 2.072.07 and 1.691.69, a gap confirmed on the four audit pools measured under both protocols (2.042.04 against 1.691.69), while the 0.950.95 criterion is not reliably attainable under fixed depth (Supplemental Material). The scale of these fits verifies the mechanism expectation that capacity tracks 1/p∗(q)1/p^*(q), which grows as q2q^2 at large q. For the matched classical best-of-q control with the same table-based policy, the corresponding capacity increased only from 1111 to 2828 question–answer pairs and fitted B0cl∝q0.62B_0 cl q^0.62. The fitted exponents differed by 1.121.12, with a 95%95\% bootstrap interval of [0.98,1.31][0.98,1.31]; the classical protocol involves no stopping choice, and a gap of about one unit persists under the unified fixed-depth comparison at the 0.900.90 threshold (Supplemental Material). Thus, over the measured range, the coherent amplification budget increased the number of questions supported by a fixed-size policy trained at that budget substantially faster than classical repetition. These are finite-range empirical fits, not asymptotic complexity exponents. VII Conclusion and Outlook Slow thinking can be viewed as dynamics over reasoning trajectories. An autoregressive LLM defines a statistical distribution over possible action sequences, but each inference run follows only one sampled sequence. A quantum AI model can instead evolve a coherent superposition of many sequences. In a general quantum readout, different histories can interfere when their amplitudes are recombined; in the Grover realization studied here, this recombination acts on the collective accepted and rejected components. Quantum slow thinking is therefore a discrete path integral over reasoning trajectories: the reasoning horizon sets the space of histories, while interference determines how strongly different answers are represented. Here we make this idea trainable using Grover amplitude amplification. Classical RLVR rewards sampled trajectories that reach the correct answer. Once one strategy succeeds more often, training repeatedly reinforces it and may gradually suppress competing strategies. With a finite number of Grover rounds, by contrast, the highest final success can occur while the success probability before interference is still below one. Training therefore need not force every problem to be solved almost certainly before the quantum evolution begins. In our models, this altered training pressure preserves multiple successful routes while increasing the probability of obtaining the correct answer. The essential mechanism is not the use of quantum parameters alone: the same quantum models undergo policy collapse when trained with the classical single-attempt objective. It is the joint design of training and quantum interference that mitigates policy collapse. Notably, the gain requires only this coarsest, ensemble-level interference: no phase relation between individual reasoning paths is used anywhere in the construction. We demonstrate this mechanism on a 2×32× 3 sliding-puzzle benchmark, in which the target configuration is known but the sequence of moves leading to it must be discovered. Both the table-based QuCoNet and the parameter-sharing neural quantum AI model retain branching ensembles of reasoning paths. At four Grover rounds, corresponding to nine applications of the reasoning circuit, they achieve 3.23.2 and 3.93.9 times the held-out accuracy of the strongest matched classical controls, respectively, and retain 7575–91%91\% of the held-out accuracy of the untrained diversity-preserving reference, which none of the trained policies surpasses on the held-out questions of this solution-dense benchmark. If q denotes the number of applications of the reasoning circuit, the number of question–answer pairs supported by a policy of fixed size, trained at each budget, grows approximately as q1.74q^1.74 under coherent quantum inference over the tested range, compared with q0.62q^0.62 under classical repetition. These results establish quantum slow thinking as a trainable inference paradigm: the interior target set by Grover inference preserves exploratory diversity, and the interference converts interior success probabilities into verified performance. The known-target benchmark allows every completed trajectory to be checked by an exact verifier. In generic question answering, however, the correct answer is not supplied in advance. A learned verifier or value model would then estimate the correctness of candidate answers and coherently convert this estimate into a phase, without measuring or destroying the superposition of reasoning paths. Learning this evaluator jointly with the reasoning policy is a direct route from the present construction toward general quantum reasoning. On the readout side, general non-diagonal measurements and learned path-sensitive verifiers would engage interference between individual reasoning paths, a resource the present two-sector mechanism leaves untouched and a natural place to look for further advantages. A physical realization will additionally require coherent memory, reversible implementation of the learned evaluator, and control of noise and of fault-tolerance costs. Classical slow thinking converts additional inference time into more numerous or longer sampled trajectories. Quantum slow thinking converts the same resource into longer coherent evolution over a superposition of reasoning histories. Because these histories remain coherent until their amplitudes are recombined, exploration and selection become parts of the same quantum dynamics. On the benchmark studied here, this two-sector interference architecture enables quantum slow thinking to maintain high verified accuracy without collapsing the diversity of reasoning paths, while substantially outperforming matched classical slow-thinking baselines. Quantum-AI architectures with richer interference may yield further advantages, either by preserving still more trajectory diversity or by improving performance along other dimensions; determining what these architectures can achieve remains an open direction for future work. Acknowledgements. X.C. and K.C. are supported by the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant No. XDB1680102, the National Key Research and Development Program of China under Grant No. 2024YFA1408604, and the National Natural Science Foundation of China under Grants No. 12474245 and No. 12447103. X.C. is also supported by the China Postdoctoral Science Foundation under Grant No. 2026M793770. X.-H.D. thanks the Shenzhen Science and Technology Program (KQTD20200820113010023) and the Innovation Program for Quantum Science and Technology (2024ZD0300400). References [1] J. Wei, X. Wang, D. Schuurmans, M. Bosma, B. Ichter, F. Xia, E. H. Chi, Q. V. Le, and D. Zhou, Chain-of-thought prompting elicits reasoning in large language models, in Advances in Neural Information Processing Systems, Vol. 35 (2022) p. 24824–24837. [2] D. Guo, D. Yang, H. Zhang, et al., DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning, Nature 645, 633 (2025). [3] C. Snell, J. Lee, K. Xu, and A. Kumar, Scaling LLM test-time compute optimally can be more effective than scaling model parameters, arXiv:2408.03314 (2024), arXiv:2408.03314 . [4] B. Brown, J. Juravsky, R. Ehrlich, R. Clark, Q. V. Le, C. Ré, and A. Mirhoseini, Large language monkeys: Scaling inference compute with repeated sampling, arXiv:2407.21787 (2024), arXiv:2407.21787 . [5] D. Kahneman, Thinking, Fast and Slow (Farrar, Straus and Giroux, New York, 2011). [6] D. Silver, A. Huang, C. J. Maddison, et al., Mastering the game of Go with deep neural networks and tree search, Nature 529, 484 (2016). [7] C. B. Browne, E. Powley, D. Whitehouse, et al., A survey of monte carlo tree search methods, IEEE Transactions on Computational Intelligence and AI in Games 4, 1 (2012). [8] Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. K. Li, Y. Wu, and D. Guo, DeepSeekMath: Pushing the limits of mathematical reasoning in open language models, arXiv:2402.03300 (2024), arXiv:2402.03300 . [9] Y. Yue, Z. Chen, R. Lu, A. Zhao, Z. Wang, Y. Yue, S. Song, and G. Huang, Does reinforcement learning really incentivize reasoning capacity in LLMs beyond the base model?, in Advances in Neural Information Processing Systems (NeurIPS), Vol. 38 (2025) arXiv:2504.13837 . [10] S. Yuan, J. Chen, J. Zheng, M. Li, L. Feng, D. Wang, T. Xiang, T. Liu, and B. An, Understanding diversity collapse in RLVR via the lens of overtraining, arXiv:2606.15455 (2026), arXiv:2606.15455 . [11] G. Cui, Y. Zhang, J. Chen, L. Yuan, et al., The entropy mechanism of reinforcement learning for reasoning language models, arXiv:2505.22617 (2025), arXiv:2505.22617 . [12] F. Chen, A. Raventós, N. Cheng, S. Ganguli, and S. Druckmann, Rethinking fine-tuning when scaling test-time compute: Limiting confidence improves mathematical reasoning, arXiv:2502.07154 (2025), arXiv:2502.07154 . [13] G. D. Paparo, V. Dunjko, A. Makmal, M. A. Martin-Delgado, and H. J. Briegel, Quantum speedup for active learning agents, Physical Review X 4, 031002 (2014). [14] A. Katabarwa and N. Karimatari, Quantum projective simulation with Hamiltonian evolution: A study in reinforcement learning, arXiv:1708.00123 (2017), arXiv:1708.00123 . [15] G. Franceschetto and A. Ricou, Demonstration of quantum projective simulation on a single-photon-based quantum computer, Physical Review A 110, 062613 (2024). [16] S. Jerbi, C. Gyurik, S. Marshall, H. J. Briegel, and V. Dunjko, Parametrized quantum policies for reinforcement learning, in Advances in Neural Information Processing Systems, Vol. 34 (2021) arXiv:2103.05577 . [17] J. Zeng, Y. Wu, J.-G. Liu, L. Wang, and J. Hu, Learning and inference on generative adversarial quantum circuits, Physical Review A 99, 052306 (2019). [18] A. Hamann and S. Wölk, Performance analysis of a hybrid agent for quantum-accessible reinforcement learning, New Journal of Physics 24, 033044 (2022). [19] V. Saggio, B. E. Asenbeck, A. Hamann, et al., Experimental quantum speed-up in reinforcement learning agents, Nature 591, 229 (2021). [20] T. H. Su, S. Shresthamali, and M. Kondo, Quantum framework for reinforcement learning: Integrating Markov decision process, quantum arithmetic, and trajectory search, Physical Review A 111, 062421 (2025a), arXiv:2412.18208 . [21] T. H. Su, S. Shresthamali, and M. Kondo, Scalable quantum reinforcement learning on NISQ devices with dynamic-circuit qubit reuse and Grover optimization, arXiv:2509.16002 (2025b), arXiv:2509.16002 . [22] Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Physical Review A 48, 1687 (1993). [23] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous, One-dimensional quantum walks, in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC) (2001) p. 37–49. [24] J. Kempe, Quantum random walks: an introductory overview, Contemporary Physics 44, 307 (2003). [25] X. Cai, S. Hu, T. Wang, Y. Huang, P. Zhang, Y. Deng, and K. Chen, Learning-at-criticality in large language models for quantum field theory and beyond, Chinese Physics Letters 42, 120002 (2025). [26] S. Hu, X. Cai, Y. Huang, Z. Yao, L. Zhang, P. Zhang, Y. Deng, and K. Chen, Emergent slow thinking in LLMs as inverse tree freezing, arXiv:2509.23629 (2025), arXiv:2509.23629 . [27] L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the 28th Annual ACM Symposium on Theory of Computing (1996) p. 212–219. [28] G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Contemporary Mathematics 305, 53 (2002). [29] M. Boyer, G. Brassard, P. Høyer, and A. Tapp, Tight bounds on quantum searching, Fortschritte der Physik 46, 493 (1998). [30] S. Dernbach, A. Mohseni-Kabir, S. Pal, M. Gepner, and D. Towsley, Quantum walk neural networks with feature-dependent coins, Applied Network Science 4, 76 (2019). [31] D. Dong, C. Chen, H. Li, and T.-J. Tarn, Quantum reinforcement learning, IEEE Transactions on Systems, Man, and Cybernetics, Part B 38, 1207 (2008). [32] S. Wiedemann, D. Hein, S. Udluft, and C. B. Mendl, Quantum policy iteration via amplitude estimation and Grover search – towards quantum advantage for reinforcement learning, Transactions on Machine Learning Research (2023), arXiv:2206.04741 . [33] R. M. Wilson, Graph puzzles, homotopy, and the alternating group, Journal of Combinatorial Theory, Series B 16, 86 (1974). [34] R. J. Williams, Simple statistical gradient-following algorithms for connectionist reinforcement learning, Machine Learning 8, 229 (1992). [35] Y. Chow, G. Tennenholtz, I. Gur, V. Zhuang, B. Dai, S. Thiagarajan, C. Boutilier, R. Agarwal, A. Kumar, and A. Faust, Inference-aware fine-tuning for best-of-N sampling in large language models, arXiv:2412.15287 (2024), arXiv:2412.15287 . [36] R. J. Bell and P. Dean, Atomic vibrations in vitreous silica, Discussions of the Faraday Society 50, 55 (1970). [37] F. Wegner, Inverse participation ratio in 2+ϵ2+ε dimensions, Zeitschrift für Physik B 36, 209 (1980). [38] T. J. Yoder, G. H. Low, and I. L. Chuang, Fixed-point quantum search with an optimal number of queries, Physical Review Letters 113, 210501 (2014). [39] C. H. Bennett, Logical reversibility of computation, IBM Journal of Research and Development 17, 525 (1973). [40] D. P. Kingma and J. Ba, Adam: A method for stochastic optimization, in International Conference on Learning Representations (ICLR) (2015) arXiv:1412.6980 . [41] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, Attention is all you need, in Advances in Neural Information Processing Systems, Vol. 30 (2017) p. 5998–6008. Supplemental Material for “Do Quantum AIs Dream in Paths? Path-Integral Slow Thinking through Grover Interference” This Supplemental Material derives the trajectory formulation and the Grover-induced interior training target, proves monotonicity for terminal-outcome-only classical sampling, and reports the complete task construction, model and circuit definitions, control families, validation tests, scaling analysis, and reproducibility information underlying the main text. SI Classical trajectory measures and coherent path sums Let x denote an input problem and γ=(z1,…,zT)γ=(z_1,…,z_T) a complete sequence of intermediate reasoning states or actions, where T is the trajectory length. Let θ denote the trainable model parameters. An autoregressive policy assigns Pθ[γ|x]=∏t=1Tπθ(zt|x,z<t)=e−ILLM[γ|x].P_θ[γ|x]= _t=1^T _θ(z_t|x,z_<t)=e^-I_LLM[γ|x]. (S1) Here πθ(zt|x,z<t) _θ(z_t|x,z_<t) is the normalized conditional probability of the next state, z<t=(z1,…,zt−1)z_<t=(z_1,…,z_t-1) is the complete prefix, and ILLM[γ|x]=−logPθ[γ|x]I_LLM[γ|x]=- P_θ[γ|x] is the trajectory surprisal. No Markov assumption is made: every factor may depend on the complete prefix. The probability of an answer y is a statistical sum over the trajectories that produce it, and one inference run samples a realized trajectory from this distribution. A quantum reasoning circuit assigns amplitudes rather than probabilities, AQ[γ|x]=∏t=1Tαθ(zt|x,z<t)=|AQ[γ|x]|eiSQ[γ|x]/ℏ,A_Q[γ|x]= _t=1^T _θ(z_t|x,z_<t)=|A_Q[γ|x]|e^iS_Q[γ|x]/ , (S2) where αθ _θ is a complex conditional transition amplitude, SQS_Q denotes the accumulated effective phase action, and ℏ fixes the phase unit and may be set to one; SQS_Q is defined modulo 2πℏ2π . We denote the corresponding state-preparation circuit by A. Let |γ⟩|γ denote the basis state containing the complete trajectory record, and let MyM_y be the positive measurement operator, or POVM element, associated with outcome y. The outcome probability is the double path sum PQ(y|x)=∑γ,γ′AQ[γ|x]AQ∗[γ′|x]⟨γ′|My|γ⟩.P_Q(y|x)= _γ,γ A_Q[γ|x]A_Q^*[γ |x] γ |M_y|γ . (S3) The diagonal terms define a classical mixture of histories; the off-diagonal terms encode coherent recombination. Equations (S2) and (S3) give the discrete path-integral representation used in the main text. For a general MyM_y, off-diagonal matrix elements allow different histories to interfere when the measurement coherently recombines them. In the Grover realizations studied here, fresh which-path registers keep individual action sequences orthogonal. The verifier applies a common phase to the collective accepted sector; by itself, this phase operation changes no probability. The state-preparation reflection, implemented with †A and A, converts the phase contrast between the accepted and rejected components into a coherent rotation of their weights. No pairwise interference between individual path records contributes to the success probability or to the path-resolved observables studied here, nor is such pairwise interference required for amplitude amplification. SII Tasks, models, and training protocol SII.1 Reasoning tasks and data splits The primary task is goal-directed navigation on the configuration graph of a 2×32× 3 sliding puzzle. Under single slides the puzzle has 6!/2=3606!/2=360 reachable configurations and a hole-position-dependent branching number. To obtain a regular graph we restrict the hole to the two middle-column cells and use three self-inverse compound moves: a vertical slide V exchanging the hole between the two middle cells, and two three-slide cycles L and R that carry the hole to the other middle cell around the left or right pair of corners. Slide moves preserve the parity of tile inversions [33], so of the 2×5!=2402× 5!=240 middle-column arrangements exactly the 120120 sharing the goal’s parity are reachable and form a closed component: N=120N=120 nodes of degree K=3K=3, each generator being its own inverse. A question is an ordered pair (Q,A)(Q,A) at shortest-path distance 33–66; a trajectory succeeds on its first arrival at A within M=8M=8 moves. For each question-pool seed we draw 192192 pairs. The first B pairs form the training set and the last 6464 form the held-out set, shared by all model families and all values of B for that seed; the two sets contain no common pair (zero collisions across all question-pool seeds and training-set sizes). Unless noted otherwise, reported tabular points pool 3232 question-pool seeds while fixing the optimization seed at 4242. A pool–optimizer-seed cross-audit at B=32B=32 (Grover q=3q=3, Grover q=9q=9, and best-of-four objectives on pools 11–44, each retrained with three additional optimization seeds) found within-pool optimizer-seed standard deviations of 0.0100.010–0.0260.026 across objectives and splits, comparable to the matched pool-to-pool values of 0.0080.008–0.0280.028 (both ranges exclude the saturated Grover q=9q=9 training cells, where both spreads vanish), so the question-pool ensembles are not hiding optimization scatter. Every Grover q=9q=9 run reached training accuracy 1.0001.000 under the adaptive rule, and no Grover-trained run of the audit placed any training question at the deterministic boundary (pi>0.98p_i>0.98) at these budgets, whereas the best-of-four control placed up to two of 3232 questions there per pool. The q=7,9q=7,9 scans away from B=32B=32, the random-regular replication, and the large-size scans use eight question-pool seeds. The large-B capacity scan of Sec. SIX uses the same construction with 1616 larger pools: 768768 pairs per seed, extended to 12801280 pairs for B>704B>704, with the first 704704 training pairs and the held-out set identical across the two pools so that the two curves stitch together. For q=3,5,7,9q=3,5,7,9, the coherent grid is B∈8,16,32,64,96,128,192,256,384,512,704B∈\8,16,32,64,96,128,192,256,384,512,704\; the q=11q=11 scan adds B=768,896,1024B=768,896,1024, and the q=13q=13 scan additionally includes B=1216B=1216. The matched classical capacity control uses those same 1616 768768-pair pools, the same ordered training prefixes, and B∈1,2,4,6,8,12,16,24,32,40,48,64,96,128B∈\1,2,4,6,8,12,16,24,32,40,48,64,96,128\. Here and below, q denotes the total number of forward or inverse applications of the reasoning circuit. Thus q=2r+1q=2r+1 for r Grover rounds. Throughout the Supplemental Material, accuracy denotes the mean final success probability over the specified set of question–answer pairs. As a topology control, we generate uniform random 33-regular graphs with the same N, horizon, distance filter, and question protocol. A size scan uses N∈120,240,480N∈\120,240,480\ at B=32B=32. These are not intended as language tasks; they isolate the relation among policy support, a verifiable trajectory predicate, and the inference map. SII.2 Classical and quantum walkers The classical table policy, CoNet, has unconstrained real parameters, or logits, ℓ∈ℝN×K ^N× K. At node x it selects edge k with probability πx(k)=eℓxk/∑k′eℓxk′ _x(k)=e _xk/ _k e _xk . The sampled baseline uses REINFORCE [34], binary rewards, and a per-question mean baseline. Exact-gradient controls differentiate through the absorbing Markov dynamic program described in Sec. SIII. A repeated-sampling (best-of-k) control, which succeeds if any of k independent completed trajectories passes the verifier [35], minimizes ℒcl,k=−∑i[1−(1−pi)k].L_cl,k=- _i [1-(1-p_i)^k ]. (S4) The autoregressive (sequentially conditioned) quantum table policy, QuCoNet, has a coin Cx=exp(iHx)C_x= (iH_x) at every node, where HxH_x is a real symmetric 3×33× 3 matrix. It therefore has six real parameters per node and 720720 parameters in total. At step s, a question-dependent basis channel cs∈0,…,K−1c_s∈\0,…,K-1\ enters the coin. The length-M channel sequence is a deterministic code for (Q,A)(Q,A), formed by interleaving the base-K digits of the start and target node labels and repeating or truncating the pattern to length M. At M=8M=8 the truncation drops one base-33 digit of each label, so the code is not injective: across the 3232 mainline pools, 1818 training questions share a channel sequence with another training question of the same pool, and 6666 of the 2,0482,048 held-out questions (3.2%3.2\%) share one with a training question. The node labels themselves carry no information the model can exploit: retraining the Grover q=3q=3 objective on the eight mainline pools after two independent uniformly random node relabelings (graph, questions, and answers relabeled together; optimization seed fixed) reproduced the native results: the relabeled-minus-native differences are −0.006±0.032-0.006± 0.032 in training accuracy and +0.007±0.023+0.007± 0.023 held-out (mean ± sample standard deviation over the 1616 runs), both consistent with zero. If xkx_k denotes the neighbor reached from node x through local edge k, the training-time transition probability is P(x→xk∣cs)=|Cx[cs,k]|2.P(x→ x_k c_s)=|C_x[c_s,k]|^2. (S5) Fresh path-record registers make different action histories orthogonal. Hence the position marginal during training is exactly the classical Markov chain of Eq. (S5), even though the same gates define a coherent unitary at inference. The classical single-attempt objective trains the success probability of one completed attempt, whereas the Grover-based objective trains the success after coherent inference. Their losses are −∑ipi- _ip_i and −∑iG≤q(pi)- _iG_≤ q(p_i) (Sec. SV), respectively. Both use exact gradients. The two models are matched in graph interface, horizon, training-set size, and optimization protocol, not in raw parameter count (360360 stochastic logits versus 720720 real coin parameters). This mismatch cannot explain the central comparison: the monotonicity result in Sec. SIV applies to any policy architecture when classical procedures access only the terminal binary verifier outcome of each independent completed sample, while the exact-gradient classical controls remove estimator noise altogether. SIII Exact evaluation and path support For a question (Q,A)(Q,A), depth-first enumeration visits all action sequences of length at most M. A branch terminates and contributes its probability when it first reaches A; branches below probability 10−1510^-15 are pruned. An equivalent memory-light computation propagates a position occupancy vector, zeros the target outflow at every step, and accumulates its inflow. Enumeration and this absorbing dynamic program agree to 10−910^-9 on random checkpoints; the remaining precision is set by the stored float32 parameters, which can overshoot unit probability by up to ∼4×10−6 4× 10^-6 on saturated questions; all read-out maps clip p to [0,1][0,1] before use. Enumeration also gives individual successful-path probabilities wjw_j. With w~j=wj/∑jwj w_j=w_j/ _jw_j, we quantify the effective number of routes [36, 37] by IPR=1∑jw~j2.IPR= 1 _j w_j^2. (S6) Batch means are weighted by question success probability, ∑ipiIPRi/∑ipi _ip_iIPR_i/ _ip_i, so dead questions do not inflate or dilute the measure. Figure S1 shows that Grover-based training retains several effective routes, whereas the effective path number under single-attempt and repeated-sampling training approaches one. The figure shows q=3,5q=3,5; the retained ensemble grows with the intended number of circuit applications, with accuracy-weighted ⟨IPR⟩=1.6, 2.8, 4.2, 5.7 =1.6,\,2.8,\,4.2,\,5.7 on training questions at B=32B=32 for q=3,5,7,9q=3,5,7,9 (held-out values within 0.40.4 of these). The weighted means summarize broad per-question distributions: pooled over the eight shared pools at B=32B=32, the training IPR at q=3q=3 has median 1.191.19 with interquartile range [1.00,1.96][1.00,1.96] (23%23\% of questions above 22), and at q=9q=9 median 5.505.50 with interquartile range [3.45,8.35][3.45,8.35] (92%92\% above 22, maximum 16.216.2). The inverse participation ratio (IPR) is a path-count diagnostic; it is not evidence for interference among those routes. It is also strictly invariant under the amplification itself: r Grover rounds multiply the entire accepted component by a common factor, so the conditional weight of every accepted path, w~j=wj/∑jwj w_j=w_j/ _jw_j, is exactly unchanged, and the training loss, a function of pip_i alone, is constant on surfaces of fixed pip_i regardless of how the success weight distributes over routes. Any change in IPR is therefore a property of the optimization dynamics toward the interior target, not of the Grover map, consistent with the two-sided control of Sec. SVII. Figure S1: Effective successful-path number on training (left) and held-out (right) questions. Grover-based training retains multiple effective paths, whereas single-attempt and best-of-two objectives approach the single-path reference (dotted). The inverse participation ratio is weighted by each question’s success probability. Figure S2 makes the same point on a single question by drawing where the trained success probability flows. Single-attempt-trained CoNet and single-attempt-trained QuCoNet both collapse onto one route, so the collapse is a property of the objective rather than the substrate; only Grover-based training holds the question at p∗(3)p^*(3) with a branching ensemble. Panels (b),(c) of the main-text opening figure reproduce the left (classical single-attempt) and right (Grover-trained) panels. Figure S2: Success-probability flow for one training question (B=32B=32, question-pool seed 11; start, green circle; target, purple star), with nodes ordered left to right by graph distance from the start and each edge’s width giving its share of the question’s total success probability. Left: the single-attempt-trained CoNet policy collapses onto a single route (p=0.993p=0.993, IPR=1.10IPR=1.10). Middle: the QuCoNet policy of identical architecture, trained with the single-attempt objective, collapses in the same way (p=1.000p=1.000, IPR=1.04IPR=1.04), so the collapse comes from the objective, not the substrate. Right: the same QuCoNet policy trained for one Grover round holds the question at p∗(3)=1/4p^*(3)=1/4 with a branching ensemble (p=0.250p=0.250, IPR=3.56IPR=3.56), colored by orthogonal path-record channel. The inverse participation ratio counts effective routes and is not evidence of interference among them. All matched-cost comparisons count applications of the reasoning circuit A or its inverse. Preparing the state costs one application, and each Grover round adds †A and A, so r rounds use q=2r+1q=2r+1 circuit applications. The coherent procedure is therefore compared with q independent classical attempts. This cost model excludes the r coherent verifier reflections and also assigns no cost to the classical verifier outcomes. The comparison point moves in either direction when these choices vary. If a coherent reflection costs λv _ v circuit-application units and a classical verification costs λc _ c units, the budget that funds r Grover rounds funds k=[(2r+1)+λvr]/(1+λc)k=[(2r+1)+ _ vr]/(1+ _ c) classical attempts. Our convention λv=λc=0 _ v= _ c=0 gives k=q=2r+1k=q=2r+1. Charging only the quantum side (λv=1 _ v=1, λc=0 _ c=0) raises the classical allowance at r=4r=4 from 99 to 1313 attempts; recomputing the best-of-k envelope of all 2727 controls at k=13k=13 raises the strongest classical held-out mean from 0.1260.126 to 0.1560.156, so the main-text ratios 3.23.2 and 3.93.9 become 2.62.6 and 3.23.2 with the ordering unchanged. Charging both sides equally (λv=λc=1 _ v= _ c=1) instead lowers the classical allowance to k=(3r+1)/2≈1.5rk=(3r+1)/2≈ 1.5r, fewer than in our comparison. Coherent synthesis of the verifier reflection is an additional physical resource and is discussed as a limitation in Sec. SX. SIV Classical sample-access monotonicity The main-text monotonicity observation includes two assumptions that are essential for its scope. First, the verifier is sound: an accepted completed trajectory is a valid solution. Second, the procedure is success maximizing: once at least one accepted solution has been observed, it retains or returns an accepted solution rather than intentionally converting that event into failure. These assumptions exclude perverse rules such as “reject whenever a success is observed,” which are nonmonotone but useless for solving the task. Proof. Let p<p′p<p . Couple attempt t at the two single-attempt success probabilities by drawing the same ut∼Uniform[0,1]u_t [0,1] and declaring the outcome successful at p if ut<pu_t<p, and at p′p if ut<p′u_t<p . Realize the procedure’s private randomness as a single sequence drawn once and shared between the two worlds, and let τ be the first attempt at which the coupled outcomes differ, that is, the first t with ut∈[p,p′)u_t∈[p,p ). Before τ the two worlds hold identical verifier histories and private randomness, hence take identical adaptive actions: when to stop, whether to draw again, which verified solution to return. If τ never occurs before the procedure stops, the two runs coincide and either both succeed or both fail. If it does occur, the run at p′p has just observed a verified success, and a sound, success-maximizing rule must therefore succeed. The run at p may still succeed later, but cannot outperform a success. On every realization the run at p′p therefore does at least as well, and its success probability is nondecreasing in p. □ The statement is deliberately an access theorem, not a theorem that every conceivable classical algorithm is monotone in every internal policy parameter. It covers procedures that act on independent completed samples only through their verifier verdicts; a rule that keys on trajectory content can correlate with the identity of the policy and evade the coupling. It does not cover a procedure with coherent access to amplitudes, a procedure that changes the underlying generator between attempts using extra semantic information, or a manually imposed nonmonotone utility. Tree search may allocate samples much better than naive independent repeated sampling; so long as success is obtained by observing verified classical trajectories, however, increasing the probability of an otherwise identical successful draw cannot hurt. SV Amplification objective and stopping rule Write the prepared state as |ψ⟩=|0⟩=sinϑ|ψacc⟩+cosϑ|ψrej⟩,sin2ϑ=p,0≤ϑ≤π2,|ψ =A|0 = \,| _acc + \,| _rej , ^2 =p, 0≤ ≤ π2, (S7) where |ψacc⟩| _acc and |ψrej⟩| _rej are the normalized projections onto the verifier-accepted and rejected subspaces. Standard amplitude amplification [27, 28] gives Gq(p)=sin2(qϑ)G_q(p)= ^2(q ) for an odd number q of circuit applications. To avoid deliberate overshoot in the training objective, we use G≤q(p) G_≤ q(p) =Gq^(p,q)(p), =G_ q(p;q)(p), (S8) q^(p,q) q(p;q) =2min[q−12,r∗(p)]+1, =2 \! [ q-12,r^*(p) ]+1, r∗(p) r^*(p) =max[0,round(π4arcsinp−12)]. = \! [0,round ( π4 p- 12 ) ]. Here r∗(p)r^*(p) is the optimal round count of quantum search [29]; for p=0p=0 we set r∗(0)=0r^*(0)=0, so G≤q(0)=0G_≤ q(0)=0. The interior maxima p∗(q′)=sin2π2q′,q′=3,5,…,q,p^*(q )= ^2\! π2q , q =3,5,…,q, (S9) are the base probabilities amplified exactly to unit success. Among these, p∗(q)p^*(q) is the smallest and is the maximum reached from the initialized small-p regime. For q≥5q≥ 5, smaller secondary peaks in the histograms of Fig. S3 lie near higher-order maxima from which fewer rounds suffice. Figure S3: Exact training-set distributions of the per-question success probability after Grover-based training for q=3,5,7,9q=3,5,7,9 (B=32B=32, 3232 question-pool seeds each). Dashed lines mark the predicted interior optimum p∗(q)=sin2[π/(2q)]p^*(q)= ^2[π/(2q)] of Eq. (S9); panel titles give the intended number of circuit applications and its interior optimum. The distribution concentrates at p∗(q)p^*(q) in every panel; smaller peaks at q≥5q≥ 5 lie near higher-order maxima requiring fewer than q circuit applications. Equation (S8) is an objective-level optimal-stop convention; it nominally uses p. The main held-out comparison does not rely on it: every held-out accuracy in the main text is reported under a fixed-depth protocol that always uses all q circuit applications and never consults p. The convention is nearly immaterial there: at B=32B=32 the fixed-depth sequence 0.0420.042, 0.1470.147, 0.2720.272, 0.4070.407 for q=3,5,7,9q=3,5,7,9 lies within 0.0120.012 of the G≤qG_≤ q values 0.0430.043, 0.1490.149, 0.2780.278, 0.4180.418, and the difference stays below 0.0260.026 over the entire training-set-size grid. The held-out per-question probabilities lie almost entirely below the lowest maximum, where the two rules coincide. The convention matters only for the near-unity training-set accuracies at q≥5q≥ 5, where the smaller peaks at higher-order maxima overshoot the deepest fixed-depth protocol: the G≤qG_≤ q training accuracies at B=32B=32, which are 0.9530.953, 1.0001.000, 1.0001.000, 1.0001.000 for q=3,5,7,9q=3,5,7,9 (question-pool standard deviation 0.0210.021 at q=3q=3 and below 10−310^-3 beyond), fall to 0.9530.953, 0.9400.940, 0.8460.846, 0.7720.772 when every question receives all q circuit applications. A fixed-depth implementation can recover the training-side values with a fixed-depth GqG_q training objective, fixed-point amplitude amplification [38], or an amplitude-estimation stopping rule [28]. Training-side accuracies in the main text use the G≤qG_≤ q convention of Eq. (S8), which is the objective being optimized; held-out numbers use the fixed-depth protocol throughout. Training at larger q also produces a better held-out policy at every tested inference depth, rather than merely applying deeper inference to the same residual probability. Table S1 evaluates each model trained at q for every inference depth q′q : every column increases down the rows. The q=9q=9-trained model has the highest mean even at a single round, and the q=3q=3-trained model reaches only 0.1110.111 at nine circuit applications, little more than a quarter of the q=9q=9-trained value. Table S1: Cross-depth evaluation on held-out questions at B=32B=32: rows are training objectives and columns are the fixed inference depths, using all q′q circuit applications; the optimal-stop rule raises the diagonal by at most 0.0120.012 and the off-diagonal cells, which overshoot more often, by up to 0.030.03. The q=5q=5–99 entries at q′=3q =3 lie within one seed standard deviation of one another. q′=3q =3 q′=5q =5 q′=7q =7 q′=9q =9 trained at q=3q=3 0.042 0.067 0.091 0.111 trained at q=5q=5 0.069 0.147 0.215 0.263 trained at q=7q=7 0.076 0.176 0.272 0.349 trained at q=9q=9 0.079 0.192 0.309 0.407 At B=32B=32, the results across inference depths are summarized in Table I of the main text of the main text; its classical row is the best-performing control at each q in the audit of Sec. SVII (Table S3), granted the same q verified samples. On this puzzle the one-round tabular system is not yet better on held-out questions; its decisive held-out separation begins at larger q. This is why the main text reports the entire sequence rather than presenting a universal one-round held-out advantage. Figure S4: Performance at increasing coherent inference depth. The Grover-trained model is evaluated at its matched number q of circuit applications under the G≤qG_≤ q rule, which stays within 0.0260.026 of the fixed-depth protocol on held-out questions. The exact best-of-two and capped c=0.25c=0.25 walkers are evaluated with nine attempts on training (a) and held-out (b) questions across training-set size B on the sliding puzzle; the best-performing control in Table S3 at each q is slightly stronger. Grover-based objectives at larger q improve throughout and the ordering with q stays monotone, while these fixed-depth classical references do not separate. The held-out panel (b) is the full-B view of the B=32B=32 ladder in Table I of the main text. The dedicated 1616-pool scan used for the main-text capacity fit is reported in Sec. SIX. SVI Coherent inference circuit Figure S5 summarizes the construction of this section: the walk that trains as a classical Markov chain is, run coherently, a reasoning circuit whose accepted and rejected components are rotated by the Grover reflections. Figure S5: Classical sampling and coherent inference use the same local walk. Left: CoNet samples one action from π(⋅∣x)π(· x) at each node and returns one trajectory per attempt. Middle: QuCoNet applies the local coin operator CxC_x and a reversible shift S at each step. The shift moves to the neighboring node while recording the action in a fresh which-path register, giving =∏sSCxA= _sSC_x. Measuring these records reproduces the CoNet trajectory distribution. Right: when the same reasoning circuit is kept coherent, the verifier reflection I−2PaccI-2P_acc gives the accepted and rejected components opposite phases. The reflection about the prepared state converts this phase difference into amplitude amplification. After r rounds the accepted-sector angle is (2r+1)ϑ(2r+1) . No pairwise interference between individual path records is required. SVI.1 State preparation and reversible shift Let ℋposH_pos be the position space spanned by the N graph nodes and let ℋcsH_c_s be the K-dimensional record for the action taken at step s. The coherent Hilbert space is ℋ=ℋpos⊗ℋc1⊗⋯⊗ℋcM,dimℋ=NKM=787,320.H=H_pos _c_1 ·s _c_M, =NK^M=787,320. (S10) It embeds in ⌈log2N⌉+M⌈log2K⌉=23 _2N +M _2K =23 qubits, counting only the logical position and path-record registers; verifier workspace, comparator, and readout ancillas are additional (Sec. SX). Unused basis states are padded by identity action. Step s applies the current node’s coin operator to register csc_s and then a flip-flop shift, a reversible operation that moves to a neighboring node while recording the traversed action, |x,k⟩⟼|nbr(x,k),rev(x,k)⟩.|x,k |nbr(x,k),rev(x,k) . (S11) Here nbr(x,k)nbr(x,k) is the neighboring node reached through local edge k, and rev(x,k)rev(x,k) is the label of the same edge at that neighbor. This reverse-edge label records the action needed to undo the move. The resulting map is a permutation of the joint position-register basis and hence a unitary; a neighbor column by itself need not be a permutation. Eight steps form A. SVI.2 First-arrival oracle without measurement Absorbing classical evaluation stops on first arrival, whereas a unitary circuit cannot stop by measurement. Each final basis state nevertheless contains a complete action record, and the reversible shifts decode it to a unique path. The accepted-subspace projector PaccP_acc is therefore diagonal: it accepts a final basis state if and only if its decoded path first reaches the target at some step s≤Ms≤ M. A reversible implementation [39] computes this Boolean predicate into an ancilla, applies a phase, and uncomputes it. The Grover iterate can be written =(2|0⟩⟨0|−I)†(I−2Pacc).Q=A(2|0 \! 0|-I)A (I-2P_acc). (S12) Although |ψacc⟩| _acc is a high-dimensional entangled superposition of many trajectories, Q preserves the two-dimensional plane spanned by |ψacc⟩| _acc and |ψrej⟩| _rej . The standard rotation therefore depends only on p=⟨ψ|Pacc|ψ⟩p= ψ|P_acc|ψ . Orthogonal which-path records do not obstruct the rotation, and no cancellation among individual accepted paths is needed. SVI.3 Full-state verification We propagated every training and held-out question for the one-round-trained model at question-pool seed 1 and B=32B=32 through the full state space of Eq. (S10). The circuit and enumeration are independent implementations. Table S2 shows single-precision agreement. The first row is the central implementation check: the coherent, never-absorbed circuit has exactly the same accepted-subspace weight as the absorbing-state calculation used for training. In Table S2, pienump_i enum is the independently enumerated success probability and sin2ϑi=pi ^2 _i=p_i for question i. Table S2: Full-Hilbert-space verification. Maxima are over 3232 training and 6464 held-out questions. The after-round value in the last row is the mean of G3(pi)G_3(p_i) over questions, not G3G_3 of the mean. Check value maxi|⟨ψi|Pacc|ψi⟩−pienum| _i| _i|P_acc| _i -p_i enum| 3.6×10−73.6× 10^-7 maxi|‖Pacc|ψi⟩‖2−sin2(3ϑi)| _i|\|P_accQ| _i \|^2- ^2(3 _i)| 1.5×10−51.5× 10^-5 maxi|‖Pacc2|ψi⟩‖2−sin2(5ϑi)| _i|\|P_accQ^2| _i \|^2- ^2(5 _i)| 1.3×10−51.3× 10^-5 Mean training p / after one round 0.243/0.9700.243/0.970 SVII Classical controls and diagnostic questions The controls separate five possible explanations of the observed difference: gradient-estimator noise, model architecture, loss shape, post-training coherent inference, and the favorable uniform prior of the small graph. Does estimator noise explain the difference? Differentiating Eq. (S4) removes Monte Carlo gradient-estimation noise and implements the inference-aware classical objective [35] directly. It closely reproduces the sampled best-of-two result across B. At B=32B=32, the exact-gradient and sampled models reach 0.6570.657 and 0.6590.659, respectively, when granted three attempts, below the one-round system’s 0.9530.953. This comparison isolates the objective from the estimator. What is the strongest terminal-outcome-only baseline? Table S3 audits the 27 controls that access only the final binary verifier outcome. They include single-attempt, best-of-k up to k=64k=64, capped, and entropy-regularized objectives on the softmax walker, and the same classical objectives trained on the coin architecture itself, which the which-path structure makes a classical Markov model. All matched-cost comparisons in the main text use the best result from this family at each q and data split. At three circuit applications the strongest member on training questions is the QuCoNet-architecture best-of-four control (0.7290.729); on held-out questions the strongest members are the best-of-k controls with large k (0.0710.071 to 0.1260.126 from three to nine applications). The family exhibits a trade-off between accuracy and coverage. Objectives that perform well at small q concentrate probability on fewer questions and generalize less well, while best-of-6464 retains broader coverage but cannot convert it into high accuracy at small q. No single control achieves both. The single-attempt, best-of-two, capped, and large-k softmax families span the full B grid; the entropy-regularized and QuCoNet-architecture families exist at B∈8,32,128B∈\8,32,128\. At each B, the reported classical control is the best available member of this family. In Table S3, “single-attempt, Adam” denotes the earlier 120120-epoch Adam run, whereas “single-attempt, protocol-matched” uses the same 200200-epoch optimization and model-selection schedule as the core Grover-trained tabular runs. Table S3: Control audit at B=32B=32: best-of-q accuracy of the 27 classical objectives on training and held-out questions. Results pool 3232 question-pool seeds for every family. “QuCoNet arch.” rows train a classical objective using the same local coin operators as QuCoNet. The main text’s “strongest classical control” is the best result in this table at each q and data split. training held-out objective q=3q=3 q=5q=5 q=7q=7 q=9q=9 q=3q=3 q=5q=5 q=7q=7 q=9q=9 single-attempt, REINFORCE 0.602 0.621 0.632 0.639 0.057 0.066 0.071 0.075 single-attempt, Adam 0.537 0.545 0.551 0.555 0.049 0.052 0.055 0.057 single-attempt, protocol-matched 0.533 0.540 0.544 0.547 0.045 0.048 0.050 0.052 single-attempt, exact gradient 0.535 0.541 0.545 0.548 0.047 0.050 0.052 0.053 best-of-2, sampled 0.659 0.701 0.716 0.723 0.053 0.060 0.065 0.068 best-of-2, exact 0.657 0.699 0.714 0.720 0.054 0.060 0.065 0.068 best-of-4, exact 0.681 0.755 0.784 0.796 0.062 0.074 0.081 0.086 best-of-8, exact 0.664 0.780 0.831 0.856 0.070 0.087 0.099 0.107 best-of-16, exact 0.601 0.750 0.829 0.873 0.071 0.091 0.105 0.116 best-of-32, exact 0.486 0.655 0.762 0.832 0.065 0.090 0.109 0.124 best-of-64, exact 0.352 0.508 0.623 0.710 0.058 0.085 0.107 0.126 capped c=0.25c=0.25 0.607 0.736 0.799 0.831 0.070 0.090 0.104 0.114 capped c=0.50c=0.50 0.656 0.714 0.732 0.740 0.061 0.072 0.078 0.083 capped c=0.75c=0.75 0.628 0.660 0.675 0.684 0.052 0.059 0.064 0.068 single-attempt +λH+λ H, λ=0.01λ=0.01 0.558 0.566 0.570 0.572 0.055 0.065 0.072 0.078 single-attempt +λH+λ H, λ=0.03λ=0.03 0.558 0.565 0.568 0.570 0.060 0.072 0.080 0.086 single-attempt +λH+λ H, λ=0.1λ=0.1 0.521 0.525 0.527 0.528 0.058 0.071 0.081 0.089 best-of-2 +λH+λ H, λ=0.01λ=0.01 0.664 0.705 0.720 0.726 0.061 0.074 0.082 0.088 best-of-2 +λH+λ H, λ=0.03λ=0.03 0.666 0.705 0.719 0.725 0.064 0.080 0.090 0.098 best-of-2 +λH+λ H, λ=0.1λ=0.1 0.643 0.684 0.698 0.704 0.065 0.084 0.097 0.107 QuCoNet arch., single-attempt 0.592 0.598 0.600 0.602 0.018 0.021 0.023 0.024 QuCoNet arch., best-of-2 0.699 0.733 0.745 0.750 0.014 0.017 0.019 0.021 QuCoNet arch., best-of-4 0.729 0.802 0.829 0.840 0.017 0.021 0.024 0.027 QuCoNet arch., best-of-8 0.707 0.820 0.871 0.896 0.017 0.022 0.025 0.028 QuCoNet arch., best-of-16 0.648 0.796 0.871 0.912 0.017 0.023 0.028 0.031 QuCoNet arch., best-of-32 0.564 0.735 0.835 0.894 0.019 0.027 0.033 0.038 QuCoNet arch., best-of-64 0.437 0.610 0.728 0.809 0.023 0.034 0.044 0.052 What does the uniform policy diagnose? The untrained uniform walker, evaluated on the same pools, has mean first-arrival probability p¯=0.0088 p=0.0088 on both splits (the two pools have the same graph-level mean under uniform routing). On the held-out split, classical sampling raises its accuracy to 0.0260.026, 0.0430.043, 0.0600.060, 0.0760.076 at q=3,5,7,9q=3,5,7,9 verified attempts, while fixed-depth amplification reaches 0.0770.077, 0.2040.204, 0.3670.367, 0.5440.544; the corresponding training values differ by at most 0.0010.001. The G≤qG_≤ q values equal the fixed-depth values: every uniform success probability in these pools lies so deep in the small-p tail that the optimal iteration count exceeds the largest tested q. These numbers bound the trained systems from two sides (main-text Table I and its discussion): no trained system matches the uniform walker’s held-out accuracy after coherent inference, and the uniform walker matches no trained system on the training questions. Paired by question pool at q=9q=9, the held-out difference is −0.127±0.032-0.127± 0.032 (95%95\% confidence, eight pools) for Grover-trained QuCoNet minus the uniform reference, and +0.281±0.016+0.281± 0.016 (3232 pools) against the strongest classical control. This uniform reference is also specific to a small, solution-dense instance. Under uniform routing the mean first-arrival probability falls with graph size (0.0280.028, 0.0190.019, 0.0160.016 on the random-regular held-out pools at N=120N=120, 240240, 480480) and with question difficulty (0.1020.102 to 0.00440.0044 across graph distance 33 to 77 on the puzzle, the last at horizon M=9M=9), and the amplified value falls with it: the uniform walker’s one-round held-out lead over the natively trained walker on the random-regular family shrinks from 1.7×1.7× at N=120N=120 (0.217±0.0250.217± 0.025 against 0.125±0.0320.125± 0.032) through 1.4×1.4× at N=240N=240 to statistical parity at N=480N=480 (0.129±0.0170.129± 0.017 against 0.113±0.0340.113± 0.034), while the trained walker’s lead over the classical control grows from 1.8×1.8× to 3.1×3.1× over the same range, and at graph distance 77 the neural quantum AI model already matches the uniform value (0.187±0.0170.187± 0.017 against 0.1980.198 after three rounds). Nothing here depends on the training set: the uniform walker’s accuracy after coherent inference comes from the uniform prior itself, a consequence of the small, solution-dense benchmark rather than a strategy available on hard instances. Does coherent inference rescue a classically trained policy? The decisive test of the objective grants every classically trained policy the quantum inference circuit. The capped walker (c=0.25c=0.25), evaluated with one fixed-depth round, reaches 0.7060.706 on training questions against the Grover-trained 0.9530.953: only 45%45\% of its trained probability lies within [0.2,0.3][0.2,0.3], while 41%41\% has drifted above 0.30.3, where the rotation overshoots (its own design point; two fixed-depth rounds reduce it to 0.2210.221). The neural capped policy fails the same way, drifting to a mean trained p=0.51p=0.51 where one round returns 0.460.46. The strongest hybrid of any control is the QuCoNet-architecture best-of-3232 walker plus one fixed-depth round, at 0.9190.919, still below the Grover-trained value. On held-out questions, controls trained with large-k objectives perform well after coherent inference at shallow depth (best-of-6464 plus fixed-depth inference: 0.1320.132, 0.2050.205, 0.2550.255, 0.2990.299 for q=3,5,7,9q=3,5,7,9) but fall behind the models trained at larger q from q=7q=7 (0.2720.272, 0.4070.407). The one-sided classical objectives neither constrain probabilities that drift above the target nor sustain the gain at greater inference depth. The Grover-based objective supplies a gradient on both sides of the optimum. A two-sided classical objective with the same property is examined below. Does the coin architecture alone prevent collapse? The same coins, trained on −∑ipi- _ip_i, undergo the same boundary concentration as CoNet. For the question of the main-text opening figure, this single-attempt-trained coin policy has p=1.000p=1.000 and IPR=1.04IPR=1.04 [Fig. S2], against p=0.250p=0.250 and IPR=3.56IPR=3.56 under the one-round loss. Thus unitarity of the parameter matrix is insufficient; coherent inference must define the training target. Can generic diversity regularization preserve probability for later coherent inference? We add the Shannon-entropy bonus λ∑xH[πx]λ _xH[ _x], where H[πx]=−∑kπx(k)logπx(k)H[ _x]=- _k _x(k) _x(k), to the single-attempt and best-of-two objectives for λ∈0.01,0.03,0.1λ∈\0.01,0.03,0.1\ at B∈8,32,128B∈\8,32,128\, with 3232 question-pool seeds at B=32B=32 and eight at B∈8,128B∈\8,128\. The bonus either changes matched-cost accuracy by only a few points or degrades it when uniform-routing pressure overwhelms reward. It keeps some small-p held-out mass alive but does not supply the question-wise stationary point of Eq. (S9). Can classical training import the interior target? The exact classical loss −∑imin(pi,c)- _i (p_i,c) with c∈0.25,0.5,0.75c∈\0.25,0.5,0.75\ stops rewarding a question once pip_i exceeds the cap c. At c=0.25c=0.25 it is the strongest capped control, and the stronger of the two controls tracked across training-set size in Fig. S4. It demonstrates that classical training can use a target supplied from outside the main-text monotonicity statement. But sampling raises a base probability p=0.25p=0.25 only to 1−(0.75)k1-(0.75)^k, while one Grover round raises the interior optimum to unity. The control is trained with exact gradients and therefore has no Monte Carlo gradient-estimation noise; the remaining cost difference occurs at inference. For its per-question probabilities pi\p_i\, let k be the smallest number of independent verified attempts whose mean best-of-k accuracy matches the Grover-trained model. At B=32B=32, k≈5×105k≈ 5× 10^5 to match the 0.9530.953 training accuracy after amplification (4×1054× 10^5–5×1055× 10^5 across the at-capacity sizes B=16B=16 and 3232; at smaller B both models saturate and at larger B the lower coherent training accuracy is cheaper to match); this tail-sensitive catch-up cost arises from the small-p portion of the learned distribution and is not implied by C3[p∗(3)]C_3[p^*(3)] alone. Its one-sided objective also has zero gradient for questions that drift above c. To isolate that asymmetry, we also test the symmetric loss ℒ2s=∑i(pi−c)2L_2s= _i(p_i-c)^2 with c=p∗(q)c=p^*(q). This removes the one-sidedness and converges near the target: on the QuCoNet architecture the trained probabilities lie within c±0.05c± 0.05 (fraction 0.910.91 at c=p∗(3)c=p^*(3) and 1.001.00 at the higher-order maxima), and classical inference remains limited to the best-of-k success of a distribution at c. Trained on the same coin architecture as the quantum model, this control tracks the Grover-trained held-out sequence (0.0390.039, 0.1570.157, 0.3030.303, 0.4790.479 against 0.0420.042, 0.1470.147, 0.2720.272, 0.4070.407 under fixed-depth inference), matching within seed spread at q≤5q≤ 5 and sitting slightly above it at the larger q (paired by pool, the two-sided-minus-native held-out difference is −0.001±0.006-0.001± 0.006, +0.007±0.007+0.007± 0.007, +0.033±0.010+0.033± 0.010, +0.061±0.011+0.061± 0.011 across q=3,5,7,9q=3,5,7,9), where the Grover-based loss leaves probability at higher-order maxima that the deepest fixed-depth protocol over-rotates; its held-out mean p stays at the uniform value. The same holds for path diversity: over the eight shared question pools, the accuracy-weighted training IPR of this control is 1.621.62, 3.253.25, 6.146.14, 9.319.31 at q=3,5,7,9q=3,5,7,9, against 1.621.62, 2.832.83, 4.054.05, 5.795.79 for native Grover training, so a classical loss aimed at the same interior target retains at least as many successful routes (the excess at large q mirrors the accuracy excess above: the two-sided loss pins every question at the first maximum, whereas the native loss leaves some weight at higher-order maxima). The held-out sequence, and the retained path diversity, are therefore set by the interior target, not by the particular loss used to reach it. Its fixed-depth training accuracy after coherent inference is 0.9520.952, 1.0001.000, 1.0001.000, 1.0001.000, without the higher-order peaks that reduce the native loss under the deepest fixed-depth protocol (the G≤qG_≤ q rule absorbs that difference). On the softmax walker the same loss also lifts held-out mean p (0.009→0.0280.009→ 0.028 at c=p∗(3)c=p^*(3)) and with it the fixed-depth sequence (0.1270.127, 0.2290.229, 0.3750.375, 0.5030.503), but this is a transfer effect of the shared per-node softmax rows on the small dense puzzle graph, not of the loss: it is absent on the coin architecture, and on the random-regular family the same control gains little and falls below the natively trained walker at every size. Both versions are oracle-assisted diagnostics rather than deployed procedures: the constant c=p∗(q)c=p^*(q) is supplied by the quantum analysis rather than derived from the inference dynamics the policy will use. The loss itself is classically estimable: the product of two independent verifier verdicts, (X−c)(Y−c)(X-c)(Y-c) with X,Y∼Bernoulli(p)X,Y (p), has expectation (p−c)2(p-c)^2, and pairing it with the score function yields an unbiased gradient estimator, whose sample complexity we do not evaluate here. By contrast, the Grover target is derived from the deployed circuit: under the fixed-depth protocol, the measured binary outcome is an unbiased sample of Gq(p)G_q(p) with no per-question input; realizing the adaptive G≤qG_≤ q additionally requires the stopping choice q^(p,q) q(p;q), which itself uses an estimate of p (Sec. SV). The present experiments nevertheless train with exact classically computed probabilities and gradients; a hardware implementation would require a corresponding stochastic-gradient estimator. Optimization and selection. Tabular runs are evaluated every epoch and neural runs every ten epochs; neural results report the final epoch. Archived tabular checkpoints are selected by the training value of the loss being optimized for the classical best-of-k, capped, and two-sided objectives, and by the highest raw single-attempt rate otherwise. For single-attempt objectives the two rules coincide. For the Grover-based objective they do not, because the raw rate is not monotone in the objective. At moderate and large training-set sizes, the interior optimum and IPR form a long plateau after convergence and final-versus-best selection is immaterial, but at the smallest B/NB/N (B/N≲0.1B/N 0.1) the raw rate peaks during an early transient that overshoots the interior optimum, so the archived checkpoint there predates convergence. For this reason the capacity scan of Sec. SIX reads every run history at its converged final epoch; reading the archived best-rate epoch instead depresses the low-B plateau into a spurious dip and shifts the capacity thresholds by up to four percent. A protocol-identical 200200-epoch classical rerun reproduces the archived 120120-epoch baseline (single-attempt 0.2570.257 versus 0.2520.252 at B=128B=128). Some question pools at the largest q converge to a deterministic boundary solution rather than the lowest interior maximum. We report all pools; eliminating these optimization failures is not part of the present claim. The core exact-gradient tabular runs use Adam [40] for 200200 epochs with learning rate 0.050.05, softmax logits, and seed 4242 for each archived configuration; reported tabular ensembles vary the question-pool seed, not this optimization seed. The neural coin runs use 200200 epochs, learning rate 0.0030.003, gradient-norm clipping at 1.01.0, evaluation every ten epochs, and the architecture stated below. These settings, including objective and seed, are stored with each run in the archived JSON configuration or history file. The separate model-width sweep uses at most 300300 epochs with early stopping after a minimum of 6060 epochs. SVIII A parameter-sharing neural quantum AI model The table-based model above uses one local 3×33× 3 unitary coin operator per node, parameterized by the six independent entries of a real symmetric generator and hence 720720 real parameters in total. A row is updated by every question whose paths visit that node, so questions interact where their reachable prefixes overlap. We repeat the core measurements with the table replaced by a single neural network. A two-layer, four-head prefix-conditioned transformer [41] (dmodel=32d_model=32 and 29,19029,190 parameters, with dmodeld_model denoting the hidden width) reads the question, the target, and the move history of a branch and emits the six independent entries of the same eiHe^iH coin. The circuit still uses one fresh record register per step. Every question now shares every parameter, and the coin conditions on the whole path prefix rather than the current node. The walk stays a record-controlled unitary, block-diagonal in the which-path basis, so the classical-Markov training structure and the objective theory of Secs. SV–SVI carry over unchanged. Per-question success is again evaluated exactly, here by a level-synchronous sweep of the prefix tree, validated against independent enumeration to 4×10−84× 10^-8. Unless noted, B=32B=32 on the puzzle and results use 3232 replicas; the same replica index selects both the question pool and the neural-network initialization. All neural runs, Grover-based and classical alike, use one implementation with identical architecture, optimizer, learning rate, epoch count, and checkpoint selection; the training loss is the only changed setting, so the classical controls are not under-tuned relative to the Grover-trained runs. The interior optimum is set by the objective, not the parameterization. Table S4 collects the main matrix, and Fig. S6(a) shows the trained distributions. The Grover-based objective places the neural policy near the predicted interior optimum (q=3q=3: mean initial success p=0.2493±0.0036p=0.2493± 0.0036, every question in the interior band 0.02<pi<0.980.02<p_i<0.98, ⟨G≤3⟩=0.9995 G_≤ 3 =0.9995), whereas the same network under the single-attempt and best-of-two objectives concentrates at the boundary (interior fraction 0.050.05 and 0.230.23). At larger q, the neural means lie systematically above the optima (0.1080.108, 0.0660.066, 0.0450.045 against 0.0950.095, 0.0500.050, 0.0300.030 for q=5,7,9q=5,7,9), an offset of the shared parameterization that costs little accuracy after coherent inference. For the neural policy at q≥5q≥ 5, the trained probabilities are therefore near, rather than exactly at, the analytic optimum. Boundary concentration is a property of the classical target, reproduced on a policy whose memorization structure, in which all parameters are shared, is the opposite of the table’s. Table S4: Parameter-sharing neural quantum AI model at B=32B=32 (3232 replicas), mean± deviation. “Interior” is the fraction of questions with 0.02<pi<0.980.02<p_i<0.98. For the Grover-based rows, “held-out” is accuracy at the matched q under the fixed-depth protocol, using all q circuit applications; the optimal-stop rule adds at most 0.0030.003, and the ratio is this held-out accuracy divided by the strongest same-architecture classical control’s best-of-q value; for the control rows, “held-out” is single-attempt accuracy (their best-of-q values appear in the text). objective initial success p interior held-out ratio Grover-based, q=3q=3 0.249±0.0040.249± 0.004 1.001.00 0.073±0.0170.073± 0.017 3.0×3.0× Grover-based, q=5q=5 0.108±0.0100.108± 0.010 1.001.00 0.193±0.0250.193± 0.025 5.1×5.1× Grover-based, q=7q=7 0.066±0.0070.066± 0.007 1.001.00 0.340±0.0300.340± 0.030 6.9×6.9× Grover-based, q=9q=9 0.045±0.0040.045± 0.004 1.001.00 0.496±0.0430.496± 0.043 8.2×8.2× single-attempt 0.776±0.0810.776± 0.081 0.050.05 0.0080.008 — best-of-two 0.915±0.0540.915± 0.054 0.230.23 0.0080.008 — capped c=p∗(3)c=p^*(3) 0.512±0.0400.512± 0.040 1.001.00 0.0090.009 — Figure S6: Grover-based training with a parameter-sharing neural quantum AI model (two-layer prefix-conditioned transformer, 29,19029,190 shared parameters; 3232 replicas unless noted). (a) At B=32B=32, Grover-based training retains interior per-question probabilities near the predicted optima, whereas the single-attempt objective concentrates them near the boundaries. (b) At fixed model size, the training plateau persists through the tested range of B while held-out accuracy increases; the dotted line marks the 720720-parameter table’s capacity threshold at the 0.900.90 level of the separate four-pool audit (B0(0.9)=40B_0^(0.9)=40; the sixteen-pool 0.950.95 definition of the main text gives B0(3)≈33B_0(3)≈ 33). (c) At matched q, the neural quantum AI model exceeds both the per-node table and the strongest same-architecture classical control. Parameter sharing retains held-out performance; importing a target does not import coherent inference. On held-out questions the neural policy trained at q=3q=3 already exceeds the strongest matched-cost control of its own architecture (3.0×3.0× at three circuit applications) [Fig. S6(c)], where the per-node table does not exceed the matched classical control at q=3q=3. Against the strongest control of any parameterization (the large-k softmax family of Table S3), the neural sequence is 1.01.0, 2.12.1, 2.92.9, 3.63.6 times across q=3,5,7,9q=3,5,7,9: indistinguishable from parity at q=3q=3 (0.073±0.0170.073± 0.017 versus 0.070±0.0260.070± 0.026) and ahead from q=5q=5. Among the neural controls themselves, the single-attempt and best-of-two policies reach 0.0220.022 and 0.0190.019 at best-of-three and stay below the capped family at every q, so the capped control is the strongest same-architecture comparator throughout. It keeps essentially every question interior (fraction 0.9980.998), but its mean trained probability is 0.5120.512, not the supplied optimum p∗(3)=0.25p^*(3)=0.25; the one-sided cap therefore demonstrates interior retention rather than faithful target placement. The symmetric two-sided control above provides the direct target-import diagnostic. Granted best-of-q at each q, the capped controls (c=p∗(3)c=p^*(3) and c=p∗(5)c=p^*(5), which agree to 0.0020.002) run 0.024,0.038,0.049,0.0600.024,0.038,0.049,0.060 across q=3,5,7,9q=3,5,7,9, while the Grover-trained policy runs 0.073,0.193,0.340,0.4960.073,0.193,0.340,0.496: a held-out lead that widens monotonically from 3.0×3.0× to 8.2×8.2× as q increases [Fig. S6(c)], and that beats the per-node table’s corresponding values (0.042,0.147,0.272,0.4070.042,0.147,0.272,0.407) at every q. Granting the capped network quantum inference instead, one fixed-depth round raises its held-out accuracy to 0.0630.063, close to the Grover-trained 0.0730.073 at q=3q=3. In these terminal-outcome-only sampling controls, supplying the target does not supply coherent amplification, and the gap grows with difficulty and size: at graph distance 77 (horizon M=9M=9, eight replicas) the policy trained at q=7q=7 reaches 0.1870.187 held-out, 10.4×10.4× the strongest same-architecture control, and on random 33-regular graphs at N=480N=480 the policy trained at q=5q=5 reaches 8.8×8.8×; the comparators for these two claims are retrained on the harder task and the larger graphs, respectively. Capacity as a function of model size. Sweeping B at fixed 2929k parameters, the q=3q=3 Grover-training plateau remains above the capacity threshold throughout the tested range [Fig. S6(b)]: ⟨G≤3⟩=0.9995,0.9952,0.9909,0.9939,0.9802,0.9762 G_≤ 3 =0.9995,0.9952,0.9909,0.9939,0.9802,0.9762 at B=32,64,96,128,192,256B=32,64,96,128,192,256 (the last two are four replicas), still 0.9760.976 at B=256≈8B0(3)B=256≈ 8\,B_0(3) of the 720720-parameter table under the common 0.950.95 definition. The curve decreases gradually rather than showing the table model’s abrupt loss of capacity, and held-out accuracy ends higher at the largest tested B (0.073→0.0920.073→ 0.092) after a shallow dip through B=96B=96, a gain the per-node table cannot achieve. For the width sweep we use a separate 0.90.9 threshold. Its q=3q=3 capacity threshold moves outward with parameter count: B0(0.9)≈114B_0^(0.9)≈ 114 at dmodel=8d_model=8 (5.95.9k), while dmodel≥16d_model≥ 16 holds above 0.90.9 through the largest pool tested (B=256B=256, so the threshold is right-censored: it lies beyond the largest training-set size tested). This supports a qualitative outward shift of capacity with model size, though it does not fit a size exponent. The compiled neural policy remains unitary. The full-Hilbert-space verification of Sec. SVI repeats on compiled, prefix-controlled coins from trained transformer instances: the amplitude state over all KMK^M move sequences reproduces the absorbed prefix-tree probability to 8×10−78× 10^-7 (float32 network into a float64 circuit), and one Grover round through the reflection identity matches sin2(3ϑ) ^2(3 ) to 10−1410^-14 on q=3q=3 and q=9q=9 Grover-trained instances alike. The neural-coin held-out accuracies are small, so the q=3q=3 ratios carry wide relative uncertainty and the B=192,256B=192,256 points use four replicas; the classical controls are trained at B=32B=32 and reused as the matched-cost comparator. The qualitative ordering (an interior optimum, collapse under one-sided classical objectives, and a widening gap between coherent and classical inference with difficulty and size) is stable across all replicas. SIX Replication and scaling The random-regular family repeats three qualitative facts: single-attempt training concentrates the unitary model at the boundary; one-round Grover-based training retains an interior distribution; and training at larger q improves held-out accuracy after coherent inference. Across the full B grid, the q=9q=9 system achieves 1.71.7–4.64.6 times the best classical control at nine attempts in Table S3 on the puzzle, and 2.62.6–5.45.4 times on the random-regular family, whose control set lacks the large-k best-of-k sequence. On random-regular graphs, the held-out matched-cost lead remains at N=120,240,480N=120,240,480 [Fig. S7]. The training-set gap narrows with N at fixed B, as expected when capacity pressure falls: the converged coherent system holds training accuracy at or near unity at every size while the classical control rises. The held-out ratio grows from approximately 1.81.8 to 3.13.1. Figure S7: Problem-size control on random 33-regular graphs at B=32B=32. The one-round system (plotted under the G≤3G_≤ 3 optimal-stop rule; the fixed-depth values quoted in the text are up to 0.0060.006 lower) is compared with the exact best-of-two-trained classical model at three and nine samples. The training-set difference narrows as B/NB/N falls; the held-out matched-cost difference persists. Two scaling relations clarify the mechanism. First, a large-B scan on the puzzle (the 1616 extended pools of Sec. SII) uses a common 0.950.95 cutoff on mean training accuracy after inference to define the capacity threshold B0B_0. Specifically, B0B_0 is the first downward crossing of the 1616-pool mean curve, interpolated linearly in logB B; every run history is read at its final epoch (Sec. SVII). A small fraction of cells still drifts at the training horizon (the mean accuracy over the final quarter moves by more than 10−310^-3 in 9%9\% of coherent and 12%12\% of classical cells); reading a last-quarter average instead of the final epoch moves both fitted exponents by less than 0.0050.005, so the convention is immaterial at the reported precision. At q=3q=3, all 1616 individual coherent curves reach the 0.950.95 plateau. Each bootstrap draw resamples the 1616 question pools jointly for the coherent and classical scans, preserving the within-pool comparison. All 20,00020,000 draws resolve every capacity threshold. The measured capacity thresholds for q=3,5,7,9,11,13q=3,5,7,9,11,13 are B0=33,64,107,168,274,450.B_0=33,64,107,168,274,450. (S13) The log–log fit against q gives B0∝q1.739B_0 q^1.739 (R2=0.976R^2=0.976), with central bootstrap intervals [1.729,1.755][1.729,1.755] at 68%68\% and [1.718,1.771][1.718,1.771] at 95%95\%. A fit against 1/p∗(q)1/p^*(q) has exponent 0.900.90, and p∗(q)B0(q)p^*(q)B_0(q) ranges from 5.15.1 to 8.28.2. The ordinary-least-squares slope error is 0.140.14, reflecting residual departure from a perfect power law that resampling the question pools does not measure. The exponent also inherits the capacity-threshold definition: at threshold 0.900.90 it is 2.0672.067, with a 95%95\% bootstrap interval [2.034,2.098][2.034,2.098], while at 0.850.85 the largest-q threshold lies beyond the present B range and is therefore right-censored. A separate four-pool audit at the 0.900.90 threshold found that fixed-depth GqG_q inference without adaptive stopping moves the thresholds to 4040, 6868, 125125, 203203, 317317, 467467, still monotone in q, with fitted exponent 1.691.69; the adaptive rule on the same four pools gives 2.042.04, consistent with the 1616-pool value above. The protocol comparison is threshold-dependent at the edges: at the 0.950.95 level the fixed-depth mean hovers at the criterion itself and does not produce a well-defined ladder (the deepest protocol rotates early-maximum questions past their peaks, Sec. SV), while at a 0.700.70 level the two protocols nearly coincide over the range they resolve (1.661.66 against 1.711.71 across q≤7q≤ 7; the larger-q thresholds lie beyond the tested B range). Classical best-of-q success involves no stopping choice, so the coherent–classical exponent difference of about one unit persists when both sides are read under the unified fixed-depth protocol. A lower target asks less success weight of each shared routing bottleneck, allowing a fixed policy to hold more questions before frustration. For the matched classical scan, we train the same 720720-parameter coin architecture with the exact best-of-q loss in Eq. (S4), for q=3,5,7,9,11,13q=3,5,7,9,11,13, and evaluate each policy at the q for which it was trained. All settings other than the outer response function are shared with the coherent scan. A position-Markov dynamic program computes the same per-question probabilities as the full autoregressive state; a direct check finds maximum probability error 3.7×10−73.7× 10^-7, relative gradient error below 3.6×10−63.6× 10^-6, and probability disagreement 1.0×10−61.0× 10^-6 after a matched 2020-epoch Adam trajectory. At the same 0.950.95 threshold, the classical capacity thresholds are B0cl=11.3,15.3,18.3,21.7,25.5,28.3.B_0 cl=11.3,15.3,18.3,21.7,25.5,28.3. (S14) Their finite-range fit is B0cl∝q0.624B_0 cl q^0.624, with central bootstrap intervals [0.536,0.699][0.536,0.699] at 68%68\% and [0.436,0.765][0.436,0.765] at 95%95\%. At threshold 0.900.90 the exponent is 0.6180.618, with 95%95\% interval [0.573,0.712][0.573,0.712]. Thus the classical plateau is real but confined to small training sets; a scan beginning at B=8B=8 without matched values of q does not resolve it reliably. At matched q, the ratio B0/B0clB_0/B_0 cl grows from 2.912.91 to 15.8915.89 across the tested range. The fitted exponents differ by 1.1161.116 (95% bootstrap interval [0.979,1.306][0.979,1.306]) under joint resampling of the same question pools. This is a controlled finite-task separation, not an asymptotic query-complexity statement. Second, for a fixed distribution of base probabilities, classical attempts need O(1/p)O(1/p) samples to reach constant success while amplitude amplification with a phase-matched final reflection needs O(1/p)O(1/ p) applications [28]. The per-question query-count diagnostic in Fig. S8 recovers fitted slopes 1.311.31 and 0.630.63 against 1/p1/p on the finite task. The classical value exceeds unity because the exact requirement k(p)=⌈ln(1−η)/ln(1−p)⌉k(p)= (1-η)/ (1-p) , where η is the desired final success probability (here η=0.9η=0.9), is only asymptotically linear in 1/p1/p. Ignoring the integer ceiling to display the local continuum slope, one obtains dlnk/dln(1/p)=p/[−(1−p)ln(1−p)]d k/d (1/p)=p/[-(1-p) (1-p)], which rises from 1.051.05 at p=0.1p=0.1 to 1.441.44 at p=0.5p=0.5, so a single power law fitted across the resolved window lands above one, while restricting the fit to the small-p tail returns an exponent within a few percent of unity. Counting reasoning-circuit applications directly as q, the quantum fit remains closer to its 1/21/2 asymptote; integer rounding over the resolved window raises the finite-range slope to 0.630.63. These are finite-range diagnostics of the standard asymptotic maps, not a standalone end-to-end hardware speedup. Only this query-complexity diagnostic permits a phase-matched final reflection; all policy accuracies and training objectives above use the fixed-phase map of Eq. (S8). Figure S8: Finite-range check of the standard query scaling. Here one query is one application of the reasoning circuit A or its inverse. The queries required to reach per-question success 0.90.9 are plotted against inverse base probability. Classical verified sampling approaches linear growth in 1/p1/p, whereas phase-matched amplitude amplification follows the square-root scale. The final reflection uses a phase adjustment chosen to reach the target success without overshooting it by an integer Grover round. SX Scope, physical resources, and reproducibility Computational boundary. Training, sweeps, and the full coherent circuit are evaluated by exact classical calculation. This is useful for testing the mechanism because it removes sampling error and exposes the entire policy, but does not establish a quantum hardware advantage. A physical realization must pay for reversible state preparation, †A , the first-arrival oracle, ancilla cleanup, and error correction. For the neural experiment, our full-state check validates the compiled prefix-controlled unitary; it does not provide an efficient reversible implementation of the transformer. Such an implementation, or the cost of compiling its prefix-dependent coins, is an additional resource not included in the query counts. Coherence and memory. The circuit requires coherence across the full horizon and fresh which-path storage. Its logical record cost is M⌈log2K⌉M _2K qubits; the present experiment embeds the complete state in 2323 qubits before oracle ancillas. Noise can turn the accepted/rejected rotation into classical mixing and erase the benefit. No robustness threshold is inferred from the noiseless data. Reasoning scope. The task is Markovian, fixed horizon, and equipped with an exact binary verifier. The work does not yet model a language policy with growing context, tool calls, self-modification, or a verifier that is probabilistic or learned. Which-path orthogonality means that the present system does not require direct pairwise interference among semantic paths; instead, the Grover reflection recombines their amplitudes through the collective accepted and rejected sectors. It establishes the smaller but operationally precise primitive needed before richer models: coherent access to the distribution of complete reasoning trajectories. Reproduction. The training drivers, sweep launchers, analysis scripts, and distilled probability caches are collected in the paper’s code repository; the principal analysis scripts (under docs/discussion/scripts/ and notes/scripts/) include: • circuit_verify.py for Table S2; • grover_sweep_analysis.py for the interior optima and the grids at increasing q; • grover_ipr_analysis.py for path support; • blind_schedule_analysis.py for the fixed-depth evaluation, the capacity-threshold bootstrap and sensitivity, and the larger-q IPR values; • control_audit_analysis.py for the control audit (Table S3), the untrained baseline, the cross-depth matrix (Table S1), and the fixed-depth capacity thresholds; • classical_capacity_controlled.py, capacity_scaleup_analysis.py, and plot_capacity_knee.py for the matched 1616-pool capacity scan, bootstrap uncertainty from the shared question pools, threshold sensitivity, and the main-text comparison; • grover_sizescan_analysis.py for Fig. S7; • twosided_target_control.py and twosided_coin_control.py for the two-sided imported-target controls, twosided_ipr_wave.py for their path-diversity comparison, and untrained_scaling.py for the untrained walker’s size and difficulty dependence; • fixed_depth_capacity_check.py for the adaptive-versus-fixed-depth capacity protocol comparison, and cost_model_sensitivity.py for the verification-cost sensitivity; • robustness_audits.py for the pool–optimizer-seed cross-audit and the node-relabeling invariance test (relabeled pools built by relabel_qa.py); • amplification_scaling.py and grover_exchange_rate.py for query scaling. The tracked file docs/discussion/scripts/_sweep_out/capacity_scaleup_16.json stores all pool-level capacity curves and the bootstrap summaries obtained by jointly resampling the 1616 pools. The other caches store the exact success probability of every question under the reported trained models, so the tables and most figures can be re-derived from the code repository alone. Raw checkpoints and run records are not included there and are required to regenerate the training sweeps. All figures included in the manuscript are tracked artifacts so that the LaTeX package compiles from a clean checkout.