Quantum Programming 101

2016-12-11 - Programming, Mathematics

Latest revision: 2024-08-20

Are you familiar with programming, but know absolutely nothing about quantum mechanics?

This was exactly my case when the IBM Quantum Experience was announced. For the first time, a quantum computer has been made publicly available, and anybody selected to participate could send programs to it.

I applied. I was selected. And then I had a really rough time attempting to decipher the user guide of the IBM 5Q quantum computer I had access to. The IBM staff tried to ease the learning curve, but I felt that the documentation made a lot of assumptions that a non-physicist do not have, and "intuitive" ideas presented to me (like the Bloch sphere) just confused me even more.

Therefore, I decided to compile below a generic introduction on quantum programming designed for classical programmers to ease their learning curve. I hope it will be useful to you and anybody else you share it to.

Be warned however that quantum programming requires some pretty advanced mathematical knowledge, but as long as you're familiar with probability, binary numbers, complex numbers and linear algebra, you should be fine.

Are you ready? Let's go!

Meet the qubit

The qubit is an extension of the bit. Just like the bit, it returns a value of 0 or 1 when read, and the returned value doesn't change when read multiple times consecutively.

Unlike the bit however, the qubit does not simply store a value of 0 or 1. In fact, its internals cannot be well-defined, as its output is in general dependent on global factors which cannot be fully known. For example, when qubits interact with each other, they may become entangled in a way which causes an operation on one to affect the output of the other regardless of the physical distance between them.

What is possible however is to determine the probability of a qubit returning 0 or 1 based on our partial knowledge of it and all the other qubits it has interacted with during previous operations.

Note that a qubit not guaranteed to return a specific value is said to be in a superposition state.

Probability amplitudes

A probability amplitude is a complex number directly linked to a possible qubits' output combination. The probability of reading a specific output combination is equal to the square of the absolute value of its probability amplitude.

Therefore, the known state of an entire set of qubits can be stored as a vector of all probability amplitudes of this set. By convention, this vector is a column vector ordered from lowest to highest possible binary outputs. Such a vector is called a quantum state.

Here is an example of a quantum state of 2 entangled qubits, along with its output probabilities:

\begin{matrix} [\begin{matrix} a_{0, 0} \\ a_{0, 1} \\ a_{1, 0} \\ a_{1, 1} \end{matrix}] = [\begin{matrix} \frac{i}{\sqrt{2}} \\ 0 \\ 0 \\ \frac{- i}{\sqrt{2}} \end{matrix}] \\ P (0, 0) = {| a_{0, 0} |}^{2} = {| \frac{i}{\sqrt{2}} |}^{2} = \frac{1}{2} \\ P (0, 1) = {| a_{0, 1} |}^{2} = {| 0 |}^{2} = 0 \\ P (1, 0) = {| a_{1, 0} |}^{2} = {| 0 |}^{2} = 0 \\ P (1, 1) = {| a_{1, 1} |}^{2} = {| \frac{- i}{\sqrt{2}} |}^{2} = \frac{1}{2} \end{matrix}

Initial state

A standard quantum computer initializes its qubits as independent quantum states with probability amplitudes of 1 for returning 0 and 0 for returning 1:

[\begin{matrix} 1 \\ 0 \end{matrix}]

This effectively causes all qubits to always return 0 if immediately read.

System scaling

Quantum states can be combined as a single quantum state in order to operate on qubits between them. This is done by calculating the Kronecker product of the quantum states:

[\begin{matrix} 1 \\ 0 \end{matrix}] \otimes [\begin{matrix} 1 \\ 0 \end{matrix}] = [\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix}]

Note that two groups of different qubits sharing a quantum state are entangled if and only if they cannot be described as independent quantum states.

Quantum gates

While classical computers uses logic gates to operate on bits, quantum computers uses quantum gates to operate on qubits. A quantum gate can be represented as a unitary matrix of side length of 2 to the power of the number of qubits it operates on.

The effect of a quantum gate is calculated by multiplying the quantum gate matrix with the quantum state of the qubit set going through it. The result is a new quantum state.

Here is an example of a 1-qubit quantum gate applied on an initial quantum state to make it always return 1:

\begin{matrix} 𝑿 = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] \\ 𝑿 [\begin{matrix} 1 \\ 0 \end{matrix}] = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} 1 \\ 0 \end{matrix}] = [\begin{matrix} 0 \\ 1 \end{matrix}] \end{matrix}

In the case where a quantum gate operates on a subset of the total number of entangled qubits, the Kronecker product can again be used to expand the quantum gate matrix with a 2 by 2 identity matrix per qubit. This allows quantum computers to execute some programs significantly faster on average than what is possible on classical computers, since the execution time to apply a specific quantum gate instruction is constant.

For example, here is a 2-qubit quantum gate that reverses the least significant qubit's output only if the most significant qubit would return 1. It is expanded as a 3-qubit operator in a way that applies the gate on the two most significant qubits. It is then applied on a quantum state that always returns 100 to make it always return 110 instead:

\begin{matrix} 𝑪𝑵𝑶𝑻 = [\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}] \\ (𝑪𝑵𝑶𝑻 \otimes 𝑰_{2}) [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}] = ([\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}] \otimes [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}]) [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}] = [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{matrix}] \end{matrix}

Note that a quantum gate's matrix may require a change of basis (through standard linear algebra) if the order of qubits we want to operate on do not match those of the quantum state. This also applies for expanded quantum gate matrices.

Programming

After considering the limitations of the architecture of the quantum computer used, the only thing left is to write a desired quantum program in a compatible programming language, just like any classical program,

Here is an example of a program written in IBM's QASM assembly language:

//IBMQASM 1.1
qreg q,5;
gate h, [[0.7071067811865476,0.7071067811865476],[0.7071067811865476,-0.7071067811865476]];
gate cx, [[1,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,1,0]];
h q[1];
cx q[1], q[2];
measure q[1];
measure q[2];

This example sets two qubits in a popular quantum state (the Bell state) before measuring them. The expected output is 00 with ½ probability and 11 with ½ probability.

Hardware errors

One major problem in current quantum computers is the instability of qubits, and the process of error injections in a quantum state is called decoherence. In addition, qubit measurement devices also have error biases as well.

Until technology is perfected to reduce these errors to a trivial level, a quantum programmer should take into consideration error probabilities of the computer's architecture, and apply error correction algorithms to its programs when necessary.

Describing a mixed state of probabilities due to these error sources can be done with a density matrix, which is out of scope of this post.

To be continued?

I hope that my explanation was clear enough for you to be able to design your own quantum programs. Quantum programming is a young science so there's still plenty to discover, but you may want to look at some existing quantum algorithms for inspiration.

Special thanks to the entire IBM Quantum staff for introducing me to quantum computers and answering my technical questions!

Bonus content!

Dagger symbol

In quantum physics literature, the dagger symbol is often used to represent the conjugate transpose of a matrix:

𝑨^{†} = {\overline{𝑨}}^{T}

bra-ket notation

During my research, I often stumbled on quantum states defined in bra-ket notation. Here is what you should know if you would like to read other sources on the subject.

By definition, a ket is written in the form $| x ⟩$ where $x$ is an arbitrary label, and represents a column vector in complex space.

Similarly, a bra is written in the form $⟨ x |$ and represents the conjugate transpose of the corresponding ket:

⟨ x | = {| x ⟩}^{†}

Also by definition:

\begin{matrix} ⟨ x | y ⟩ = ⟨ x | | y ⟩ \\ | x ⟩ | y ⟩ = | x ⟩ \otimes | y ⟩ \\ | x y ⟩ = | x ⟩ \otimes | y ⟩ \end{matrix}

One big advantage of this notation is to be able to perform the following decomposition of any quantum state, which can help designing and analyzing programs:

[\begin{matrix} a_{0, \dots, 0, 0, 0} \\ a_{0, \dots, 0, 0, 1} \\ a_{0, \dots, 0, 1, 0} \\ a_{0, \dots, 0, 1, 1} \\ ⋮ \\ a_{1, \dots, 1, 1, 1} \end{matrix}] = \sum_{k} a_{k} | k ⟩

Here are some common ket constants:

\begin{matrix} | 0 ⟩ = [\begin{matrix} 1 \\ 0 \end{matrix}] \\ | 1 ⟩ = [\begin{matrix} 0 \\ 1 \end{matrix}] \\ | + ⟩ = \frac{1}{\sqrt{2}} [\begin{matrix} 1 \\ 1 \end{matrix}] \\ | - ⟩ = \frac{1}{\sqrt{2}} [\begin{matrix} 1 \\ - 1 \end{matrix}] \\ | +i ⟩ = \frac{1}{\sqrt{2}} [\begin{matrix} 1 \\ i \end{matrix}] \\ | −i ⟩ = \frac{1}{\sqrt{2}} [\begin{matrix} 1 \\ - i \end{matrix}] \end{matrix}

Useful quantum gates

Wikipedia offers a comprehensive list of named quantum games.

You may also want to refer to the full list of quantum gates supported by the IBM Quantum Experience.

A Technical Introducition to MathML Core for Writing Mathematics on the Web

2024-09-01 - Programming, Mathematics

Thanks to recent efforts, all major web browsers currently support MathML Core, a subset of MathML focused on important presentation markup, to support mathematics on the web. As of this writing, the MathML Core specifications are still not finalized, but given its strong origins and support, it can…

The New Open Source Video Game Randomizer List Is Now Live

2024-08-02 - Video Games, Programming

Time to update your bookmarks! After a few months of work behind the scenes, the new open source version of The BIG List of Video Game Randomizer is now live for your enjoyment, with dark mode support and a brand new UI for better readability! The new URL is: https://randomizers.debigare.com/ (The…

Open treasure chest with a question mark in it

The Future of the Video Game Randomizer List

2024-05-13 - Video Games, Programming, Anecdotes

It's hard to believe that it's been almost 8 years since I first posted on the ROMhacking.net forums a list of video game randomizers that I found online, and that it would evolve into the massive project it has become today, with almost 900 entries currently being listed. It's always a strange…

Dice stacked in a triangle shape, with their face numbers matching their row position

I Designed the Perfect Gambling Game, But...

2023-11-27 - Mathematics, Business, Game Design

Back in 2006-07-08, during the 13th Canadian Undergraduate Mathematics Conference at McGill University, I presented a gambling game I designed with the novel property of being both advantageous to players and the house, and that despite this proprety, that pretty much nobody in their right mind…

Minifying JSON Text Beyond Whitespace

2023-08-27 - Programming, Mathematics

JSON is a common data serialization format to transmit information over the Internet. However, as I mentioned in a previous article, it's far from optimal. Nevertheless, due to business requirements, producing data in this format may be necessary. I won't go into the details as to how one could…

See all of my articles