12
$\begingroup$

Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra:

and for Max 3LIN:

It may be very useful to compile a list of all known classical algorithms inspired from quantum computing. What other examples are known?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
6
$\begingroup$

As claimed by Leslie G. Valiant in a seminal paper 1 of his,

Holographic algorithms are inspired by the quantum computational model. However, they are executable on classical computers and do not need quantum computers.

That's an algorithmic design technique that has been used (by Valiant himself and others) to produce polynomial time algorithms for several problems that are minor variations of important NP-hard problems (more about it on wikipedia 2).

Improve this answer
$\endgroup$
9
$\begingroup$

There's also a recent work on low-rank semidefinite programming that, though not based directly on a quantum algorithm, still uses the same quantum-inspired techniques.

Improve this answer
$\endgroup$
3
$\begingroup$

There is a whole body of work to do with quantum inspired evolutionary algorithms(QIEA), with actual algorithms that use quantum computation techniques, see survey (source ACM) . Another quantum inspired algorithm uses it in numerical optimization.

Improve this answer
$\endgroup$
3
$\begingroup$

The quantum Monte Carlo quantum annealing (QMC-QA1) or discrete-time simulated quantum annealing (SQA2) algorithm(s) performed better than the tested D-Wave device in recent studies:

We establish the first example of a scaling advantage for an experimental quantum annealer over classical simulated annealing: we find that the D-Wave device exhibits certifiably better scaling than simulated annealing, with 95% confidence, over the range of problem sizes that we can test. However, we do not find evidence for a quantum speedup: simulated quantum annealing exhibits the best scaling by a significant margin.

Since both the D-Wave device and SQA outperform SA for certain problem instances, this gives the impression that SQA is a sort of quantum-inspired algorithm. The newer study testing the D-Wave 2000Q processor also finds that its performance correlates better with a proposed classical model labeled "spin-vector Monte Carlo (SVMC) algorithm" in that study than with SQA:

We use this to argue that a key reason for the quantum annealer’s slowdown relative to SQA is its sub-optimally high temperature, which causes it to behave more like SVMC. Thus, the strong performance of SQA on the logical-planted instance class suggests that this class is a good target or basis for the exploration of an eventual quantum speedup using QA hardware.

If we ignore the background D-Wave story, can we still conclude that SQA is a quantum-inspired optimization algorithm that outperforms classical simulated annealing (and maybe other optimization algorithms) for certain problems? It depends. If the goal is actually to find the ground state of some quantum system, then the answer is yes. But if the goal is to have a general purpose optimization algorithm similar to simulated annealing, then the answer is no.

  1. Martoňák, R., Santoro, G. E. & Tosatti, E. Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model. Phys. Rev. B 66, 094203 (2002). URL http://link.aps.org/doi/10.1103/PhysRevB.66.094203
  2. Santoro, G. E., Martoňák, R., Tosatti, E. & Car, R. Theory of quantum annealing of an Ising spin glass. Science 295, 2427–2430 (2002). URL http://dx.doi.org/10.1126/science.1068774.
Improve this answer
$\endgroup$
1
$\begingroup$

Take a look at quantum-inspired linear genetic programming. This algorithm aims to induce computer programs in imperative languages. E.g.:

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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