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?

  • $\begingroup$ 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? $\endgroup$
    – AHusain
    Commented Jul 13, 2019 at 16:48
  • $\begingroup$ @AHusain I meant here O(n) qubits (the same as in the classical case) $\endgroup$
    – user7988
    Commented Jul 14, 2019 at 8:18

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.