Tag: quantum computing

Visualising qubits on the Bloch sphere

This post brings together visualisations and sums that I found really helpful for getting to grips with the Bloch sphere representation of qubit states.

Recap

The state of a qubit is represented by the linear combination

\(\displaystyle \alpha |0\rangle + \beta |1\rangle\)

for complex amplitudes \(\alpha, \beta \in \mathbb{C}\). The amplitudes satisfy \(|\alpha|^2 + |\beta|^2 = 1\), where

\(\displaystyle |x  + yi| = \sqrt{x^2 + y^2}\),

the modulus of a complex number.

The probability of measuring (using the classical basis) a 0 is \(|\alpha|^2\) and of measuring a 1 is \(|\beta|^2\), by the Born rule.

Distinct states can imply the same measurement probabilities:

Example 1. The amplitudes in the following state are defined without any imaginary component:

\(\displaystyle \sqrt{\frac{1}{2}} |0\rangle + \sqrt{\frac{1}{2}} |1\rangle\).

Apply the Born rule and the probability of both measurement outcomes is \(\frac{1}{2}\).□

Example 2. The following example has an imaginary component in both amplitudes:

\(\displaystyle \frac{1}{2}(1 + i) |0\rangle + \frac{1}{2}(1 + i) |1\rangle\).

The modulus of both amplitudes is \(\sqrt{(\frac{1}{2})^2 + (\frac{1}{2})^2} = \sqrt{\frac{1}{2}}\). So the probability of obtaining either a 0 or a 1 is again \(\frac{1}{2}\).□

Bloch sphere

The state of a qubit can be represented as a point on the surface of sphere, known as the Bloch sphere. To make sense of this representation, let’s look at a couple of animations, GIFed from the QuVis visualisation project at the University of St Andrews.

Firstly, consider the following circle sliding down and up the sphere (you could think of this as travelling along the sphere’s latitudes):

The first thing to note is that the north (top) and south (bottom) pole of the sphere are where the pure \(|0\rangle\) and \(|1\rangle\) states live, respectively.

The location of the circle determines the probability of a particular measurement outcome. If the circle is at the north pole, then the probability of measuring a 0 is 1. If it’s at the south pole, then the probability of measuring a 1 is 1. At the equator, there’s a 50-50 chance of a 0 or a 1. All points on the circle at any given latitude represent states with the same measurement probabilities. Each latitude circle denotes what is called a magnitude.

Now let’s stop in the middle latitude. We can also rotate around the sphere (think of this as travelling along different longitudes):

These circles represent different relative phases of the state. Phases cannot be directly detected by measurement using the classical computational basis; however, there are methods to see what the phase is and phases are important in quantum algorithms.

Here’s a still of the sphere:

The angle \(\theta\) indexes the longitudes (moving north or south) and \(\phi\) indexes the longitudes (sweeping east or west).

The state of a qubit can be written in terms of these two parameters as follows:

\(\displaystyle \cos\frac{\theta}{2} |0\rangle + e^{i \phi} \sin\frac{\theta}{2} |1\rangle\).

Let’s fix \(\phi = 0\), so \(e^{i \phi} = 1\) and the equation above simplifies to:

\(\displaystyle \cos\frac{\theta}{2} |0\rangle + \sin\frac{\theta}{2} |1\rangle\).

The full sweep from north pole to south pole is \(180^{\circ}\) or \(\pi\) radians. Let’s try north pole (\(\theta = 0\)), equator (\(\theta = \frac{\pi}{2}\)), and south pole (\(\theta = \pi\)).

\(\theta\) \(\displaystyle \alpha = \cos\frac{\theta}{2}\) \(\displaystyle \beta = \sin\frac{\theta}{2}\) State
\(\displaystyle 0\) \(1\) \(0\) \(\displaystyle |0\rangle\)
\(\displaystyle \frac{\pi}{2}\) \(\displaystyle \sqrt{\frac{1}{2}}\) \(\displaystyle \sqrt{\frac{1}{2}}\) \(\displaystyle \frac{|0\rangle + |1\rangle}{\sqrt{2}}\)
\(\displaystyle \pi\) \(0\) \(1\) \(\displaystyle |1\rangle\)

Now what effect does the phase have? Fix \(\theta = \frac{\pi}{2}\), so the measurement probabilities are constant. A \(360^{\circ}\) turn is equal to \(2\pi\) radians. We shall try \(\phi = 0, \frac{\pi}{2}, \pi, \frac{3\pi}{2}\). This time I’m using Grokking the Bloch Sphere to visualise.

Bloch sphere \(\phi\) \(\displaystyle \alpha = \cos\frac{\theta}{2}\) \(\displaystyle \beta = e^{i \phi} \sin\frac{\theta}{2}\)
\(\displaystyle 0\) \(\displaystyle \frac{1}{\sqrt{2}}\) \(\displaystyle \frac{1}{\sqrt{2}}\)
 \(\displaystyle \frac{\pi}{2}\) \(\displaystyle \frac{1}{\sqrt{2}}\) \(\displaystyle \frac{i}{\sqrt{2}}\)
 \(\displaystyle \pi\) \(\displaystyle \frac{1}{\sqrt{2}}\) \(\displaystyle -\frac{1}{\sqrt{2}}\)
 \(\displaystyle \frac{3\pi}{2}\) \(\displaystyle \frac{1}{\sqrt{2}}\) \(\displaystyle –\frac{i}{\sqrt{2}}\)

Note how the \(\beta\) amplitudes come in pairs, one positive, one negative. The sign flips when spinning half a circle.

Simple examples of bras and kets

Animated interpretation of the Matrix’s digital rain, by Jahobr

Quantum computing involves lots of matrix multiplication. After seeing definitions, sometimes you just need a few simple examples.

Here’s a matrix:

\(\begin{pmatrix}
3 & 1 & 4\\
1 & 5 & 9\\
2 & 6 & 5
\end{pmatrix}\)

We can pull out the second row by multiplying as follows:

\(\begin{pmatrix}
0 & 1 & 0
\end{pmatrix}\begin{pmatrix}
3 & 1 & 4\\
1 & 5 & 9\\
2 & 6 & 5
\end{pmatrix} = \begin{pmatrix}
1 & 5 & 9
\end{pmatrix}\)

And the third row:

\(\begin{pmatrix}
0 & 0 & 1
\end{pmatrix}\begin{pmatrix}
3 & 1 & 4\\
1 & 5 & 9\\
2 & 6 & 5
\end{pmatrix} = \begin{pmatrix}
2 & 6 & 5
\end{pmatrix}\)

Or the second column:

\(\begin{pmatrix}
3 & 1 & 4\\
1 & 5 & 9\\
2 & 6 & 5
\end{pmatrix} \begin{pmatrix}
0 \\
1 \\
0
\end{pmatrix} = \begin{pmatrix}
1 \\
5 \\
6
\end{pmatrix}\)

Here’s the middle element:

\(\begin{pmatrix}
0 & 1 & 0
\end{pmatrix}\begin{pmatrix}
3 & 1 & 4\\
1 & 5 & 9\\
2 & 6 & 5
\end{pmatrix} \begin{pmatrix}
0 \\
1 \\
0
\end{pmatrix} = 5\)

And the top-left element:

\(\begin{pmatrix}
1 & 0 & 0
\end{pmatrix}\begin{pmatrix}
3 & 1 & 4\\
1 & 5 & 9\\
2 & 6 & 5
\end{pmatrix} \begin{pmatrix}
1 \\
0 \\
0
\end{pmatrix} = 3\)

Bra-kets

Again, this time using Dirac notation.

Let \(M= \begin{pmatrix}
3 & 1 & 4\\
1 & 5 & 9\\
2 & 6 & 5
\end{pmatrix}\)

And define the following kets:

\(|e_o\rangle = \begin{pmatrix}
1\\
0\\
0
\end{pmatrix}\)

\(|e_1\rangle = \begin{pmatrix}
0\\
1\\
0
\end{pmatrix}\)

\(|e_2\rangle = \begin{pmatrix}
0\\
0\\
1
\end{pmatrix}\)

This means we get the following bras (yes, they are really called that):

\(\langle e_o | = \begin{pmatrix}
1 &
0 &
0
\end{pmatrix}\)

\(\langle e_1 | = \begin{pmatrix}
0 &
1 &
0
\end{pmatrix}\)

\(\langle e_2 | = \begin{pmatrix}
0 &
0 &
1
\end{pmatrix}\)

We can pull out the second row of \(M\) like so:

\(\langle e_1 | M = \begin{pmatrix}1 & 5 & 9\end{pmatrix}\)

And the third row:

\(\langle e_2 | M = \begin{pmatrix}2 & 6 & 5\end{pmatrix}\)

Or the second column:

\(M |e_1\rangle = \begin{pmatrix}
1 \\
5 \\
6
\end{pmatrix}\)

Here’s the middle element:

\(\langle e_1 | M | e_1 \rangle = 5\)

And the top-left:

\(\langle e_0 | M | e_0 \rangle = 3\)

To get the \(6\), do:

\(\langle e_2 | M | e_1 \rangle = 6\)

 

Measurement in quantum computing

This post explores what happens when you measure one entangled qubit in a part-entangled three-qubit system.

It’s easy to think about measurement for a single qubit. Suppose the qubit is in the following superposition:

\(\displaystyle \alpha |0\rangle + \beta|1\rangle\).

If we measure it, then by the Born rule

\(\displaystyle P(|0\rangle) = |\alpha|^2\) and

\(\displaystyle P(|1\rangle) = |\beta|^2\),

where \(|z|\) is the modulus of \(z\).

For example, if

\(\displaystyle |\psi\rangle = 0.6 |0\rangle + 0.8|1\rangle\),

then

\(\displaystyle P(|0\rangle) = |0.6|^2 = 0.36\), and

\(\displaystyle P(|1\rangle) = |0.8|^2 = 0.64\).

Following measurement, the qubit’s posterior state, \(|\psi’\rangle\), collapses to whatever the measurement outcome was, so \(|\psi’\rangle = |0\rangle\) or \(|\psi’\rangle = |1\rangle\).

We can measure one qubit in a system of two or more qubits, but now things are more complex. If the qubit we measure is entangled with others, then their superpositions collapse too. Any qubits that are unentangled with the one being measured should survive measurement unscathed.

Quantum mechanics gives us predictions for systems of any number of qubits and configurations (see Matuschak and Nielsen, 2020, postulate 3). Let’s see what happens when we apply it to the following three qubit system:

\(\displaystyle |\psi\rangle = \frac{|000\rangle + |011\rangle + |100\rangle + |111\rangle}{2}\)

Numbering the qubits right to left, the first two (call them \(q[0]\) and \(q[1]\)) are entangled, the third, \(q[2]\), is unentangled with the first two. We are going to measure \(q[0]\).

We need a set of measurement operators. For a single qubit in the classical measurement basis these are \(|0\rangle\langle 0|\) and \(|1\rangle\langle 1|\). To parse this Dirac notation, note that \(\langle \phi |^\dagger = |\phi \rangle\) and \(|\phi \rangle^\dagger = \langle \phi |\), where \(M^\dagger\) is the conjugate transpose of \(M\); i.e., transpose a row vector to a column vector, or vice versa, and take the complex conjugate of each element.

So

\(\displaystyle |0\rangle\langle 0| = \begin{pmatrix} 1\\ 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}\)

\(\displaystyle |1\rangle\langle 1| = \begin{pmatrix} 0\\ 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}\)

We have three qubits, so we need to pad out these measurement operators with the identity matrix to give

\(M_{q[0] = 0} = I \otimes I \otimes  |0\rangle\langle 0|\)

\(M_{q[0] = 1} = I \otimes I \otimes  |1\rangle\langle 1|\)

where

\(\displaystyle I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\)

and \(\otimes\) is the tensor product. This is exactly what we did previously when applying one qubit gates to systems of more than one qubit.

The probability that the measurement outcome for the first qubit is \(1\) is

\(\displaystyle P(q[0] = 1)  =  \langle \psi | M_{q[0] = 1}^\dagger  M_{q[0] = 1} |\psi\rangle = \frac{1}{2}\).

Suppose \(q[0] = 1\) is indeed the measurement outcome. What’s left of the system state (the posterior state), call it \(|\psi’\rangle\)?

\(\displaystyle |\psi’\rangle= \frac{M_{q[0] = 1} | \psi \rangle}{\sqrt{P(q[0] = 1)}} = \frac{\frac{1}{2}(|011\rangle + |111\rangle)}{\sqrt{\frac{1}{2}}} = \frac{|011\rangle + |111\rangle}{\sqrt{2}}\)

So, the first two qubits have collapsed to the same state, \(|1\rangle\). The third is still in superposition (it would be \(|0\rangle\) or \(|1\rangle\) if we measured it). The arithmetic works!

Maybe it’s easier to see what’s going on if we write \(|\psi’\rangle\) as

\(\displaystyle \frac{|011\rangle + |111\rangle}{\sqrt{2}} = \sqrt{0.5}|0{\underline{11}}\rangle + \sqrt{0.5}|1{\underline{11}}\rangle\).

The previously entangled qubits are now underlined. There’s a 50-50 chance that measuring again would give \(q[2]  = 1\) and a 100% chance that \(q[0] = q[1]  = 1\).

Similarly, the probability that \(q[0] = 0\)  is

\(\displaystyle P(q[0] = 0)  =  \langle \psi | M_{q[0] = 0}^\dagger  M_{q[0] = 0} |\psi\rangle = \frac{1}{2}\).

If this is the actual measurement outcome, then the posterior state is

\(\displaystyle |\psi’\rangle= \frac{M_{q[0] = 0} | \psi \rangle}{\sqrt{P(q[0] = 0)}} = \frac{\frac{1}{2}(|000\rangle + |011\rangle)}{\sqrt{\frac{1}{2}}} = \frac{|000\rangle + |100\rangle}{\sqrt{2}}\)

Again, the first two qubits have collapsed to the same state, this time \(|0\rangle\). The third is still in superposition.

Praxis

That’s the sums. Let’s see what happens when we run this on one of IBM Quantum’s computers. The circuit that establishes the state above and measures \(q[0]\), \(q[1]\), and \(q[2]\) (in that order) is as follows:

The OpenQASM code (auto generated) is:

OPENQASM 2.0;
include "qelib1.inc"

qreg q[3];
creg c[3];

reset q[0];
reset q[1];
reset q[2];
h q[0];
h q[2];
cx q[0], q[1];
measure q[0] -> c[0];
measure q[1] -> c[1];
measure q[2] -> c[2];

Results following 1,000 runs on ibmq_lima (a Falcon r4T):

Outcomes matched predictions for entanglement (\(q[0] = q[1]\)) on 92.3% of runs. Of these, 48.3% were both 1s (versus both 0s), 95% CI = [45.0, 51.6], which is compatible with the 50-50 split we would expect. However, \(q[2] = 1\) on 42% of those entangled trials, which is statistically significantly lower than the predicted 50% (95% CI = [39.1, 45.5]).

Second time lucky, in case that was a fluke:

The bar chart looks a little more symmetrical. This time on correctly entangled runs, \(q[2] = 1\) across 47.5% of those runs. This wasn’t statistically significantly different to 50% (95% CI = [44.3, 50.8]) so it’s compatible with what we expect. But maybe this series of runs was a fluke…?

Another time, with 10,000 runs: \(q[2] = 1\) across 46.2% of correctly entangled runs (95% CI = [45.2, 47.3]). So it seems possible there is some bias on ibmq_lima.

I tried again on another computer: ibm_oslo (a Falcon r5.11H). Now with 20,000 runs – the maximum allowed in one booking. The outcomes for \(q[0]\) and \(q[1]\) were the same (i.e., as predicted) on 93.9% of runs. Of those, \(q[2] = 1\) on 50.1% of runs and this was not statistically significantly different to 50%, 95% CI = [49.4, 50.8].

Digression on quantum randomness

At this point I began to suspect that I’m not the first person to investigate bias. Tamura and Shikano (2021) ran a series of random number generator tests on measurements on a 20 qubit computer, IBM 20Q Poughkeepsie, obtaining 4,743,168 samples for each qubit. The circuit had a Hadmard gate, establishing the state

\(\displaystyle H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}\).

The bias is already visible from their Figure 3, without examining the tests (though note the y-axis range – it’s not as bad as it first looks). The Born rule would predict results around 0.5 (and statistics would predict very close to it, given the sample size):

So it looks like Poughkeepsie is an imperfect implementation.

I tried the same circuit on ibm_oslo with 10,000 runs on 7 qubits:

Here are the results:

0 1 % of 1s Lower CI Upper CI CI inc. 50%
c[0] 5078 4922 49.2 48.2 50.2 TRUE
c[1] 4852 5148 51.5 50.5 52.5 FALSE
c[2] 5065 4935 49.4 48.4 50.3 TRUE
c[3] 4963 5037 50.4 49.4 51.4 TRUE
c[4] 5092 4908 49.1 48.1 50.1 TRUE
c[5] 5025 4975 49.8 48.8 50.7 TRUE
c[6] 4797 5203 52.0 51.0 53.0 FALSE

Looking only at the marginal frequencies, that looks random enough… Two of the 95% CIs didn’t include 50%, perhaps due to a fluke. There are a dozen other properties we would want to check (see Tamura and Shikano, 2021) . But I’ll stop there.

This illustrates that imperfect implementations of quantum theory (and an imperfect universe, perhaps!) means we can’t assume that random sequences generated by a quantum process will be any more random than a pseudorandom generator – even if the theory says they will be. We need to check. This is another illustration of the role of implementation in trustworthiness that arose when exploring the BB84 quantum key distribution protocol. BB84 is perfectly secure in theory, but lots of extra work is needed to take account of imperfect implementation.

References

Matuschak, A., & Nielsen, M. A. (2020). Quantum Mechanics Distilled.

Tamura, K., & Shikano, Y. (2021). Quantum Random Numbers Generated by a Cloud Superconducting Quantum Computer. In T. Takagi, M. Wakayama, K. Tanaka, N. Kunihiro, K. Kimoto, & Y. Ikematsu (Eds.), International Symposium on Mathematics, Quantum Theory, and Cryptography (Vol. 33, pp. 17–37). Springer Singapore.

Teleporting a quantum state

This post explores the results of trying quantum teleportation on an actual quantum computer™.

Suppose Alice has a quantum state she would like to send to Bob,

\(|\mathit{Alice\ state}\rangle = \alpha|0\rangle + \beta|1\rangle\),

and they both hold entangled qubits, \(|\mathit{Alice\ tangle}\rangle\) and \(|\mathit{Bob\ tangle}\rangle\). It’s possible to teleport \(|\mathit{Alice\ state}\rangle\) to Bob via the entanglement, even if they are millions of miles apart! I’m going for teleportation within a computer so not quite so far.

One step of the process, after some operators are applied, is that Alice measures her qubits and tells Bob what the outcomes were. These measurements – one of \(|0\rangle|0\rangle\), \(|0\rangle|1\rangle\), \(|1\rangle|0\rangle\), or \(|1\rangle|1\rangle\) at random – don’t reveal the qubit state being teleported. In fact Alice doesn’t even need to know the state, so could be relaying a private message. The communication of these two measurement outcomes can’t happen faster than light speed, so the teleportation doesn’t break relativity.

Here’s a picture of the process, in lieu of a proper explanation (built and simulated using IBM Quantum Composer):

The pink bit over on the right hand size follows the rules below (lightly reordered from Flarend and Hilborn, 2022, p. 156) to recover the state depending on the outcomes of Alice’s measurements:

alice_tangle alice_state Gate to apply to bob_tangle
0 0 \(I\)
0 1 \(Z\)
1 0 \(X\)
1 1 \(Y\)

Here are the Pauli matrices referred to above:

\(X = \begin{pmatrix} 0&1\\ 1&0 \end{pmatrix}\)

\(Y = i\begin{pmatrix} 0&-1\\ 1&0 \end{pmatrix}\)

\(Z = \begin{pmatrix} 1&0\\ 0&-1 \end{pmatrix}\)

(\(i = \sqrt{-1}\).)

\(I\) is the \(2 \times 2\) identity matrix that does nothing, so there’s a chance that the correct state magics its way to Bob without him applying any transformation. Alice just needs to tell him when she measured her qubits.

It works in the simulator, but annoyingly doesn’t run on IBM’s quantum computers because of the way I encoded the conditionals (Error: Instruction bfunc is not supported [7001]). I’ve used a classical computing conditional to choose which of the four gates to apply, which requires a sort of dynamic quantum circuit that’s not supported.

But there’s another way! Since \(Y = iXZ\), we get the following:

alice_tangle alice_state Gate to apply to bob_tangle
0 0 \(I\)
0 1 \(Z\)
1 0 \(X\)
1 1 \(iXZ\)

It’s possible to control \(Z\) and \(X\) with a qubit – the latter is just a controlled NOT (CNOT). So it looks easy to get the combinations. Apart from the \(i\). Mermin (2007, p. 154) ignores it for reasons I don’t yet follow (is the \(Y\) really needed after all?). He also has the gates in the order

which seems to me back to front. I’ll ignore \(i\) too but order the gates to match the arithmetic. Here’s a circuit, second attempt:

The state circled in purple is what Alice is sending to Bob. Since we know the correct answer, I (or Bob) will make the quantum tomography easier by inverting the RX and RY gates Alice used to setup the state. This means we can look out for an easier basis state, \(|0\rangle\) (the states circled in green show where the \(|0\rangle\) came from and where it is measured).

If the teleportation worked, the 3rd classical bit (most significant bit, leftmost) will always be a 0. It is in the simulations:

Now let’s try on the quantum computer. Off it goes to ibm_nairobi. Let’s see what happens…

It was actually on the queue for 40 minutes in the end.

And here are the results – not quite as nice as the simulation:

Did it work? Well, given what I expected to happen, it did on 68.2% of the 1,000 runs (95% CI = [65.1%, 71.0%]). Here’s a table:

Measurement outcome Frequency
000 136
001 201
010 188
011 157
100 106
101 102
110 60
111 50

I was hoping for something a bit closer to 99%, but whatever happened it’s definitely not just a coin flip!

Let’s give it another go with a simpler circuit:

This will only work when Alice’s measurements are \(|0\rangle|0\rangle\), so for this setup they both keep trying with fresh entangled pairs until Alice gets the desired measurements. Again she needs to tell him when she has measured and what she got. I’ve undone the superposition again Bob’s side, so by “work” I mean Bob’s measurement is also \(|0\rangle\). Looks good in the simulator:

Fingers crossed. Here’s what happens when it’s run on the actual™  computer (ibmq_belem).

That looks a lot better (we’re just interested in the two bars pointed to above). Though it’s still a bit suspicious that Bob’s qubit is mostly \(|0\rangle\), irrespective of what Alice’s qubits are.

I think I’ve found the problem (emphasis original):

“The IBM quantum computers currently do not support instructions after measurements, meaning we cannot run the quantum teleportation in its current form on real hardware. Fortunately, this does not limit our ability to perform any computations due to the deferred measurement principle… The principle states that any measurement can be postponed until the end of the circuit, i.e. we can move all the measurements to the end, and we should see the same results…”

Third time lucky – this time only measuring as a final step:

This looks a little more convincing since Bob gets about the same number of \(|1\rangle\)s and \(|0\rangle\)s when Alice’s qubits are wrong. He still mostly gets \(|0\rangle\) when Alice’s qubits align (i.e., she measures \(|0\rangle|0\rangle\)).

References

Flarend, A., & Hilborn, B. (2022). Quantum computing: from Alice to Bob. Oxford University Press.

Mermin, N. D. (2007). Quantum computer science: an introduction. Cambridge University Press.

Quantum key distribution using BB84

Suppose Alice has a secret message she wants to send to Bob. They have two information channels: a quantum channel (e.g., Bob is able to detect polarised photons sent by Alice from a satellite) and a two-way unsecure classical channel (e.g., unencrypted email). Let’s assume that the message and key are both encoded using binary and the key is a one-time pad. They will eventually XOR message and key to encrypt and decrypt the message. Eve the eavesdropper wants to intercept their messages.

BB84 (Bennett & Brassard, 1984) is an approach to quantum key distribution that allows Alice to send an encryption key to Bob and for them to verify with a high level of confidence that the key hasn’t been intercepted. Once convinced that the key was sent securely, Alice can use it to encrypt the secret message and send it over the unsecure classical channel. Bob safely decrypts at the other side.

BB84 takes advantages of three related features of quantum mechanics.

  1. If a qubit is in superposition, e.g., \(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\), then it’s impossible to infer its state from one observation. In particular, suppose an eavesdropper, Eve, measured the qubit and observed \(|1\rangle\). She couldn’t tell whether it had been in the state \(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\) or \(|1\rangle\).
  2. Once you measure a qubit in superposition, it collapses to a basis state, so Eve couldn’t intercept the key and retransmit it onto Bob.
  3. You also can’t clone a qubit that is in an unknown state so, e.g., Eve couldn’t intercept a qubit from Alice, clone it, measure one of the pair and pass the other unmeasured qubit onto Bob.

Here’s how BB84 works.

Alice begins by generating a stream of random bits:

110110100110000101110…

Some of these bits will be used for the key.

Next, she generates a random stream of bases, classical basis (\(+\)) or the Hadamard basis (\(\times\)):

\(+\)\(\times\)\(+\)\(+\)\(\times\)\(+\)\(\times\)\(+\)\(\times\)\(\times\)\(+\)\(\times\)\(\times\)\(+\)\(\times\)\(+\)\(\times\)\(\times\)\(+\)\(\times\)\(+\)…

These will determine which basis Alice uses to send each bit of the key. The figure below (from Mayers, 2001) shows the bases in state space.

For a photon, the classical basis corresponds to vertical/horizontal polarisation and the Hadamard basis to the diagonal polarisations. Note in this case the state space corresponds nicely with the physical realisation of the qubit; that won’t always be the case, e.g., consider spin up and down states for electrons.

Here are the qubit states Alice sends:

\(\Psi(0, +) = |0\rangle\)

\(\Psi(1, +) = |1\rangle\)

\(\displaystyle \Psi(0, \times) = H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}\)

\(\displaystyle \Psi(1, \times) = H|1\rangle = \frac{|0\rangle -|1\rangle}{\sqrt{2}}\)

Where \(\displaystyle H = \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix}\), the Hadamard gate.

Alice sends the potential key bits using the randomly chosen bases.

Bob measures them, randomly deciding whether to assume a classical or Hadamard basis – for the latter applying the Hadamard gate before measuring. The possible outcomes in the absence of eavesdropping are as follows:

Alice sends Bob assumes classical Bob assumes Hadamard
\(\Psi(0, +) = |0\rangle\) \(P(|0\rangle) = 1\) \(P(|0\rangle) = \frac{1}{2}\)
\(\Psi(1, +) = |1\rangle\) \(P(|1\rangle) = 1\) \(P(|1\rangle) = \frac{1}{2}\)
\(\Psi(0, \times) = H|0\rangle\) \(P(|0\rangle) = \frac{1}{2}\) \(P(|0\rangle) = 1\)
\(\Psi(1, \times) = H|1\rangle\) \(P(|1\rangle) = \frac{1}{2}\) \(P(|1\rangle) = 1\)

So if Bob randomly chooses the correct basis, he gets the correct bit; if not, he gets a random bit, with a 50-50 chance of a 1 or 0.

Bob tells Alice via the unsecure channel the sequence of bases he used. At this point, doing so doesn’t help Eve since the qubits have already been measured.

Alice tells Bob which bases were correct, again on the unsecure channel, so Bob can discard measurements for the rest. She also sacrifices a random sample of the key bits by sharing what the right answer is for those. If Eve intercepted any, then they won’t all have made it to Bob: either they will be missing or Eve will have had to replace them with a random bit.

If Alice and Bob are satisfied that the test qubits made it across okay without being intercepted, then they use the remainder for the key, sending the encrypted message through the unsecure channel.

That’s the gist. The devil’s in the detail, e.g., working out how many bits to send to ensure enough remain after checking for intercepts; how many to sacrifice to check that Eve wasn’t eavesdropping; while taking account of errors in transmission that will mean qubits don’t arrive intact for innocent reasons other than eavesdropping.

The security of BB84 depends on the quality of the implementation. The field of quantum hacking explores a variety of ways to exploit imperfections, e.g., classical side channels that leak information about what was sent, which can be intercepted without interfering with the qubit. Researchers devise clever ways to defend against these attacks. See, e.g., Dixon et al. (2017).

References

Bennett, C. H. & Brassard, G. (1984). Quantum cryptography: Public key distribution and coin tossing. Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing (pp. 175-179), India.

Dixon, A. R., Dynes, J. F., Lucamarini, M., Fröhlich, B., Sharpe, A. W., Plews, A., Tam, W., Yuan, Z. L., Tanizawa, Y., Sato, H., Kawamura, S., Fujiwara, M., Sasaki, M., & Shields, A. J. (2017). Quantum key distribution with hacking countermeasures and long term field trial. Scientific Reports, 7, 1978.

Mayers, D. (2001). Unconditional security in quantum cryptography. Journal of the ACM, 48, 351–406.

Quantum entanglement

This brief post shows how to establish an entangled state on IBM Quantum’s computers – here using ibmq_manila.

The circuit to establish \(\displaystyle \frac{|00\rangle + |11\rangle}{\sqrt{2}}\) is as follows:

A few clicks later, and the circuit is added to the queue…

The total wait to get onto ibmq_manila was about an hour and the circuit ran 1,000 times in 5 seconds.

Here are the results:

It worked across 93.9% of runs: both qubits had the same measurement outcome, roughly 50-50 split between \(|00\rangle\) and \(|11\rangle\).

 

Why do quantum circuits often end with an exclusive-OR (XOR)?

In a previous post I worked through the arithmetic of the Deutsch quantum algorithm to show that it works, but I avoided attempting to explain why any of it works. In this post I’ll explain one corner of the circuit: why the gate implementing the function tested by the algorithm outputs the exclusive-OR (XOR) of \(y\) and \(f(x)\): \(y \oplus f(x)\). See the picture below (Mermin, 2007, p. 42). The question is, why is that output not just \(f(x)\), since that’s what the circuit is supposed to compute?

There are two parts to the explanation. Firstly, quantum gates have to be reversible, because that’s how the physics works. The reason for that is far bigger than this blog post and I’m not a physicist. Try Richard Feynman’s (1985) explanation. If we believe Feynman, then the reason XOR appears in many algorithms is easy to grasp. Below I’ll expand the arithmetic provided by Mermin (2007, p. 37, the paragraph around equation 2.3).

Let’s start with the punchline.

Double application of \(U_f\) leads to the bottom register of the circuit evaluating to \([y \oplus f(x)] \oplus f(x)\), which is equivalent to \(y \oplus [f(x) \oplus f(x)]\) by the associativity of \(\oplus\). This simplifies to \(y\), as the table below shows for the four combinations of \(y\) and \(f(x)\):

\(y\) \(f(x)\) \(\overbrace{f(x) \oplus f(x)}^{\textstyle z}\) \(y \oplus z\)
0 0 0 0
0 1 0 0
1 0 0 1
1 1 0 1

Note how \(f(x) \oplus f(x)\) cancels out \(f(x)\), leaving \(y\), so the first and last column are equal. The XOR ensures that double application of \(U_f\) gives us \(y\) again!

Another way to write this without the table:

\([y \oplus f(x)] \oplus f(x)\)

= { associativity of \(\oplus\) }

\(y \oplus [f(x) \oplus f(x)]\)

= { since \(1 \oplus 1 = 0\oplus 0 = 0\) }

\(y \oplus 0\)

= { definition of \(\oplus\) }

\(y\).

Now we just have to show that

\(U_f U_f (|x\rangle \otimes |y\rangle)\)

sends us to

\(| x\rangle \otimes | y \oplus f(x) \oplus f(x)\rangle\)

so that the sums above are relevant:

\(U_f U_f (|x\rangle \otimes |y\rangle)\)

= { by application of \(U_f\) }

\(U_f (|x\rangle \otimes |y \oplus f(x)\rangle)\)

= { by application of \(U_f\) again }

\(|x\rangle \otimes |[y \oplus f(x)] \oplus f(x)\rangle\).

We’re done.

More on reversibility

The requirement that gates are reversible is often described by saying that quantum algorithms change the state of qubits using unitary transformations. A matrix \(U\) representing such a transformation is unitary if and only if \(U U^\dagger = I\), where \(I\) is the identity matrix and \(U^\dagger\) is the conjugate transpose of \(U\) (see Adedoyin et al., 2022). If the elements of \(U\) don’t have any imaginary parts then \(U^\dagger\) is just the transpose of \(U\).

Let’s try it for the most complicated (relatively speaking!) function from the Deutsch problem, \(U_{f_2}\):

As we saw, this is represented by the following matrix:

\(U_{f_2} = \mbox{CNOT} (I \otimes X) = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

Is it unitary?

\(U_{f_2} U_{f_2}^\dagger\)

=

\(\begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

=

\(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

=

\(I\).

Yes.

References

Feynman, R. P. (1985). Quantum mechanical computers. Optics News, 11(2), 11–20.

Mermin, N. D. (2007). Quantum computer science: an introduction. Cambridge University Press.

J., A., Adedoyin, A., Ambrosiano, J., Anisimov, P., Casper, W., Chennupati, G., Coffrin, C., Djidjev, H., Gunter, D., Karra, S., Lemons, N., Lin, S., Malyzhenkov, A., Mascarenas, D., Mniszewski, S., Nadiga, B., O’Malley, D., Oyen, D., Pakin, S., … Lokhov, A. Y. (2022). Quantum Algorithm Implementations for Beginners. ACM Transactions on Quantum Computing, 3(4), 1–92.

IBM Quantum ibmq_quito runs of the Deutsch algorithm

 

The Deutsch algorithm decides whether a function \(f : \{0, 1\} \rightarrow \{0, 1\}\) is constant (\(f(0) = f(1)\)) or balanced (for this problem, \(f(0) \ne f(1)\), but see also the Deutsch–Jozsa algorithm).

There are four possible functions, \(f_i\), as follows:

Function \(f_i(0)\) \(f_i(1)\) Type
\(f_0\) 0 0 Constant
\(f_1\) 0 1 Balanced
\(f_2\) 1 0 Balanced
\(f_3\) 1 1 Constant

Classically, we would need to query \(f\) twice to decide whether an unknown function is constant or balanced. The quantum algorithm uses superposition to get the answer in one query.

I worked through the sums and circuit notation in this post. Below, circuits for running the algorithm for each of the four functions on one of IBM Quantum‘s quantum computers, ibmq_quito. I ran each 1,000 times to see how often an actual quantum computer(!) gets the right answer. I’ve also pasted in the Python code, which was generated automatically, and can be used to setup the circuits again.

The measurement outcome should be 1 for a constant function and 0 for a balanced function. As you can see, the modal answer across runs is correct, but there is a bit of noise.

f0 (constant)

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_q = QuantumRegister(2, 'q')
creg_c = ClassicalRegister(1, 'c')
circuit = QuantumCircuit(qreg_q, creg_c)
circuit.reset(qreg_q[0])
circuit.reset(qreg_q[1])
circuit.x(qreg_q[0])
circuit.x(qreg_q[1])
circuit.h(qreg_q[0])
circuit.h(qreg_q[1])
circuit.h(qreg_q[0])
circuit.measure(qreg_q[0], creg_c[0])
# @columns [0,0,1,1,2,2,3,4]

f1 (balanced)

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_q = QuantumRegister(2, 'q')
creg_c = ClassicalRegister(1, 'c')
circuit = QuantumCircuit(qreg_q, creg_c)
circuit.reset(qreg_q[0])
circuit.reset(qreg_q[1])
circuit.x(qreg_q[0])
circuit.x(qreg_q[1])
circuit.h(qreg_q[0])
circuit.h(qreg_q[1])
circuit.cx(qreg_q[0], qreg_q[1])
circuit.h(qreg_q[0])
circuit.measure(qreg_q[0], creg_c[0])
# @columns [0,0,1,1,2,2,3,4,5]

f2 (balanced)

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_q = QuantumRegister(2, 'q')
creg_c = ClassicalRegister(1, 'c')
circuit = QuantumCircuit(qreg_q, creg_c)
circuit.reset(qreg_q[0])
circuit.reset(qreg_q[1])
circuit.x(qreg_q[0])
circuit.x(qreg_q[1])
circuit.h(qreg_q[0])
circuit.h(qreg_q[1])
circuit.x(qreg_q[1])
circuit.cx(qreg_q[0], qreg_q[1])
circuit.h(qreg_q[0])
circuit.measure(qreg_q[0], creg_c[0])
# @columns [0,0,1,1,2,2,3,4,5,6]

f3 (balanced)

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_q = QuantumRegister(2, 'q')
creg_c = ClassicalRegister(1, 'c')
circuit = QuantumCircuit(qreg_q, creg_c)
circuit.reset(qreg_q[0])
circuit.reset(qreg_q[1])
circuit.x(qreg_q[0])
circuit.x(qreg_q[1])
circuit.h(qreg_q[0])
circuit.h(qreg_q[1])
circuit.x(qreg_q[1])
circuit.h(qreg_q[0])
circuit.measure(qreg_q[0], creg_c[0])
# @columns [0,0,1,1,2,2,3,4,5]

First time running a quantum circuit

This eve I clicked a few things, pieced together a simple quantum computing circuit and ran it on a quantum computer – an actual quantum computer(!), IBM Quantum’s ibm_nairobi.

Here’s the circuit, the Deutsch algorithm with \(U_{f_2}\) slotted in as the function to test. Pretend you can’t see what function it is – the result of the algorithm will tell us (something about) which it is.

In hindsight, I could have simplified it…

Wait a bit…

Then finally, a result!

The zeroth bit (least significant bit) is (almost always) zero, so the function is balanced.

 

The arithmetic of the Deutsch algorithm

The Deutsch algorithm (named after its originator David Deutsch) is a vivid and simple illustration of the power of quantum computing. Beyond achieving this admirable goal, it has no practical purpose, though it does seem to have inspired more useful algorithms. This blog post works through the arithmetic to show that the algorithm works (I did the sums to convince myself as I couldn’t grasp what was going on in Dirac notation). I don’t attempt to explain why it works.

The problem

Here’s the problem the Deutsch algorithm solves.

Suppose you are presented with a function \(f : \{0, 1\} \rightarrow \{0, 1\}\). You don’t know how \(f\) is defined, but you can call it with a \(0\) or a \(1\) and see what result it gives. The result will always be a \(0\) or a \(1\).

Your task is to decide whether or not \(f\) is constant, that is, \(f(0) = f(1)\). If \(f\) isn’t constant, it is said to be balanced since for one input the answer is \(0\) and for the other it is \(1\).

There are four possible functions, \(f_i\), as follows:

Function \(f_i(0)\) \(f_i(1)\) Type
\(f_0\) 0 0 Constant
\(f_1\) 0 1 Balanced
\(f_2\) 1 0 Balanced
\(f_3\) 1 1 Constant

Classically, to distinguish between the constant and balanced functions we would simply call \(f(0)\) and \(f(1)\), look at the results, and see which function it is. The Deutsch quantum algorithm can distinguish between a constant and balanced function by calling the function only once. It can’t tell us which function it is, just whether it is constant or balanced.

The circuit

Here is the circuit that solves it (diagram mildly simplified from Alice Flarend and Bob Hilborn, 2022, Fig 11.3, p. 163):

The gate \(U_f\) is a representation of the unknown function, \(H\) is the Hadamard gate (named after Jacques Hadamard), and \(M\) is measurement. Let’s work through the arithmetic. I’ll start with the easy bits at the input and output before tackling \(U_f\) in the middle.

The inputs

To get it going, first we need to apply \(H\) to the basis state \(|1\rangle\).

\(\displaystyle H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\),

\(\displaystyle |1\rangle = \begin{bmatrix} 0 \\ 1  \end{bmatrix}\), so

\(\displaystyle H|1\rangle = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1  \end{bmatrix}\).

Next, since the circuit starts with two qubits both in the state \(H|1\rangle\), we need to calculate the tensor product \(H|1\rangle \otimes H|1\rangle\):

\(\displaystyle H|1\rangle \otimes H|1\rangle = \frac{1}{2} \begin{bmatrix} 1 \\ -1 \\ -1 \\ 1  \end{bmatrix}\).

In ket notation, and reading top to the bottom of the column matrix, this is equivalent to:

\(\displaystyle \frac{1}{2}|00\rangle-\frac{1}{2}|01\rangle-\frac{1}{2}|10\rangle+\frac{1}{2}|11\rangle\).

\(|00\rangle\) means the inputs (reading the circuit top to bottom) were \(0\) and \(0\), \(|01\rangle\) means \(0\) and \(1\), and so on.

This pair of qubits is in superposition. If we measured after this step, then each of the four input possibilities would be observed with equal probability. (Use Born’s rule to square the state magnitudes; each is \(1/4\).)

The output

After the \(U_f\) magic happens (next section), we undo the Hadamard on the top path (register) of the circuit. Another tensor product gives us the appropriate matrix, this time of Hadamard and the identity matrix, \(I\), defined:

\(\displaystyle I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\).

So, \(\displaystyle H \otimes I = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{bmatrix}\).

The middle

Now we are left with the four implementations of \(U_f\), the overall structure of which is as follows (Mermin, 2007, p. 42):

Note that the first input, \(|x\rangle\) to the gate remains unchanged by the output and the second out is the exclusive-OR (XOR) of \(y\) and \(f(x)\). (In a future blog post I explain why this helps.) Here are the sums for each \(U_f\) (the pictures are from Mermin, 2007, p. 42; I did the ‘rithmetic):

\(U_{f_0}\):

This is the easiest – it’s just the identity matrix. In the spirit of how we typically create a product of inputs, this is the following tensor product:

\(\displaystyle U_{f_0} = I \otimes I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\),

the structure of which pleases me for some reason (how the \(4 \times 4\) identity matrix has a couple of \(2 \times 2\) identity matrices in top-left and bottom-right corners, and how \(\otimes\) makes it happen!).

\(U_{f_1}\):

This is the controlled NOT gate:

\(U_{f_1} = \mbox{CNOT} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\).

\(U_{f_2}\):

This takes the NOT (a.k.a. \(X\)) of the second input and then applies CNOT to both inputs. Let’s take the first step first:

\(I \otimes X = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\).

(This is mildly pleasing: note the \(2 \times 2\) NOT gate at the top left and bottom right.)

Now multiply CNOT by it:

\(U_{f_2} = \mbox{CNOT} (I \otimes X) = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

\(U_{f_3}\):

Another easier one: just NOT the second input, so we need \(I \otimes X\) and we already calculated it above:

\(U_{f_3} = I \otimes X = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\).

Gluing it all together

Now the fun bit in a big table. Let

\(\mbox{Inp} = H|1\rangle \otimes H|1\rangle\) and
\(\mbox{Undo} = H \otimes I\).

That is, \(\mbox{Inp}\) is the input and \(\mbox{Undo}\) is the step in the Deutsch circuit before measurement which applies the Hadamard gate.

Function \(\mbox{Inp}\ U_{f_i}\) \(\mbox{Inp}\ U_{f_i}\ \mbox{Undo}\)
\(f_0\)
(constant)		 \(\displaystyle \frac{1}{2} \begin{bmatrix} 1 \\ -1 \\ -1 \\ 1  \end{bmatrix}\) \(\displaystyle \frac{1}{\sqrt{2}} \begin{bmatrix} 0 \\ 0 \\ 1 \\ -1  \end{bmatrix}\)
\(f_1\)
(balanced)		 \(\displaystyle \frac{1}{2} \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1  \end{bmatrix}\) \(\displaystyle \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \\ 0 \\ 0  \end{bmatrix}\)
\(f_2\)
(balanced)		 \(\displaystyle \frac{1}{2} \begin{bmatrix} -1 \\ 1 \\ -1 \\ 1  \end{bmatrix}\) \(\displaystyle \frac{1}{\sqrt{2}} \begin{bmatrix} -1 \\ 1 \\ 0 \\ 0  \end{bmatrix}\)
\(f_3\)
(constant)		 \(\displaystyle \frac{1}{2} \begin{bmatrix} -1 \\ 1 \\ 1 \\ -1  \end{bmatrix}\) \(\displaystyle \frac{1}{\sqrt{2}} \begin{bmatrix} 0 \\ 0 \\ -1 \\ 1  \end{bmatrix}\)

To see what we would measure, use Born’s rule and square the amplitudes. This gives the following probabilities for each qubit pair:

\(P(|00\rangle)\) \(P(|01\rangle)\) \(P(|10\rangle)\) \(P(|11\rangle)\)
\(f_0\)
(constant)		 \(0\) \(0\) \(\frac{1}{2}\) \(\frac{1}{2}\)
\(f_1\)
(balanced)		 \(\frac{1}{2}\) \(\frac{1}{2}\) \(0\) \(0\)
\(f_2\)
(balanced)		 \(\frac{1}{2}\) \(\frac{1}{2}\) \(0\) \(0\)
\(f_3\)
(constant)		 \(0\) \(0\) \(\frac{1}{2}\) \(\frac{1}{2}\)

If the function is constant, the probability that the first qubit is a \(1\), which I’ll write \(P(|1\_\rangle)\), is:

\(\displaystyle P(|1\_\rangle) = P(|10\rangle) + P(|11\rangle) = \frac{1}{2} + \frac{1}{2} = 1\).

We observe either \(|10\rangle\) or \(|11\rangle\) with equal probability but the first qubit is always \(1\).

If the function is balanced, the probability that the first qubit is a \(0\) is:

\(\displaystyle P(|0\_\rangle) = P(|00\rangle) + P(|01\rangle) = \frac{1}{2} + \frac{1}{2} = 1\).

For this possibility, we observe either \(|00\rangle\) or \(|01\rangle\) with equal probability but the first qubit is always a \(0\).

It worked! Looking at this first qubit tells us whether the function was constant or balanced. The second qubit has a 50-50 chance of being a \(1\) or \(0\) so doesn’t tell us anything helpful.

See this post for the output when I ran the algorithm on an actual quantum computer, ibmq_quito.

But why does it work?!

As I mentioned at the outset, I am not going to attempt to explain why it works, but Mermin’s (2007, p. 41) potted history of the algorithm may be of interest:

“Deutsch’s problem is the simplest example of a quantum tradeoff that sacrifices particular information to acquire relational information. A crude version of it appeared in a 1985 paper by David Deutsch that, together with a 1982 paper by Richard Feynman, launched the whole field. In that early version the trick could be executed successfully only half the time. It took a while for people to realize that the trick could be accomplished every single time.”

References

Flarend, A., & Hilborn, B. (2022). Quantum computing: from Alice to Bob. Oxford University Press.

Mermin, N. D. (2007). Quantum computer science: an introduction. Cambridge University Press.