9.9 Quantum cryptography
The exchange of secret messages in a completely secure manner requires a perfect cypher such as the Vernam cypher10 or one-time pad invented in 1917. Unfortunately, it requires a key equal in size to the plain text message and Shannon’s information theory11 says it cannot be reduced without compromising security. Thus, distributing the key itself, especially for voluminous data, e.g., bank transactions, is a problem since the key must be sent over a secure channel. In practice, less secure methods, such as the RSA public key cryptosystem12 are often used.
In 1984, Charles H. Bennett and Gilles Brassard described the first completely secure quantum key distribution algorithm, now known as the BB84 protocol13. It relies on the Hadamard operator to create random numbers, and the fact that a quantum system collapses when measured. Thus, an eavesdropper intercepting a message will invariably make its presence known as a disturbance in the key distribution channel. Quantum entanglement is not used in the BB84 protocol, yet it is so secure that encrypted messages can be sent publicly.
In the protocol, suppose Alice and Bob want to communicate privately, and Eve wants to eavesdrop. Their available means of communication are an ordinary bidirectional open channel (e.g., a telephone) and a unidirectional quantum channel. Both channels can be intercepted. The quantum channel allows Alice to send individual photons to Bob who can measure their quantum state. Eve may measure the state of these photons and resend them to Bob. To establish the key Alice begins by sending Bob a sequence of encoded photons. For encoding, Alice randomly uses one of the following two bases:
where the arrows indicate the polarized state of the photon used to encode the binary digits 0 and 1. Bob measures the state of the photons he gets by randomly picking either basis. After the qubits have been transmitted and measured, Alice and Bob communicate, over the open channel, the basis they used for coding and decoding of each bit. (This amounts to sending a string of symbols, which are meaningless without the measurements themselves.) On average, 50% of the time their bases will match. Alice and Bob use those photons as the key for which their bases agree and discard the other photons. So far nothing has been gained by using qubits.
Can Eve steal the key? Suppose Eve measures the state of the photons sent by Alice and resends new photons with the measured state to Bob. However, being unaware of the basis sequence used by Alice, Eve will get her measurement basis wrong, on average, 50% of the time. Thus, when Bob measures a resent photon with the correct basis (Alice’s basis) there will be a 25% probability that he will measure the wrong value. This is because Eve, by measuring the photons en route, would have collapsed them to her measured value. Thus, Eve is bound to introduce a high rate of error that Alice and Bob can detect by communicating a sufficient number of parity bits of their keys over the open channel. So, not only will Eve’s version of the key will be, on average, 25% incorrect, but that someone is snooping will be apparent to Alice and Bob. If so detected, Alice and Bob simply discard the key and send a new one. Only when both are certain that their key is uncompromised will they use it for encryption. Their encrypted messages can now be broadcast if you please.
Later, Bennett14 found a fiberoptic interferometric version of the quantum key distribution method, and then Bennett and Wiesner15 developed a method that uses macroscopic signals instead of single photons thereby solving the problem of stray light and lowering the cost of the device by using signals which are more efficient and less noisy than photon counting detectors at the wavelengths where optical fibers are most transparent. Both methods were patented.
10 The star algorithms of quantum computing
We now come to more complex algorithms, mainly Peter Shor’s highly efficient algorithm for finding the prime factors of an integer, and Lov Grover’s search algorithm which efficiently conducts a search through unstructured search spaces. Both algorithms were breakthroughs, in terms of computational efficiency in comparison to the best known classical algorithms for either problem, and in terms of conceptual ideas. It is all about managing the relative phase factors using unitary operators.
Recall that the basis independent global phase factors do not affect measurement, hence they can be ignored. Only states, which differ by relative phases in some basis, give rise to physically observable differences in measurement. Therefore, the key to algorithm design is manipulating relative phase as we just saw in Sec. 9.8 using the Mach-Zehnder interferometer. Further, algorithms described in this section depend heavily on quantum entanglement. Note further that it is assumed that given a function f(x), it is possible to break down its computation to the application of a set of one-qubit and two-qubit unitary operations. Typically, the sequence of operations is designed to map the state |x, 0〉 to the state |x, f(x)〉 for any input x. The number of qubits required to represent x and f(x) are appropriately chosen before starting the computations.
10.1 Quantum Fourier transform
Fourier transforms map from the time domain to the frequency domain. In other words, they map functions of period r to functions that have non-zero values only at multiples of the frequency 2π/r. The discrete Fourier transform (DFT) operates on N equispaced samples in the interval [0, 2π] for some N and outputs a function whose domain is the integers between 0 and N-1. The DFT of a sampled function of period r is a function concentrated near multiples of N/r. If the period r divides N evenly, the result is a function that has non-zero values only at multiples of N/r. Otherwise, the result will approximate this behavior, and there will be non-zero terms at integers close to multiples of N/r. In the special case when N is a power of 2, the DFT results in a version known as the Fast Fourier transform (FFT).
The discrete Fourier transform takes as input a vector of complex numbers, x0 , x1, …, xN-1 where N is a fixed positive integer, and outputs another vector of complex numbers y0 , y1, …, yN-1 defined by
The quantum Fourier transform (QFT) is exactly the same transform. When written in the Dirac notation on an orthonormal basis |0〉 , …, |N-1〉 , it is defined to be a linear operator with the following action on the basis states16,
Equivalently, the action on an arbitrary state may be written as
where the amplitudes yk are the discrete Fourier transform of the amplitudes xj, and k and j both range over the binary representations for the integers between 0 and N-1. We see that it corresponds to a vector notation for the Fourier transform (first equation of this subsection) for the case N = 2n. If the state is measured after the Fourier transform is performed, the probability that the result will be |k〉 is |yk|2. Note that the QFT does not output a function the way the Uf transformation does, i.e, no output appears in an extra register. It can be shown that QFT is unitary.
The best classical algorithms for computing the discrete Fourier transform of 2n elements such as the Fast Fourier Transform (FFT), take roughly N log(N) = n2n steps to Fourier transform N = 2n numbers. On a quantum computer, it takes about log2(N) = n2 steps, an exponential reduction! Of course, we need to deal with the fact that the results of such parallel calculations are not readily accessible.
If we take N = 2n, where n is some integer17, and |0〉, …, |2n – 1〉 as the computational basis for an n-qubit quantum computer, it is convenient to write the state |j〉 using the binary representation j = j1 j2 … jn as a shorthand for j = j12n-1 + j22n-2 + … + jn20 and likewise the notation 0.j1 j2 … jm as a shorthand for the binary fraction j1/2 + j2/22 + … + jm/2m. Then
Thus, we have
The above product representation shows the state is unentangled and may even be viewed as an alternative definition of the quantum Fourier transform. It is particularly useful when visualizing the unitary transformations needed to form them. For example, it is obvious that unitary gates of the form
are expected to play a role.
Let us see what sequence of unitary gates allows the QFT to be calculated. Take the state | j1 … jn〉 as input. An application of the Hadamard gate to the first qubit produces the state
since e2πi0j1= -1 when j1=1, and +1 otherwise. Now an application of the controlled-R2 gate (this is a conditional rotation) produces the state
By continuing with the controlled-R3, R4 through Rn gates, we successively add an extra bit to the phase of the coefficient of the first |1〉. In the end the resulting state is
Next, we perform a similar procedure on the second qubit, namely, the application of a Hadamard gate followed by controlled-R2 through Rn-1 gates, to obtain
By continuing in this fashion for each successive qubit, we get the final state
Finally, the swap operation (see Section 9.4) is used to reverse the order of the qubits to provide the final result
On a quantum computer the Fourier transform can be done using O(n2) gates18. This spectacular reduction in computational steps is not feasible on a classical computer even for rather small values of n. The importance of QFT is that many quantum algorithms seem to follow the generic sequence: a Fourier transform, followed by a f-controlled-U, followed by another Fourier transform, or has this sequence as an important component.
10 Developed by Gilbert Vernam of AT&T. This is the only known totally secure cipher.
11 See, e.g., Goldreich (2004). See also: Black, Kuhn & Williams (2002), Sec. 5.
12 Rivest, Shamir & Adleman (1978). Rivest, Shamir, and Adleman received the Turing award for 2002 for their contributions to public key cryptography. http://www.acm.org/announcements/turing_2002.html. See also: Allenby & Redfern (1989), pp. 279-284.
13 Bennett & Brassard (1984). The conference was held at Bangalore, India, December 1984. The first quantum cryptographic ideas were proposed by Stephen Wiesner in the late 1960s, but unfortunately were not accepted for publication! Bennett and Brassard built upon Wiesner’s work. A simple proof of the security of the BB84 protocol was provided by Shor and Preskill in Shor & Preskill (2000).
14 Bennett (1994). See also: Bennett (1992). It describes a fiberoptic interferometric version of quantum key distribution. See also: Bennett & Brassard (1989).
15 Bennett & Wiesner (1996).
16 The quantum version was worked out by Coppersmith (1994) and Deutsch (1994) independently. See also: Ekert and Josza (1996) and Barenko (1996).
17 To keep the discussion simple, we shall not consider the case when N ≠2n. However, we do remark that the larger the power of 2 used as a base for the transform, the better is the approximation.
18 These are a Hadamard gate and n-1 conditional rotations on the first qubit, followed by a Hadamard gate and n-2
conditional rotations on the second qubit, and so on. In all there will be n+(n-1)+ … +1 = n(n+1)/2 gates. In addition, there are at most n/2 swaps to be done where each swap can be accomplished using three controlled-NOT gates.