This seems pretty important, and I wish I could understand it without spending the rest of the day (week?) reading academic papers. If someone decides to write a For Dummies version, a link would be greatly appreciated.
You sound like me. I also enjoy reading everything people like Scott, Terry Tao (https://terrytao.wordpress.com/) & Dick Lipton (https://rjlipton.wordpress.com/about-me/) post, but have a deep understanding approaching none of it. Nevertheless, I find complexity & algorithms interesting, and it's so far out of my daily routine that it's mentally stimulating even (nay, especially because) if I have to spend a few hours in Wikipedia with every post.
Query complexity is about how much of the input needs to be read? Possibly about how many times each bit of the input needs to be read?
There are different models of computation being compared: the familiar deterministic algo on classical computer, random algo (with zero error or with bounded error) on classical computer, and bounded error algo on quantum computer.
They went looking for functions whose query complexity on different models of computation would have Interesting And Unexpected relationships.
The (1) item basically means they found a function for which the gap in query complexity (between running a bounded-error algorithm on a quantum computer and a deterministic algorithm on a classical computer) is larger than previously conjectured; "there exists at least one problem for which the advantage a bounded-error quantum algorithm has over a deterministic algorithm is even bigger than previously thought."
Query complexity is all about how many peeks it takes to figure out something about a random-access bit array.
For example, suppose I give you a bunch of bits and promise that either exactly 3/4s of them are true, or exactly 3/4s of them are false. How many times do you need to peek at a bit in the array before you can classify it into the 3/4-true or 3/4-false categories?
- If you use a deterministic peeking strategy, you need to check at least 1/2 of the input. If you don't, you're guaranteed to fail on some inputs.
- If you use a randomized peeking strategy, then you can avoid having "bad" inputs and become pretty sure of the answer after only a constant number of randomly sampled peeks. But if you want to be certain, then you'll still need to sample at least 1/2 of the input.
- If you're allowed to use a quantum peeking strategy, then you can solve the problem with certainty with a single superposed peek by applying one iteration of Grover's algorithm [1].
That's an example of a query separation. Quantumly, we can solve a problem with certainty in Θ(1) queries where classically we needed Θ(n) queries. However, the example function I gave is partial: the allowed inputs were restricted to satisfy a useful property (3/4-true or 3/4-false).
The new result is about total functions, where all inputs must be allowed. A variant of the example I gave that is total is a function that classifies inputs as at-least-3/4-true vs less-than-3/4-true. That happens to make things harder for the quantum algorithm, increasing the required number of superposed peeks (I think it's Θ(sqrt(N)), but I might be wrong [2]).
So tweaking the example function to be total shrank the separation from 1-vs-N to sqrt(N)-vs-N. Is there some other problem, where the total separation is larger? Yes. The authors of the paper managed to find a problem where the number of superposed peeks was the fourth root of the classical peeks, instead of just the square root like the example I gave.
I'm still lost on that prerequisite part, about a quantum algorithm someone computing something that depends on all the bits without looking at all of them. It sounds like, if I classically query all the bits, that counts as n queries, but if I apply some quantum operation to the n bits, that only counts as 1 query?
In what sense is the quantum algorithm (like for DJ or Grover's) only doing 1 query? How would that differ from calling it "one query" if I build a (classical) circuit of OR/AND gates and plug it in to the bits one time?
A quantum query is thought of as one query because it acts like one query in other contexts. For example, if the input is defined computationally ("evaluate F(n) to get the n'th bit"), then a quantum circuit will only need to include one copy of F (and only evaluate it once) if the quantum query complexity is 1, whereas a classical parallel circuit would need many copies of F. Also, a single superposed query is guaranteed to only reveal 1 bit of information about the input (though it may be about some aggregate property). A parallel query would reveal n bits. (That difference can matter in cryptography.)
Of course in practice the common case will be that your input is stored as bits in ram, and in that case it would almost always be cheaper and faster to use O(N) ram-with-built-in-CPU instead of O(N) quantum ram. Still, query complexity is theoretically interesting.
Explanation for non-PhD's (my qualifications: I do some quantum research, and the other day I was at Aaron's talk he refers to, and briefly talked to him afterward).
The overarching problem is whether we can prove that quantum algorithms are exponentially faster than classical algorithms. We believe it's true for things like factoring or discrete log (maybe), but these are conjectural because proving lower bounds for general classical algorithms is really really hard.
One the other hand, there are other problem models in which we can prove quantum algorithms are much faster than classical algorithms. These generally take the form of a "black-box query" model. Here is one example: there is a hidden boolean function f(x), and you get the promise that it has one of two properties (which are mutually exclusive). You get to query inputs x and receive outputs f(x), and you want to determine which of the two properties it has. The simplest example of such a problem is determining whether a function is contstant or is 0 on exactly half of the inputs and 1 on the other half. Classically you have to query 2^(n-1) + 1 inputs in the worst case. If you're allowed to give queries which are quantum superpositions of some inputs, then you can actually do it with one query. [1]
The model studied by Aaronson and Ambainis et al. is a slightly different kind of black box model, but with a similar flavor. You know f and you get query access to the bits of an unknown input x. You want to compute f(x) with as few queries as possible. Clearly you can do it with N queries where x has N bits, but some quantum algorithms can do it in 1 query by making a quantum query. In that model the goal is still to show the biggest gap in the number of needed queries between quantum algorithms and classical algorithms (possibly with randomness). Also people are interested in the difference between classical algorithms with randomness and without randomness, and in addition to proving the biggest quantum/classical gap, Amabainis et al refute a major conjecture about the biggest possible randomized/determinstic classical gap.
1. From 1998 [1] that the biggest gap in this model between quantum and classical was quadratic. (they got quartic)
2. From 1984 [2] that the biggest randomized/classical gap was something like N^0.75 (they got quadratic)
The reason I call these "major" is perhaps not exciting to people outside of academia: smart people tried to do better than [1] and [2] but couldn't for > 10 years. These works definitely deepen our theoretical understanding of the differences between quantum/randomized/classical computing. But you have to take it with the grain of salt that a major breakthrough is relative to the incentives and motivations of academic researchers.
15 comments
[ 3.3 ms ] story [ 31.9 ms ] threadQuery complexity is about how much of the input needs to be read? Possibly about how many times each bit of the input needs to be read?
There are different models of computation being compared: the familiar deterministic algo on classical computer, random algo (with zero error or with bounded error) on classical computer, and bounded error algo on quantum computer.
They went looking for functions whose query complexity on different models of computation would have Interesting And Unexpected relationships.
The (1) item basically means they found a function for which the gap in query complexity (between running a bounded-error algorithm on a quantum computer and a deterministic algorithm on a classical computer) is larger than previously conjectured; "there exists at least one problem for which the advantage a bounded-error quantum algorithm has over a deterministic algorithm is even bigger than previously thought."
For example, suppose I give you a bunch of bits and promise that either exactly 3/4s of them are true, or exactly 3/4s of them are false. How many times do you need to peek at a bit in the array before you can classify it into the 3/4-true or 3/4-false categories?
- If you use a deterministic peeking strategy, you need to check at least 1/2 of the input. If you don't, you're guaranteed to fail on some inputs.
- If you use a randomized peeking strategy, then you can avoid having "bad" inputs and become pretty sure of the answer after only a constant number of randomly sampled peeks. But if you want to be certain, then you'll still need to sample at least 1/2 of the input.
- If you're allowed to use a quantum peeking strategy, then you can solve the problem with certainty with a single superposed peek by applying one iteration of Grover's algorithm [1].
That's an example of a query separation. Quantumly, we can solve a problem with certainty in Θ(1) queries where classically we needed Θ(n) queries. However, the example function I gave is partial: the allowed inputs were restricted to satisfy a useful property (3/4-true or 3/4-false).
The new result is about total functions, where all inputs must be allowed. A variant of the example I gave that is total is a function that classifies inputs as at-least-3/4-true vs less-than-3/4-true. That happens to make things harder for the quantum algorithm, increasing the required number of superposed peeks (I think it's Θ(sqrt(N)), but I might be wrong [2]).
So tweaking the example function to be total shrank the separation from 1-vs-N to sqrt(N)-vs-N. Is there some other problem, where the total separation is larger? Yes. The authors of the paper managed to find a problem where the number of superposed peeks was the fourth root of the classical peeks, instead of just the square root like the example I gave.
1: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.124... Relativized Separation of EQP from P^NP, Green & Pruim
2: https://en.wikipedia.org/wiki/Quantum_algorithm#Quantum_coun...
01011111
01010000
In what sense is the quantum algorithm (like for DJ or Grover's) only doing 1 query? How would that differ from calling it "one query" if I build a (classical) circuit of OR/AND gates and plug it in to the bits one time?
Of course in practice the common case will be that your input is stored as bits in ram, and in that case it would almost always be cheaper and faster to use O(N) ram-with-built-in-CPU instead of O(N) quantum ram. Still, query complexity is theoretically interesting.
The overarching problem is whether we can prove that quantum algorithms are exponentially faster than classical algorithms. We believe it's true for things like factoring or discrete log (maybe), but these are conjectural because proving lower bounds for general classical algorithms is really really hard.
One the other hand, there are other problem models in which we can prove quantum algorithms are much faster than classical algorithms. These generally take the form of a "black-box query" model. Here is one example: there is a hidden boolean function f(x), and you get the promise that it has one of two properties (which are mutually exclusive). You get to query inputs x and receive outputs f(x), and you want to determine which of the two properties it has. The simplest example of such a problem is determining whether a function is contstant or is 0 on exactly half of the inputs and 1 on the other half. Classically you have to query 2^(n-1) + 1 inputs in the worst case. If you're allowed to give queries which are quantum superpositions of some inputs, then you can actually do it with one query. [1]
The model studied by Aaronson and Ambainis et al. is a slightly different kind of black box model, but with a similar flavor. You know f and you get query access to the bits of an unknown input x. You want to compute f(x) with as few queries as possible. Clearly you can do it with N queries where x has N bits, but some quantum algorithms can do it in 1 query by making a quantum query. In that model the goal is still to show the biggest gap in the number of needed queries between quantum algorithms and classical algorithms (possibly with randomness). Also people are interested in the difference between classical algorithms with randomness and without randomness, and in addition to proving the biggest quantum/classical gap, Amabainis et al refute a major conjecture about the biggest possible randomized/determinstic classical gap.
[1]: https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorith...
Sorry, but could you explain what that major conjecture is?
1. From 1998 [1] that the biggest gap in this model between quantum and classical was quadratic. (they got quartic)
2. From 1984 [2] that the biggest randomized/classical gap was something like N^0.75 (they got quadratic)
The reason I call these "major" is perhaps not exciting to people outside of academia: smart people tried to do better than [1] and [2] but couldn't for > 10 years. These works definitely deepen our theoretical understanding of the differences between quantum/randomized/classical computing. But you have to take it with the grain of salt that a major breakthrough is relative to the incentives and motivations of academic researchers.
[1]: http://arxiv.org/abs/quant-ph/9802049
[2]: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86...