3 ms·
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
by 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.