REVIEW 3 major objections 4 minor 52 references
Permutation Matrix Representation Quantum Monte Carlo
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A single QMC algorithm, built from permutation matrices, can sample the partition functions of arbitrary finite-dimensional Hamiltonians without Trotter error.
desk verdict A well-built QMC framework that deserves refereeing, but the ergodicity claim for the length-two update set is asserted, not proved, and the headline speedup would be stronger with an exact-baseline check. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the permutation matrix representation of Hamiltonians, $H = \sum_j D_j P_j$, together with the identity that expresses each off-diagonal configuration's weight as an exponential of the divided differences of the classical energies along the walk. In PMR, a configuration is a pair $(|z\rangle, S_{i_q})$ where $S_{i_q}$ is a product of off-diagonal permutation operators whose product is the identity; the states $|z_j\rangle$ visited by the walk generate a multiset of classical energies. The divided-difference exponential $e^{-\beta[E_{z_0},...,E_{z_q}]}$ is what replaces the infinite series over diagonal insertions, making the method Trotter-error-free and parameter-free, and it is what turns the partition function into a sum of generalized Boltzmann weights. The four update moves—classical moves, cyclic rotations, block swaps, and cycle completion—are all formulated directly in the permutation group.
What would settle it
Enumerate all identity-closed permutation-walk configurations up to a fixed length for a small model, draw the graph whose vertices are configurations and whose edges are the paper's four update moves, and test whether every configuration is reachable from every other; if any component is disconnected, PMR-QMC cannot be ergodic. A complementary test is to compare PMR-QMC thermal averages with exact diagonalization on a small transverse-field Ising model and look for systematic bias.
Extended reading notes
Core claim
The central discovery is that the partition function of any Hamiltonian representable as $H = \sum_j D_j P_j$, with $D_j$ diagonal and $P_j$ permutation matrices in the computational basis, can be written exactly as a sum over closed permutation walks. The derivation starts from the Taylor expansion of $e^{-\beta H}$, groups terms into sequences of off-diagonal operators, and collapses the sum over diagonal insertions using divided differences. The result is $Z = \sum_z \sum_{S_{i_q} = 1} D(z,S_{i_q}) e^{-\beta[E_{z_0},...,E_{z_q}]}$, where each configuration contributes a real generalized Boltzmann weight and the sequence $S_{i_q}$ must multiply to the identity. The paper then constructs a Markov chain over these configurations using four update moves and derives estimators for diagonal and off-diagonal observables, including products of off-diagonal operators. It uses the same machinery to show that the sign problem is controlled by closed-walk signs rather than by the sign of individual off-diagonal matrix elements, and it demonstrates the method's performance on transverse-field Ising benchmarks.
Load-bearing premise
The method's correctness rests on the update moves being able to reach every closed permutation-walk configuration that contributes to the partition function, an ergodicity claim the paper asserts for its length-two subsequence moves without proof.
Editorial extensions
If this is right
- A single PMR-QMC implementation can be applied to Hamiltonians with single-body, two-body, or higher-body off-diagonal terms, to bosonic models, and to purely classical Hamiltonians, without model-specific update rules.
- Because the expansion is Trotter-error-free and parameter-free, the only approximation is statistical sampling; no extrapolation over an imaginary-time step or coupling parameter is required.
- The sign-problem criterion implies that some non-stoquastic Hamiltonians remain sign-problem-free, and some stoquastic-looking ones may not be; the test is the sign of closed permutation walks, not the sign of matrix entries.
- On the random 3-regular MAX2SAT transverse-field benchmarks, PMR reaches converged thermal averages within seconds in cases where stochastic series expansion does not finish within 24 hours.
- For transverse-field Ising models with random XX interactions, the method yields thermal data without special cluster updates, and the data show that an XX catalyst reduces the dependence of diagonal energy on graph degree.
Reading between the lines
- If the ergodicity assumption holds in general, the same update grammar should extend to fermionic or hard-core boson models by choosing the appropriate permutation group, where the closed-walk sign criterion may give a constructive test for sign-problem-free simulations.
- The bundling of infinitely many SSE weights into a single divided-difference weight suggests the speedup over SSE should grow when classical energy spectra are degenerate; this can be tested by comparing runtime scaling on models with tunable degeneracy.
- One could use the closed-walk sign criterion as a design tool: engineering a Hamiltonian's permutation group to forbid odd-length negative cycles would guarantee sign-problem-free sampling even for non-stoquastic interactions.
- A practical check of the method's robustness would be to run PMR-QMC with the length-two moves against exact diagonalization on small frustrated instances, and to measure the integrated autocorrelation time of the expansion order $q$.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a quantum Monte Carlo framework, PMR-QMC, built on casting Hamiltonians as sums of generalized permutation matrices and expanding the partition function in off-diagonal terms. The central formal result is a partition-function identity in which all weights are expressed as products of hopping strengths and divided-difference exponentials of classical energies, closing over permutation words that reduce to the identity. The authors argue the method is parameter-free and Trotter error-free, and they demonstrate its flexibility by simulating transverse-field Ising models and an Ising model with random XX interactions, comparing runtime favorably against stochastic series expansion. They also use the framework to discuss when non-stoquastic Hamiltonians exhibit sign problems. The paper claims four or more orders of magnitude speedup over SSE on random 3-regular MAX2SAT instances, and presents thermal results for the XX-augmented model.
Significance. If the central claims hold, PMR-QMC is a significant methodological contribution: it provides a single update/measurement framework for arbitrary finite-dimensional Hamiltonians, avoids Trotter error, and bundles many SSE configurations into single weights, leading to large runtime advantages on the stoquastic testbed. The divided-difference machinery is inherited from the authors' prior published work, but the PMR generalization, the closed-walk interpretation of the sign problem, and the demonstration on XX-interacting models are new. The paper also gives constructive proof (Appendix A) that any finite-dimensional matrix admits a PMR decomposition, and the machine-checkable identity in Eqs. (10)-(19) is a genuine strength. Caveats: the claimed generality is tempered by the unproven ergodicity assertion in Sec. VI B and by the lack of a convergence diagnostic in the numerical studies.
major comments (3)
- [Sec. VI B, Table I, Figs. 5-6] The assertion that restricting the cycle-completion moves to subsequences of length two 'is enough to ensure ergodicity' is load-bearing but unproved. The partition-function identity (19) sums over all closed permutation words, so the Markov chain must be irreducible on every configuration with positive weight. The listed moves i)-v) in Table I are plausible generators, but no argument is given that they connect all configurations for arbitrary insertion positions, and no autocorrelation or exact-baseline convergence check is reported. A disconnected sampling space would produce systematically wrong thermal averages while still yielding a plausible-looking runtime comparison, so this issue needs either a proof or a numerical diagnostic (e.g., comparison against exact diagonalization on small instances, or a test that the estimator is independent of the initial configuration).
- [Sec. V C 4 (cycle completion) and Sec. VI B] The cycle-completion update as described in the text and Table I involves replacing a length-two subcycle by its complement, e.g., XiXk -> XiXj, XjXk, which changes q by +1, and the inverse operation changes q by -1. For the q-change to be reversible and detailed-balanced, the intermediate group element XjXk must be a valid permutation in the group (with zero Hamiltonian weight if not present in H, as the authors state in Sec. V A). However, the text does not specify how the lookup table of subcycles is generated, nor how the zero-weight group elements are handled when they are used as intermediates. Since the acceptance probability in Eq. (23) involves only the weight ratio, a zero-weight intermediate would be sampled with probability zero, so the move would be effectively rejected. The paper should clarify how the update scheme avoids this and how the ergodicity claim accounts for zero-weight intermediates.
- [Sec. III, Eqs. (15)-(19), Sec. IV] The formal derivation of the partition function expansion is coherent, but the treatment of the complex-to-real weight replacement needs more care. In Sec. III the authors state that imaginary contributions cancel because for every configuration C there is a conjugate configuration Cbar with weight W_barC = conj(W_C), and then 'we may therefore redefine D(z,S_iq) = Re[prod_j d^(i_j)_z_j], obtaining strictly real-valued weights.' This replacement is only valid if the real part is the correct weight for the partition function, which requires the imaginary parts to cancel exactly in the sum over configurations. The cancellation is asserted, not proved, and for a finite sample of configurations the real-part sum and the true partition function need not coincide unless the multiset of configurations is closed under conjugation. The authors should provide a proof or a more careful statement that the sampling of Re[W_c] reproduces Z.
minor comments (4)
- [Sec. VI A, Figs. 3-4] The runtime comparison is presented as a wall-clock-time plot, but no details are given about the implementation of SSE, the number of seeds, the hardware, or the precise stopping criterion for the 24-hour window. These details are needed to make the speedup claim reproducible.
- [Sec. V D, Eqs. (29)-(36)] The notation for the improved measurements is dense, and the indices in Eqs. (33)-(36) are not all defined explicitly (e.g., the meaning of z' in Eq. (36) and the ranges of j in the sums over rotated configurations). A clearer derivation or a worked example would help the reader verify the measurement estimators.
- [Sec. II D (Bose-Hubbard)] The Bose-Hubbard example states that the operators P_<i,j> = b_i^dagger b_j are permutation matrices in the number basis, but these operators are not permutations in the usual finite-dimensional sense because they act on an infinite-dimensional space and annihilate the vacuum. The authors should clarify that this is an infinite-dimensional analog and that the PMR decomposition in Appendix A is only proved for finite-dimensional matrices.
- [Sec. VI B, par. after Eq. (37)] The phrase 'we restrict to subsequences of length two which is enough to ensure ergodicity' is followed by a Table I that lists five move types; the table caption says 'Cycle completion moves', but moves iv) and iii) do not change q and are more naturally classified as swaps or contractions. The terminology should be aligned.
Circularity Check
No significant circularity: the partition-function expansion is a re-derived mathematical identity, the numerical benchmarks are empirical rather than fitted, and the unproven ergodicity assertion is an algorithmic assumption, not a circular reduction.
full rationale
The paper's central identity, Eq. (15) and Eq. (19), is obtained by expanding exp(-beta H) in a Taylor series and regrouping diagonal contributions into divided differences. Although the divided-difference simplification and the positivity statement are cited to the authors' prior Refs. [13,14], those are published, parameter-free mathematical lemmas whose stated assumptions do not include the present results, and the paper itself displays the derivation from Eq. (7) through Eq. (19). No fitted parameter is renamed as a prediction: the PMR-versus-SSE runtime comparison is an empirical benchmark, and the XX-model observations in Sec. VI B are direct QMC estimates with no parameter fitted to the plotted data. The one load-bearing assertion that is not proved is the ergodicity claim in Sec. VI B: 'For our updates, we restrict to subsequences of length two which is enough to ensure ergodicity.' The paper provides no proof, autocorrelation diagnostic, or exact-baseline check sensitive to a disconnected sampling space. That is a genuine correctness risk, but it is not a circular step: the algorithm's correctness does not reduce by construction to its inputs, nor does it rest on a self-citation chain that already contains the conclusion. Accordingly the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- standard math Any finite-dimensional matrix can be decomposed into a sum of generalized permutation matrices as in Eq. (1).
- standard math The off-diagonal partition function expansion with divided differences, Eq. (15), is valid and the factor (-1)^q times the divided difference of e^{-beta x} is strictly positive.
- domain assumption The Markov chain updates, in particular the restriction to length-two subsequences, are ergodic over all closed permutation walks contributing to Z.
- domain assumption Complex-valued weights can be replaced by their real parts because conjugate configurations cancel exactly in the partition function.
Cite this review
Pith. "Pith review of Permutation Matrix Representation Quantum Monte Carlo." pith.science (2026). https://pith.science/paper/VKY5YS7M
@misc{pith2026190803740,
author = {Pith},
title = {Pith review of: Permutation Matrix Representation Quantum Monte Carlo},
year = {2026},
howpublished = {\url{https://pith.science/paper/VKY5YS7M}},
note = {Machine review of arXiv:1908.03740}
}
read the original abstract
We present a quantum Monte Carlo algorithm for the simulation of general quantum and classical many-body models within a single unifying framework. The algorithm builds on a power series expansion of the quantum partition function in its off-diagonal terms and is both parameter-free and Trotter error-free. In our approach, the quantum dimension consists of products of elements of a permutation group. As such, it allows for the study of a very wide variety of models on an equal footing. To demonstrate the utility of our technique, we use it to clarify the emergence of the sign problem in the simulations of non-stoquastic physical models. We showcase the flexibility of our algorithm and the advantages it offers over existing state-of-the-art by simulating transverse-field Ising model Hamiltonians and comparing the performance of our technique against that of the stochastic series expansion algorithm. We also study a transverse-field Ising model augmented with randomly chosen two-body transverse-field interactions.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Classical moves Classical moves are any moves that involve a ma- nipulation of the classical state|z⟩ while leaving Siq unchanged [see Fig. 2(a)]. In a single bit-flip clas- sical move, a spin from the classical bit-string state |z⟩ ofC is picked randomly and is flipped, generating a state|z′⟩ and hence a new configuration C′. Cal- culating the weight of C′ ...
-
[2]
Cyclic rotations The ‘cyclic rotation’ move, [Fig. 2(b)], consists of identifying short sub-sequences, or cycles, of consec- utive operators in the sequence Siq, whose product is the identity element, i.e., sub-sequences that obey Pij··· Pij+C = 1. (24) Depending on the nature of the operators, preparing a lookup table of short cycles that evaluate to the...
-
[3]
2(c)] is an update that in- volves a change of the classical state z
Block-swap A block swap [Fig. 2(c)] is an update that in- volves a change of the classical state z. Here, a random position k in the product Siq is picked such that the product is split into two (non-empty) sub- sequences, Siq = S2S1, with S1 = Pik··· Pi1 and S2 = Piq··· Pik+1. The classical state |z′⟩ at posi- tion k in the product is given by |z′⟩ =S1|z...
-
[4]
The cycle completion move has the effect of changing the value of q
Cycle completion The moves presented so far have left the number of group elements in the sequence, or expansion order, namely q, unchanged. The cycle completion move has the effect of changing the value of q. A lookup table of short cycles obeying Pij··· Pij+C = 1 (27) will be helpful in this case. The cycle completion move identifies a sub-cycle in the se...
-
[5]
Diagonal measurements A diagonal operator Λ obeys Λ |z⟩ = λ(z)|z⟩ where λ(z) is a number that depends both on the operator and the state it acts on. Since ⟨z|ΛSiq|z⟩ = λ(z)⟨z|Siq|z⟩, for any given configura- tionC = (|z⟩,S iq), there is a contribution λ = λ(z) to the diagonal operator thermal average ⟨Λ⟩. To improve statistics, one may also consider rotati...
-
[6]
Off-diagonal measurements We next consider the case of measuring the expec- tation value of an off-diagonal operator Pk, namely, 9 ⟨Pk⟩. To do this, we interpret the instantaneous con- figuration as follows WC =D(z,Siq )e−β[EC]⟨z|Siq|z⟩ = ( diqe−β[EC] e−β[EC′] ) × [ D(z,Siq−1)e−β[EC′]⟨z|Siq−1Piq|z⟩ ] , (32) where C′ is the configuration associated with the mu...
-
[7]
Products of off-diagonal measurements The sampling of expectation values of the form ⟨Pk1Pk2⟩ proceeds very similarly to the single op- erator case except that now both operators must appear at the end of the sequence. The argument proceeds similarly to the single off-diagonal mea- surement, and we have that the contribution to the expectation value of⟨Pk1P...
-
[8]
Improved measurements As will often happen, certain physical operators will have more than one representation as group el- ement. E.g., if P3 =P1P2, one could measure both the single operator ⟨P3⟩ and the operator product ⟨P1P2⟩ and combine the results. VI. RESULTS In this section we present some results that high- light some of the advantages that PMR ha...
Show all 52 references
-
[9]
Landau and K
D. Landau and K. Binder, A Guide to Monte Carlo Simulations in Statistical Physics (Cambridge Uni- versity Press, New York, NY, USA, 2005)
2005
-
[10]
M. N. . G. Barkema, Monte Carlo Methods in Sta- tistical Physics (Oxford Uinversity Press, 1999)
1999
-
[11]
Aspuru-Guzik, A
A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-Gordon, Science 309, 1704 (2005)
2005
-
[12]
Kassal, S
I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, and A. Aspuru-Guzik, Proceedings of the National Academy of Sciences 105, 18681 (2008)
2008
-
[13]
B. P. Lanyon, J. D. Whitfield, G. G. Gillett, M. E. Goggin, M. P. Almeida, I. Kassal, J. D. Biamonte, M. Mohseni, B. J. Powell, M. Barbieri, A. Aspuru- Guzik, and A. G. White, Nature Chemistry 2, 106 EP (2010)
2010
-
[14]
Lonardoni, F
D. Lonardoni, F. Pederiva, and S. Gandolfi, Journal of Physics: Conference Series 529, 012012 (2014)
2014
-
[15]
Chandrasekharan and U.-J
S. Chandrasekharan and U.-J. Wiese, Phys. Rev. Lett. 83, 3116 (1999)
1999
-
[16]
T. D. Kieu and C. J. Griffin, Phys. Rev. E 49, 3855 (1994)
1994
-
[17]
A. W. Sandvik, J. Phys, A 25, 3667 (1992)
1992
-
[18]
A. W. Sandvik, Phys. Rev. B 59, R14157 (1999)
1999
-
[19]
N. V. Prokof’ev, B. V. Svistunov, and I. S. Tupitsyn, Journal of Experimental and Theoretical Physics 87, 310 (1998)
1998
-
[20]
Mazzola and M
G. Mazzola and M. Troyer, Journal of Statistical Mechanics: Theory and Experiment 2017, 053105 (2017)
2017
-
[21]
Albash, G
T. Albash, G. Wagenbreth, and I. Hen, Phys. Rev. E 96, 063309 (2017)
2017
-
[22]
Hen, Journal of Statistical Mechanics: Theory and Experiment 2018, 053102 (2018)
I. Hen, Journal of Statistical Mechanics: Theory and Experiment 2018, 053102 (2018)
2018
-
[23]
D. C. Handscomb, Proc. Camb. Phil. Soc. 58, 594598 (1962)
1962
-
[24]
D. C. Handscomb, Proc. Camb. Phil. Soc. 60, 115122 (1964)
1964
-
[25]
A. W. Sandvik and J. Kurkij¨ arvi, Phys. Rev. B43, 5950 (1991)
1991
-
[26]
A. W. Sandvik, Phys. Rev. E 68, 056701 (2003)
2003
-
[27]
J. A. Barker, The Journal of Chemical Physics 70, 2914 (1979), https://doi.org/10.1063/1.437829
1979 doi
-
[28]
Joyner, Adventures in group theory
D. Joyner, Adventures in group theory. Rubik’s cube, Merlin’s machine, and other mathematical toys (Baltimore, MD: Johns Hopkins University Press, 2008)
2008
-
[29]
Lewenstein, A
M. Lewenstein, A. Sanpera, and V. Ahufinger, Ul- tracold Atoms in Optical Lattices: Simulating quan- tum many-body systems (OUP Oxford, 2012)
2012
-
[30]
M. P. A. Fisher, P. B. Weichman, G. Grinstein, and D. S. Fisher, Phys. Rev. B 40, 546 (1989)
1989
-
[31]
Jaksch and P
D. Jaksch and P. Zoller, Annals of Physics 315, 52 (2005), special Issue
2005
-
[32]
Giamarchi, C
T. Giamarchi, C. R¨ uegg, and O. Tchernyshyov, Na- ture Physics 4, 198 (2008), arXiv:0712.2250 [cond- mat.str-el]
2008 arXiv
-
[33]
Hen, Phys
I. Hen, Phys. Rev. E 99, 033306 (2019)
2019
-
[34]
E. T. Whittaker and G. Robinson, in The Calculus of Observations: A Treatise on Numerical Mathe- matics (New York: Dover, New York, 1967)
1967
-
[35]
de Boor, Surveys in Approximation Theory 1, 46 (2005)
C. de Boor, Surveys in Approximation Theory 1, 46 (2005)
2005
-
[36]
Bravyi, D
S. Bravyi, D. P. DiVincenzo, R. I. Oliveira, and B. M. Terhal, Quant. Inf. Comp. 8, 0361 (2008)
2008
- [37]
-
[38]
Marvian, D
M. Marvian, D. A. Lidar, and I. Hen, Nature Com- munications 10, 1571 (2019)
2019
-
[39]
Gupta and I
L. Gupta and I. Hen, Advanced Quantum Technolo- gies 2, 1900108 (2019)
2019
-
[40]
Zivcovich, Dolomites Research Notes on Approx- imation 12, 28 (2019)
F. Zivcovich, Dolomites Research Notes on Approx- imation 12, 28 (2019)
2019
-
[41]
Gupta, L
L. Gupta, L. Barash, and I. Hen, Com- puter Physics Communications 254 (2020), 10.1016/j.cpc.2020.107385
2020
-
[42]
Farhi, D
E. Farhi, D. Gosset, I. Hen, A. W. Sandvik, P. Shor, A. P. Young, and F. Zamponi, Phys. Rev. A 86, 052334 (2012)
2012
-
[43]
Hukushima and K
K. Hukushima and K. Nemoto, J. Phys. Soc. Japan 65, 1604 (1996), arXiv:cond-mat/9512035
1996 arXiv
-
[44]
Marinari, G
E. Marinari, G. Parisi, and J. J. Ruiz-Lorenzo, in Spin Glasses and Random Fields , edited by A. P. Young (World Scientific, Singapore, Singa- pore, 1998) p. 59, (arXiv:cond-mat/9701016)
1998 arXiv
-
[45]
Hen and A
I. Hen and A. P. Young, Phys. Rev. E 84, 061152 14 (2011)
2011
-
[46]
Kadowaki and H
T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355 (1998)
1998
-
[47]
G. A. Durkin, Phys. Rev. A 99, 032315 (2019)
2019
-
[48]
Albash, Phys
T. Albash, Phys. Rev. A 99, 042334 (2019)
2019
-
[49]
Crosson, E
E. Crosson, E. Farhi, C. Yen-Yu Lin, H.-H. Lin, and P. Shor, ArXiv e-prints (2014), arXiv:1401.7320 [quant-ph]
2014 arXiv
-
[50]
Hormozi, E
L. Hormozi, E. W. Brown, G. Carleo, and M. Troyer, Phys. Rev. B 95, 184416 (2017)
2017
-
[51]
Nishimori and K
H. Nishimori and K. Takada, Frontiers in ICT 4, 2 (2017)
2017
-
[52]
Appendix A: Finite dimensional permutation matrix representations To show that any finite-dimensional matrix can be written in the form of Eq
Rotman, An Introduction to the Theory of Groups (New York: Springer-Verlag, 1995). Appendix A: Finite dimensional permutation matrix representations To show that any finite-dimensional matrix can be written in the form of Eq. (1), we will make use of ‘cycle notation’ [44] — a c...
1995
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.