A Busy Developer’s Guide to Quantum Computing - Part 2
Introduction
In the previous Part of the series, I gave a quick overview of a quantum computer. In this Part, I’m going to talk a little bit about qubits and other building blocks behind that picture.
I keep it lightweight, showing only the parts necessary to understand the logic behind this discussion.
Let’s start from a single qubit.
Single qubit
Qubit is the basic building block of a quantum computer. It represents a single quantum effect. Notable examples of these effects include the energy levels of a trapped ion, photon polarization, and electron spin.
We can treat a qubit as an abstraction that hides a physical implementation (a two-level quantum mechanical system) and exposes only the features essential for quantum computation.
A qubit can switch between two states — we can assign them with values 0 and 1. In this sense, a qubit resembles a single bit of classical computer memory. However, sometimes a qubit behaves as being in both states at once. We say that such a qubit is in a superposition.
We can do two kinds of actions with a qubit: transform and measure.
Measuring a qubit
It is impossible to just peek inside a qubit to determine its state. When we want to read the qubit value, we need to measure it first. Only then we are able to copy it to classical memory for further use.
A measurement always returns a definite value: 0 or 1 — regardless if the qubit was in superposition or not. By measuring a qubit in superposition we force it to choose one of the two values. A result of such measurement will be random — we cannot predict which value will be returned for the particular qubit, but we can predict a probability of getting a given value at measurement.
At the same time, a measurement resets the qubit state. If we perform a second measurement immediately after the first one, it will always return the same value. It means that by measuring a single qubit we are not able to determine if it was in a superposition or not. To recreate the information about the superposition we need to do an experiment on a series of identically prepared qubits. Later, in Part 3, you’ll see how these experiments can be done in IBM Qiskit.
In the experiment, we take a large sample of identically prepared qubits and measure each of them in sequence to gather statistics. The statistics are random, but they should reflect a predicted probability.
A result of an experiment with a single qubit in a superposition with a probability distributed unevenly
Basic qubit states are usually represented as symbols: |0⟩ and |1⟩. A superposition is represented as a linear combination of basic states:
A superposition with arbitrary probabilities
The coefficients a₀ and a₁ represent the probability of getting each value at measurement. Later, I usually omit these coefficients for simplicity. Here, a combination without coefficients represents a superposition with probabilities distributed evenly:
A superposition with probabilities distributed evenly
Transforming a qubit
We can change the qubit state without measuring it by applying a transformation. Any transformation can be defined as a function on basic states.
An example transformation defined on basic states
For example, the above transformation:
- when applied to a qubit in state |0⟩ — transforms it to |1⟩,
- when applied to a qubit in state |1⟩ — transforms it to |0⟩.
This transformation resembles a logic Not operation from a classic computer. You can look at this transformation as a logic operation flipping the bit value of the qubit. Later, in Part 3 I’ll talk more about how you can define custom transformations.
It is important to realize that a transformation does not require any measurement in order to work. When applied to a superposition, the transformation behaves as if processing both basic states in parallel, while preserving the probabilities.
For example, let's assume we have a qubit in a superposition where the probability of measuring |0⟩ is 0.75, and the probability of measuring |1⟩ is 0.25. If we apply the above transformation to this qubit, the probabilities will be preserved but the bit value will be flipped for both basic states. Now, the probability of measuring |0⟩ will be 0.25, and the probability of measuring |1⟩ will be 0.75.
Note that there is no randomness here, even though we speak about probabilities. Randomness appears only when by measuring the qubit we force it to choose one of the two values.
This leads us back to vectorization.
Qubit and vectorization
We can treat a transformation on a qubit as the simplest case of vectorization.
A single qubit as the simplest case of vectorization
The function here represents a transformation working on both elements of the vector in parallel. The vector has two elements corresponding to 0 and 1. Each element represents an expected probability of getting given value at measurement.
There is yet another specific feature of qubit transformation that may be counterintuitive. A result of a transformation on one element can influence the probability of the other one and vice versa. Multiple results computed in parallel can amplify a given probability or cancel each other out.
To understand how canceling out probabilities is possible, we need to talk a little bit about phase.
Probability and phase
Probability in quantum computing has two parameters: amplitude and phase. In that regard it behaves a little bit like waves. Here, I follow a simplified description and assume that phase can be either equal or opposite (see: Quantum Computing for Everyone by Chris Bernhardt).
Recall, that when two identical waves meet crest-to-crest, they amplify each other — we say that they are in the same phase. When they meet crest-to-trough, they cancel each other out — we say that they are in opposite phases.
We will represent an opposite phase as a “minus” sign added to a basic state or a superposition. For example, in the following superposition, the “minus” sign signals that the basic states |0⟩ and |1⟩ are in opposite phases:
A superposition with probabilities in opposite phases
The phase has no effect at measurement. An effective probability of getting a given value at measurement is represented by the amplitude alone. But the phase plays an important role during computation. It allows us to cancel out unwanted results of the parallel computation.
Quantum register
A set of qubits put together in sequence creates a quantum register. We’ll see how the rules governing single qubits generalize to the whole register.
Instead of looking at separate states of individual qubits, we will consider a joint state of the whole register. For example, for two qubits, we get the following basic states of the register: |00⟩, |01⟩, |10⟩, |11⟩. Here, each basic state is written as |ab⟩, where “a” and “b” represent the states of each qubit in the register — the left bit is the state of the first qubit, and the right bit is the state of the second qubit.
Basic register state as a combination of qubit states
Each basic state of the register of length k corresponds to one binary integer of the same length — with each qubit representing one binary digit.
Just like a single qubit, a quantum register can be in a superposition. And like a single qubit, it can be transformed and measured.
Measuring a register
Measuring a register means measuring each individual qubit in sequence. The order in which qubits are measured can be arbitrary.
Each measurement of an individual qubit returns a definite value: 0 or 1 — which corresponds to one digit of a binary integer. To get a complete integer we need to measure all qubits.
A register in superposition behaves as being in many basic states at once. Again, we cannot predict which value will be returned for the particular set of qubits, but we can predict a probability of getting given values at measurement.
In general, a superposition of the register can be represented as a linear combination of basic states with some coefficients representing probabilities:
A quantum register in a superposition with arbitrary probabilities
Again, in case of a superposition with probabilities distributed evenly, I’m omitting these coefficients for simplicity:
A quantum register in a superposition with probabilities distributed evenly
Entanglement
Sometimes, a superposition can be decomposed into independent states of individual qubits:
A state of the quantum register as a composition of states of two qubits in superpositions
The above superposition is a linear combination of two qubits in superpositions. Each basic state of the left qubit is combined with each basic state of the right qubit which gives the resulting state of the register.
In such a case, the expected probabilities of measuring each qubit remain independent. If we measure one qubit — no matter what result we get — it has no influence on our expectation about measuring the other qubit.
But the state of the register is not always a simple combination of the states of individual qubits. The register allows for states, in which the expected probabilities of individual qubits depend on each other. We say that such qubits are entangled.
For example, let’s consider the following state of the register:
A quantum register in an entangled state
In this case, if we measure one qubit and get 0, then a measurement of the other qubit will always give us 0. Likewise, if we measure one qubit and get 1, then a measurement of the other qubit will always give us 1. And it is not important which qubit is measured first.
Role of entanglement
Quantum entanglement is essential for allowing a quantum computational speed-up in many algorithms (see: Jozsa-Linden). It’s also crucial for the approach to solving custom problems I’m presenting in this series.
Thanks to entanglement we can create key-value pairs described in Part 1.
A key-value pair with k bits representing a key plus additional bits containing a value
The picture above shows one basic state of a multi-qubit register. First _k _qubits represent a constant key and the rest qubits a mutable value associated with the key.
But we usually don’t want to store a single key-value pair in the register. Rather, we want to create a superposition that represents multiple key-value pairs simultaneously. Entanglement enables it.
We can implement it by creating a superposition containing all keys and entangling each key with its associated value. Entanglement allows us to associate any value to any key in the superposition.
Transforming a register
Transformations on a register can span multiple qubits at once. For example, a transformation needs to span at least two qubits to be able to produce entangled states. I’m going to show it in more detail in Part 3.
As before, when applied to a superposition, the transformation behaves as if processing all basic states in parallel, while preserving their probabilities.
As before, the results of the transformation of one element can influence the probabilities of the others. Multiple results computed in parallel can amplify a given probability or cancel each other out.
Register and vectorization
By extension, we can treat a transformation of the register as a form of vectorization.
A transformation processing all basic states in parallel
The function here represents a transformation working on all elements of the vector in parallel. The vector elements correspond to all basic states of the register. Each element represents an expected probability of getting a given value at measurement.
Measuring all qubits in the register results in a single value — a single binary integer of length
Measuring all qubits results in a single value
Putting it all together
In effect, we returned to the picture presented in Part 1:
- Here, a vector represents the state of a quantum register — possibly in a superposition.
- Each vector element corresponds to one binary integer and represents a probability of getting a given value at measurement.
- Computation is performed as a sequence of transformations on the register. Each transformation produces a new vector.
- Finally, we perform a measurement which produces a single number. The result may be random but its probability is determined by the preceding transformations.
- The trick is to guide the computation in a way that would increase the probability of getting an expected result at measurement.
Summary
In this Part, I talked a little bit about qubits and quantum registers. I discussed two kinds of actions that can be performed on them: measurement and transformations. I discussed superpositions and how they relate to measurement and transformations. I talked a little bit about specific quantum features like probability phase and quantum entanglement. I showed how these concepts relate to the vectorization analogy presented previously.
In Part 3, I briefly describe how programming a quantum computer can actually look. I discuss how you can define custom transformations and create entangled states in practice.
