Tag: computer science

Experiments to protect against harvest now, decrypt later

Quantum computing needs thousands of qubits to crack the public key encryption we currently rely on and at present the largest (publicly announced) quantum computer only has 433 qubits. The sales pitch for protecting against quantum attacks now is that baddies could be quietly harvesting encrypted data, so that when quantum computers are ready, off they go and decrypt.

There are two main approaches to protect against quantum attacks.

One approach, quantum encryption key distribution (QKD), can be implemented one qubit at a time, e.g., by sending photons along fibre optic cables. Each photon is a realisation of a qubit. HSBC is trialling a QKD approach developed by BT and Toshiba, which builds on BB84 from forty years ago. I’ve attempted to explain BB84 in a previous blog post.

Vodafone has opted for a non-quantum approach to defend against attacks on crypto by trialling new public key encryption algorithms, on classical computers, that are thought to be quantum-safe: post-quantum cryptography (PQC).

The next major revision of Google Chrome will include a hybrid approach combining X25519 , a standard method already used by Chrome and others browsers, with Kyber-768, a PQC method that has so far resisted attack.

Since PQC methods are new, the hybrid approach offers protection while the maths continues to be stress-tested. This is important since there has already been an embarrassingly quick crack of a supposedly quantum-safe approach.

A survey of impossibility results in computer science and neighbours (Brcic & Yampolskiy, in press)

Abstract:

An impossibility theorem demonstrates that a particular problem or set of problems cannot be solved as described in the claim. Such theorems put limits on what is possible to do concerning artificial intelligence, especially the super-intelligent one. As such, these results serve as guidelines, reminders, and warnings to AI safety, AI policy, and governance researchers. These might enable solutions to some long-standing questions in the form of formalizing theories in the framework of constraint satisfaction without committing to one option. We strongly believe this to be the most prudent approach to long-term AI safety initiatives. In this paper, we have categorized impossibility theorems applicable to AI into five mechanism-based categories: deduction, indistinguishability, induction, tradeoffs, and intractability. We found that certain theorems are too specific or have implicit assumptions that limit application. Also, we added new results (theorems) such as the unfairness of explainability, the first explainability-related result in the induction category. The remaining results deal with misalignment between the clones and put a limit to the self-awareness of agents. We concluded that deductive impossibilities deny 100%-guarantees for security. In the end, we give some ideas that hold potential in explainability, controllability, value alignment, ethics, and group decision-making.

References

Brcic, M., & Yampolskiy, R. V. (in press). Impossibility Results in AI: A Survey. ACM Computing Surveys.

Writing a song “is an act of self-murder”: Nick Cave on ChatGPT

The best part of Nick Cave’s critique of ChatGPT is, IMHO, the following:

“Songs arise out of suffering, by which I mean they are predicated upon the complex, internal human struggle of creation and, well, as far as I know, algorithms don’t feel.”

A close second:

“Writing a good song is not mimicry, or replication, or pastiche, it is the opposite. It is an act of self-murder that destroys all one has strived to produce in the past.”

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.