RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

New separations in query complexity

April 20, 2016 - 11:00am
Troy Lee
Centre for Quantum Technologies, Singapore

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.

3100A Computer and Space Sciences
College Park, MD 20742

Subscribe to A Quantum Bit 

Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...

Sign Up Now

Sign up to receive A Quantum Bit in your email!

 Have an idea for A Quantum Bit? Submit your suggestions to