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

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?

• Do you really only want n qubits. What about multiplying by sizeOfInt etc for the kind of data stored in the nodes. Also no ancillas? – AHusain Jul 13 '19 at 16:48
• @AHusain I meant here O(n) qubits (the same as in the classical case) – user Jul 14 '19 at 8:18