Is it possible to simulate any classical algorithm with the same efficiency on quantum computer?

Question

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?

Answer 1

Yes, any classical algorithm can be implemented as a quantum circuit with almost same efficiency.

At first, we make our algorithm reversible (just include input as part of the output). Then represent it as a classical logic circuit and then modify this circuit such that it will contain only reversible classical logical gates https://en.wikipedia.org/wiki/Reversible_computing#Logical_reversibility. Actually we can use only classical Toffoli gate since it's universal for classical reversible circuits. Finally reversible classical gates are simply translated to corresponding quantum gates.