1

An Introduction to Quantum Computing

For Computer Science Undergraduates

Aria Schultz

Abstract

Quantum computing is still in its infancy. The world is still waiting for the first quantum computer to be built. It would be naive to try and speculate as to when hardware for quantum computing will become a reality; however, it would also be naive to forgo exposing oneself to the unique benefits and problems of quantum computing under the assumption that quantum computers are a long ways away.

This paper will strive to provide a cursory overview of the key points of quantum computing and is aimed at the computer science undergraduate. Because of this, many of the concepts will be basic overviews namely the underlying mathematical basis for quantum computing.

Introduction

In order to begin exploring the world of quantum computing it is useful to first compare and contrast it with classical computing. Within the context of this paper, “classical computing” will refer to the standard computing model that has memory composed of a series of bits. These bits (which shall be referred to as Cbits henceforth) have a value of either 0 or 1. The state of a classical computer can be seen as the state of all of the Cbits in the computer's memory. When working with Cbits in a classical computer it is a trivial operation to read the state of the Cbit and such an operation has no effect on the value the Cbit holds.

In contrast, the idea of a state has a very different meaning for a quantum bit (which shall be denoted as Qbit henceforth). Before delving into that, it seems important to dispel a popular misconception that whereas a Cbit holds the state of 0 or 1, a Qbit can hold a state of any number between 0 and 1. This idea is a fundamental misunderstanding of how a Qbit works.

To begin understanding how a Qbit works it is important to start with the key concept that it is impossible to read the state of a Qbit. In order to get any information from a Qbit one must invoke a process known as measuring. The act of measuring a Qbit does not yield the state of the Qbit (as was just pointed out, this is impossible) instead the process of measuring a Qbit causes it to collapse into either the state of 0 or 1. Therefore, it is of utmost importance to understand that although a Qbit is capable of holding very complex information, once one tries to retrieve this information the Qbit will collapse down to a 0 or 1.

QuantumSuperpositon

So what information does a Qbit have in its state? The answer to that is both simple, and complex. The state of a Qbit can be 0 or 1. It can also be 0 AND 1, or 0 AND 1 AND 0, etc. In other words a Qbit can hold multiple states through quantum superpositon. Superpositon is a basic concept of quantum mechanics. The logic of superpositon flies in the face of everything we experience in the macro world. Our brains are sure of the idea that an object can only be in one definite state at any given time. A light switch is either on or off, it cannot be on and off at the same time. This simple rule that we often take for granted fails to characterize how things behave at a quantum level. At that level it is possible, say, for an atom to be rotating clockwise and counter-clockwise at the same time. This is known as quantum superpositon, the concept that at the quantum level an object may not have one simple state, but instead multiple states that all exist concurrently. It is this fundamental idea that gives quantum computing its power.

Manipulating Qbits

In classical computing Cbits are manipulated through the application of logic gates (AND, XOR, etc.). The majority of these logic gates cannot be reversed once they have been applied with the exception of something like NOT which can simply be applied a second time to reverse the operation. When working with Qbits all operations can be reversed with the exception of measuring the Qbits. Since measurement can be put off until calculations are completed this is not a big issue.

The exact mechanic of the Qbits logic gates all being reversible has its explanation in linear algebra. Given that linear algebra is not a required course for computer science undergraduates, and trying to write a summary with enough brevity to allow room for the real meat of this article (the portion on that chiefly pertains to computer science) the underlying mathematical formulas and their notation will have to be replaced with a bit of hand waving[1].

The basic point that should be understood is that a Qbit's state is represented mathematically as any two-dimensional unit vector spanned by the vectors (0) and (1) over the complex numbers . Thus the state of a Qbit can be generalize as

S = α0 (0) + α1(1)

where α0and α1 complex number coefficients. Therefore, the state S associated with a Qbit is the superpositon of the states 0 and 1 with amplitudes α0and α1. The state of a single Cbit can only hold one bit of information (a 0 or 2), but a Qbit is represented by two complex numbers and in order to represent it with an arbitrary amount of precision one requires an arbitrary number of bits to specify the two complex numbers α0 and α1 [1].

In the case of Qbits, the logic gates that are applied are unitary matrices. These matrices are basically rotations that act on a Qbit, and as such they can all be undone easily by applying the opposite rotation. The benefits of this will be expanded on later, when I discuss the computational process of a quantum computer.

Given that Qbits have far more complex states it would seem as though a quantum computer has vastly superior computational power when compared to a classical computer, but there is a major catch. As previously stateda Qbit may contain a plethora of information there is no way to “read” that information from the Qbit as one would with a Cbit in classical computing. You cannot get the amplitudesα0 and α1instead your perform something called “measuring” to obtain a value from a Qbit. This measurement will collapse the Qbit to either a 0 or 1.

Applying a measurement to a Qbit does not determine the result held in a Qbit. Instead, the superpositon of states that a Qbit is in determines the probability that it will collapse into a particular state. The probability of a particular result is the square of the magnitude of the amplitude. In the example above of a single Qbit with amplitudes α0and α1the probability that measuring this Qbit will yield a 0 is | α0|

One should avoid thinking of measuring a Qbit as the same thing as measuring someone's weight. This is not the case. It would be more correct to compare it with measuring a person’s IQ. Having someone take an IQ test will not yield any preexisting numerical property of a person, just what happens when you give someone an IQ test [1].

Given these conditions it may be hard to imagine how anything of significance can be computed using a Qbit. The trick is to use the unitary transformations to most amplitudes at or near zero, and have useful information carried in any amplitude that has a decent chance of yielding the correct result. As such, quantum computers are most useful at finding solutions that can then be easily checked using some other method to verify their accuracy. Additionally, note that the chance of getting an incorrect result often has a low probability.

The Computational Process in a Quantum Computer

Having described how a Qbit stores information and how information is manipulated and retrieved from a Qbit it is time to talk about how one computes with a Qbit. Considering what has been said so far about the Qbit, one may be wondering how a quantum computer could offer any advantage over a classical one. In truth, if this was all a quantum computer had to offer it would not be worth the effort of actually trying to build one, but the true beauty of a quantum computer comes from the interesting computations that can be performed with a Qbit that are not possible on classical computers. By taking advantage of quantum superpositon a programmer can sacrifice gaining one piece of information for another. This trade-off is typical of quantum computing, and leads to its most powerful features.

The basis of this kind of trade-off is to set the input of a function to be the superpositon of all possible inputs the function can take, and then execute the function. Thus, the output of the function will be all the calculations of the function. With a 100 bit input register, this would result in 1030 evaluations for the price of one. Of course, as has been reiterated throughout this paper, there is no way to extract that information from the Qbits. All that one can do is measure the output of the function, which will cause the Qbits complex state to collapse down do a simple 0 or 1. Thus, one can only learn a random value of the function this way, but there are some interesting implications to this sort of parallelism if oneis willing to give up the actual results of a computation.

Deutsch's Problem

The first example of this quantum trade-off, and the example that got the whole field of quantum computing started, is the Deutsch's Problem. The problem goes like this. Say there is a function f that takes a single Qbit of input and returns a single Qbit as output. The function f will perform some action on the input in order to produce an output. On a classical computer if one wanted to know the result of f(0) they would have to run the function and check the output (which would be a 0 or 1), and similarly one would call f(1) to obtain that result.

Things work the same on a quantum computer as well. Calling f(0) will return the computed value of f(0). Now suppose all one wanted to know was whether f(0) was equal to f(1). On a classical computer there would be no choice but to call f twice, passing 0 and 1, then compare the results. A quantum computer, on the other hand, can make the determination with only one call to f!

Of course, there is the quantum trade-off to keep in mind. In this case, what is lost is the actual values of f(0) and f(1), but that information is irrelevant to answering the question of whether or not the values are equal. In this way a quantum computer can trade one piece of information for another.

The way one accomplishes this feat is by using superpositon to set the input register to be 0 and 1. Now if f is executed on the input that is a superpositon of both the inputs we wish to check an interesting thing happens. The output register will just have a copy of the input register from before f was called, and the input register will have either a 0 or a 1 depending on whether f(0) == f(1) [4].

Simon's Problem

The next problem that we are going to examine is called Simon's problem. It is an extension of the trick used in Deutsch's problem with the added benefit of being able to clearly see the speed up that a quantum computer can offer over a classical machine.

The Problem

In Simon's problem we have a function f(x) that takes an integer x as its input. The function then computes the bitwise modulo-2 sum[2] of x and sum unknown integer a. The goal is to find the value of a or in other words find the period of f.

In order to solve this problem on a classical computer all that can really be done is start putting in values for x and keep going until you find a value for f(xi) that is equal to some previous value f(xj) obtained from the function. Then you would know that a equals the bitwise modulo-2 addition of xi and xj. The number of times you must call this method in order to have an appreciable chance of finding the value of a grows exponentially with the number of bits in a. If a had 100 bits a classical computer would have to call f about 1015 times. At ten million calls per second, it would take about three years [2].

The Solution

A quantum computer can determine the value of a with high probability (less than one in a million chance of failing) by calling f about 120 times given an a with 100 bits. This can be accomplished by the trick we used in Deutsch's problem and set all the bits of the input x to be a superpositon of all possible inputs[3]. Now when the function f is run and we measure the input register we will learn (with equal probability) a random number y for which the modulo-2 sum of a and y is 0. This value y gives us a subset of the bits in a hose modulo-2 sum is 0. Therefore, if n is the number of bits in a we can lean the value of a with high probability by invoking the function n + 20 times. This is a clear case where a quantum computer calculates the correct result with a high probability and the result can be confirmed by a classical computer in far less time than a classical computer could ever calculate the result.

Implications of Quantum Computing Techniques

These two problems may seem a bit artificial; however, they are intentionally simple in order to give you an idea of the types of things one can do on a quantum computer, and how this can lead to massive performance increases. The trick of using quantum superpositon to perform calculations in parallel is at the heart of what gives quantum computing its allure. Always keep in mind though, that the results of a parallel computation cannot be obtained, but we can set things up so that by giving up learning the results of any of the calculations we can learn other information about a function.

The concept of quantum parallelism can be used in some truly amazing ways from Groover's algorithm, a search algorithm that runs in (π/4) √N time, to an algorithm that utterly defeats the one of the most widely used encryption scheme today RSA[4]. This is only a quick overview of the usefulness of quantum computation and how one computes at the quantum level. From here we can begin discussing some of the recent progress that has been made in the hardware side of the field.

Quantum Hardware

During the past several years there have been a number of very important break-throughs in the quest to build the first true quantum computer. These discoveries give a decent picture of what the current issues with building a quantum computer are. They highlight the progress that has been made, and the obstacles that need to be overcome. The also demonstrate the major issues that must be solved in order to build a full scale quantum computer.

Problems

The main issue that one must contend with when they try to build a quantum computer is how to make a Qbit. The majority of problems dealing with quantum hardware involve creating and maintaining a Qbit. There are many different ways a Qbit can be created, and the only real restriction is that you need something that can be in a superpositon of states [3]. Current physical implementations are based on a variety of approaches including superconductors, ions, the magnetic resonance of molecules in a solution, and the list goes on. The basic problem that all these methods run into though is not how to create a Qbit, but how to get that Qbit to maintain its state for sufficiently long enough time to perform calculations.

In order for a Qbit to properly hold its state, it must be completely isolate from the outside world. Any interference will cause the state of the Qbit to decay, and become unusable. IBM has been working on an implementation of Qbits. The IBM group announced earlier this year that they have made a number of break-throughs which have allowed them to keep a Qbit free from any outside interference for a longer period of time allowing the group to run some simple calculations on them.

Another group of researchers at Yale created the first solid-state quantum processor back in 2009. The chip had a 2-Qbit register and the Qbits could only maintain their states for a microsecond which is considerably longer than what previous Qbits were capable of in the past.

I highlight these two groups because I think they illustrate the problem with building a full scale quantum computer quite well. Even though both groups have very different approaches they have the same basic problem: the Qbits are being interfered with by the outside environment which causes them to decay and become useless. As you add more and more Qbits to a machine, the likelihood that any one of those Qbits will decay before your calculation completes increases dramatically.

Controversies

Currently there is a lot of controversy surrounding a company named D-Wave. D-Wave claims that they have built a full scale quantum computer; however, the company has not allowed for any peer review of this so called quantum computer. As a result there is a great deal of debate in the scientific community about whether this machine is truly a quantum computer or not. Though the machine certainly has an interesting story, there is no consensus on whether D-Wave Systems has actually produced a quantum computer or not.

Recently a lead scientist for the aerospace company Lockheed Martin gave the group at D-Wave code from their F-16 fighter jet. The group at Lockheed knew there was a bug in the code, and they wanted to see if D-Wave’s quantum computer could analyze the code and find the bug.

After taking the code from Lockheed D-Wave came back and announced they had found the bug. Lockheed was so impressed by this that they paid $10 million for a quantum computer that is now set up in a Lockheed research lab.