Sur ce site

Sur le Web du CNRS

Accueil du site > À la une > A quantum algorithm for exact Monte Carlo sampling

A quantum algorithm for exact Monte Carlo sampling

par Nicolas Destainville - 12 juillet 2010

Toutes les versions de cet article : English , français

One of the motivations of Quantum Information is to propose algorithms adapted to future quantum computers that would make “classical” algorithms (those used on our computers) more efficient. To this goal, three researchers of the LPT (Toulouse) and of the LPTMS (Paris) have recently published a work, appeared in Physical Review Letters (June 2010), where they propose the quantum version of the “Coupling from the past” algorithm by James Propp and David Wilson. This celebrated algorithm has been proposed 15 years ago in order to sample exactly configurations of a system among a large number, according to a given probability distribution. This is a recurrent problematics in Applied Mathematics, in Computer Science, as well as in Theoretical Physics. The central idea of this algorithm is to follow in parallel the history of all configurations, which evolve according to a traditional Monte Carlo algorithm. When all histories have converged to a same configuration, then the latter is exactly distributed according to the desired distribution. Unfortunately, following all histories is computationally prohibitive in practice. There comes the idea proposed by the three researchers, which consists of parallelizing this task on a quantum processor. The last stage of the algorithm, the detection of convergence, requires the use of Grover’s procedure, a celebrated algorithm of Quantum Information, which enables to find efficiently an element in a non-structured list.

PNG - 63.9 ko

Top : schematic view of the algorithm by Propp and Wilson, where each line represents a configuration and where each column corresponds to a step of the algorithm ; a sequence of green arrows represents an history, and all histories have converged to the same configuration (state 2 here) at the end of the algorithm. Bottom : the quantum version of a step, where each line now represents a quantum bit (or “qubit”).

Details can be found in the article
Quantum algorithm for exact Monte Carlo sampling
N. Destainville, B. Georgeot, O. Giraud
Phys. Rev. Lett. 104, 250502 (2010)