“Are there limits to what computers are actually able to compute, and do quantum computers really solve more problems than conventional computers? Computer scientist Scott Aaronson will discuss these kinds of fundamental questions during the Paul Bernays Lectures 2019.
In 2007, an ad spot ran on Australian TV that involved two models in a dressing room discussing quantum mechanics. The two of them discuss how quantum mechanics is not physics in the usual sense; it’s not about matter, energy or waves, but about information, probabilities and observables.
The notable thing about this advertisement is not that two models have a casual conversation about theoretical physics, but that quantum mechanics is represented not only as an interesting research perspective for physics, but also for computer science. This scientific position was not as widespread 12 years ago as it is today, now that quantum computing has developed rapidly and also established itself at ETH Zurich beyond physics.
Since then, multiple experiments – including by ETH researchers – have been able to show that constructing computers that function according to the rules of quantum mechanics is possible in principle; various technologies are available and a reputable competition has been running for some time to challenge people to build the first quantum computer (see Globe 2/2018).
A quantum pioneer and zookeeper of complexities
A computer scientist who continually puts forward original arguments about the extent to which quantum computers could one day solve problems that are too complex for current computers – this is Scott Aaronson, Professor of Computer Science at the University of Texas in Austin and founding director of its Quantum Information Center. The models’ dialogue in the advertisement is actually a quotation from his book Quantum Computing since Democritus.
“What’s typical of Scott Aaronson is that he thinks beyond the conventional computer model and pursues the fundamental question of what types of computers could potentially solve more problems than current computers,” says ETH professor Renato Renner, a physicist who specialises in quantum information theory. Renner has already debated intensively with Aaronson on his blog (see the discussion under “Responses”). Aaronson has also visited ETH Zurich before – for the Zurich Physics Colloquium 2009.
Aaronson has been called a “complexonaut”, because he goes to the limits of complex problems to sound out the basic possibilities and limitations of computers – whether computers as we know them today, quantum computers, or completely new types of computers that are currently almost unimaginable. In his well-known Complexity Zoo, which can be found online, he groups together various classes of problem to show how well they can be computed and solved.
Aaronson is a researcher who is happy to ask big, fundamental questions. He will continue this theme in Zurich, where he will present three lectures for the Paul Bernays Lectures 2019 and discuss three key questions from theoretical computer science and physics.
What is actually computable and to what extent do new insights from quantum physics extend computability?
Are there problems that new kinds of computers, such as quantum computers, can solve more quickly and efficiently than current computers? Are there even particularly complex problems that can only be solved by quantum computers or other future computers?
Will we be able to create useful quantum computers, and what is the current status of the various approaches to constructing a quantum computer?
The theoretical foundations of Aaronson’s ideas are based on the Church-Turing thesis. This central thesis of computer science dates back to the computer pioneers Alonzo Church (1903-1995) and Alan Turing (1912-1954). Heavily simplified, it states that all problems for which we can intuitively imagine and formulate a solution are computable. This means that in principle, all problems that are computable by today’s mathematical computer models are also solvable by our current computers.
Can quantum computers solve more problems?
Does this really mean all problems? Not quite. There are also problems that are indeed computable and solvable in principle, but actually computing them would take far too much time. Computer scientists call these problems that computers cannot solve within a useful timeframe “not efficiently solvable”.
Generally speaking, many phenomena from quantum physics are currently not efficiently solvable. That’s why both physicists and computer scientists are examining whether quantum computers can efficiently solve more problems than conventional computers. “With our current level of knowledge, almost everyone agrees that quantum computers are faster than conventional computers. However, nobody has been able to prove it. This assumption is therefore one of the biggest questions in computer science,” says Renner, who will introduce Aaronson at the Paul Bernays Lectures.
There are also counterarguments: the Church-Turing thesis states that all solvable problems can be solved on a conventional computer. The extended version follows that all efficiently solvable problems can also be efficiently solved on a conventional computer. It’s known that a conventional computer can simulate a quantum computer – just not efficiently.
If someone succeeds in efficiently simulating a quantum computer on a conventional computer, the conventional computer would be able to solve the same problems as the quantum computer – which would also mean that quantum computers cannot fundamentally solve different problems than conventional computers. Aaronson himself argues in the other direction.
Looking ahead: encryption and gravity
One well-known example that conventional computers currently cannot compute efficiently relates to factorisation – splitting a large composite number into individual divisors. “In the case of factorisation, however, there are algorithms that can efficiently solve this problem – but these only work on a quantum computer,” says Renner. As current encryption and security techniques online are based on the factorisation problem, Aaronson is also researching the security-relevant implications of quantum computing.
Looking ahead to the future of computers, Aaronson and Renner are thinking even further: could there be completely new types of computers that use other physical phenomena than quantum mechanics? The theory of gravity, for example. Could this then allow us to solve problems that even quantum computers cannot solve efficiently?”