Grover’s algorithm verified. In 1997, Isaac L. Chuang (IBM, Almaden), Neil A. Gershenfeld (MIT, Cambridge), and Mark G. Kubinec (Univ. of California, Berkeley) actually built a simple two-qubit NMR quantum computer using liquid chloroform (CHCl3) and successfully ran Grover’s algorithm28. In 2000, Chuang and his team reported the experimental implementation of Grover’s algorithm on a three-qubit NMR quantum computer comprising molecules of 13C-labeled CHFBr2, in which the three weakly coupled spin-1/2 nuclei behave as the bits and are initialized, manipulated, and read out using magnetic resonance techniques29.
Computational complexity of Grover’s algorithm. It is well known that classical methods for this search problem require n/2 searches on average to find a solution. Grover’s algorithm requires O√(n) steps. Not only that, Grover’s algorithm is also the fastest even among all possible quantum algorithms for this problem30. Note that the task remains computationally hard, that is, it is not transferred to a new complexity class, but it is remarkable that such a seemingly hopeless task can be speeded up at all. Any problem for which finding solutions is hard, but testing a candidate solution is easy, can as a last resort be solved by an exhaustive search. In such cases, Grover’s algorithm may prove very useful.
Remarks on Grover’s algorithm. There are variations of Grover’s algorithm, which can find the largest or smallest value in a list, or the modal value31, and so on. So, it is quite a versatile searching tool. However, in practice, searching a physical database is unlikely to become a major application of Grover’s algorithm for non-algorithmic reasons, at least so long as classical memory remains cheaper than quantum memory. For since the operation of transferring a database from classical to quantum memory (bits to qubits) would itself require O(n) steps, Grover’s algorithm would improve search times by at best a constant factor, which could also be achieved by classical parallel processing. Grover’s algorithm becomes really useful when searching through lists that are not stored in memory but are themselves generated on the fly by a computer program.
10.5 Dense coding
Bennett and Wiesner32 found a method that uses an entangled pair of qubits to encode and transmit two classical bits worth of information. Since entangled pairs can be distributed ahead of time, only one qubit needs to be physically transmitted from sender to receiver to communicate two bits of information. Hence the name dense coding.
If Alice and Bob wish to communicate in this manner, then each is sent one particle from an entangled pair of particles in the state33
Let Alice get the first particle and Bob the second. The distribution of the entangled particles between the two establishes a quantum communication channel between them. Note that there are four mutually orthogonal states |00〉 + |11〉, |00〉- |11〉, |01〉 + |10〉, |01〉 -|10〉, which form the Bell basis. So, when, Alice receives two classical bits, encoding the numbers 0 through 3, she performs one of the following transformations on her qubit depending on the encoded number:
29 Vandersypen, et al (2000).
30 Bennett, et al (1997).
31 Modal value: the most frequently occurring value.
32 See Bennett & Wiesner (1992). See also: Rieffel & Polak (2000).
33 See, e.g., Rieffel & Polak (2000).