A finite-dimensional physical processor cannot exactly program a continuous family of distinct unitary channels. We show that this obstruction becomes quantitative when the target channel is stored in a normalized Choi state and its output observables are reconstructed by sampling physical channels and classically post-processing their measurement outcomes. For arbitrary $d$-dimensional channels, we construct a target-independent exact reconstruction protocol and prove the optimal one-copy sampling overhead, which grows quadratically with system dimension. We further prove the sharp fixed-$d$ law that the excess overhead vanishes inversely with the number of identical Choi programs. The upper bound combines deterministic port-based teleportation with a quasi-decomposition that corrects its depolarizing distortion. The converse maps any low-overhead reconstruction protocol to a physical learner of unknown unitaries and uses local quantum estimation to recover the same leading coefficient. These results recast the universal no-programming obstruction as a quantitative trade-off between quantum program memory and classical sampling, with a leading cost that reflects the locally learnable unitary degrees of freedom.
A finite-dimensional physical processor cannot exactly program a continuous family of distinct unitary channels. We show that this obstruction becomes quantitative when the target channel is stored in a normalized Choi state and its output observables are reconstructed by sampling physical channels and classically post-processing their measurement outcomes. For arbitrary d-dimensional channels, we construct a target-independent exact reconstruction protocol and prove the optimal one-copy sampling overhead, which grows quadratically with system dimension. We further prove the sharp fixed-d law that the excess overhead vanishes inversely with the number of identical Choi programs. The upper bound combines deterministic port-based teleportation with a quasi-decomposition that corrects its depolarizing distortion. The converse maps any low-overhead reconstruction protocol to a physical learner of unknown unitaries and uses local quantum estimation to recover the same leading coefficient. These results recast the universal no-programming obstruction as a quantitative trade-off between quantum program memory and classical sampling, with a leading cost that reflects the locally learnable unitary degrees of freedom.
We study the persistent quantum and classical memory required for exact heralded storage and retrieval of quantum measurements. Given only black-box access to the measurement channel, we construct an exact compression of the port-based program into an outcome-type record and a quantum register, with total dimension polynomial in the query count. For every universal retrieval processor we prove the bounds Q+C≥log2n and 2Q+C≥log2((n−1)d2+1) on the numbers Q of qubits and C of bits of the program, for n-outcome POVMs on Cd with d≥2. For n≥2, no finite classical memory removes the need for quantum memory: any such processor requires a quantum program of dimension at least d, at that dimension its classical alphabet must have at least n symbols, and both minima are attained by a single-query protocol with success 1/d2. Combining direct-program compression with a converse from approximate measurement programming gives logarithmic total-memory scaling in 1/(1−p) as the uniform success probability p approaches one, at fixed d,n≥2. At fixed input dimension and target success below one, the optimal total-memory scaling is logarithmic in n. We also construct self-contained programs under branch-decomposition access and compare the quantum and classical costs of all constructions, including where the outcome-type record is kept: for POVMs with n nonzero rank-one effects the direct program admits a purely quantum allocation whose register is never larger than that of the minimal-Naimark unitary program and which succeeds more often whenever n>d.
A quantum memory can preserve a subsystem perfectly while discarding information needed by a later operation. We study the total intermediate dimension required for channel synthesis when the first stage protects a b-dimensional subsystem and has a prescribed noncommutative graph imposing full confusability on an a-dimensional control register. For a finite family of classically controlled branches, exact synthesis is possible if and only if the target graph contains the prescribed graph of the first stage. For every feasible family, we construct a single processor that implements all branches exactly. The processor uses pairwise nonorthogonal pure program states in a register of dimension at most a. A target graph may be realizable with a carrier of dimension b, while synthesizing a channel with that graph can require dimension ab. We also characterize the closure of the attainable channels, distinguishing exact synthesis from arbitrarily accurate approximation. Finally, for a family built from the trine communication task, a four-dimensional carrier permits exact synthesis with quantum programs under output depolarization. At the same total carrier dimension and without free shared randomness, classical programs have optimal normalized diamond error (1−η)/4, where 0≤η≤1 is the depolarization strength. For η<1, the gap persists under sufficiently small perturbations of the target branches.
We ask whether coupling a fixed finite-dimensional environment to a quantum process can be undone functorially: does tensoring with an environment E admit an adjoint in the category of quantum channels, and in related categories of instruments and stochastic maps? We prove that it does not, unless the environment is trivial. Our central new tool is an intercept principle: an enriched adjunction must preserve the affine dimension of hom-sets coefficient by coefficient, and probability normalization contributes a dimension-counting intercept that no environment-independent representing object can absorb. Specialized to the environment endofunctor, this gives a single coefficient-rigidity obstruction that governs channels, ordered instruments, finite stochastic maps, and higher-order superchannels uniformly, and yields an exact classification in each case: a left or right adjoint exists precisely when the environment is isomorphic to the tensor unit. We introduce an operational counterpart of this categorical obstruction. No finite-dimensional quantum memory with a fixed processor can store and exactly evaluate all channels on a nontrivial system, and any natural finite-memory encoding of processes would induce the adjoint just shown to be impossible. For approximate compression into insufficient memory we prove a new quantitative floor on the achievable diamond-norm error, sharp for the argument used and extended from linear to arbitrary continuous encoders by a Borsuk–Ulam argument. Finally, we place these obstructions against the standard theory of exact recovery: a channel is Petz-recoverable exactly when its complementary channel is constant, a morphism-level splitting that we show is strictly weaker than the functorial currying structure ruled out above. We delimit what these results do and do not establish, and accompany the mathematical claims with a machine-checkable verification suite.
Quantum process tomography, the task of estimating an unknown quantum channel, is a central problem in quantum information theory. A long-standing open question is how many uses of an unknown channel are required to learn it in diamond distance, the standard metric for distinguishing quantum processes. While quantum state tomography is well understood, for general channels the problem remained open beyond the unitary case. Here we establish the query complexity of channel tomography with optimal dependence on the dimension parameters, at any fixed constant accuracy. We design an algorithm showing that any channel with input/output dimensions din,dout and Kraus rank at most k can be learned to accuracy ε using O(dindoutk/ε2) channel uses. Conversely, we prove that Ω(dindoutk) uses are necessary at constant accuracy and that, for non-minimal Kraus rank, a separate Ω(1/ε2) contribution is unavoidable. Since channels subsume states, unitaries, isometries, and measurements as special cases, our protocol provides a unified framework for these tomography tasks, yielding new guarantees for isometry and measurement tomography while recovering known optimal scalings for state and unitary tomography. Our algorithm follows the natural strategy of performing optimal tomography on the Choi state. The main technical contribution is to show that this suffices to control the induced diamond-distance error, avoiding the dimension loss incurred by a naive conversion from Choi-state trace distance to channel diamond distance. The protocol uses the channel non-adaptively to prepare Choi-state copies, purifies them in parallel, and performs optimal pure-state tomography on the resulting purifications. Hence, we reduce channel tomography to pure-state tomography.
Within flagged unitary–replacer channels, optimized recovered entanglement fidelity is spectrally incomplete: it fixes weighted transparency but not the hidden replacer spectrum or conditional Choi entropy. For a resolved positive-probability sector with known transparency 0 ≤ a < 1, we prove a family-specific noncommutative triangular transfer from conditional Choi moments M2, . . . , Md to hidden-spectrum power sums. Recursive inversion, Newton–Girard identities, and a rank-one step recover the unordered replacer and conditional Choi spectra, including multiplicities and zero eigenvalues. The order-d threshold is sharp within the consecutive sector-resolved hierarchy: every truncation below d fails local injectivity on positive simple-spectrum chambers. At fixed dimension and flag distribution, we also determine the complete homogeneous and heterogeneous fixed-fidelity Choi-entropy intervals, including lower/equality structure, interval filling, and heterogeneous optimizer geometry, while retaining the established quantum-Fano upper envelope. With transparency unknown, the consecutive map (a, λ) ↦ (M2, . . . , Md+1) is generically locally invertible on the positive ordered simple-spectrum interior for every d ≥ 2. Global uniqueness holds in d = 2, 3; for the specific map F4 = (M2, M3, M4, M5), d = 4 exhibits an exact open two-sheet ambiguity with exactly two ordered physical inverse branches, while d ≥ 5 remains unresolved. At a = 1, the moments lose all replacer-spectrum information. The results are family-specific and assume sector-resolved access; they do not imply universal channel reconstruction, tomography, or resource optimality.
Within flagged unitary–replacer channels, optimized recovered entanglement fidelity is spectrally incomplete: it fixes weighted transparency but not the hidden replacer spectrum or conditional Choi entropy. For a resolved positive-probability sector with known transparency 0 ≤ a < 1, we prove a family-specific noncommutative triangular transfer from conditional Choi moments M₂,...,M_d to hidden-spectrum power sums. Recursive inversion, Newton–Girard identities, and a rank-one step recover the unordered replacer and conditional Choi spectra, including multiplicities and zero eigenvalues. The order-d threshold is sharp within the consecutive sector-resolved hierarchy: every truncation below d fails local injectivity on positive simple-spectrum chambers. At fixed dimension and flag distribution, we also determine the complete homogeneous and heterogeneous fixed-fidelity Choi-entropy intervals, including lower/equality structure, interval filling, and heterogeneous optimizer geometry, while retaining the established quantum-Fano upper envelope. With transparency unknown, the consecutive map (a, λ) ↦ (M₂,...,M_{d+1}) is generically locally invertible on the positive ordered simple-spectrum interior for every d ≥ 2. Global uniqueness holds in d = 2, 3; for the specific map F₄ = (M₂, M₃, M₄, M₅), d = 4 exhibits an exact open two-sheet ambiguity with exactly two ordered physical inverse branches, while d ≥ 5 remains unresolved. At a = 1, the moments lose all replacer-spectrum information. The results are family-specific and assume sector-resolved access; they do not imply universal channel reconstruction, tomography, or resource optimality.