Consider any data structure based on the binary search trees, e.g. set. Classical computers can make queries (insert, remove, test if element present), into this structure in $O(\log n)$ time, where $n$ is the number of elements.
Using the quantum circuit representation, set data structure requires $n$ wires to be implementable. The unitary matrices that represent queries on $n$ wires will have size $2^n \times 2^n$. The boundary on the length of the gate sequence is $O(2^n)$ (see Number of gates required to approximate arbitrary unitaries). Therefore, generally we won't be able to achieve classical $O(\log n)$ query complexity, we will have even worse $O(2^n)$!
I understand that $O(2^n)$ is given for arbitrary matrix. The question is: is it possible to implement the unitary matrices that represent set queries on $n$ qubits with a gate sequence of $O(\log n)$ length?