Understanding Quantum Algorithms via Query Complexity

Understand

Query complexity is a model of computation in which we have to compute a function $f(x_1, \ldots, x_N)$ of variables $x_i$ which can be accessed via queries.

• The complexity of an algorithm is measured by the number of queries that it makes.
• Query complexity is widely used for studying quantum algorithms, for two reasons.
• First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm).