We correct an error in the proof of Theorem 11 in our paper “Approximate Degradable Quantum Channels”, IEEE Trans. Inf. Theory, vol. 63, no. 12, pp. 7832-7844, 2017, concerning an upper bound on the private capacity of an approximate anti-degradable channel. Furthermore, we show how to obtain a tighter bound for the quantum capacity.

Circuit knitting is the process of partitioning large quantum circuits into smaller subcircuits such that the result of the original circuits can be deduced by only running the subcircuits. Such techniques will be crucial for near-term and early fault-tolerant quantum computers, as the limited number of qubits is likely to be a major bottleneck for demonstrating quantum advantage. One typically distinguishes between gate cuts and wire cuts when partitioning a circuit. The cost for any circuit knitting approach scales exponentially in the number of cuts. One possibility to realize a cut is via the quasiprobability simulation technique. In fact, we argue that all existing rigorous circuit knitting techniques can be understood in this framework. Furthermore, we characterize the optimal overhead for wire cuts where the subcircuits can exchange classical information or not. We show that the optimal cost for cuttingnwires without and with classical communication between the subcircuits scales asO(16n) andO(4n), respectively.

Uhlmann’s theorem states that, for any two quantum states ρABand σA, there exists an extension σABof σAsuch that the fidelity between ρABand σABequals the fidelity between their reduced states ρAand σA. In this work, we generalize Uhlmann’s theorem to α-R´enyi relative entropies for α ∈ [1/2, ∞], a family of divergences that encompasses fidelity, relative entropy, and max-relative entropy corresponding to α = 1/2, α = 1, and α = ∞, respectively.

We introduce a novel capacity measure 2sED for statistical models based on the effective dimension. The new quantity provably bounds the generalization error under mild assumptions on the model. Furthermore, simulations on standard data sets and popular model architectures show that 2sED correlates well with the training error. For Markovian models, we show how to efficiently approximate 2sED from below through a layerwise iterative approach, which allows us to tackle deep learning models with a large number of parameters. Simulation results suggest that the approximation is good for different prominent models and data sets.

The scarcity of qubits is a major obstacle to the practical usage of quantum computers in the near future. To circumvent this problem, various circuit knitting techniques have been developed to partition large quantum circuits into subcircuits that fit on smaller devices, at the cost of a simulation overhead. In this work, we study a particular method of circuit knitting based on quasiprobability simulation of nonlocal gates with operations that act locally on the subcircuits. We investigate whether classical communication between these local quantum computers can help. We provide a positive answer by showing that for circuits containing$n$nonlocal CNOT gates connecting two circuit parts, the simulation overhead can be reduced from$O(9^{n})$to$O(4^{n})$if one allows for classical information exchange. Similar improvements can be obtained for general Clifford gates and, at least in a restricted form, for other gates such as controlled rotation gates.

The min-entropy of a quantum system A conditioned on another quantum system E describes how much randomness can be extracted from A with respect to an adversary in possession of E. This quantity plays a crucial role in quantum cryptography: the security proofs of many quantum cryptographic protocols reduce to showing a lower bound on such a min-entropy. Here, we develop a new tool, called generalised entropy accumulation, for computing such bounds. Concretely, we consider a sequential process in which each step outputs a system Aiand updates a side information register E. We prove that if this process satisfies a natural “non-signalling” condition between past outputs and future side information, the min-entropy of the outputs $A_{1},\ldots,\ A_{n}$ conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) [1], which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition.Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. In particular, it is the first general tool that is applicable to mistrustful device-independent cryptography. To demonstrate this, we give the first security proof for blind randomness expansion [2] against general adversaries. Furthermore, our generalised EAT can be used to give improved security proofs for quantum key distribution [3], and also has applications beyond quantum cryptography.

Quantum computations are typically performed as a sequence of basic operations, called quantum gates. Different gate sequences, called quantum circuits, can implement the same overall quantum computation. Since every additional quantum gate takes time and introduces noise into the system, it is important to find the smallest possible quantum circuit that implements a given computation, especially for near-term quantum devices that can execute only a limited number of quantum gates before noise renders the computation useless. An important building block for many quantum circuit optimization techniques is pattern matching: given a large and small quantum circuit, we would like to find all maximal matches of the small circuit, called a pattern , in the large circuit, considering pairwise commutation of quantum gates. In this work, we present the first classical algorithm for pattern matching that provably finds all maximal matches and is efficient enough to be practical for circuit sizes typical for near-term devices. We demonstrate numerically 1 that combining our algorithm with known pattern-matching-based circuit optimization techniques reduces the gate count of a random quantum circuit by ∼ 30% and can further improve practically relevant quantum circuits that were already optimized with state-of-the-art techniques.

Lyapunov exponents describe the asymptotic behavior of the singular values of large products of random matrices. A direct computation of these exponents is however often infeasible. By establishing a link between Lyapunov exponents and an information theoretic tool called entropy accumulation theorem we derive an upper and a lower bound for the maximal and minimal Lyapunov exponent, respectively. The bounds assume independence of the random matrices, are analytical, and are tight in the commutative case as well as in other scenarios. They can be expressed in terms of an optimization problem that only involves single matrices rather than large products. The upper bound for the maximal Lyapunov exponent can be evaluated efficiently via the theory of convex optimization.

We consider the problem of estimating a probability distribution that maximizes the entropy while satisfying a finite number of moment constraints, possibly corrupted by noise. Based on duality of convex programming, we present a novel approximation scheme using a smoothed fast gradient method that is equipped with explicit bounds on the approximation error. We further demonstrate how the presented scheme can be used for approximating the chemical master equation through the zero-information moment closure method, and for an approximate dynamic programming approach in the context of constrained Markov decision processes with uncountable state and action spaces.

Quantum generalizations of Rényi's entropies are a useful tool to describe a variety of operational tasks in quantum information processing. Two families of such generalizations turn out to be particularly useful: the Petz quantum Rényi divergence D̅αand the minimal quantum Rényi divergence D̅α. In this paper, we prove a reverse Araki-Lieb-Thirring inequality that implies a new relation between these two families of divergences, namely that αD̅α(ρ∥σ) ≤ D̅α(ρ∥σ) for α ϵ [0, 1] and where ρ and σ are density operators. This bound suggests defining a “pretty good fidelity”, whose relation to the usual fidelity implies the known relations between the optimal and pretty good measurement as well as the optimal and pretty good singlet fraction.

A Markov chain is a tripartite quantum state ρABCwhere there exists a recovery map RB→BCsuch that ρABC= RB→BC(ρAB). More generally, an approximate Markov chain ρABCis a state whose distance to the closest recovered state RB→BC(ρAB) is small. Recently it has been shown that this distance can be bounded from above by the conditional mutual information I(A : C|B)ρof the state. We improve on this connection by deriving the first bound that is tight in the commutative case and features an explicit recovery map that only depends on the reduced state pBC. The key tool in our proof is a multivariate extension of the Golden-Thompson inequality, which allows us to extend logarithmic trace inequalities from two to arbitrarily many matrices.

Quantum generalizations of Rényi's entropies are a useful tool to describe a variety of operational tasks in quantum information processing. Two families of such generalizations turn out to be particularly useful: the Petz quantum Rényi divergence D̅αand the minimal quantum Rényi divergence D̃α. In this paper, we prove a reverse Araki-Lieb-Thirring inequality that implies a new relation between these two families of divergences, namely, αD̅α(Q∥σ) ≤ D̃α(Q∥σ) for α ∈[0,1] and where Q and σ are density operators. This bound suggests defining a ”pretty good fidelity,” whose relation to the usual fidelity implies the known relations between the optimal and pretty good measurement as well as the optimal and pretty good singlet fraction. We also find a new necessary and sufficient condition for optimality of the pretty good measurement and singlet fraction.

Degradable quantum channels are an important class of completely positive trace-preserving maps. Among other properties, they offer a single-letter formula for the quantum and the private classical capacity and are characterized by the fact that a complementary channel can be obtained from the channel by applying a degrading channel. In this paper, we introduce the concept of approximate degradable channels, which satisfy this condition up to some finite ε ≥ 0. That is, there exists a degrading channel which upon composition with the channel is ε-close in the diamond norm to the complementary channel. We show that for any fixed channel the smallest such ε can be efficiently determined via a semidefinite program. Moreover, these approximate degradable channels also approximately inherit all other properties of degradable channels. As an application, we derive improved upper bounds to the quantum and private classical capacity for certain channels of interest in quantum communication.

The quantum relative entropy is well known to obey a monotonicity property (i.e., it does not increase under the action of a quantum channel). Here we present several refinements of this entropy inequality, some of which have a physical interpretation in terms of recovery from the action of the channel. The recovery channel given here is explicit and universal, depending only on the channel and one of the arguments to the relative entropy.

The quantum relative entropy between two states satisfies a monotonicity property, meaning that applying the same quantum channel to both states can never increase their relative entropy. It is known that this inequality is only tight when there is a “recovery map” that exactly reverses the effects of the quantum channel on both states. In this paper we strengthen this inequality by showing that the difference of relative entropies is bounded below by the measured relative entropy between the first state and a recovered state from its processed version. The recovery map is a convex combination of rotated Petz recovery maps and perfectly reverses the quantum channel on the second state. As a special case we reproduce recent lower bounds on the conditional mutual information such as the one proved in [Fawzi and Renner, Commun. Math. Phys., 2015]. Our proof only relies on elementary properties of pinching maps and the operator logarithm.

Arıkan's polar coding technique is based on the idea of synthesizing n channels from the n instances of the physical channel by a simple linear encoding transformation. Each synthesized channel corresponds to a particular input to the encoder. For large n, the synthesized channels become either essentially noiseless or almost perfectly noisy, but in total carry as much information as the original n channels. Capacity can therefore be achieved by transmitting messages over the essentially noiseless synthesized channels. Unfortunately, the set of inputs corresponding to reliable synthesized channels is poorly understood, in particular, how the set depends on the underlying physical channel. In this work, we present two analytic conditions sufficient to determine if the reliable inputs corresponding to different discrete memoryless channels are aligned or not, i.e., if one set is contained in the other. Understanding the alignment of the polarized sets is important as it is directly related to universality properties of the induced polar codes, which are essential in particular for network coding problems. We demonstrate the performance of our conditions on a few examples for wiretap and broadcast channels. Finally, we show that these conditions imply that the simple quantum polar coding scheme of Renes et al. [Phys. Rev. Lett., 109, 050504, 2012] requires entanglement assistance for general channels, but also show such assistance to be unnecessary in many cases of interest.

We propose an iterative method for approximating the capacity of classical-quantum channels with a discrete input alphabet and a finite-dimensional output under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. To provide an additive ε-close estimate to the capacity, the presented algorithm requires O((N ν M)M3log(N)1/2ε-1) steps, where N denotes the input alphabet size and M denotes the output dimension. We then generalize the method to the task of approximating the capacity of classical-quantum channels with a bounded continuous input alphabet and a finite-dimensional output. This, using the idea of a universal encoder, allows us to approximate the Holevo capacity for channels with a finite-dimensional quantum mechanical input and output. In particular, we show that the problem of approximating the Holevo capacity can be reduced to a multi-dimensional integration problem. For certain families of quantum channels, we prove that the complexity to derive an additive ε-close solution to the Holevo capacity is subexponential or even polynomial in the problem size. We provide several examples to illustrate the performance of the approximation scheme in practice.

The quantum relative entropy between two states satisfies a monotonicity property meaning that applying the same quantum channel to both states can never increase their relative entropy. It is known that this inequality is only tight when there is a recovery map that exactly reverses the effects of the quantum channel on both states. In this paper, we strengthen this inequality by showing that the difference of relative entropies is bounded below by the measured relative entropy between the first state and a recovered state from its processed version. The recovery map is a convex combination of rotated Petz recovery maps and perfectly reverses the quantum channel on the second state. As a special case, we reproduce recent lower bounds on the conditional mutual information, such as the one proved by Fawzi and Renner. Our proof only relies on the elementary properties of pinching maps and the operator logarithm.

Arikan's polar coding technique is based on the idea of synthesizing n channels from the n instances of the physical channel by a simple linear encoding transformation. Each synthesized channel corresponds to a particular input to the encoder. For large n, the synthesized channels become either essentially noiseless or almost perfectly noisy, but in total carry as much information as the original n channels. Capacity can therefore be achieved by transmitting messages over the essentially noiseless synthesized channels. Unfortunately, the set of inputs corresponding to reliable synthesized channels is poorly understood, in particular how the set depends on the underlying physical channel. In this work, we present two analytic conditions sufficient to determine if the reliable inputs corresponding to different discrete memoryless channels are aligned or not, i.e. if one set is contained in the other. Understanding the alignment of the polarized sets is important as it is directly related to universality properties of the induced polar codes, which are essential in particular for network coding problems. Finally we show that these conditions imply that the simple quantum polar coding scheme of Renes et al. [Phys. Rev. Lett. 109, 050504 (2012)] requires entanglement assistance for general channels, but also show such assistance to be unnecessary in many cases of interest.

Degradable quantum channels are an important class of completely positive trace-preserving maps. Among other properties, they offer a single-letter formula for the quantum and the private classical capacity and are characterized by the fact that the complementary channel can be obtained from the channel by applying a degrading map. In this work we introduce the concept of approximate degradable channels, which satisfy this condition up to some finite ε ≥ 0. That is, there exists a degrading map which upon composition with the channel is ε-close in the diamond norm to the complementary channel. We show that for any fixed channel the smallest such ε can be efficiently determined via a semidefinite program. Moreover, these approximate degradable channels also approximately inherit all other properties of degradable channels. As an application, we derive improved upper bounds to the quantum and private classical capacity for certain channels of interest in quantum communication.

We construct an explicit quantum coding scheme which achieves a communication rate not less than the coherent information when used to transmit the quantum information over a noisy quantum channel. For Pauli and erasure channels, we also present efficient encoding and decoding algorithms for this communication scheme based on polar codes (essentially linear in the blocklength), but which do not require the sender and receiver to share any entanglement before the protocol begins. Due to the existence of degeneracies in the involved error-correcting codes, it is indeed possible that the rate of the scheme exceeds the coherent information. We provide a simple criterion which indicates such performance. Finally, we discuss how the scheme can be used for secret key distillation as well as private channel coding.

We propose an iterative method for approximately computing the capacity of discrete memoryless channels, possibly under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. The presented method requires O(M2N√log N/ε) to provide an estimate of the capacity to within ε, where N and M denote the input and output alphabet size; a single iteration has a complexity O(MN). We also show how to approximately compute the capacity of memoryless channels having a bounded continuous input alphabet and a countable output alphabet under some mild assumptions on the decay rate of the channel's tail. It is shown that discrete-time Poisson channels fall into this problem class. As an example, we compute sharp upper and lower bounds for the capacity of a discrete-time Poisson channel with a peak-power input constraint.

We propose an iterative method for efficiently approximating the capacity of discrete memoryless channels, possibly having additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. To find an ε-approximation of the capacity, in case of no additional input constraints, the presented method has a computational complexity O(1 over εM2N√logN), where N and M denote the input and output alphabet size, and a single iteration has a complexity O(MN).

We present a new algorithm, based on duality of convex programming and the specific structure of the channel capacity problem, to iteratively construct upper and lower bounds for the capacity of memoryless channels having continuous input and countable output alphabets. Under a mild assumption on the decay rate of the channel's tail, explicit bounds for the approximation error are provided. We demonstrate the applicability of our result on the discrete-time Poisson channel having a peak-power input constraint.

We prove two results on the universality of polar codes for source coding and channel communication. First, we show that for any polar code built for a source PX,Zthere exists a slightly modified polar code-having the same rate, the same encoding and decoding complexity and the same error rate-that is universal for every source PX,Ywhen using successive cancellation decoding, at least when the channel PY|Xis more capable than PZ|Xand PXis such that it maximizes I(X; Y )-I(X;Z) for the given channels PY|Xand PZ|X. This result extends to channel coding for discrete memoryless channels. Second, we prove that polar codes using successive cancellation decoding are universal for less noisy discrete memoryless channels.

We construct an explicit entanglement distillation scheme which achieves the coherent information when used to send quantum information over a noisy quantum channel. For Pauli and erasure channels we present efficient encoding and decoding algorithms based on polar codes. Unlike previous constructions, this scheme does not require the sender and receiver to share noiseless entanglement before the protocol begins. It is possible, but still unproven, that the scheme even achieves a rate beyond the coherent information, due to degeneracies of certain error correcting codes. Finally we discuss how the scheme can be used for secret key distillation and private channel coding.

We construct a channel coding scheme to achieve the capacity of any discrete memoryless channel based solely on the techniques of polar coding. In particular, we show how source polarization and randomness extraction via polarization can be employed to “shape” uniformly-distributed i.i.d. random variables into approximate i.i.d. random variables distributed according to the capacity-achieving distribution. We then combine this shaper with a variant of polar channel coding, constructed by the duality with source coding, to achieve the channel capacity. Our scheme inherits the low complexity encoder and decoder of polar coding. It differs conceptually from Gallager's method for achieving capacity, and we discuss the advantages and disadvantages of the two schemes. An application to the AWGN channel is discussed.