New paths in the quest for quantum computational advantage

Quantum computers make use of the laws of quantum physics in order to solve computational tasks. This differs from conventional digital computers (that is, essentially all computers used in current technology), which make use of the laws of classical physics only. There is hope that quantum computers can be vastly more powerful than digital computers at solving certain computational tasks, and as a result recent years have seen a surge in interest and investment in quantum computing. There are now a large number of both start-up companies and tech giants (including IBM, Google and Microsoft) pursuing the possibility of developing scalable quantum computers, although the technology is still in its infancy. Theorists working in the field of quantum computing have two challenges: (i) find ways to use these quantum computers to solve useful computational problems, that go beyond the capabilities of digital computers; and (ii) construct mathematical proofs that confirm the superiority of quantum computers for these tasks. This research tackles both of these challenges. Regarding (i), the focus is on a type of quantum algorithm called a variational quantum algorithm. The types of quantum computers which run these algorithms are often called quantum neural networks, because in order to solve the computational problem, the controls of the quantum computers are optimised in a way analogous to optimising the weights of a neural network. As a result, variational quantum algorithms also have strong connections to techniques in the nascent field of quantum machine learning. Unlike neural networks, for which many optimisation techniques are known, very little is known about the best way to optimise quantum neural networks however. This proposal makes progress in this challenge by investigating a number of new techniques to this end. This involves leveraging ideas from classical optimisation (see graduated optimisation) as well as designing new techniques that exploit the quantum nature of the problem. Finding the mathematical proofs needed for point (ii) is notoriously difficult, and theorists nearly always have to rely on unproven (but widely believed to be true) conjectures in order to arrive at a proof. An exception to this rule was recently shown (see for example https://science.sciencemag.org/content/362/6412/308). Here, the authors show that an effect called Bell nonlocality allows quantum computers to outperform digital computers at some tasks, without any further assumptions. This part of the project will leverage the principle investigators expertise in Bell nonlocality to strengthen and clarify this connection, and find new examples of quantum computational advantages that step from this phenomenon. Ultimately this will bring new insight into the reasons why quantum computers are stronger than their classical digital counterparts.