3 ms·

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

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

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