Boltzmann sampling with quantum annealers via fast Stein correction

Koji Tsuda; Ryosuke Shibukawa; Ryo Tamura

arxiv: 2309.04120 · v1 · submitted 2023-09-08 · ❄️ cond-mat.stat-mech · quant-ph

Boltzmann sampling with quantum annealers via fast Stein correction

Ryosuke Shibukawa , Ryo Tamura , Koji Tsuda This is my paper

Pith reviewed 2026-05-24 06:41 UTC · model grok-4.3

classification ❄️ cond-mat.stat-mech quant-ph

keywords Boltzmann samplingquantum annealingStein correctionrandom feature mapsthermal averagesD-Wavedistribution correctionexponentiated gradient

0 comments

The pith

Fast approximate Stein correction reduces error in thermal averages from quantum annealer samples.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Quantum annealers can generate samples from Boltzmann distributions but their internal sampling distribution is unknown, so standard correction methods like importance sampling cannot be used. Stein correction can reweight samples without that knowledge, yet the exact version requires solving a large quadratic program that is impractical. The paper introduces an approximation that uses random feature maps to represent the Stein operator and exponentiated gradient updates to find the weights quickly. When this fast version is applied to samples from D-Wave devices on standard benchmark problems, the residual error in computed thermal averages drops substantially. If the approach holds, quantum annealers become a practical route to Boltzmann sampling at arbitrary temperatures.

Core claim

The paper develops a fast approximate Stein correction method based on random feature maps and exponentiated gradient updates that computes sample weights without knowing the quantum annealer's sampling distribution. Applied to D-Wave outputs, the method reduces the residual error of thermal average calculations significantly on benchmarking problems, suggesting quantum annealers could serve as a viable alternative to Markov chain Monte Carlo once corrected.

What carries the argument

Fast approximate Stein correction via random feature maps for the Stein operator and exponentiated gradient updates to compute sample weights.

If this is right

Quantum annealers could generate usable Boltzmann samples at temperatures where their raw output is biased.
Thermal averages in statistical mechanics models could be estimated more reliably with quantum hardware.
Stein-based correction becomes feasible for large sample sets where exact quadratic programming fails.
Quantum annealers might compete with established Markov chain Monte Carlo methods once the correction is included.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same fast correction could be tested on other hardware samplers whose distributions are also unknown.
Accuracy at very low temperatures might still require additional techniques beyond this correction.
The random feature approximation's scaling with problem size could be checked on larger spin-glass instances.

Load-bearing premise

The unknown distribution produced by the quantum annealer can be corrected effectively by the approximated Stein operator without the approximation introducing uncontrolled bias into the thermal averages.

What would settle it

Apply the fast Stein correction to D-Wave samples on a benchmark with known exact thermal averages and observe that the error does not decrease or increases relative to the uncorrected samples.

Figures

Figures reproduced from arXiv: 2309.04120 by Koji Tsuda, Ryosuke Shibukawa, Ryo Tamura.

**Figure 1.** Figure 1: Results for Stein correction on GSD 8. (a) Computational time of exact and fast Stein correction depending on the number of samples n when ℓ = 5, 000. The inset is the log scale figure. (b) Residual error of the Stein kernel matrix Kp against the number of random features ℓ when n = 1, 000. Five independent runs are performed, and the mean and standard deviation are plotted as lines and error bars, respect… view at source ↗

**Figure 2.** Figure 2: Residual errors of internal energy E(β), magnetic susceptibility χ(β), and Binder cumulant U4(β). The thermal averages are calculated by MCMC, a naive average by quantum annealer (QA), and Stein correction (SC), respectively. The number of samples is fixed as n = 10, 000, and the results depending on n are shown in Fig. S1. Five independent runs are performed, and the mean and standard deviation are plotte… view at source ↗

read the original abstract

Despite the attempts to apply a quantum annealer to Boltzmann sampling, it is still impossible to perform accurate sampling at arbitrary temperatures. Conventional distribution correction methods such as importance sampling and resampling cannot be applied, because the analytical expression of sampling distribution is unknown for a quantum annealer. Stein correction (Liu and Lee, 2017) can correct the samples by weighting without the knowledge of the sampling distribution, but the naive implementation requires the solution of a large-scale quadratic program, hampering usage in practical problems. In this letter, a fast and approximate method based on random feature map and exponentiated gradient updates is developed to compute the sample weights, and used to correct the samples generated by D-Wave quantum annealers. In benchmarking problems, it is observed that the residual error of thermal average calculations is reduced significantly. If combined with our method, quantum annealers may emerge as a viable alternative to long-established Markov chain Monte Carlo methods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a workable fast approximation to Stein correction for D-Wave samples that cuts residual error on benchmarks, but the random-feature step leaves open the risk of uncontrolled bias.

read the letter

The main takeaway is that this work turns Stein correction into something you can actually run on quantum-annealer output by swapping the big quadratic program for random feature maps and exponentiated gradient updates. That removes the main practical blocker when the sampling distribution is unknown, which is the usual situation with D-Wave hardware. They apply it to thermal-average calculations and report that the corrected results have lower residual error than the raw samples on their test cases. The combination is new enough in the annealer context and directly targets a known limitation rather than re-deriving the base Stein identity. Credit is due for making the method scale to realistic problem sizes without needing the exact distribution. The citation to Liu and Lee is straightforward and the method stays independent of it. The experiments appear to be on standard benchmarking problems, which is the right place to start. The soft spot is the approximation quality. The random-feature version of the Stein operator is not guaranteed to keep the expectation identity intact to high accuracy, and any leftover violation shows up as bias in the reweighted averages. The abstract only states that error drops significantly without giving bounds on the approximation error, problem dimensions, or a head-to-head with exact Stein weights on the same instances. If the full paper supplies those numbers and shows the bias stays small, the concern is minor; otherwise it is the central thing a referee would press on. No other obvious gaps in the logic or circularity. This is for people who already work with quantum annealers for statistical mechanics sampling and want a post-processing route that does not require knowing the hardware distribution. A reader who needs a drop-in correction for existing annealer runs would get immediate value if the implementation is reproducible. It deserves a serious referee because the core idea is targeted, the motivation is solid, and the experiments address a concrete barrier even if the approximation analysis needs tightening.

Referee Report

2 major / 1 minor

Summary. The manuscript develops a fast approximate Stein correction method based on random feature maps and exponentiated gradient updates to reweight samples generated by D-Wave quantum annealers. This enables correction of the unknown sampling distribution for Boltzmann sampling without requiring the analytical form of the distribution, and the authors report that the approach significantly reduces residual errors in computed thermal averages on benchmark problems, potentially making quantum annealers competitive with MCMC methods.

Significance. If the empirical error reductions are robust and the approximation does not introduce uncontrolled bias, the work provides a practical algorithmic layer that could broaden the applicability of quantum annealers to finite-temperature sampling tasks where conventional importance sampling is inapplicable. The absence of circularity with the underlying Stein identity (Liu and Lee, 2017) and the focus on computational efficiency are strengths.

major comments (2)

[Method (random feature map + exponentiated gradient)] The random feature map approximation to the Stein operator (described in the method section) replaces the exact operator whose expectation vanishes under the target measure; the manuscript provides no quantitative bound on the residual violation of this identity after approximation and exponentiated-gradient optimization. Any such violation directly biases the reweighted expectations, and without either an error bound or a direct comparison of approximate versus exact Stein weights on the same instances, the central claim of reliable correction rests solely on observed error reduction.
[Numerical experiments / benchmarking] The benchmarking section reports that residual error is reduced significantly but supplies no details on problem sizes, number of instances, specific models tested, baseline methods (e.g., uncorrected annealer samples or other correction schemes), or statistical error bars. This makes it impossible to judge whether the improvement is statistically meaningful or generalizes beyond the chosen instances.

minor comments (1)

[Method] Notation for the random-feature dimension and the exponentiated-gradient step-size parameter should be introduced explicitly with symbols rather than described only in prose.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We respond to each major comment below.

read point-by-point responses

Referee: [Method (random feature map + exponentiated gradient)] The random feature map approximation to the Stein operator (described in the method section) replaces the exact operator whose expectation vanishes under the target measure; the manuscript provides no quantitative bound on the residual violation of this identity after approximation and exponentiated-gradient optimization. Any such violation directly biases the reweighted expectations, and without either an error bound or a direct comparison of approximate versus exact Stein weights on the same instances, the central claim of reliable correction rests solely on observed error reduction.

Authors: We acknowledge that the random feature approximation combined with exponentiated gradient updates does not come with a quantitative bound on the residual violation of the Stein identity, and that the manuscript does not include a direct comparison against exact Stein weights. Deriving such a bound is technically challenging and outside the scope of the present work, whose primary goal is to obtain a computationally tractable correction when the exact quadratic program is infeasible. The method is therefore presented as a practical heuristic whose value is demonstrated by the observed reduction in residual error on the benchmark instances. In the revision we will add an explicit discussion of this approximation gap and its potential implications for bias. revision: partial
Referee: [Numerical experiments / benchmarking] The benchmarking section reports that residual error is reduced significantly but supplies no details on problem sizes, number of instances, specific models tested, baseline methods (e.g., uncorrected annealer samples or other correction schemes), or statistical error bars. This makes it impossible to judge whether the improvement is statistically meaningful or generalizes beyond the chosen instances.

Authors: We agree that the current manuscript does not provide sufficient experimental details. In the revised version we will expand the benchmarking section to report the concrete problem sizes, the number of instances, the specific models (e.g., random Ising instances), the baselines employed (including uncorrected D-Wave samples), and statistical error bars obtained from repeated runs. This will enable a clearer assessment of statistical significance and generality. revision: yes

Circularity Check

0 steps flagged

No circularity; independent approximation layered on external Stein reference

full rationale

The paper introduces a new fast approximate Stein correction procedure (random feature maps + exponentiated gradient) to reweight samples from an unknown quantum-annealer distribution. This construction is presented as an algorithmic contribution that builds directly on the external 2017 Liu & Lee Stein identity; no equation or claim reduces to a self-definition, a fitted parameter relabeled as a prediction, or a load-bearing self-citation. The reported outcome is an empirical reduction in residual error on benchmarks, which is not forced by the method's own inputs. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on the external Stein correction framework (Liu and Lee 2017) and the domain assumption that the annealer distribution, though unknown, can be corrected by reweighting. No free parameters, new axioms, or invented entities are introduced in the abstract.

axioms (1)

domain assumption Stein correction can be applied to reweight samples without knowledge of the sampling distribution
Explicitly stated as the reason Stein correction is usable where importance sampling is not.

pith-pipeline@v0.9.0 · 5692 in / 1183 out tokens · 21566 ms · 2026-05-24T06:41:03.857734+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

[1]

Binder and A

K. Binder and A. P. Young, Rev. Mod. Phys. 58, 801 (1986)

work page 1986
[2]

Binder and E

K. Binder and E. Luijten, Phys. Rep. 344, 179 (2001)

work page 2001
[3]

Zhang, S

N. Zhang, S. Ding, J. Zhang, and Y. Xue, Neurocom- 5 puting 275, 1186 (2018)

work page 2018
[4]

R. G. Melko, G. Carleo, J. Carrasquilla, and J. I. Cirac, Nat. Phys. 15, 887 (2019)

work page 2019
[5]

Doucet, N

A. Doucet, N. De Freitas, N. J. Gordon, et al., Sequential Monte Carlo methods in practice (Springer, 2001)

work page 2001
[6]

Hukushima and K

K. Hukushima and K. Nemoto, J. Phys. Soc. Japan 65, 1604 (1996)

work page 1996
[7]

Iba, Int

Y. Iba, Int. J. Mod. Phys. C 12, 623 (2001)

work page 2001
[8]

Hukushima and Y

K. Hukushima and Y. Iba, AIP Conference Proceedings 690, 200 (2003)

work page 2003
[9]

M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Jo- hansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, Nature 473, 194 (2011)

work page 2011
[10]

Nelson, M

J. Nelson, M. Vuffray, A. Y. Lokhov, T. Albash, and C. Coffrin, Phys. Rev. Applied 17, 044046 (2022)

work page 2022
[11]

Raymond, S

J. Raymond, S. Yarkoni, and E. Andriyash, Frontiers in ICT 3 (2016)

work page 2016
[12]

Marshall, D

J. Marshall, D. Venturelli, I. Hen, and E. G. Rieffel, Phys. Rev. Appl. 11, 044083 (2019)

work page 2019
[13]

Marshall, E

J. Marshall, E. G. Rieffel, and I. Hen, Phys. Rev. Appl. 8, 064025 (2017)

work page 2017
[14]

Sandt and R

R. Sandt and R. Spatschek, Sci. Rep. 13, 6754 (2023)

work page 2023
[15]

Vuffray, C

M. Vuffray, C. Coffrin, Y. A. Kharkov, and A. Y. Lokhov, PRX Quantum 3, 020317 (2022)

work page 2022
[16]

Matsuda, H

Y. Matsuda, H. Nishimori, and H. G. Katzgraber, New J. Phys. 11, 073021 (2009)

work page 2009
[17]

Liu and J

Q. Liu and J. Lee, in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics , Pro- ceedings of Machine Learning Research, Vol. 54 (PMLR,

work page
[18]

Hodgkinson, R

L. Hodgkinson, R. Salomone, and F. Roosta, arXiv (2020), 2001.09266 [math.ST]

work page arXiv 2020
[19]

Pelofske, J

E. Pelofske, J. Golden, A. B¨ artschi, D. O’Malley, and S. Eidenbenz, in 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE,

work page 2021
[20]

J. Yang, Q. Liu, V. Rao, and J. Neville, in Proceedings of the 35th International Conference on Machine Learn- ing, Proceedings of Machine Learning Research, Vol. 80 (PMLR, 2018) pp. 5561–5570

work page 2018
[21]

Rahimi and B

A. Rahimi and B. Recht, Adv. Neural Inf. Process. Syst. 20 (2007)

work page 2007
[22]

Kivinen and M

J. Kivinen and M. K. Warmuth, Inform. and Comput. 132, 1 (1997)

work page 1997
[23]

Dwavesystems/minorminer,

“Dwavesystems/minorminer,” https://github.com/ dwavesystems/minorminer, accessed: 2023-08-03

work page 2023
[24]

M. S. Andersen, J. Dahl, L. Vandenberghe, et al., Avail- able at cvxopt.org 54 (2013)

work page 2013
[25]

S. Aoki, H. Hara, and A. Takemura, Markov bases in algebraic statistics (Springer Science & Business Media, 2012)

work page 2012
[26]

Inagaki, Y

T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Ta- mate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K. Aihara, K.-I. Kawarabayashi, K. Inoue, S. Utsunomiya, and H. Takesue, Science 354, 603 (2016)

work page 2016
[27]

Z. Mao, Y. Matsuda, R. Tamura, and K. Tsuda, Digital Discovery 2, 1098 (2023)

work page 2023

[1] [1]

Binder and A

K. Binder and A. P. Young, Rev. Mod. Phys. 58, 801 (1986)

work page 1986

[2] [2]

Binder and E

K. Binder and E. Luijten, Phys. Rep. 344, 179 (2001)

work page 2001

[3] [3]

Zhang, S

N. Zhang, S. Ding, J. Zhang, and Y. Xue, Neurocom- 5 puting 275, 1186 (2018)

work page 2018

[4] [4]

R. G. Melko, G. Carleo, J. Carrasquilla, and J. I. Cirac, Nat. Phys. 15, 887 (2019)

work page 2019

[5] [5]

Doucet, N

A. Doucet, N. De Freitas, N. J. Gordon, et al., Sequential Monte Carlo methods in practice (Springer, 2001)

work page 2001

[6] [6]

Hukushima and K

K. Hukushima and K. Nemoto, J. Phys. Soc. Japan 65, 1604 (1996)

work page 1996

[7] [7]

Iba, Int

Y. Iba, Int. J. Mod. Phys. C 12, 623 (2001)

work page 2001

[8] [8]

Hukushima and Y

K. Hukushima and Y. Iba, AIP Conference Proceedings 690, 200 (2003)

work page 2003

[9] [9]

M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Jo- hansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, Nature 473, 194 (2011)

work page 2011

[10] [10]

Nelson, M

J. Nelson, M. Vuffray, A. Y. Lokhov, T. Albash, and C. Coffrin, Phys. Rev. Applied 17, 044046 (2022)

work page 2022

[11] [11]

Raymond, S

J. Raymond, S. Yarkoni, and E. Andriyash, Frontiers in ICT 3 (2016)

work page 2016

[12] [12]

Marshall, D

J. Marshall, D. Venturelli, I. Hen, and E. G. Rieffel, Phys. Rev. Appl. 11, 044083 (2019)

work page 2019

[13] [13]

Marshall, E

J. Marshall, E. G. Rieffel, and I. Hen, Phys. Rev. Appl. 8, 064025 (2017)

work page 2017

[14] [14]

Sandt and R

R. Sandt and R. Spatschek, Sci. Rep. 13, 6754 (2023)

work page 2023

[15] [15]

Vuffray, C

M. Vuffray, C. Coffrin, Y. A. Kharkov, and A. Y. Lokhov, PRX Quantum 3, 020317 (2022)

work page 2022

[16] [16]

Matsuda, H

Y. Matsuda, H. Nishimori, and H. G. Katzgraber, New J. Phys. 11, 073021 (2009)

work page 2009

[17] [17]

Liu and J

Q. Liu and J. Lee, in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics , Pro- ceedings of Machine Learning Research, Vol. 54 (PMLR,

work page

[18] [18]

Hodgkinson, R

L. Hodgkinson, R. Salomone, and F. Roosta, arXiv (2020), 2001.09266 [math.ST]

work page arXiv 2020

[19] [19]

Pelofske, J

E. Pelofske, J. Golden, A. B¨ artschi, D. O’Malley, and S. Eidenbenz, in 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE,

work page 2021

[20] [20]

J. Yang, Q. Liu, V. Rao, and J. Neville, in Proceedings of the 35th International Conference on Machine Learn- ing, Proceedings of Machine Learning Research, Vol. 80 (PMLR, 2018) pp. 5561–5570

work page 2018

[21] [21]

Rahimi and B

A. Rahimi and B. Recht, Adv. Neural Inf. Process. Syst. 20 (2007)

work page 2007

[22] [22]

Kivinen and M

J. Kivinen and M. K. Warmuth, Inform. and Comput. 132, 1 (1997)

work page 1997

[23] [23]

Dwavesystems/minorminer,

“Dwavesystems/minorminer,” https://github.com/ dwavesystems/minorminer, accessed: 2023-08-03

work page 2023

[24] [24]

M. S. Andersen, J. Dahl, L. Vandenberghe, et al., Avail- able at cvxopt.org 54 (2013)

work page 2013

[25] [25]

S. Aoki, H. Hara, and A. Takemura, Markov bases in algebraic statistics (Springer Science & Business Media, 2012)

work page 2012

[26] [26]

Inagaki, Y

T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Ta- mate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K. Aihara, K.-I. Kawarabayashi, K. Inoue, S. Utsunomiya, and H. Takesue, Science 354, 603 (2016)

work page 2016

[27] [27]

Z. Mao, Y. Matsuda, R. Tamura, and K. Tsuda, Digital Discovery 2, 1098 (2023)

work page 2023