An Interactive Introduction To Quantum Computing Part 2

Quantum Search

This article was originally written in 2014, but has had some minor improvements in December 2017 and January 2018 when I received some useful feedback after the article had unexpectedly been posted on Hacker News in December 2017.

This is Part 2 of a two part series. In Part 1 I explained some of the basics of qubits, including the mysterious notions of phase and quantum interference. Here in Part 2, you will learn how quantum computers may one day be able to solve search problems faster than conventional computers.

Multiple qubits

Important: There is something really important I feel the need to emphasize as we start dealing with multiple qubits.

The blue disks introduced in Part 1 do not correspond to single qubits.

Each blue disk corresponds to a distinct state of the entire quantum system. If you are not sure what I mean by that, then please hang in there, it will hopefully become aparent very soon.

Controlled NOT

The Controlled NOT operator is a very simple but powerful two-qubit operator.

The Controlled NOT operator modifies the value of one qubit (the target qubit) based on the value of another qubit (the control qubit).

Specifically, the Controlled NOT operator flips the value of the target qubit if the control qubit has a value of 1.

For example: Suppose we have two qubits with an initial value of “11”. Let's use the left qubit as the control qubit and the right qubit as the target. Then the result of applying a Controlled NOT will be “10”. As usual, we represent this as “11 → 10”

Continuing with our choice of left qubit as control qubit and right qubit as target, there are four scenarios to consider for the Controlled NOT operator.

Quantum Entanglement

A combination of the Hadamard followed by a Controlled NOT can put two qubits into a state of “quantum entanglement”.

In what follows, we take a two qubit system in the state “00”, apply the Hadamard operation to the left qubit, and then use that left qubit as the control in a Controlled NOT of the right qubit:

Initial State

State:

After applying a Hadamard to the left qubit

When you apply a Hadamard to the left qubit, that qubit goes into a superposition of 0 and 1. The right qubit is not touched and continues to have the value 0. So the pair of qubits goes into a superposition of 00 and 10.

State:

After a Controlled NOT of the right qubit controlled by the left qubit

The Controlled NOT will leave the 00 state unchanged as the control qubit (left qubit) is 0.

When acting on the 10 state, the control qubit is 1, and so the target bit is flipped resulting in 11. So the pair of qubits goes into a superposition of 00 and 11.

State:

Note that, if you were to measure the qubits while they are in this state, you would find that they are either both 0 or both 1. This sort of correlation between qubit values within a superposition is called “quantum entanglement”.

Why quantum entanglement is so special deserves an entire article of its own. For now, I am simply using entanglement to emphasise how quantum superposition can apply to the combined state of a number of qubits.

Arbitrary Logic Functions

In addition to the NOT operator that we have already seen, a quantum computer can implement the standard logic functions of AND and OR. From these, one can compute any function over a fixed number of bits.

The details are surprisingly fascinating and not as straight forward as you might expect. However, for the purposes of this article, I want you to trust me when I say it can be done. This will allow us to move more quickly to the even more fascinating topic of quantum search.

Before we can cover quantum search, there is one more quantum operator I need to introduce.

Controlled Phase Flip

Recall that the term phase, introduced in Part 1, refers to the arrow direction of a state.

The controlled phase flip is a multi qubit operator. It flips the phase of the states where all of the specified qubits have the value of 1.

More useful to us, however, is a generalised form of the controlled phase flip. It will flip the phase of the states where the target qubits have any specified combination of 1's and 0's.

Try it yourself:

Quantum Search

Imagine you are trying to crack an n-bit encryption key by brute force: i.e. by trying every one of the 2n possible values.

This is a classic needle in a haystack search problem.

In other words, it belongs to a class of problems for which there exists an efficient function, called an oracle (or verification) function, that takes a candidate value as input and returns true if the candidate is the correct value. However, the only way to find the correct value is to test the oracle function on practically every possible value.

A conventional computer will need to evaluate the oracle function, on average, 2n-1 times.

By using Grover's algorithm, a quantum computer only needs to evaluate the oracle function less than √(2n) times.

Even if a conventional computer can compute the oracle function in a nanosecond, if the input was 64 bits long, then it would probably take hundreds of years for that conventional computer to find the answer. A quantum computer might possibly take just a few seconds. A conventional computer would have to evaluate the oracle function an average of 263 times, compared to just over four billion times for a quantum computer. It is likely however, at least in the early days of quantum computing, that individual operations on a quantum computer may be vastly slower than on a conventional computer. It may take a while before quantum computers ever get to solve a problem any faster than conventional computers.

For the extremely simple case where the input is only 2 bits, there are four possible answers. A conventional computer may need to test up to three of those possible values. (If it isn't the first three, then you can infer it must be fourth one without testing it.) As you will see below, a quantum computer can find the answer using a single invocation of the oracle function.

Quantum Search over 2 Qubits

First recall that the objective is to find the value of x for which the oracle function is true. For Grover's Search Algorithm to work, it is essential that the oracle function is true for exactly one value of x.

In the conventional descriptions of Grover's Search Algorithm, it is assumed that the oracle function will flip the value of an “output” qubit when the input matches the desired result. It is a lot more convenient if we do away with the output bit, and instead flip the phase when the input matches the desired result.

Here are the steps to Grover's Search Algorithm for the very simple case of two bits.

For example, the problem may be to find factors of 15 that are less than 4. This is obviously trivial for such small values, but the problem of finding factors for very large numbers (e.g. numbers with over 100 digits) is currently a very computationally expensive problem.

  1. Start with the qubits in a superposition of all possible states: 00, 01, 10, and 11 (all with the same phase).
  2. Apply the oracle function once only. Note that, because the system starts in a superposition of all possible states, the oracle function is effectively applied to all possible states, but it will only flip the phase of the state for which we are searching. If you were to perform a measurement now, all the possible outcomes are still equally likely and so we don't seem to have made any progress. However, the next three steps use quantum interference to find the correct answer.
  3. Apply a Hadamard operation to both qubits.
  4. Flip the phase of the 00 state.
  5. Apply a Hadamard operation to both qubits again.
  6. Constructive and destructive quantum interference will ensure that, of the four possible states, a measurement is guaranteed to result in only the desired state.

You can try it yourself below. Your task is to find the value for which the oracle function f is "true". i.e. the state for which f will flip the phase. On a classical computer you would typically end up testing at least half the states before finding the answer. On a quantum computer you can test all the states simultaneously.

Apply the oracle function (to all states):
Only the searched-for state now has a non-zero probability and a measurement can be safely applied.

Don't forget, unlike what happens in the animation, each operation is effectively applied to all the states simultaneously.

Beyond Quantum Search

The two bit search is a bit of a special case where the oracle function only needs to be invoked once. As the number of bits increases, it becomes necessary to invoke the oracle function multiple times. In fact it needs to be invoked ¼π√(2n) times.

While general quantum search techniques may seem quite impressive, even ¼π√(2n) gets very large very quickly.

All you have to do is double the number of bits to wipe out any advantages. For example, over a 128 bit search space, a quantum computer would need to evaluate the oracle function almost as many times as a conventional computer does over a 64 bit search space. Even at one evaluation per nanosecond, it would take hundreds of years to crack a 128 bit encryption key.

However, encryption keys commonly used for securing internet traffic (RSA keys) can be broken using a special purpose quantum algorithm. These encryption schemes rely on the difficulty of factoring very large numbers, something that can be easily done on a quantum computer using Shor's Algorithm.

Shor's Algorithm has a “asymptotic” behaviour of O((log N)3). I won't try to explain the exact meaning of this statement, but it is quite possible that current encryption keys could be broken in sub-second time frames. Also, simply doubling the length of the key would have a barely noticeable effect on the time taken. The limiting factor is likely to be the number of qubits required since you need at least as many qubits as the key length.

D-Wave

You may have heard of D-Wave quantum computers.

These are currently the only commercially available quantum computers. D-Wave are building quantum computers containing 512 qubits, which in theory could be in a super position of 2512 states. Update Jan 2017: D-Wave have now built a 2000 qubit system and have plans for a 4000 qubit system.

Despite having such a large number of qubits, there is little evidence that they have been solving problems any faster than conventional computers.

D-Wave computers are special purpose “quantum annealing” computers. The quantum computers that I have been describing so far are known as “quantum gate” computers. Describing the differences are beyond the scope of this (already long) article.

Before they can start out-performing conventional computers, it is possible that D-Wave simply needs to use more qubits, or perhaps they may need to figure out how to make more effective use of their existing qubits. However, it quite possibly will not be long before we start seeing impressive results.

Some philosophy

Describing quantum computing in terms of superpositions of states that “collapse” to the observed state upon “measurement” is a very conventional approach to explaining the physics behind quantum computing. However, there are some serious deficiencies with this approach.

Probably the most fundamental problem is: What is so special about measurement that it causes quantum superpositions to collapse?

The measuring equipment itself is made of the same stuff as the qubits being measured (protons, neutrons, electrons, and photons).

When measuring a qubit that is in a superposition of two different states, there is nothing in quantum physics that says why the measuring equipment might cause the superposition to collapse to a single state instead of the measuring equipment becoming entangled with the qubit. Instead of the quantum state collapsing, the result could be a superposition of the following two states:

If you consider your conscious awareness to be nothing more than patterns of activity in your brain, and that your brain is governed by the laws of physics, then there is nothing in quantum physics that says why, when you look at the measurement outcome, you yourself do not become entangled with the quantum qubit and the measuring equipment. The result would be a superposition of the following two states:

Think of it as two alternative realities existing. In one reality you see a 0, and in the other you see a 1. Quantum interference is the only ways that these realities interact.

Variations on this interpretation of quantum physics are taken quite seriously by many physicists and physics philosophers, and is commonly referred to as the “Many Worlds” interpretation of quantum physics. Much has been written on the topic, and an internet search will point you to many good (and not so good) articles.

Quantum computing provides a nice way of looking at some of these issues. It may even provide a way of simulating ideas by, for example, representing different states of an observer using qubits.

This article has already covered more topics than I originally planned. However, I feel the need to include a little bit of a mathematical explanation to some of the material. For those that are not interested in the mathematics, feel free to skip to the Useful Links Section at the end.

Some mathematics

In this article I used little blue disks with red arrows to represent the probabilities of a set of bits or qubits being in different states. It is likely that I caused some confusion by quietly using the disks in subtly different ways when describing two quite different types of uncertainty.

When describing ordinary non-quantum bits, the system is in a definite state, but which state that is may be unknown. In this situation, it is most convenient if the arrow lengths are proportional to the probabilities of the respective states so that they can be added head to tail. If there were two scenarios, S1 and S2, both ending in the same state, where S1 has a probability of p1 and S2 has a probability of p2, then the probability of that final state is p1 + p2.

When describing qubits in a superposition of different states, it is no longer simply a case of not knowing which state they are in, the system actually seems to be in multiple states at once. In this situation, it is most convenient if the arrow lengths are proportional to the square roots of the probabilities of the respective states (the disk areas now effectively represent probabilities except for a factor of π). The arrow directions represent their phases. When two scenarios end in the same state, you need to use vector addition to add the arrows.

The arrows represent what physicists call “amplitudes”.

Conventionally, an amplitude is represented using a complex number whose value on the complex number plane coincides with the end of our arrow. If our arrow has a length r and a phase θ, then it is represented as the complex number:

r (cos(θ) + i sin(θ))

If a state had this amplitude, then the probability of that state being the outcome of a measurement is r2.

When we talk of “adding arrows head to tail”, we can simply add the corresponding complex numbers using ordinary complex number arithmetic.

Given that the probabilities of all possible outcomes have to add up to 1, it follows that the sum of the squares of the amplitude magnitudes also have to add up to 1. All quantum operators preserve this property.

If the amplitudes for the 0 and 1 states of a qubit are the (possibly complex) numbers a0 and a1 respectively, then applying a Hadamard results in the amplitudes of 0 and 1 becoming (1/√2)(a0 + a1) and (1/√2)(a0 - a1) respectively.

For the simple case of a qubit being 100% in the 1 state with a phase of 0, applying a Hadamard results in the amplitudes of 0 and 1 being 1/√2 and -1/√2 respectively. Notice that if you square and add these together that you get 1.

That is already more mathematics as I wanted to cover in this article. For more, see some of the useful links listed in the next section.