What are quantum algorithms?

‍

Representing algorithms in a quantum computer

In this article, we’ll introduce you to how we build and represent algorithms in a quantum computer.

Quantum circuits

In the field of quantum computing, we use a simple visual tool called a quantum circuit to illustrate how an algorithm or program is executed. These circuits are a bit different than the circuits you might see in electronics which show connections in space. In quantum circuits, we show connections between qubits in space as well as operations performed in time. If you’ve ever played a musical instrument, you can think about a quantum circuit like a musical score that plays an algorithm as you read along.

The first critical elements are the horizontal rails which each represent individual qubits initialized in a starting state. Multiple qubits are represented by multiple rails. The horizontal axis then represents time. We can then add different quantum logic operations in order to build up a program. As time flows from left to right, the state of the set of qubits changes because of the operations.

Quantum logic operations

Now let’s look at the next critical elements - the quantum logic operations. Each of these is represented by a small symbol with a letter or short phrase inside. Some act on individual qubits, like bit flips (X), phase flips (Z), and Hadamard gates (H). Others are drawn as connecting two qubits together - common examples are the SWAP and CNOT gates. The CNOT gate is a very special form of conditional logic similar to the conventional XOR gate. These two-qubit gates are essential for actually building up the complex quantum state which is used to perform a computation inside the quantum computer. Due to its action, it’s also known as an “entangling gate” which (under the right circumstances) generates entanglement between qubits.

Measurement

The final element is measurement. In quantum computers, we generally only perform measurements at the end of a quantum computation, because once we perform a measurement on a qubit, we destroy quantum superpositions. The result of any measurement on an individual qubit will be a 1 or a 0.

Consider a simple example. Let’s start with two qubits initialized in the state $|0 \rangle$, each represented as a rail. Now let’s perform a Hadamard gate on the first qubit. This transforms qubit one from a basis state to an equal superposition of the two basis states of the qubit. On the Bloch sphere that means it evolves from a pole to the equator. If you then apply a CNOT gate between the two qubits while the first is in a superposition, the result is a fundamentally different object. Instead of two separate qubits, we now have an entangled pair in something called a Bell State.

There’s just no way to describe that classically as two separate qubits; the state now exists not as individual qubits but rather as a mathematical description of the “correlations” between them. These correlations describe how the outcome of measurements on one qubit would be linked to measurements on the other. With this example, measuring 0 or 1 on one qubit would ALWAYS result in the same measurement outcome on the other. That’s because they aren’t really independent anymore!

That’s a pretty simple example that does something really interesting but not necessarily really useful. But if you add together enough qubits and enough operations in just the right way, you can actually perform something quite impactful...like Shor’s algorithm.

Building a useful quantum algorithm requires us to manipulate the enormous superposition states of all qubits in such a way that even when we destroy everything at the end by measuring our qubits we still get a useful outcome. Shor’s algorithm is extremely clever because it figures out how to do this successfully. That’s great! However, Shor’s algorithm is extremely complex to implement. Performing any useful factoring will require thousands of qubits each capable of performing perhaps trillions of operations as the algorithm runs.

So although quantum computers have advantages over classical computers, why aren’t we there yet? The answer is noise and error which cause quantum computers to fail.