Degradation and Amplification of Computational Hardness

Peixue Wu, Yunkai Wang

We investigate superadditivity of quantum capacity through private channels whose Choi-Jamiolkowski operators are private states. This perspective links the security structure of private states to quantum capacity and clarifies the role of the shield system: information encoded in the shield system that would otherwise leak to the environment can be recycled when paired with an assisting channel, thereby boosting capacity. Our main contributions are threefold: Firstly, we develop a general framework that provides a sufficient condition for capacity amplification, which is formulated in terms of the assisting channel's Holevo information. As examples, we give explicit, dimension and parameter dependent amplification thresholds for erasure and depolarizing channels. Secondly, assuming the Spin alignment conjecture, we derive a single-letter expression for the quantum capacity of a family of private channels that are neither degradable, anti-degradable, nor PPT; as an application, we construct channels with vanishing quantum capacity yet unbounded private capacity. Thirdly, we further analyze approximate private channels: we give an alternative proof of superactivation that extends its validity to a broader parameter regime, and, by combining amplification bounds with continuity estimates, we establish a metric separation showing that channels exhibiting capacity amplification have nonzero diamond distance from the set of anti-degradable channels, indicating that existing approximate (anti-)degradability bounds are not tight. We also revisit the computability of the regularized quantum capacity and modestly suggest that this fundamental question still remains open.

Ashley M. Aitken

Bill Rosgen

The computational problem of distinguishing two quantum channels is central to quantum computing. It is a generalization of the well-known satisfiability problem from classical to quantum computation. This problem is shown to be surprisingly hard: it is complete for the class QIP of problems that have quantum interactive proof systems, which implies that it is hard for the class PSPACE of problems solvable by a classical computation in polynomial space. Several restrictions of distinguishability are also shown to be hard. It is no easier when restricted to quantum computations of logarithmic depth, to mixed-unitary channels, to degradable channels, or to antidegradable channels. These hardness results are demonstrated by finding reductions between these classes of quantum channels. These techniques have applications outside the distinguishability problem, as the construction for mixed-unitary channels is used to prove that the additivity problem for the classical capacity of quantum channels can be equivalently restricted to the mixed unitary channels.

O. Ozan Koyluoglu, Rajiv Soundararajan, Sriram Vishwanath

This paper considers a state dependent broadcast channel with one transmitter, Alice, and two receivers, Bob and Eve. The problem is to effectively convey (“amplify”) the channel state sequence to Bob while “masking” it from Eve. The extent to which the state sequence cannot be masked from Eve is referred to as leakage. This can be viewed as a secrecy problem, where we desire that the channel state itself be minimally leaked to Eve while being communicated to Bob. This paper is aimed at characterizing the tradeoff region between amplification and leakage rates for such a system. An achievable coding scheme is presented, wherein the transmitter transmits a partial state information over the channel to facilitate the amplification process. For the case when Bob observes a stronger signal than Eve, the achievable coding scheme is enhanced with secure refinement. Outer bounds on the tradeoff region are also derived, and used in characterizing some special case results. In particular, the optimal amplification-leakage rate difference, called as differential amplification capacity, is characterized for the reversely degraded discrete memoryless channel, the degraded binary, and the degraded Gaussian channels. In addition, for the degraded Gaussian model, the extremal corner points of the tradeoff region are characterized, and the gap between the outer bound and achievable rate-regions is shown to be less than half a bit for a wide set of channel parameters.