MSRI Streaming Video Series
Ashwin Nayak - Holevo's theorem and its implications for quantum communication and computation
The nature of the information content of n quantum bits is quite paradoxical---eventhough 2^n - 1 complex numbers are necessary to specify the state of these n qubits, they cannot be used to encode more than n classical bits of information. This is a consequence of Holevo's theorem, a deep result from quantum information theory. Holevo's theorem thus forms the basis of several results showing the limitations of communicating with quantum bits. We give a more transparent explanation of the above "paradox." Our result in fact enables us to get tighter bounds on the number of quantum bits used in the encoding in terms of the probability of correct decoding. Now consider a scenario where the recipient of the encoding is interested in only _one_, a priori unknown bit of the original n. The situation here is subtly different from that in Holevo's theorem, since the measurement the recipient makes to extract one bit could potentially destroy some or all of the remaining encoded information. Indeed, this allows us to encode, for example, two bits into one qubit; such compression is not possible classically. Using such dense quantum codes, we could succinctly encode an entire telephone directory such that any single number could be extracted from it via a suitable measurement. However, using simple entropy arguments based on Holevo's theorem, we show that these codes cannot be very succinct---they require at least a _linear_ number of quantum bits. Finally, we show that the same technique can be used to prove limitations on the computing power of a finite number of quantum bits (i.e., of quantum finite automata). We show that checking if a number is a small even requires quantum automata that are exponentially larger than the corresponding deterministic automata. This is in sharp contrast to a result of Ambainis and Freivalds that quantum automata can be exponentially smaller than classical ones for certain other problems.