Quantum algorithm for exact Monte Carlo sampling

Nicolas Destainville (1, 2) , Bertrand Georgeot (3) , Olivier Giraud (4, 3)

1 PhyStat - Physique Statistique des Systèmes Complexes (LPT)
2 LPT - Laboratoire de Physique Théorique
3 ICQ - Cohérence Quantique (LPT)
4 LPTMS - Laboratoire de Physique Théorique et Modèles Statistiques

We build a quantum algorithm which uses the Grover quantum search procedure in order to sample the exact equilibrium distribution of a wide range of classical statistical mechanics systems. The algorithm is based on recently developed exact Monte Carlo sampling methods, and yields a polynomial gain compared to classical procedures.

Domaines: Physique Quantique [quant-ph]

Nicolas Destainville, Bertrand Georgeot, Olivier Giraud. Quantum algorithm for exact Monte Carlo sampling. Physical Review Letters, 2010, 104, pp.250502. ⟨10.1103/PhysRevLett.104.250502⟩. ⟨hal-00463472⟩