In my previous post I presented a few ideas from quantum mechanics. The next question to address is “how does this relate to computing?“. Let’s start by familiarizing ourselves with classical computing. A classical computer is just a normal, everyday style computer, like the one you’re looking at right now. Anyone who’s done any computer science or electronics will know that a computer employs binary logic, i.e. a language consisting of ‘0’ and ‘1’, and is constructed from gates. A gate is the most fundamental building block in a classical computer and performs very simple logical operations. For example, there is the so called AND gate, which has two binary inputs and one binary output. The output of the gate is ‘1’ only if both inputs are ‘1’, otherwise the output is ‘0’. Similarly, there is the OR gate, which outputs a ‘1’ if either or both inputs are a ‘1’. There is also a single bit gate, called the NOT gate, which simply inverts whatever the input state was. In fact, these three gates form a so called universal set of gates for classical computing, which means that any logical operation can be implemented using them. The PC on your desk is constructed from nothing other than a massive number of elementary gates like these, which jointly perform the much more complicated logical operations your computer is capable of.

So, that’s classical computers in a nutshell. What about quantum computers? Much in the same way that a classical computer uses bits, a quantum computer employs so called qubits, or quantum bits. If you read my last post you’ll recall that in quantum mechanics, superpositions of different states are possible. The idea of superpositions applies to qubits as well, which means that, in addition to taking on values of ‘0’ and ‘1’, a qubit can take on superpositions of ‘0’ and ‘1’. In other words, a qubit can simultaneously be in some combination of these two states. If we have multiple qubits we can have superpositions of multiple qubit states. For example, with two qubits, we could have a superpostion of all the states ’00’, ’01’, ’10’ and ’11’. In a classical computer we could only represent any one of these states at a given time.

So what do we do with our wonderful qubits? In quantum computing we have something analogous to the classical gate. You guessed it, the quantum gate. Much like a classical gate, a quantum gate operates on one or more input qubits to produce output qubits. What makes quantum gates so powerful however is that if we input a superposition state we get more than just a binary sequence at the output. Instead we get a superposition state, where each element of the superposition is the action of the gate on the corresponding element of the input superposition. In short, the gate simultaneously operates on all components of a superposition state. This idea is probably best illustrated by example. We’ll consider the so called controlled-NOT (or CNOT) gate. This gate has two input and two output qubits and performs the following logical operation: if the first qubit is ‘1’ the second qubit has its value flipped, otherwise it is left alone. So, if we input the state ’00’ we get an output state of ’00’, and if we input the state ’10’ we get ’11’. Now suppose that we input a superposition of these two states. In this case we get an output state containing a superposition of ’00’ and ’11’. Pretty cool, huh?

I’m sure it won’t take much to convince you that quantum circuits have the potential to be much more powerful than their classical counterparts, since we can input superposition states into a circuit and get an output state which contains a superposition of all the results, all in one go. Unfortunately there are some rather nasty caveats associated with qubits. Most notably, it actually isn’t posibble to directly measure a superpostion state and determine what all the components in the superposition are. So even though we might have some wonderful quantum circuit which gives us a superposition of answers to some problem, we can’t extract what the solutions are. This is clearly pretty nasty and limits the applications for quantum computers. Nonetheless, in some cases there are clever ways around this problem, which I won’t go into here. Rest assured however that despite the aforementioned problem, quantum computers still have the potential to solve problems which could otherwise never be solved on classical computers due to their computational complexity.