Accueil du site > À la une > A quantum algorithm for exact Monte Carlo sampling
A quantum algorithm for exact Monte Carlo sampling
par - 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.
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)
Dans la même rubrique :
- Exceeding the Pauli limit
- Google matrix of the world trade network
- Symmetry-protected topological phases of cold atoms in one dimension
- Measuring the size of Schrödinger’s cat
- Fractionalization of Itinerant Anyons in One-Dimensional Chains
- How to reproduce bacterial propulsion in a biomimetic way ?
- Local injection of pure spin current generates electric current vortices
- Condensate-free superfluid induced by frustrated proximity effect
- Ultimate quantum limits to sensitivity of nano-oscillator based "artificial noses"
- Preuve expérimentale du couplage spin-orbite Zeeman
- Gapless spin liquid in the frustrated square lattice Heisenberg quantum antiferromagnet
- An Ideal Test Bed for 2D Magnetism
- Spin-Wave Localization for 2D Bosons in a Random Potential
- DNA bubbles and bending : how conformational fluctuations modify its thermal denaturation
- Phase separation and flux quantization in the doped quantum dimer model on the square and triangular lattices
- How disorder can turn into long-range order at high magnetic field ?
- Computing fidelity at magnetic quantum phase transitions
- Topological chiral spin liquid groundstate of a frustrated antiferromagnetic Heisenberg model
- Comment développer l’intelligence collective grâce à l’information sociale
- Comment les poissons interagissent et coordonnent leurs déplacements dans un banc