The Nature of Quantum Computing: Parallelism Is Easy, Interference Is Hard

This is an expansion of a post about the natural visualization of quantum parallelism during quantum state initialization as a binomial tree.

While superposition and entanglement are mentioned a lot as quantum features that make Quantum Computing useful, they are really not specific to quantum phenomena. A spinning coin or rolling die are in a state that is considered a superposition of their possible outcomes. Entanglement is also reflected in conditional probabilities, and in any program that uses conditional statements. What makes entanglement special in quantum mechanics is that it can work at a distance. It is also expensive to implement in real quantum hardware. Like in any program, conditionals make variables interact. Without such interaction, independent variables could only implement logic that is remotely interesting or useful.

The real power of Quantum Computing comes from parallelism: applying a single-qubit gate instantly changes the amplitudes (complex probabilities) of all possible outcomes, which can be thought of as all binary strings with a position for each qubit in the system. The data is not stored in the qubits, it is either reflected in the exponential number of amplitudes, or in the outcomes that are allowed or prioritized to be measured. In both cases the changes are made by applying single-qubit gates, which in turn update the amplitudes of all possible outcomes.

Parallelism

Typically a quantum system starts in a deterministic state where the only possible outcome is the one consisting of only 0s, which has amplitude 1, and all the other outcomes have amplitude 0. When we apply a single-qubit gate to a qubit, a transfer of amplitude will happen, making the 1 side of that qubit possible. Applying another gate to a new qubit will "transfer" some (or all) of the existing amplitudes to an equal number of new outcomes. The growth matches a binomial tree, where at each step you take a copy of the existing tree, and do a pairwise transfer of amplitude from the existing to the new tree. Note that labels at a given level in the tree decompose in the same number of powers of 2.

It is important to note that the same formula is used for the transfer in all pairs. If you look at a single-qubit gate as a 2x2 matrix, only the first column matters at this stage, consisting of two complex numbers whose squared lengths add up to 1, just like in a rotation that uses the cosine and sine of the same angle as mathematical representation.

The classical equivalent of quantum parallelism is a giant for loop that processes all amplitudes in pairs. Here is a simple implementation from a simulator, with a complete description of what a single-qubit gate does:

A system of 40 qubits has over a trillion amplitudes, and classically updating all of them with every operation is quite expensive. Adding the 41st qubit and applying a gate to it creates more than a trillion amplitudes and outcomes in parallel. That shows the real power of Quantum Computing.

Interference

Using the same formula for all pairs simplifies the parallel construction, but also creates specific patterns that make building a desired state very hard. Each amplitude is affected by the gates applied to all qubits. To understand how the process works, let us look at one of the amplitudes in the state above, let's say 13. Its amplitude will reflect transfers from parents in the level above its own, and children in the level below. The parents are those obtained with removing one of the powers of 2 in its representation as 13 = 8 + 4 + 1. The children are those obtained by adding one of the missing powers of 2, in this case there is only one. Qubits can be thought of as dimensions, each of them pairing states at a given distance.

Having simple rules is both a blessing and a curse though. As we know from Digital Signaling Processing and other fields, interference is hard to tame. Applying a gate has a huge blast radius, countered by the ability to use controlled gates, which limits the set of amplitudes that get changed. Controlled gates require entanglement, but are easy to implement in a simulator:

Combining (controlled) quantum gates to build a desired state through interference is both a science and an art. The two best known tools that help achieving this goal are the Quantum Fourier Transform and the Grover Iterate, on which many quantum algorithms are built.

Fourier Transforms

Fourier transforms are used in many fields, and are quite well understood. The quantum version turns out to be a useful tool that makes many algorithms efficient. It can convert phase patterns into magnitude ones, and the other way around. For example, a rotation can be used to create a geometric phase sequence with a certain period into amplitudes whose magnitudes are higher around that period. This is the essence of the Phase Estimation algorithm. We can use this idea to encode numbers, for example, let us say we want to encode 10.67 using 4 qubits.

The colors reflect where the amplitude phases fall on the color wheel. Simulator code to implement the encoding is shown here:

Grover Iterates

A Grover Iterate helps amplify the amplitudes of selected outcomes. That is a very useful pattern that is using interference in a very clever and counterintuitive way. As an example, this is the result of using 3 iterations to increase the amplitude of 11 in a 4-qubit system.

Simulator code to implement the encoding is shown here, with a superposition created using Ry rotations:

A lot of times we have to heuristically create our own interference patterns, as we can do to create a quantum state that only allows outcomes with no consecutive 1s, whose number is a Fibonacci number.

Remarks

Quantum Parallelism is extremely powerful, but taking advantage of it requires taming interference. Mapping business problems to efficient interference patterns is hard. Coming up with new interference patterns is also hard. It is ideal that the two aspects are kept separate, as patterns can be applied to many problems.

We showed the classical versions of applying Fourier Transforms and Grover iterates to emphasize the simplicity of using such patterns after they are discovered. Simulators are great at exploring interference patterns, but there is no substitute for quantum parallelism, which is only possible on quantum devices.