"Breakthrough" research in query complexity

CQT researchers and their collaborators defined a function with a quartic quantum speed-up – a record – that makes quick work of following pointers hidden in unsorted data. Image: Kevin Utting, www.flickr.com/photos/tallkev/, CC-BY-2.0

New work by computer scientists at the Centre for Quantum Technologies and collaborators at the University of Latvia is causing a stir in the community. Their results in query complexity have been hailed as a "breakthrough" on the widely-read blog Shtetl-Optimized by computer scientist Scott Aaronson at the Massachusetts Institute of Technology (MIT).

He writes: "The highest compliment one researcher can pay another is, 'I wish I'd found that myself.' And I do, of course, but having missed it, I'm thrilled that at least I get to be alive for it and blog about it. Huge congratulations to the authors!"

The work takes down long-standing conjectures about the relationships between different flavours of query complexity, including showing the greatest quantum advantage yet known for a 'total function'.

The results appear in the preprint "Separations in Query Complexity Based on Pointer Functions" by Andris Ambainis, Kaspars Balodis, Alexander Belov and Juris Smotrovs from the University of Latvia and Troy Lee and Miklos Santha from CQT, posted online on 16 June. The blog post appeared 17 June. Within a week, the article had been downloaded over 500 times.

Complexity relationships

Query complexity is a measure of how much one needs to know about the input of a function to determine the output. It comes in various flavours, depending on what constraints you apply to how you access the input – including whether you can query the input bits in a quantum way – and if you must know the output with certainty or just with high probability.

Grover's algorithm famously brings a quantum speed-up to the problem of searching an unsorted database. In this case, the quantum query complexity is a power of two better (ie. smaller) than that of the classical query complexity. Written D(f)~Q(f)^2, it translates to a quadratically faster run-time for the quantum algorithm.

Grover's algorithm works no matter what entries are in the database. Researchers call this a total function because there are no restrictions on the input. Although Grover's algorithm was formulated in 1996, it had remained the best known quantum speed-up for a total function. Only for partial functions, defined for only some inputs, are larger exponential separations are known. Given this situation, researchers felt that might be the limit.

"It was really quite a deeply held belief in the community that a quadratic separation was the best possible," says Troy, a Principal Investigator at CQT and faculty at Nanyang Technological University. The new work overturns that belief, showing a function for which the quantum query complexity is a power of four better: D(f)~Q(f)^4.

This function does not solve any particular real-world problem, but its existence raises the possibility that a super-quadratic quantum speed-up is possible for other functions of practical importance.

Since the announcement of this result, researcher Shalev Ben-David at MIT has published a preprint solving a problem the paper left open. He shows there is even a super-quadratic quantum speedup over randomized algorithms, whereas the previous work showed this just for deterministic algorithms. "This is pretty interesting, even after our results I thought this may not be possible," says Troy. There's a post about this on Shtetl-Optimized too.

Record-breaking results

The researchers also set new records for the relationships between deterministic and randomised zero-error query complexity (refuting a conjecture that had stood since 1986), and zero-error and bounded-error randomized query complexities. Read more at Shtetl-Optimized and in the preprint.

All the functions the team studied are variants of one recently defined by other researchers in another paper. That paper improved one of the results in recent work by Miklos, a CQT Principal Investigator also at the French national research organisation CNRS. "So he was of course interested to see what they had done and see if he could improve it further," explains Troy.

Troy and Miklos began working to extend the result with co-author Alexander Belov, who was visiting CQT for two months earlier in 2015. When Alexander returned to Latvia, he brought in colleagues there. As soon as the team spotted the implications for quantum query complexity, "it was like drop everything, work on this," says Troy. "It was extremely fast. The whole paper took maybe two weeks to write."

The authors will be submitting the paper for presentation at conferences.