31
$\begingroup$

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.

$\endgroup$
25
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Yes, a classical computer can simulate a quantum computer in terms of computational efficiency but it would be limited up to 23 qubits till 2005-2006 using IBM Bluegene supercomputer cluster at Forschungszentrum Juelich in Germany. However, the latest update as per 2017 is a world record of 46 qubits.

World Record: Quantum Computer with 46 Qubits simulated

Jülich, 15 December - Scientists from the Jülich Supercomputing Centre have set a new world record. Together with researchers from Wuhan University and the University of Groningen, they successfully simulated a quantum computer with 46 quantum bits – or qubits – for the first time. For their calculations, the scientists used the Jülich supercomputer JUQUEEN as well as the world’s fastest supercomputer Sunway TaihuLight at China’s National Supercomputing Center in Wuxi.

$\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.