Jan 11 Andris Ambainis.'Separations in query complexity based on pointer functions' (Part 1)

QIP 2016, Banff, 10-16 January 2016

Plenary Talk

Date: 11 Jan 2016

Title: "Separations in query complexity based on pointer functions"
Authors: Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Juris Smotrovs and Miklos Santha.

We show a number of new separations between various query complexity measures, including: 1. A function f for which the bounded error quantum query complexity, Q(f)Q(f) is, up to logarithmic factors, equal to D1/4(f)D1/4(f) (where D(f)D(f) is the deterministic query complexity of ff). This is the first improvement over the quadratic gap between Q(f)Q(f) and D(f)D(f) provided by Grover's algorithm. 2. A function f for which the exact quantum query complexity QE(f)QE(f) is, up to logarithmic factors, equal to (R0(f))2/3(R0(f))2/3 where R0R0 is the zero-error randomized complexity of ff. Previously, the biggest gap was QE(f)=O(R0(f)0.86...QE(f)=O(R0(f)0.86...) by Ambainis (STOC'2013). 3. A function f for which the zero-error randomized complexity R0(f)R0(f) is, up to logarithmic factors, equal to (D(f))1/2(D(f))1/2. This is a seperation between two complexity measures which are both classical but it provides an improvement for a question where the previous best separation (R0(f)=O(D(f)0.753...R0(f)=O(D(f)0.753...) was shown in 1986. All of our examples are based on a function recently introduced by Goos, Pitassi, and Watson to separate the unambiguous nondeterministic query complexity from deterministic query complexity and which was used to resolve the famous Clique vs. Independent Set problem in communication complexity.