Introduction to Quantum Computers

The following sections are included:

• Preface

• Contents

At present there are two basic directions on the intersection of modern physics, computer science, and material science. The first is the traditional approach, struggling to squeeze more devices on a computer chip. This direction is a central focus of nanotechnology – a modern science which uses a nanometer scale (10^-9 m) to measure the size of electronic devices. Since the late 1980s, researchers around the globe have tried to create single-electron devices to replace the conventional MOSFETs (metal-oxide-semiconductor-field-effect-transistor). These devices operate by moving a single electron in and out of a conducting region. Single-electron devices may serve as transistors, memory cells, or building blocks for logic gates [1]-[7]. The single-electron transistor has evolved so that it is now possible, at room temperature, by applying a voltage to the operating electrode (gate), to transfer a single electron from a reservoir into a semiconductor island (so-called "quantum dot") surrounded by non-conducting material. Once an electron is in the dot, it blocks the transfer of other electrons due to the strong Coulomb repulsion (Coulomb blockade effect) [5, 6]. The current through a transistor depends on the number of electrons stored in the dot, allowing one to "write" and to "erase" the information. Another promising idea explores the use of molecules as naturally occurring nanometer-scale structures to design molecular devices [5],[8]-[11]. Devices in these classes take advantage of the quantum physics that dominates the nano-meter scale. All these devices are described by conventional current-voltage characteristics and are intended for traditional digital computers that operate using two values of a bit, "0" and "1"…

The simplest "theoretical" digital computer is the Turing machine [44, 45]. Here the word "digital" indicates that the computer operates only with definite numbers (and does not use any quantum mechanical superposition of states). This machine was suggested by the British mathematician, A.M. Turing. The Turing machine has three parts, a tape divided into the squares, a scanner, and a dial, as in Fig. 2.1. This machine can write a symbol X or 1 in a blank square, and erase them. Any positive integer is written as a sequence of 1's. For example, the number 5 corresponds to the sequence 11111. The symbol X indicates where a number begins or ends. For example, Fig. 2.1 shows two numbers 1 which are "prepared" for addition. The program for addition is presented in Tbl. 2.1. The symbol D is the command to "write the digit 1" in the corresponding square on the tape; X means "write X"; E means "erase"; R means "move the tape one square to the right"; L means "move tape one square to the left". The numbers 1 to 6 after the letter indicate the command to "change the dial setting to this number". The question mark represents a "mistake"; an exclamation mark means "job is completed"…

Most "practical" computers make use of the binary system. In this system, any integer N is represented in the form,

where a_n takes the values, 0 or 1. For example, 59 = (111011), is a notation for, …

In a "practical" digital computer information is coded as a string of bits. In "quantum" computers, the elements that carry the information are the quantum states. For example, one can use two quantum states of an atom – the ground state and the excited state. The quantum system can be populated either in the ground state |0〉, or in the excited state |1〉. One might think that a quantum computer provides only an opportunity for greatly increasing of the density of bits. The reality, however, is much more powerful. A quantum system can be populated not only in the ground state or the excited state |0〉 or |1〉, but in any linear combination (or superposition) of these two states. That is why instead of the term "bit", the new term "qubit" (quantum bit) was introduced. The main advantage of quantum computation is that it allows one to make use of the technique of quantum parallelism, which can produce quantum computations that are even more powerful than massively parallel classical ones…

The quantum algorithm described above includes the use of the discrete Fourier transform (4.4). The question is how to describe this transformation in terms of quantum-mechanical operators? The efficient algorithm for Fourier transform based on application of quantum-mechanical operators was suggested by Coppersmith and Deutsch (see review [39]). Assume we have L qubits in the register X, which can hold any number x, from 0 to 2^L - 1. Any number x (in decimal notation) can be expressed as the state,

where …

The quantum algorithm for finding the period of a periodic function was used by Shor [19] to factorized an integer. We shall describe this algorithm using as an example, the number, N = 30. First, we select randomly a number y, such that the greatest common divisor of the numbers y and N is equal to 1. (It is known that if y (1 < y < N) is selected randomly, the probability that two numbers have the greatest common divisor of one unit, is greater than 1/log₂ N [39]. Euclid's efficient algorithm for finding the greatest common divisor is described below.) Now we describe Shor's method of factoring the number N. Let us consider the periodic function,

where a (mod b) is the remainder of a/b. For N = 30, let us randomly select y = 11. Then, we have from (6.1), as 11² = 121 = 4 · 30 + 1. Next, …

Any transformation of bits or qubits can be implemented in hardware using a combination of the simplest logic gates. For a digital computer, the simplest logic gate is the single-bit NOT-gate or N-gate (the gate with one input bit). The truth table for initial (input) a_i and final (output) b_f values is given in Tbl. 7.1. This gate changes the value of a bit,

…

We describe here the main ideas of the semiconductor logic gates, following [46]. In conventional computers, transistors are used as the switches. Transistors are made using semiconductors, usually silicon, with a small amount of impurities. If the added impurity introduces a surplus of electrons (n-type semiconductor), we have additional free electrons in the conduction band (an allowed energy region for electrons in which a current can flow). If the added impurity introduces a deficiency of electrons (p-type semiconductor), we get additional "holes" in the valence band which behave like positive charges. If we put n-type and p-type semiconductor slices together, electrons can flow only from the n-type to the p-type semiconductor. So, the system of two slices conducts current only if the negative terminal of the battery is connected to the n-type semiconductor (Fig. 8.1). Silicon is a classical example of semiconductor. It has four valence electrons. Assume, that we add to silicon a small amount of phosphorus which has five valence electrons. In a silicon crystal lattice four of these electrons hold the atom in place in the lattice: each impurity atom bonds four silicon atoms. The fifth electron of phosphorus is free to move. So, we have a surplus of free electrons. This is an n-type semiconductor. If we add boron which has 3 valence electrons it captures an additional electron. This impurity atom bonds to four silicon atoms, but now one has a deficiency of electrons. This is a p-type semiconductor. In a pure silicon, the density of electrons in conduction band, n_e, is equal to the density of holes in the valence band, n_p. Both n_e and n_p depend on the temperature. (The product n_en_p does not change when we add an impurity.)…

A logic gate is called reversible if one can reconstruct the input when one knows the output. For example, the N-gate is reversible. Indeed, if the output a_f = 0, we know that the input a_i = 1, and vice versa (see Tbl. 7.1, where we should put a_f instead of b_f). The AND-gate is obviously irreversible (see Tbl. 7.2, where we should put a_f instead of c_f). Indeed, if the output a_f = 0, we can not say if the pair (a_i, b_i) is equal to (0,0), (0,1), or (1,0). The same is true for OR, XOR, and NOR-gates. Both classical and quantum mechanics in the Hamiltonian formulation describe only reversible processes. So a computer based on quantum-mechanical logic must involve only reversible logic gates. In Tbl. 9.1 we show the truth table for the two-bit CONTROL-NOT (CN) reversible gate. The first bit a is called the control bit. The control bit does not change its value after the action of the CN-gate. The second bit b is called the target bit. The CN-gate changes the value of the target bit if the value of the control bit is equal to one. We can write for the CN-gate,

or …

Unlike the digital logic gates, quantum logic gates generally act on a superposition of digital states. Quantum logic gates can be represented by operators or matrices. Consider the matrix A with matrix elements A_ik. An adjoint matrix A^† is defined as a matrix with the matrix elements,

where "star" means the complex conjugate. For example, for the matrices, the adjoint matrices are, as …

The quantum CONTROL-NOT (CN) logic gate can be described by the following operator,

…

Here we shall consider how to implement the simplest logic gate, the N-gate, using a two level quantum system. There exists a great number of quantum systems which can be treated approximately as having only two-levels. We shall consider one of them – the proton spin, I = 1/2, in a uniform magnetic field which points in the positive z-direction…

Here we discuss how to realize the operator, A_j,

…

Now we discuss how to implement the operator B_jk (13.2). Let us, for example, have two interacting three-level systems (see Fig. 14.1). Assume that the energy of the states of the k-atom depends on the state of j-atom: the lower dashed level of the k-atom in Fig. 14.1 corresponds to the state |1_j〉; the upper "dashed level" corresponds to the state |0_j〉. So, instead of one frequency ω^k (1_k ↔ 2_k), we have two frequencies and (where the subscript corresponds to the state of the neighboring atom, j)…

We can wonder what the connection is between the quantum dynamics described by the Schrödinger equation and the unitary transformations which describe the quantum logic gates. In this chapter, we shall describe their relation. Let us suppose, for simplicity, that the Hamiltonian of the system is time-independent. Then, the Schrödinger equation,

has the solution, where for any operator F it is assumed, …

So far we have considered an isolated ("pure") quantum system. The same approach is valid for an ensemble of "pure" quantum systems, under the assumption of zero temperature. In reality, this assumption means that the temperature is small in comparison with the energy separation between the considered levels,

where k_B is the Boltzmann constant, ω₀ is the frequency of transition between the levels of qubits, |0〉 and |1〉; and T is the temperature. Gershenfeld, Chuang and Lloyd [28, 29], and Cory, Fahmy and Havel [30] pointed out that the quantum logic gates and quantum computation can be realized also at finite temperature, and even for high temperatures, k_BT ≫ ħω₀. This inequality is typical for electron and nuclear spin systems. For example, for a nuclear spin, the typical transition frequency is ω₀/2π ~ 10⁸Hz. So, at room temperature (T ~ 300K) one has: ħω₀/k_BT ~ 10^-5. That is why we consider in this chapter a high temperature description of quantum systems. Then, using this approach, we will discuss in Chapter 26 the implementation of quantum logic gates at room temperature…

Now we consider the physical implementation of quantum computation in a real physical system. The first physical system used for logic gates was the system of cold ions in an ion trap which is very well isolated from the surrounding…

Now we consider how to realize the transformations described in the previous Chapter, by applying the electromagnetic pulses to ions in the ion trap. A qubit consists of the ground state and the long-lived (metastable) excited state of an ion. To realize logic gates, Cirac and Zoller [21] considered two excited degenerate states (states having identical energies) of the n-th ion, |1_n〉 and |2_n〉, which could be driven by laser beams of different polarizations, say σ₊ and σ_- (Fig. 18.1). The state |2_n〉 is used as an auxiliary state…

In this chapter, we consider how to implement in an ion trap both A_j and B_jk gates (17.10), which are necessary for the discrete Fourier transform. First, we discuss the A_j operator. If we apply to the j-th ion a π/2-pulse with the phase π/2; we get,

…

A second promising system we consider is the system of nuclear spins which are also well isolated from the surroundings. Let us consider, for example, a solid with the linear chains of atoms (ions) containing nuclear spins. We assume that any interaction between chains is negligible. At the same time, we shall take into consideration the interaction between the nearest neighbors in the chain. Assume that a solid is placed into a uniform magnetic field which is oriented along the z-axis. Then, the one-spin Hamiltonian, without the interaction, can be written in the form (12.3). Following Lloyd [35], we suppose that we have a chain of three types of nuclei, ABCABCABC…. All three types have the same spin I = 1/2, but they have different magnetic moments (different gyromagnetic ratios). Assume that the interaction between the spins of a chain (for example, a dipole-dipole interaction) is small in comparison with the interaction of spins with the external magnetic field. Then we can take into consideration only the zz part of interaction, , (Ising interaction), which commutes with the non-interacting Hamiltonian. Here, J is the effective constant of the Ising interaction. The Hamiltonian of the whole system (without the electromagnetic field) can be written as,

where we sum over all spins in the chain, and …

So far one can not experimentally operate on individual spins such as on an ion in the ion traps. The problem of manipulation of quantum states using a spin system is rather complicated, and was not investigated experimentally so far. We consider in this chapter only the digital states |0〉 and |1〉, without superpositions and entanglements. So, the phase of the states is not important for us…

The difference in frequencies does not provide a 100% selective excitation of a given resonant spin because of non-resonant effects in the radio frequency pulses. This effect can be studied by explicit numerical calculations. Let us consider, as an example, the CN-gate based on a system of two spins [54], I = 1/2, placed in a constant homogeneous magnetic field which is pointed in the positive z-direction. We take into consideration the Ising interaction between two spins and the interaction of each of these spins with an electromagnetic field which rotates in (x, y) plane (see Chapter 12). The Hamiltonian of the system can be written in the form,

where the two spins have different gyromagnetic ratios, γ₁ and γ₂. The spins are interacting with a circularly polarized transverse electromagnetic field of the frequency, ω, (12.20). In this case, the Hamiltonian (22.1) can be rewritten in the form (see (12.22) and (12.23)), where ω_k = γ_k B^Z, Ω_k = γ_kh is the Rabi frequency (h is the dimensional amplitude of the transversal magnetic field). The energy levels of the two-spin system (22.1) are shown in Fig. 22.1, for the case, ω₁ > ω₂. If one applies a π-pulse with the frequency ω = ω₂ - J, it can provide a CN-gate with the first (left) spin as a control qubit, and the second (right) spin as a target qubit – the second spin changes its state only if the first spin is in the state |1〉…

A one-qubit rotation, under the action of a resonant π-pulse, is a commonly used experimental technique. That is why the present efforts of experimental groups are concentrated on the design of the two-qubit quantum logic gates. Recall that the quantum CN-gate, in combination with the one-qubit rotations, is universal for quantum computation, i.e. any logic gate can be constructed from their combinations [20]. The same is true for the CZ-gate and one-qubit rotations, because the CN-gate itself can be obtained as a combination of the CZ-gate and one-qubit rotations (see Chapter 18)…

One of the main challenges for a theory of quantum computers is the problem of error correction. The standard way to correct a computer error uses redundancy. One uses several elements to represent the same bit. To incorporate the error correction procedure into a digital atomic chain computer, Lloyd suggested using the more complicated three-level systems [18]. The atoms (A, B, or C) must possess an additional excited state |2〉 which decays quickly into the ground state…

We shall consider here a quantum two-qubit gate in the simplest system which contains only two spins with the Ising interaction. The energy levels of the system are shown in Fig. 22.1. The Hamiltonian of the system, including the interaction with the electromagnetic field, is given by the expression (22.2)…

This chapter is based on the idea suggested independently in [28, 29] and [30], for quantum computation at room temperature. To explain the idea, let us first consider an ensemble of noninteracting spins, I = 1/2, in an external magnetic field which points in the positive z-direction. In the state of the thermal equilibrium, the system can be described by the density matrix (16.17) which for the typical condition, k_BT ≫ ħω₀ has the form (16.19). The expression (16.19) consists of two terms: The first term, which corresponds to the infinite temperature, is proportional to the unit matrix, ρ_∞ = (1/2)E. This term does not influence the average spin, , which can be measured experimentally for an ensemble of spins. Indeed, for example,

as I^x E = I^x, and Tr{I^x} = 0. The same is true for the operators I^y and I^z…

To explain the dynamics of an ensemble of four-spin molecules, let us write the Hamiltonian of the complex,

taking into consideration the Ising interaction between all spins [64]. To get the Hamiltonian in a system of coordinates which rotates with the frequency of the circular polarized magnetic field, ω, we use the unitary transformation (15.5a), where the lower index, "0", indicates the last spin, D; index "1" refers to the spin C, and so on. Using the method, which was described in Chapter 15, we get the time-independent Hamiltonian in the rotating frame, where, in the second term we suppose i < k, ω_k = γ_k B^z, Ω_k = γ_kh. When the rotating magnetic field is absent (Ω_k = 0, ω = 0), the Hamiltonian (27.2) has only diagonal matrix elements, which determine the energies of the stationary states. To find these energies, we should rewrite the expression for (12.4), in terms of the four-spin basic states, |i₃j₂k₁n₀〉. So, we have, where we assume summation over the indices i₃, j₂, k, and n₀. In the same way, we can write the second term in the Hamiltonian (27.2) in terms of the four-spin basic states, |i₃j₂k₁n₀〉, …

Now we shall discuss how to make the transformation,

where we assume summation over the indices i, k, n, and m; a_iknm are the numbers in the second row of Tbl. 26.1; are the numbers in the third row of Tbl. 26.1. Ignoring the factor, β/16, these numbers represent the diagonal elements of the deviation matrix. To realize this transformation, Gershenfeld and Chuang [29] applied the next sequence (GC-sequence) of the CN-gates to the initial density matrix (26.16), …

Here we present our vision of the current stage of quantum computation. We mentioned in the Introduction that there exist two main directions for design of future computers. One of them is connected with the development of digital computers, and is based on electron conductivity. The other direction—of quantum computation—is connected with development of quantum computers, and is based mainly on the resonant interaction of electromagnetic pulses with nuclear or atomic systems. The output of quantum computation, in a simple variant, is a sequence of data, "there is voltage" (which represents "1"), and "there is no voltage" (which represents "0"). There exist other suggestions for implementations of quantum computation, for example, those using the spin states of coupled single-electron quantum dots [65]. These systems do not use resonance pulses, and could be of significant interest for quantum computation.

The following sections are included:

• Bibliography

• Index