Quantum-classical markov chain monte carlo

A system for sampling from a probability distribution approximating a Boltzmann distribution of an n-spin Ising model, the system comprising:

• a classical computer;
• and
• a quantum computer,
• wherein the classical computer is configured to select a first n-spin configuration of n ordered spins associated with the n-spin Ising model;
• wherein the quantum computer is configured to:
• prepare a first n-qubit state that is associated with said selected first n-spin configuration, wherein each n-qubit state is associated with a unique one n-spin configuration of said n ordered spins, and the first n-qubit state is a computational-basis state |x encoding a classical n-bit string x,
• apply a unitary operator to the first n-qubit state resulting in an evolved second n-qubit state, the unitary operator being part of a quantum channel CE acting on computational-basis states and defining, for each pair of classical n-bit strings x and y, a proposal probability qyx, wherein qyx is defined as a probability that, when the quantum channel CE is applied to the first n-qubit state |xx| and a resulting second n-qubit state is measured in a quantum computational basis, a measurement result is the classical n-bit string y, and wherein the quantum channel CE satisfies qyx=qxy for all classical n-bit strings x and y, and
• measure the evolved second n-qubit state to identify a corresponding second n-spin configuration represented by a classical n-bit string y;
• and
• wherein the classical computer is further configured to calculating, an acceptance probability Ayx to determine whether to replace the selected first n-spin configuration represented by x with the second n-spin configuration represented by y corresponding to said evolved second n-qubit state or whether to keep the selected first n-spin configuration unmodified by the applying the unitary operator to obtain an output n-spin configuration, wherein the acceptance probability Ayx depends on the n-spin Ising model and not on any explicit numerical value of the proposal probabilities qyx or qxy defined by the quantum channel CE.