Quantum computing offers solutions to deal with very large data sets by applying nature’s laws to programming. Games are a playful way to enthuse especially young students to tackle tomorrow’s problems as results can be seen quickly. The game “Battleships with partial NOT gates” teaches principles of quantum mechanics and “Nine Quantum’s Morris” – the quantum computing version of the board game “Nine Men’s Morris” – introduces the programmer to tensor and graph neural networks, which are used in particle physics, for example particle track reconstruction.
The principle idea of the application of quantum computing is transferring well known processes in nature to programming. Although describing nature’s properties by the complicated mathematical theory of quantum mechanics is challenging, learning quantum computing is not particularly harder to learn than any other programming language. Most probably, the easiest way to get into quantum computing is programming games as progress is made fast and results can be seen almost immediately.
Basics of Quantum mechanics: Battleships with partial NOT gates
Many consider “Battleships with partial NOT gates” as particularly suited for learning the basic concepts of quantum mechanics and programming as the game offers an intuitive approach to quantum computing. The game itself is the quantum computing version of the board game battleships played on a Japanese board. In this version, a fleet also can be destroyed by a given percentage only and ships even can be immune to destruction. Originally designed for a five qubit machine, each point – a qubit – on the grid represents a place where the ships might be.
So, what’s a qubit?
Bits & qubits
The main difference between classical computing and quantum computing is qubits instead of classical bits, which can take only values of 0 and 1. Qubits (short for quantum bits) consist of so-called states |0> and |1> or – even more precisely – of weighted superpositions of these states. This fact allows to include much more information in a single qubit than would be possible in the classical case. Measuring a qubit means that a random choice is done, for which the probability of the outcome between the states |0> and |1> is given by the weights. Mapping the |0> and |1> states onto a sphere (the so-called Bloch-Sphere), they would correspond to the poles on the Z axis. The qubits are then given by a vector pointing to the surface of the sphere, for which the X and Y coordinate are given by the weight that was assigned before. Hence, the vectors have a maximum length of 1. A classical bit would be visualised by a single Z axis, in which the poles correspond to the values 0 and 1. In principle, it is possible to understand the qubit’s behaviour by knowing only two coordinates. “Battleships with partial NOT gates” applies so-called gates to the states, which are nothing more than coordinate transformations. The axes of the Bloch-Sphere correspond to either “destruction”, “immunity” or “attack” and the outcome of the measurement provides the status of the ship and fleet [1].
Nine Quantum’s Morris: One board, multiple applications in finance and physics
“Nine Quantum’s Morris” was developed as the quantum computing version of “Nine Men’s Morris” with a board based on the ATLAS detector geometry. Originally, it has been proposed as a challenge for CERN summer students at the CERN openlab Webfest 2019 and won the second prize [2]. The idea was followed-up in this year’s online Webfest due to its success, this time using quantum annealing and its underlying algorithm, which is also more and more used nowadays in both physics and finance.
Quantum annealing is used to solve optimisation problems by framing them as energy minimisation problems. Nature strives to minimise energy, which is the reason that the application of physics processes reflecting this behaviour solves the problems more or less automatically in a very elegant way. Quantum annealing itself is described by a thermodynamical process: The energy minimisation of the system is a result of a progressive temperature cooling, which in turn lets super-posed quantum states collapse into classical states. Another important aspect addressed by quantum annealing is the so-called probabilistic sampling, for which many low energy states are scanned and thus the shape of the energy function is charted.
A suitable underlying physics model describing these processes accurately is the Ising model, commonly used in lattice gauge theories. Its so-called Hamiltonian, an operator representing the energy of the system, is well adapted to the problem: The interaction term describes the coupling to edges and the term proportional to the magnetic field describes the weight of nodes and vertices. Lattice gauge theories are used as gauge theories of a discretised spacetime on a lattice in a non-perturbative description, such as QCD in particle physics. Therein, strong interaction evolves from one point to the next on the lattice following nature’s rules similarly to the men of Nine Men’s Morris, who follow the rules of the game. Both the lattice and the “Nine Men’s Morris” board have similar types of connections. The quantum annealing model application to quantised lattice gauge theories is referred to as “quantum link”.
Alternative approach to Quantum Annealing: Tensor Networks
Quantum graph neural networks offer another interesting alternative to describe the “Nine Quantum’s Morris” board. These belong to universal quantum gate models and can be rewritten as classical electrical circuits. Any new combination of circuits can be easily generated using quantum circuit operations, which leads to solutions of a wide range of problems – even more as for quantum annealing, in which only a limited set of problems can be examined.
After realizing “Nine Quantum’s Morris” using quantum gate operations, it has been shown by the collaboration between gluoNNet, CERN openlab and the Middle Technical East University of Ankara as well as researchers from Caltech and the University of Oxford that a Quantum Graph Neural Network is also successfully applicable to particle track reconstruction problems in physics. Experimental physicists expect a huge increase in the amount of data, in particular with the arrival of the High Luminosity LHC (HL-LHC). This might be even more the case with potential future projects, e.g. the Future Circular Collider. The HL-LHC will challenge existing machine learning algorithms used for particle track reconstruction.
Quantum graph neural network consists of an edge network and a node network applied iteratively. Both types of networks are expressed by quantum tensor networks. Simulations of these circuits are often done with the help of GPUs in order to achieve faster results [3]. The passage of particles through the detectors leading to a signal is reconstructed by the graph neural network. Graph neural networks measure the probability of a connection between two detector signals. Points are not necessarily connected between each other in graph neural networks unlike for so-called tensor neural networks, which only take the relevant information out of a model. This technique leads to a focus to the overall behaviour of a model, which is an efficient way to study complex systems such as quantum mechanical probability distributions.
[1] https://medium.com/qiskit/how-to-program-a-quantum-computer-982a9329ed02
[2] https://home.cern/news/news/knowledge-sharing/accessibility-projects-stand-out-webfest-
2019
[3] https://arxiv.org/abs/2007.06868, https://arxiv.org/abs/2012.01379