Quantum channels and memory

Answered Can an algorithm tell how much memory a repeated channel needs?

No.

1. No algorithm can tell how much memory a repeated quantum channel needs

   Seth Douglas and Nidhal Mghirbi · version 1.1.0 · 7 October 2026

   For a device that applies a channel again and again with maximally mixed fresh qubits, the answer turns on one set of channels: inside it, channels with a flat probe can be served with memory that grows more slowly than the number of uses; outside it, a device with sublinear memory fails with probability tending to one.

   • Answered Can an algorithm tell how much memory a repeated quantum channel needs?

   The paperPDFDOICode

2. Causal quantum-channel simulation: memory beyond entropy

   Seth Douglas and Nidhal Mghirbi · version 1.1.2 · 30 September 2026

   Two explicit channels with the same complete Choi spectrum and the same entropies need different amounts of memory at the same optimal exchange rate.

   • Answered Do a channel’s spectrum and entropies determine the memory needed to simulate it causally?

   The paperPDFDOICode

3. Factorizable rational quantum channels at an explicit distance from finite tracial baths

   Nidhal Mghirbi and Seth Douglas · version 2.0.0 · 6 October 2026

   Explicit rational channels that are factorizable but not limits of channels implementable with a finite maximally mixed environment, at a positive and explicit distance from that closure.

   • Answered Is every factorizable rational channel a limit of channels with a finite maximally mixed environment?

   The paperPDFDOICode

4. The memory and purity cost of immediate delivery

   Seth Douglas and Nidhal Mghirbi · version 1.0.0 · 7 October 2026

   How many qubits a device must keep, exchange and be given pure to apply one channel $n$ times when each output must leave before the next input arrives.

   • Answered Which unital channels are repeatable by one device with a finite memory and no resets?

   The paperPDFDOICode

5. Bath dimension and initial entropy for closed repeated use of a quantum channel

   Seth Douglas · version 1.1.0 · 16 September 2026 · arXiv:2609.18267

   The bath dimension and initial entropy that closed, repeated use of a quantum channel requires.

   The paperPDFDOICode

6. Closed mixed-apparatus compression of Schur channels: exact–approximate separation and scheduled delivery

   Seth Douglas · version 1.0.0 · 16 September 2026

   A Schur channel of Gram rank $k$ on dimension $d$ is implemented to error $\epsilon$ by one fixed unitary with apparatus dimension $O({\epsilon }^{-2}(\sqrt{k}+\ln d))$.

   The paperPDFDOICode

7. The clean two-query threshold for unitary synthesis

   Seth Douglas · version 1.0.4 · 13 September 2026

   Clean two-query synthesis of every $n$-qubit unitary needs, and can be done with, $\mathrm{\Theta }(2^n)$ qubits and oracle input bits, up to a factor $\log (1/\epsilon )$; the garbage-model problem reduces to a clean four-insertion width bound, which remains open.

   • Partly answered Can every $n$-qubit unitary be implemented by a polynomial-size circuit making few queries to a classical oracle?
   • Answered How many qubits does clean two-query synthesis of every $n$-qubit unitary need?
   • Open Does the clean four-insertion width bound hold? posed here

   The paperPDFDOICode

8. Quantum recovery from finitely many sharp questions

   Seth Douglas · version 1.0.0 · 16 September 2026

   When approximate recovery of finitely many sharp binary observables guarantees recovery of the entire quantum input, with matching fixed-gap minimax bounds.

   • Answered When does recovering finitely many sharp binary observables recover the whole quantum input?

   The paperPDFDOICode

9. Where the quantum capacity sits in the arithmetical hierarchy

   Seth Douglas and Nidhal Mghirbi · version 1.0.0 · 2 November 2026 · 15 pages

   For effectively described finite-dimensional channels, the quantum capacity $Q$ is approximated uniformly from below by an increasing computable sequence of rationals, so the threshold problem for $Q$ lies in ${\Pi }_2^0$ and its gapped version is computably enumerable; consequently the conjecture of Bhattacharyya, Mehta and Zhao that the threshold problem is ${\Pi }_3^0$-hard is false as printed under computable reductions. Positivity of $Q$ is semi-decidable, and, on exact algebraic inputs, decidable exactly when the zero-capacity channels form a computably enumerable set. For the magic-square game graph every evaluated spectral bound equals 6, and the independence number of its strong square is exactly 29.

   The paperPDFDOICode

• Partly answered Can every $n$-qubit unitary be implemented by a polynomial-size circuit making few queries to a classical oracle?
• Answered Which unital channels are repeatable by one device with a finite memory and no resets?