5 ms·

A query complexity breakthrough

69 points by ianamartin 11y ago

nateabele 11y ago
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.
- eitally 11y ago
  You sound like me. I also enjoy reading everything people like Scott, Terry Tao (https://terrytao.wordpress.com/ https://terrytao.wordpress.com/) & Dick Lipton (https://rjlipton.wordpress.com/about-me/ 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.
- marvel_boy 11y ago
  Newbie here. I support this, can somebody explain this breaktrough with an example?
- ble 11y ago
  The parts I can digest: 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."
- gone35 11y ago
  Check out the addendum. Does it help?
- Strilanc 11y ago
  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. 1: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.124.7667&rep=rep1&type=pdf 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_counting https://en.wikipedia.org/wiki/Quantum_algorithm#Quantum_coun...
  - TheLoneWolfling 11y ago
    Don't you only need 1/4 + 1, for the deterministic case? It's still Θ(n), though.
    - 11y ago
aerovistae 11y ago
Yeah, seriously, +1 to nateabele's comment here. Can anyone explain this for non-PhDs?
j2kun 11y ago
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]: https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorith...
- beltsonata 11y ago
  >Amabainis et al refute a major conjecture about the biggest possible randomized/determinstic classical gap. Sorry, but could you explain what that major conjecture is?
  - 11y ago

69 points by ianamartin 11y ago

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.

eitally 11y ago
You sound like me. I also enjoy reading everything people like Scott, Terry Tao (https://terrytao.wordpress.com/ https://terrytao.wordpress.com/) & Dick Lipton (https://rjlipton.wordpress.com/about-me/ 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.
marvel_boy 11y ago
Newbie here. I support this, can somebody explain this breaktrough with an example?
ble 11y ago
The parts I can digest: 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."
gone35 11y ago
Check out the addendum. Does it help?
Strilanc 11y ago
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. 1: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.124.7667&rep=rep1&type=pdf 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_counting https://en.wikipedia.org/wiki/Quantum_algorithm#Quantum_coun...
- TheLoneWolfling 11y ago
  Don't you only need 1/4 + 1, for the deterministic case? It's still Θ(n), though.
  - 11y ago

aerovistae 11y ago

Yeah, seriously, +1 to nateabele's comment here. Can anyone explain this for non-PhDs?

j2kun 11y ago

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]: https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorith...

beltsonata 11y ago
>Amabainis et al refute a major conjecture about the biggest possible randomized/determinstic classical gap. Sorry, but could you explain what that major conjecture is?
- 11y ago