Quantum Algorithms Database
Quantum Belief Propagation
A quantum generalization of the classical belief propagation algorithm used for probabilistic inference in graphical models, relevant to both quantum error correction and quantum machine learning.
Year
2007 (Leifer & Poulin)
Inventor(s)
Leifer & Poulin
Speedup Type
Heuristic (No Proven Speedup)
Difficulty
★★★★★
The Problem
Efficiently estimating probabilities in complex networks of interdependent variables — a core task in classical statistical inference and machine learning.
How It Works
Generalizes classical message-passing inference rules to quantum states, propagating quantum 'belief' information across a network structure to estimate quantum marginal probabilities.
Real-World Impact
Has direct applications in decoding certain quantum error-correcting codes, connecting classical inference theory to practical quantum error correction implementations.