As the first quantum computers (composed of few qubits) are already a reality, the natural question arises: what kind of problems can they solve?
Or in other words, what kind of computational power does quantum computing give us? Arjan Cornelissen defended his PhD thesis on Friday 17th February 2023 whose research questions revolve around this topic.
While future quantum computers will in principle be able to perform any computation that classical computers can, in some cases they will be able to significantly outperform their classical counterparts. Arjan worked on two kinds of computational tools where this is the case: sampling algorithms and algorithms that solve decision problems.
In sampling algorithms, randomness is classically used as a tool to simulate processes with uncertainty (financial markets for example), such that subsequent predictions can be obtained from these simulations. Quantum algorithms, on the other hand, operate on quantum states, and in doing so can perform simulations in a “coherent superposition”, meaning that a quantum algorithm can spread out its attention to many possible options, with a tiny amount devoted to each of them. However, recombining the individual partial results from such coherent superposition to obtain predictions about the underlying random process (e.g., the stock market) is an inherently difficult problem. Arjan developed algorithms which extract the relevant information from quantum states, and showed that this can theoretically be used to make predictions more efficiently than is possible on present-day computational hardware.
On the other hand, decision problems are those that result in a “yes or no” answer. There exist several frameworks that allow for the design of quantum algorithms that solve these decision problems. Arjan developed a geometrical description of one of these frameworks, referred to as the “span program framework”. The core intuitive insight is that quantum algorithm designed using this framework can be interpreted as gyroscopes that either spin horizontally, or at an angle, providing novel insights into the inner workings of the algorithm.
He remains interested to reach a better understanding of the computational power of quantum computing, and in the future would like to advise people about solving specific problems by means of a quantum computer. Additionally, one of the potential long-term applications of Arjan’s research is the development of debugging software for quantum algorithms. He currently proceeds to research these topics as a PostDoc in Paris.
Arjan Cornelissen conducted his PhD research in the group of Maris Ozols. The research was funded by the University of Amsterdam and was carried out at QuSoft and CWI.
