Omar Fawzi

We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. Our hardness results also hold for deciding if the contraction coefficient is equal to 1. As a consequence, we show that deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.

We study the complexity of computing the mixed Schatten $\|\Phi\|_{q\to p}$ norms of linear maps $\Phi$ between matrix spaces. When $\Phi$ is completely positive, we show that $\| \Phi \|_{q \to p}$ can be computed efficiently when $q \geq p$. The regime $q \geq p$ is known as the non-hypercontractive regime and is also known to be easy for the mixed vector norms $\ell_{q} \to \ell_{p}$ [Boyd, 1974]. However, even for entanglement-breaking completely-positive trace-preserving maps $\Phi$, we show that computing $\| \Phi \|_{1 \to p}$ is $\NP$-complete when $p>1$. Moving beyond the completely-positive case and considering $\Phi$ to be difference of entanglement breaking completely-positive trace-preserving maps, we prove that computing $\| \Phi \|^+_{1 \to 1}$ is $\NP$-complete. In contrast, for the completely-bounded (cb) case, we describe a polynomial-time algorithm to compute $\|\Phi\|_{cb,1\to p}$ and $\|\Phi\|^+_{cb,1\to p}$ for any linear map $\Phi$ and $p\geq1$.

The rates of several device-independent (DI) protocols, including quantum key-distribution (QKD) and randomness expansion (RE), can be computed via an optimization of the conditional von Neumann entropy over a particular class of quantum states. In this work we introduce a numerical method to compute lower bounds on such rates. Our rate calculations are valid for systems on general separable Hilbert spaces and we also investigate the convergence of our method to the actual rate, proving convergence in certain situations. Applying our method to compute the rates of DI-RE and DI-QKD protocols we find substantial improvements over all previous numerical techniques, demonstrating significantly higher rates for both DI-RE and DI-QKD. In particular, for DI-QKD we show a new minimal detection efficiency threshold which is within the realm of current capabilities. Moreover, we demonstrate that our method is able to converge rapidly by recovering instances of all known tight analytical bounds. Finally, we note that our method is compatible with the entropy accumulation theorem and can thus be used to compute rates of finite round protocols and subsequently prove their security.

Abstract In the analysis of quantum information processing tasks, the choice of distance measure between states or channels often plays a crucial role. This submission introduces new quantum Rnyi divergences for states and channels that are based on a convex optimization program involving the matrix geometric mean. These divergences have mathematical and computational properties that make them applicable to a wide variety of problems. We use these Rnyi divergences to obtain semidefinite programming lower bounds on the key rates for device-independent cryptography, and in particular we find a new bound on the minimal detection efficiency required to perform device-independent quantum key distribution without additional noisy preprocessing. Furthermore, we give several applications to quantum Shannon theory, in particular proving that adaptive strategies do not help in the strong converse regime for quantum channel discrimination and obtaining improved bounds for quantum capacities.

Removing assumptions about devices and signals from quantum cryptography protocols is an important task. Often it is assumed that measurements are memoryless and each signal is measured independently. We aim to remove this assumption by considering a related problem involving what we call quantum exams: First assume a student has a quantum memory which has an encoding of a classical string. Consider that the student is asked to produce a small subset of the string (i.e. and exam), and then is asked for another subset of the string. If the student can make a good estimate in the first exam, he should be able to also make a good estimate in the second exam. We examine this problem in the case of a classical or quantum memory for the student, and its relation to quantum cryptography.