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.
How much distinguishability can a noisy quantum channel preserve when its input is correlated with an untouched quantum memory? This paper gives an exact finite semidefinite program for that question for every finite-dimensional completely positive, trace-preserving channel. The complete coefficient compares joint states with the same memory marginal. The conditional coefficient instead subtracts the distinguishability already present in the memory. Both coefficients, and conditional mutual-information contraction with a separate conditioning system, equal one minus the reciprocal of an optimization in the channel’s unnormalized Choi matrix. The equivalent inverse formula retains an essential range condition, including for singular channels. The proof solves a centered matrix-Gram problem, shows that its optimization center can be positive, and constructs a signed observable lift through an erasure channel. Two weighted quadratic inequalities give the universal entropy bound. A rare coherent memory sector proves sharpness while preserving both local marginals exactly. A memory of bounded dimension suffices, including with prescribed faithful input marginals. The same program gives exact coefficients for regular modular Petz divergences whose generators have finite endpoint value and recession slope, every fixed Petz Rényi order strictly between zero and one, and quantum Chernoff divergence. Further results include a harmonic dual, an exact tensor-product law, a strict-contraction criterion, a sharp comparison with positive quantum Doeblin minorization, and explicit classical, depolarizing and orthogonal-unitary-noise formulas. Ordinary quantum mutual-information contraction is a different optimization. For qubit depolarization the paper determines its exact value on the full completely positive parameter interval. At shrinkage one half, ordinary relative-entropy, ordinary mutual-information and complete entropy contraction are respectively 1/4, 1/3 and 3/8. In higher dimension, bounds and a strict separation are proved without asserting an exact ordinary-MI formula. A discontinuity between nearly complete amplitude damping and pure reset rules out uniformly bounded-use estimation of the exact coefficient from an unknown channel, even with adaptive experiments and quantum ancillas. Thus evaluation from exact supplied Choi data does not imply stable experimental acquisition. Rare sharpness witnesses can carry vanishing absolute information; the results do not assert a communication rate, physical simulator, general recovery map or polynomial cost in physical qubit count.
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.
A programmable quantum processor implements a target unitary using information stored in a classical or quantum program register. For arbitrary unitaries in SU(d), quantum programs attain the optimal leading-order memory cost, whereas deterministic classical rounding requires twice as much memory for the same diamond-distance error. We show that this gap disappears when classical randomization is allowed. We introduce barycentric programming, which stores the label of a unitary randomly selected from a finite set, with probabilities chosen so that first-order approximation errors cancel in the averaged unitary channel. Consequently, the diamond-distance error scales quadratically with the discretization spacing. For any ν-parameter family of unitaries forming a compact, smooth manifold without boundary, this method achieves error ε using only (ν/2)log2(1/ε)+O(1) classical bits. We also prove a matching lower bound for arbitrary quantum programs, determining the optimal leading-order program size for general unitary families. Thus, classical randomization achieves the optimal scaling (ν/2+o(1))log2(1/ε) without requiring coherent quantum memory.
One additional retained measurement outcome can change the optimal approximation order in classical-input simulation of a quantum superchannel. A classical-input realization first measures the external input and then applies a deterministic conditional process. The budget counts the complete retained label, including any shared random choice used at a later stage. We construct a fixed-dimensional family of state-input superchannels for which increasing the budget from four outcomes to five changes the optimal approximation error from linear to quadratic just above the exact realization threshold. The error is measured in the trace norm of the process Choi operator, and the optimization allows arbitrary measurement effects and deterministic conditional processes. The quadratic order is optimal over all finite measurements, and five is the smallest outcome budget that attains it. The same approximation orders hold in diamond distance for the associated joint-input channels. A correlated splitting of one effect cancels the linear defect with only a second-order change in the measurement obtained by merging the split outcomes. Throughout the family, the output channels share a four-outcome mother measurement and the process Choi operator is separable across the external-input cut. An independent theorem establishes local linear stability under stochastic postprocessing for rank-one target POVMs with distinct support rays, provided that the unknown POVM has no more outcomes than the target.
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.