News for hackers. Stuff that matters.
Re:A query complexity breakthrough by SilasX on Thursday June 18, 2015 @04:19PM (#9741376)
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?

Re:A query complexity breakthrough by Strilanc on Friday June 19, 2015 @05:26AM (#9743744)
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.