Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.11066

Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory

Ming Yang

quant-phcs.AIcs.CCSubmitted Aug 11, 2026• Announced Aug 12, 2026• 0 citations
arXivHTMLPDF

Abstract

We prove inference-time quantum coordination advantages for specified AI state-tracking tasks. A solver compresses semantic history into a future-accessible boundary state and later answers a query. We count communication $B$, persistent instance-dependent memory $M$, and local work $D$; classical recurrence, caches, tools, and recomputation are allowed and charged. The central result is a boundary-preserving semantic-compilation theorem. It maps a finite one-way, streaming, or adaptive causal task into a semantic AI interface while preserving event order and access to past input. Classical boundary-state lower bounds and quantum-memory upper bounds transfer up to explicit compiler overhead, independently of the finite-precision recurrent architecture. Two applications have classical semantics. Matched-entity synopsis QA inherits the hidden-matching separation between $O(\log N)$ qubits and $Ω(\sqrt{N})$ classical boundary bits. Continual requirements auditing inherits a Max-$k$SAT streaming separation: a recurrent solver uses $O(\log^5 n\log(1/δ))$ qubits and polylogarithmic classical workspace to obtain a $0.7172$-approximation, whereas every classical one-pass finite-information solver attaining that ratio requires $Ω(\sqrt{n})$ coordination width. As a quantum-native compiler test, a stabilizer latent-state dialogue uses $n$ qubits, while every exact finite-state classical causal online realization satisfies $B+M \ge \frac{1}{2}n^2+(\frac{3}{2}-\log_2 3)n+O(1)$. The source protocols, streaming algorithms, and stabilizer witness are imported; the new result is their architecture-independent semantic transfer. These are memory and coordination separations, not runtime or empirical advantages for present-day language models. The stabilizer result assumes exact simulation and ideal noiseless quantum memory.

Comments
Comments and suggestions are welcome on alphaXiv

Related papers

Genuine Global Kochen-Specker Contextuality as Classical Coordination Cost

Ming Yang

We formulate classical simulation of quantum correlations as coordination across a spacetime separator. All past-dependent information capable of influencing the future must cross the separator either through communicated messages or through a persistent classical state. We prove a general lower bound on this classical coordination cost in terms of the nonnegative rank of the separator correlation matrix, with approximate and amortized extensions governed by approximate nonnegative rank and Wyner common information. For sequential processes, we introduce a causal positive-realization rank that enforces consistent response and state-update maps, and we explain how bounded local computation and support-covering models arise as restricted cases. We apply the framework to genuine global Kochen--Specker contextuality, in which local subsystems are noncontextual and the tested multipartite blocks are generalized-Bell-local, while the complete empirical model has no global noncontextual explanation. At the symmetric point of a polarization--path Hardy construction, exact classical simulation requires two coordination bits, whereas the corresponding quantum separator requires one qubit. Under exact repetition, the classical lower bound is the base-two logarithm of three bits per copy; with asymptotically vanishing error, it becomes one and a half classical bits per copy, compared with one qubit per copy. We further construct a finite stabilizer--Peres--Mermin family for which the exact classical coordination cost grows quadratically with system size, while the quantum boundary cost grows only linearly. The separation applies to arbitrary finite-state causal online simulators. Establishing a constant-error quadratic separation and an intrinsic construction without flag conditioning remain open.

quant-pharXiv:2606.23577•Jun 23, 2026•0 citations

Representation-Dependent Recoverability in Quantum Compilation

Jinze Yang, Yangyang Li, Xiu-Hao Deng

Fault-tolerant compilation can disperse high-level structure: schedules split an accumulated phase across rounds, gate synthesis replaces an angle by a Clifford+$T$ word, and randomized compiling spreads rotations over sign-randomized fragments. They preserve the computation but change how cheaply a downstream compiler can recover the aggregate phase data. We formalize this representation-dependent recoverability by charging two channels: output committed before the suffix arrives, and a serialized restart state crossing the cut. For an $r$-round accumulation of a commuting layer with $m$ generators at accuracy $ε$ ($K_ε=Θ(1/ε)$), any $p$-pass compiler correct on every valid stream with failure probability at most $δ$ obeys $\overline{A}_p+(2p-1)S\geq(1-δ)m\log_2 K_ε-h_2(δ)$, where $\overline{A}_p$ is committed output and $S$ is the crossing-state cap. The bound covers compile-time randomized compiling; a memory-capped block compiler attains it within a constant factor, and direct semantic aggregation reaches compact output with logarithmic state. The two channels are not always interchangeable. A compiler whose committed prefix is executed at the cut pays a toll the state channel never pays: the entropy $\log_2\binom{m}{k}$ of the mask naming which $k$ coordinates it commits early. Compilers that defer or buffer pay none of it. We prove both directions and, with instrumented compilers under a preregistered protocol, measure a per-generator toll matching $\log_2\binom{m}{k}/k$ that vanishes for a public mask and a buffered control. Under a disclosed fixed-total-error Clifford+$T$ and surface-code model, a materialize-first pipeline costs orders of magnitude more logical $T$ states and spacetime volume than a semantic-first one. Phase semantics should therefore be preserved until aggregation whenever the interface permits.

quant-pharXiv:2609.29210•Sep 25, 2026•0 citations

Quantum memory advantage for quantum process tomography

Carlos Bravo-Prieto, Weiyuan Gong, Antonio Anna Mele

Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be $Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$, where $d_{\mathrm{in}}$ and $d_{\mathrm{out}}$ are the channel input and output dimensions, respectively, and $\varepsilon$ is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires $Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$ queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound $O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$. Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case $d_{\mathrm{in}}=1$. By contrast, coherent protocols with quantum memory achieve query complexity $Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)$. Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.

quant-pharXiv:2607.13476•Jul 16, 2026•0 citations

Readout-Dependent Prediction Rankings and Certified Noncommuting Quantum Memory

Satoshi Kawasaki

This preprint studies readout-dependent prediction in a specified classical-quantum continuous-time model with an autonomous classical source and a driven qubit memory. A dynamic model (D) is compared with a scalar-contact model (MATCH) reconstructed to match stationary contact occupancy and both directional switching fluxes. The predictor observes only the qubit memory and the declared classical record j; the target is a future binary signal at an independent exponential horizon. Two distinct results are established by exact interval certificates. At B04, (s,u,v,Omega)=(-1/16,0,0,1), D has lower Brier loss under fixed-Z readout by at least 1/5,000,000, but higher loss under each model's optimal quantum readout by at least 1/2,000,000. This is a commuting conditional-state example. Separately, at nine D-only points with u=1/8, v=0, s in {-1/16,0,1/16}, and Omega in {1/16,1/4,1}, both j sectors have squared normalized commutator norm greater than 10^-8, and the same state's gain over fixed-Z readout is greater than 10^-3. These shared nine-point bounds were extracted after certification. The standard Sylvester readout construction is explicitly attributed. The results are fixed-point statements; they do not establish a continuous parameter region, an unrestricted classical-resource advantage, a causal role of noncommutativity in the B04 reversal, or equal thermodynamic costs. Exact evidence and editable source accompany the preprint in a separate Dataset item. OpenAI ChatGPT/Codex and Anthropic Claude systems assisted the work. Their roles and the limitations of the archived checks are disclosed. AI checks are not human or institutional independent validation. This preprint is not a peer-reviewed journal article. Companion evidence and editable source: https://doi.org/10.6084/m9.figshare.33756607

•Sep 14, 2026•0 citations

Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds

Nadezhda Voronova

How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment. We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests. To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting $r$ independent matching requests requires $Ω(r)$ qubits for $r\le N^{1/2-δ}$ and every fixed $δ\in(0,1/2)$, even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through $r=Θ(\sqrt N)$. We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes. Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an $Ω(n)$ space lower bound in random edge order for large enough cycles, with consequences for several graph problems. Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.

quant-pharXiv:2610.06727•Oct 6, 2026•0 citations

History-Conditioned Quantum Error Correction under Temporally Correlated Noise: Finite-Horizon Performance and Reproducible Simulations of a Three-Qubit Phase-Error Code

TrinityLabo

This preliminary research preprint presents a reproducible numerical study of history-conditioned quantum error correction under temporally correlated noise. We consider a three-qubit phase-error code subject to a synthetic Pauli noise model with a persistent hidden noise regime. A noisy classical monitor and the accumulated syndrome/measurement history are used to estimate that regime through standard Bayesian hidden-Markov filtering, and recovery operations are selected by a causal maximum-a-posteriori rule. The central question is whether accessible temporal information can extend the finite interval over which encoded quantum information remains reliable. In 100,000 matched synthetic trajectories, survival through 20 correction rounds increases from 0.74406 for a snapshot MAP decoder to 0.91455 for the history-conditioned decoder. Under a 90% no-logical-fault survival criterion, the empirical computational-memory window increases from 6 to 25 rounds, with a simultaneous 95% lower confidence band supporting 23 rounds for the history-conditioned policy. Control experiments show that the advantage disappears when temporal predictability is removed: when the hidden regime becomes independent from round to round, the history-conditioned and snapshot policies coincide. Additional monitor and model ablations demonstrate that the benefit depends on correction-relevant temporal correlations, informative side information, and adequate calibration. The work also formulates finite-horizon survival criteria and sufficient error-budget bounds without assuming independent logical faults, while explicitly separating classical filter stability from preservation of quantum information. This study does not claim a new Bayesian filtering method, superiority over existing temporal quantum-error-correction decoders, a scalable fault-tolerance threshold, or demonstrated room-temperature quantum-computing hardware. Rather, it provides a concrete operational specialization of the broader TrinityLabo history-first framework and a small, reproducible benchmark showing how temporal inference can condition quantum recovery under specified noise assumptions. Ambient-temperature operation remains a future experimental application requiring calibrated device-level noise models, fault-prone syndrome extraction, hardware latency analysis, and comparison against established temporal decoders.

•Sep 26, 2026•0 citations
We prove inference-time quantum coordination advantages for specified AI state-tracking tasks. A solver compresses semantic history into a future-accessible boundary state and later answers a query. We count communication BBB, persistent instance-dependent memory MMM, and local work DDD; classical recurrence, caches, tools, and recomputation are allowed and charged. The central result is a boundary-preserving semantic-compilation theorem. It maps a finite one-way, streaming, or adaptive causal task into a semantic AI interface while preserving event order and access to past input. Classical boundary-state lower bounds and quantum-memory upper bounds transfer up to explicit compiler overhead, independently of the finite-precision recurrent architecture. Two applications have classical semantics. Matched-entity synopsis QA inherits the hidden-matching separation between O(log⁡N)O(\log N)O(logN) qubits and Ω(N)Ω(\sqrt{N})Ω(N​) classical boundary bits. Continual requirements auditing inherits a Max-kkkSAT streaming separation: a recurrent solver uses O(log⁡5nlog⁡(1/δ))O(\log^5 n\log(1/δ))O(log5nlog(1/δ)) qubits and polylogarithmic classical workspace to obtain a 0.71720.71720.7172-approximation, whereas every classical one-pass finite-information solver attaining that ratio requires Ω(n)Ω(\sqrt{n})Ω(n​) coordination width. As a quantum-native compiler test, a stabilizer latent-state dialogue uses nnn qubits, while every exact finite-state classical causal online realization satisfies B+M≥12n2+(32−log⁡23)n+O(1)B+M \ge \frac{1}{2}n^2+(\frac{3}{2}-\log_2 3)n+O(1)B+M≥21​n2+(23​−log2​3)n+O(1). The source protocols, streaming algorithms, and stabilizer witness are imported; the new result is their architecture-independent semantic transfer. These are memory and coordination separations, not runtime or empirical advantages for present-day language models. The stabilizer result assumes exact simulation and ideal noiseless quantum memory.
We formulate classical simulation of quantum correlations as coordination across a spacetime separator. All past-dependent information capable of influencing the future must cross the separator either through communicated messages or through a persistent classical state. We prove a general lower bound on this classical coordination cost in terms of the nonnegative rank of the separator correlation matrix, with approximate and amortized extensions governed by approximate nonnegative rank and Wyner common information. For sequential processes, we introduce a causal positive-realization rank that enforces consistent response and state-update maps, and we explain how bounded local computation and support-covering models arise as restricted cases. We apply the framework to genuine global Kochen--Specker contextuality, in which local subsystems are noncontextual and the tested multipartite blocks are generalized-Bell-local, while the complete empirical model has no global noncontextual explanation. At the symmetric point of a polarization--path Hardy construction, exact classical simulation requires two coordination bits, whereas the corresponding quantum separator requires one qubit. Under exact repetition, the classical lower bound is the base-two logarithm of three bits per copy; with asymptotically vanishing error, it becomes one and a half classical bits per copy, compared with one qubit per copy. We further construct a finite stabilizer--Peres--Mermin family for which the exact classical coordination cost grows quadratically with system size, while the quantum boundary cost grows only linearly. The separation applies to arbitrary finite-state causal online simulators. Establishing a constant-error quadratic separation and an intrinsic construction without flag conditioning remain open.
Fault-tolerant compilation can disperse high-level structure: schedules split an accumulated phase across rounds, gate synthesis replaces an angle by a Clifford+TTT word, and randomized compiling spreads rotations over sign-randomized fragments. They preserve the computation but change how cheaply a downstream compiler can recover the aggregate phase data. We formalize this representation-dependent recoverability by charging two channels: output committed before the suffix arrives, and a serialized restart state crossing the cut. For an rrr-round accumulation of a commuting layer with mmm generators at accuracy εεε (Kε=Θ(1/ε)K_ε=Θ(1/ε)Kε​=Θ(1/ε)), any ppp-pass compiler correct on every valid stream with failure probability at most δδδ obeys A‾p+(2p−1)S≥(1−δ)mlog⁡2Kε−h2(δ)\overline{A}_p+(2p-1)S\geq(1-δ)m\log_2 K_ε-h_2(δ)Ap​+(2p−1)S≥(1−δ)mlog2​Kε​−h2​(δ), where A‾p\overline{A}_pAp​ is committed output and SSS is the crossing-state cap. The bound covers compile-time randomized compiling; a memory-capped block compiler attains it within a constant factor, and direct semantic aggregation reaches compact output with logarithmic state. The two channels are not always interchangeable. A compiler whose committed prefix is executed at the cut pays a toll the state channel never pays: the entropy log⁡2(mk)\log_2\binom{m}{k}log2​(km​) of the mask naming which kkk coordinates it commits early. Compilers that defer or buffer pay none of it. We prove both directions and, with instrumented compilers under a preregistered protocol, measure a per-generator toll matching log⁡2(mk)/k\log_2\binom{m}{k}/klog2​(km​)/k that vanishes for a public mask and a buffered control. Under a disclosed fixed-total-error Clifford+TTT and surface-code model, a materialize-first pipeline costs orders of magnitude more logical TTT states and spacetime volume than a semantic-first one. Phase semantics should therefore be preserved until aggregation whenever the interface permits.
Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be Θ(din3dout3/ε2)Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)Θ(din3​dout3​/ε2), where dind_{\mathrm{in}}din​ and doutd_{\mathrm{out}}dout​ are the channel input and output dimensions, respectively, and ε\varepsilonε is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires Ω(din3dout3/ε2)Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)Ω(din3​dout3​/ε2) queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound O(din3dout3/ε2)O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)O(din3​dout3​/ε2). Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case din=1d_{\mathrm{in}}=1din​=1. By contrast, coherent protocols with quantum memory achieve query complexity Θ(din2dout2/ε2)Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)Θ(din2​dout2​/ε2). Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
This preprint studies readout-dependent prediction in a specified classical-quantum continuous-time model with an autonomous classical source and a driven qubit memory. A dynamic model (D) is compared with a scalar-contact model (MATCH) reconstructed to match stationary contact occupancy and both directional switching fluxes. The predictor observes only the qubit memory and the declared classical record j; the target is a future binary signal at an independent exponential horizon. Two distinct results are established by exact interval certificates. At B04, (s,u,v,Omega)=(-1/16,0,0,1), D has lower Brier loss under fixed-Z readout by at least 1/5,000,000, but higher loss under each model's optimal quantum readout by at least 1/2,000,000. This is a commuting conditional-state example. Separately, at nine D-only points with u=1/8, v=0, s in {-1/16,0,1/16}, and Omega in {1/16,1/4,1}, both j sectors have squared normalized commutator norm greater than 10^-8, and the same state's gain over fixed-Z readout is greater than 10^-3. These shared nine-point bounds were extracted after certification. The standard Sylvester readout construction is explicitly attributed. The results are fixed-point statements; they do not establish a continuous parameter region, an unrestricted classical-resource advantage, a causal role of noncommutativity in the B04 reversal, or equal thermodynamic costs. Exact evidence and editable source accompany the preprint in a separate Dataset item. OpenAI ChatGPT/Codex and Anthropic Claude systems assisted the work. Their roles and the limitations of the archived checks are disclosed. AI checks are not human or institutional independent validation. This preprint is not a peer-reviewed journal article. Companion evidence and editable source: https://doi.org/10.6084/m9.figshare.33756607
How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment. We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests. To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting rrr independent matching requests requires Ω(r)Ω(r)Ω(r) qubits for r≤N1/2−δr\le N^{1/2-δ}r≤N1/2−δ and every fixed δ∈(0,1/2)δ\in(0,1/2)δ∈(0,1/2), even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through r=Θ(N)r=Θ(\sqrt N)r=Θ(N​). We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes. Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an Ω(n)Ω(n)Ω(n) space lower bound in random edge order for large enough cycles, with consequences for several graph problems. Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.
This preliminary research preprint presents a reproducible numerical study of history-conditioned quantum error correction under temporally correlated noise. We consider a three-qubit phase-error code subject to a synthetic Pauli noise model with a persistent hidden noise regime. A noisy classical monitor and the accumulated syndrome/measurement history are used to estimate that regime through standard Bayesian hidden-Markov filtering, and recovery operations are selected by a causal maximum-a-posteriori rule. The central question is whether accessible temporal information can extend the finite interval over which encoded quantum information remains reliable. In 100,000 matched synthetic trajectories, survival through 20 correction rounds increases from 0.74406 for a snapshot MAP decoder to 0.91455 for the history-conditioned decoder. Under a 90% no-logical-fault survival criterion, the empirical computational-memory window increases from 6 to 25 rounds, with a simultaneous 95% lower confidence band supporting 23 rounds for the history-conditioned policy. Control experiments show that the advantage disappears when temporal predictability is removed: when the hidden regime becomes independent from round to round, the history-conditioned and snapshot policies coincide. Additional monitor and model ablations demonstrate that the benefit depends on correction-relevant temporal correlations, informative side information, and adequate calibration. The work also formulates finite-horizon survival criteria and sufficient error-budget bounds without assuming independent logical faults, while explicitly separating classical filter stability from preservation of quantum information. This study does not claim a new Bayesian filtering method, superiority over existing temporal quantum-error-correction decoders, a scalable fault-tolerance threshold, or demonstrated room-temperature quantum-computing hardware. Rather, it provides a concrete operational specialization of the broader TrinityLabo history-first framework and a small, reproducible benchmark showing how temporal inference can condition quantum recovery under specified noise assumptions. Ambient-temperature operation remains a future experimental application requiring calibrated device-level noise models, fault-prone syndrome extraction, hardware latency analysis, and comparison against established temporal decoders.