Sequential Capacity of Quantum Processes with Finite Memory

I. INTRODUCTION

• The capacity counts adaptive testing stages on fresh runs that separate responses by a prescribed probability gap.Each complete path must be consistent with one process whose responses lie above or below each threshold by the required margin.Source: §I · p. 1
• At fixed margin, time-dependent qubit phase channels attain K log K capacity without propagated memory, with exact zero-or-one responses.The fixed-memory upper order is O_d,r(K log((K + 1)/γ)).Source: §I · p. 1
• Classical stochastic processes measuring in a fixed basis at each transition have linear capacity at fixed visible dimension, state count, and gap.Under the same tester permissions, their capacity contrasts with Θ_d,r,γ(K log(K + 1)) for the quantum class.Source: §I · p. 1
• The exact response tree also forces order K log K prediction errors when announced response probabilities are revealed to fixed accuracy.A physical cover supplies the matching upper bound.Source: §I · p. 2
• For phase tables selected by a measured classical address of dimension R = 2^h, noisy capacity is Θ_γ(RT log_2[1 + min(T, 1/e)]).Here K = h + T, and e is the residual phase-flip probability after specified syndrome correction; the bound includes e = 0.Source: §I · p. 2

II. PROCESSES, TESTS, AND SEQUENTIAL CAPACITY

• A process has an initialized state and K transition channels, each acting on the visible system and a propagated register of dimension at most r.Persistent classical labels count toward that register; fresh local environments discarded at transitions are allowed.Source: §II · p. 2
• A normalized binary tester may use private registers, adapt interventions to earlier outcomes, and make a final binary measurement.The tester’s private workspace is separate from memory retained inside the process.Source: §II · p. 2
• Sequential response capacity is the supremum depth of a γ-shattered binary tree of experiments, thresholds, and processes.Each leaf process must keep responses at least γ/2 on the appropriate side of every threshold along its path.Source: §II · p. 2
• Every node is a fresh complete experiment, and one fixed target—including its initialization and transition channels—must serve its whole path.The branch labels describe response ranges and need not be sampled Bernoulli outcomes.Source: §II · p. 3
• The normalized Choi description represents process responses through positive tester operators paired with causal process states.The tester outcome operators sum to one on every causal state, and the causal equations admit sequential channel realizations.Source: §II · p. 3

III. THE FIXED-MEMORY LAW AND ITS PHASE MECHANISM

• The tester selects coefficients in {−1, 0, 1} and a final measurement phase to accumulate signed phases on a retained control qubit.The tester conditionally prepares and reverses known carrier inputs around each forward transition call.Source: §III · p. 3
• For K = 2ℓ, the phase construction yields exactly K(1 + ℓ/2) independent labels, with all responses exactly zero or one.At fixed margin, memory-one qubit unitary processes attain the matching horizon lower bound.Source: §III · p. 3
• Signed Boolean inversion recovers successive binary digits after earlier coordinates are fixed along the response path.Each query uses each transition once; probability bisection supplies the precision dependence.Source: §III · p. 3
• The same horizon order needs no additional private qubit when the tester coherently recycles the visible interface.Repeating one unknown phase across all K transitions instead gives Θ_γ(log(K + 1)) capacity.Source: §III · p. 3
• After one complete run, a finite classical target label has mutual information at most 2(K + 1) log_2 d bits with the tester’s final register.The phase tree nevertheless has superlinear depth at memory one.Source: §III · p. 3
• Figure 1 depicts a complete response path with responses 1, 0, 1 at threshold 1/2, witnessed by one fixed phase pair.Each row is a fresh controlled experiment, with settings determined by earlier responses.Source: Figure 1 · p. 4

IV. CLASSICAL COMPARISON AND PREDICTION

• At fixed d, r, and γ, basis-measuring classical stochastic processes have Θ_d,r,γ(K) capacity, versus Θ_d,r,γ(K log(K + 1)) for quantum processes.Each measured stochastic transition is an exact convex mixture of finitely many deterministic tables; the quantum lower bound uses r = 1.Source: §IV · p. 4
• With scalar probability feedback accurate to ε/8, the minimax expected number of predictions with error above ε is Θ_d,r,ε(min{N, K log(K + 1)}).A uniform leaf of the exact phase tree fixes the target before learning and leaves each next response fair given previous responses.Source: §IV · p. 4
• With one binary outcome per run, the minimax expected average squared error is Θ_d,r(min{1, K ln(K + N)/N}).The protocol uses N complete process runs and KN unknown transitions.Source: §IV · pp. 4–5

• Θγ(RT log2[1 + min(T, 1/e(q))]) is the capacity for the measured-address family under known Pauli noise.Here R is the number of address values, T the number of phase transitions, and e(q) the residual phase-flip probability.Source: §V · p. 5
• Correction groups errors as {I, Z} and {X, Y}, leaving residual phase-flip probability e(q) and coherence factor 1 − 2e(q) per active transition.The tester uses known controlled-NOT and sign controls, then measures the returned carrier to distinguish the error pairs.Source: §V · p. 5
• Pure transverse flips have e(q) = 0 for every 0 ≤ a ≤ 1, so the logarithmic enhancement survives, whereas fixed positive e(q) truncates it.The relevant noise quantity is the phase noise remaining after the specified correction.Source: §V · p. 5
• For dephasing, the phase-flip probability is p/2, and each query costs K = h + T transitions.The theorem uses H = min(T, 1/p), with 1/0 = ∞; its constants are independent of R, T, and p.Source: Table I · p. 6, §V · p. 6
• At p = 1/log2 T, the measured-address family has capacity of order RT log2 log2 T for sufficiently large T.Source: §V · p. 6
• For q = (1 − 2p, p, p, 0), classical programs need Θ(T log T) bits, while response capacity is Θγ,p(T) and an exact quantum program uses O_p(T) qubits.These are complete-process simulation resources, distinct from response capacity.Source: §V · p. 7

• The lower-bound approach uses unitary columns queried in order, with earlier labels determining the next query, and amplitude amplification producing a fixed probability gap.Addressing several blocks yields a direct-sum construction whose memory includes retained addresses and an explicit loading horizon.Source: §VI · p. 7
• At d = 2 and r = K2, the lower bound grows as K4/log2 K, while the optimized-program upper bound grows as O(K3 loga K).Consequently, a uniform bound of the form CKr[log(K + 1) + log(r + 1)]a cannot hold for any constants C, a ≥ 0 at fixed d and γ.Source: §VI · p. 7
• For r ≥ d2K−1, the construction reaches the saturated duration dependence, and this memory also suffices to realize every causal process on the interface.The lower construction uses Bell-pair address digits to select an arbitrary output table.Source: §VI · p. 7

• For fixed d, r, and 0 < ξ < 1/2, the smallest log2 D for a common state encoding with target-independent effects and uniform response error at most ξ has order K log(K + 1).The lower bound uses the perfect phase tree; the upper bound encodes centers of a proper process-class cover as orthogonal labels.Source: §VII · p. 8
• The deterministic program encodes the initial state and all K transitions in a common compressed image space, with retrieval error uniform over adaptive testers.The construction uses low-Kraus-rank channel components, inner-product-preserving embeddings, and correlated port-based teleportation resources.Source: §VII · p. 8
• The causal upper bound follows from a log-determinant potential, shrinking toward the maximally mixed causal state, and an online inequality along a shattered-tree path.The potential is R(ρ) = −ln det ρ − d2K+1 ln(d2K+1).Source: §VII · p. 8
• Direct tree conversion of Ref. [6]'s full-strategy estimate gives order ν2 ln ν/γ2, while the causal upper bound is 4ν ln(4/γ)/γ2.Here ν = d2K+1.Source: §VII · p. 8

• The optimal joint dependence on duration, memory, and margin remains open when the memory budget varies.The least memory needed to attain the saturated order is also unresolved, as is the optimal joint small-margin dependence for Theorem V.1.Source: §VIII · p. 9
• Open computational questions include program preparation, constrained optimization, learning from experimental records, and the complexity of proper prediction under specified experiment and loss restrictions.Source: §VIII · p. 9

• No experimental data was generated; the proofs are contained in the article and its appendices.Source: DATA AVAILABILITY · p. 9

Perfect-margin phase trees

• The phase-tree construction uses coherent control to realize bounded signed phase queries across the transitions.The visible qubit process has fixed phase descriptions and propagates no private register; each query uses every transition once and requires no postselection.Source: Appendix A · pp. 9–10
• The memory-one phase family has exact sequential fat dimension L(K) at every margin, with every tree response equal to zero or one.For K = 2n, its depth is K(1 + n/2).Source: Appendix A · p. 9
• A threshold of 1/2 yields signed response margin 1/2 at every node, and each complete branch assignment specifies one phase vector satisfying its path constraints.Source: Appendix A · p. 11

Horizon and margin

• For general K, dyadic blocks concatenate the phase-tree construction, while probability bisection over independent output coordinates supplies margin dependence.The appendix derives a joint horizon-and-margin lower order from these two subfamilies.Source: Appendix A · p. 11

Probability-grid trees

• A finite family of memory-one replacer processes has an exact sequential fat dimension given by the probability-grid count.The grid uses independent output labels and concatenated bisection trees over its coordinates.Source: Appendix A · p. 11

Joint horizon and margin

• The physical-cover upper bound and the constructions establish a joint duration–precision order at fixed memory, with constants independent of K and γ.Source: Appendix A · p. 11

Column family

• A sequential family of unitary-column matrices carries R(R −1)/2 independent signs, queried in column order with responses independent of later signs.The tester's query vector depends only on earlier columns.Source: Appendix B · p. 12

Constant-gap decoder

• The constant-gap decoder separates the two cases with success-probability difference greater than 1/16 using at most ⌈N + 1⌉ alternating unitary operations.Source: Appendix B · p. 12

Streaming implementation

• An R = dℓ-dimensional process memory can implement one tester-held unitary use, including reference correlations, in 2ℓ transitions and reset its memory.Source: Appendix B · p. 13

Unitary-column lower bound

• With independently chosen matrices in scheduled blocks, the construction yields GR(R −1)/2 tree levels with margin at least γ/2 for 0 < γ ≤ 1/16.Each block resets process memory; the same complete process realizes every constraint along a path.Source: Appendix B · p. 14

Memory scaling

• When the logarithm is O(ℓ), the cited ratio tends to infinity at least as fast as a positive constant times 2^(ℓ/2)/ℓ².Source: Appendix B · p. 14

Appendix C: Addressing independent processes within one memory cap

• Theorem C.1 combines branch families’ shattered trees under a direct-sum memory cap, with deterministic address loading adding a transitions to the horizon.After loading, the selected branch’s response is unchanged; concatenating the branch trees yields the combined construction.Source: Appendix C · pp. 14, 16
• Corollary C.4 establishes a qubit-memory lower bound for every integer K ≥ 8 and 0 < γ ≤ 1/16, while optimal joint dependence on all four parameters remains open.Source: Appendix C · p. 17

1. A cover with physical centers

• Physical covers with centers inside the memory-capped process class yield the fixed-memory upper order used in the paper’s main law.The construction covers an initial state and K fixed-dimensional channels while keeping each center a physical process with memory cap r.Source: §1 · p. 18

2. Information carried by one program for a complete leaf

• Whole-process programs encode each process as a state on a common finite-dimensional space, allowing tester responses to be bounded through information carried by that state.The same argument applies to approximations by convex hulls of fixed response functions.Source: §2 · p. 19

3. Finite mixtures of channels with small Kraus rank

• Every channel on C^n is a finite convex combination of channels with Kraus rank at most n, enabling a finite-mixture response approximation.These auxiliary mixtures are not necessarily physical within the original memory cap: retaining a component label may require additional process memory.Source: §3 · pp. 19–20

4. A finite port-based program

• The finite teleportation protocol uses a covariant resource and a complete deterministic correction-free port selection, with added measurement terms that cannot reduce fidelity.The construction follows finite covariant port-based teleportation work [17] [18].Source: §4 · pp. 20–21
• For the covariant finite-port teleportation channel, the full diamond error is exactly 2(1−F), where F is its normalized entanglement fidelity.The maximally entangled input attains the reverse inequality because the two Choi sectors are orthogonal.Source: §4 · p. 23
• A shared finite-dimensional program space and fixed physical retrieval circuit implement Φ∘T for every channel Φ, with retrieval trace preserving on every program input.The construction uses a common support for the channel programs, and its retrieval circuit remains completely positive and trace preserving even for reference-entangled programs.Source: §4 · p. 23
• Replacing each of K transitions with a retrieved channel of diamond error at most η/K bounds terminal trace error by η and binary response-probability error by η/2, uniformly over testers.The simulator encodes the initial state exactly and uses one transition-program factor per step; composing an adaptive binary tester gives an effect on the encoded program space.Source: §4 · p. 24

Appendix E: An upper bound for all causal processes

• L ≤ 4ν ln(4/γ)/γ² bounds every finite γ-shattered depth over the full causal set, and therefore every memory-capped class.The argument uses a log-determinant potential whose curvature is controlled by changes in complete-tester outcome probabilities.Source: Appendix E · pp. 24–26

Appendix F: Dense tables and the saturated memory regime

• Θ_d,γ(d²ᴷ) capacity holds for the full causal class and memory-capped processes once r ≥ d²ᴷ⁻¹.A dense table of response bits is queried with exact zero-or-one probabilities using generalized Bell measurements and Weyl operators.Source: Appendix F · pp. 26–27

1. Information in one physical trajectory

• For the memory-one qubit phase family, fresh-run leaf counts and perfect-margin tree depth grow as K log K, while one run retains at most 2(K + 1) bits.The passage distinguishes response-tree depth across fresh experiments from information retained in one physical trajectory.Source: §1 · p. 27

2. Exact component programs

• Exact fixed component programs induce program-based capacity bounds when the initial and transition program dimensions and component input/output dimensions are bounded.The processors simulate target components as complete channels, including propagated memory and reference-entangled inputs, and use one fixed product program state per target.Source: §2 · pp. 27–28

3. An alternative bound from heralded teleportation

• Heralded teleportation gives an alternative program-capacity bound using perfect successful branches with probability p = s/(s + n² − 1).The accepting event forms a program effect, and the physical-cover, deterministic-program, heralded-program, and full-causal bounds can be minimized at the required parameters.Source: §3 · p. 28

Appendix H: Capacity with known dephasing and a classical address

• Appendix H constructs short coherent phase tests and an exact finite program for the noisy process, with Boolean coordinates inherited from Theorem A.1.Its circuit calculation determines coordinate visibility under the specified noise.Source: Appendix H · p. 28

1. Complete channel model

• The noisy-channel model uses K = h + T transitions, a known fixed noise rate p ∈ [0, 1/4], and a classical address retained as the entire process memory.Each response-tree leaf has one fixed table with margin γ/2 on either side of its thresholds; each query is a fresh run of the initialized target.Source: §1 · p. 29

2. Exact finite simulation of the noisy channels

• For 0 < p ≤ 1/4, Lemma H.1 is titled “A common polygon of phase channels”; the cited equality is an identity of channels and holds after adjoining any reference system.Each coordinate (t, j) occurs in only one transition of a run, so the product in (H7) implements the independent local noise of the original process.Source: §2 · pp. 29–30
• A fixed processor measures the program in the specified basis and runs its complete table; this CPTP simulation yields a target-independent effect when composed with a normalized tester.Source: §2 · p. 30

3. Information and covering bounds

• A phase cover uses N = ⌈4πT/γ⌉ rounded phases, limits each tester’s response error to γ/4, and forces distinct shattered-tree leaves to use distinct centers, so 2L ≤ NRT.The common postprocessing dephasing preserves the cover bound.Source: §3 · pp. 30–31

4. A retained control and a reset carrier

• A coherent control retained outside the process and a reset carrier implement phase queries whose control coherence is multiplied by (1 − p)e^(±iθ) on active slots and remains unchanged on inactive slots.Fresh noise environments are discarded between slots, allowing the channel identity to compose across a string of queries.Source: §4 · p. 32

5. Two addresses and two blocks of length two

• The two-address, two-block example shatters a complete depth-12 tree using one phase table per path, with two-slot visibility 9/16 even at p = 1/4.At p = 1/4, a single coherent probe through all four slots instead has visibility 0.31640625, versus 0.5625 for the two-slot query.Source: §5 · p. 32

6. Boolean phase trees in noisy blocks

• For dyadic phase blocks with np ≤ 1/4, bit-isolation queries have signed margin vq/2 and shatter a bit exactly when vq ≥ γ, with one complete target witnessing the node inequalities.At p = 0, every block has visibility one regardless of its length.Source: §6 · p. 33

7. Block partition and uniform constants

• Constructed nodes have visibility at least 3/4 for p > 0 and one for p = 0; at p = 0, the resulting order is Θγ(RT log2(1 + T)), with endpoint cases T = 1 and R = 1 included.Source: §7 · p. 34

8. Sampling threshold responses

• For L adaptively selected nodes, Hoeffding’s inequality and a union bound give simultaneous response-estimation error at most γ/4, enough to determine the response side with a promised γ/2 threshold gap.The estimates assume independent complete resets; the total cost includes full runs, process transitions, resets, readout, and classical computation.Source: §8 · p. 34

Appendix I: Capacity with known Pauli noise

• At fixed small gap, matching capacity bounds scale as RT log2[1 + min{T, 1/e(q)}], so residual phase error limits the logarithmic duration enhancement.The bounds hold for R = 2^h, T ≥ 1, and known q with 0 ≤ e(q) ≤ 1/8; e(q) is the residual phase-flip probability after recovery.Source: Appendix I · p. 35

1. Syndrome recovery and the phase tree

• Syndrome measurement identifies the Pauli-error pair, and the more likely phase correction leaves error probability e(q); inactive slots preserve the control coherence.Short blocks keep visibility at least 3/4, supporting phase-tree tests with a signed margin of at least 3/8.Source: §1 · p. 35

2. An exact quantum program and uniform upper bounds

• A fixed quantum processor gives an upper bound by programming noisy phase channels, while phase rounding supplies a second bound that also applies at e = 0.The rounded-table cover changes every adaptive response by at most γ/8; combining it with the program bound yields the uniform upper bound.Source: §2 · pp. 36–37

3. Obstruction to a finite classical channel dictionary

• When qI, qX, and qZ are positive and qY = 0, no finite collection of fixed qubit channels can convexly represent the full phase-channel circle.The obstruction follows because distinct phases require distinct lines in the odd Choi subspace; an example has an exact three-qubit quantum program despite this classical obstruction.Source: §3 · p. 37

4. Classical and quantum programs for a complete process

• For the specified noisy phase family, the classical dictionary cost is Θ(T log2(T/ϵ)), while the theorem also quantifies quantum program storage.The classical cost is for 0 < p ≤ 1/8 and 0 < ϵ ≤ 1/64; program preparation and decoder computation are counted separately from storage.Source: §4 · p. 38

Fully measured processes

• At fixed d, r, and γ, fully measured processes have capacity Θd,r,γ(K), in contrast to the paper’s K log(K + 1) quantum phase-tree depth.The measured class allows time-dependent stochastic memory updates, with persistent random records stored in the r-state memory.Source: Appendix J · pp. 40–41

Prediction from scalar responses

• With fixed precision, scalar-feedback prediction has worst-case mistakes of order min{N, K log(K + 1)}.A halving predictor uses a finite physical cover, while a random exact-response-bit tree supplies the lower bound.Source: Appendix J · pp. 40–41
• Sampling scalar feedback to accuracy ε across N adaptively chosen rounds requires m fresh runs per round, with total cost Nm complete runs and KNm transitions.The stated guarantee has probability at least 1 − ζ.Source: Appendix J · p. 41

Prediction from single outcomes

• For single-outcome feedback, the squared probability-error risk has order min{N, K log(K + 1)} + K log(1 + N/K) at fixed d and r.The lower bounds combine an exact zero-or-one phase tree with memory-one replacer channels; the upper bound uses exponential weighting over physical-cover centers.Source: Appendix J · p. 42

Coherent reuse of the visible interface

• For K = 2ℓ with ℓ≥0, the class Fvis(K) admits an exact zero-or-one response tree of depth 1 + ℓK/2.The construction prepares the visible qubit in |+⟩, uses each forward target transition once, and conjugates calls by known Pauli X at negative signs. A final equatorial measurement gives the response using the interface itself.Source: Appendix K · p. 43
• For independent phase parameters, restricting testers to the visible qubit still yields capacity of order K log(K + 1) at fixed gap.Padding a dyadic prefix handles general K.Source: Appendix K · p. 43

Repeated transition parameters

• If one unknown qubit phase channel is repeated at all K transitions, full adaptive testers instead have capacity Θγ(log(K + 1)) at fixed γ.A repeated-channel cover gives the upper bound, and a bit-query phase tree gives the matching lower bound.Source: Appendix K · p. 44