Sequential Capacity of Quantum Processes with Finite Memory

quant-ph cs.LG Yibin Wang · Oct 1, 2026

What it does

Why it matters

The core construction shows that memory-one qubit phase channels already attain this scaling with exact zero-or-one responses, while fully measured classical processes under the same tester permissions are limited to linear capacity. The...

Main concern

Community signal

0 up · 0 down

AI Review AI reviewed

Plain-language introduction

How complex can a quantum device's responses become when it runs longer with a fixed internal memory? This paper quantifies this through sequential response capacity—the depth of an adaptively shattered binary tree of experiments—and proves a tight law: for fixed visible and memory dimensions, capacity grows as $\Theta(K\log((K+1)/\gamma))$ in run length $K$ and probability gap $\gamma$. The core construction shows that memory-one qubit phase channels already attain this scaling with exact zero-or-one responses, while fully measured classical processes under the same tester permissions are limited to linear capacity. The result establishes a fundamental information-theoretic separation between coherent quantum control and classical stochastic transitions under a finite memory budget.

Critical review

Verdict

Bottom line

The paper makes a substantial theoretical advance: it pins down the joint duration–precision asymptotics for finite-memory quantum processes and separates them cleanly from classical analogues. The fixed-memory law in Theorem III.1 is backed by an explicit phase-tree lower bound (Appendix A) and a matching physical-cover upper bound (Proposition D.1). The author is admirably explicit about open problems, noting that the optimal duration–memory–margin trade-off remains unsettled when memory grows with $K$, and that a gap persists in the quadratic-memory regime. Nevertheless, as a characterization of the fixed-memory landscape, the argument is tight and convincing.

“For every fixed $d\geq 2$ and $r\geq 1$, $C_{\gamma}(K,d,r)=\Theta_{d,r}\!\left(K\log_{2}\frac{K+1}{\gamma}\right)$.”

Theorem III.1 · Section III

“These bounds leave a gap in some memory regimes and match the exponential duration dependence once the memory can realize every causal process on the interface.”

Introduction · Introduction, penultimate paragraph

“The computational costs of program preparation, constrained optimization and learning from an experimental record remain to be determined.”

Section VIII · Section VIII, Remark VIII.1

What holds up

Three elements are particularly strong. First, the exact lower-bound construction using signed-phase trees and Boolean inversion (Appendix A) is conceptually elegant: it shows that a single visible qubit with no hidden memory can generate perfectly sharp zero-or-one responses across $\Theta(K\log K)$ adaptive stages. Second, the classical comparison is rigorous: Proposition J.1 proves that fully measured stochastic processes with arbitrary internal classical registers have only linear capacity. Third, the upper-bound machinery—physical covers of CPTP components and quantum program simulators via port-based teleportation (Appendices D–F)—is developed carefully enough to match the lower order in the fixed-memory regime.

“The lower bound is realized by a finite family of memory-one unitary processes with exactly $2^{L(K)}$ distinct response functions. Its sequential fat dimension is exactly $L(K)$ at every such margin, and every response used by the tree equals either zero or one.”

Theorem A.1 · Appendix A

“$\operatorname{sfat}_{\gamma}\mathcal{C}_{d,r}(K)=\Theta_{d,r,\gamma}(K)$.”

Proposition J.1 · Appendix J

“$\operatorname{sfat}_{\gamma}(\mathcal{P}_{d,r}(K))\leq\left\lfloor p_{n,K}\log_{2}\!\left(1+\frac{8(K+1)}{\gamma}\right)\right\rfloor$.”

Proposition D.1 · Appendix D.1

Main concerns

The main limitation is that the growing-memory regime is only partially resolved. Corollary VI.1 shows a quadratic-memory lower bound of $\Omega_{\gamma}(K^4/\log^2 K)$ against an upper bound of $O_{\gamma}(K^{11/2}\log K)$, leaving a polynomial gap. The noise analysis for addressed phase tables (Theorem V.1 and Theorem I.1) is restricted to fixed margins $0<\gamma\leq 1/16$ and known Pauli noise; the joint small-margin dependence is left open. More practically, the paper is purely information-theoretic: it assumes ideal coherent controls and exact zero-or-one responses for the lower bound, without discussing how experimental imperfections would affect the claimed scalings. Finally, the sheer density of the appendices—spanning Boolean inversion, unitary-column addressing, dense coding, port-based teleportation, and causal log-determinant bounds—makes independent verification laborious.

“For $d=2$, $r=K^{2}$, $K\geq 8$ and $0<\gamma\leq 1/16$, $C_{\gamma}(K;2,K^{2})\geq K^{4}/(4096\sqrt{2}\,\lceil\log_{2}(K+1)\rceil^{2})$.”

Corollary VI.1 · Section VI, Eq. (21)

“For every $R=2^{h}$, integer $T\geq 1$, $0\leq p\leq 1/4$, and $0<\gamma\leq 1/16$...”

Theorem V.1 · Section V

“The computational costs of program preparation, constrained optimization and learning from an experimental record remain to be determined.”

Section VIII · Section VIII, Remark VIII.1

Evidence and comparison

The evidence is entirely proof-theoretic and appears internally consistent. Prior work by Raza et al. (cited in text) provided an $O_{d,r}(K\log((K+1)/\gamma))$ upper bound via strategy-norm covers; the author fairly notes that applying their method to the present model yields the same fixed-memory order and then closes the lower side. The classical comparison is careful: the linear classical bound is derived under the same tester permissions, with the quantum advantage pinned on coherent time-dependent parameters rather than memory size. The dephasing results (Appendices H–I) are novel, though their sharpness relies on an exact classical polygon simulation that assumes known noise parameters; related metrology literature is cited appropriately.

“Raza et al. construct strategy-norm covers and obtain online guarantees for a specified bounded-component class of multitime qubit processes. Their method approximates local components and adds the approximation errors. Applied to the initial state and the fixed-dimensional transition channels here, the same method gives the upper order $O_{d,r}(K\log((K+1)/\gamma))$.”

Introduction · Introduction

“classical stochastic processes that completely measure the input and memory at each transition have linear capacity in $K$ at fixed visible dimension, internal state count and gap.”

Introduction · Introduction, paragraph 4

“a regular polygon with $m=\lceil\pi/\arccos(1-p)\rceil$ vertices contains the coherence circle of radius $1-p$.”

Section V · Section V, after Eq. (18)

Reproducibility

No code or data artifacts are provided. The Data Availability statement confirms that all proofs are contained in the appendices and that no experimental data was generated. Reproducing the fixed-memory lower bound requires implementing the signed-phase tree and Möbius-inversion bookkeeping of Appendix A, while the upper bound needs the covering-number estimates of Appendix D and the port-based teleportation simulator of Theorem D.6; both are intricate but fully specified. The Acknowledgements disclose OpenAI Codex assistance for formatting, numerical checks, and counterexample searches, which raises a reproducibility flag: independent verification would benefit from publicly released verification scripts.

“The proofs are contained in this article and its appendices. No experimental data was generated.”

Data Availability · Data Availability

“Möbius inversion of subset sums, also called Boolean inversion, isolates successive binary digits with offsets determined by earlier labels.”

Introduction · Introduction

“OpenAI Codex assisted with language editing, formatting, diagram preparation, technical checks and improvement, and code for numerical experiments and counterexample searches.”

Acknowledgements · Acknowledgements

Abstract

How complex can the responses of a quantum device become as it runs longer with a fixed internal memory? We quantify this complexity through sequential response capacity: how many adaptive testing stages, each using a fresh run, can continue to separate possible processes by a prescribed gap in response probabilities. For fixed system and memory sizes, we establish a tight law relating this capacity to run length and probability resolution. At fixed resolution, the capacity grows on the order of $K\log K$, where $K$ is the number of time steps in each run. Our construction attains this growth using time-dependent phase rotations on a single visible qubit with no additional internal memory; its tests give response probabilities exactly zero or one. Under the same tests, classical stochastic processes that measure in a fixed basis at every step have only linear capacity at fixed sizes and resolution. For phase sequences selected by a stored classical label, we then quantify how known independent Pauli noise changes this logarithmic enhancement. With ideal controls and weak residual phase noise after correction, we prove matching capacity bounds at a fixed small probability gap. These bounds identify the inverse residual phase-flip probability as the coherence timescale that limits the extra logarithmic growth.

Challenge the Review

Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.

Challenges are public to read, but only signed-in members can post them. Your challenge text is stored with your account for moderation, but usernames are not shown in the public thread.

No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.