Quantum algorithm for exact Monte Carlo sampling

Nicolas Destainville 1, Bertrand Georgeot 1, 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