The existence of quantum uncertainty relations is the essential reason that some classically unrealizable cryptographic primitives become realizable when quantum communication is allowed. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking [ 2004]. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n-bit message is encoded in a quantum system using a classical key of size much smaller than n. Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message, in which case the message is said to be “locked”. Furthermore, knowing the key, it is possible to recover, that is “unlock”, the message. In this article, we make the following contributions by exploiting a connection between uncertainty relations and low-distortion embeddings of Euclidean spaces into slightly larger spaces endowed with the e1 norm. We introduce the notion of a metric uncertainty relation and connect it to low-distortion embeddings of e2 into e1. A metric uncertainty relation also implies an entropic uncertainty relation. We prove that random bases satisfy uncertainty relations with a stronger definition and better parameters than previously known. Our proof is also considerably simpler than earlier proofs. We then apply this result to show the existence of locking schemes with key size independent of the message length. Moreover, we give efficient constructions of bases satisfying metric uncertainty relations. The bases defining these metric uncertainty relations are computable by quantum circuits of almost linear size. This leads to the first explicit construction of a strong information locking scheme. These constructions are obtained by adapting an explicit norm embedding due to Indyk [2007] and an extractor construction of [2009]. We apply our metric uncertainty relations to exhibit communication protocols that perform equality testing of n-qubit states. We prove that this task can be performed by a single message protocol using O(log2 n) qubits and n bits of communication, where the computation of the sender is efficient.
Aubrun, Szarek and Werner @cite_17 @cite_29 also used a connection between low-distortion embeddings and quantum information. They show in @cite_17 that the existence of large subspaces of highly entangled states follows from Dvoretzky's theorem for the Schatten @math -norm The Schatten @math -norm of a matrix @math is defined as the @math norm of a vector of singular values of @math . for @math . This in turns shows the existence of channels that violate additivity of minimum output @math -R 'enyi entropy as was previously demonstrated by @cite_55 . Using a more delicate argument @cite_64 , they are also able to recover Hastings' @cite_81 counterexample to the additivity conjecture.
@cite_64 @cite_55 @cite_29 @cite_81 @cite_17
2071160621 1972266216 1975244148 2020559278
For all p > 1, we demonstrate the existence of quantum channels with non-multiplicative maximal output p-norms. Equivalently, for all p > 1, the minimum output Renyi entropy of order p of a quantum channel is not additive. The violations found are large; in all cases, the minimum output Renyi entropy of order p for a product channel need not be significantly greater than the minimum output entropy of its individual factors. Since p = 1 corresponds to the von Neumann entropy, these counterexamples demonstrate that if the additivity conjecture of quantum information theory is true, it cannot be proved as a consequence of any channel-independent guarantee of maximal p-norm multiplicativity. We also show that a class of channels previously studied in the context of approximate encryption lead to counterexamples for all p > 2. In this paper we obtain new bounds for the minimum output entropies of random quantum channels. These bounds rely on random matrix techniques arising from free probability theory. We then revisit the counterexamples developed by Hayden and Winter to get violations of the additivity equalities for minimum output Renyi entropies. We show that random channels obtained by randomly coupling the input to a qubit violate the additivity of the @math -Renyi entropy. For some sequences of random quantum channels, we compute almost surely the limit of their Schatten @math norms. We reduce the number of open additivity problems in quantum information theory by showing that four of them are equivalent. Namely, we show that the conjectures of additivity of the minimum output entropy of a quantum channel, additivity of the Holevo expression for the classical capacity of a quantum channel, additivity of the entanglement of formation, and strong superadditivity of the entanglement of formation, are either all true or all false. We consider the image of some classes of bipartite quantum states under a tensor product of random quantum channels. Depending on natural assumptions that we make on the states, the eigenvalues of their outputs have new properties which we describe. Our motivation is provided by the additivity questions in quantum information theory, and we build on the idea that a Bell state sent through a product of conjugated random channels has at least one large eigenvalue. We generalize this setting in two directions. First, we investigate general entangled pure inputs and show that Bell states give the least entropy among those inputs in the asymptotic limit. We then study mixed input states, and obtain new multi-scale random matrix models that allow to quantify the difference of the outputs’ eigenvalues between a quantum channel and its complementary version in the case of a non-pure input.