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 these topics will be completely explained in this introductory material.

Quantum Computing

A quantum computer would be a computer that take advantage of quantum mechanical principles according to which physical systems behave. We often think of quantum mechanics as being the set of mechanical laws or principles that very small particles obey. While this is not entirely true, it is a reasonable way of explaining things to the layman. 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 are what we are talking about when we talk about quantum systems. We must have quantum mechanical evolution, which cannot be reasonbly approximated with classical mechanics, and use it in a particular way to really obtain a quantum computation or to really do quantum information processing.

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 we must pay careful attention to in order to achieve 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 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. Also, it should noted that throughout these notes, these 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.

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 second 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, its 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. I started learning about these things in 2000, and I would attribute most of what I know about the subject to Daniel Lidar, whether it be direct or indirect. He was one of the first people to realize the importance of attacking the problem whole-heartedly. People recognized the problem, and Shor, et al. really made remarkable statements with their work on quantum error correcting codes. This work showed that errors could, in principle, be corrected, leading the way for future research since it was now 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 decoherence-free subspaces, (and noiseless subsystems) and dynamical decoupling. However, an all-out attack will include other methods of error prevention. Error prevention methods, as I call all of these along with combinations, are the subject of the last part of this course/book for that reason.

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. (ref.)) 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. The limit to small is quantum mechanics – quantum mechanics starts to become the dominate mechanism by which constituents interact. 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 parallelize computations. However, there are processes which cannot be parallelized. So where do we turn? A quantum computer would help with this.
3. 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 futher in the next section.
5. Quantum information can be used in a variety of ways beyond computing. Such as quantum cryptography, quantum games, and quantum communication of all sorts. (Use Carl’s notes here and cite them (ref.))

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

1.1.3 Specific Uses

There are three advantages of quantum computing devices which are often quoted.

1. Factor large integers efficiently (known as Shor’s algorithm)
2. Find an object in an unsorted database more efficiently than a classical machine (known as Govers algorithm, e.g. phone number lookup)
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.

How does it do this?

Now, the claim is that quantum computers could solve some problems more efficiently than classical ones. 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 treated it for years) but a set of rules governing the behavior 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 speedups and other information processing tasks more efficiently than classical systems?” Most 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. (By efficiently here, let us just say that we mean “as well as a quantum one.”) So what I will discuss is what I would call intuitive arguments for why be believe a quantum computer can accomplish things a classical one cannot. We should not claim this is proof of anything at this point.

The first argument is that when a machine has different rules for operating, we expect it to do different things. The rules by which classical computing machines function are, in some sense, different from the ones governing the behavior of quantum machines. This is quite vague, especially given the earlier comments about how everything really is quantum mechanical. The way I think about it (you’re welcome to argue) is that 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.” If this sounds like a circular argument, primarily involving semantics, you are not so far off. However, my motivation for this is a definition I was given in a vector and tensor analysis class: an object is a tensor if it transforms like a tensor. So I say, an object is classical if it obeys classical equations.

The next argument is that there are states which are uniquely quantum mechanical. These are states which would have been mysterious to Newton, and ideed they were mysterious to Einstein, and furthermore they are still mysterious today! The important point is that they are not states of classical systems, i.e. they are not states which behave classically. They are unique to quantum mechanics and are called entangled states. 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 speedups.

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 used is Qbit, see [11]) 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 D.