Computing may itself be a complex world for many, but classical computational complexity is an area literally booming with research. Quantum computers add a new dimension to this field in the form of quantum complexity. Now, a major problem concerning quantum computing has been settled by Ran Raz, professor at Princeton University, and Avishay Tal, now a post-doctoral fellow at Stanford University. “The quantum complexity world is rocking…” writes Lance Fortnow, Professor of Computer Science at Georgia Institute of Technology, in his blog, referring to the splash made by a paper posted online on May 31 in the Weizmann Institute website.
Now what could be so exciting? It’s a complex story that begins with complexity classes. First, computing problems have degrees of hardness associated with them. The class in which you place a problem is related to the efficiency of the algorithm used to solve it, namely, the number of operations a computer must make to arrive at the solution.
Think of a set of Russian Matrioshka dolls: the biggest doll contains a smaller one which in turn contains a smaller one and so on. The hierarchy of complexity classes can be viewed as a set of Matrioshka dolls.
The smallest doll here is the set P of problems for which there are known efficient, ‘polynomial time’ algorithms. One such example is matrix multiplication. As the size of the matrices increase, the time taken to multiply them using a classical algorithm increases as a polynomial function of the size of the matrices. Linear programming is another problem in P.
A larger doll containing P is the set NP. While algorithms that solve problems in NP are not yet known, efficient algorithms that can verify whether a proposed solution is a correct answer do exist.A typical problem in the NP class is a version of the travelling salesperson problem: Given pairwise distances between ‘n’ cities, we ask if there is a route to visit every city just once so that only ‘L’ litres of petrol are spent.
A still larger doll, or a class that contains all the above-mentioned classes, is PH, which stands for polynomial hierarchy.
Complexity crunch
The analogy of Matrioshka dolls must be taken carefully though, because it is still not known whether the problems in NP have efficient algorithms that can solve them. Hence, whether P equals NP is an open problem. Indeed, it is a millennium problem in the Clay Institute’s list. If someone shows that the classes all have polynomial time algorithms, there could be a great complexity crunch!
Into this hierarchy of Matrioshka dolls comes the class BQP which consists of all the problems that can be solved efficiently by a quantum computer. For ‘efficiently’ read ‘in polynomial time’.
The question is will this class BQP fit into the classical hierarchy or will it be disjoint? In the analogy of Matrioshka dolls, will it have a different shape, so that it won’t fit in somewhere in between the class PH and NP?
An outright answer to this question is difficult, but scientists invoke the concept of an oracle. An oracle is a device that will give an answer to a query about the solution of the problem – like the master gives answers in a ‘twenty questions’ game. The more the number of queries posed to the oracle, the more the ‘time’ taken to solve the problem.
Quantum and tractable
Raz and Tal invoke an oracle, in the presence of which they have shown that there are problems in BQP which are not in PH. Using clues provided by an oracle, some problems in BQP can be solved in polynomial time. Even with the clues, the problems would take much, much longer on a classical computer. This is called an ‘oracle separation’ between BQP and PH.
This is a big result because, as Raz puts it, “Our result shows that relative to some oracles, for some computational problems, quantum algorithms are more efficient than the entire classical polynomial hierarchy.” Alternatively, as Lance Fortnow explains in his blog, this result can be seen “as an indication that even in a world where P=NP (and even if integer factoring is easy), quantum algorithms might still have an edge over classical computation,” explains Tal in an email.
The duo uses a concept called ‘forrelation’ that was introduced by computer scientist Scott Aaronson of University of Texas at Austin, in the context of this very problem, a few years ago.
At a talk at Stanford's theory seminar in May 2018, computer scientist Pooya Hatami described his recent work on pseudo-random generators, jointly with Chattopadhyay, Hosseini and Lovett, and something clicked. “One lemma drew my attention and I thought about it for a few days, looked at the proof, and tried to understand its power. I then realised that this is exactly what we were missing,” says Tal.
“The Raz and Tal work is a great theoretical result, solving a 25-year-old problem in quantum complexity theory,” says V Arvind, complexity theory expert and director of Institute of Mathematical Sciences, Chennai.
“It is not clear to me if we can infer something new from this result about the power of quantum computing in practice. A similar result showing an oracle separation of BQP from NP was shown several years ago, using much simpler techniques. And anything practical we might want to infer is already implied by the earlier result,” he adds.
