How do you decide which quantum channel keeps more information? There is more than one way to ask. You can compare how well two states remain distinguishable, how much information an ensemble retains, or how sensitively an output responds to a small change. These are different mathematical questions. This paper asks when they give the same ordering of quantum channels. The comparison is complete: an input may share correlations with a separate, finite quantum reference, and the reference can be as large as needed. That extra system makes the question richer than looking at the channel output alone. For finite-dimensional channels, the manuscript claims an equivalence among complete comparisons expressed through relative entropy, Holevo information, BKM and SLD Fisher information, and measured chi-squared divergence. It also studies the complementary channel—the part of a Stinespring description that goes to the environment—and claims that the information order reverses under genuine complementation. The second part asks whether these comparisons can be decided by an algorithm. The paper claims coRE-completeness for a class of strictly positive rational-complex measurements, and that no computable bound on reference size suffices for the stated SLD comparison. It also claims fixed-additive-accuracy inapproximability for a bounded entropy defect. These are claims about precisely specified mathematical decision problems, not a claim that every practical channel comparison is impossible. The companion paper, From complete channel order to capacity and one-way distillation, explores consequences for communication and distillation using the order results developed here. See the manuscript page for a further introduction and citation details.
How do you decide which quantum channel keeps more information? There is more than one way to ask. You can compare how well two states remain distinguishable, how much information an ensemble retains, or how sensitively an output responds to a small change. These are different mathematical questions. This paper asks when they give the same ordering of quantum channels. The comparison is complete: an input may share correlations with a separate, finite quantum reference, and the reference can be as large as needed. That extra system makes the question richer than looking at the channel output alone. For finite-dimensional channels, the manuscript claims an equivalence among complete comparisons expressed through relative entropy, Holevo information, BKM and SLD Fisher information, and measured chi-squared divergence. It also studies the complementary channel—the part of a Stinespring description that goes to the environment—and claims that the information order reverses under genuine complementation. The second part asks whether these comparisons can be decided by an algorithm. The paper claims coRE-completeness for a class of strictly positive rational-complex measurements, and that no computable bound on reference size suffices for the stated SLD comparison. It also claims fixed-additive-accuracy inapproximability for a bounded entropy defect. These are claims about precisely specified mathematical decision problems, not a claim that every practical channel comparison is impossible. The companion paper, From complete channel order to capacity and one-way distillation, explores consequences for communication and distillation using the order results developed here. See the manuscript page for a further introduction and citation details.
Recent examples have shown that zero private capacity need not imply antidegradability and that two channels with zero private capacity can nevertheless transmit private information together. Existing entropic channel orders compare what a receiver and its environment can learn and thereby bound capacities. We connect these orders to the recent constructions through binary estimation, whose minimum mean-square error is governed by measured χ2 divergence. A new integral representation shows how measured χ2 on a qubit extension recovers quantum χ2. It lets us pass from complete measured-χ2 ordering to complete quantum-χ2, relative-entropy, and less-noisy ordering. Zhu and Wang used a signed lift to show that their qutrit channel has zero private capacity. We show that Hermitian-smoothed measured-χ2 ordering characterizes when such lifts exist, even with a quantum reference. Environmental dominance in binary estimation at every blocklength yields a finite-code reliability--secrecy bound. These results explain why complete comparison prevents activation with antidegradable helpers whereas regularized comparison alone does not. Building on that qutrit example, we establish this stability for a range of noisy Werner--Holevo channels, determine sharp private-capacity and antidegradability thresholds, and compute exact complementary capacities in a nondegradable range. By contrast, we extend Pauli half-erasure activation to all 1/2≤p<1 and establish the same range for a new four-level family. Reference-assisted measured-χ2 witnesses show why these activating constructions lack complete comparison.
When does a difference in information become a way to communicate? Imagine two quantum channels as competing routes through noise. One might preserve a distinction that the other loses. That difference is interesting on its own; the question here is whether it can be turned into something operational: a channel that can carry private or quantum information at a positive rate. This paper presents a construction intended to make that step. Starting from a failure of complete quantum-channel information order, it constructs a channel claimed to have strictly positive ordinary private and quantum capacity. “Complete” matters because the comparison allows an input to be correlated with a finite quantum reference: information may be visible in the joint system even when it is hidden from the channel output alone. The construction accounts for the resources it uses, including transmission of the reference and uses of an activation helper. Its conclusion concerns strict positivity: a rate greater than zero, however small. It does not claim a uniform positive gap or fixed-error capacity inapproximability. The paper also develops reductions connecting the capacity questions to one-way distillable entanglement and secret key. The state constructions are designed to retain any prescribed lower bound on two-way distillation. On this basis, the manuscript claims exact-zero undecidability classifications for finite rational-complex memoryless channels and corresponding classifications for the one-way quantities. The information-order equivalences and undecidability premises used in these conclusions are developed in the companion paper, Complete information orders of quantum channels: equivalence and undecidability. A further introduction and citation details are available on the manuscript page.
An important distinction in our understanding of capacities of classical versus quantum channels is marked by the following question: is there an algorithm which can compute (or even efficiently compute) the capacity? While there is overwhelming evidence suggesting that quantum channel capacities may be uncomputable, a formal proof of any such statement is elusive. We initiate the study of the hardness of computing quantum channel capacities. We show that, for a general quantum channel, it is QMA-hard to compute its quantum capacity, and that the entanglement-assisted zero-error capacity under some restrictions is uncomputable; indicative of the fact that quantum channel capacities may generally be undecidable.
Quantum channels, also called quantum operations, are linear, trace preserving and completely positive transformations in the space of quantum states. Such operations describe discrete time evolution of an open quantum system interacting with an environment. The thesis contains an analysis of properties of quantum channels and different entropies used to quantify the decoherence introduced into the system by a given operation. Part I of the thesis provides a general introduction to the subject. In Part II, the action of a quantum channel is treated as a process of preparation of a quantum ensemble. The Holevo information associated with this ensemble is shown to be bounded by the entropy exchanged during the preparation process between the initial state and the environment. A relation between the Holevo information and the entropy of an auxiliary matrix consisting of square root fidelities between the elements of the ensemble is proved in some special cases. Weaker bounds on the Holevo information are also established. The entropy of a channel, also called the map entropy, is defined as the entropy of the state corresponding to the channel by the Jamiolkowski isomorphism. In Part III of the thesis, the additivity of the entropy of a channel is proved. The minimal output entropy, which is difficult to compute, is estimated by an entropy of a channel which is much easier to obtain. A class of quantum channels is specified, for which additivity of channel capacity is conjectured. The last part of the thesis contains characterization of Davies channels, which correspond to an interaction of a state with a thermal reservoir in the week coupling limit, under the condition of quantum detailed balance and independence of rotational and dissipative evolutions. The Davies channels are characterized for one-qubit and one-qutrit systems.
How much memory does it take to apply the same quantum channel many times, when each output must be released before the next input arrives and every retained qubit counts? One-use invariants do not decide it. Two explicit channels on dimension 1664 have identical normalized Choi spectra (32 eigenvalues 1/32), the same maximal complementary entropy 5, and zero asymptotic purity cost. At the same optimal exchange rate, one is implemented exactly with five memory qubits for any number of uses, while the other needs Omega(n^(1/(2 log_2(107)+2))) memory qubits for n uses, at every fixed error at most 1/16 and whatever purity is available; memory O(n^(1/3) log^(4/3) n) suffices for it. The hard channel is built from Houghton's group H_3. Behind the example is a general theory: the achievable exchange and purity rates, the purity cost kappa, which vanishes exactly on the closure of finite tracial factorizations, and memory bounds from how well a channel's environment is approximated by finite ones, and, for channels built from finite presentations, from the approximation profile of the group. Version 1.1 adds where the expensive channels lie: on the relative boundary of the closure; any fixed depolarizing admixture brings them down to polylogarithmic memory at the rank rate; on a face containing the Houghton channel a single moment of a trace on the group decides expense; and one free fermion per site already forces polynomial memory. Version 1.1.1 adds a map of what the main separation depends on (published inputs, companion results and new arguments), sets finite-budget and asymptotic-rate statements side by side, cites the companion papers at their published versions, pins the tested software versions, and makes every check refuse to run under optimized Python. The mathematical results are unchanged. Version 1.1.2 corrects attributions and makes two headline statements precise. The separation of Theorem A is stated at the exchange budget 5n/2, and the channels that need polynomial memory at every exchange rate are those with purity limited to O(log n). Credits added or corrected: Bisio, D'Ariano, Perinotti and Chiribella, and Bisio, D'Ariano, Perinotti and Sedlak; Boes et al. for the square-root dephasing construction; Lie, Son, Boes, Ng and Wilming for the exact case of the tracialization lemma; Faist, Berta and Brandao for the relation to the thermodynamic capacity; Haagerup, Musat and Rordam for the moment criteria; Thoma, Johnson, Watrous, Horodecki-Oppenheim-Winter and Lie-Jeong; Cornulier for the Baumslag-Solitar bound. Known results are moved out of numbered statements. The mathematical results and the numbering are unchanged. All operational bounds use complete-experiment error against adaptive observers with quantum references. The general rate-region achievability result uses a cited closed-device theorem; the explicit separation does not. This preprint archive includes the PDF, TeX source, finite verification scripts, and scoped Lean arithmetic proofs. The artifacts do not formally verify the entire manuscript; their scope and external dependencies are documented in verification/README.md.
Quantum experiments without a definite causal order offer new ways to distinguish devices, estimate physical parameters, and communicate. We prove a common limit on these tasks: the geometric Rényi divergence at the output of a deterministic completely positive process cannot exceed the sum of the divergences of its individual channel uses. The inequality holds for every Rényi order in (0,1)∪(1,2] and any number of independently replaceable channels. Parallel experiments with separate reference-assisted inputs approach the bound, giving an exact equality after optimization over processes. We also prove an additive bound on the right logarithmic derivative Fisher information of parameter-dependent channels under every fixed process in this class. A resulting Cramér--Rao bound limits locally unbiased estimation precision without assuming a definite causal order, and an erasure-probability example attains the bound. The proofs for the geometric Rényi divergence and RLD Fisher information follow from the requirement that every independent choice of channels produce a normalized output. We show how this requirement controls positive local operations, and how small channel perturbations convert the divergence inequality into a Fisher-information bound, including for singular channels. Further applications give finite-use bounds on channel discrimination and exclusion, together with communication and private-state-generation converses when the processes preserve the relevant comparison conditions.