Similar to the question Could a Turing Machine simulate a quantum computer?: given a 'classical' algorithm, is it always possible to formulate an equivalent algorithm which can be performed on a quantum computer? If yes, is there some kind of procedure we can follow for this? The resulting algorithm will probably not take full advantage of the possibilities of quantum computing, it's more of a theoretical question.


Yes, it can do so in a rather trivial way: Use only reversible classical logical gates to simulate computations using boolean logic (for instance, using TOFFOLI to simulate NAND gates), use only the standard basis states $\lvert 0\rangle$ and $\lvert 1\rangle$ as input, and only perform standard basis state measurements at the output. In this way you can simulate exactly the same calculations as the classical computer does, on a gate-by-gate basis.


Yes, it can because quantum computing is a generalization of classical computing. So the procedure you ask for exists.

We can take a universal classical logic gate such as NOR gate, generalize to a reversible quantum version of that NOR gate. Thus a procedure can be as follows:

  • Design classical circuit
  • Rewrite classical circuit using only the chosen universal classical gate (e.g. NOR)
  • Convert the classical circuit above using quantum the quantum version of the classical universal gate

We pick a set of basis states, to represent the two binary classical states, and we ignore complex amplitudes as the other answer, by jknappen, implies.


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.