One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet there are ways of conveying information with exponentially fewer qubits than possible classically. Moreover, these methods have a very simple structure---they involve little interaction between the communicating parties. We look more closely at the ways in which information encoded in quantum states may be manipulated, and consider the question as to whether every classical protocol may be transformed to a ``simpler'' quantum protocol of similar efficiency. By a simpler protocol, we mean a protocol that uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity, thus answering the above question in the negative. Our result builds on two primitives, local transitions in bi-partite states (based on previous work) and average encoding which may be of significance in other applications as well.
In some scenarios there are ways of conveying information with many fewer, even exponentially fewer, qubits than possible classically. Moreover, some of these methods have a very simple structure-they involve only few message exchanges between the communicating parties. It is therefore natural to ask whether every classical protocol may be transformed to a "simpler" quantum protocol-one that has similar efficiency, but uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity. This, in particular, proves a round hierarchy theorem for quantum communication complexity, and implies, via a simple reduction, an Omega(N1k/) lower bound for k message quantum protocols for Set Disjointness for constant k. Enroute, we prove information-theoretic lemmas, and define a related measure of correlation, the informational distance, that we believe may be of significance in other contexts as well
We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model of quantum private simultaneous message protocols (QPSM), where classical communication is free, and quantum communication is the primary complexity measure. We show the following upper and lower bounds. (1) For every quantum channel mapping
n to
m qubits, we give a QPSM protocol with quantum communication
m, using exponential pre-shared entanglement. In particular, constant-output channels have
O(1) quantum communication, and classical-output channels require no quantum communication. (2) With
O(n) pre-shared entanglement, every one-qubit-output channel has an
O(n)-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant
c>0 for which any protocol with at most
cn pre-shared entanglement requires
Ω(n) quantum communication. (3) In contrast, we identify a structured class of quantum channels, Clifford-induced channels, for which there exist QPSM protocols with
O(n) pre-shared entangled qubits and only
O(1) quantum communication complexity. Through our connection, we obtain analogous upper and lower bounds on the quantum encoding size of QDRE. Our results show that the amount of pre-shared entanglement plays a central role in quantum encoding size and quantum communication complexity.
This dissertation is motivated by the following fundamental questions: (a) are there any exponential gaps between quantum and classical communication complexities? (b) what is the role of entanglement in assisting quantum communications? (c) how to characterize the nonlocality of quantum operations? We study four specific problems below. 1. The communication complexity of the Hamming Distance problem. The Hamming Distance problem is for two parties to determine whether or not the Hamming distance between two n-bit strings is more than a given threshold. We prove tighter quantum lower bounds in the general two-party, interactive communication model. We also construct an efficient classical protocol in the more restricted Simultaneous Message Passing model, improving previous results. 2. The Log-Equivalence Conjecture. A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical ones for computing a total Boolean function in the two-party, interactive model. The answer is believed to be No. Razborov proved this conjecture for the most general class of functions so far. We prove this conjecture for a broader class of functions that we called block-composed functions. Our proof appears to be the first demonstration of the dual approach of the polynomial method in proving new results. 3. Classical simulations of bipartite quantum measurement. We define a new ix concept that measures the nonlocality of bipartite quantum operations. From this measure, we derive an upper bound that shows the limitation of entanglement in reducing communication costs. 4. The maximum tensor norm of bipartite superoperators. We define a maximum tensor norm to quantify the nonlocality of bipartite superoperators. We show that a bipartite physically realizable superoperator is bi-local if and only if its maximum tensor norm is 1. Furthermore, the estimation of the maximum tensor norm can also be used to prove quantum lower bounds on communication complexities.
Can quantum communication be more efficient than its classical counterpart? Holevo's theorem rules out the possibility of communicating more than n bits of classical information by the transmission of n quantum bits --- unless the two parties are entangled, in which case twice as many classical bits can be communicated but no more. In apparent contradiction, there are distributed computational tasks for which quantum communication cannot be simulated efficiently by classical means. In extreme cases, the effect of transmitting quantum bits cannot be achieved classically short of transmitting an exponentially larger number of bits. In a similar vein, can entanglement be used to save on classical communication? It is well known that entanglement on its own is useless for the transmission of information. Yet, there are distributed tasks that cannot be accomplished at all in a classical world when communication is not allowed, but that become possible if the non-communicating parties share prior entanglement. This leads to the question of how expensive it is, in terms of classical communication, to provide an exact simulation of the spooky power of entanglement.
Quantum computation and information has become a central research area in theoretical computer science. It studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. On one hand, the ability of a quantum system to be in a superposition of states provides a way to encode an exponential amount of information in a quantum state. However, this information is accessible only indirectly via measurements. The goal of this thesis is precisely to investigate the fundamental question of how information is encoded and processed in quantum mechanical systems. (1) We investigate their power relative to classical encodings in the model of one-way communication complexity and show that they can be exponentially more efficient, answering a long standing open question in the area of quantum communication complexity. (2) We show how the theory developed for the study of quantum information can be employed in order to answer questions about classical coding theory and complexity. We resolve a main open question about the efficiency of Locally Decodable Codes by reducing the problem to one about quantum codes and solving the latter using tools from quantum information theory. This is the first example where quantum techniques are essential in resolving a purely classical question. (3) We investigate the power of quantum encodings in the area of cryptography. We study certain cryptographic primitives, such as Private Information Retrieval, Symmetrically-Private Information Retrieval and Coin Flipping.