Making Quantum Computers
Superposition, quantum parallelism, and entanglement are the three key ingredients for qubits in quantum computers. But what is the recipe for mixing these ingredients to make quantum chips?
Superposition
Superposition is a fancy word for a linear combination. For a quantum bit (qubit) there are only two possible states: \(|0\rangle\) and \(|1\rangle\). But instead of having a purely binary value, a qubit is generally in linear combination of both: \(a|0\rangle + b|1\rangle\).
Prior to measurement, a qubit is typically in such a superposition. Measurement corresponds to projection of an observable quantum state onto one of the basis vectors of the measurement basis selected. So, when you measure a qubit, you still only get one of two possible states with the probability given by the squared absolute values of the (complex) amplitudes, which is known as Born’s rule.
The normalization constraint \(|a|^2+|b|^2=1\) is such that these probabilities sum up to unity: the qubit must, upon measurement in the standard computational basis, be in either the \(|0\rangle\) or \(|1\rangle\) state. There are no other options, because it is a qubit.
Quantum Parallelism
The memory requirements for simulating a quantum computer on a regular computer scale exponentially with the number of qubits. That is because each qubit will be in a superposition of two distinct states. With two qubits, we have four possible states. At three qubits, we have eight states, and so on. Quantum parallelism is therefore a consequence of superposition.
To see that quantum parallelism is quite different from parallelism in CPUs and GPUs, we merely have to think about how such processors achieve it: with multiple copies of the same hardware. Beyond that, we still need algorithms that can exploit the additional cores. That last bit is similar to quantum computers, but the key difference is of course that the parallelism is baked into the machine by quantum physics: we do not need additional hardware at all.
Not all algorithms can, however, fully exploit quantum parallelism, which is why the speed-up of quantum algorithms can be exponential, but it rarely is, and definitely not by default. So far, we only know of a few algorithms that are of practical use and come with exponential speed-ups: Shor’s for integer factorization, HHL’s for solving sparse linear systems, and QFT.
Many online articles 'explain' that quantum computers process all possible states at the same time, which is what makes quantum computers fast. That is complete nonsense! Upon measurement you only see one of many possible outcomes. It is the quantum algorithm that may be able to exploit quantum parallelism prior to measurement, which can yield up to exponential speed-ups, but that is definitely not a given.
Entanglement
Without entanglement, superposition and quantum parallelism are worthless. Or rather: they do not offer any advantage to a classical computer, because we could easily simulate the behaviour of such machines on CPUs or GPUs.
In quantum computers, there are two essential ways of generating interactions: interference and entanglement. Interference allows desired solutions of algorithms to be amplified while undesired solutions are muted. It is, for instance, used in Grover’s search algorithm. But Grover’s algorithm also relies on entanglement.
Entanglement is a way of efficiently encoding varying levels of correlations among qubits, regardless of their physical separation. Entanglement is thought to be a necessary condition for quantum advantage or a speed-up in algorithms, because entanglement tends to be hard to simulate efficiently on a classical computer. It is not a sufficient condition for a quantum speed-up as per the Gottesman–Knill theorem, though.
DiVincenzo Criteria
The DiVincenzo criteria are a set of necessary cooking instructions needed to make a practical quantum computer from qubits based on the three core ingredients: superposition, quantum parallelism, and entanglement. These criteria are fairly obvious, but that does not necessarily make them easy to achieve on different types of hardware.
First off, qubits need to be well-defined and scalable, so each qubit can be addressed individually and we can have as many as needed. Once you have these qubits, you need to be able to initialize them, apply a universal set of gates (i.e. operations) on them with decent coherence times, and measure the qubits with high fidelity.
Hardware: Qubit Modalities
How easy or hard it is to satisfy these criteria depends on the underlying hardware. There are many different qubit modalities or flavours: superconductors (charge, phase, flux), trapped ions (energy levels), neutral atoms (energy levels), quantum dots (electron spins), nitrogen vacancies in diamond (electron and nuclear spins), photonics (modes), NMR (nuclear spins), and topological qubits (Majorana bound states). Apart from photonics and possibly NV centres in diamond, all flavours must be chilled near absolute zero during use.
While superconductors are the most common flavour today, they have lower gate fidelity and coherence times than trapped ions. Superconducting qubits somewhat make up for that with a much higher gate speed, though. For both flavours, there exist designs to scale these systems to a few thousand physical qubits already. The other technologies are not yet quite as advanced.
Adiabatic quantum computers and quantum annealers are special flavours that do not have any quantum logic gates.
In adiabatic quantum computers, the idea is to find the ground state of a Hamiltonian (think: function) by slowing changing a Hamiltonian with a known ground state into the desired one.
If that happens adiabatically (i.e. slowly enough), the system remains in the ground state, so you obtain the ground state of the Hamiltonian of interest.
Unfortunately, for large problems, we tend to bump into the 'minimal gap' problem: the phase transition from the initial to the desired Hamiltonian leads to an 'avoided crossing', or a set of energy states that come close but never quite touch.
It is nearly impossible to prevent the system from leaping to such excited states due to environmental noise, even at extremely low temperatures.
Quantum annealers can actually leave the ground state, but they rely on tunnelling and relaxation to return to the ground state after passing an avoided crossing instead.
It has yet to be proven whether quantum annealing offers any quantum advantage.
While these flavours differ in their mode of operation, they all share the same core ingredients for the qubits: superposition, quantum parallelism, and entanglement. Using the five steps from DiVincenzo, we can thus make quantum chips.
Bon appétit!