Introduction
Formally, a quantum phase transition (QPT) is defined by nonanalytic behavior of a system’s ground-state energy in the thermodynamic limit [1 ] . Traditionally, QPTs are analyzed using local order parameters, such the average local magnetization in the transverse-field Ising model (TFIM) [1 ] . However, identifying a suitable local order parameter for a new model is often challenging—and for topological QPTs, it is entirely infeasible [2 , 3 ] . Consequently, substantial effort has been devoted to developing generic methods for studying QPTs that do not rely on prior knowledge of an order parameter [4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 20 , 21 , 22 ] [17, 18, 19]. Nevertheless, these approaches still rely on manually encoding subtle, system-specific prior knowledge. Building on recent advancements in quantum Monte Carlo (QMC) methods [23 , 24 , 25 ] [26] and the well-established fidelity-based approach to QPTs [4 , 22 ] [17, 18, 19], we propose an automated, order-parameter-free, black-box method for studying QPTs that requires no manual encoding of system-specific details.
More precisely, we derive QMC estimators for energy susceptibility (ES) [27 , 28 ] [18] and fidelity susceptibility (FS) [4 , 9 ] [17, 18, 19, 29], which can identify quantum critical points in QPTs without relying on order parameters. While related estimators have appeared in other QMC frameworks [17–19], our derivations and resulting estimators are developed within the relatively recent permutation matrix representation QMC (PMR-QMC), which offers several key advantages over earlier methods [23 , 24 , 25 ] [26, 30, 31, 32]. Most relevant to this work, it was recently shown that ergodic PMR-QMC update rules satisfying detailed balance can be generated via a deterministic, automated algorithm for essentially arbitrary Hamiltonians [23 , 24 , 25 ] . Furthermore, our estimators are applicable to arbitrarily complex driving terms, as we demonstrate in this work. To the best of our knowledge, neither of these capabilities was supported by previous approaches. Taken together, these features allow our method to be applied directly to a wide range of systems without the need to manually encode laborious, system-specific details.
To this end, we apply our approach to estimate ES and FS in three spin systems: a 2D TFIM model, a 2D XXZ model, and a 100-spin model with random Pauli operator terms that—to our knowledge—cannot be studied using any other method. Given any spin-1/2 Hamiltonian expressed as a sum of Pauli operator products, our current implementation [33] can attempt to locate quantum critical points by estimating ES and/or FS. As with any QMC method, our approach may encounter convergence issues due to frustration or the sign problem [34 , 35 ] , which can sometimes be mitigated with custom QMC updates [36 , 37 ] or other techniques [34 , 35 , 38 , 39 , 40 , 41 , 42 ] . For the three models studied in this work, however, no manual, system-specific adjustments were required to ensure convergence. In all cases, our code automatically monitors the severity of the sign problem [23 , 43 ] and performs thermalization and autocorrelation diagnostics to ensure reliable estimates.
Our implementation [33] builds upon preexisting open-source code for arbitrary spin-1/2 models [43 ] . Since our estimators are derived within the general PMR-QMC framework, which can represent arbitrary Hamiltonians [26, 30], they can readily be ported to any existing or future PMR-QMC codebases. At present, this includes Bose-Hubbard models on arbitrary graphs [24 ] , arbitrary spin-1/2, high-, and mixed-spin systems [23 , 25 ] , and fermionic systems [25 , 44 ] . In summary, PMR-QMC can automatically generate QMC moves for essentially any Hamiltonian [23 , 24 , 25 ] , and in this work, we derive generic ES and FS estimators within this framework. Combined with automatic convergence diagnostics, our approach—unlike previous numerical methods—can reliably be used as a black-box tool for studying QPTs.
Results
Before deriving formal estimators in Section IV, we demonstrate our method through a series of numerical experiments using open source PMR-QMC code [33] that builds upon prior work [23 , 43 ] (see Section A for basics of PMR-QMC and Section B for basic code instructions). Each model is a spin-1/2 system defined in terms of the standard Pauli operators X X X , Y Y Y , and Z Z Z .
We use the notation for the ES χ E \chi_E χ E and the FS χ F \chi_F χ F as defined in “Theoretical background: Energy and fidelity susceptibilities” in Section IV; the PMR-QMC conventions follow “PMR-QMC background and notation” also in Section IV. X i X_i X i , Y i Y_i Y i , and Z i Z_i Z i denote Pauli X X X , Y Y Y , and Z Z Z operators acting on spin i i i , respectively. All error bars and continuous error bands estimate the spread of the plotted quantity over independent QMC runs: Either 2 σ 2\sigma 2 σ (for thermal averages) or direct 95% percentile intervals (for wall-clock times).
We begin with illustrative experiments on well-known models, emphasizing agreement with expected results and, where applicable, reproducing prior plots [18, 19]. We then present a more challenging experiment involving an ensemble of random models, for which our approach still accurately estimates ES and FS. Notably, for this latter case, we are unaware of any other method capable of studying the model successfully. Yet, our single code can handle all of these models with only straightforward adjustments to input files [33].
A simple two spin model
We begin by studying,
H ( λ ) = Z 1 Z 2 + γ ( X 1 + X 2 ) + λ ( Z 1 + Z 2 ) , (1) H(\lambda) = Z_1 Z_2 + \gamma(X_1 + X_2) + \lambda(Z_1 + Z_2), \tag*{(1)} H ( λ ) = Z 1 Z 2 + γ ( X 1 + X 2 ) + λ ( Z 1 + Z 2 ) , (1)
first introduced and studied in a quantum sensing experiment on an NMR system via the fidelity approach (we choose γ = 0.1 \gamma= 0.1 γ = 0.1 ) [45 ] . By design, this model exhibits an avoided level crossing near the critical points λ ≈ ± 1 \lambda\approx\pm1 λ ≈ ± 1 , where the ES and FS are expected to peak. Our QMC approach correctly locates these peaks by computing the FS as shown in Figure 1 . In fact, as shown, our
Figure 1. FS for the two spin model, Eq. (1) , considered in Ref. [45 ] for different inverse temperatures, β \beta β . Data from QMC are averaged over 5 independent random seeds, whereas direct numerical calculations are shown as lines.
approach correctly matches direct numerical calculations for each temperature tested. Furthermore, our plot shows expected convergence of χ F β → χ F \chi_F^\beta\to\chi_F χ F β → χ F as β → ∞ \beta\to\infty β → ∞ . At β = 20 \beta= 20 β = 20 specifically, the QMC results closely match the exactly computed T = 0 T = 0 T = 0 results. This verifies the basic veracity of our method.
Next, we remark that prior QMC approaches are generally incapable of estimating the FS, as they must typically restrict themselves to models for which H 1 ∝ diag ( H ) H_1 \propto\operatorname{diag}(H) H 1 ∝ diag ( H ) or H 1 ∝ H − diag ( H ) H_1 \propto H - \operatorname{diag}(H) H 1 ∝ H − diag ( H ) [22 ] [17, 18, 19]. Despite the simplicity of this model, it does not satisfy this condition. Yet, our method easily handles this model without even needing to write a specialized code for this case.
A square lattice TFIM
Secondly, we consider the well-known and extensively studied [18, 46, 47] transverse-field Ising model (TFIM),
H T F I M ( h ) = H J + h H h = − ∑ ⟨ i , j ⟩ X i X j − h ∑ i = 1 n Z i , (2) H_{\mathrm{TFIM}}(h)=H_J+hH_h=-\sum_{\langle i,j\rangle}X_iX_j-h\sum_{i=1}^{n}Z_i, \tag*{(2)} H TFIM ( h ) = H J + h H h = − ⟨ i , j ⟩ ∑ X i X j − h i = 1 ∑ n Z i , (2)
on a square lattice with periodic boundary conditions (PBC). For our purposes, we focus our efforts on a simple 4 × 4 4 \times4 4 × 4 model at fixed h = 1 h=1 h = 1 and compute the ES and FS as a function of inverse temperature for either H J H_J H J or h H h hH_h h H h as the “driving term.” Notably, these results are actually not unconditional ES and FS as defined in Eqs. (20) and (21) , but rather, the result of restricting computations only to the positive parity subspace of the TFIM. We refer interested readers to Section C for details on this methodological trick, but we remark that our approach is a non-trivial convenience of PMR-QMC that highlights its versatility.
The results are shown in Figure 2 and demonstrate three things. Firstly, they showcase the ability of our method to consider different driving term choices as well as compute things in a fixed parity subspace. Secondly, they help verify the correctness of our approach, as the FS plot correctly matches results independently calculated with SSE-QMC [18]. Finally, they correctly reveal an expected feature of the ES and FS. Namely, one might naively expect that, for the purposes of detecting a quantum critical point, one is free to view either the static term H J H_J H J or the driving term h H h hH_h h H h in Eq. (2) as the perturbation.
Figure 2. We compute ES and FS restricted to the positive parity subspace (see Section C) of a 4 × \times × 4 square TFIM with PBC and h = 1 h = 1 h = 1 as a function of β \beta β . QMC data are averaged over 100 independent runs. Our FS results are consistent with a similar computation performed with SSE-QMC [18].
In the T = 0 T=0 T = 0 limit, this is correct since
χ F , 0 H J = h 2 χ F , 0 h H h , χ E , 0 H J = h 2 χ E , 0 h H h , (3) \chi_{F,0}^{H_J}=h^2\chi_{F,0}^{hH_h}, \qquad\chi_{E,0}^{H_J}=h^2\chi_{E,0}^{hH_h}, \tag*{(3)} χ F , 0 H J = h 2 χ F , 0 h H h , χ E , 0 H J = h 2 χ E , 0 h H h , (3)
follows from plugging in H J = H − h H h H_J=H-hH_h H J = H − h H h into Eqs. (9) and (14) alongside the observation ⟨ ψ n ∣ H ∣ ψ 0 ⟩ = 0 \langle\psi_n|H|\psi_0\rangle=0 ⟨ ψ n ∣ H ∣ ψ 0 ⟩ = 0 for all n ≠ 0 n\ne0 n = 0 . In these plots, we have chosen h = 1 h=1 h = 1 , and correspondingly, we find that both the ES and FS converge for either perturbation choice (H J H_J H J or h H h hH_h h H h ) when β \beta β is large enough. Yet for any finite β \beta β , the relation is less trivial, and in fact, one finds that there is no simple relation that holds across all inverse temperatures [18]. Methodologically, this provides a different way to test for empirical convergence of the finite temperature ES and FS to groundstate values.
So far, we have considered simple models of fixed size. To connect these ideas to the study of QPTs in the infinite system limit, we remark that one can simply compute the ES and FS for increasingly larger system sizes. This is done, for example, in Fig. 4 of Ref. [18]. As expected, this results in an increasingly sharper peak in both the ES and FS as h h h approaches the known critical point h c ≈ 3.044 h_c\approx3.044 h c ≈ 3.044 [47]. In addition, one can perform finite size scaling and data collapse in accordance with expected scaling relations, Eqs. (16) and (17) , to extract the critical exponent ν ≈ 0.6301 \nu\approx0.6301 ν ≈ 0.6301 [18, 46]. Expressed differently, our method is straightforwardly compatible with studying QPTs in the infinite size limit with enough computational effort, which we show more directly for the XXZ model next.
A square lattice XXZ model
Thirdly, we study the antiferromagnetic XXZ model on a square lattice with PBC,
H = J z 4 ∑ ⟨ i , j ⟩ Z i Z j + λ 4 ∑ ⟨ i , j ⟩ ( X i X j + Y i Y j ) , (4) H=\frac{J_z}{4}\sum_{\langle i,j\rangle}Z_iZ_j+\frac{\lambda}{4}\sum_{\langle i,j\rangle}\left(X_iX_j+Y_iY_j\right), \tag*{(4)} H = 4 J z ⟨ i , j ⟩ ∑ Z i Z j + 4 λ ⟨ i , j ⟩ ∑ ( X i X j + Y i Y j ) , (4)
which relates to a hard-core boson model [48, 49] via the Matsubara–Matsuda transformation [50]. The finite-temperature phase diagram of this model has been studied intensely [48], and various facts of this diagram have been replicated by FS approaches with exact diagonalization [51] and SSE-QMC [19]. From a QPT perspective, this model prefers Néel order in the XY plane when λ \lambda λ dominates and an antiferromagnetic Ising groundstate when J z J_z J z dominates. The point λ = J z \lambda=J_z λ = J z is a known quantum critical point known as the Heisenberg point [19, 48]. Furthermore [19, 48], it is known that thermal fluctuations at finite temperature destroy the antiferromagnetic Ising phase at a second-order phase transitions. Fixing λ = 1 \lambda=1 λ = 1 , J z = 1.5 J_z=1.5 J z = 1.5 and varying temperature T T T , one can search for the expected critical point ( T / λ ) c ≈ 0.75 (T/\lambda)_c\approx0.75 ( T / λ ) c ≈ 0.75 [19, 48]. Using the ES and FS, we search for this critical point in Figure 3 , and the empirical peak as we scale system size agrees with expectations. The FS plot in particular is consistent with results obtained in Ref. [19]. More broadly, these experiments show that our method can scale to large system sizes (which are necessary for finite size scaling in the study of QPTs) and also can study finite temperature phase transitions.
Figure 3. We compute ES and FS for the XXZ model in Eq. (4) on a square lattice with PBC as a function of temperature, T T T , for different model sizes. QMC data are averaged over at least 200 independent runs. Our FS results are consistent with a similar computation performed with SSE-QMC [19].
A random ensemble
Finally, we consider an ensemble of random 100-spin Hamiltonians generated by random unitary rotations of Eq. (1) (see Section D for full details of this family). By unitary invariance, observables for these random models agree with the simple two qubit model despite each H U i = U i H ( λ ) U i † H_{U_i}=U_iH(\lambda)U_i^\dagger H U i = U i H ( λ ) U i † and associated driving term U i H 1 U i † U_iH_1U_i^\dagger U i H 1 U i † being quite complicated, containing hundreds of random Pauli terms over 100 spins. Using standard QMC approaches, it is not possible to study this ensemble, but it is straightforward to try in PMR-QMC, and the results agree with known expectations as shown in Figure 4 .
Figure 4. Comparison of QMC estimates with exact values for an ensemble of 100-spin Hamiltonians generated by random rotations of Eq. (1) . Detailed information on the ensemble can be found in Section D. QMC estimates are averaged across 10 random models. In all cases, the QMC estimates show excellent agreement with exact finite β \beta β curves. (a) The imaginary time correlator, G ( τ ) G(\tau) G ( τ ) , has the expected symmetry around β / 2 = 10 \beta/2=10 β /2 = 10 . (b) The ES correctly predicts critical points despite the β = 20 \beta=20 β = 20 curve not quite converging to the β = ∞ \beta=\infty β = ∞ curve. (c) The FS correctly predicts critical points more sharply than ES, and the β = 20 \beta=20 β = 20 curve matches the β = ∞ \beta=\infty β = ∞ curve.
Specifically, PMR-QMC estimators consistently show excellent agreement with exact numerical results for the imaginary-time correlator G ( τ ) G(\tau) G ( τ ) , the ES, and the FS, as shown in Figure 4 . Furthermore, our results confirm established characteristics of these observables; for instance, G ( τ ) G(\tau) G ( τ ) exhibits symmetry about β / 2 \beta/2 β /2 (see Fig. 1 in Ref. [18] and Fig. 7 in Ref. [19]).
Simulation resources and scaling
Numerical demonstrations for Figure 1 and 4, corresponding to studies of Eq. (1) and its random rotations, were performed on a single 2.3 GHz Intel i9 laptop processor. The remaining experiments involving the TFIM and XXZ models (Figure 2 and 3) were executed on a University of Southern California high-performance computing
cluster. The algorithm is highly memory-efficient [23 , 52 ] , with modest requirements even for large-scale simulations (approximately 200 MB of memory per run was sufficient for all calculations reported here). Consequently, our performance analysis focuses primarily on time.
As a QMC method, our approach is naturally suited for lazy parallel execution and exhibits near-perfect strong scaling as the number of cores increases (see, e.g., Fig. 8 of Ref. [23 ] ). Table 1 summarizes the number of MPI threads (N p N_p N p , approximately corresponding to the number of cores) and wall-clock times used to produce the results in Figure 1 to 4. Additional details regarding simulation parameters and computational resources are provided in Section B.
Table 1. We summarize the resources used to generate data in this work. Further information is contained in Section B.
Next, we briefly discuss the empirical scaling of our algorithm. In Figure 5 , we plot the total simulation time used to generate Figure 1 in our study of the two qubit model in Eq. (1) . Though a simple model, simulation time grows as a function of β \beta β and near the avoided level crossings, as expected.
Figure 5. Simulation time used to generate Figure 1 .
In Figure 6 , we repeat our study of the XXZ model at the critical temperature T c ≈ 0.75 T_{\mathrm{c}} \approx0.75 T c ≈ 0.75 at (a) different system sizes N = L 2 N = L^{2} N = L 2 and (b) with different measurements protocols. We also show the modest wall-clock time scaling as a function of T T T for different L L L . In our timing experiments, all simulations are run on the same 2.6 GHz AMD EPYC 7513 CPU and simulation parameters are fixed to values listed in the caption, chosen to be in the same range as those used for Figure 3 . The different measurements correspond to either running QMC without performing any measurement, while measuring only the ES, or while measuring only the FS. In all cases, times are similar and the scaling is roughly proportional to N 2 = L 4 N^{2} = L^{4} N 2 = L 4 . Given that ES and FS have O ( 1 ) O(1) O ( 1 ) and O ( q 3 ) O(q^{3}) O ( q 3 ) estimators (see Theorems 1 and 2), this may be surprising, but measurements are performed sparsely (every N s k i p = 5000 N_{\mathrm{skip}} = 5000 N skip = 5000 MC moves), so wall-clock time is dominated by QMC simulation itself. Further discussion and empirical testing of resource scaling is given in Section B.
Figure 6. Estimate of total simulation time scaling for the L × L L \times L L × L XXZ model data in Figure 3 . Timings are given with the following simulation parameters fixed: N t h e r m = 0 N_{\mathrm{therm}} = 0 N therm = 0 , N m e a s = 4 × 10 8 N_{\mathrm{meas}} = 4 \times10^{8} N meas = 4 × 1 0 8 , N s k i p = 5 × 10 3 N_{\mathrm{skip}} = 5 \times10^{3} N skip = 5 × 1 0 3 . Errors bars are estimated over 20 independent runs (N p = 20 N_{\mathrm{p}} = 20 N p = 20 ). We refer readers to Section B for more details on the meaning of simulation parameters. (Left) Wall-clock time as a function of L L L at the critical temperature T c ≈ 0.75 T_{\mathrm{c}} \approx0.75 T c ≈ 0.75 , separated by what is being measured. Simulation time scales roughly as L 4 = N 2 L^{4} = N^{2} L 4 = N 2 in this case. (Right) Wall-clock times to simulate the XXZ model as a function of T T T for different L L L , with all measurement approaches averaging together.
Discussion
We have developed a universal black-box, finite-temperature quantum Monte Carlo (QMC) approach for studying quantum phase transitions (QPTs). Specifically, we derived PMR-QMC estimators for energy susceptibility (ES) and fidelity susceptibility (FS), which serve as general-purpose, order-parameter-free tools for locating quantum critical points. At the same time, given
a Hamiltonian, we can compute a set of ergodic QMC updates that satisfy detailed balance.
Thanks to the generality of both the PMR-QMC framework and our PMR-based derivations, we successfully studied various aspects of QPTs, ES, and FS for a transverse-field Ising model, an XXZ model, and even a random ensemble—all using a single code. These demonstrations required no model-specific modifications to the source code—only a specification of the Hamiltonian and the desired partition, both of which can be arbitrary. As such, our method and publicly available open-source code are designed to be accessible and user friendly.
Of note, our method can estimate the ES in constant time for models with a simple driving term such as in the TFIM or XXZ model. Though the ES is expected to be a weaker indicator of criticality than the FS in general, we have found it to be sufficient in all models studied in this work. Hence, our approach is not only general but also very efficient for many systems of interest in condensed matter physics.
There are several promising avenues for future research. Foremost, we aim to apply our approach to physically relevant models with non-standard driving terms. We also intend to extend our method to bosonic, fermionic, and high-spin systems of current interest.
We hope the results of this work will provide a valuable and versatile tool for condensed matter physicists and researchers studying quantum phase transitions.
Methods
We introduce requisite technical background then state and discuss the novel PMR-QMC estimators utilized in our study of QPTs in § 2 . Importantly, we state Theorems 1 and 2, which provide estimators for ES and FS applicable to most well-studied condensed matter models. At the cost of some efficiency, we also generalize these theorems to arbitrary Hamiltonians.
Energy and fidelity susceptibilities
We discuss the ES and the FS as two generic, order-parameter-free tools to study QPTs [4 , 9 ] [18, 19]. Throughout, we assume an n n n spin Hamiltonian with non-degenerate groundstate,
H ( λ ) = H 0 + λ H 1 , (5) H(\lambda)=H_0+\lambda H_1, \tag*{(5)} H ( λ ) = H 0 + λ H 1 , (5)
that has quantum critical point (QCP) at λ = λ c \lambda=\lambda_c λ = λ c , denoting the boundary between two quantum phases of a QPT. Henceforth, we refer to H 0 H_0 H 0 as the static term and H 1 H_1 H 1 as the driving term for convenience. Given the spectral decomposition, H ( λ ) ∣ ψ k ( λ ) ⟩ = E k ( λ ) ∣ ψ k ( λ ) ⟩ H(\lambda)\lvert\psi_k(\lambda)\rangle=E_k(\lambda)\lvert\psi_k(\lambda)\rangle H ( λ ) ∣ ψ k ( λ )⟩ = E k ( λ ) ∣ ψ k ( λ )⟩ , we define the ES [27 , 28 ] [18]
χ E ( λ ) = − ∂ 2 E 0 ( λ ) ∂ λ 2 . (6) \chi_E(\lambda)=-\frac{\partial^2 E_0(\lambda)}{\partial\lambda^2}. \tag*{(6)} χ E ( λ ) = − ∂ λ 2 ∂ 2 E 0 ( λ ) . (6)
For second-order QPTs such as that in the TFIM [1 ] , the ES is expected to have a peak or even diverge, and hence, it can be used to locate QCPs. Similarly, the second-order term in the Taylor expansion of groundstate fidelity, or FS [9 ] ,
χ F ( λ ) = lim δ λ → 0 − 2 ln ∣ ⟨ ψ 0 ( λ ) ∣ ψ 0 ( λ + δ λ ) ⟩ ∣ δ λ 2 , (7) \chi_F(\lambda)=\lim_{\delta\lambda\to0}\frac{-2\ln\left|\langle\psi_0(\lambda)|\psi_0(\lambda+\delta\lambda)\rangle\right|}{\delta\lambda^2}, \tag*{(7)} χ F ( λ ) = δ λ → 0 lim δ λ 2 − 2 ln ∣ ⟨ ψ 0 ( λ ) ∣ ψ 0 ( λ + δ λ )⟩ ∣ , (7)
also exhibits a peak or diverges at QCPs for a wide variety of QPTs [28 , 53 ] [18], including first-order [11 ] , second-order [11 ] , topological [54 , 55 ] , and as seen recently, even dynamical QPTs [11 ] .
There are several equivalent characterizations of both quantities that are useful in different contexts. First, we discuss various rich characterizations of the FS [4 , 7 , 9 , 28 , 53 ] . By a direct Taylor expansion and simplification of ⟨ ψ 0 ( λ ) ∣ ψ 0 ( λ + δ λ ) ⟩ \langle\psi_0(\lambda)|\psi_0(\lambda+\delta\lambda)\rangle ⟨ ψ 0 ( λ ) ∣ ψ 0 ( λ + δ λ )⟩ , one finds the differential form,
χ F ( λ ) = ⟨ ∂ λ ψ 0 ( λ ) ∣ ∂ λ ψ 0 ( λ ) ⟩ − ⟨ ∂ λ ψ 0 ( λ ) ∣ ψ 0 ( λ ) ⟩ ⟨ ψ 0 ( λ ) ∣ ∂ λ ψ 0 ( λ ) ⟩ , (8) \chi_F(\lambda)=\langle\partial_\lambda\psi_0(\lambda)|\partial_\lambda\psi_0(\lambda)\rangle-\langle\partial_\lambda\psi_0(\lambda)|\psi_0(\lambda)\rangle\langle\psi_0(\lambda)|\partial_\lambda\psi_0(\lambda)\rangle, \tag*{(8)} χ F ( λ ) = ⟨ ∂ λ ψ 0 ( λ ) ∣ ∂ λ ψ 0 ( λ )⟩ − ⟨ ∂ λ ψ 0 ( λ ) ∣ ψ 0 ( λ )⟩ ⟨ ψ 0 ( λ ) ∣ ∂ λ ψ 0 ( λ )⟩ , (8)
which has a clear relation to the quantum metric tensor, i.e., the real part of the quantum geometric tensor [7 , 28 ] . Using non-degenerate perturbation theory, we can also derive the spectral form,
χ F H 1 ( λ ) = ∑ n ≠ 0 ∣ ⟨ ψ n ( λ ) ∣ H 1 ∣ ψ 0 ( λ ) ⟩ ∣ 2 [ E n ( λ ) − E 0 ( λ ) ] 2 , (9) \chi_F^{H_1}(\lambda)=\sum_{n\ne0}\frac{\left|\langle\psi_n(\lambda)|H_1|\psi_0(\lambda)\rangle\right|^2}{\left[E_n(\lambda)-E_0(\lambda)\right]^2}, \tag*{(9)} χ F H 1 ( λ ) = n = 0 ∑ [ E n ( λ ) − E 0 ( λ ) ] 2 ∣ ⟨ ψ n ( λ ) ∣ H 1 ∣ ψ 0 ( λ )⟩ ∣ 2 , (9)
where the superscript now indicates which term we treat as driving the perturbation. Finally, we can derive an integral representation [9 ] that is useful in deriving both scaling relations [53 ] [18] and in generalizing the Gibbs state for QMC [17–19].
To proceed [18], we define the imaginary time evolved operator H 1 ( τ ) ≡ e τ H ( λ ) H 1 e − τ H ( λ ) H_1(\tau)\equiv e^{\tau H(\lambda)}H_1e^{-\tau H(\lambda)} H 1 ( τ ) ≡ e τ H ( λ ) H 1 e − τ H ( λ ) and the connected correlation function,
G 0 H 1 ( τ ; λ ) ≡ θ ( τ ) ( ⟨ ψ 0 ( λ ) ∣ H 1 ( τ ) H 1 ∣ ψ 0 ( λ ) ⟩ − ⟨ ψ 0 ( λ ) ∣ H 1 ∣ ψ 0 ( λ ) ⟩ 2 ) , (10) G_0^{H_1}(\tau;\lambda)\equiv\theta(\tau)\left(\langle\psi_0(\lambda)|H_1(\tau)H_1|\psi_0(\lambda)\rangle-\langle\psi_0(\lambda)|H_1|\psi_0(\lambda)\rangle^2\right), \tag*{(10)} G 0 H 1 ( τ ; λ ) ≡ θ ( τ ) ( ⟨ ψ 0 ( λ ) ∣ H 1 ( τ ) H 1 ∣ ψ 0 ( λ )⟩ − ⟨ ψ 0 ( λ ) ∣ H 1 ∣ ψ 0 ( λ ) ⟩ 2 ) , (10)
for θ ( τ ) \theta(\tau) θ ( τ ) the Heaviside step function. Dropping λ \lambda λ dependence for simplicity, inserting the resolution of the identity between H 1 H_1 H 1 and e − τ H e^{-\tau H} e − τ H and simplifying, we find
G 0 H 1 ( τ ; λ ) = θ ( τ ) ∑ n ≠ 0 e τ ( E 0 − E n ) ∣ ⟨ ψ 0 ∣ H 1 ∣ ψ n ⟩ ∣ 2 . (11) G_0^{H_1}(\tau;\lambda)=\theta(\tau)\sum_{n\ne0}e^{\tau(E_0-E_n)}\left|\langle\psi_0|H_1|\psi_n\rangle\right|^2. \tag*{(11)} G 0 H 1 ( τ ; λ ) = θ ( τ ) n = 0 ∑ e τ ( E 0 − E n ) ∣ ⟨ ψ 0 ∣ H 1 ∣ ψ n ⟩ ∣ 2 . (11)
Taking the inverse Fourier transform,
G ~ 0 H 1 ( ω ) = ∫ R e − i τ ω G 0 H 1 ( τ ) = ∑ n ≠ 0 ∣ ⟨ ψ 0 ∣ H 1 ∣ ψ n ⟩ ∣ 2 E n − E 0 + i ω , (12) \widetilde{G}_0^{H_1}(\omega)=\int_{\mathbb{R}}e^{-i\tau\omega}G_0^{H_1}(\tau)=\sum_{n\ne0}\frac{\left|\langle\psi_0|H_1|\psi_n\rangle\right|^2}{E_n-E_0+i\omega}, \tag*{(12)} G 0 H 1 ( ω ) = ∫ R e − i τ ω G 0 H 1 ( τ ) = n = 0 ∑ E n − E 0 + iω ∣ ⟨ ψ 0 ∣ H 1 ∣ ψ n ⟩ ∣ 2 , (12)
we see a strong resemblance between this formula and Eq. (9) . Namely, we recognize,
χ F H 1 ( λ ) = i d G ~ 0 H 1 ( ω ) d ω = ∫ 0 ∞ τ G 0 H 1 ( τ ; λ ) d τ , (13) \chi_F^{H_1}(\lambda)=i\frac{d\widetilde{G}_0^{H_1}(\omega)}{d\omega}=\int_0^\infty\tau G_0^{H_1}(\tau;\lambda)d\tau, \tag*{(13)} χ F H 1 ( λ ) = i d ω d G 0 H 1 ( ω ) = ∫ 0 ∞ τ G 0 H 1 ( τ ; λ ) d τ , (13)
which is the sought after integral representation. This form relates χ F \chi_F χ F to the dynamical response of the system to H 1 H_1 H 1 , revealing its physical content [9 , 53 ] [18].
A similar story holds for ES [18]. Applying non-degenerate perturbation theory, we find the second derivative of energy is given by
χ E H 1 ( λ ) = 2 ∑ n ≠ 0 ∣ ⟨ ψ n ( λ ) ∣ H 1 ∣ ψ 0 ( λ ) ⟩ ∣ 2 E n ( λ ) − E 0 ( λ ) , (14) \chi_E^{H_1}(\lambda)=2\sum_{n\ne0}\frac{\left|\langle\psi_n(\lambda)|H_1|\psi_0(\lambda)\rangle\right|^2}{E_n(\lambda)-E_0(\lambda)}, \tag*{(14)} χ E H 1 ( λ ) = 2 n = 0 ∑ E n ( λ ) − E 0 ( λ ) ∣ ⟨ ψ n ( λ ) ∣ H 1 ∣ ψ 0 ( λ )⟩ ∣ 2 , (14)
which—aside from the pre-factor of 2 2 2 —differs from Eq. (9) only by the denominator. By inspection of Eq. (14) and Eq. (12) ,
χ E H 1 ( λ ) = 2 G ~ 0 H 1 ( ω = 0 ) = 2 ∫ 0 ∞ G 0 H 1 ( τ ; λ ) d τ . (15) \chi_E^{H_1}(\lambda)=2\widetilde{G}_0^{H_1}(\omega=0)=2\int_0^\infty G_0^{H_1}(\tau;\lambda)d\tau. \tag*{(15)} χ E H 1 ( λ ) = 2 G 0 H 1 ( ω = 0 ) = 2 ∫ 0 ∞ G 0 H 1 ( τ ; λ ) d τ . (15)
With these integral expressions now derived, we can compare the ES and FS, Eqs. (13) and (15) more directly. Evidently, the important difference is that the FS involves a linear factor of τ \tau τ in the integrand, which arises from the difference of the square in the denominators of Eqs. (9) and (14) . Intuitively, one might expect that leads to the FS having a sharper peak at quantum critical points, and this holds rigorously by performing a standard scaling analysis [28 , 53 , 56 ] and manifests in practical simulations [18, 29]. Considering L d L^d L d particles on a d d d -dimensional lattice that undergoes a second-order QPT at critical point λ c \lambda_c λ c , one can derive the scaling relations [18],
L − d χ E , 0 H 1 ( λ ) ∼ ∣ λ − λ c ∣ − α ∼ L ( 2 / ν ) − ( d + z ) (16) L^{-d}\chi_{E,0}^{H_1}(\lambda)\sim|\lambda-\lambda_c|^{-\alpha}\sim L^{(2/\nu)-(d+z)} \tag*{(16)} L − d χ E , 0 H 1 ( λ ) ∼ ∣ λ − λ c ∣ − α ∼ L ( 2/ ν ) − ( d + z ) (16)
L − d χ F , 0 H 1 ( λ ) ∼ ∣ λ − λ c ∣ − ( 2 − d ν ) ∼ L ( 2 / ν ) − d . (17) L^{-d}\chi_{F,0}^{H_1}(\lambda)\sim|\lambda-\lambda_c|^{-(2-d\nu)}\sim L^{(2/\nu)-d}. \tag*{(17)} L − d χ F , 0 H 1 ( λ ) ∼ ∣ λ − λ c ∣ − ( 2 − d ν ) ∼ L ( 2/ ν ) − d . (17)
Here, the correlation length diverges as ξ ∼ ∣ λ − λ c ∣ − ν \xi\sim|\lambda-\lambda_c|^{-\nu} ξ ∼ ∣ λ − λ c ∣ − ν , z z z is the dynamical critical exponent, and α \alpha α is defined through the hyperscaling formula 2 − α = ν ( d + z ) 2-\alpha=\nu(d+z) 2 − α = ν ( d + z ) . Evidently, ES diverges whenever ν < 2 / ( d + z ) \nu<2/(d+z) ν < 2/ ( d + z ) and the FS whenever ν < 2 / d \nu<2/d ν < 2/ d , and hence the FS is a stronger indicator of quantum criticality [18].
These groundstate concepts have also been successfully extended to mixed states [7 , 8 , 28 ] , particularly thermal states [6 , 22 ] [18]. A thermal state of a given Hamiltonian H H H is given by
1 Z e − β H , Z = Tr [ e − β H ] , (18) \frac{1}{\mathcal{Z}}e^{-\beta H}, \qquad\mathcal{Z}=\operatorname{Tr}\left[e^{-\beta H}\right], \tag*{(18)} Z 1 e − β H , Z = Tr [ e − β H ] , (18)
for inverse temperature β = 1 / T \beta=1/T β = 1/ T . A thermal average is thus given by ⟨ O ⟩ ≡ Tr [ O e − β H ] / Z \langle O\rangle\equiv\operatorname{Tr}\left[Oe^{-\beta H}\right]/\mathcal{Z} ⟨ O ⟩ ≡ Tr [ O e − β H ] / Z . We can now introduce a finite temperature connected correlator [18],
G H 1 ( τ ; λ ; β ) = θ ( τ ) ( ⟨ H 1 ( τ ) H 1 ⟩ − ⟨ H 1 ⟩ 2 ) , (19) G^{H_1}(\tau;\lambda;\beta)=\theta(\tau)\left(\langle H_1(\tau)H_1\rangle-\langle H_1\rangle^2\right), \tag*{(19)} G H 1 ( τ ; λ ; β ) = θ ( τ ) ( ⟨ H 1 ( τ ) H 1 ⟩ − ⟨ H 1 ⟩ 2 ) , (19)
with which we can derive the integral forms [18],
χ E H 1 ( λ ; β ) = ∫ 0 β G H 1 ( τ ; λ ; β ) d τ (20) \chi_E^{H_1}(\lambda;\beta)=\int_0^\beta G^{H_1}(\tau;\lambda;\beta)\,\mathrm{d}\tau \tag*{(20)} χ E H 1 ( λ ; β ) = ∫ 0 β G H 1 ( τ ; λ ; β ) d τ (20)
χ F H 1 ( λ ; β ) = ∫ 0 β / 2 τ G H 1 ( τ ; λ ; β ) d τ . (21) \chi_F^{H_1}(\lambda;\beta)=\int_0^{\beta/2}\tau G^{H_1}(\tau;\lambda;\beta)\,\mathrm{d}\tau. \tag*{(21)} χ F H 1 ( λ ; β ) = ∫ 0 β /2 τ G H 1 ( τ ; λ ; β ) d τ . (21)
These are particularly convenient for QMC [17–19]. The finite temperature connected correlator is periodic about β / 2 \beta/2 β /2 , so we can equivalently write
χ E H 1 ( λ ; β ) = 2 ∫ 0 β / 2 G H 1 ( τ ; λ ; β ) d τ , (22) \chi_E^{H_1}(\lambda;\beta)=2\int_0^{\beta/2}G^{H_1}(\tau;\lambda;\beta)\,\mathrm{d}\tau, \tag*{(22)} χ E H 1 ( λ ; β ) = 2 ∫ 0 β /2 G H 1 ( τ ; λ ; β ) d τ , (22)
for which it becomes apparent χ E H 1 ( λ ; β ) → χ E H 1 ( λ ) \chi_E^{H_1}(\lambda;\beta)\to\chi_E^{H_1}(\lambda) χ E H 1 ( λ ; β ) → χ E H 1 ( λ ) and χ F H 1 ( λ ; β ) → χ F H 1 ( λ ) \chi_F^{H_1}(\lambda;\beta)\to\chi_F^{H_1}(\lambda) χ F H 1 ( λ ; β ) → χ F H 1 ( λ ) as β → ∞ \beta\to\infty β → ∞ . In this sense, the finite temperature susceptibilities are a strict generalization of the groundstate susceptibilities, so we will henceforth write only χ E \chi_E χ E and χ F \chi_F χ F when our discussion does not rely on specific parameters at play, i.e. choice of driving term, H 1 H_1 H 1 . A longer discussion connecting Eq. (21) to a more general notion of the Bures metric divergence at quantum critical points between mixed thermal states [6 ] is provided in § 2 .B of Ref. [18].
Given a Hamiltonian of the form Eq. (5) , we can estimate the ES and FS via Eqs. (20) and (21) provided we can estimate ⟨ H 1 ⟩ \langle H_1\rangle ⟨ H 1 ⟩ , ∫ 0 β ⟨ H 1 ( τ ) H 1 ⟩ \int_0^\beta\langle H_1(\tau)H_1\rangle ∫ 0 β ⟨ H 1 ( τ ) H 1 ⟩ and ∫ 0 β / 2 τ ⟨ H 1 ( τ ) H 1 ⟩ \int_0^{\beta/2}\tau\langle H_1(\tau)H_1\rangle ∫ 0 β /2 τ ⟨ H 1 ( τ ) H 1 ⟩ . In PMR-QMC, we can derive estimators for each of these quantities independent of the details of H H H , and hence, for arbitrarily complicated driving terms H 1 H_1 H 1 . This generality is what allowed us to, using a single estimator code, estimate ES and FS for the variety of models in § 2 . In the following, we justify this claim by presenting explicit estimators and discussing their properties and computational complexity.
PMR-QMC background and notation
A complete justification for our estimators requires substantial background in the permutation matrix representation (PMR) and PMR-QMC which we discuss in Section A (see also Refs. [23 ] [26]). The main derivations are also technical and lengthy and hence contained in Section E. Here, we provide a summary mainly to define the necessary notation and basic ideas.
Firstly, the PMR itself is a general matrix decomposition that allows us to write H ( λ ) = D 0 ( λ ) + ∑ j = 1 M D j ( λ ) P j H(\lambda)=D_0(\lambda)+\sum_{j=1}^{M}D_j(\lambda)P_j H ( λ ) = D 0 ( λ ) + ∑ j = 1 M D j ( λ ) P j for D j ( λ ) D_j(\lambda) D j ( λ ) matrices diagonal in the a fixed basis, { ∣ z ⟩ } \{|z\rangle\} { ∣ z ⟩} and { P j } ⊂ G \{P_j\}\subset G { P j } ⊂ G for G G G an Abelian permutation group with simple transitive group action on { ∣ z ⟩ } \{|z\rangle\} { ∣ z ⟩} [26]. Performing an off-diagonal series expansion of Z ≡ Tr [ e − β H ( λ ) ] \mathcal{Z}\equiv\operatorname{Tr}\left[e^{-\beta H(\lambda)}\right] Z ≡ Tr [ e − β H ( λ ) ] [31, 32], we can decompose the partition function into a sum of efficiently computable weights of the form [52 ] [30],
Z = ∑ z , S i q w ( z , S i q ) ≡ ∑ C w C , (23) \mathcal{Z}=\sum_{z,S_{i_q}}w_{(z,S_{i_q})}\equiv\sum_C w_C, \tag*{(23)} Z = z , S i q ∑ w ( z , S i q ) ≡ C ∑ w C , (23)
for basis states z z z and products of permutations S i q = P i q ⋯ P i 1 S_{i_q}=P_{i_q}\cdots P_{i_1} S i q = P i q ⋯ P i 1 for q ≥ 0 q\geq0 q ≥ 0 and each P i k ∈ { P j } P_{i_k}\in\{P_j\} P i k ∈ { P j } , and w C w_C w C . Exploiting the fact that G G G is Abelian and only those terms contribute where S i q S_{i_q} S i q evaluates to the identity, one can devise an automatic generation of a set of QMC update moves such that the resulting Markov chain is ergodic and satisfies detailed balance for essentially any physical Hamiltonian [23 , 24 , 25 , 44 ] . This is the reason we are able to study a wide variety of models with a fixed code.
A PMR-QMC estimator O C O_C O C is a function of C C C such that
⟨ O ⟩ = ∑ C w C O C ∑ C w C , (24) \langle O\rangle=\frac{\sum_C w_C O_C}{\sum_C w_C}, \tag*{(24)} ⟨ O ⟩ = ∑ C w C ∑ C w C O C , (24)
which we denote as O C ≡ ⟨ O ⟩ O_C\equiv\langle O\rangle O C ≡ ⟨ O ⟩ to be read “O C O_C O C estimates ⟨ O ⟩ \langle O\rangle ⟨ O ⟩ ” for convenience. Some of the present authors derived and explored the properties of a wide variety of estimators in PMR-QMC generally [26]. The basic idea is that since both H H H and O O O can always be decomposed in terms of the same group basis G G G , then one can always derive an expression for O C O_C O C . In many cases of interest, such as if O = H 0 O=H_0 O = H 0 or O = H 1 O=H_1 O = H 1 for any bi-partition of H H H , then this formal expression leads to a faithful estimator in practical simulation [26]. This is why our estimators for the correlator, ES, and FS are independent of the choice of bi-partition.
To discuss our estimators more in-depth, we must introduce some standard PMR-QMC notation. First, we denote ∣ z k ⟩ ≡ S i k ∣ z ⟩ |z_k\rangle\equiv S_{i_k}|z\rangle ∣ z k ⟩ ≡ S i k ∣ z ⟩ as the basis state resulting from applying the first k k k permutations from S i q S_{i_q} S i q . Next, we denote the diagonal energies E z k ≡ ⟨ z k ∣ D 0 ∣ z k ⟩ E_{z_k}\equiv\langle z_k|D_0|z_k\rangle E z k ≡ ⟨ z k ∣ D 0 ∣ z k ⟩ . Writing D i k D_{i_k} D i k as the diagonal operator associated to P i k P_{i_k} P i k , we can define the off-diagonal hopping term, D ( z , S i q ) ≡ ∏ k ⟨ z k ∣ D i k ∣ z k ⟩ D_{(z,S_{i_q})}\equiv\prod_k\langle z_k|D_{i_k}|z_k\rangle D ( z , S i q ) ≡ ∏ k ⟨ z k ∣ D i k ∣ z k ⟩ . Finally, we denote e − β [ E z 0 , … , E z q ] e^{-\beta[E_{z_0},\ldots,E_{z_q}]} e − β [ E z 0 , … , E z q ] as the divided difference of the exponential e − β x e^{-\beta x} e − β x with respect to the multiset of diagonal energies given [57 , 58 ] . These thus defined, we can write the standard PMR-QMC result
w ( z , S i q ) = D ( z , S i q ) e − β [ E z 0 , … , E z q ] , (25) w_{(z,S_{i_q})}=D_{(z,S_{i_q})}e^{-\beta[E_{z_0},\ldots,E_{z_q}]}, \tag*{(25)} w ( z , S i q ) = D ( z , S i q ) e − β [ E z 0 , … , E z q ] , (25)
as the efficiently computable PMR-QMC weight. We remark that the divided difference of the exponential (DDE) is especially important in our estimator derivations, and a detailed explanation of the DDE is given in Section A 3.
Pure diagonal estimators
For simplicity, we first assume H 1 ∝ D 0 H_1 \propto D_0 H 1 ∝ D 0 , i.e., as in the TFIM studied in § 2 . Using the properties of the PMR-QMC, we can readily derive the estimators,
E z ≡ ⟨ D 0 ⟩ (26) E_z \equiv\langle D_0\rangle \tag*{(26)} E z ≡ ⟨ D 0 ⟩ (26)
and
E z e − β [ E z 0 , … , E z q ] ∑ j = 0 q E z j e − τ [ E z j , … , E z q ] × e − ( β − τ ) [ E z 0 , … , E z j ] ≡ ⟨ D 0 ( τ ) D 0 ⟩ (27) \frac{E_z}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{j=0}^{q} E_{z_j}e^{-\tau[E_{z_j},\ldots,E_{z_q}]}
\times e^{-(\beta-\tau)[E_{z_0},\ldots,E_{z_j}]} \equiv\langle D_0(\tau)D_0\rangle \tag*{(27)} e − β [ E z 0 , … , E z q ] E z j = 0 ∑ q E z j e − τ [ E z j , … , E z q ] × e − ( β − τ ) [ E z 0 , … , E z j ] ≡ ⟨ D 0 ( τ ) D 0 ⟩ (27)
as we show in Section Section E. These estimators involve only sums and products of (1) diagonal energies E z j E_{z_j} E z j and (2) divided differences of these diagonal energies—the same quantities that appear in the PMR-QMC weight, Eq. (25) . As such, they are both readily computable in a PMR-QMC simulation in O ( 1 ) O(1) O ( 1 ) and O ( q 2 ) O(q^2) O ( q 2 ) time, respectively (see Ref. [26] and Section A 4 to understand the time complexity). Utilizing both of these estimators, we can estimate G D 0 ( τ ; λ ; β ) G^{D_0}(\tau;\lambda;\beta) G D 0 ( τ ; λ ; β ) via Eq. (19) .
Furthermore, the only non-trivial τ \tau τ dependence in these estimators is contained in the divided difference expressions of Eq. (27) . Amazingly (see Ref. [59 ] and Lemma 1 in Section E 3), we can readily derive the exact integral relation
∫ 0 β e − τ [ x j + 1 , … , x q ] e − ( β − τ ) [ x 0 , … , x j ] d τ = − e − β [ x 0 , … , x q ] (28) \int_0^\beta e^{-\tau[x_{j+1},\ldots,x_q]}e^{-(\beta-\tau)[x_0,\ldots,x_j]}\,d\tau=-e^{-\beta[x_0,\ldots,x_q]} \tag*{(28)} ∫ 0 β e − τ [ x j + 1 , … , x q ] e − ( β − τ ) [ x 0 , … , x j ] d τ = − e − β [ x 0 , … , x q ] (28)
Combined with Eq. (27) , we have thus derived
− E z e − β [ E z 0 , … , E z q ] ∑ j = 0 q E z j e − β [ E z 0 , … , E z q , E z j ] ≡ ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ (29) \frac{-E_z}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{j=0}^{q}E_{z_j}e^{-\beta[E_{z_0},\ldots,E_{z_q},E_{z_j}]}
\equiv\int_0^\beta\langle D_0(\tau)D_0\rangle\,d\tau \tag*{(29)} e − β [ E z 0 , … , E z q ] − E z j = 0 ∑ q E z j e − β [ E z 0 , … , E z q , E z j ] ≡ ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ (29)
which gives an estimator for χ E D 0 \chi_{E}^{D_0} χ E D 0 (see Eq. (20) ) when combined with Eq. (26) . As shown in Section E 5, specifically Lemma 3, a similar but more complicated derivation yields,
E z e − β [ E z 0 , … , E z q ] ∑ j = 0 q E z j ∑ r = 0 j e − β 2 [ E z 0 , … , E z r ] × ∑ m = j q e − β 2 [ E z r , … , E z q , E z j , E z m ] ≡ ∫ 0 β / 2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ (30) \frac{E_z}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{j=0}^{q}E_{z_j}\sum_{r=0}^{j}e^{-\frac{\beta}{2}[E_{z_0},\ldots,E_{z_r}]}
\times\sum_{m=j}^{q}e^{-\frac{\beta}{2}[E_{z_r},\ldots,E_{z_q},E_{z_j},E_{z_m}]}
\equiv\int_0^{\beta/2}\tau\langle D_0(\tau)D_0\rangle\,d\tau \tag*{(30)} e − β [ E z 0 , … , E z q ] E z j = 0 ∑ q E z j r = 0 ∑ j e − 2 β [ E z 0 , … , E z r ] × m = j ∑ q e − 2 β [ E z r , … , E z q , E z j , E z m ] ≡ ∫ 0 β /2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ (30)
which gives an estimator for χ F D 0 \chi_{F}^{D_0} χ F D 0 via Eq. (21) . These integrated quantities and hence the ES and FS can be evaluated in O ( q 2 ) O(q^2) O ( q 2 ) and O ( q 4 ) O(q^4) O ( q 4 ) time, respectively.
Several comments are in order. Firstly, our derivations for ES and FS involve first deriving an estimator for the correlator. We then extend this estimator to the ES and FS by an analytical and exact evaluation of the divided difference integrals, i.e., no numerical integration is required.
Improved ES and FS estimators
In the previous section, we derived O ( q 2 ) O(q^2) O ( q 2 ) and O ( q 4 ) O(q^4) O ( q 4 ) estimators for the ES and FS for H 1 ∝ D 0 H_1 \propto D_0 H 1 ∝ D 0 . These estimators can be improved to O ( 1 ) O(1) O ( 1 ) and O ( q 3 ) O(q^3) O ( q 3 ) time in this case (as well as if H 1 ∝ H − D 0 H_1 \propto H-D_0 H 1 ∝ H − D 0 ), which we state as theorems.
Theorem 1 (An O ( 1 ) O(1) O ( 1 ) ES estimator). The ES for H 1 ∝ D 0 H_1 \propto D_0 H 1 ∝ D 0 or H 1 ∝ H − D 0 H_1 \propto H-D_0 H 1 ∝ H − D 0 can be estimated in O ( 1 ) O(1) O ( 1 ) time via
β E z 0 2 + q E z 0 + 1 q > 0 β E z 0 e − β [ E z 0 , … , E z q − 1 ] e − β [ E z 0 , … , E z q ] ≡ ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ , (31) \beta E_{z_0}^{2}+qE_{z_0}+\mathbf{1}_{q>0} \beta E_{z_0}\frac{e^{-\beta[E_{z_0},\ldots,E_{z_{q-1}]}}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}
\equiv\int_0^\beta\langle D_0(\tau)D_0\rangle\,d\tau, \tag*{(31)} β E z 0 2 + q E z 0 + 1 q > 0 β E z 0 e − β [ E z 0 , … , E z q ] e − β [ E z 0 , … , E z q − 1 ] ≡ ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ , (31) for 1 q > 0 \mathbf{1}_{q>0} 1 q > 0 zero if q ≤ 0 q\leq0 q ≤ 0 and one if q > 0 q>0 q > 0 .
Theorem 2 (An O ( q 3 ) O(q^3) O ( q 3 ) estimator for FS). The FS for H 1 ∝ D 0 H_1 \propto D_0 H 1 ∝ D 0 or H 1 ∝ H − D 0 H_1 \propto H-D_0 H 1 ∝ H − D 0 can be computed in O ( q 3 ) O(q^3) O ( q 3 ) time via
1 q = 0 ( β E z 0 ) 2 8 + 1 q > 0 E z 0 e − β [ E z 0 , … , E z q ] ∑ r = 0 q e − β 2 [ E z 0 , … , E z r ] ( β 2 8 E z r e − β 2 [ E z r , … , E z q ] + β 2 8 e − β 2 [ E z r + 1 , … , E z q ] ∑ i = r + 1 q ( i − r ) e − β 2 [ E z r , … , E z q , E z i ] ) ≡ ∫ 0 β / 2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ , (32) \mathbf{1}_{q=0}\frac{(\beta E_{z_0})^2}{8}+\mathbf{1}_{q>0}\frac{E_{z_0}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{r=0}^{q}e^{-\frac{\beta}{2}[E_{z_0},\ldots,E_{z_r}]}
\left(\frac{\beta^2}{8}E_{z_r}e^{-\frac{\beta}{2}[E_{z_r},\ldots,E_{z_q}]}+\frac{\beta^2}{8}e^{-\frac{\beta}{2}[E_{z_{r+1}},\ldots,E_{z_q}]}
\sum_{i=r+1}^{q}(i-r)e^{-\frac{\beta}{2}[E_{z_r},\ldots,E_{z_q},E_{z_i}]}\right)
\equiv\int_0^{\beta/2}\tau\langle D_0(\tau)D_0\rangle\,d\tau, \tag*{(32)} 1 q = 0 8 ( β E z 0 ) 2 + 1 q > 0 e − β [ E z 0 , … , E z q ] E z 0 r = 0 ∑ q e − 2 β [ E z 0 , … , E z r ] ( 8 β 2 E z r e − 2 β [ E z r , … , E z q ] + 8 β 2 e − 2 β [ E z r + 1 , … , E z q ] i = r + 1 ∑ q ( i − r ) e − 2 β [ E z r , … , E z q , E z i ] ) ≡ ∫ 0 β /2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ , (32) for 1 q > 0 \mathbf{1}_{q>0} 1 q > 0 zero if q ≤ 0 q\leq0 q ≤ 0 and one if q > 0 q>0 q > 0 .
Our proof, given in complete detail in Section E, amounts to stating and proving several novel divided difference relations that can be used to simplify Eq. (29) and Eq. (30) . This will be necessary only simplifies the H 1 ∝ D 0 H_1 \propto D_0 H 1 ∝ D 0 case, the H 1 ∝ H − D 0 H_1 \propto H-D_0 H 1 ∝ H − D 0 case follows by linearity and the derivation of a few O ( 1 ) O(1) O ( 1 ) estimators for average energy ⟨ H ⟩ \langle H\rangle ⟨ H ⟩ and similar quantities.
Stated abstractly, the constraint H 1 ∝ D 0 H_1 \propto D_0 H 1 ∝ D 0 or H 1 ∝ H − D 0 H_1 \propto H-D_0 H 1 ∝ H − D 0 may seem restrictive, but recall that this applies to the TFIM and XXZ models studied in § 2 . More generally, many well studied models in condensed matter physics have such simple driving terms that are either purely diagonal or purely off-diagonal. As such, we have derived a constant time ES estimator for a wide variety of models.
General case estimators
Generally, H 1 H_1 H 1 may contain both diagonal and off-diagonal terms, i.e., Eq. (1) or the random ensemble studied in § 2 . This is not a fundamental issue for PMR-QMC, as whenever H H H is in PMR form with R R R term, H = ∑ j D j P j H=\sum_j D_jP_j H = ∑ j D j P j , we can always write H 1 = ∑ j Λ j D j P j H_1=\sum_j\Lambda_jD_jP_j H 1 = ∑ j Λ j D j P j for Λ j \Lambda_j Λ j diagonal matrices by the group structure of the PMR (see Section F 1). Observables of this type are said to be in canonical PMR form, and can be estimated correctly [26]. Namely, we can readily estimate ⟨ H 1 ⟩ \langle H_1\rangle ⟨ H 1 ⟩ and ⟨ H 1 ( τ ) H 1 ⟩ \langle H_1(\tau)H_1\rangle ⟨ H 1 ( τ ) H 1 ⟩ using expressions that generalize Eqs. (26) and (27) .
For example, we can readily derive the estimator [26],
δ P l ( q ) Λ l ( z ) e − β [ E z 0 , … , E z q − 1 ] e − β [ E z 0 , … , E z q ] ≡ ⟨ Λ l D l P l ⟩ , (33) \delta_{P_l}^{(q)}\frac{\Lambda_l(z)e^{-\beta[E_{z_0},\ldots,E_{z_{q-1}}]}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}} \equiv\langle\Lambda_lD_lP_l\rangle, \tag*{(33)} δ P l ( q ) e − β [ E z 0 , … , E z q ] Λ l ( z ) e − β [ E z 0 , … , E z q − 1 ] ≡ ⟨ Λ l D l P l ⟩ , (33)
from which we can estimate ⟨ H 1 ⟩ \langle H_1\rangle ⟨ H 1 ⟩ by linearity. Here, δ P l ( q ) \delta_{P_l}^{(q)} δ P l ( q ) equals 1 if the q t h q^{\mathrm{th}} q th or final permutation in S i q S_{i_q} S i q is P l P_l P l and is 0 otherwise, and we have used the shorthand Λ l ( z ) ≡ ⟨ z ∣ Λ l ∣ z ⟩ \Lambda_l(z)\equiv\langle z|\Lambda_l|z\rangle Λ l ( z ) ≡ ⟨ z ∣ Λ l ∣ z ⟩ . As for ⟨ H 1 ( τ ) H 1 ⟩ \langle H_1(\tau)H_1\rangle ⟨ H 1 ( τ ) H 1 ⟩ , we can also derive an estimator for ⟨ ( Λ k D k P k ) ( τ ) Λ l D l P l ⟩ \langle(\Lambda_kD_kP_k)(\tau)\Lambda_lD_lP_l\rangle ⟨( Λ k D k P k ) ( τ ) Λ l D l P l ⟩ that—up to small technicalities—contains the same τ \tau τ dependence as Eq. (27) used to estimate ⟨ D 0 ( τ ) D 0 ⟩ \langle D_0(\tau)D_0\rangle ⟨ D 0 ( τ ) D 0 ⟩ . Hence, even for arbitrary H 1 H_1 H 1 , we can extend our estimator for ⟨ H 1 ( τ ) H 1 ⟩ \langle H_1(\tau)H_1\rangle ⟨ H 1 ( τ ) H 1 ⟩ to estimators for χ E H 1 \chi_E^{H_1} χ E H 1 and χ F H 1 \chi_F^{H_1} χ F H 1 by our novel divided difference integral relations alone.
Specific expressions for these estimators and more discussion are provided in Section F for interested readers. The functional difference between these general estimators and those for H 1 ∝ D 0 H_1\propto D_0 H 1 ∝ D 0 or H 1 ∝ H − D 0 H_1\propto H-D_0 H 1 ∝ H − D 0 is that we estimate things term-by-term and exploit linearity. As such, the complexity estimation also depends on the number of non-trivial terms contained in H 1 H_1 H 1 . Assuming there are R R R non-trivial terms, the complexity of estimating the ES and FS in the most general case is then O ( R 2 q 2 ) O(R^2q^2) O ( R 2 q 2 ) and O ( R 2 q 4 ) O(R^2q^4) O ( R 2 q 4 ) , respectively. In practice, the average complexity is much better, as we do not need to compute the full estimators whenever various O ( 1 ) O(1) O ( 1 ) delta function conditions are not satisfied (see Eq. (33) ). Consequently, we were able to, for example, study the random ensemble with hundreds of terms successfully in § 2 .
Comparison to prior estimators
We compare our work to similar efforts in Refs. [17–19] which heavily inspired us. The principal advantage of our formulation is its direct applicability to arbitrary Hamiltonians and driving terms without modification, enabling, for example, the study of random ensembles in Figure 4 . For a more direct comparison, we henceforth focus on conventional models for which established (finite temperature) QMC algorithms exist and where the
driving term is purely off-diagonal, H 1 ∝ H − D 0 H_1\propto H-D_0 H 1 ∝ H − D 0 (i.e. as in an XXZ). In this case, we have derived O ( 1 ) O(1) O ( 1 ) ES and O ( q 3 ) O(q^3) O ( q 3 ) FS estimators, respectively.
In Ref. [19], a general FS estimator applicable to multiple QMC frameworks is introduced, which improves upon the prior stochastic series expansion (SSE) estimator derived in Refs. [17, 18]. Given the close structural relationship between SSE and PMR-QMC [30–32], we compare our estimator to the SSE estimator derived in Ref. [19]. For an SSE operator string truncation length M M M , the estimator (see Fig. 3 of [19]) requires O ( M ) O(M) O ( M ) computational effort in the worst case. Since this is as fast as the O ( M ) O(M) O ( M ) estimator for ES derived in Ref. [18], one need not consider measuring ES in SSE. Although M M M is not directly comparable to q q q in PMR-QMC—each PMR-QMC weight represents an infinite resummation of SSE terms through the divided-difference treatment of diagonal contributions [30–32]—one may expect the O ( M ) O(M) O ( M ) estimator to be asymptotically faster than our O ( q 3 ) O(q^3) O ( q 3 ) FS estimator.
The practical advantage of an O ( M ) O(M) O ( M ) SSE estimator over our O ( q 3 ) O(q^3) O ( q 3 ) PMR-QMC estimator is not necessarily decisive, however. First, the total simulation time in QMC is not always dominated by estimator evaluation. As illustrated in Figure 6 , simulation time is often governed by the Monte Carlo updates themselves rather than by measurement routines, and similar conditions were used to obtain the ES and FS data in Figure 3 . In such cases, differences in estimator complexity are largely inconsequential. Second, PMR-QMC has been observed to equilibrate substantially faster than SSE for disordered or glassy systems [30, 32], again diminishing the relevance of raw estimator complexity.
We therefore expect a meaningful advantage of the O ( M ) O(M) O ( M ) SSE estimator only in regimes where the total computational cost of PMR-QMC is indeed dominated by our O ( q 3 ) O(q^3) O ( q 3 ) estimator (we explore this regime of PMR-QMC empirically in Section B3). Yet even in these cases, one can alternatively compute the ES, for which we have derived an O ( 1 ) O(1) O ( 1 ) estimator. Unless one is studying a system where the FS exhibits a pronounced peak in the absence of a corresponding ES feature [29], it is unclear which approach offers superior overall efficiency. Accordingly, we conclude that the primary advantage of the formulation in Ref. [19] lies in its generality across diverse QMC methodologies.
Code and Data Availability
Simulation code, data, and analysis scripts are open source [33] and available either through Zenodo, zenodo.org/records/17786518 , or GitHub, github.com/nazzell/advancedPMRQMC/tree/v3.0.0 .
Acknowledgements
The authors acknowledge the Center for Advanced Research Computing (CARC) at the University of Southern California for providing the computing resources used in this work. This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001122C0063. All material, except scientific articles or papers published in scientific journals, must, in addition to any notices or disclaimers by the Contractor, also contain the following disclaimer: Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Defense Advanced Research Projects Agency (DARPA). N.E. was partially supported by the U.S. Department of Energy (DOE) Computational Science Graduate Fellowship under Award No. DE-SC0020347 and the ARO
MURI grant W911NF-22-S-000 during parts of this work.
Author Contributions
I.H. and N.E. conceived the research problem. N.E., L.B., and I.H. jointly derived the analytical results for the estimators. N.E. and L.B. developed the software, performed the numerical experiments, and analyzed the data. All authors wrote and revised the manuscript and approved the final version.
Competing Interests
The authors declare no competing interests.
Review of technical PMR-QMC background
Permutation matrix representation
The permutation matrix representation (PMR) [38 ] is a general matrix decomposition of square matrices [26] with several applications in condensed matter physics and quantum information [23 , 24 , 25 , 34 , 38 , 44 , 60 , 61 , 62 , 63 ] [30]. Functionally, we say a square matrix H H H is in PMR form provided it is written H = D 0 + ∑ j D j P j H = D_0 + \sum_j D_jP_j H = D 0 + ∑ j D j P j for each D j D_j D j a diagonal matrix and P j P_j P j permutations with no fixed points [38 ] . More rigorously [26], this is guaranteed provided { P j } ⊂ G \{P_j\} \subset G { P j } ⊂ G for G G G a permutation group with simply transitive group action on computational basis states, { ∣ z ⟩ } \{|z\rangle\} { ∣ z ⟩} . The most important consequence of this form is that products of permutations P i P j P_iP_j P i P j have no fixed points unless P i P j = 1 P_iP_j = 1 P i P j = 1 . A through definition of the PMR with several examples is contained in the work by some of the present authors [26].
Off-diagonal series expansion
The off-diagonal series expansion (OSE), first introduced in Refs. [31, 32], is the starting point of the PMR-QMC [38 ] . Alongside basic group theory, it is also the tool by which we can readily derive general estimators for arbitrary observables in PMR-QMC [26]. Let f f f by any analytic function and H = D 0 + ∑ j D j P j H = D_0 + \sum_j D_jP_j H = D 0 + ∑ j D j P j be a Hamiltonian in PMR form. The OSE, then, is a convenient expansion of Tr [ f ( H ) ] \operatorname{Tr}[f(H)] Tr [ f ( H )] into a “classical term” and an infinite series of “quantum, non-commuting” corrections, which will become clear shortly.
A derivation of the OSE of Tr [ f ( H ) ] \operatorname{Tr}[f(H)] Tr [ f ( H )] begins by a direct Taylor series expansion of f ( H ) f(H) f ( H ) about 0. Doing so yields,
Tr [ f ( H ) ] = ∑ z ∑ n = 0 ∞ f ( n ) ( 0 ) n ! ⟨ z ∣ ( D 0 + ∑ j D j P j ) n ∣ z ⟩ (34) \operatorname{Tr}[f(H)] = \sum_z \sum_{n=0}^{\infty} \frac{f^{(n)}(0)}{n!}\left\langle z\left|\left(D_0+\sum_j D_jP_j\right)^n\right|z\right\rangle \tag*{(34)} Tr [ f ( H )] = z ∑ n = 0 ∑ ∞ n ! f ( n ) ( 0 ) ⟨ z ( D 0 + j ∑ D j P j ) n z ⟩ (34)
= ∑ z ∑ n = 0 ∞ ∑ { C i n } f ( n ) ( 0 ) n ! ⟨ z ∣ C i n ∣ z ⟩ , (35) = \sum_z \sum_{n=0}^{\infty} \sum_{\{C_{i_n}\}} \frac{f^{(n)}(0)}{n!}\langle z|C_{i_n}|z\rangle, \tag*{(35)} = z ∑ n = 0 ∑ ∞ { C i n } ∑ n ! f ( n ) ( 0 ) ⟨ z ∣ C i n ∣ z ⟩ , (35)
where in the second line we sum over all operator sequences consisting of n n n products of D 0 D_0 D 0 and D j P j D_jP_j D j P j terms, which we denote { C i n } \{C_{i_n}\} { C i n } . The multi-index i n ≡ ( i 1 , … , i n ) i_n \equiv(i_1,\ldots,i_n) i n ≡ ( i 1 , … , i n ) denotes the ordered sequence, i.e. i 3 = ( 3 , 0 , 1 ) i_3 = (3,0,1) i 3 = ( 3 , 0 , 1 ) indicates the sequence C i 3 = ( D 1 P 1 ) D 0 ( D 3 P 3 ) C_{i_3} = (D_1P_1)D_0(D_3P_3) C i 3 = ( D 1 P 1 ) D 0 ( D 3 P 3 ) , read from right to left. More generally, each i k ∈ { 0 , … , M } i_k \in\{0,\ldots,M\} i k ∈ { 0 , … , M } denotes a single term from the PMR form H = ∑ j = 0 M D j P j H = \sum_{j=0}^{M}D_jP_j H = ∑ j = 0 M D j P j .
For convenience, we can separate the contributions from diagonal operators D j D_j D j from off-diagonal permutations, P j P_j P j which yields [31, 32] the following complicated expression,
Tr [ f ( H ) ] = ∑ z ∑ q = 0 ∞ ∑ S i q D ( z , S i q ) ⟨ z ∣ S i q ∣ z ⟩ ( ∑ n = q ∞ f ( n ) ( 0 ) n ! ∑ i ∑ i k i = n − q E z 0 k 0 ⋯ E z q k q ) , (36) \operatorname{Tr}[f(H)] = \sum_z \sum_{q=0}^{\infty} \sum_{S_{i_q}} D_{(z,S_{i_q})}\langle z|S_{i_q}|z\rangle\left(\sum_{n=q}^{\infty}\frac{f^{(n)}(0)}{n!}\sum_{\substack{i\\ \sum_i k_i=n-q}} E_{z_0}^{k_0}\cdots E_{z_q}^{k_q}\right), \tag*{(36)} Tr [ f ( H )] = z ∑ q = 0 ∑ ∞ S i q ∑ D ( z , S i q ) ⟨ z ∣ S i q ∣ z ⟩ n = q ∑ ∞ n ! f ( n ) ( 0 ) i ∑ i k i = n − q ∑ E z 0 k 0 ⋯ E z q k q , (36)
which is justified in prior works [31, 32]. We now briefly summarize the notation, which will be used throughout. Firstly, S i q = P i q ⋯ P i 1 S_{i_q}=P_{i_q}\cdots P_{i_1} S i q = P i q ⋯ P i 1 denotes a product over q q q permutations, each taken from { P j } j = 1 M \{P_j\}_{j=1}^{M} { P j } j = 1 M , i.e., the multiset indices are now i j ∈ { 1 , … , M } i_j\in\{1,\ldots,M\} i j ∈ { 1 , … , M } . Next, we denote ∣ z 0 ⟩ ≡ ∣ z ⟩ |z_0\rangle\equiv|z\rangle ∣ z 0 ⟩ ≡ ∣ z ⟩ and ∣ z k ⟩ ≡ P i k ⋯ P i 1 ∣ z ⟩ |z_k\rangle\equiv P_{i_k}\cdots P_{i_1}|z\rangle ∣ z k ⟩ ≡ P i k ⋯ P i 1 ∣ z ⟩ . This allows us to define the “diagonal energies” as E z k ≡ ⟨ z k ∣ H ∣ z k ⟩ = ⟨ z k ∣ D 0 ∣ z k ⟩ E_{z_k}\equiv\langle z_k|H|z_k\rangle=\langle z_k|D_0|z_k\rangle E z k ≡ ⟨ z k ∣ H ∣ z k ⟩ = ⟨ z k ∣ D 0 ∣ z k ⟩ (recall ∣ z k ⟩ |z_k\rangle ∣ z k ⟩ is a basis for D 0 D_0 D 0 not of H H H ) and the off-diagonal “hopping strengths” D ( z , S i q ) ≡ ∏ k = 1 q ⟨ z k ∣ D i k ∣ z k ⟩ D_{(z,S_{i_q})}\equiv\prod_{k=1}^{q}\langle z_k|D_{i_k}|z_k\rangle D ( z , S i q ) ≡ ∏ k = 1 q ⟨ z k ∣ D i k ∣ z k ⟩ . The sum over ∑ ∑ k i \sum_{\sum k_i} ∑ ∑ k i is again the set of weak partitions of n − q n-q n − q into q + 1 q+1 q + 1 integers.
This complicated expression can be greatly simplified in two ways. Firstly, by the no-fixed points property of the PMR [26], ⟨ z ∣ S i q ∣ z ⟩ = 1 \langle z|S_{i_q}|z\rangle=1 ⟨ z ∣ S i q ∣ z ⟩ = 1 if and only if S i q = 1 S_{i_q}=1 S i q = 1 and is zero otherwise. Secondly, as first noticed in earlier works [31, 32], the diagonal term in parentheses can be identified with the so-called divided difference of f f f [57 , 58 ] . Together, we can write
Tr [ f ( H ) ] = ∑ z ∑ q = 0 ∞ ∑ S i q = 1 D ( z , S i q ) f [ E z 0 , … , E z q ] , (37) \operatorname{Tr}[f(H)] = \sum_z \sum_{q=0}^{\infty} \sum_{S_{i_q}=1} D_{(z,S_{i_q})}f[E_{z_0},\ldots,E_{z_q}], \tag*{(37)} Tr [ f ( H )] = z ∑ q = 0 ∑ ∞ S i q = 1 ∑ D ( z , S i q ) f [ E z 0 , … , E z q ] , (37)
for f [ E z 0 , … , E z q ] f[E_{z_0},\ldots,E_{z_q}] f [ E z 0 , … , E z q ] is the divided difference of f f f with respect to the multiset of diagonal energies E z 0 , … , E z q E_{z_0},\ldots,E_{z_q} E z 0 , … , E z q . The divided difference plays a pivotal role in our derivation, so we review it in detail in the next section. For now, we simply remark that this form is precisely what we refer to as the off-diagonal series expansion of Tr [ f ( H ) ] \operatorname{Tr}[f(H)] Tr [ f ( H )] . As the name suggests, it is a perturbative series in q q q , the size of the off-diagonal “quantum dimension.” Put differently, when q = 0 q=0 q = 0 , this is the expansion of Tr [ f ( D 0 ) ] \operatorname{Tr}[f(D_0)] Tr [ f ( D 0 )] , and the remaining terms correct for the off-diagonal, non-commuting contribution, as claimed in the beginning.
Divided differences
We briefly review the technical details of the divided difference, inspired by the treatment in Refs. [26, 31, 32]. The divided difference of any holomorphic function f ( x ) f(x) f ( x ) can be defined over the multiset [ x 0 , … , x q ] [x_0,\ldots,x_q] [ x 0 , … , x q ] using a contour integral [57 , 58 ] ,
f [ x 0 , … , x q ] ≡ 1 2 π i ∮ Γ f ( x ) ∏ i = 0 q ( x − x i ) d x , (38) f[x_0,\ldots,x_q] \equiv\frac{1}{2\pi i}\oint_{\Gamma}\frac{f(x)}{\prod_{i=0}^{q}(x-x_i)}\,\mathrm{d}x, \tag*{(38)} f [ x 0 , … , x q ] ≡ 2 π i 1 ∮ Γ ∏ i = 0 q ( x − x i ) f ( x ) d x , (38)
for Γ \Gamma Γ a positively oriented contour enclosing all the x i x_i x i ’s. Several elementary properties utilized in PMR-QMC [30, 32] follow directly from this integral representation, or by invoking Cauchy’s residue theorem. For example, f [ x 0 , … , x q ] f[x_0,\ldots,x_q] f [ x 0 , … , x q ] is invariant to permutations of arguments, the definition reduces to Taylor expansion weights when arguments are repeated,
f [ x 0 , … , x q ] = f ( q ) ( x ) q ! , x 0 = x 1 … = x q = x , (39) f[x_0,\ldots,x_q]=\frac{f^{(q)}(x)}{q!},\qquad x_0=x_1\ldots=x_q=x, \tag*{(39)} f [ x 0 , … , x q ] = q ! f ( q ) ( x ) , x 0 = x 1 … = x q = x , (39)
and whenever each x i x_i x i is distinct, we find
f [ x 0 , … , x q ] = ∑ i = 0 q f ( x i ) ∏ k ≠ i ( x i − x k ) , (40) f[x_0,\ldots,x_q]=\sum_{i=0}^{q}\frac{f(x_i)}{\prod_{k\ne i}(x_i-x_k)}, \tag*{(40)} f [ x 0 , … , x q ] = i = 0 ∑ q ∏ k = i ( x i − x k ) f ( x i ) , (40)
the starting definition in Refs. [30–32]. Each of these divided difference definitions can be shown to satisfy the Leibniz rule [57 ] ,
( f ⋅ g ) [ x 0 , … , x q ] = ∑ j = 0 q f [ x 0 , … , x j ] g [ x j , … , x q ] = ∑ j = 0 q g [ x 0 , … , x j ] f [ x j , … , x q ] (41) (f\cdot g)[x_0,\ldots,x_q]=\sum_{j=0}^{q}f[x_0,\ldots,x_j]g[x_j,\ldots,x_q]=\sum_{j=0}^{q}g[x_0,\ldots,x_j]f[x_j,\ldots,x_q] \tag*{(41)} ( f ⋅ g ) [ x 0 , … , x q ] = j = 0 ∑ q f [ x 0 , … , x j ] g [ x j , … , x q ] = j = 0 ∑ q g [ x 0 , … , x j ] f [ x j , … , x q ] (41)
which is particularly important in our derivations.
Yet another useful way to view the divided difference for our work is to derive its power series expansion,
f [ x 0 , … , x q ] = ∑ m = 0 ∞ f ( q + m ) ( 0 ) ( q + m ) ! ∑ ∑ k j = m j = 0 q ∏ j = 0 q x j k j , (42) f[x_0,\ldots,x_q]=\sum_{m=0}^{\infty}\frac{f^{(q+m)}(0)}{(q+m)!}\sum_{\substack{\sum k_j=m\\j=0}}^{q}\prod_{j=0}^{q}x_j^{k_j}, \tag*{(42)} f [ x 0 , … , x q ] = m = 0 ∑ ∞ ( q + m )! f ( q + m ) ( 0 ) ∑ k j = m j = 0 ∑ q j = 0 ∏ q x j k j , (42)
where the notation ∑ ∑ k j = m q \sum_{\sum k_j=m}^{q} ∑ ∑ k j = m q is a shorthand introduced in Refs. [31, 32] which represents a sum over all weak integer partitions of m m m into q + 1 q+1 q + 1 parts. More explicitly, it is an enumeration over all vectors k \boldsymbol{k} k in the set { k = ( k 0 , … , k q ) : k i ∈ N 0 , ∑ j = 0 q k j = m } \{\boldsymbol{k}=(k_0,\ldots,k_q): k_i\in\mathbb{N}_0,\sum_{j=0}^{q}k_j=m\} { k = ( k 0 , … , k q ) : k i ∈ N 0 , ∑ j = 0 q k j = m } , where N 0 \mathbb{N}_0 N 0 is the natural numbers including zero. To derive the series expansion, we first Taylor expand f ( x ) f(x) f ( x ) inside the contour integral,
f [ x 0 , … , x q ] = ∑ n = 0 ∞ f ( n ) ( 0 ) n ! ( 1 2 π i ∮ Γ x n ∏ i = 0 q ( x − x i ) d x ) = ∑ n = 0 ∞ f ( n ) ( 0 ) n ! [ x 0 , … , x q ] n , (43) f[x_0,\ldots,x_q]=\sum_{n=0}^{\infty}\frac{f^{(n)}(0)}{n!}\left(\frac{1}{2\pi i}\oint_{\Gamma}\frac{x^n}{\prod_{i=0}^{q}(x-x_i)}\,\mathrm{d}x\right)=\sum_{n=0}^{\infty}\frac{f^{(n)}(0)}{n!}[x_0,\ldots,x_q]^n, \tag*{(43)} f [ x 0 , … , x q ] = n = 0 ∑ ∞ n ! f ( n ) ( 0 ) ( 2 π i 1 ∮ Γ ∏ i = 0 q ( x − x i ) x n d x ) = n = 0 ∑ ∞ n ! f ( n ) ( 0 ) [ x 0 , … , x q ] n , (43)
where we have introduced the shorthand [ x 0 , … , x q ] k ≡ p k [ x 0 , … , x q ] [x_0,\ldots,x_q]^k\equiv p_k[x_0,\ldots,x_q] [ x 0 , … , x q ] k ≡ p k [ x 0 , … , x q ] for p k ( x ) = x k p_k(x)=x^k p k ( x ) = x k as introduced in Refs. [31, 32]. The divided difference of a polynomial has a closed form expression most easily written with the change of variables n → q + m n\to q+m n → q + m ,
[ x 0 , … , x q ] q + m = { 0 m < 0 1 m = 0 ∑ ∑ k j = m ∏ j = 0 q x j k j m > 0 , (44) [x_0,\ldots,x_q]^{q+m}=
\begin{cases}
0 & m<0\\
1 & m=0\\
\sum_{\sum k_j=m}\prod_{j=0}^{q}x_j^{k_j} & m>0,
\end{cases} \tag*{(44)} [ x 0 , … , x q ] q + m = ⎩ ⎨ ⎧ 0 1 ∑ ∑ k j = m ∏ j = 0 q x j k j m < 0 m = 0 m > 0 , (44)
as noted in the same notation in Refs. [31, 32] and derived with a different notation in Ref. [57 ] . Together, these two observations yield Eq. (42) .
As with previous PMR works [30, 32], we are also especially interested in the divided difference of the exponential (DDE) where we utilize the shorthand notation e t [ x 0 , … , x q ] ≡ f [ x 0 , … , x q ] e^{t}[x_0,\ldots,x_q]\equiv f[x_0,\ldots,x_q] e t [ x 0 , … , x q ] ≡ f [ x 0 , … , x q ] for f ( x ) = e t x f(x)=e^{tx} f ( x ) = e t x . Replacing f ( q + m ) ( 0 ) f^{(q+m)}(0) f ( q + m ) ( 0 ) with t q + m t^{q+m} t q + m gives the power series expansion of the DDE, as derived in the appendices of Refs. [31, 32]. Replacing the variable x → α x x\to\alpha x x → α x in Eq. (38) , we find the rescaling relation,
α q e t [ x 0 , … , α x q ] = e α t [ x 0 , … , x q ] , (45) \alpha^q e^{t}[x_0,\ldots,\alpha x_q]=e^{\alpha t}[x_0,\ldots,x_q], \tag*{(45)} α q e t [ x 0 , … , α x q ] = e α t [ x 0 , … , x q ] , (45)
which is useful in numerical schemes [52 , 64 ] and in computing the Laplace transform. In particular, combining Eq. (45) with Eq. (11) of Ref. [65] with P m ( x ) = 1 P_m(x)=1 P m ( x ) = 1 , we find
L { e α t [ x 0 , … , x q ] } = α q ∏ j = 0 q ( s − α x j ) (46) \mathcal{L}\left\{e^{\alpha t[x_0,\ldots,x_q]}\right\}=\frac{\alpha^q}{\prod_{j=0}^{q}(s-\alpha x_j)} \tag*{(46)} L { e α t [ x 0 , … , x q ] } = ∏ j = 0 q ( s − α x j ) α q (46)
where L \mathcal{L} L denotes the Laplace transform from t → s t \to s t → s . One can alternatively derive Eq. (46) by directly performing the integration to the contour integral definition in Eq. (38) , e.g. by Taylor expanding e α t x e^{\alpha t x} e α t x and re-summing term-by-term, legitimate by the uniform convergence of the exponential.
Computational complexity of estimators in PMR-QMC
Throughout this work, we refer to complexity of evaluating PMR-QMC estimators. For interested readers, more details and examples of tracking complexity in PMR-QMC estimation are contained in Sec. VIII of Ref. [26]. Here, we give a brief summary of how time is accounted.
When evaluating an estimator in PMR-QMC, we have O ( 1 ) O(1) O ( 1 ) access to each E z E_z E z and to each { exp { − β [ E z 0 ] } , exp { − β [ E z 0 , E z 1 ] } , … , exp { − β [ E z 0 , … , E z q − 1 ] } , exp { − β [ E z 0 , … , E z q ] } \{\exp\{-\beta[E_{z_0}]\},\exp\{-\beta[E_{z_0},E_{z_1}]\},\ldots,\exp\{-\beta[E_{z_0},\ldots,E_{z_{q-1}}]\},\exp\{-\beta[E_{z_0},\ldots,E_{z_q}]\} { exp { − β [ E z 0 ]} , exp { − β [ E z 0 , E z 1 ]} , … , exp { − β [ E z 0 , … , E z q − 1 ]} , exp { − β [ E z 0 , … , E z q ]} {citep}[23, 30], but evaluating the divided difference with the addition or removal of an input has an $O(q)$ cost {citep}[52]. For example, $E_z$ is an $O(1)$ estimator of $\langle D_0\rangle$ by {xref}Eq. (26) and {xref}Eq. (27) is an $O(q^2)$ estimator of $\langle D_0(\tau)D_0\rangle$. Generally, we expect $\langle q\rangle \propto \beta$ for many systems {citep}[32]`, but we also expect the total simulation time to be determined by the complexity of QMC updates rather than that of the estimators for a wide range of temperatures.
Code usage and empirical resource scaling
The open-source C++ implementation accompanying this work [33] extends previously developed PMR-QMC frameworks capable of simulating arbitrary spin-1/2 Hamiltonians [23 , 43 ] . The software has been designed to facilitate reproducibility and ease of use. In this section, we summarize the basic usage workflow and provide representative empirical benchmarks of computational resource requirements.
Code usage
Comprehensive usage instructions and example input files are provided in the accompanying README file [33]. Here, we provide a specific simple example to illustrate the ease with which one may use our code to estimate ES and FS for a user-defined Hamiltonian.
First, we define the Hamiltonian as a human-readable Pauli string in a file called H.txt. For concreteness,
-1.00 1 Z 2 Z 3 Z
-0.68 1 X
-0.73 1 Z 2 X
0.82 1 Y 3 Y
defines H.txt as a sum of random Pauli strings. To specify simulation parameters and what we intended to measure, we edit a file called parameters.hpp. For example,
#define beta 2.0
#define steps 100000
sets β = 2.0 \beta=2.0 β = 2.0 and the number of MC steps to 10 5 10^5 1 0 5 . We can also specify which measurements to make, i.e.,
#define MEASURE_HDIAG
#define MEASURE_HDIAG_CORR
#define MEASURE_HDIAG_EINT
#define MEASURE_HDIAG_FINT
informs our code to measure ⟨ D 0 ⟩ \langle D_0\rangle ⟨ D 0 ⟩ , ⟨ D 0 ( τ ) D 0 ⟩ \langle D_0(\tau)D_0\rangle ⟨ D 0 ( τ ) D 0 ⟩ (for τ \tau τ specified in the parameter file), ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ \int_0^\beta\langle D_0(\tau)D_0\rangle d\tau ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ and ∫ 0 β / 2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ \int_0^{\beta/2}\tau\langle D_0(\tau)D_0\rangle d\tau ∫ 0 β /2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ . Note that if our code detects that one intends to estimate both HDIAG and HDIAG_EINT, it automatically compute the ES via Eq. (20) via jackknife binning analysis [66 ] . Similarly, the FS is estimated via Eq. (21) provided HDIAG and HDIAG_FINT are measured.
We then compile and execute our C++ code, specifying whether we intend to perform parallelization with MPI or not, and if so, how many threads (approximately the number of CPU cores) to use. Compiling and executing the above example on our laptop using six threads, N p = 6 N_{\mathrm{p}} = 6 N p = 6 , yields a simulation summary text file whose final lines include,
Number of MPI processes: 6
Collecting statistics and finalizing the calculation
Total number of MC updates = 600000
Total mean(q) = 3.365
Total max(q) = 14
Total mean(sgn(W)) = 0.674666667
Total std.dev.(sgn(W)) = 0.00939374389
Total of observable #1: H_{diag}
Total mean(O) = -0.800449775
Total std.dev.(O) = 0.0133078895
Total of observable #2: measure_Hdiag_corr
Total mean(O) = 0.727002872
Total std.dev.(O) = 0.0109234895
Total of observable #3: measure_Hdiag_Eint
Total mean(O) = 1.58395933
Total std.dev.(O) = 0.015689912
Total of observable #4: measure_Hdiag_Fint
Total mean(O) = 0.377212308
Total std.dev.(O) = 0.0048761732
Total of derived observable: diagonal energy susceptibility
Total mean(O) = 0.302519643
Total std.dev.(O) = 0.0330613162
Total of derived observable: diagonal fidelity susceptibility
Total mean(O) = 0.0568523869
Total std.dev.(O) = 0.00782769997
Total elapsed cpu time = 0.894016 seconds
Wall-clock time = 0.174136 seconds
which gives the estimated value of each of the above observables, estimated over six MPI threads.
Out software supports changing the following basic simulation parameters,
β \beta β – the inverse temperature
N t h e r m N_{\mathrm{therm}} N therm – number of QMC moves used to thermalize/equilibrate (i.e., before any measurements are taken)
N m e a s N_{\mathrm{meas}} N meas – number of QMC moves during which measurements are taken
N s k i p N_{\mathrm{skip}} N skip – number of QMC moves between measurements (i.e., controls the sparsity of measurements)
N b i n s N_{\mathrm{bins}} N bins – number of bins for the error estimation via binning analysis (see Appendix B of Ref. [23 ] )
N p N_{\mathrm{p}} N p – number of MPI threads (approximately the number of CPU cores) used in lazy parallel accumulation,
all of which affect the expected total wall-clock time required for desired observable estimates to converge to thermal expectation values. Of particular note, N s k i p N_{\mathrm{skip}} N skip can control whether the QMC simulation time is dominated by QMC update costs or QMC measurements costs, as we will return to in the next section. In the above example, we chose β = 2 \beta= 2 β = 2 , N t h e r m = 0 N_{\mathrm{therm}} = 0 N therm = 0 , N m e a s = 10 5 N_{\mathrm{meas}} = 10^{5} N meas = 1 0 5 , N s k i p = 100 N_{\mathrm{skip}} = 100 N skip = 100 , N b i n s = 100 N_{\mathrm{bins}} = 100 N bins = 100 , and N p = 6 N_{\mathrm{p}} = 6 N p = 6 .
We also briefly mention some of the helpful outputs of our algorithm that are not just observable estimates. For all simulations, the statistics,
⟨ q ⟩ \langle q\rangle ⟨ q ⟩ – the empirical average value of q q q throughout simulation
q max q_{\max} q m a x – the maximum instantaneous value of q q q throughout simulation
⟨ s g n ⟩ \langle\mathrm{sgn}\rangle ⟨ sgn ⟩ – the average sign of the PMR-QMC weight throughout simulation
σ s g n \sigma_{\mathrm{sgn}} σ sgn – the standard deviation of sgn across the simulation
σ O \sigma_O σ O – one standard deviation error estimate for measured observable O, obtained by binning analysis [23 ]
are returned automatically. For the above example, we find ⟨ q ⟩ = 3.365 \langle q\rangle= 3.365 ⟨ q ⟩ = 3.365 , q max = 14 q_{\max} = 14 q m a x = 14 , ⟨ s g n ⟩ = 0.675 \langle\mathrm{sgn}\rangle= 0.675 ⟨ sgn ⟩ = 0.675 , and σ s g n = 0.009 \sigma_{\mathrm{sgn}} = 0.009 σ sgn = 0.009 . Provided at least 5 MPI threads are used, our simulation also automatically performs autocorrelation/thermalization testing. The testing principle is quite simple: each parallel simulation runs with a different random seed and is hence uncorrelated from one another after a sufficient number of burn-in steps, N t h e r m N_{\mathrm{therm}} N therm . One can thus compare the statistical error obtained from any single run to that of the error estimated across N p N_{\mathrm{p}} N p runs to check for autocorrelation.
Namely, if the two error estimates are comparable in value, this suggests that measurement blocks are effectively uncorrelated and thus that autocorrelation time is shorter than the block length. If the two estimates differ, albeit not substantially, this typically suggests that the autocorrelation time exceeds the block length, yet remains much shorter than the timescale of the entire simulation. Yet when the error from a single run significantly underestimates the error across runs (e.g., by a factor of 2 or more), this typically indicates that the autocorrelation time is too large, and longer simulations are required to ensure reliable estimates. In the above example, the thermalization test for ⟨ D 0 ⟩ \langle D_0\rangle ⟨ D 0 ⟩ reads
Observable #1: H_{diag}, mean of std.dev.(O) = 0.0353, std.dev. of mean(O) = 0.0409: test passed
which shows that the test passes. In fact, thermalization tests for all observables passed.
Additional empirical resource estimates
We provide additional empirical resource estimates and information, supplementing our brief summary in § 2 . In Table II , we summarize in greater detail (compared to Table I) the simulation input parameters, resources, and output statistics relevant to the simulation used to generate data for the main figures in our paper. As stated in the main text, 200MB of memory was more than enough for our simulations, so we focus on simulation time as the important resource estimate.
Table II. TABLE II. Simulation parameters, wall-clock times, and average value of q q q corresponding to Figure 1 , Figure 2 , Figure 3 , and Figure 4 . Ranges reflect the minimum and maximum value for any listed parameter across entire dataset. All simulations required less than 200 MB of memory per core. Except for the mild sign problem encountered in the model of Figure 4 (with worse average sign for any parameter studied given by ⟨ s g n ⟩ = 0.85 ( 4 ) \langle\mathrm{sgn}\rangle= 0.85(4) ⟨ sgn ⟩ = 0.85 ( 4 ) ), all other models were sign-problem free under PMR-QMC.
This table should be interpreted as a coarse estimate of simulation time (and not absolute or optimal times) needed to study the critical properties of these models for several reasons. First, we did not attempt to optimize these parameters for speed, but instead simply choose values large enough for correctness. In addition, we measured all observables of interest at the same time, so times are reflective of the slowest thermalization observable. Third, we did not keep hardware constant, as we ran simulations on a high performance computing (HPC) cluster with a queuing system.
Nevertheless, certain informative relative scalings can be observed from our simulations. Visually, this is perhaps most appealing seen in Figure 7 . Here, is is seen that criticality indicators ES and FS follow a similar trend to total simulation time and ⟨ q ⟩ \langle q\rangle ⟨ q ⟩ when studying Eq. (1) with a fixed set of simulation parameters and CPU hardware. We can produce an analogous plot for the ensemble of random rotations of this model, Figure 8 . Like the simple two qubit case, simulation time and ⟨ q ⟩ \langle q\rangle ⟨ q ⟩ follow a dependence on λ \lambda λ analogous to ES and FS. Yet, in addition, this ensemble can have a mild sign problem, which manifests particularly at λ = − 1 \lambda= -1 λ = − 1 (where the worse average sign is 0.85(4)). This sign problem asymmetry at the two peaks results in a corresponding asymmetry in the simulation time. In other words,
Figure 7. We again show the data plotted in Figure 1 and Figure 5 with the addition of an ES and ⟨ q ⟩ \langle q\rangle ⟨ q ⟩ plot in studying Eq. (1) . Simulations were performed on 2.3 GHz Intel i9 CPU with input parameters as given in Table II .
Figure 8. A timing study of the randomly rotated, post-selected ensemble studied in Figure 4 and described in Section D.
total simulation time—even for fixed simulation parameters and ⟨ q ⟩ \langle q\rangle ⟨ q ⟩ —can be adversely affected by the sign problem, as one would expect.
More generally, the instantaneous complexity of QMC updates and measurements in our algorithm depends on the dynamic quantum dimension parameter q q q , and we know ⟨ q ⟩ \langle q\rangle ⟨ q ⟩ itself scales with the difficulty of simulation. For example, when studying random quantum spin glasses with N N N spins and a transverse field term of strength Γ \Gamma Γ , Ref. [32] observed an empirical scaling of ⟨ q ⟩ ∼ Γ 2 β N \langle q\rangle\sim\Gamma^{2\beta N} ⟨ q ⟩ ∼ Γ 2 β N . In Figure 9 , we re-simulate the 4 × 4 4 \times4 4 × 4 TFIM studied in Figure 2 , with general simulation parameters as listed in the caption. This plot empirically illustrates two things. First, in the left plot, we indeed find ⟨ q ⟩ ∼ β \langle q\rangle\sim\beta ⟨ q ⟩ ∼ β as observed previously [32]. Second, the sparsity of measurements (controlled by N s k i p N_{\mathrm{skip}} N skip ) has a large effect on simulation time when estimating expensive observables such as FS. Furthermore, we verify empirically the claim that the ES has O ( 1 ) O(1) O ( 1 ) cost, as simulation time when measuring ES or doing no measurement matches each other well regardless of N s k i p N_{\mathrm{skip}} N skip . As summarized in Table II, the actual simulation parameters used to generate Figure 2 were in the sparse measurement regime of N s k i p = 10 3 N_{\mathrm{skip}} = 10^{3} N skip = 1 0 3 . We verify this empirically in Figure 10 by repeating the TFIM calculation with comparable parameters. Specifically, we find that simulation time is roughly independent of the measurement strategy, even when measuring the expensive FS quantity.
Figure 9. We re-simulate the 4 × 4 4 \times4 4 × 4 TFIM model studied in Figure 2 . Simulations were performed on N p = 6 N_{\mathrm{p}} = 6 N p = 6 threads in parallel on 2.3 GHz Intel i9 CPUs with N t h e r m = 0 N_{\mathrm{therm}} = 0 N therm = 0 , N m e a s = 10 6 N_{\mathrm{meas}} = 10^{6} N meas = 1 0 6 and N b i n s = 100 N_{\mathrm{bins}} = 100 N bins = 100 . RNG seeds were fixed for each thread across different β \beta β . The three curves correspond to three measurement strategies: measure nothing, measure only (diagonal) ES, or measure only (diagonal) FS. (Left) We show ⟨ q ⟩ \langle q\rangle ⟨ q ⟩ as a function of β \beta β . (b) We set N s k i p = 1 N_{\mathrm{skip}} = 1 N skip = 1 so that we sample estimators densely at each QMC step/update. (c) We set N s k i p = 100 N_{\mathrm{skip}} = 100 N skip = 100 so that we sample estimators sparsely every 100 QMC steps.
Figure 10. We repeat the numerical experiment on Figure 9 but with parameters that more closely match those actually used to generate Figure 2 . Namely, we choose N t h e r m = 10 6 N_{\mathrm{therm}} = 10^{6} N therm = 1 0 6 , N m e a s = 10 7 N_{\mathrm{meas}} = 10^{7} N meas = 1 0 7 , N s k i p = 10 3 N_{\mathrm{skip}} = 10^{3} N skip = 1 0 3 , N b i n s = 100 N_{\mathrm{bins}} = 100 N bins = 100 , and N p = 50 N_{\mathrm{p}} = 50 N p = 50 . Using this many cores, we again use the USC HPC cluster but this time with a fixed 2.6 GHz Intel Xeon E5-2640 CPU for all simulations. Wall-clock time scales as a modest power law in beta, ∼ β 1.23 \sim\beta^{1.23} ∼ β 1.23 for all three curves, consistent with Fig. 3 of Ref. [23 ] .
Parity restricted PMR-QMC for the TFIM
In our transverse-field Ising model (TFIM) numerical experiments of Section II, i.e. Figure 2 , we computed the ES and FS restricted to the positive parity subspace of the TFIM. We briefly discuss the details of our methodology. First, we study a rotated TFIM for which the transverse field term is ∑ i Z i \sum_i Z_i ∑ i Z i , Eq. (2) . In doing so, the parity operator,
P = ∏ i = 1 N Z i (47) \mathcal{P} = \prod_{i=1}^{N} Z_i \tag*{(47)} P = i = 1 ∏ N Z i (47)
commutes with the TFIM, [ H , P ] = 0 [H,\mathcal{P}] = 0 [ H , P ] = 0 . Hence, the parity P = ± 1 P = \pm1 P = ± 1 is a good quantum number, and it is well known that the groundstate of the TFIM lies in the P = + 1 P = +1 P = + 1 parity sector by the Perron–Frobenius theorem [18].
For our rotated TFIM choice, P \mathcal{P} P is purely diagonal. For both SSE-QMC [18] and PMR-QMC (see Eq. (23) ), computational basis elements ∣ z ⟩ |z\rangle ∣ z ⟩ are part of the QMC configuration. At any given time in simulation, then, one can query the eigenvalue of P \mathcal{P} P ∣ z ⟩ |z\rangle ∣ z ⟩ , which is the instantaneous parity P c P_c P c . Note that, in fact, ∣ z ⟩ |z\rangle ∣ z ⟩ is a bitstring, so the parity can readily be obtained by determining if there are an odd number of 1’s in ∣ z ⟩ |z\rangle ∣ z ⟩ or not. In the SSE-QMC approach [18], the authors simply keep track of P c P_c P c during simulation and post-select on measurement outcomes.
In contrast, we perform PMR-QMC sampling restricted to the positive parity subspace the entire simulation. This is possible because the set of PMR-QMC updates is standardized in terms of the permutation group that comprises H H H . A careful look at the updates for spin-1/2 systems [23 ] reveals that there are only two updates that can change a configurations parity: a classical update or a block swap. In our TFIM implementation [33], we simply choose an initial ∣ z ⟩ |z\rangle ∣ z ⟩ with positive parity and only allow classical updates or block swaps that preserve parity. Both can be altered to preserve parity without post-selection, which is therefore more efficient than the SSE approach.
In a standard classical update, a random bit is flipped. In our code, we simply flip two random bits instead, which preserves parity. In a standard block swap, the classical state is also updated. Specifically, the permutation string S i q S_{i_q} S i q is split into two S i q = S 2 S 1 S_{i_q}=S_2S_1 S i q = S 2 S 1 for S 1 = P i k ⋯ P i 1 S_1=P_{i_k}\cdots P_{i_1} S 1 = P i k ⋯ P i 1 and S 2 = P i q ⋯ P i k + 1 S_2=P_{i_q}\cdots P_{i_{k+1}} S 2 = P i q ⋯ P i k + 1 for k ∈ { 1 , … , q − 1 } k\in\{1,\ldots,q-1\} k ∈ { 1 , … , q − 1 } chosen randomly. The classical state at position k k k is then ∣ z ′ ⟩ = S 1 ∣ z ⟩ |z'\rangle=S_1|z\rangle ∣ z ′ ⟩ = S 1 ∣ z ⟩ with energy E z ′ E_{z'} E z ′ . The updated block-swap configuration is then C ′ = { ∣ z ′ ⟩ , S 1 S 2 } \mathcal{C}'=\{|z'\rangle,S_1S_2\} C ′ = { ∣ z ′ ⟩ , S 1 S 2 } , which swaps S 1 S_1 S 1 and S 2 S_2 S 2 while updating ∣ z ⟩ → ∣ z ′ ⟩ |z\rangle\to|z'\rangle ∣ z ⟩ → ∣ z ′ ⟩ . The parity ∣ z ′ ⟩ |z'\rangle ∣ z ′ ⟩ can change based on S 1 S_1 S 1 .
For the TFIM, however, each P i P_i P i is just a 2-body X X X string, i.e., X 1 X 2 X_1X_2 X 1 X 2 , S i q = 1 S_{i_q}=1 S i q = 1 if and only if each permutation appears an even number of times. Together, this means S 1 S_1 S 1 flips the parity of ∣ z ′ ⟩ |z'\rangle ∣ z ′ ⟩ if and only if k k k is odd. Hence, parity can be preserved by only sampling k ∈ { 1 , … , q − 1 } k\in\{1,\ldots,q-1\} k ∈ { 1 , … , q − 1 } that is also even. This can easily be accomplished, and is what we do in our code [33]. Together, these small changes ensure we stay in the P = + 1 P=+1 P = + 1 parity sector during the entire PMR-QMC simulation.
Additional details on generating special unitaries
Consider U = ∑ k = 1 L c k Q k U=\sum_{k=1}^{L}c_kQ_k U = ∑ k = 1 L c k Q k for c ∈ R L \mathbf{c}\in\mathbb{R}^{L} c ∈ R L and each Q k Q_k Q k a Pauli matrix over n n n spins (we use Q Q Q to distinguish from the permutation P j P_j P j in the PMR form of H H H ). By construction, we can efficiently form the matrix U H ( λ ) U † UH(\lambda)U^\dagger U H ( λ ) U † for H ( λ ) = Z 1 Z 2 + 0.1 ( X 1 + X 2 ) + λ ( Z 1 + Z 2 ) H(\lambda)=Z_1Z_2+0.1(X_1+X_2)+\lambda(Z_1+Z_2) H ( λ ) = Z 1 Z 2 + 0.1 ( X 1 + X 2 ) + λ ( Z 1 + Z 2 ) , our prototypical example Hamiltonian from Ref. [45 ] , whenever L L L is polynomial in n n n . This is because for each term in H H H , we need only perform L 2 L^2 L 2 Pauli conjugations, i.e. compute terms like Q k X 1 Q l Q_kX_1Q_l Q k X 1 Q l , which are themselves computable in O ( n ) O(n) O ( n ) time using a look-up table or a symplectic inner product technique as in Clifford simulations.
In addition, U U U can easily be shown to be unitary whenever ∥ c ∥ 2 = 1 \lVert\mathbf{c}\rVert_2=1 ∥ c ∥ 2 = 1 and { Q k } k = 1 L \{Q_k\}_{k=1}^{L} { Q k } k = 1 L all anti-commute (see Eq. (6) in [67 ] ). The largest maximal set of anti-commuting Paulis is 2 n + 1 2n+1 2 n + 1 , and there is an O ( n ) O(n) O ( n ) algorithm to generate a canonical set of this type [68 ] . Let Q \mathcal{Q} Q denote this canonical set of 201 Paulis for a 100-spin system, which, in particular, includes X ⊗ 100 X^{\otimes100} X ⊗ 100 . We can now describe our algorithm to generate 10 random unitaries such that H U i ≡ U i H ( λ ) U i † H_{U_i}\equiv U_iH(\lambda)U_i^\dagger H U i ≡ U i H ( λ ) U i † satisfies the four properties described in the main text.
To begin with, we generate 50 random unitaries by (a) selecting L ∈ [ 1 , … , 201 ] L\in[1,\ldots,201] L ∈ [ 1 , … , 201 ] uniformly at random, (b) construct a random list of anti-commuting Paulis of the form { X ⊗ 100 } ∪ { Q i } i = 2 L \{X^{\otimes100}\}\cup\{Q_i\}_{i=2}^{L} { X ⊗ 100 } ∪ { Q i } i = 2 L for each Q i Q_i Q i drawn uniformly without replacement from Q \mathcal{Q} Q , (c) generating c i ∼ N ( 0 , 1 ) c_i\sim\mathcal{N}(0,1) c i ∼ N ( 0 , 1 ) for i = 1 , … , L i=1,\ldots,L i = 1 , … , L independently and then renormalizing. In step (b), we always include X ⊗ 100 X^{\otimes100} X ⊗ 100 to ensure each H U i ( λ ) ≡ U i H ( λ ) U i † H_{U_i}(\lambda)\equiv U_iH(\lambda)U_i^\dagger H U i ( λ ) ≡ U i H ( λ ) U i † has non-trivial support on all 100 spins. By construction, H U i H_{U_i} H U i has hundreds of Pauli terms, and yet, it is easy to generate and store. What remains to show is that we can find a subset of 10 without a severe sign problem.
To our knowledge, there is no simple calculation to check for the sign problem for these models a priori. So in practice, we simply ran a PMR-QMC simulation for each model for β = 5 \beta=5 β = 5 and λ = 1 \lambda=1 λ = 1 , which approximately the critical point for this model. The PMR-QMC code in Ref. [23 , 43 ] automatically tracks the average and variance of the sign of the QMC weight, so we then simply post-selected those models with the highest average sign. Empirically, we find the worst average sign in this set of 10 is 0.9983 ± 0.0006 0.9983\pm0.0006 0.9983 ± 0.0006 (this is 2 σ 2\sigma 2 σ ), so this subset is essentially sign problem free at λ = 1.0 \lambda=1.0 λ = 1.0 (but this does not hold for all λ \lambda λ as seen before in Figure 8 ). This post-selection step is contained in a Jupyter notebook of our code [33], namely in before_fig2_post_selection.ipynb. We provide a graphical summary of the practical meaning of this post selection process in Figure 11 . In short, the worse the sign problem is, the longer the simulation takes to run and the less accurate it is for a fixed set of QMC simulation parameters. By post-selecting on those models with the 10 highest average signs, we thus generate an ensemble with random, high weight Pauli terms that is nevertheless efficiently simulable in PMR-QMC.
Figure 11. Here, we plot summary statistics of all 50 random models described generally above. Each plot shows how the average sign (for fixed QMC parameters) is correlated with important simulation properties like (left) simulation time (b) average value of q q q , and (c) percent error in estimating the FS. In Figure 4 , we only simulate those 10 random models with the highest average sign in this plot.
Derivations of PMR-QMC estimators for pure diagonal or pure off-diagonal driving
We derive the ES and FS estimators for the H 1 ∝ D 0 H_{1} \propto D_{0} H 1 ∝ D 0 case stated in Section IV. Most notably, we prove Theorems 1 and 2. We then substantiate the claim that these same estimators also straightforwardly carry over to the H 1 ∝ H − D 0 H_{1} \propto H-D_{0} H 1 ∝ H − D 0 case.
Derivation strategy
Recall from the main text (or see Ref. [26]) that a PMR-QMC estimator O C O_{C} O C is a function of C C C such that
⟨ O ⟩ = ∑ C w C O C ∑ C w C , (48) \langle O\rangle= \frac{\sum_{C} w_{C}O_{C}}{\sum_{C}w_{C}}, \tag*{(48)} ⟨ O ⟩ = ∑ C w C ∑ C w C O C , (48)
for w C = D ( z , S i q ) e − β [ E z 0 , … , E z q ] w_{C}=D_{(z,S_{i_{q}})}e^{-\beta[E_{z_{0}},\ldots,E_{z_{q}}]} w C = D ( z , S i q ) e − β [ E z 0 , … , E z q ] the generalized PMR-QMC Boltzmann weight. For convenience, we write O C = ^ ⟨ O ⟩ O_{C}\widehat{=}\langle O\rangle O C = ⟨ O ⟩ to be read “O C O_{C} O C estimates ⟨ O ⟩ \langle O\rangle ⟨ O ⟩ .” Our first goal is to derive an estimator for the ES when H 1 ∝ D 0 H_{1}\propto D_{0} H 1 ∝ D 0 .
In most practical applications, H 1 ∝ D 0 H_{1}\propto D_{0} H 1 ∝ D 0 follows from the relation λ H 1 = D 0 \lambda H_{1}=D_{0} λ H 1 = D 0 , i.e., the driving term multiplied by λ \lambda λ is the diagonal portion of H H H . As such, ⟨ H 1 ⟩ = ⟨ D 0 ⟩ / λ \langle H_{1}\rangle=\langle D_{0}\rangle/\lambda ⟨ H 1 ⟩ = ⟨ D 0 ⟩ / λ , and more generally, it is enough to simply estimate ⟨ D 0 ⟩ \langle D_{0}\rangle ⟨ D 0 ⟩ and related quantities. To this end, we observe
χ E D 0 ( λ ; β ) = ∫ 0 β ( ⟨ D 0 ( τ ) D 0 ⟩ − ⟨ D 0 ⟩ 2 ) d τ . (49) \chi_{E}^{D_{0}}(\lambda;\beta)=\int_{0}^{\beta}\left(\langle D_{0}(\tau)D_{0}\rangle-\langle D_{0}\rangle^{2}\right)d\tau. \tag*{(49)} χ E D 0 ( λ ; β ) = ∫ 0 β ( ⟨ D 0 ( τ ) D 0 ⟩ − ⟨ D 0 ⟩ 2 ) d τ . (49)
gives the ES (see Eq. (20) ) up to a multiplicative correction, i.e., χ E H 1 = χ E D 0 / λ 2 \chi_{E}^{H_{1}}=\chi_{E}^{D_{0}}/\lambda^{2} χ E H 1 = χ E D 0 / λ 2 (or more generally just χ E H 1 ∝ χ E D 0 \chi_{E}^{H_{1}}\propto\chi_{E}^{D_{0}} χ E H 1 ∝ χ E D 0 ). Thus, we focus on attention on estimating χ E D 0 \chi_{E}^{D_{0}} χ E D 0 .
Our strategy is to first derive estimators for ⟨ D 0 ⟩ \langle D_{0}\rangle ⟨ D 0 ⟩ and ⟨ D 0 ( τ ) D 0 ⟩ \langle D_{0}(\tau)D_{0}\rangle ⟨ D 0 ( τ ) D 0 ⟩ in Section E2. As we shall see, E z = ^ ⟨ D 0 ⟩ E_{z}\widehat{=}\langle D_{0}\rangle E z = ⟨ D 0 ⟩ does not depend on τ \tau τ . Then, in Section E3, we show ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ \int_{0}^{\beta}\langle D_{0}(\tau)D_{0}\rangle d\tau ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ can be evaluated exactly and analytically into a valid estimator via novel divided difference relations. Together, these results give an O ( q 2 ) O(q^{2}) O ( q 2 ) estimator for ES. In Section E3, we further simplify our estimator into a constant time O ( 1 ) O(1) O ( 1 ) ES estimator using additional novel divided difference relations. This completes most of the work of proving Theorem 1.
By a similar chain of reasoning,
χ F D 0 ( λ ; β ) = ∫ 0 β / 2 τ ( ⟨ D 0 ( τ ) D 0 ⟩ − ⟨ D 0 ⟩ 2 ) d τ , (50) \chi_{F}^{D_{0}}(\lambda;\beta)=\int_{0}^{\beta/2}\tau\left(\langle D_{0}(\tau)D_{0}\rangle-\langle D_{0}\rangle^{2}\right)d\tau, \tag*{(50)} χ F D 0 ( λ ; β ) = ∫ 0 β /2 τ ( ⟨ D 0 ( τ ) D 0 ⟩ − ⟨ D 0 ⟩ 2 ) d τ , (50)
gives the FS (see Eq. (21) ) up to a multiplicative correction, and our strategy remains similar. Namely, we show in Section E5 that ∫ 0 β / 2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ \int_{0}^{\beta/2}\tau\langle D_{0}(\tau)D_{0}\rangle d\tau ∫ 0 β /2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ can also be evaluated exactly and analytically via novel divided difference relations. This results in an O ( q 4 ) O(q^{4}) O ( q 4 ) estimator for FS. By yet additional novel divided difference relations, we reduce this to O ( q 3 ) O(q^{3}) O ( q 3 ) operations in Section E6. This completes most of the work of proving Theorem 2.
Finally, we show how all the estimators we derived for the H ∝ D 0 H\propto D_{0} H ∝ D 0 case carry over straightforwardly to the H 1 ∝ H − D 0 H_{1}\propto H-D_{0} H 1 ∝ H − D 0 case and with the same complexities in Appendix E7 thus completing the justification for Theorems 1 and 2.
Estimators for ⟨ D 0 ⟩ \langle D_{0}\rangle ⟨ D 0 ⟩ and ⟨ D 0 ( τ ) D 0 ⟩ \langle D_{0}(\tau)D_{0}\rangle ⟨ D 0 ( τ ) D 0 ⟩
Since ⟨ z ∣ D 0 e − β H ∣ z ⟩ = E z ⟨ z ∣ e − β H ∣ z ⟩ \langle z|D_{0}e^{-\beta H}|z\rangle=E_{z}\langle z|e^{-\beta H}|z\rangle ⟨ z ∣ D 0 e − β H ∣ z ⟩ = E z ⟨ z ∣ e − β H ∣ z ⟩ , then by a direct off-diagonal series expansion of Tr [ D 0 e − β H ] \operatorname{Tr}[D_{0}e^{-\beta H}] Tr [ D 0 e − β H ] (see also Sec. VIII.A of Ref. [26]), we find
E z = ^ ⟨ D 0 ⟩ , (51) E_{z}\widehat{=}\langle D_{0}\rangle, \tag*{(51)} E z = ⟨ D 0 ⟩ , (51)
is an O ( 1 ) O(1) O ( 1 ) estimator (see Section A4).
Next, we derive an estimator for ⟨ D 0 ( τ ) D 0 ⟩ \langle D_0(\tau)D_0\rangle ⟨ D 0 ( τ ) D 0 ⟩ . One approach is by direct off-diagonal series expansion and simplification [26]. Here, we argue that direct Leibniz rule logic (Eq. (41) ), we can correctly conclude,
⟨ z ∣ D 0 e − τ H D 0 e − ( β − τ ) H ∣ z ⟩ = E z ∑ j = 0 q E z j e − τ [ E z j , … , E z q ] e − ( β − τ ) [ E z 0 , … , E z j ] . (52) \langle z|D_0e^{-\tau H}D_0e^{-(\beta-\tau)H}|z\rangle=E_z\sum_{j=0}^{q}E_{z_j}e^{-\tau[E_{z_j},\ldots,E_{z_q}]}e^{-(\beta-\tau)[E_{z_0},\ldots,E_{z_j}]}. \tag*{(52)} ⟨ z ∣ D 0 e − τ H D 0 e − ( β − τ ) H ∣ z ⟩ = E z j = 0 ∑ q E z j e − τ [ E z j , … , E z q ] e − ( β − τ ) [ E z 0 , … , E z j ] . (52)
The basic idea is simple: without the middle D 0 D_0 D 0 term, we can safely apply the Leibniz rule to the off-diagonal expansion since e − τ H e^{-\tau H} e − τ H and e − ( β − τ ) H e^{-(\beta-\tau)H} e − ( β − τ ) H commute. Accounting for the non-commuting D 0 D_0 D 0 , however, is simple—we just pick up a factor of E z j E_{z_j} E z j from the D 0 ∣ z j ⟩ D_0|z_j\rangle D 0 ∣ z j ⟩ as shown. Hence, we find
( D 0 ( τ ) D 0 ) C ≡ E z e − β [ E z 0 , … , E z q ] ∑ j = 0 q E z j e − τ [ E z j , … , E z q ] e − ( β − τ ) [ E z 0 , … , E z j ] ≤ ⟨ D 0 ( τ ) D 0 ⟩ . (53) (D_0(\tau)D_0)_{\mathrm C}\equiv\frac{E_z}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{j=0}^{q}E_{z_j}e^{-\tau[E_{z_j},\ldots,E_{z_q}]}e^{-(\beta-\tau)[E_{z_0},\ldots,E_{z_j}]}\leq\langle D_0(\tau)D_0\rangle. \tag*{(53)} ( D 0 ( τ ) D 0 ) C ≡ e − β [ E z 0 , … , E z q ] E z j = 0 ∑ q E z j e − τ [ E z j , … , E z q ] e − ( β − τ ) [ E z 0 , … , E z j ] ≤ ⟨ D 0 ( τ ) D 0 ⟩ . (53)
as claimed in Eq. (27) .
Energy susceptibility in quadratic time
We shall show
− E z 0 e − β [ E z 0 , … , E z q ] ∑ j = 0 q E z j e − β [ E z 0 , … , E z q , E z j ] ≤ ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ . (54) \frac{-E_{z_0}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{j=0}^{q}E_{z_j}e^{-\beta[E_{z_0},\ldots,E_{z_q},E_{z_j}]}\leq\int_{0}^{\beta}\langle D_0(\tau)D_0\rangle d\tau. \tag*{(54)} e − β [ E z 0 , … , E z q ] − E z 0 j = 0 ∑ q E z j e − β [ E z 0 , … , E z q , E z j ] ≤ ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ . (54)
Combined with Eqs. (Eqs. (49) and (E4)), this gives an estimator for χ E D 0 \chi_{E}^{D_0} χ E D 0 that requires O ( q 2 ) O(q^2) O ( q 2 ) operations (see Section A 4). By inspection of Eq. (53) , showing Eq. (54) amounts to proving the following integral relation.
Lemma 1 (Convolution lemma [59 ] ).
∫ 0 β e − τ [ x j + 1 , … , x q ] e − ( β − τ ) [ x 0 , … , x j ] d τ = − e − β [ x 0 , … , x q ] . (55) \int_{0}^{\beta}e^{-\tau[x_{j+1},\ldots,x_q]}e^{-(\beta-\tau)[x_0,\ldots,x_j]}\,d\tau=-e^{-\beta[x_0,\ldots,x_q]}. \tag*{(55)} ∫ 0 β e − τ [ x j + 1 , … , x q ] e − ( β − τ ) [ x 0 , … , x j ] d τ = − e − β [ x 0 , … , x q ] . (55)
Proof. For convenience, we define the functions
f ( t ) = e − t [ x j + 1 , … , x q ] (56) f(t)=e^{-t[x_{j+1},\ldots,x_q]} \tag*{(56)} f ( t ) = e − t [ x j + 1 , … , x q ] (56)
g ( t ) = e − t [ x 0 , … , x j ] (57) g(t)=e^{-t[x_0,\ldots,x_j]} \tag*{(57)} g ( t ) = e − t [ x 0 , … , x j ] (57)
The convolution of these functions,
( f ∗ g ) ( t ) = ∫ 0 t f ( τ ) g ( t − τ ) d τ (58) (f*g)(t)=\int_{0}^{t}f(\tau)g(t-\tau)\,d\tau \tag*{(58)} ( f ∗ g ) ( t ) = ∫ 0 t f ( τ ) g ( t − τ ) d τ (58)
is by construction the integral we want to evaluate for t = β t=\beta t = β . Let L { f ( t ) } \mathcal{L}\{f(t)\} L { f ( t )} denote the Laplace transform of f ( t ) f(t) f ( t ) from t → s t\to s t → s . By the convolution property of the Laplace transform and Eq. (46) , we find
L { ( f ∗ g ) ( t ) } = L { f ( t ) } L { g ( t ) } (59) \mathcal{L}\{(f*g)(t)\}=\mathcal{L}\{f(t)\}\mathcal{L}\{g(t)\} \tag*{(59)} L {( f ∗ g ) ( t )} = L { f ( t )} L { g ( t )} (59)
= ( ( − 1 ) q − j − 1 ∏ l = j + 1 q ( s + x l ) ) ( ( − 1 ) j ∏ m = 0 j ( s + x m ) ) = ( − 1 ) q − 1 ∏ l = 0 q ( s + x l ) = L { − e − t [ x 0 , … , x q ] } . (60) =\left(\frac{(-1)^{q-j-1}}{\prod_{l=j+1}^{q}(s+x_l)}\right)\left(\frac{(-1)^j}{\prod_{m=0}^{j}(s+x_m)}\right)=\frac{(-1)^{q-1}}{\prod_{l=0}^{q}(s+x_l)}=\mathcal{L}\left\{-e^{-t[x_0,\ldots,x_q]}\right\}. \tag*{(60)} = ( ∏ l = j + 1 q ( s + x l ) ( − 1 ) q − j − 1 ) ( ∏ m = 0 j ( s + x m ) ( − 1 ) j ) = ∏ l = 0 q ( s + x l ) ( − 1 ) q − 1 = L { − e − t [ x 0 , … , x q ] } . (60)
Taking the inverse Laplace transform of the first and final expression proves the claimed integral relation. □
Inspection of Eq. (53) and Eq. (55) shows the validity of Eq. (54) immediately. As an aside, we remark that a direct proof by series expanding both DDE via Eq. (42) , integrating term-by-term, regrouping, and simplifying is also possible.
Energy susceptibility in constant time
The ES estimator in Eq. (54) requires O ( q 2 ) O(q^2) O ( q 2 ) operations to evaluate, but it can be simplified into an O ( 1 ) O(1) O ( 1 ) estimator and validate Theorem 1 in a few steps. We begin with a simple proposition.
Proposition 1 (Re-scaling relation [59 ] ).
e − τ [ x 0 , … , x q ] = ( − τ ) q e [ − τ x 0 , … , − τ x q ] . (61) e^{-\tau[x_0,\ldots,x_q]} = (-\tau)^q e^{[-\tau x_0,\ldots,-\tau x_q]}. \tag*{(61)} e − τ [ x 0 , … , x q ] = ( − τ ) q e [ − τ x 0 , … , − τ x q ] . (61) Proof. By the change of variables y = − τ z y=-\tau z y = − τ z in Eq. (38) , we find the claimed result.
We can now simplify the sum in Eq. (54) into a compact derivative form.
Lemma 2 (A weighted, repeated argument sum simplification [59 ] ).
∑ j = 0 q x j e − τ [ x 0 , … , x q , x j ] = ( τ ∂ ∂ τ − q ) e − τ [ x 0 , … , x q ] . (62) \sum_{j=0}^{q} x_j e^{-\tau[x_0,\ldots,x_q,x_j]} = \left(\tau\frac{\partial}{\partial\tau}-q\right)e^{-\tau[x_0,\ldots,x_q]}. \tag*{(62)} j = 0 ∑ q x j e − τ [ x 0 , … , x q , x j ] = ( τ ∂ τ ∂ − q ) e − τ [ x 0 , … , x q ] . (62) Proof. We prove this by induction.
Base case. When q = 0 q=0 q = 0 , we have x 0 e − τ [ x 0 , x 0 ] = x 0 ∂ e − τ x 0 / ∂ x 0 = − τ x 0 e − τ x 0 x_0e^{-\tau[x_0,x_0]}=x_0\partial e^{-\tau x_0}/\partial x_0=-\tau x_0e^{-\tau x_0} x 0 e − τ [ x 0 , x 0 ] = x 0 ∂ e − τ x 0 / ∂ x 0 = − τ x 0 e − τ x 0 , so Eq. (62) holds.
Induction step. By Prop. 1, we write the right-hand side as,
( τ ∂ τ − ( q + 1 ) ) ( − τ ) q + 1 e [ − τ x 0 , … , − τ x q + 1 ] = − ( − τ ) q + 2 ∂ ∂ τ e [ − τ x 0 , … , − τ x q + 1 ] (63) (\tau\partial_\tau-(q+1))(-\tau)^{q+1}e^{[-\tau x_0,\ldots,-\tau x_{q+1}]} = -(-\tau)^{q+2}\frac{\partial}{\partial\tau}e^{[-\tau x_0,\ldots,-\tau x_{q+1}]} \tag*{(63)} ( τ ∂ τ − ( q + 1 )) ( − τ ) q + 1 e [ − τ x 0 , … , − τ x q + 1 ] = − ( − τ ) q + 2 ∂ τ ∂ e [ − τ x 0 , … , − τ x q + 1 ] (63) = − ( − τ ) q + 2 1 2 π i ∮ Γ ∂ ∂ τ e z ∏ i = 0 q + 1 ( z + τ x i ) d z = ∑ j = 0 q + 1 x j e − τ [ x 0 , … , x q + 1 , x j ] . (64) = -(-\tau)^{q+2}\frac{1}{2\pi i}\oint_{\Gamma}\frac{\partial}{\partial\tau}\frac{e^z}{\prod_{i=0}^{q+1}(z+\tau x_i)}\,dz = \sum_{j=0}^{q+1}x_j e^{-\tau[x_0,\ldots,x_{q+1},x_j]}. \tag*{(64)} = − ( − τ ) q + 2 2 π i 1 ∮ Γ ∂ τ ∂ ∏ i = 0 q + 1 ( z + τ x i ) e z d z = j = 0 ∑ q + 1 x j e − τ [ x 0 , … , x q + 1 , x j ] . (64) Therefore, Eq. (62) is true for all q q q .
To turn this simplification into a useful result for PMR-QMC estimation, we employ the following proposition.
Proposition 2 (Parametric derivative). [59 ]
∂ ∂ τ e − τ [ x 0 , … , x q ] = − x 0 e − τ [ x 0 , … , x q ] − e − τ [ x 1 , … , x q ] . (65) \frac{\partial}{\partial\tau}e^{-\tau[x_0,\ldots,x_q]}=-x_0e^{-\tau[x_0,\ldots,x_q]}-e^{-\tau[x_1,\ldots,x_q]}. \tag*{(65)} ∂ τ ∂ e − τ [ x 0 , … , x q ] = − x 0 e − τ [ x 0 , … , x q ] − e − τ [ x 1 , … , x q ] . (65) Proof. First, define g ( x ) = − x e − τ x g(x)=-xe^{-\tau x} g ( x ) = − x e − τ x for convenience. By Eq. (38) ,
∂ ∂ τ e − τ [ x 0 , … , x q ] ≡ ∂ ∂ τ 1 2 π i ∮ Γ e − τ z ∏ i = 0 q ( z − x i ) d z = 1 2 π i ∮ Γ − z e − τ z ∏ i = 0 q ( z − x i ) d z ≡ g [ x 0 , … , x q ] . (66) \frac{\partial}{\partial\tau}e^{-\tau[x_0,\ldots,x_q]}\equiv\frac{\partial}{\partial\tau}\frac{1}{2\pi i}\oint_{\Gamma}\frac{e^{-\tau z}}{\prod_{i=0}^{q}(z-x_i)}\,dz=\frac{1}{2\pi i}\oint_{\Gamma}\frac{-ze^{-\tau z}}{\prod_{i=0}^{q}(z-x_i)}\,dz\equiv g[x_0,\ldots,x_q]. \tag*{(66)} ∂ τ ∂ e − τ [ x 0 , … , x q ] ≡ ∂ τ ∂ 2 π i 1 ∮ Γ ∏ i = 0 q ( z − x i ) e − τ z d z = 2 π i 1 ∮ Γ ∏ i = 0 q ( z − x i ) − z e − τ z d z ≡ g [ x 0 , … , x q ] . (66) Employing the Leibniz rule, Eq. (41) , we get the desired result.
Corollary 1 (Computing the weighted, repeated argument sum [59 ] ).
∑ j = 0 q x j e − τ [ x 0 , … , x q , x j ] = { ( − x 0 τ − q ) e − τ [ x 0 , … , x q ] − τ e − τ [ x 1 , … , x q ] , for q > 0 , − τ x 0 e − τ x 0 , for q = 0. (67) \sum_{j=0}^{q}x_j e^{-\tau[x_0,\ldots,x_q,x_j]}=
\begin{cases}
(-x_0\tau-q)e^{-\tau[x_0,\ldots,x_q]}-\tau e^{-\tau[x_1,\ldots,x_q]}, & \text{for } q>0,\\
-\tau x_0e^{-\tau x_0}, & \text{for } q=0.
\end{cases} \tag*{(67)} j = 0 ∑ q x j e − τ [ x 0 , … , x q , x j ] = { ( − x 0 τ − q ) e − τ [ x 0 , … , x q ] − τ e − τ [ x 1 , … , x q ] , − τ x 0 e − τ x 0 , for q > 0 , for q = 0. (67) Proof. This follows from applying Prop. 2 to Lem. 2.
We now prove the main part of Theorem 1—that we have an O ( 1 ) O(1) O ( 1 ) estimator for ES—since
β E z 0 2 + q E z 0 + 1 q > 0 β E z 0 e − β [ E z 0 , … , E z q − 1 ] e − β [ E z 0 , … , E z q ] ≤ ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ . (68) \beta E_{z_0}^{2}+qE_{z_0}+1_{q>0}\beta E_{z_0}\frac{e^{-\beta[E_{z_0,\ldots,E_{z_{q-1}}]}}}{e^{-\beta[E_{z_0,\ldots,E_{z_q}]}}} \leq\int_0^\beta\langle D_0(\tau)D_0\rangle d\tau. \tag*{(68)} β E z 0 2 + q E z 0 + 1 q > 0 β E z 0 e − β [ E z 0 , … , E z q ] e − β [ E z 0 , … , E z q − 1 ] ≤ ∫ 0 β ⟨ D 0 ( τ ) D 0 ⟩ d τ . (68)
Proof. The original ES estimator in Eq. (54) can be simplified using Eq. (67) . The first two terms follow by simple algebraic manipulation. The final term follows by algebra and periodicity, i.e., E z 0 = E z q E_{z_0}=E_{z_q} E z 0 = E z q for a valid set of PMR-QMC diagonal energies. After a PMR-QMC update, we have O ( 1 ) O(1) O ( 1 ) access to β \beta β , each E z j E_{z_j} E z j , and each successive divided difference e − β E z 0 , e − β [ E z 0 , E z 1 ] , … , e − β [ E z 0 , … , E z q ] e^{-\beta E_{z_0}},e^{-\beta[E_{z_0,E_{z_1}]} ,\ldots,e^{-\beta[E_{z_0,\ldots,E_{z_q}]}}} e − β E z 0 , e − β [ E z 0 , E z 1 ] , … , e − β [ E z 0 , … , E z q ] , which includes e − β [ E z 0 , … , E z q − 1 ] e^{-\beta[E_{z_0,\ldots,E_{z_{q-1}}]}} e − β [ E z 0 , … , E z q − 1 ] .
Fidelity susceptibility in quartic time
We shall now show
E z 0 e − β [ E z 0 , … , E z q ] ∑ j = 0 q E z j ∑ r = 0 j e − β 2 [ E z 0 , … , E z r ] ∑ m = j q e − β 2 [ E z r , … , E z q , E z j , E z m ] ≡ ∫ 0 β / 2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ , (69) \frac{E_{z_0}}{e^{-\beta[E_{z_0,\ldots,E_{z_q}]}}}\sum_{j=0}^{q}E_{z_j}\sum_{r=0}^{j}e^{-\frac{\beta}{2}[E_{z_0,\ldots,E_{z_r}]}\sum_{m=j}^{q}e^{-\frac{\beta}{2}[E_{z_r,\ldots,E_{z_q},E_{z_j},E_{z_m}]}\equiv\int_{0}^{\beta/2}\tau\langle D_0(\tau)D_0\rangle d\tau,}} \tag*{(69)} e − β [ E z 0 , … , E z q ] E z 0 j = 0 ∑ q E z j r = 0 ∑ j e − 2 β [ E z 0 , … , E z r ] ∑ m = j q e − 2 β [ E z r , … , E z q , E z j , E z m ] ≡ ∫ 0 β /2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ , (69)
which gives rise to an O ( q 4 ) O(q^4) O ( q 4 ) estimator (see Section A4) for χ F D 0 \chi_F^{D_0} χ F D 0 in Eq. (50) when combined with Eq. (51) . As with the ES, this essentially reduces to proving divided difference relations since we need only integrate the expression in Eq. (53) . To this end, we first state and prove a helpful proposition.
Proposition 3 (Repeated argument sum simplification [59 ] ).
∑ j = 0 q e − τ [ x 0 , … , x q , x j ] = − τ e − τ [ x 0 , … , x q ] (70) \sum_{j=0}^{q}e^{-\tau[x_0,\ldots,x_q,x_j]}=-\tau e^{-\tau[x_0,\ldots,x_q]} \tag*{(70)} j = 0 ∑ q e − τ [ x 0 , … , x q , x j ] = − τ e − τ [ x 0 , … , x q ] (70) Proof. Denote f ( τ ) ≡ e − τ [ x 0 , … , x q ] f(\tau)\equiv e^{-\tau[x_0,\ldots,x_q]} f ( τ ) ≡ e − τ [ x 0 , … , x q ] and recall L { e − τ [ x 0 , … , x q ] } = ( − 1 ) q / ( ∏ i = 0 q ( s + x i ) ) \mathcal{L}\{e^{-\tau[x_0,\ldots,x_q]}\}=(-1)^q/\left(\prod_{i=0}^{q}(s+x_i)\right) L { e − τ [ x 0 , … , x q ] } = ( − 1 ) q / ( ∏ i = 0 q ( s + x i ) ) . By the derivative property of the Laplace transform,
L { − τ f ( τ ) } = ∂ ∂ s L { f ( τ ) } = ∑ j = 0 q ( − 1 ) q + 1 ( s + x j ) ∏ i = 0 q ( s + x i ) = L { ∑ j = 0 q e − τ [ x 0 , … , x q , x j ] } , (71) \mathcal{L}\{-\tau f(\tau)\}=\frac{\partial}{\partial s}\mathcal{L}\{f(\tau)\}=\sum_{j=0}^{q}\frac{(-1)^{q+1}}{(s+x_j)\prod_{i=0}^{q}(s+x_i)}=\mathcal{L}\left\{\sum_{j=0}^{q}e^{-\tau[x_0,\ldots,x_q,x_j]}\right\}, \tag*{(71)} L { − τ f ( τ )} = ∂ s ∂ L { f ( τ )} = j = 0 ∑ q ( s + x j ) ∏ i = 0 q ( s + x i ) ( − 1 ) q + 1 = L { j = 0 ∑ q e − τ [ x 0 , … , x q , x j ] } , (71) and the result follows by taking the inverse Laplace transform of the left-most and right-most expressions.
Using this proposition and results we have shown previously, we can now prove the following integral relation.
Lemma 3 (Fidelity susceptibility integral).
I ≡ ∫ 0 β / 2 τ e − τ [ x j + 1 , … , x q ] e − ( β − τ ) [ x 0 , … , x j ] d τ = ∑ r = 0 j e β 2 [ x 0 , … , x r ] ∑ m = j + 1 q e β 2 [ x r , … , x q , x m ] , (72) I\equiv\int_{0}^{\beta/2}\tau e^{-\tau[x_{j+1},\ldots,x_q]}e^{-(\beta-\tau)[x_0,\ldots,x_j]}d\tau=\sum_{r=0}^{j}e^{\frac{\beta}{2}[x_0,\ldots,x_r]}\sum_{m=j+1}^{q}e^{\frac{\beta}{2}[x_r,\ldots,x_q,x_m]}, \tag*{(72)} I ≡ ∫ 0 β /2 τ e − τ [ x j + 1 , … , x q ] e − ( β − τ ) [ x 0 , … , x j ] d τ = r = 0 ∑ j e 2 β [ x 0 , … , x r ] m = j + 1 ∑ q e 2 β [ x r , … , x q , x m ] , (72) Proof. This relation follows from the Leibniz rule (Eq. (41) ), Proposition 3, and Eq. (55) applied in order,
I = ∑ r = 0 j e − ( β / 2 − τ ) [ x 0 , … , x r ] ∫ 0 β / 2 τ e − τ [ x j + 1 , … , x q ] e − ( β / 2 − τ ) [ x r , … , x j ] d τ (73) I=\sum_{r=0}^{j}e^{-(\beta/2-\tau)[x_0,\ldots,x_r]}\int_{0}^{\beta/2}\tau e^{-\tau[x_{j+1},\ldots,x_q]}e^{-(\beta/2-\tau)[x_r,\ldots,x_j]}d\tau \tag*{(73)} I = r = 0 ∑ j e − ( β /2 − τ ) [ x 0 , … , x r ] ∫ 0 β /2 τ e − τ [ x j + 1 , … , x q ] e − ( β /2 − τ ) [ x r , … , x j ] d τ (73) = ∑ r = 0 j ∑ m = j + 1 q e − ( β / 2 − τ ) [ x 0 , … , x r ] ∫ 0 β / 2 e − τ [ x j + 1 , … , x q , x m ] e − ( β / 2 − τ ) [ x r , … , x j ] d τ (74) =\sum_{r=0}^{j}\sum_{m=j+1}^{q}e^{-(\beta/2-\tau)[x_0,\ldots,x_r]}\int_{0}^{\beta/2}e^{-\tau[x_{j+1},\ldots,x_q,x_m]}e^{-(\beta/2-\tau)[x_r,\ldots,x_j]}d\tau \tag*{(74)} = r = 0 ∑ j m = j + 1 ∑ q e − ( β /2 − τ ) [ x 0 , … , x r ] ∫ 0 β /2 e − τ [ x j + 1 , … , x q , x m ] e − ( β /2 − τ ) [ x r , … , x j ] d τ (74) = ∑ r = 0 j e − ( β / 2 − τ ) [ x 0 , … , x r ] ∑ m = j + 1 q e − β 2 [ x r , … , x q , x m ] , (75) =\sum_{r=0}^{j}e^{-(\beta/2-\tau)[x_0,\ldots,x_r]}\sum_{m=j+1}^{q}e^{-\frac{\beta}{2}[x_r,\ldots,x_q,x_m]}, \tag*{(75)} = r = 0 ∑ j e − ( β /2 − τ ) [ x 0 , … , x r ] m = j + 1 ∑ q e − 2 β [ x r , … , x q , x m ] , (75) where in the final line we use β → β / 2 \beta\to\beta/2 β → β /2 when employing Eq. (55) .
This lemma is already sufficient to demonstrate Eq. (69) , but to make things clearer, we state the following corollary first.
Corollary 2. Lemma 3 is general for any multiset [ x 0 , … , x q ] [x_0,\ldots,x_q] [ x 0 , … , x q ] partitioned at arbitrary index j j j . As a specific special case of interest now, we consider [ x j + 1 , … , x q ] [x_{j+1},\ldots,x_q] [ x j + 1 , … , x q ] replaced with [ x j , … , x q ] [x_j,\ldots,x_q] [ x j , … , x q ] ,
I ′ ≡ ∫ 0 β / 2 τ e − τ [ x j , … , x q ] e − ( β − τ ) [ x 0 , … , x j ] d τ = ∑ r = 0 j e − β 2 [ x 0 , … , x r ] ∑ m = j q e − β 2 [ x r , … , x q , x j , x m ] . (76) I'\equiv\int_{0}^{\beta/2}\tau e^{-\tau[x_j,\ldots,x_q]}e^{-(\beta-\tau)[x_0,\ldots,x_j]}d\tau=\sum_{r=0}^{j}e^{-\frac{\beta}{2}[x_0,\ldots,x_r]}\sum_{m=j}^{q}e^{-\frac{\beta}{2}[x_r,\ldots,x_q,x_j,x_m]}. \tag*{(76)} I ′ ≡ ∫ 0 β /2 τ e − τ [ x j , … , x q ] e − ( β − τ ) [ x 0 , … , x j ] d τ = r = 0 ∑ j e − 2 β [ x 0 , … , x r ] m = j ∑ q e − 2 β [ x r , … , x q , x j , x m ] . (76)
Proof. This result follows from Lemma 3 with the main change being that the m m m index now starts at j j j instead of j + 1 j+1 j + 1 . To explain the notation change, it is useful to simply repeat the above derivation, which proceeds as,
I ′ = ∑ r = 0 j e − ( β / 2 − τ ) [ x 0 , … , x r ] ∫ 0 β / 2 τ e − τ [ x j , … , x q ] e − ( β / 2 − τ ) [ x r , … , x j ] d τ (77) I'=\sum_{r=0}^{j}e^{-(\beta/2-\tau)[x_0,\ldots,x_r]}\int_{0}^{\beta/2}\tau e^{-\tau[x_j,\ldots,x_q]}e^{-(\beta/2-\tau)[x_r,\ldots,x_j]}\,\mathrm{d}\tau \tag*{(77)} I ′ = r = 0 ∑ j e − ( β /2 − τ ) [ x 0 , … , x r ] ∫ 0 β /2 τ e − τ [ x j , … , x q ] e − ( β /2 − τ ) [ x r , … , x j ] d τ (77)
= ∑ r = 0 j ∑ m = j q e − ( β / 2 − τ ) [ x 0 , … , x r ] ∫ 0 β / 2 e − τ [ x j , … , x q , x m ] e − ( β / 2 − τ ) [ x r , … , x j ] d τ (78) =\sum_{r=0}^{j}\sum_{m=j}^{q}e^{-(\beta/2-\tau)[x_0,\ldots,x_r]}\int_{0}^{\beta/2}e^{-\tau[x_j,\ldots,x_q,x_m]}e^{-(\beta/2-\tau)[x_r,\ldots,x_j]}\,\mathrm{d}\tau \tag*{(78)} = r = 0 ∑ j m = j ∑ q e − ( β /2 − τ ) [ x 0 , … , x r ] ∫ 0 β /2 e − τ [ x j , … , x q , x m ] e − ( β /2 − τ ) [ x r , … , x j ] d τ (78)
= ∑ r = 0 j e − ( β / 2 − τ ) [ x 0 , … , x r ] ∑ m = j + 1 q e − β 2 [ x r , … , x q , x j , x m ] , (79) =\sum_{r=0}^{j}e^{-(\beta/2-\tau)[x_0,\ldots,x_r]}\sum_{m=j+1}^{q}e^{-\frac{\beta}{2}[x_r,\ldots,x_q,x_j,x_m]}, \tag*{(79)} = r = 0 ∑ j e − ( β /2 − τ ) [ x 0 , … , x r ] m = j + 1 ∑ q e − 2 β [ x r , … , x q , x j , x m ] , (79)
where the last multiset now contains an explicit extra x j x_j x j from the concatenation of [ x j , … , x q , x m ] [x_j,\ldots,x_q,x_m] [ x j , … , x q , x m ] and [ x r , … , x j ] [x_r,\ldots,x_j] [ x r , … , x j ] which both contain an explicit x j x_j x j .
Inspection of Eqs. (53) and (76) shows the validity of Eq. (69) immediately.
Fidelity susceptibility in cubic time
The FS estimator in Eq. (69) can be evaluated in O ( q 4 ) O(q^4) O ( q 4 ) operations, but we can improve it to O ( q 3 ) O(q^3) O ( q 3 ) and validate Theorem 2 in a few steps. We begin with a some helpful propositions and lemmas, where the first step is to re-order the sum.
Proposition 4 (Re-ordering sums in FS estimator).
E z 0 e − β [ E z 0 , … , E z q ] ∑ r = 0 q e − β 2 [ E z 0 , … , E z r ] ∑ j , m = r j ≤ m q E z j e − β 2 [ E z r , … , E z q , E z j , E z m ] ≃ ∫ 0 β / 2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ (80) \frac{E_{z_0}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{r=0}^{q}e^{-\frac{\beta}{2}[E_{z_0},\ldots,E_{z_r}]}\sum_{\substack{j,m=r\\j\le m}}^{q}E_{z_j}e^{-\frac{\beta}{2}[E_{z_r,\ldots,E_{z_q},E_{z_j},E_{z_m}]}}\simeq\int_{0}^{\beta/2}\tau\langle D_0(\tau)D_0\rangle\,\mathrm{d}\tau \tag*{(80)} e − β [ E z 0 , … , E z q ] E z 0 r = 0 ∑ q e − 2 β [ E z 0 , … , E z r ] j , m = r j ≤ m ∑ q E z j e − 2 β [ E z r , … , E z q , E z j , E z m ] ≃ ∫ 0 β /2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ (80)
With the re-ordering, we now observe that the innermost sum can be simplified.
Lemma 4 (A weighted, repeated argument, double, less-than sum simplification [59 ] ).
∑ i , j = 0 i ≤ j q x i e − τ [ x 0 , … , x q , x i , x j ] = ( − τ 2 2 ∂ ∂ τ − ∑ i = 0 q i ⋅ ∂ ∂ x i ) e − τ [ x 0 , … , x q ] . (81) \sum_{\substack{i,j=0\\i\le j}}^{q}x_i e^{-\tau[x_0,\ldots,x_q,x_i,x_j]}=\left(-\frac{\tau^2}{2}\frac{\partial}{\partial\tau}-\sum_{i=0}^{q}i\cdot\frac{\partial}{\partial x_i}\right)e^{-\tau[x_0,\ldots,x_q]}. \tag*{(81)} i , j = 0 i ≤ j ∑ q x i e − τ [ x 0 , … , x q , x i , x j ] = ( − 2 τ 2 ∂ τ ∂ − i = 0 ∑ q i ⋅ ∂ x i ∂ ) e − τ [ x 0 , … , x q ] . (81)
Proof. We prove this by induction.
Base case. When q = 0 q=0 q = 0 , we have
x 0 e − τ [ x 0 , x 0 , x 0 ] = x 0 ⋅ 1 2 ∂ 2 ∂ x 0 2 e − τ x 0 = τ 2 x 0 2 e − τ x 0 = − τ 2 2 ∂ ∂ τ e − τ x 0 , x_0e^{-\tau[x_0,x_0,x_0]}=x_0\cdot\frac{1}{2}\frac{\partial^2}{\partial x_0^2}e^{-\tau x_0}=\frac{\tau^2x_0}{2}e^{-\tau x_0}=-\frac{\tau^2}{2}\frac{\partial}{\partial\tau}e^{-\tau x_0}, x 0 e − τ [ x 0 , x 0 , x 0 ] = x 0 ⋅ 2 1 ∂ x 0 2 ∂ 2 e − τ x 0 = 2 τ 2 x 0 e − τ x 0 = − 2 τ 2 ∂ τ ∂ e − τ x 0 ,
so Eq. (81) holds.
Induction step. It follows from the recursive definition of the divided differences that
∑ i , j = 0 i ≤ j q + 1 x i e − τ [ x 0 , … , x q + 1 , x i , x j ] = 1 x 0 − x 1 ∑ i , j = 0 i ≤ j q + 1 x j ( e − τ [ x 0 , x 2 , … , x q + 1 , x i , x j ] − e − τ [ x 1 , x 2 , … , x q + 1 , x i , x j ] ) = 1 x 0 − x 1 ( ( ( − τ 2 2 ∂ ∂ τ − ∑ i = 1 q i ⋅ ∂ ∂ x i + 1 ) e − τ [ x 0 , x 2 , … , x q + 1 ] + x 0 e − τ [ x 0 , x 2 , … , x q + 1 , x 0 , x 1 ] + x 1 ∑ j = 1 q + 1 e − τ [ x 0 , … , x q + 1 , x j ] ) − ( ( − τ 2 2 ∂ ∂ τ − ∑ i = 1 q i ⋅ ∂ ∂ x i + 1 ) e − τ [ x 1 , x 2 , … , x q + 1 ] + x 0 ∑ j = 0 q + 1 e − τ [ x 0 , x 1 , … , x q + 1 , x j ] ) ) = ( − τ 2 2 ∂ ∂ τ − ∑ i = 0 q i ⋅ ∂ ∂ x i + 1 ) e − τ [ x 0 , … , x q + 1 ] − ∑ j = 1 q + 1 e − τ [ x 0 , … , x q + 1 , x j ] = ( − τ 2 2 ∂ ∂ τ − ∑ i = 0 q + 1 i ⋅ ∂ ∂ x i ) e − τ [ x 0 , … , x q + 1 ] . (82) \begin{aligned}
\sum_{\substack{i,j=0\\i\le j}}^{q+1}x_i e^{-\tau[x_0,\ldots,x_{q+1},x_i,x_j]}&=\frac{1}{x_0-x_1}\sum_{\substack{i,j=0\\i\le j}}^{q+1}x_j\left(e^{-\tau[x_0,x_2,\ldots,x_{q+1},x_i,x_j]}-e^{-\tau[x_1,x_2,\ldots,x_{q+1},x_i,x_j]}\right)\\
&=\frac{1}{x_0-x_1}\left(\left(\left(-\frac{\tau^2}{2}\frac{\partial}{\partial\tau}-\sum_{i=1}^{q}i\cdot\frac{\partial}{\partial x_{i+1}}\right)e^{-\tau[x_0,x_2,\ldots,x_{q+1}]}+x_0e^{-\tau[x_0,x_2,\ldots,x_{q+1},x_0,x_1]}+x_1\sum_{j=1}^{q+1}e^{-\tau[x_0,\ldots,x_{q+1},x_j]}\right)\right.\\
&\qquad\left.-\left(\left(-\frac{\tau^2}{2}\frac{\partial}{\partial\tau}-\sum_{i=1}^{q}i\cdot\frac{\partial}{\partial x_{i+1}}\right)e^{-\tau[x_1,x_2,\ldots,x_{q+1}]}+x_0\sum_{j=0}^{q+1}e^{-\tau[x_0,x_1,\ldots,x_{q+1},x_j]}\right)\right)\\
&=\left(-\frac{\tau^2}{2}\frac{\partial}{\partial\tau}-\sum_{i=0}^{q}i\cdot\frac{\partial}{\partial x_{i+1}}\right)e^{-\tau[x_0,\ldots,x_{q+1}]}-\sum_{j=1}^{q+1}e^{-\tau[x_0,\ldots,x_{q+1},x_j]}\\
&=\left(-\frac{\tau^2}{2}\frac{\partial}{\partial\tau}-\sum_{i=0}^{q+1}i\cdot\frac{\partial}{\partial x_i}\right)e^{-\tau[x_0,\ldots,x_{q+1}]}. \tag*{(82)}
\end{aligned} i , j = 0 i ≤ j ∑ q + 1 x i e − τ [ x 0 , … , x q + 1 , x i , x j ] = x 0 − x 1 1 i , j = 0 i ≤ j ∑ q + 1 x j ( e − τ [ x 0 , x 2 , … , x q + 1 , x i , x j ] − e − τ [ x 1 , x 2 , … , x q + 1 , x i , x j ] ) = x 0 − x 1 1 ( ( ( − 2 τ 2 ∂ τ ∂ − i = 1 ∑ q i ⋅ ∂ x i + 1 ∂ ) e − τ [ x 0 , x 2 , … , x q + 1 ] + x 0 e − τ [ x 0 , x 2 , … , x q + 1 , x 0 , x 1 ] + x 1 j = 1 ∑ q + 1 e − τ [ x 0 , … , x q + 1 , x j ] ) − ( ( − 2 τ 2 ∂ τ ∂ − i = 1 ∑ q i ⋅ ∂ x i + 1 ∂ ) e − τ [ x 1 , x 2 , … , x q + 1 ] + x 0 j = 0 ∑ q + 1 e − τ [ x 0 , x 1 , … , x q + 1 , x j ] ) ) = ( − 2 τ 2 ∂ τ ∂ − i = 0 ∑ q i ⋅ ∂ x i + 1 ∂ ) e − τ [ x 0 , … , x q + 1 ] − j = 1 ∑ q + 1 e − τ [ x 0 , … , x q + 1 , x j ] = ( − 2 τ 2 ∂ τ ∂ − i = 0 ∑ q + 1 i ⋅ ∂ x i ∂ ) e − τ [ x 0 , … , x q + 1 ] . (82)
Therefore, Eq. (81) is true for all q q q .
As with the ES simplification, this more compact expression involving a derivative can be converted into a valid PMR-QMC estimator using Proposition 2.
Corollary 3 (Computing the complicated weighted, repeated argument, double, less-than sum [59 ] ).
∑ i , j = 0 i ≤ j q x i e − τ [ x 0 , … , x q , x i , x j ] = { ( τ 2 x 0 2 ) e − τ [ x 0 , … , x q ] + ( τ 2 2 ) e − τ [ x 1 , … , x q ] − ∑ i = 1 q i ⋅ e − τ [ x 0 , … , x q , x i ] , for q > 0 , ( τ 2 x 0 2 ) e − τ x 0 , for q = 0. (83) \sum_{\substack{i,j=0\\i\le j}}^{q}x_i e^{-\tau[x_0,\ldots,x_q,x_i,x_j]}=
\begin{cases}
\left(\frac{\tau^2x_0}{2}\right)e^{-\tau[x_0,\ldots,x_q]}+\left(\frac{\tau^2}{2}\right)e^{-\tau[x_1,\ldots,x_q]}-\sum_{i=1}^{q}i\cdot e^{-\tau[x_0,\ldots,x_q,x_i]}, & \text{for }q>0,\\
\left(\frac{\tau^2x_0}{2}\right)e^{-\tau x_0}, & \text{for }q=0.
\end{cases} \tag*{(83)} i , j = 0 i ≤ j ∑ q x i e − τ [ x 0 , … , x q , x i , x j ] = ⎩ ⎨ ⎧ ( 2 τ 2 x 0 ) e − τ [ x 0 , … , x q ] + ( 2 τ 2 ) e − τ [ x 1 , … , x q ] − ∑ i = 1 q i ⋅ e − τ [ x 0 , … , x q , x i ] , ( 2 τ 2 x 0 ) e − τ x 0 , for q > 0 , for q = 0. (83)
Proof. This simplification follows from applying Prop. 2 to Eq. (81) .
We now prove the main part of Theorem 2—that we have an O ( q 3 ) O(q^3) O ( q 3 ) estimator for FS—since
1 q = 0 ( β E z 0 ) 2 8 + 1 q > 0 E z 0 e − β [ E z 0 , … , E z q ] ∑ r = 0 q e − β 2 [ E z 0 , … , E z r ] ( β 2 8 E z r e − β 2 [ E z r , … , E z q ] + β 2 8 e − β 2 [ E z r + 1 , … , E z q ] − ∑ i = r + 1 q ( i − r ) e − β 2 [ E z r , … , E z q , E z i ] ) = ^ ∫ 0 β / 2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ (84) \mathbf{1}_{q=0}\frac{(\beta E_{z_0})^2}{8}+\mathbf{1}_{q>0}\frac{E_{z_0}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{r=0}^{q}e^{-\frac{\beta}{2}[E_{z_0},\ldots,E_{z_r}]}\left(\frac{\beta^2}{8}E_{z_r}e^{-\frac{\beta}{2}[E_{z_r},\ldots,E_{z_q}]}+\frac{\beta^2}{8}e^{-\frac{\beta}{2}[E_{z_{r+1}},\ldots,E_{z_q}]}-\sum_{i=r+1}^{q}(i-r)e^{-\frac{\beta}{2}[E_{z_r},\ldots,E_{z_q},E_{z_i}]}\right)\ \widehat{=}\ \int_{0}^{\beta/2}\tau\langle D_0(\tau)D_0\rangle d\tau \tag*{(84)} 1 q = 0 8 ( β E z 0 ) 2 + 1 q > 0 e − β [ E z 0 , … , E z q ] E z 0 r = 0 ∑ q e − 2 β [ E z 0 , … , E z r ] ( 8 β 2 E z r e − 2 β [ E z r , … , E z q ] + 8 β 2 e − 2 β [ E z r + 1 , … , E z q ] − i = r + 1 ∑ q ( i − r ) e − 2 β [ E z r , … , E z q , E z i ] ) = ∫ 0 β /2 τ ⟨ D 0 ( τ ) D 0 ⟩ d τ (84)
Proof. The estimator follows from applying Eq. (83) to the estimator form given in Eq. (80) , taking special care to correctly translate the sum from i , j = 0 i,j=0 i , j = 0 to q q q on arguments [ x 0 , … , x q ] [x_0,\ldots,x_q] [ x 0 , … , x q ] to the sum of j , m = r j,m=r j , m = r to q q q on arguments [ E z r , … , E z q ] [E_{z_r},\ldots,E_{z_q}] [ E z r , … , E z q ] . The estimate O ( q 3 ) O(q^3) O ( q 3 ) comes from the observation that, for each r r r , we must do O ( q 2 ) O(q^2) O ( q 2 ) work.
Off-diagonal case follows from diagonal case
We now consider the case H 1 ∝ H − D 0 H_1\propto H-D_0 H 1 ∝ H − D 0 and show it reduces to using the H 1 ∝ D 0 H_1\propto D_0 H 1 ∝ D 0 estimators. Let
Γ ≡ H − D 0 , (85) \Gamma\equiv H-D_0, \tag*{(85)} Γ ≡ H − D 0 , (85)
and define the associated ES and FS
χ E Γ ( λ ; β ) = ∫ 0 β ( ⟨ Γ ( τ ) Γ ⟩ − ⟨ Γ ⟩ 2 ) d τ (86) \chi_E^\Gamma(\lambda;\beta)=\int_0^\beta\left(\langle\Gamma(\tau)\Gamma\rangle-\langle\Gamma\rangle^2\right)d\tau \tag*{(86)} χ E Γ ( λ ; β ) = ∫ 0 β ( ⟨ Γ ( τ ) Γ ⟩ − ⟨ Γ ⟩ 2 ) d τ (86)
χ F Γ ( λ ; β ) = ∫ 0 β / 2 τ ( ⟨ Γ ( τ ) Γ ⟩ − ⟨ Γ ⟩ 2 ) d τ . (87) \chi_F^\Gamma(\lambda;\beta)=\int_0^{\beta/2}\tau\left(\langle\Gamma(\tau)\Gamma\rangle-\langle\Gamma\rangle^2\right)d\tau. \tag*{(87)} χ F Γ ( λ ; β ) = ∫ 0 β /2 τ ( ⟨ Γ ( τ ) Γ ⟩ − ⟨ Γ ⟩ 2 ) d τ . (87)
As with the diagonal case, we find χ E H 1 ∝ χ E Γ \chi_{E}^{H_1} \propto\chi_{E}^{\Gamma} χ E H 1 ∝ χ E Γ and χ F H 1 ∝ χ F Γ \chi_{F}^{H_1} \propto\chi_{F}^{\Gamma} χ F H 1 ∝ χ F Γ . Since H = D 0 + ∑ j > 0 D j P j H = D_0 + \sum_{j>0} D_jP_j H = D 0 + ∑ j > 0 D j P j , then it follows that Γ = ∑ j > 0 D j P j \Gamma= \sum_{j>0} D_jP_j Γ = ∑ j > 0 D j P j . One approach to estimate the ES and FS in this case is to derive estimators for ⟨ D j P j ⟩ \langle D_jP_j\rangle ⟨ D j P j ⟩ and ⟨ ( D l P l ) ( τ ) D j P j ⟩ \langle(D_lP_l)(\tau)D_jP_j\rangle ⟨( D l P l ) ( τ ) D j P j ⟩ and use linearity. While this does work, if Γ \Gamma Γ contains R R R terms, then it incurs an overhead of doing R R R and R 2 R^2 R 2 estimations. This overhead can be avoided by using simple estimators for H H H and D 0 D_0 D 0 quantities and linearity.
Firstly, ⟨ Γ ⟩ = ⟨ H − D 0 ⟩ = ⟨ H ⟩ − ⟨ D 0 ⟩ \langle\Gamma\rangle= \langle H-D_0\rangle= \langle H\rangle- \langle D_0\rangle ⟨ Γ ⟩ = ⟨ H − D 0 ⟩ = ⟨ H ⟩ − ⟨ D 0 ⟩ by linearity. From prior work (see Sec. VI.B in Ref. [26]), we know
E z q + 1 q ≥ 1 e − β [ E z 0 , … , E z q − 1 ] e − β [ E z 0 , … , E z q ] = { E z q q = 0 E z q + e − β [ E z 0 , … , E z q − 1 ] e − β [ E z 0 , … , E z q ] q > 0 , ≐ ⟨ H ⟩ (88) E_{z_q} + 1_{q\geq1}\frac{e^{-\beta[E_{z_0},\ldots,E_{z_{q-1}}]}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}} =
\begin{cases}
E_{z_q} & q=0 \\
E_{z_q}+\dfrac{e^{-\beta[E_{z_0},\ldots,E_{z_{q-1}}]}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}} & q>0,
\end{cases}
\doteq\langle H\rangle \tag*{(88)} E z q + 1 q ≥ 1 e − β [ E z 0 , … , E z q ] e − β [ E z 0 , … , E z q − 1 ] = ⎩ ⎨ ⎧ E z q E z q + e − β [ E z 0 , … , E z q ] e − β [ E z 0 , … , E z q − 1 ] q = 0 q > 0 , ≐ ⟨ H ⟩ (88)
where 1 q ≥ 1 1_{q\geq1} 1 q ≥ 1 is the indicator function that is 0 when q < 1 q<1 q < 1 and 1 when q ≥ 1 q\geq1 q ≥ 1 . Since E z ≐ ⟨ D 0 ⟩ E_z \doteq\langle D_0\rangle E z ≐ ⟨ D 0 ⟩ , then by linearity we find,
1 q ≥ 1 e − β [ E z 0 , … , E z q − 1 ] e − β [ E z 0 , … , E z q ] ≐ ⟨ Γ ⟩ . (89) 1_{q\geq1}\frac{e^{-\beta[E_{z_0},\ldots,E_{z_{q-1}}]}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}} \doteq\langle\Gamma\rangle. \tag*{(89)} 1 q ≥ 1 e − β [ E z 0 , … , E z q ] e − β [ E z 0 , … , E z q − 1 ] ≐ ⟨ Γ ⟩ . (89)
This estimator can be used to estimate ⟨ Γ ⟩ \langle\Gamma\rangle ⟨ Γ ⟩ .
Next, we observe by linearity and cyclicity of the trace,
⟨ Γ ( τ ) Γ ⟩ = ⟨ H 2 ⟩ + ⟨ D 0 ( τ ) D 0 ⟩ − 2 ⟨ D 0 H ⟩ , (90) \langle\Gamma(\tau)\Gamma\rangle= \langle H^2\rangle+ \langle D_0(\tau)D_0\rangle- 2\langle D_0H\rangle, \tag*{(90)} ⟨ Γ ( τ ) Γ ⟩ = ⟨ H 2 ⟩ + ⟨ D 0 ( τ ) D 0 ⟩ − 2 ⟨ D 0 H ⟩ , (90)
which has the full non-trivial τ \tau τ dependence in the familiar diagonal correlator. As such, we can estimate ⟨ Γ ( τ ) Γ ⟩ \langle\Gamma(\tau)\Gamma\rangle ⟨ Γ ( τ ) Γ ⟩ and ES and FS integrals thereof provided we can derive estimators for ⟨ H 2 ⟩ \langle H^2\rangle ⟨ H 2 ⟩ and ⟨ D 0 H ⟩ \langle D_0H\rangle ⟨ D 0 H ⟩ . By off-diagonal expansion manipulations, we know (e.g., Sec. VI.B of Ref. [26]),
E z q 2 + 1 q ≥ 1 ( E z q + E z q − 1 ) e − β [ E z 0 , … , E z q − 1 ] + 1 q ≥ 2 e − β [ E z 0 , … , E z q − 2 ] e − β [ E z 0 , … , E z q ] ≐ ⟨ H 2 ⟩ (91) E_{z_q}^2 + \frac{1_{q\geq1}(E_{z_q}+E_{z_{q-1}})e^{-\beta[E_{z_0},\ldots,E_{z_{q-1}}]} + 1_{q\geq2}e^{-\beta[E_{z_0},\ldots,E_{z_{q-2}}]}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}} \doteq\langle H^2\rangle \tag*{(91)} E z q 2 + e − β [ E z 0 , … , E z q ] 1 q ≥ 1 ( E z q + E z q − 1 ) e − β [ E z 0 , … , E z q − 1 ] + 1 q ≥ 2 e − β [ E z 0 , … , E z q − 2 ] ≐ ⟨ H 2 ⟩ (91)
and (see Sec. VI.C in Ref. [26]),
E z 0 ( E z 0 + 1 q ≥ 1 e − β [ E z 1 , … , E z q ] e − β [ E z 0 , … , E z q ] ) ≐ ⟨ D 0 H ⟩ . (92) E_{z_0}\left(E_{z_0}+1_{q\geq1}\frac{e^{-\beta[E_{z_1},\ldots,E_{z_q}]}}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\right) \doteq\langle D_0H\rangle. \tag*{(92)} E z 0 ( E z 0 + 1 q ≥ 1 e − β [ E z 0 , … , E z q ] e − β [ E z 1 , … , E z q ] ) ≐ ⟨ D 0 H ⟩ . (92)
Each of the static estimators, i.e., for ⟨ D 0 ⟩ \langle D_0\rangle ⟨ D 0 ⟩ , ⟨ H ⟩ \langle H\rangle ⟨ H ⟩ , ⟨ H 2 ⟩ \langle H^2\rangle ⟨ H 2 ⟩ , and ⟨ D 0 H ⟩ \langle D_0H\rangle ⟨ D 0 H ⟩ , can be computed in constant time O ( 1 ) O(1) O ( 1 ) . Integrals of these τ \tau τ -independent quantities are also trivial. Hence, the entire complexity in evaluating ⟨ Γ ( τ ) Γ ⟩ \langle\Gamma(\tau)\Gamma\rangle ⟨ Γ ( τ ) Γ ⟩ is O ( q 2 ) O(q^2) O ( q 2 ) inherited from the complexity of computing ⟨ D 0 ( τ ) D 0 ⟩ \langle D_0(\tau)D_0\rangle ⟨ D 0 ( τ ) D 0 ⟩ . Similarly, the complexity of evaluating ES and FS is thus O ( 1 ) O(1) O ( 1 ) and O ( q 3 ) O(q^3) O ( q 3 ) via the estimators we derived in Section E. Namely, we have now finished our proof of Theorems 1 and 2 by showing that the non-trivial parts of the ES and FS estimators for both the H 1 ∝ D 0 H_1 \propto D_0 H 1 ∝ D 0 and H 1 ∝ H − D 0 H_1 \propto H-D_0 H 1 ∝ H − D 0 are the same and hence have the same complexity.
Most general driving term estimators
In the most general case, H 1 H_1 H 1 contains both diagonal and off-diagonal terms and does not satisfy H 1 ∝ D 0 H_1 \propto D_0 H 1 ∝ D 0 or H 1 ∝ H − D 0 H_1 \propto H-D_0 H 1 ∝ H − D 0 . Nevertheless, we can characterize the general form of H 1 H_1 H 1 for arbitrary Hamiltonians and use that to derive estimators for ES and FS in this arbitrary case.
In the study of quantum phase transitions, we assume H ( λ ) = H 0 + λ H 1 H(\lambda)=H_0+\lambda H_1 H ( λ ) = H 0 + λ H 1 for some [ H 0 , H 1 ] ≠ 0 [H_0,H_1]\ne0 [ H 0 , H 1 ] = 0 . Regardless of the specifics, this Hamiltonian can always be in PMR form, H ( λ ) = ∑ j D j ( λ ) P j H(\lambda)=\sum_j D_j(\lambda)P_j H ( λ ) = ∑ j D j ( λ ) P j , where we choose P 0 = 1 P_0=1 P 0 = 1 by convention. Here, we show that one can always write
H 1 = ∑ j Λ j ( λ ) D j ( λ ) P j (93) H_1 = \sum_j \Lambda_j(\lambda)D_j(\lambda)P_j \tag*{(93)} H 1 = j ∑ Λ j ( λ ) D j ( λ ) P j (93)
where Λ j ( λ ) \Lambda_j(\lambda) Λ j ( λ ) are diagonal matrices and the D j ( λ ) P j D_j(\lambda)P_j D j ( λ ) P j terms are directly taken from the PMR form of H H H . The consequence of this form is that there are no fundamental obstacles to estimating ⟨ H 1 ⟩ \langle H_1\rangle ⟨ H 1 ⟩ , ⟨ H 1 ( τ ) H 1 ⟩ \langle H_1(\tau)H_1\rangle ⟨ H 1 ( τ ) H 1 ⟩ , and integrals thereof using PMR-QMC, and in fact, estimators have a relatively simple form. A full understanding of why this is true is subtle and entrenched in PMR-QMC details, and hence, out of the scope of this work. For additional context, we point to Section V.B in Ref. [23 ] and Ref. [26], which discuss measurements of arbitrary operators O O O and what properties O O O can have in relation to H H H that prevent accurate estimation by a single PMR-QMC simulation. To reiterate our main point, proving Eq. (93) is one way to show that H 1 H_1 H 1 does not have any of these subtle problems that prevent estimation.
To begin with, we build up the PMR form of H ( λ ) H(\lambda) H ( λ ) by first writing PMR forms for H 0 H_0 H 0 and H 1 H_1 H 1 separately. For simplicity, denote P ∈ H 0 P \in H_0 P ∈ H 0 to mean there exists a term D P DP D P in the PMR expansion of H 0 H_0 H 0 where D ≠ 0 D \ne0 D = 0 . With this notation, we can write,
H 0 = ∑ P ∈ H 0 A P P , H 1 = ∑ P ∈ H 1 B P P ⟹ H ( λ ) = ∑ P ∈ H 0 , P ∈ H 1 ( A P + λ B P ) P + ∑ P ∈ H 0 , P ∉ H 1 A P P + ∑ P ∉ H 0 , P ∈ H 1 λ B P P . (94) H_0 = \sum_{P \in H_0} A_P P,\quad H_1 = \sum_{P \in H_1} B_P P \quad\Longrightarrow\quad H(\lambda) = \sum_{P \in H_0,P \in H_1} (A_P+\lambda B_P)P+\sum_{P \in H_0,P \notin H_1} A_P P+\sum_{P \notin H_0,P \in H_1} \lambda B_P P. \tag*{(94)} H 0 = P ∈ H 0 ∑ A P P , H 1 = P ∈ H 1 ∑ B P P ⟹ H ( λ ) = P ∈ H 0 , P ∈ H 1 ∑ ( A P + λ B P ) P + P ∈ H 0 , P ∈ / H 1 ∑ A P P + P ∈ / H 0 , P ∈ H 1 ∑ λ B P P . (94)
When compared with H ( λ ) = ∑ j D j ( λ ) P j H(\lambda) = \sum_j D_j(\lambda)P_j H ( λ ) = ∑ j D j ( λ ) P j , we can readily identify { P j } j = { P ∈ H 0 } ∪ { P ∈ H 1 } \{P_j\}_j = \{P \in H_0\} \cup\{P \in H_1\} { P j } j = { P ∈ H 0 } ∪ { P ∈ H 1 } and D j D_j D j as the diagonal in front of P j P_j P j , i.e., either A j A_j A j , λ B j \lambda B_j λ B j , or ( A j + λ B j ) (A_j+\lambda B_j) ( A j + λ B j ) . Before showing Eq. (93) generally, we remark that in the extremely common cases that H 1 H_1 H 1 is either purely diagonal or purely off-diagonal, things simplify and Eq. (93) is obvious. In the pure diagonal case, H 1 = 1 λ D 0 H_1 = \frac{1}{\lambda}D_0 H 1 = λ 1 D 0 , and in the pure off-diagonal case, H 1 = ∑ j > 0 1 λ D j H_1 = \sum_{j>0}\frac{1}{\lambda}D_j H 1 = ∑ j > 0 λ 1 D j .
Now for the general case, consider P ∈ H 0 P \in H_0 P ∈ H 0 , P ∉ H 1 P \notin H_1 P ∈ / H 1 where we have D j = A j D_j=A_j D j = A j and choose Λ j = 0 \Lambda_j=0 Λ j = 0 . For P ∉ H 0 P \notin H_0 P ∈ / H 0 , P ∈ H 1 P \in H_1 P ∈ H 1 , we have D j = B j D_j=B_j D j = B j and choose Λ j = 1 \Lambda_j=1 Λ j = 1 . Finally, for P ∈ H 0 P \in H_0 P ∈ H 0 , P ∈ H 1 P \in H_1 P ∈ H 1 , we have D j = ( A j + λ B j ) D_j=(A_j+\lambda B_j) D j = ( A j + λ B j ) and choose Λ j = ( A j + λ B j ) B j + \Lambda_j=(A_j+\lambda B_j)B_j^{+} Λ j = ( A j + λ B j ) B j + , where X + X^{+} X + denotes the pseudo-inverse of X X X , which prevents diving by zero. Before justifying the pseudo-inverse—which is more subtle than any discussion so far—we remark that this case is moot if H 1 H_1 H 1 is purely diagonal or purely off-diagonal, since such partitions have no P P P that is contained in both H 0 H_0 H 0 and in H 1 H_1 H 1 . To see why the pseudo-inverse works, suppose ⟨ z ∣ A j + λ B j ∣ z ⟩ = 0 \langle z|A_j+\lambda B_j|z\rangle=0 ⟨ z ∣ A j + λ B j ∣ z ⟩ = 0 which implies either ⟨ z ∣ A j ∣ z ⟩ = ⟨ z ∣ B j ∣ z ⟩ = 0 \langle z|A_j|z\rangle=\langle z|B_j|z\rangle=0 ⟨ z ∣ A j ∣ z ⟩ = ⟨ z ∣ B j ∣ z ⟩ = 0 or A j = − λ B j A_j=-\lambda B_j A j = − λ B j . In the first case, ⟨ z ∣ Λ j B j ∣ z ⟩ = 0 \langle z|\Lambda_jB_j|z\rangle=0 ⟨ z ∣ Λ j B j ∣ z ⟩ = 0 for any choice of Λ j \Lambda_j Λ j , so the pseudo-inverse works. The second-case is not relevant since it requires fine-tuning λ \lambda λ , and such exceptional points can be avoided in practice while still generating χ F P ( λ ) \chi_F^P(\lambda) χ F P ( λ ) curves.
Estimating ⟨ H 1 ⟩ \langle H_1\rangle ⟨ H 1 ⟩ and ⟨ H 1 ( τ ) H 1 ⟩ \langle H_1(\tau)H_1\rangle ⟨ H 1 ( τ ) H 1 ⟩
In the prior section, we showed that we can write H 1 = ∑ j Λ j D j P j H_1=\sum_j\Lambda_jD_jP_j H 1 = ∑ j Λ j D j P j for Λ j \Lambda_j Λ j ’s diagonal matrices whenever H = ∑ j D j P j H=\sum_jD_jP_j H = ∑ j D j P j and P 0 = 1 P_0=\mathbb{1} P 0 = 1 . By linearity, it is sufficient to derive estimators for each ⟨ Λ j D j P j ⟩ \langle\Lambda_jD_jP_j\rangle ⟨ Λ j D j P j ⟩ term, for which it is useful to separate diagonal term, Λ 0 \Lambda_0 Λ 0 from the general off-diagonal terms Λ l D l P l \Lambda_lD_lP_l Λ l D l P l for l > 0 l>0 l > 0 . In both cases, some of the present authors have derived the estimators (see Table I in [26]),
Λ 0 ( z ) ≅ ⟨ Λ 0 ⟩ (95) \Lambda_0(z) \cong\langle\Lambda_0\rangle \tag*{(95)} Λ 0 ( z ) ≅ ⟨ Λ 0 ⟩ (95)
δ P l ( q ) Λ l ( z ) e − β [ E z 0 , … , E z q − 1 ] e − β [ E z 0 , … , E z q ] ≅ ⟨ Λ l D l P l ⟩ , (96) \frac{\delta_{P_l}^{(q)}\Lambda_l(z)e^{-\beta[E_{z_0,\ldots,E_{z_q-1}]}}}{e^{-\beta[E_{z_0,\ldots,E_{z_q}]}}} \cong\langle\Lambda_lD_lP_l\rangle, \tag*{(96)} e − β [ E z 0 , … , E z q ] δ P l ( q ) Λ l ( z ) e − β [ E z 0 , … , E z q − 1 ] ≅ ⟨ Λ l D l P l ⟩ , (96)
and hence, we can evaluate ⟨ H 1 ⟩ \langle H_1\rangle ⟨ H 1 ⟩ in O ( R ) O(R) O ( R ) calls to these O ( 1 ) O(1) O ( 1 ) estimators. Here, Λ l ( z ) = ⟨ z ∣ Λ l ∣ z ⟩ \Lambda_l(z)=\langle z|\Lambda_l|z\rangle Λ l ( z ) = ⟨ z ∣ Λ l ∣ z ⟩ and δ P l ( q ) = 1 \delta_{P_l}^{(q)}=1 δ P l ( q ) = 1 if the q q q th permutation in S i q S_{i_q} S i q is P l P_l P l and is 0 otherwise. (Recall that products of permutations S i q S_{i_q} S i q partially make up PMR-QMC configurations as explained in Section A.)
Similarly, we can estimate ⟨ H 1 ( τ ) H 1 ⟩ \langle H_1(\tau)H_1\rangle ⟨ H 1 ( τ ) H 1 ⟩ by evaluating all R 2 R^2 R 2 estimators of the form ⟨ A ( τ ) B ⟩ \langle A(\tau)B\rangle ⟨ A ( τ ) B ⟩ for A , B ∈ { Λ 0 , Λ 1 D 1 P 1 , … , Λ R − 1 D R − 1 P R − 1 } A,B\in\{\Lambda_0,\Lambda_1D_1P_1,\ldots,\Lambda_{R-1}D_{R-1}P_{R-1}\} A , B ∈ { Λ 0 , Λ 1 D 1 P 1 , … , Λ R − 1 D R − 1 P R − 1 } . Just as the above estimator, it is best to consider the four possible ways of combining a pure diagonal contribution with a pure off-diagonal one,
Λ 0 ( z ) e − β [ E z 0 , … , E z q ] ∑ j = 0 q Λ 0 ( z j ) e − τ [ E z j , … , E z q ] e − ( β − τ ) [ E z 0 , … , E z j ] ≅ ⟨ Λ 0 ( τ ) Λ 0 ⟩ (97) \frac{\Lambda_0(z)}{e^{-\beta[E_{z_0,\ldots,E_{z_q}]}}\sum_{j=0}^{q}\Lambda_0(z_j)e^{-\tau[E_{z_j,\ldots,E_{z_q}]}e^{-(\beta-\tau)[E_{z_0,\ldots,E_{z_j}]}}} \cong\langle\Lambda_0(\tau)\Lambda_0\rangle} \tag*{(97)} e − β [ E z 0 , … , E z q ] ∑ j = 0 q Λ 0 ( z j ) e − τ [ E z j , … , E z q ] e − ( β − τ ) [ E z 0 , … , E z j ] ≅ ⟨ Λ 0 ( τ ) Λ 0 ⟩ Λ 0 ( z ) (97)
δ P k ( q ) Λ k ( z ) e − β [ E z 0 , … , E z q ] ∑ j = 0 q Λ 0 ( z j ) e − τ [ E z j , … , E z q − 1 ] e − ( β − τ ) [ E z 0 , … , E z j ] ≅ ⟨ ( Λ k D k P k ) ( τ ) Λ 0 ⟩ (98) \frac{\delta_{P_k}^{(q)}\Lambda_k(z)}{e^{-\beta[E_{z_0,\ldots,E_{z_q}]}}\sum_{j=0}^{q}\Lambda_0(z_j)e^{-\tau[E_{z_j,\ldots,E_{z_q-1}]}e^{-(\beta-\tau)[E_{z_0,\ldots,E_{z_j}]}}} \cong\langle(\Lambda_kD_kP_k)(\tau)\Lambda_0\rangle} \tag*{(98)} e − β [ E z 0 , … , E z q ] ∑ j = 0 q Λ 0 ( z j ) e − τ [ E z j , … , E z q − 1 ] e − ( β − τ ) [ E z 0 , … , E z j ] ≅ ⟨( Λ k D k P k ) ( τ ) Λ 0 ⟩ δ P k ( q ) Λ k ( z ) (98)
Λ 0 ( z ) e − β [ E z 0 , … , E z q ] ∑ j = 1 q − 1 δ P l ( j ) Λ l ( z j ) e − τ [ E z j , … , E z q ] e − ( β − τ ) [ E z 0 , … , E z j − 1 ] ≅ ⟨ Λ 0 ( τ ) ( Λ l D l P l ) ⟩ (99) \frac{\Lambda_0(z)}{e^{-\beta[E_{z_0,\ldots,E_{z_q}]}}\sum_{j=1}^{q-1}\delta_{P_l}^{(j)}\Lambda_l(z_j)e^{-\tau[E_{z_j,\ldots,E_{z_q}]}e^{-(\beta-\tau)[E_{z_0,\ldots,E_{z_j-1}]}}} \cong\langle\Lambda_0(\tau)(\Lambda_lD_lP_l)\rangle} \tag*{(99)} e − β [ E z 0 , … , E z q ] ∑ j = 1 q − 1 δ P l ( j ) Λ l ( z j ) e − τ [ E z j , … , E z q ] e − ( β − τ ) [ E z 0 , … , E z j − 1 ] ≅ ⟨ Λ 0 ( τ ) ( Λ l D l P l )⟩ Λ 0 ( z ) (99)
δ P k ( q ) Λ k ( z ) e − β [ E z 0 , … , E z q ] ∑ j = 1 q − 1 δ P l ( j ) Λ l ( z j ) e − τ [ E z j , … , E z q − 1 ] e − ( β − τ ) [ E z 0 , … , E z j − 1 ] ≅ ⟨ ( Λ k D k P k ) ( τ ) ( Λ l D l P l ) ⟩ . (100) \frac{\delta_{P_k}^{(q)}\Lambda_k(z)}{e^{-\beta[E_{z_0,\ldots,E_{z_q}]}}\sum_{j=1}^{q-1}\delta_{P_l}^{(j)}\Lambda_l(z_j)e^{-\tau[E_{z_j,\ldots,E_{z_{q-1}}]}e^{-(\beta-\tau)[E_{z_0,\ldots,E_{z_{j-1}}]}}} \cong\langle(\Lambda_kD_kP_k)(\tau)(\Lambda_lD_lP_l)\rangle.} \tag*{(100)} e − β [ E z 0 , … , E z q ] ∑ j = 1 q − 1 δ P l ( j ) Λ l ( z j ) e − τ [ E z j , … , E z q − 1 ] e − ( β − τ ) [ E z 0 , … , E z j − 1 ] ≅ ⟨( Λ k D k P k ) ( τ ) ( Λ l D l P l )⟩ . δ P k ( q ) Λ k ( z ) (100)
where each estimator follows as different special cases of the derivation in Sec. VIII.A in Ref. [26]. As with the ⟨ D 0 ( τ ) D 0 ⟩ \langle D_0(\tau)D_0\rangle ⟨ D 0 ( τ ) D 0 ⟩ estimator, each of these estimators requires O ( q 2 ) O(q^2) O ( q 2 ) operations, so the total complexity to evaluate ⟨ H 1 ( τ ) H 1 ⟩ \langle H_1(\tau)H_1\rangle ⟨ H 1 ( τ ) H 1 ⟩ is simply O ( R 2 q 2 ) O(R^2q^2) O ( R 2 q 2 ) .
Although these estimators are more complicated than the pure diagonal counterparts Section E 2, the big picture for ES and FS is the same. Namely, the only non-trivial τ \tau τ dependence is contained in the divided differences of the correlator estimator, for which we can apply the divided difference integral relations we have already derived.
General ES estimator
As in the derivation of the diagonal ES estimator, we need only consider deriving an estimator for ∫ 0 β ⟨ H 1 ( τ ) H 1 ⟩ d τ \int_0^\beta\langle H_1(\tau)H_1\rangle\mathrm{d}\tau ∫ 0 β ⟨ H 1 ( τ ) H 1 ⟩ d τ and combine it with our ⟨ H 1 ⟩ \langle H_1\rangle ⟨ H 1 ⟩ estimators. Although ⟨ H 1 ( τ ) H 1 ⟩ \langle H_1(\tau)H_1\rangle ⟨ H 1 ( τ ) H 1 ⟩ really consists of four different possible estimators, each of these contains an expression of the form e − τ [ … ] e − ( β − τ ) [ … ] e^{-\tau[\ldots]}e^{-(\beta-\tau)[\ldots]} e − τ [ … ] e − ( β − τ ) [ … ] for which we can apply the convolution lemma, Lemma 1. For example, applying this lemma to Eqs. (97) and (F8), we find
Λ 0 ( z ) e − β [ E z 0 , … , E z q ] ∑ j = 0 q Λ 0 ( z j ) e − β [ E z 0 , … , E z q , E z j ] = ^ ∫ 0 β ⟨ Λ 0 ( τ ) Λ 0 ⟩ d τ (101) \frac{\Lambda_0(z)}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{j=0}^{q}\Lambda_0(z_j)e^{-\beta[E_{z_0},\ldots,E_{z_q},E_{z_j}]} \widehat{=} \int_0^\beta\langle\Lambda_0(\tau)\Lambda_0\rangle\mathrm{d}\tau \tag*{(101)} e − β [ E z 0 , … , E z q ] Λ 0 ( z ) j = 0 ∑ q Λ 0 ( z j ) e − β [ E z 0 , … , E z q , E z j ] = ∫ 0 β ⟨ Λ 0 ( τ ) Λ 0 ⟩ d τ (101)
δ P k ( q ) Λ k ( z ) e − β [ E z 0 , … , E z q ] ∑ j = 1 q − 1 δ P l ( j ) Λ l ( z j ) e − β [ E z 0 , … , E z q − 1 ] = ^ ∫ 0 β ⟨ ( Λ k D k P k ) ( τ ) ( Λ l D l P l ) ⟩ d τ . (102) \frac{\delta_{P_k}^{(q)}\Lambda_k(z)}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{j=1}^{q-1}\delta_{P_l}^{(j)}\Lambda_l(z_j)e^{-\beta[E_{z_0},\ldots,E_{z_{q-1}}]} \widehat{=} \int_0^\beta\langle(\Lambda_kD_kP_k)(\tau)(\Lambda_lD_lP_l)\rangle\mathrm{d}\tau. \tag*{(102)} e − β [ E z 0 , … , E z q ] δ P k ( q ) Λ k ( z ) j = 1 ∑ q − 1 δ P l ( j ) Λ l ( z j ) e − β [ E z 0 , … , E z q − 1 ] = ∫ 0 β ⟨( Λ k D k P k ) ( τ ) ( Λ l D l P l )⟩ d τ . (102)
The former clearly resembles ⟨ D 0 ( τ ) D 0 ⟩ \langle D_0(\tau)D_0\rangle ⟨ D 0 ( τ ) D 0 ⟩ and is computable in O ( q 2 ) O(q^2) O ( q 2 ) time. Unfortunately, unlike the diagonal case simplification in Theorem 1, there does not appear any way to simplify the sum into an O ( 1 ) O(1) O ( 1 ) expression since Λ 0 ( z j ) \Lambda_0(z_j) Λ 0 ( z j ) has no relation to E z j E_{z_j} E z j . On the other hand, the second estimator can be simplified. Namely, since the inner divided difference has no direct j j j dependence,
δ P k ( q ) Λ k ( z ) e − β [ E z 0 , … , E z q ] ∑ j = 1 q − 1 δ P l ( j ) Λ l ( z j ) e − β [ E z 0 , … , E z q − 1 ] = δ P k ( q ) Λ k ( z ) e − β [ E z 0 , … , E z q ] e − β [ E z 0 , … , E z q − 1 ] ∑ j = 1 q − 1 δ P l ( j ) Λ l ( z j ) , (103) \frac{\delta_{P_k}^{(q)}\Lambda_k(z)}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{j=1}^{q-1}\delta_{P_l}^{(j)}\Lambda_l(z_j)e^{-\beta[E_{z_0},\ldots,E_{z_{q-1}}]}=\frac{\delta_{P_k}^{(q)}\Lambda_k(z)}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}e^{-\beta[E_{z_0},\ldots,E_{z_{q-1}}]}\sum_{j=1}^{q-1}\delta_{P_l}^{(j)}\Lambda_l(z_j), \tag*{(103)} e − β [ E z 0 , … , E z q ] δ P k ( q ) Λ k ( z ) j = 1 ∑ q − 1 δ P l ( j ) Λ l ( z j ) e − β [ E z 0 , … , E z q − 1 ] = e − β [ E z 0 , … , E z q ] δ P k ( q ) Λ k ( z ) e − β [ E z 0 , … , E z q − 1 ] j = 1 ∑ q − 1 δ P l ( j ) Λ l ( z j ) , (103)
then this is actually an O ( q ) O(q) O ( q ) expression. In total, this means evaluating χ E H 1 \chi_{E}^{H_1} χ E H 1 for completely general H 1 H_1 H 1 takes O ( R 2 q 2 ) O(R^2q^2) O ( R 2 q 2 ) time. In the special case that H 1 H_1 H 1 has no pure diagonal term, however, our ES estimator needs O ( R 2 q ) O(R^2q) O ( R 2 q ) effort instead.
General FS estimator
For the FS, the same logic as in the previous section applies except we employ the more complicated integral lemma, Lemma 3, to evaluate ∫ 0 β / 2 τ ⟨ H 1 ( τ ) H 1 ⟩ d τ \int_0^{\beta/2}\tau\langle H_1(\tau)H_1\rangle\mathrm{d}\tau ∫ 0 β /2 τ ⟨ H 1 ( τ ) H 1 ⟩ d τ . Doing so to Eqs. (97) and (F8), we find
Λ 0 ( z ) e − β [ E z 0 , … , E z q ] ∑ j = 0 q Λ 0 ( z j ) ∑ r = 0 j e − β 2 [ E z 0 , … , E z j ] ∑ m = j q e − β 2 [ E z r , … , E z q , E z j , E z m ] = ^ ∫ 0 β / 2 τ ⟨ Λ 0 ( τ ) Λ 0 ⟩ d τ (104) \frac{\Lambda_0(z)}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{j=0}^{q}\Lambda_0(z_j)\sum_{r=0}^{j}e^{-\frac{\beta}{2}[E_{z_0},\ldots,E_{z_j}]}\sum_{m=j}^{q}e^{-\frac{\beta}{2}[E_{z_r},\ldots,E_{z_q},E_{z_j},E_{z_m}]} \widehat{=} \int_0^{\beta/2}\tau\langle\Lambda_0(\tau)\Lambda_0\rangle\mathrm{d}\tau \tag*{(104)} e − β [ E z 0 , … , E z q ] Λ 0 ( z ) j = 0 ∑ q Λ 0 ( z j ) r = 0 ∑ j e − 2 β [ E z 0 , … , E z j ] m = j ∑ q e − 2 β [ E z r , … , E z q , E z j , E z m ] = ∫ 0 β /2 τ ⟨ Λ 0 ( τ ) Λ 0 ⟩ d τ (104)
δ P k ( q ) Λ k ( z ) e − β [ E z 0 , … , E z q ] ∑ j = 1 q − 1 δ P l ( j ) Λ l ( z j ) ∑ r = 0 j − 1 e − β 2 [ E z 0 , … , E z j ] ∑ m = j − 1 q − 1 e − β 2 [ E z r , … , E z q − 1 , E z m ] = ^ ∫ 0 β / 2 τ ⟨ ( Λ k D k P k ) ( τ ) ( Λ l D l P l ) ⟩ d τ , (105) \frac{\delta_{P_k}^{(q)}\Lambda_k(z)}{e^{-\beta[E_{z_0},\ldots,E_{z_q}]}}\sum_{j=1}^{q-1}\delta_{P_l}^{(j)}\Lambda_l(z_j)\sum_{r=0}^{j-1}e^{-\frac{\beta}{2}[E_{z_0},\ldots,E_{z_j}]}\sum_{m=j-1}^{q-1}e^{-\frac{\beta}{2}[E_{z_r},\ldots,E_{z_{q-1}},E_{z_m}]} \widehat{=} \int_0^{\beta/2}\tau\langle(\Lambda_kD_kP_k)(\tau)(\Lambda_lD_lP_l)\rangle\mathrm{d}\tau, \tag*{(105)} e − β [ E z 0 , … , E z q ] δ P k ( q ) Λ k ( z ) j = 1 ∑ q − 1 δ P l ( j ) Λ l ( z j ) r = 0 ∑ j − 1 e − 2 β [ E z 0 , … , E z j ] m = j − 1 ∑ q − 1 e − 2 β [ E z r , … , E z q − 1 , E z m ] = ∫ 0 β /2 τ ⟨( Λ k D k P k ) ( τ ) ( Λ l D l P l )⟩ d τ , (105)
where neither can be simplified by our prior formulas or clear new insights. As such, both require O ( q 4 ) O(q^4) O ( q 4 ) effort to compute, and the overall complexity of a general FS estimator requires O ( R 2 q 4 ) O(R^2q^4) O ( R 2 q 4 ) time.