1
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy