Quantum computers may soon dramatically enhance our ability to solve problems modeled by nonreversible Markov chains, according to a study published on the pre-print server arXiv.
The researchers from Qubit Pharmaceuticals and Sorbonne University, demonstrated that quantum algorithms could achieve exponential speedups in sampling from such chains, with the potential to surpass the capabilities of classical methods. These advances — if fully realized — have a range of implications for fields like drug discovery, machine learning and financial modeling.
Markov chains are mathematical frameworks used to model systems that transition between various states, such as stock prices or molecules in motion. Each transition is governed by a set of probabilities, which defines how likely the system is to move from one state to another. Reversible Markov chains — where the probability of moving from, let’s call them, state A to state B equals the probability of moving from B to A — have traditionally been the focus of computational techniques. However, many real-world systems are nonreversible, meaning their transitions are biased in one direction, as seen in certain biological and chemical processes.