Is it possible to convert classical algorithms to quantum ones?

Question

I am new in this field and I am considering to do research for my engineering degree.
First, I would like to have an opinion from more experienced people. Do you think it is possible to convert classic algorithms to quantum algorithms? Having in mind that the conversion will take in consideration the particularities of quantum algorithms.
If so, can you explain your point of view and if it is possible, an example?

Martin Vesely · Accepted Answer

It depends on what you mean by converting classical algorithm to quantum one.
One angle of view can be: Is it possible to run any classical algorithm on quantum computer? If this is a case then answer is yes. Since so-called Toffoli gate is effectivelly NAND gate (in case the controlled qubit is set to state $|1rangle$ before) and such gate enables to implement any logical function. Hence, you can use universal gate-based quantum computer for implementation of any classical algorithm.
Seconde angle of view could be: Is there a qunatum counterpart to any classical algorithm? In this case the answer is difficult and I am not sure whether it has been resolved already. However, there are some examples of quantum algorithms solving problems we have classical ones for. For instance: Shor's algorithm is used for integers factoring, Grover's algorithm for searching in unordered databases, HHL algorithm for solving systems of linear equations, there are Monte Carlo algorithms useful in finance, Hamiltonian simulations algorithms useful in simulation of quantum systems (the original purpose the quantum computers have been developed for) etc. Moreover, there is a family of so-called quantum annealers. These are single purpose quantum computers implementing quantum annealing algorithm on hardware level.

glS · Answer

Given an arbitrary classical algorithm, you can trivially convert it into a "quantum algorithm" by simply making it into a reversible circuit. There are standard ways to do this.
Of course, this doesn't really give you any "quantum advantage". Any quantum algorithm obtained this way will have the same efficiency as the same algorithm run on classical computer.
On the other hand, if the question is whether there is a standardised way to convert a given classical algorithm into a quantum one that solves the same problem more efficiently, then the answer is negative. Quantum algorithms that are more efficient than their classical counterparts do so by solving the given problem in very different ways, and there is no easy way to find such algorithms given a classical solution to the problem.

Is it possible to convert classical algorithms to quantum ones?

2 Answers

Add your own answers!

Ask a Question