Skip to main content

New separations in query complexity

QuICS_04162015_8891.JPG

Speaker

Troy Lee(Centre for Quantum Technologies, Singapore)

Event Type

QuICS seminar

Date & Time

April 20, 2016, 11:00am

Where to Attend

CSS 3100A

For partial boolean functions, whose domain can be a subset of {0,1}^n, exponential separations are known between the number of queries a classical deterministic algorithm needs to compute a function and the number of queries a quantum algorithm needs. For a total boolean function f, whose domain is all of {0,1}^n, the situation is quite different: the quantum Q(f) and deterministic D(f) query complexities are always polynomially related, in fact D(f) = O(Q(f)^6). It was widely believed this relation was far from tight, as for 20 years the largest separation known between these two measures has been quadratic, witnessed by Grover's search algorithm. We exhibit a total boolean function with a 4th power separation between its quantum and deterministic query complexities. Interestingly, no new quantum algorithms are needed to achieve this separation---our quantum algorithm is based on Grover search and amplitude amplification.

This is joint work with Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Miklos Santha, and Juris Smotrovs.