OrACu: Quantum adiabatic computer: performance on Np problems

Project Summary

Quantum theory, first introduced by Max Planck more than a century ago, has provided the theoretical underpinning for perhaps the greatest technological revolution in human history. This theory has enabled the development of many of the devices used today in computing, the invention of the laser and many of the advances in chemistry of the last century. Even so, it is likely that quantum mechanics is still capable of generating a new technological revolution in the near future.

Specifically, quantum computing seeks to exploit certain properties of quantum mechanics, with no analogue in the world around us, to solve computational problems that are currently unsolvable. The famous Schrödinger’s cat paradox can serve to roughly explain the computational power behind quantum theory. This paradox stipulates that a cat, behaving according to quantum laws, could be in a superposition of two states: alive and dead at the same time. Quantum computing uses a many-state superposition to find the solution to difficult problems.

Building a quantum computer is by no means an easy task. On the one hand, there are technical problems because quantum laws only appear in very small systems and any source of noise seriously impairs a quantum calculation. On the other hand, theoretical problems arise from the difficulty of characterising quantum systems composed of many interacting parts. These theoretical problems appear specifically in the development of a type of quantum processors known as quantum adiabatic computers. This does not prevent such processors from raising a great deal of interest as they can provide an alternative way to attack particularly difficult problems, known as Np-complete problems, for which the performance of our everyday computers is poor.

Np-complete problems appear in sectors with technological relevance, such as artificial intelligence and complex optimisation problems. Achieving even a small improvement in the resolution of these problems could result in substantial savings. For example, let us consider a home delivery company. Calculating the optimal delivery truck route is a problem closely related to Np-complete (Np-hard) problems. Route design is easy when there are few orders to deliver but can be incredibly difficult if the number of customers increases. Thus, the improvement in the design of delivery routes that a quantum computer can achieve could translate into significant fuel savings and a reduction in pollutant gas emissions. The possibility of tackling Np-complete problems has led several technology firms to put great interest in quantum adiabatic computing. Due to this demand, the company D-wave has begun to commercialise computers of this kind in recent years (the figure shows one of the chips from D-wave

Application: This project aims to characterise and propose improvements to the performance of a type of processor based on quantum adiabatic computing.  Despite the expectations that this type of computing (based on the adiabatic theorem) has raised, the optimal performance that this type of machine can achieve is unknown. Answering this question is key, not only for the immediate future of quantum technologies, but also for technological sectors such as artificial intelligence or cybersecurity.