Chapter 1 - Introduction

Introduction

In science one tries to tell people, in such a way as to be understood by everyone, something that no one ever knew before. But in poetry, it's the exact opposite.

-Paul Dirac

An Introduction to Quantum Computation

This introductory chapter is a survey of, and introduction to, topics in quantum information processing. All of these topics (and more) will be revisited in later sections. Therefore, it is not necessary, nor expected, that the reader will feel the subjects have been completely explained in this introductory material. Furthermore, if one has some background in quantum computing, this chapter may be skipped.

Quantum Mechanics

So what is quantum mechanics? We should think of it as a set of rules, in some ways similar to Newton’s laws, which describe the way the world works. These are the rules to which we must carefully attend in order to build what we will describe as a quantum computing device. We will return to this topic briefly again later. However, as is done in many places, this question is never quite answered directly. Most often we simply learn the rules and how to use them. The question itself is perhaps a little vague because there are many physical systems that don’t quite fit into an either/or categorization of quantum vs. classical (since, as stated already, classical mechanics is an approximation to quantum mechanics). Also, it should be noted that throughout these notes the terms will be somewhat misused, in the sense that certain systems will be called quantum mechanical or classical, and from now on, with few exceptions, no care will be taken to discuss subtleties.

Quantum Computing and Quantum Information Processing

A quantum computer would be a computer that would take advantage of quantum mechanical evolutions according to which physical systems behave. We often think of quantum mechanics as being the set of mechanical laws or principles that only very small particles obey. While this is not really true, it is a somewhat reasonable way of explaining things to the layman since the world of the "small" is the world where these laws are most often used and were discovered. For our purposes, we should note that everything obeys the laws of quantum mechanics and that Newtonian mechanics are rules that we use to approximate quantum mechanics. However, quantum mechanical control and natural quantum mechanical evolution, which cannot be approximated by Newton's laws, are what we are talking about when we talk about quantum systems. We must have very particular quantum mechanical evolution, which cannot be reasonably approximated with classical mechanics, and use it in a particular way to really perform a quantum computation or to really do quantum information processing.

We have not yet built a quantum computing device. However, there are many reasons to study quantum information processing other than building a fully functional quantum computer. One main reason we haven’t built one is that we have to figure out how. The experiments to perform quantum computation in physical devices take an enormous amount of effort due to noises which corrupt the information. We are going to need to fix the corrupted information, avoid the noises, or do away with them by some other means. A reason to study quantum computing, and quantum information processing more generally, is that there are really many quantum information processing tasks, or tasks which can be thought of in this way, which concern quantum control. Precise control of a quantum system is important for a variety of reasons, not the least of which is that our world is quantum mechanical! When we get right down to the very basic elements of the universe, they behave quantum mechanically. If there is one thing that the study of quantum information processing has already taught us, it's that we need to pay attention to quantum mechanics because it can be very useful to be able to manipulate quantum systems and take advantage of uniquely quantum properties. Quantum technologies are going to be extremely important in the future, even if we never built a quantum computer. (Oh, but we will!) As Feynman said, “There is plenty of room at the bottom.” We have a lot to discover about the world of the small.

Since noise has been, and is still, such a problem for quantum information, we need to deal with it. People quickly recognized this problem, and Peter Shor, and others, really made remarkable statements with their work on quantum error correcting codes. Their work showed that errors could, in principle, be corrected, leading the way for future research since it was then plausible that a quantum computer could be built – there are no fundamental obstacles. However, quantum error correcting codes are, in some sense, a software solution to a hardware problem. More physical treatments include codes which avoid errors, and control methods which are designed to average noises away. However, an all-out attack will include several different methods of error prevention used together. Error prevention methods are the subject of the last part of this course/book.

Motivation

Why do we want to build a quantum computing device?

1. To make computers faster and more compact, we have been making them smaller (This has obeyed Moore’s law, see, Moore's Law article [16]). However, there is a limit to how much smaller we can make them and still have them function as they do now. This is due to quantum mechanics. In other words, the limit to small scale computational technology is governed by quantum mechanics, since, at a certain scale, the current computational systems will not be able to be approximated by Newtonian mechanics. So, to make things smaller, we need to use quantum mechanics! More than this though, the fact that Moore’s law cannot continue indefinitely means that we will need to look elsewhere for advances in computing power. One way to increase computing power is to use parallel computations. However, there are processes which cannot be parallel. So where do we turn? A quantum computer would help with this.
2. We now know of several different quantum algorithms which are faster than any known classical algorithm for performing the same task. Some are actually provably faster. These are listed and discussed further in the next section.
3. Quantum information can be used in a variety of ways beyond computing. Such as quantum cryptography, quantum games, and quantum communication of all sorts.

An important point to take away from this section is that information is stored and manipulated by physical devices. The way in which they behave is important for the tasks that are to be performed.

Specific Uses

There are at least three advantages of quantum computing devices which are often quoted:

1. Factor large integers more efficiently than a classical machine (known as Shor’s algorithm).
2. Find an object in an unsorted database more efficiently than a classical machine (known as Govers algorithm).
3. Simulate quantum mechanical systems more efficiently than any classical system (due to Feynman and others).

COMMENTS

Shor’s algorithm would render RSA encryption useless. It is more efficient than any known classical algorithm. (There is a quantum answer to this problem however-quantum cryptography through QKD.)

Gover’s algorithm is better than any classical algorithm – phone book example: classical algorithm grows as $N/2\,\!$ and Grover’s grows as ${\sqrt {N}}\,\!$.

Simulating quantum mechanical systems is quite difficult classically. For physical scientists this could be the most important application of quantum computers. This could enable the simulation of nuclear systems, solid-state devices, biological molecules and molecular interactions, etc. much more efficiently than classical simulation. This would enable calculations which are practically impossible now.

How do quantum computers provide an advantage?

The claim is that quantum computers could solve some problems more efficiently than any classical one. So viewing our information systems as quantum systems, we may note that quantum mechanics is more than a description of the physical world (which is how physicists have treated it for years) and is instead a set of rules governing the behaviour of information when stored and manipulated quantum mechanically.

So the natural question is, “How does it do this?” We may also ask, “Where is the advantage?” In other words, “What exactly about quantum mechanics enables us to achieve speed-ups and other information processing tasks more efficiently than classical systems?” Many people, as of the time of this writing, would likely say they don’t know. For example, it is not known if there is a classical algorithm which could factor efficiently. Or perhaps they would say "entanglement" is responsible for the apparent speedups. But this is a subject yet to be discussed. (By efficiently here, let us just say that we mean “fewer resources,” and be more specific later.) One can present an intuitive plausible argument for why we believe a quantum computer can accomplish things a classical one cannot. However, there is no claim of a proof of anything at this point.

The argument concerns the fact that when a given machine has a different set of rules for operating, we expect it to be able to do different things. The rules by which classical computing machines function are, in some real sense, different from the ones governing the behaviour of quantum machines. This is quite vague, especially given the earlier comments about how everything really is quantum mechanical. One may think about it (but someone is sure to argue) as a “classical object” transforms according to a “classical equation of motion” and the result is determined by its initial state, which is “classical.” A quantum mechanical state transforms according to a “quantum equation of motion” and the result of the evolution is determined by some initial conditions, which describe a “quantum system.” Perhaps this sounds like a circular argument, primarily involving semantics. However, the motivation for this as a definition comes from vector and tensor analysis: an object is a tensor if it transforms like a tensor. So we might say, an object is classical if it obeys classical equations. In practice, this is often the way things are done. If the physical system can be well-approximated using classical mechanics, we call it classical.

One can further argue that there are states which are uniquely quantum mechanical. These are states which would have been mysterious to Newton, and indeed they were mysterious to Einstein. Furthermore, they are still mysterious today! The important point is that there is no known classical analogue for some quantum states and one can effectively argue that there can be no classical analogue. They are unique to quantum mechanics. Some of these states are called entangled states. However, there are things one can do using quantum systems using unentangled states that we have no idea how to do using classical systems.

So the answer to the question, "How do quantum computers provide an advantage?" is that we don't really know.

Let us first discuss bits and qubits. We will then discuss quantum states of many particles which correspond to entangled states. Finally, we will revisit this notion of intuition behind the quantum mechanical speed-ups.

Bits and Qubits: An Introduction

A classical bit is represented by two different states of a classical system. In classical computers it is represented by two different values of an electrical potential difference. The two different states of the system are represented by 0 and 1.

A quantum bit or qubit (better, but less often used is Qbit, see N. David Mermin's book [1]) is represented by two states of a quantum mechanical system. The two different states are represented by $\left\vert {0}\right\rangle$ and $\left\vert {1}\right\rangle$. This notation is common and is explained in some detail in Appendix C.2.2, Complex Vectors.

Figure 1.1: This is a double well with a ball in one of the two wells.

Let us discuss a way in which to think about the differences between classical and quantum systems. We will consider two wells, or valleys, with a hill in between as in Fig. 1.1. First we will consider a classical system and we will suppose there are no frictional forces. If we start the ball rolling where it is in the figure, then it will roll back and forth in Well 0. (Well 0, or “Well zero” is our name for the well on the left-hand side.) It will never leave Well 0 if we leave it alone. If we wanted it to go into Well 1 (the well on the right-hand side) we would need to nudge it or push it a little to get it over the hill. Or we could just pick it up and move it from one well to the other.

Now suppose the system is quantum mechanical. In this case, if we set up the system so that the particle initially has some kinetic energy (imagine a moving “quantum ball”), and let it go, there is some probability, after some amount of time, that the particle will be found in Well 1. This is true when the energy of the ball was not great enough to travel over the hill in the classical analogy. The probability of it being found in the other well depends on several things; the initial energy of the particle, the width of the hill, and the height of the hill (equivalently the depth(s) of the wells, which could be different). However, it won’t happen with a classical bit! So this is a difference between the classical and quantum mechanics. In quantum mechanics, the particle is in some sense in both wells at the same time. This has to do with the “wave” nature of quantum mechanics. We then say that the particle is in a superposition of Well 0 and Well 1 at the same time. Mathematically, we describe these different physical “states” or conditions of the system in the following way.

	${\begin{aligned}{\mbox{Particle is in Well }}0&=\left\vert {0}\right\rangle ,\\{\mbox{Particle is in Well }}1&=\left\vert {1}\right\rangle \end{aligned}}$	(1.1)

In other words, the state of the system is “the particle is in Well 0” is written mathematically as $\left\vert {0}\right\rangle$, and simiarly for $\left\vert {1}\right\rangle \,\!$. If the particle is in a superposition of the two, which will mean some probability for finding the particle in each well, we would write this as

	$\left\vert {\psi }\right\rangle =\alpha \left\vert {0}\right\rangle +\beta \left\vert {1}\right\rangle \,\!$	(1.2)

where $\alpha \,\!$ and $\beta \,\!$ are complex numbers (see Appendix B) and the probability of the particle being found in Well 0 is $|\alpha |^{2}\,\!$ and the probability of it being found in Well 1 is $|\beta |^{2}\,\!$.

Now, some (physicists no less) have asked how to make a deterministic transformation in a quantum system. After all, this seems to be probabilistic. The way to do that is the following. We make the hill very wide and tall and we put the particle right down in the bottom of one well and give it as little initial energy as possible. Then if we want it moved to the other well, we pick it up and move it.

If we measure the system, i.e. look to see if it is Well 0 or Well 1, we will “project it into one state or the other.” In other words, suppose the system is in the state $\left|\psi \right\rangle \,\!$ above. If we look to see where the particle is and find it in Well 1, then the probability is clearly zero that it is in the other well. This is called the projection postulate in quantum mechanics and we will see how to represent this mathematically later.

Throughout the notes, when trying to think about a physical qubit, this simple picture is often helpful. Therefore, we will refer back to it from time to time.

Obstacles to Building a Reliable Quantum Computer

Noise is the greatest obstacle to building a quantum computer. This was also the case with early electronic classical computing devices. In this case there is an intuitive explanation. In a quantum computation, a quantum system becomes entangled. Without going into detail, let us just say highly correlated is synonymous with entangled. (Entangled states are discussed in Chapter 4.) Affecting one part of the system can affect another since two parts are highly correlated. Entanglement is believed by some to be responsible for the power of some quantum information processing tasks and there is evidence for this. However, the fact that these entangled systems are being used during the computation means that if a noise affects one part of the system, then other parts of the system are also affected. In this sense, quantum systems are very delicate and must be handled with care.

For our purposes, we will need to discuss open-system evolution and closed-system evolution. A closed system is one which does not have any interaction with external objects. We may also refer to such a system as isolated. For example, one knows that if a jar has a very good lid on it, no liquid can leak out, or into, the jar. So if we put a certain amount of liquid in it now, we can expect it will all be there later. This is a closed system and the liquid is isolated from masses external to the jar. In other words, no other mass can get in or out.

A better example is what we call thermally isolated or a thermally closed system, meaning no heat energy is exchanged with any other system. An open system is one which can interact with its environment in some way. In these examples, a lid that is not sealed can allow liquid vapor to escape and one that is not thermally isolated, or thermally closed can heat up or cool down.

For the quantum information processing tasks we have in mind, we will consider quantum information which is isolated form its environment and what we usually mean is that the quantum system is isolated and cannot be affected by an outside source. It is important to note that isolated, or closed systems, are ideal. While they may often be good approximations to a system, they are basically never really completely isolated or closed. One may consider larger and larger systems to try to obtain a closed system, but this is most often impractical, although it can be useful for modeling. The fact that systems are never completely closed means that errors will creep into our quantum information processing, and we must find a way in which to deal with these errors in order to build reliable quantum information processing devices.

Further Reading

N. David Mermin's book [1] is a recent and excellent introductory text. Nielsen and Chuang's book [2] is also very good and has become somewhat of a standard reference. John Preskill's notes [5] are free to read and were part of the motivation for writing this book. They are quite thorough and even include exercises on his course page. One may also want to consult Quantiki's (http://www.quantiki.org/) excellent encyclopedia of quantum information http://www.quantiki.org/wiki/Main_Page. There is an article concerning introductory material, entitled Basic Concepts in Quantum Computation, and also tutorials on various topics.

Footnotes

Continue to Chapter 2 - Qubits and Collections of Qubits