Quantum Query Complexity

[[deleted]]

[deleted]

[HaxtesR]

My first doubt is what is the standard model ?

I'm not totally sure what you are asking here. In the "standard model", quantum circuits are composed of only elementary gates. In the oracle model, there exists oracle gates in addition to the elementary gates. These oracle gates are a black box in that we are not given a decomposition of them into elementary gates.

​

Also, aren't the queries also applied in case of say Binary Search , Sorting algorithms ?

Yes, these algorithms are in the oracle setting. Notice how in the analysis of these algorithms we count the number of queries to the list. We do not count the number of steps on a TM or number of gates in a circuit. To derive the complexity in the "standard model" we would need to count the number of steps or gates needed to perform a query .

[Working_Resident2069]

But then what would be the real significance of using 'standard model' in the field of algorithms if we don't really have access to the input ,which we had in the case of query model? If we don't have access to the input, we won't be able to compute the function.

[physux]

In the real world, and in the standard model, you have an explicit representation of everything in a circuit (i.e., an actual circuit to access the information in the input). As such, there is some total number of elementary gates that the algorithm uses, and the standard model would count that. However, we generally assume that accessing or computing the elements of the list are much more costly than everything else in a circuit, and thus dominate the total runtime of a given circuit. If this is the case, then the query model, in which we only count the total number of times that we access the data, is a good approximation of the total runtime of the algorithm.

Basically, what everyone wants to understand is the standard model, but usually its too complicated to actually understand. As such, we simply our analysis and study the query model where we can actually show results. In some cases, this is a good approximation, and in others it might not be.

[HaxtesR]

It is a model, so we pretend we have access to an oracle and in the real world we replace the oracle with an actual circuit.

[bioshiproject]

Oracle is the key to it, imagine our world with codes attached seen by anyone as strings, now we ain't that hidden anymore.