Quantum Algorithms
Hopefully you have read my earlier posts on quantum mechanics or similar. So now that we understand a bit about quantum mechanics and how we express state in a quantum computer, we can start to think about what a quantum algorithm looks like.
We have learnt that qubits can be held in a superposition of quantum states. A system with n qubits can have a superposition of 2ⁿ states that can be operated on simultaneously, so quantum computers scale exponentially. And we’ve learnt that the superposition represents multiple quantum states coexisting in the waveform. The superposition defines the likelihood that when measured the qubit will be in any given state. To build a quantum algorithm we must manipulate the wave function so that when we measure the qubits we are likely to get the right answer.
We represent quantum algorithms as circuits: a series of operations performed on qubits linearly over time. Operations are performed by gates, which may operate on one or two qubits. Once the circuit has completed, the state of one or more qubits will be observed. If the state of the qubits is not observed then the operations can be reversed to undo the state transitions of the qubits.
In fact it is important for the gates to perform reversible operations for the operations to be deterministic in their manipulation of the wave function. This is because the laws of physics are themselves reversible and we need to maintain the superposition of states over a quantum circuit for it to work. If we were to discard information such that we were not able to reverse the operations then that could count as a measurement and could cause the wave form of the system to collapse.
Initialising the quantum computer
We know that once measured a qubit is in a certain state and that subsequent measurements will return the same result. So we can reset the system by measuring the observables.
Manipulating qubits with quantum gates
Quantum gates change the state of the quantum computer, putting the qubits into a superposition of quantum states or entangling qubits so that the result of one depends on another. Quantum gates correspond to local unitary transformations: unitary transformations on a fixed number of qubits. A transformation is unitary if the sum of all probabilities of all basis states is one. Gates can be represented by tables such as the following where the inputs on the left are transformed to the state on the right.
|00⟩ → |00⟩
|01⟩ → |01⟩
|10⟩ → 1/√2 (|10⟩ + |11⟩)
|11⟩ → 1/√2 (|10⟩ — |11⟩)
If we represented this gate as a matrix with rows as input basis vectors and columns as output basis vectors then its inverse must be its conjugate transpose in order for the gate to be unitary and therefore feasible.
Shor gives an example using the gate above in his paper “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer ” which I’m summarising here:
Suppose our machine is in the following superposition of states
1/√2 |10⟩ + 1/√2 |11⟩
and we apply the unitary transformation represented by the gate above.
The resulting output once the starting state has been multiplied by the gate matrix will be:
1/√2 . 1/√2 (|10⟩ + |11⟩) — 1/√2 . 1/√2 (|10⟩ — |11⟩) = |11⟩
Had we started with a different state we would have ended up with a different state, but given our starting wave function we can be sure that when we measure the circuit it is in state |11⟩.
This is a neat example of how quantum interference can be used to eliminate states, leaving us potentially with the answer we want. Remember that interference is when waves reinforce each other or cancel out. Quantum algorithms often rely on superposition to perform calculations on many values in parallel. The next step is to manipulate the superposition to get a high probability of the answer we want so that the result we measure has a high probability of being correct.
In a quantum circuit we represent each qubit as a horizontal line and then apply gates to the qubits over time, making the quantum circuit analogous to a music score that instructs us to perform operations on sound of specific frequencies.
In the circuit below Hadamard gates are applied to the first set of qubits, then a unitary operator is applied to the second set of n qubits to raise a number a to the power of 2, with the first set of qubits used as control qubits. Finally we apply a Quantum Fourier Transform to the first set of qubits and we measure the result. This is a summary of Shor’s Algorithm which I will describe later.
Gates are implemented by manipulating the state of one or more qubits. Where the gate operates on more than one qubit the operation depends on quantum entanglement. Gates are implemented in different ways for different quantum technology, but commonly microwaves or lasers are used to control the qubits at very low temperatures.
Reading out the result
Once all the gates have been applied, it is time to read the result from the quantum circuit. Ideally the end state will be a pure state that can be completely observed with compatible measurements, but that is rarely practical. The uncertainty principle means that incompatible measurements can alter previously observed states. For example if you measure position after measuring momentum then subsequent measurements of momentum will be changed. Compatible measurements however can be combined and mixed measurements can be used to derive results statistically.
Noise and error correction
Quantum computers are noisy in that they contain a great number of errors. Errors can occur when initiating the qubits, when applying gates and when measuring the state of the qubits at the end. Even without errors in the implementation of the machine, pure measurement is rarely practical so the result must be derived statistically.
To handle the high error rates in quantum circuits it is common to encode one logical qubit with a number of physical qubits where the redundancy is used for error correction. This means that when we read in the news about machines with hundreds of qubits, generally they are talking about physical qubits and the machines still only have a few logical qubits. This makes it hard to use them for any practical use and only a very small number of problems have been successfully mapped to a real quantum device.
To make matters worse, quantum algorithms rely on manipulating probabilities to give a high chance of success. This means that uncertainty and error is built into the algorithm: we are likely to get a correct answer but we might not. We’ll look later at Shor’s algorithm which first involves guessing a value that might give us a correct result, then assuming our guess is good, the algorithm is still not guaranteed to give us a correct answer, but is likely to give us an answer that is close. For some algorithms the wrong answer might be close to the right answer in some way so we can avoid rerunning the quantum subroutine and instead try a range of value close to the value we measured.
At the moment it is only possible to perform a hundred or so gates on a quantum circuit without error and for most practical applications of quantum computing we need millions of gates so we have a long way to go, but I am now confident that we will get there within my lifetime. Possibly before my children have the opportunity to study quantum computing.
