This article will examine states that superpose different amounts of entanglement and protocols that run in superposition but generate or consume different amounts of entanglement. In both cases we find a uniquely quantum difficulty: entanglement cannot be conditionally discarded without either using communication or causing decoherence. I will first describe the problem of entanglement spread in states and operations, as well as some methods of dealing with it. Then I'll describe three applications to problems that at first glance appear to be quite different: first, a reinterpretation of the old observation that creating n partially entangled states from singlets requires theta(sqrt(n)) communication, but cannot itself be used to communicate; second, a new lower bound technique for communication complexity; third, an explanation of how to extend the quantum reverse Shannon theorem from tensor power sources to general sources.
This article will examine states that superpose different amounts of entanglement and protocols that run in superposition but generate or consume different amounts of entanglement. In both cases we find a uniquely quantum difficulty: entanglement cannot be conditionally discarded without either using communication or causing decoherence. I will first describe the problem of entanglement spread in states and operations, as well as some methods of dealing with it. Then I'll describe three applications to problems that at first glance appear to be quite different: first, a reinterpretation of the old observation that creating n partially entangled states from singlets requires theta(sqrt(n)) communication, but cannot itself be used to communicate; second, a new lower bound technique for communication complexity; third, an explanation of how to extend the quantum reverse Shannon theorem from tensor power sources to general sources.
This article will examine states that superpose different amounts of entanglement and protocols that run in superposition but generate or consume different amounts of entanglement. In both cases we find a uniquely quantum difficulty: entanglement cannot be conditionally discarded without either using communication or causing decoherence. I will first describe the problem of entanglement spread in states and operations, as well as some methods of dealing with it. Then I’ll describe three applications to problems that at first glance appear to be quite different: first, a reinterpretation of the old observation that creating n partially entangled states from singlets requires θ ( √ n) communication, but cannot itself be used to communicate; second, a new lower bound technique for communication complexity; third, an explanation of how to extend the quantum reverse Shannon theorem from tensor power sources to general sources. 1
One of the many bizarre features of entanglement is that Alice, by sending a qubit to Bob in a separable state, can generate some entanglement between herself and Bob. This protocol is stripped down to the bare essentials to better elucidate the key properties of the initial resource state that enable this entanglement distribution. The necessary and sufficient conditions under which the correlations of a Bell-diagonal state serve as a useful resource are proven, giving upper and lower bounds on the entanglement that can be distributed when those conditions are met.
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly⊆PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP⊂BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).
The main focus of this thesis is quantum entanglement and, more specifically, pro- tocols that allow its distribution between distant places. In the last decades, with the rise of attention on quantum technologies, entangle- ment is mostly seen as a resource, that could be exchanged, measured, and ideally stored and used when convenient. However, entanglement is not as stable and cheap as the classical resources. One reason for this is that entanglement between two quantum systems is easily disrupted by the interaction with the environment that surrounds them. The presence of noise is even more significant when we wish to entangle two systems that are very far away, a task that is essential for quantum communication technologies. In this case, what can disrupt the entanglement is not only the noise that the particles experience locally, but also the noise in the quantum channel during the communication process, which can be significant over long distances. For this reason, it is important to design distribution protocols that work well in such conditions. In 2003, Cubitt et al. showed the existence of a very curious class of protocols, often called entanglement distribution with separable states (EDSS). They proved that a non-entangled (separable) carrier can be used to increase, or even gener- ate entanglement between two already distant parties. From this, some questions arise. First, what limits or allows an entanglement distribution protocol, if not the entanglement that is sent. Quantum discord was shown to be a necessary, but not sufficient, resource for entanglement distribution. Another natural question is whether these protocols can beat others, for technological purposes, especially in noisy conditions. I will describe some work I have done in an attempt to partially 9 address both of these questions. After introducing various tools and concepts that are useful to understand this topic (chapter 1) and motivate the necessity of entanglement distribution in quantum communication (chapter 2), I will describe a proof-of-principle experiment demon- strating EDSS schemes (chapter 3). Later (chapter 4), I will introduce a more general classification of distribution protocols (excessive or non-excessive protocols), based on whether the entanglement gain is larger than the one that is communicated, describing specific examples and general properties of such protocols. I will then partially address the problem regarding the robustness to the noise of communica- tion protocols (chapter 5). Finally, in chapter 6, I will describe how entanglement of a bipartite state can grow with a quantum measurement with unknown results. I discuss the properties of the measurement and of the initial state that make this process effective.
Dual to the usual noisy channel coding problem, where a noisy (classical or quantum) channel is used to simulate a noiseless one, reverse Shannon theorems concern the use of noiseless channels to simulate noisy ones, and more generally the use of one noisy channel to simulate another. For channels of nonzero capacity, this simulation is always possible, but for it to be efficient, auxiliary resources of the proper kind and amount are generally required. In the classical case, shared randomness between sender and receiver is a sufficient auxiliary resource, regardless of the nature of the source, but in the quantum case the requisite auxiliary resources for efficient simulation depend on both the channel being simulated, and the source from which the channel inputs are coming. For tensor power sources (the quantum generalization of classical IID sources), entanglement in the form of standard ebits (maximally entangled pairs of qubits) is sufficient, but for general sources, which may be arbitrarily correlated or entangled across channel inputs, additional resources, such as entanglement-embezzling states or backward communication, are generally needed. Combining existing and new results, we establish the amounts of communication and auxiliary resources needed in both the classical and quantum cases, the tradeoffs among them, and the loss of simulation efficiency when auxiliary resources are absent or insufficient. In particular we find a new single-letter expression for the excess forward communication cost of coherent feedback simulations of quantum channels (i.e. simulations in which the sender retains what would escape into the environment in an ordinary simulation), on non-tensor-power sources in the presence of unlimited ebits but no other auxiliary resource. Our results on tensor power sources establish a strong converse to the entanglement-assisted capacity theorem.
Entanglement concentration requires no classical communication, but the best prior art result for diluting to N copies of a partially entangled state requires an amount of communication on the order of sqrt(N) bits. Our main result is to prove this prior art result optimal up to a constant factor; any procedure for creating N partially entangled states from singlets requires Omega(sqrt(N)) bits of classical communication. Previously not even a constant bound was known for approximate entanglement transforms. We also prove a lower bound on the inefficiency of the process: to dilute singlets to N copies of a partially entangled state, the entropy of entanglement must decrease by Omega(sqrt(N)).