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

Not the answer you're looking for? Browse other questions tagged or ask your own question.