**Quantum computers are the Holy Grail of information theorists. For years, scientists have been trying to crack their mysteries, to harvest their interesting applications. They are predicted to have tremendous computational power, exponentially larger than the computers available today. However, so far, they have been difficult to actually build. Prof. Ashley Montanaro will investigate the path from the theoretical foundations of quantum computing their applications to real-life problems.**

One of the most famous truths in computer science is described by Moore's law: "*The number of transistors we are able to place on a microchip doubles every 18 months*". This empirical observation, formulated in the 70s by the co-founder of Intel Gordon Moore, still holds nowadays, and represents a good indicator of the tremendous computational development we have experienced in the past years. A higher density of transistors per chip, in facts, translates to a higher complexity - and power - of the processors. However, this situation is not going to last forever. Eventually, Moore's law is doomed to fail, due to the physical limits of miniaturisation and increasing costs to develop new generations of chips.

**The wonders of quantum mechanics**

Does this mean that we will have to deal with a cap in the computational power of the new generations of processors? Not necessarily. A promising technology to overcome the limitations of conventional devices is the Quantum computer. As the name suggests, this device would make use of the principles of quantum mechanics - the branch of physics dealing with very small objects, like subatomic particles. Research in quantum technologies is proceeding fast all over the world. Governments and companies are preparing the field for the so-called ‘second quantum revolution’, where we will be able to use new technologies based on quantum physics for commercial applications. The European Commission has planned to invest over 1 billion € in the next 10 years in quantum research through its Quantum flagship initiative.

Where classical processors work with "bits" - that can assume the two states 0 and 1 and represents the building blocks of information theory - quantum computers have "qubits", quantum-bits, simultaneously in both the states 0 and 1. In principle, this opens the possibility to engineer completely new algorithms to perform computations, in a way that classical bits cannot achieve. This means that quantum computers could revolutionise the possibilities of numerical simulations, deep learning, artificial intelligence and all those tasks that require tremendous computing power.

**From theory to applications**

Quantum computers seem to be a great technology, but, unfortunately, we are not there yet. Building large systems of qubits is extremely challenging. Up to now, despite the great number of institutional and commercial competitors in the field, only quantum computers with a small number of qubits have been produced. Going beyond a few tens of qubits is a challenge for the near future. Ashley Montanaro, from the University of Bristol, has received ERC funding to work on the foundational theory and the applications of quantum computing. “*Ten years ago researchers were still very sceptical about the realisation of a large-scale quantum computer. Now many scientists, including myself, are very confident that we will get there relatively soon, and it’s useful to prepare the field*” he says.

His first objective is to develop new theoretical quantum algorithms to tackle, in a more efficient way, real-life problems that are difficult to treat with classical processors. This involves establishing what problems are worth addressing, and realising new quantum algorithms for these problems. The second goal is to demonstrate formally to what extent quantum algorithms will represent an improvement on classical ones, the so-called quantum computational supremacy. Finally, he will work on new quantum algorithms for important questions in quantum physics, such as the characterisation of the properties of new molecules in material science.

Understanding the theoretical challenges and possibilities of this new technology is also important for realising what characteristics the future quantum computers should have, and it could help the researchers to identify the path that will finally lead to a large quantum computer, and to the enormous opportunities that it will bring.

**Biography**

**Ashley Montanaro** has worked in the field of quantum computing for 15 years, specialising in quantum algorithms and quantum computational complexity, and has published over 50 papers on this topic. He holds a PhD in quantum computing from the University of Bristol, supervised by Prof. Richard Jozsa, has been a postdoctoral fellow at the University of Cambridge, and is now Reader in Quantum Computation at Bristol. He held an EPSRC Early Career Research Fellowship from 2014 to 2019 and was awarded a Whitehead Prize in 2017 by the London Mathematical Society. He currently serves on the Steering Committee of the international conference on Quantum Information Processing (QIP), and as a Founding Editor of the journal Quantum. He is co-founder of Phasecraft, a quantum software startup, and is a founding consultant of Q&I, an organisation providing expert advice on quantum technologies to business.