Question
Aaronson wrote in his thesis that
“essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic algorithm, to the algorithms of Hallgren and van Dam, Hallgren, and Ip—are oracle algorithms at their core. We do not know of any non-relativizing quantum algorithm technique analogous to the arithmetization technique that was used to prove PSPACE ⊆ IP. If such a technique is ever discovered, I will be one of the first to want to learn it.”
The common quantum algorithms I know of can be all explained using black-box model (i.e., query model):
Grover's search. An $O(\sqrt{n})$-query algorithm that computes the OR of $n$ bits.
Shor's algorithm. The kernel, Shor's period finding algorithm, is an $O({\rm poly} \log n)$-query algorithm that computes the period of a function, given its truth table as an $n$-bit input.
There are more examples like quantum local search and quantum-walk-based algorithms.
Do we have any problem that admits a quantum speedup, which cannot be explained using black-box model at present?
Meaning of this question
The quantum query complexity of any partial Boolean function is completely characterized by the general adversary bound (see e.g. [LMR+11]), which is a natural method, in the sense of Razborov and Rudich. If it turns out that every quantum technique relativizes, I think we will have some very interesting insight on quantum computing, from a computational complexity aspect.