# Simple, complex, and linear: Exploring Quantum Lattice Gas Cellular Automata

##### About our guest author

**Niccolò Fonio** joined Quanscient Quantum Labs as a visiting PhD researcher from Aix-Marseille University in September. His research focuses on Quantum Lattice Gas Cellular Automata, applying his expertise in quantum computing and fluid dynamics. In this guest blog post, Niccolò shares his insights into this research area and his experience working with our team in Tampere, Finland.

### What is Lattice Gas Cellular Automata?

If I had to describe Lattice Gas Cellular Automata in three words, they would be: simple, complex, and linear. Let’s see how all these fit together.

Lattice gas cellular automata (LGCA) is a numerical method developed in the 80’s and it is tremendously simple. To wrap up a bit, we can start from a cellular automata.

- Take a line made of cells where each cell has a value 0 or 1
- At one time step each cell value gets updated depending on the values of its neighbors
- Go to the next time step

Super straightforward, isn’t it?

### Simple yet complex

This system became quite popular thanks to Conway’s “Game of life”, which aims to model a simple population dynamics.

However, this is a cellular automata, but what is then a Lattice gas cellular automata? The principle is the same but in each cell, there are more bits, and their value depends on the presence of particles with defined velocity. Cells are then placed in a lattice. For example, the string [n_0 n_1 n_2] represents the presence of particles with velocities [v_0 v_1 v_2].

Bits in the same cell represent particles *at the same point in space*. And what happens to moving particles at the same point in space? They collide! Thus, LGCA is a class of dynamical systems whose dynamic is composed of a collision step and a streaming step, when particles move according to their velocities, in a discretized space-time. To picture it, you can imagine an unusual billiard game, where balls (particles), can move only in definite directions.

If we have clarified why LGCA are (quite) *simple*, we can now say why they are also *complex*: and this is not a contradiction! I bumped into the concept of complex systems in the last year of my bachelor's. If you look it up, Wikipedia defines it as follows:*“A complex system is a system composed of many components which may interact with each other”*

We can also add a principal property: it shows emergent behavior. In this sense, we have several components that interact. The interaction can be easy, complicated, or unknown, but the important thing is that it gives place to some observable emergent phenomena. Be careful: complex does not mean complicated!

### My journey to Quantum LGCA

This has been a truly fascinating concept that I have always felt. That is why I decided to study Physics of complex systems at the University of Turin. Back then I did not know about LGCA, I was (and I am still) fascinated by quantum mechanics and black holes. Complexity is a key concept in several theoretical researches.

It was only during my master’s that I came in touch with quantum computing and quantum information: a very interesting topic, truly promising technology that is being developed nowadays and has the premise of being game-changing for our society. This brought me to do my master’s thesis at Aix-Marseille University, under the supervision of Pierre Sagaut and Giuseppe Di Molfetta, who proposed a topic I had never heard of before: Quantum lattice gas cellular automata for hydrodynamics.

### Why Quantum LGCA?

In the ‘80s Friesch, Hasslacher and Pomeau (FHP) discovered that the simple and complex billboard game we described above is capable of simulating a fluid if you impose some precise yet general rules, i.e. conservation laws. Specifically, it is capable of simulating Navier-Stokes-like equations. This was a big deal for that time, and signed a milestone in numerical physics because it was possible to simulate a fluid with a system that could be easily coded on a computer, that was parallelizable and gave rise to some crucial developments in CFD.

LGCA is the parent of the Lattice Boltzmann Method (about which there is another blog post here), which could be seen as its natural evolution for fixing some precise “bugs” of the system. LGCA did not reproduce, in fact, *exactly *the Navier-Stokes equations, and it had some unphysical features that, even if numerically tractable, persisted. However, while LBM is intrinsically non-linear and non-unitary, LGCA is *naturally linear*.

The microscopic behavior is, as we said, simple, it does not involve any known solution: the non-linearities emerge in the macroscopic behavior of the system. Here a light bulb lights up: Quantum computing is unitary, thus linear. Is it possible then to simulate an LGCA with a quantum computer? How does that work? Can it capture non-linearities? All foreseen gravid questions.

### Exponential advantage with quantum computing

It is very interesting to think about the possibilities of this algorithm because we could apply the methods of quantum computing to get an advantage. For example, two properties of a quantum mechanical/computing system are *superposition *and *quantum parallelism*.

These two together allow for an exponential advantage in the representation of the lattice for a LGCA. An exponential advantage means that where before we needed 10^{x} bits for representing our system, on a quantum computer we need “only” x log10. That is roughly the difference between one billion and 30, but also a thousand billion and 40, a billion billions and 60.

However, even if the lattice is representable the work is not done yet, and a lot of research is needed to truly capture the advantage of translating this classical algorithm with quantum computers. Luckily this is raising bigger and bigger interest in the scientific community.

### Researching Quantum LGCA at Quanscient

Fascinated by this research and after having obtained some first results, since the weather was pleasant in the south of France and there was the possibility, I embarked on the adventure of the PhD to study more in detail the applications of Quantum LGCA to Computational Fluid Dynamics.

It was during the first year of my PhD that I discovered Quanscient, and Quanscient discovered me. After a workshop together and some scientific discussions, I understood that this was the place where I could learn a lot and collaborate to unfold some important properties of these dynamical systems and their applications.

My research here then focuses on Quantum LGCA and their properties, so on how we can get the best LGCA for fluid dynamic simulations.

### Experiencing Finland and Quanscient

Another aspect that convinced me to collaborate is that I had never been to Finland! I have always been curious about different countries, and cultures, constantly fascinated by the beauty of diversity. I’ve lived in Italy, Belgium, and France and, principally, I do not mind living in cold weather. This is how I ended up writing this blog post from Tampere!

I discovered a sparkling environment, scientifically and from an entrepreneurial point of view. I am learning how research works in a startup, I am learning by sharing ideas with new colleagues every day, and I am learning really well how teamwork works in a company. It’s my first experience in a startup and I could not expect something better.

I also discovered that Finland is estimated to have more than two hundred thousand lakes and that 75% of the surface is covered in forests. So this just confirmed what I was expecting: you can breathe really good air and a promising future up here.