Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2603.12334

Quantum algorithms for compact polymer thermodynamics

Davide Rattacaso, Daniel Jaschke, Antonio Trovato, Ilaria Siloi, Simone Montangero

quant-phcond-mat.softcond-mat.stat-mechSubmitted Mar 12, 2026• Announced Mar 16, 2026• 0 citations
arXivHTMLPDF

Abstract

Efficient sampling from ensembles of Hamiltonian cycles is critical for predicting the thermodynamic properties of compact polymers, with applications including modeling protein and RNA folding and designing soft materials. Although classical Monte Carlo methods are widely regarded as the standard approach, their efficiency is strongly limited when applied to compact polymers. In this work, we enable a quadratic speedup in the estimation of thermodynamic properties of maximally compact polymers and heteropolymers by quantum computation. To this end, we encode the target thermodynamic ensemble into the amplitudes of a quantum state, i.e., a quantum sample, which can be processed via amplitude amplification. Using quantum equational reasoning, we construct a local parent Hamiltonian whose unique ground state realizes a quantum sample of all Hamiltonian cycles. This state can be prepared on quantum hardware using ground-state preparation methods, such as quantum annealing, and subsequently manipulated to generate quantum samples of polymers and heteropolymers at a target temperature. Finally, we approximate the quantum sample as a tensor network, revealing an entanglement area law. For fixed-width rectangular lattices, we obtain a time-efficient and compact encoding of the full ensemble of Hamiltonian cycles, enabling the efficient evaluation of expectation values, partition functions, and configuration probabilities via tensor contractions, without resorting to sampling.

Comments
18 pages, 11 figures

Related papers

Polymer Physics by Quantum Computing

Cristian Micheletti, Philipp Hauke, Pietro Faccioli

Sampling equilibrium ensembles of dense polymer mixtures is a paradigmatically hard problem in computational physics, even in lattice-based models. Here, we develop a formalism based on interacting binary tensors that allows for tackling this problem using quantum annealing machines. Our approach is general in that properties such as self-avoidance, branching, and looping can all be specified in terms of quadratic interactions of the tensors. Microstates' realizations of different lattice polymer ensembles are then seamlessly generated by solving suitable discrete energy-minimization problems. This approach enables us to capitalize on the strengths of quantum annealing machines, as we demonstrate by sampling polymer mixtures from low to high densities, using the D-Wave quantum annealer. Our systematic approach offers a promising avenue to harness the rapid development of quantum machines for sampling discrete models of filamentous soft-matter systems.

arXiv:2104.10102•Physical Review Letters•Aug 19, 2021•48 citations

Speedup via quantum sampling

Paweł Wocjan, Anura Abeyesinghe

The Markov-chain Monte Carlo method is at the heart of efficient approximation schemes for a wide range of problems in combinatorial enumeration and statistical physics. It is therefore very natural and important to determine whether quantum computers can speed up classical mixing processes based on Markov chains. To this end, we present a quantum algorithm, making it possible to prepare a quantum sample---i.e., a coherent version of the stationary distribution of a reversible Markov chain. Our algorithm has a significantly better running time than that of a previous algorithm based on adiabatic-state generation. We also show that our methods provide a greater speedup over a recently proposed method for obtaining the ground states of (classical) Hamiltonians.

arXiv:0804.4259•Physical Review A•Oct 31, 2008•120 citations

Efficient Quantum Monte Carlo through Cluster Expansions

Jorge Sánchez-Segovia, Álvaro M. Alhambra

The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of $(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}$, where $N$ is the system size, $\varepsilon$ the desired precision, and $Δ$ the interaction-graph degree. This becomes particularly severe in long-range systems, where $Δ\equiv N$, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime $\tilde{\mathcal{O}}(N^4\varepsilon^{-3})$. For quantum partition functions at temperatures $β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)$, this improves to $\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})$, where $D$ is the lattice dimension. The framework directly applies to long-range quantum systems with interactions $\propto1/r^α$, including $2$-local models with $α>2D$.

quant-pharXiv:2610.03893•Oct 6, 2026•0 citations

Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions

Harrow, AW, Wei, AY

Copyright © 2020 by SIAM Markov chain Monte Carlo algorithms have important applications in counting problems and in machine learning problems, settings that involve estimating quantities that are difficult to compute exactly. How much can quantum computers speed up classical Markov chain algorithms? In this work we consider the problem of speeding up simulated annealing algorithms, where the stationary distributions of the Markov chains are Gibbs distributions at temperatures specified according to an annealing schedule. We construct a quantum algorithm that both adaptively constructs an annealing schedule and quantum samples at each temperature. Our adaptive annealing schedule roughly matches the length of the best classical adaptive annealing schedules and improves on nonadaptive temperature schedules by roughly a quadratic factor. Our dependence on the Markov chain gap matches other quantum algorithms and is quadratically better than what classical Markov chains achieve. Our algorithm is the first to combine both of these quadratic improvements. Like other quantum walk algorithms, it also improves on classical algorithms by producing “qsamples” instead of classical samples. This means preparing quantum states whose amplitudes are the square roots of the target probability distribution. In constructing the annealing schedule we make use of amplitude estimation, and we introduce a method for making amplitude estimation nondestructive at almost no additional cost, a result that may have independent interest. Finally we demonstrate how this quantum simulated annealing algorithm can be applied to the problems of estimating partition functions and Bayesian inference.

•Jan 1, 2020•26 citations

Toward end-to-end quantum simulation for protein dynamics

Zhenning Liu, Xiantao Li, Chunhao Wang +1 more

Modeling and simulating the protein folding process overall remains a grand challenge in computational biology. We systematically investigate end-to-end quantum algorithms for simulating various protein dynamics with effects, such as mechanical forces or stochastic noises. A major focus is the read-in of system settings for simulation, for which we discuss (i) efficient quantum algorithms to prepare initial states--whether for ensemble or single-state simulations, in particular, the first efficient procedure for preparing Gaussian pseudo-random amplitude states, and (ii) the first efficient loading of the connectivity matrices of the protein structure. For the read-out stage, our algorithms estimate a range of classical observables, including energy, low-frequency vibrational modes, density of states, displacement correlations, and optimal control parameters. Between these stages, we simulate the dynamic evolution of the protein system, by using normal mode models--such as Gaussian network models (GNM) and all-atom normal mode models. In addition, we conduct classical numerical experiments focused on accurately estimating the density of states and applying optimal control to facilitate conformational changes. These experiments serve to validate our claims regarding potential quantum speedups. Overall, our study demonstrates that quantum simulation of protein dynamics represents a robust, end-to-end application for both early-stage and fully fault-tolerant quantum computing.

arXiv:2411.03972•Nov 6, 2024•2 citations

Quantum sampling algorithms, phase transitions, and computational complexity

Dominik S. Wild, Dries Sels, Hannes Pichler +2 more

Drawing independent samples from a probability distribution is an important computational problem with applications in Monte Carlo algorithms, machine learning, and statistical physics. The problem can be solved in principle on a quantum computer by preparing a quantum state that encodes the entire probability distribution followed by a projective measurement. We investigate the complexity of adiabatically preparing such quantum states for the Gibbs distributions of various classical models including the Ising chain, hard-sphere models on different graphs, and a model encoding the unstructured search problem. By constructing a parent Hamiltonian, whose ground state is the desired quantum state, we relate the asymptotic scaling of the state preparation time to the nature of transitions between distinct quantum phases. These insights enable us to identify adiabatic paths that achieve a quantum speedup over classical Markov chain algorithms. In addition, we show that parent Hamiltonians for the problem of sampling from independent sets on certain graphs can be naturally realized with neutral atoms interacting via highly excited Rydberg states.

arXiv:2109.03007•Physical Review A•Sep 2, 2021•14 citations
Efficient sampling from ensembles of Hamiltonian cycles is critical for predicting the thermodynamic properties of compact polymers, with applications including modeling protein and RNA folding and designing soft materials. Although classical Monte Carlo methods are widely regarded as the standard approach, their efficiency is strongly limited when applied to compact polymers. In this work, we enable a quadratic speedup in the estimation of thermodynamic properties of maximally compact polymers and heteropolymers by quantum computation. To this end, we encode the target thermodynamic ensemble into the amplitudes of a quantum state, i.e., a quantum sample, which can be processed via amplitude amplification. Using quantum equational reasoning, we construct a local parent Hamiltonian whose unique ground state realizes a quantum sample of all Hamiltonian cycles. This state can be prepared on quantum hardware using ground-state preparation methods, such as quantum annealing, and subsequently manipulated to generate quantum samples of polymers and heteropolymers at a target temperature. Finally, we approximate the quantum sample as a tensor network, revealing an entanglement area law. For fixed-width rectangular lattices, we obtain a time-efficient and compact encoding of the full ensemble of Hamiltonian cycles, enabling the efficient evaluation of expectation values, partition functions, and configuration probabilities via tensor contractions, without resorting to sampling.
Sampling equilibrium ensembles of dense polymer mixtures is a paradigmatically hard problem in computational physics, even in lattice-based models. Here, we develop a formalism based on interacting binary tensors that allows for tackling this problem using quantum annealing machines. Our approach is general in that properties such as self-avoidance, branching, and looping can all be specified in terms of quadratic interactions of the tensors. Microstates' realizations of different lattice polymer ensembles are then seamlessly generated by solving suitable discrete energy-minimization problems. This approach enables us to capitalize on the strengths of quantum annealing machines, as we demonstrate by sampling polymer mixtures from low to high densities, using the D-Wave quantum annealer. Our systematic approach offers a promising avenue to harness the rapid development of quantum machines for sampling discrete models of filamentous soft-matter systems.
The Markov-chain Monte Carlo method is at the heart of efficient approximation schemes for a wide range of problems in combinatorial enumeration and statistical physics. It is therefore very natural and important to determine whether quantum computers can speed up classical mixing processes based on Markov chains. To this end, we present a quantum algorithm, making it possible to prepare a quantum sample---i.e., a coherent version of the stationary distribution of a reversible Markov chain. Our algorithm has a significantly better running time than that of a previous algorithm based on adiabatic-state generation. We also show that our methods provide a greater speedup over a recently proposed method for obtaining the ground states of (classical) Hamiltonians.
The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of (Nε−1)O(log⁡Δ)(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}(Nε−1)O(logΔ), where NNN is the system size, ε\varepsilonε the desired precision, and ΔΔΔ the interaction-graph degree. This becomes particularly severe in long-range systems, where Δ≡NΔ\equiv NΔ≡N, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime O~(N4ε−3)\tilde{\mathcal{O}}(N^4\varepsilon^{-3})O~(N4ε−3). For quantum partition functions at temperatures β≤βsampling≡O(1)β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)β≤βsampling​≡O(1), this improves to O~(N3+1/Dε−3)\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})O~(N3+1/Dε−3), where DDD is the lattice dimension. The framework directly applies to long-range quantum systems with interactions ∝1/rα\propto1/r^α∝1/rα, including 222-local models with α>2Dα>2Dα>2D.
Copyright © 2020 by SIAM Markov chain Monte Carlo algorithms have important applications in counting problems and in machine learning problems, settings that involve estimating quantities that are difficult to compute exactly. How much can quantum computers speed up classical Markov chain algorithms? In this work we consider the problem of speeding up simulated annealing algorithms, where the stationary distributions of the Markov chains are Gibbs distributions at temperatures specified according to an annealing schedule. We construct a quantum algorithm that both adaptively constructs an annealing schedule and quantum samples at each temperature. Our adaptive annealing schedule roughly matches the length of the best classical adaptive annealing schedules and improves on nonadaptive temperature schedules by roughly a quadratic factor. Our dependence on the Markov chain gap matches other quantum algorithms and is quadratically better than what classical Markov chains achieve. Our algorithm is the first to combine both of these quadratic improvements. Like other quantum walk algorithms, it also improves on classical algorithms by producing “qsamples” instead of classical samples. This means preparing quantum states whose amplitudes are the square roots of the target probability distribution. In constructing the annealing schedule we make use of amplitude estimation, and we introduce a method for making amplitude estimation nondestructive at almost no additional cost, a result that may have independent interest. Finally we demonstrate how this quantum simulated annealing algorithm can be applied to the problems of estimating partition functions and Bayesian inference.
Modeling and simulating the protein folding process overall remains a grand challenge in computational biology. We systematically investigate end-to-end quantum algorithms for simulating various protein dynamics with effects, such as mechanical forces or stochastic noises. A major focus is the read-in of system settings for simulation, for which we discuss (i) efficient quantum algorithms to prepare initial states--whether for ensemble or single-state simulations, in particular, the first efficient procedure for preparing Gaussian pseudo-random amplitude states, and (ii) the first efficient loading of the connectivity matrices of the protein structure. For the read-out stage, our algorithms estimate a range of classical observables, including energy, low-frequency vibrational modes, density of states, displacement correlations, and optimal control parameters. Between these stages, we simulate the dynamic evolution of the protein system, by using normal mode models--such as Gaussian network models (GNM) and all-atom normal mode models. In addition, we conduct classical numerical experiments focused on accurately estimating the density of states and applying optimal control to facilitate conformational changes. These experiments serve to validate our claims regarding potential quantum speedups. Overall, our study demonstrates that quantum simulation of protein dynamics represents a robust, end-to-end application for both early-stage and fully fault-tolerant quantum computing.
Drawing independent samples from a probability distribution is an important computational problem with applications in Monte Carlo algorithms, machine learning, and statistical physics. The problem can be solved in principle on a quantum computer by preparing a quantum state that encodes the entire probability distribution followed by a projective measurement. We investigate the complexity of adiabatically preparing such quantum states for the Gibbs distributions of various classical models including the Ising chain, hard-sphere models on different graphs, and a model encoding the unstructured search problem. By constructing a parent Hamiltonian, whose ground state is the desired quantum state, we relate the asymptotic scaling of the state preparation time to the nature of transitions between distinct quantum phases. These insights enable us to identify adiabatic paths that achieve a quantum speedup over classical Markov chain algorithms. In addition, we show that parent Hamiltonians for the problem of sampling from independent sets on certain graphs can be naturally realized with neutral atoms interacting via highly excited Rydberg states.