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

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

URL: http://arxiv.org/abs/2608.11066v1
Date: Tue, 11 Aug 2026 15:32:15 GMT
Title: Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory
Abstract summary: We prove inference-time quantum coordination advantages for specified AI state-tracking tasks.<n>We map a finite one-way, streaming, or adaptive causal task into a semantic AI interface while preserving event order and access to past input.
Score: 5.649244092106778
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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.

Related papers

On the Limits of Quantum Multiparty Simultaneous Communication [1.7205106391379026]
We establish a multiparty exponential separation through $nameIC_k,n$, a natural $k$-party generalization of textscIndex Coordination.<n>We show that quantum superposition cannot efficiently simulate the coordination afforded by public randomness, extending this separation to arbitrary $k$.
arXiv Detail & Related papers (2026-09-09T15:07:22Z)
Separating quantum circuits from classical LLMs [2.986556069071589]
We prove unconditional separations between low-depth quantum computation and classical language-model architectures.<n>Our work initiates the study of quantum advantage in the era of large language models.
arXiv Detail & Related papers (2026-08-04T17:28:24Z)
When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models? [22.276732262979678]
We model any fixed finite-precision recurrent sequence model, including finite-precision state-space models (SSMs) with $B$ bits of internal state, as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface.<n>A single minimal-state tool, namely a tape supporting only local $mathttread$, $mathttwrite$, and $mathttmove$ commands, makes the system Turing complete.
arXiv Detail & Related papers (2026-07-07T11:32:56Z)
Distinguishing quantum processes with bounded coherent memory [0.0]
Distinguishing multi-time quantum processes is a fundamental task.<n>Standard benchmark for distinguishing two processes is the strategy-norm distance.<n>We introduce machines for autonomous distinction.
arXiv Detail & Related papers (2026-06-17T18:52:19Z)
Dynamic Large Concept Models: Latent Reasoning in an Adaptive Semantic Space [56.37266873329401]
Large Language Models (LLMs) apply uniform computation to all tokens, despite language exhibiting highly non-uniform information density.<n>We propose $textbfDynamic Large Concept Models (DLCM)$, a hierarchical language modeling framework that learns semantic boundaries from latent representations and shifts from tokens to a compressed concept space where reasoning is more efficient.
arXiv Detail & Related papers (2025-12-31T04:19:33Z)
A Quantum Algorithm For Computing Contextuality Bounds [0.0]
We give a quantum algorithm based on Grover's search algorithm, computing the degree of contextuality in $O(sqrtn loglogn)$ in $n$ states, a speedup over classical brute force method.<n>We also study variations of Grover which encode the relevant information in the phases of the basis states, reducing circuit width and depth requirements.
arXiv Detail & Related papers (2025-09-24T15:36:02Z)
Efficient Quantum State Synthesis with One Query [0.0]
We present a time analogue quantum algorithm making a single query (in superposition) to a classical oracle. We prove that every $n$-qubit state can be constructed to within 0.01 error by an $On/n)$-size circuit over an appropriate finite gate set.
arXiv Detail & Related papers (2023-06-02T17:49:35Z)
Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z)
Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
arXiv Detail & Related papers (2022-04-22T12:37:56Z)
A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z)
RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
We show that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syntax. We introduce Dyck-($k$,$m$), the language of well-nested brackets (of $k$ types) and $m$-bounded nesting depth. We prove that an RNN with $O(m log k)$ hidden units suffices, an exponential reduction in memory, by an explicit construction.
arXiv Detail & Related papers (2020-10-15T04:42:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.