It is well known quantum computers are strictly more powerful than their classical counterparts in terms of query complexity.
Are there other models (natural or artificial) that are strictly between the quantum and classical in terms of query complexity?
The seperation can be on
- specific problems: model X computes function $f$ with strictly more queries than quantum, but fewer queries than the lower bound on classic, or
- different problems: model X computes function $f_1$ with strictly more queries than quantum, but computes function $f_2$ with fewer queries than classical.
In both cases, we want for every function $f$ to have $Q_2(f) \leq X(f) \leq R_2(f)$ to avoid examples that are hard to compare to quantum (like the certificate complexity of non-deterministic queries). Here $Q_2(f)$ (and $R_2(f)$) is the two-sided $1/3$-error quantum (and classical randomized) query complexity and the inequalities are within constant factors.