To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum algorithms?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ cf classical computing embraces quantum ideas Wolchover/Simons inst $\endgroup$– vznJul 25, 2014 at 21:34
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
There is at least one example that I can remember, but there are probably more that I am not aware of.
Recently, Maarten Van den Nest and Wolfgang Dürr found a new classical algorithm (arXiv:1304.2879) to approximate certain types of partition functions (of 3-body classical Ising models on two-dimensional lattices. Their algorithm is completely classical, but several connections to quantum physics are employed in the design (read below). The algorithm was found to be exponentially faster than previously known algorithms that solve the same problem, at the time of writing*.
*I am ignorant of whether better classical or quantum algorithms have been found a posteriori.
So, there are at least two quantum ingredients used in the design of the VdND algorithm. On the one hand, the authors use a classical-quantum connection between classical Ising models and topological quantum systems (precisely, some color codes). On the other hand, the authors use classical techniques to simulate quantum systems in the derivation of the algorithm: in their proof, they first write a small quantum algorithm for the problem of interest; then, the authors show how to simulate the former quantum algorithm efficiently on a classical computer, obtaining a classical algorithm (this is rather remarkable, in my view).
answered Jul 26, 2014 at 15:08
$\begingroup$
$\endgroup$
Quantum Proofs for Classical Theorems by Andrew Drucker and Ronald de Wolf is a very nice survey on this topic.
One of the first classical results obtained by thinking about the problem quantumly was a communication complexity lower bound for the inner product function by Cleve, van Dam, Nielsen and Tapp.
$\begingroup$
$\endgroup$
A couple more links on connections and analogies between quantum physics, quantum computation and (classical) computer science (to the already posted answers).
The survey paper of Drucker and de Wolf is already mentioned.
A presentation on simulating quantum computers with (classical) probabilistic models (and references thereof).
A somewhat older paper on $PP$, $BQP$ and $PostBQP$ computation classes (arxiv, 2004). Quantum Computing, Postselection, and Probabilistic Polynomial-Time
Relations between (classical hard) computation and renormalization techniques in statistical and quantum field theory (arxiv):
Renormalization and computation I: motivation and background
Renormalization and Computation II: Time Cut-off and the Halting Problem
Renormalization group approach to the P versus NP question
Further connections in this direction in Baez, Stay (arxiv): Physics, Topology, Logic and Computation: A Rosetta Stone
A (thermodynamic) Turing Machine which can compute (quantum) Hadamard transforms (arxiv): A Thermodynamic Turing Machine: Artificial Molecular Computing Using Classical Reversible Logic Switching Networks
Finally a review on Quantum Annealing and Computation connections (arxiv, 2013): Quantum Annealing and Computation: A Brief Documentary Note
