Quantum algorithm for exact Monte Carlo sampling

Nicolas Destainville ¹, Bertrand Georgeot ¹, Olivier Giraud ^1, 2

Physical Review Letters 104 (2010) 250502

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.

• 1. Laboratoire de Physique Théorique – IRSAMC (LPT),
  CNRS : UMR5152 – Université Paul Sabatier – Toulouse III
• 2. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
  CNRS : UMR8626 – Université Paris XI – Paris Sud