Your data. Your choice.

If you select «Essential cookies only», we’ll use cookies and similar technologies to collect information about your device and how you use our website. We need this information to allow you to log in securely and use basic functions such as the shopping cart.

By accepting all cookies, you’re allowing us to use this data to show you personalised offers, improve our website, and display targeted adverts on our website and on other websites or apps. Some data may also be shared with third parties and advertising partners as part of this process.

Guide

Complexity theory: the surprise of the century?

Spektrum der Wissenschaft
4.3.2020
Translation: machine translated

It's one of the big questions in computer science: can computers solve any problem in a reasonable amount of time? Yes, says a new technical paper - and it's generating a lot of enthusiasm.

Scientists love to categorise things - at least on an abstract level. Chemists, for example, categorise all elements in the periodic table. Biologists categorise the earth's living creatures into families and species. And mathematicians have, after a long search, found and listed all infinite simple groups in the past decade.

Problems that are easy to check, even if they are difficult to solve, belong to the class NP. One example is a challenging Sudoku puzzle: it is difficult to find the correct solution. However, once you have worked it out or are presented with a completed sheet, it is easy to check whether it is correct.

The fun starts with P and NP: computer scientists have now created a hierarchy of complexity classes, from very simple to extremely sophisticated. The quantum computer has brought a twist: it enables new strategies when it comes to checking the correctness of the given solution to a problem.

An open question in complexity research has always been how complicated a problem can be at most so that a computer can still check it in a reasonable - i.e. polynomial - time. A team led by Zhengfeng Ji from the University of Technology, Sydney, has now found a surprising answer that is currently causing quite a stir among experts. According to the theory, even the most difficult problems in computer science can be tackled in a reasonable amount of time.

"I can't think of a single person who would have expected this," writes the respected computer scientist Scott Aaronson from the University of Austin in his blog. Should the work stand up to scrutiny by independent experts, it would be one of the biggest surprises in theoretical computer science this century.

The long history of complexity classes

However, the prover is not trustworthy, which is why you also need a verifier to recalculate the result provided. In Sudoku, it would be the verifier who ensures that a solution is correct. Unlike the prover, the verifier is a realistic computer that has limited resources. This means that its calculation time can only be polynomially dependent on the size of the task.

Because the solution provided by the prover may be extremely long and complicated, the examiner asks the prover various questions in an attempt to ascertain its veracity. Consider, for example, a table in a pitch-black room with several identically shaped wooden blocks lying on it. The task is to sort them according to their colour. The demonstrator - omnipotent as he is - has no problem with this. Despite the darkness, he divides the blocks into two piles.

Interrogation of multiple suspects

After this result, the field of interactive proof systems came to a standstill. At least until some researchers wondered what would happen if the two provers were not classical computers, but quantum computers that are coupled to each other via quantum physics. This is made possible by the phenomenon of entanglement, which Albert Einstein had already racked his brains over.

He called it "spooky action at a distance", because if you measure the state of one of two entangled objects, you also determine the state of the other - regardless of how far apart they are. Initially, this fact caused physicists a stomach ache, but it is now known that no information can be transported in this way.

In the beginning, complexity researchers did not pay much attention to the possibility of entangled provers, as it was assumed that the associated complexity class MIP* would be smaller than MIP or even IP. After all, the advantage of MIP is that the omniscient computers are questioned separately. If, on the other hand, they are entangled, the response of one affects the state of the other.

Entangled quantum computers as a solution

However, the first big surprise came in 2012: Vidick proved with his colleague Tsuyoshi Ito from the University of Waterloo that entangled quantum computers can also be used to check all problems from MIP in polynomial time. This means that both complexity classes are at least the same size.

The trick is to identify suitable questions through interleaving. In other words, the evidence providers first question themselves. At first glance, this may seem paradoxical, but because the two evidence providers are intertwined, they can run through several answers at the same time and thus deal with more conceivable verification steps. They pass these questions on to the examiner.

The examiner then only has to guarantee during the actual test that the questions are representative and meaningful and that the answers do not lead to any contradictions. In this way, they can carry out the test in a reasonable amount of time; the computing time required simply increases polynomially with the length.

If you have measured the speed of a particle and then determined its position, you no longer know how fast the object is now. For this reason, the two demonstrators are only allowed to carry out complementary measurements so that their answers do not influence each other. If you ask the first quantum computer for a calculated value, this deletes the corresponding information from the second quantum computer.

Unexpected twist for mathematicians

Contrary to what is often assumed, an infinite system cannot always be approximated arbitrarily precisely by a finite one

Spectrum of science

We are partners of Spektrum der Wissenschaft and want to make well-founded information more accessible to you. Follow Spektrum der Wissenschaft if you like the articles.

[[small:]]

96 people like this article


User Avatar
User Avatar

Experts from science and research report on the latest findings in their fields – competent, authentic and comprehensible.


Guide

Practical solutions for everyday problems with technology, household hacks and much more.

Show all

These articles might also interest you

  • Guide

    Ghost of Yōtei: 23 helpful beginner’s tips for this samurai adventure

    by Domagoj Belancic

  • Guide

    What are the benefits of working from home? The six most important insights

    by Spektrum der Wissenschaft

  • Review

    Ghost of Yōtei review: is this still open world?

    by Simon Balissat