4 ms·

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

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.
- Strilanc 11y ago
  You've peeked 8/4+1 = 3 times and seen 0 1 0 _ _ _ _ _. Is it 3/4 zeros or is it 3/4 ones? 01011111 01010000
  - TheLoneWolfling 11y ago
    Right. Whoops.
SilasX 11y ago
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?
- Strilanc 11y ago
  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.

TheLoneWolfling 11y ago

Don't you only need 1/4 + 1, for the deterministic case? It's still Θ(n), though.

Strilanc 11y ago
You've peeked 8/4+1 = 3 times and seen 0 1 0 _ _ _ _ _. Is it 3/4 zeros or is it 3/4 ones? 01011111 01010000
- TheLoneWolfling 11y ago
  Right. Whoops.

SilasX 11y ago

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?

Strilanc 11y ago
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.