On 25 April 2018, CWI PhD student Srinivasan Arunachalam will defend his thesis at the University of Amsterdam. Arunachalam’s work revolves around the quantum computer, a new machine that will be capable of calculations that current computers can only dream of. In his thesis, Arunachalam analyzes the strengths and weaknesses of this new type of computers for a number of problems.
Quantum computers are devices that harness the power of quantum mechanics. Where conventional computers use bits which are either 0 or 1, quantum computers use qubits that can simultaneously be 0 and 1. This fundamental difference opens the door to unprecedented calculations.
In his thesis, Arunachalam considers two main topics. Firstly, he discusses quantum algorithms, i.e. algorithms that can run on quantum computers. Secondly, he discusses how quantum computers can help with machine learning, the field of computer science that allows computers to automatically learn from data, and act on their new knowledge, without being explicitly programmed.
Quantum algorithms
An important result of Arunachalam’s work on the topic of quantum algorithms is the characterization of quantum algorithms in terms of polynomials. Arunachalam developed a new technique for showing upper and lower bounds on the complexity measure of a class of quantum algorithms. This result could potentially lead to a new class of algorithms. It also connects a well-studied branch of mathematics (operator-space theory) with quantum algorithms. This connection could potentially resolve open questions in one field using tools from the other.
Arunachalam also developed a quantum alternative for an algorithm that finds the minimum of a function. A classical technique used for this purpose is the so-called gradient-descent method. Arunachalam’s quantum alternative is quadratically faster than this classical competitor.
Machine learning
Finally, Arunachalam put his quantum expertise to use in the field of machine learning. He considers ‘probably approximately correct learning’ (PAC), a 1980s framework for the mathematical analysis of machine learning. The core idea of PAC is that, when confronted with a data set, a model will not make a perfect prediction. However, it will be ‘approximately correct’ with a high probability. PAC gives us insight in what accuracy we can expect from the model given a certain data set size, or vice versa, how many data the model needs in order to reach a certain accuracy. In his thesis, Arunachalam challenges a ‘quantum’ machine learner to learn a concept from fewer data than its classical competitor. Arunachalam found that quantum examples are actually not more powerful than classical examples, both for PAC learning and for a more realistic model called agnostic learning. The result proves that quantum computers and quantum data will not always be useful for machine learning tasks.
More information
- PhD defence Srinivasan Arunachalam
