PaperlayerView exact revision on arXiv

Source-linked AI summary

Polynomial-time classical and quantum simulation of quantum impurity models

Jiaqing Jiang, Nathan Ju, Ojas Parekh, Chaithanya Rayudu, Andrew Zhao

arXiv:2610.02167v1quant-phcond-mat.str-elcs.CCcs.DSphysics.chem-ph

TL;DR

Although impurity solvers are central to embedding methods, their rigorous efficiency was unclear, leaving open whether impurity models admit unconditional polynomial-time simulation. The paper uses state compression to establish efficient classical simulation of static properties, while showing that finite-temperature dynamical Green's functions capture universal quantum computation.

  • Problem

    Impurity solvers are central to embedding methods, but their rigorous efficiency was unclear and an unconditional polynomial-time algorithm for impurity models remained an open question.

    Source: §1 · p. 3

  • Method

    The paper develops compression methods for static-state simulation and new encodings with algorithmic cooling to establish finite-temperature dynamical hardness.

    Source: §1.1 · pp. 5–6

  • Results

    Static ground-state and thermal properties admit polynomial-time classical algorithms, whereas estimating nonequilibrium Green's functions is complete for universal quantum computation even at finite temperature.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The results rule out superpolynomial quantum speedups for static properties while identifying dynamical impurity simulation as a route to quantum advantage.

    Source: §1 · pp. 3–4

    The algorithms have exponential dependence on impurity size m, treated as a fixed constant, and the possibility of a polynomial quantum speedup for static properties remains open.

    Source: §1.3 · p. 10

Abstract

from arXiv · show

Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods. They describe a small subsystem of interacting fermions coupled to a large, noninteracting bath. We perform a comprehensive study of the computational complexity of simulating impurity models, delineating the boundary between classical and quantum tractability for this class of problems. Our main finding is that static properties of quantum impurity models can be calculated efficiently on a classical computer. Specifically, we give classical algorithms that (1) estimate the ground-state energy to additive precision $\delta$ in time $\mathrm{poly}(n,\delta^{-1})$, and (2) estimate the partition function at inverse temperature $\beta$ to relative precision $\delta$ in time $\mathrm{poly}(n,\beta,\delta^{-1})$, where $n$ is the system size. These results improve the previous best-known complexity for ground-state energy estimation from quasipolynomial to polynomial time, while establishing for the first time rigorous polynomial-time guarantees for simulating impurity models in thermal equilibrium. On the other hand, we find that simulating dynamical properties of impurity models is hard for classical computers but easy on a quantum computer. As a canonical example, we show that computing their nonequilibrium Green's functions captures the full power of quantum computation, even at finite temperature. Taken together, our results rule out superpolynomial quantum speedups for computing static properties, but provide an avenue for quantum advantage in simulating impurity physics out of equilibrium.

1 Introduction

The section examines the computational tractability of quantum impurity models, contrasting polynomial-time classical algorithms for static properties with dynamics, where nonequilibrium Green’s functions can capture quantum-computational hardness. It also describes a subspace-compression approach and points to open directions for extending or improving the results.

1 Introduction

  • Static ground-state and thermal properties are classically computable in polynomial time, improving the prior ground-energy guarantee [BG17] and ruling out superpolynomial quantum speedups for these properties.The results also provide the first rigorous analysis of thermal simulation for impurity models.Source: §1 · p. 3
  • At finite temperature, estimating nonequilibrium Green’s functions is complete for universal quantum computation, while at infinite temperature it remains complete for the one-clean-qubit model.The results imply that any superpolynomial quantum advantage for quantum-enhanced DMFT must come from dynamical quantities.Source: §1 · p. 4

1.1 Main results

  • For a constant-size interacting impurity coupled to a free-fermion bath, ground energy and thermal properties can be estimated classically in polynomial time without geometric or spectral assumptions.The ground-energy runtime is poly(n, δ^-1); thermal expectation values of fermionic Gaussian operators and the partition function have runtime poly(n, β, δ^-1).Source: §1.1 · p. 4
  • The compression lemma gives ground states support on dimension poly(n, δ^-1, ω^-1) and, when βω ≥ 9 log n, thermal states support on dimension poly(n, β, δ^-1), independent of impurity interaction and coupling strengths.For ground-energy estimation, ω can be adjusted to Ω(δ/n) while changing the ground energy by O(δ).Source: §1.1 · p. 5

1.2 Technical overview

  • A bandwise Krylov basis is computable without knowing the ground state, creates a coarse-grained one-dimensional chain, and enables compression despite arbitrary impurity-bath coupling.The method separates bath energies into bands, enlarges the impurity with the first Krylov block, and controls higher-order occupation statistics to obtain a polynomial-dimensional compressed subspace.Source: §1.2 · pp. 7, 9

1.3 Outlook

  • Compression yields polynomial-time classical algorithms for static impurity properties, ruling out superpolynomial quantum advantage for the static problem [BG17].The framework approximates ground states and thermally gapped Gibbs-state components in low-dimensional subspaces, putting impurity solvers’ empirical success [GML+11] on rigorous footing; applications such as DMFT [BWM+16] would need to exploit dynamics for superpolynomial advantage.Source: §1.3 · p. 9
  • Extending compression to excited states or adapting it to dynamical problems could broaden which impurity properties admit provably efficient classical simulation [ATE+14].Source: §1.3 · pp. 9–10
  • The algorithms have exponential dependence on impurity size m, treated as fixed; reducing it could enable nontrivial algorithms for extensive systems such as the Fermi–Hubbard model [QSA+22].Source: §1.3 · p. 10
  • A polynomial quantum speedup for static properties remains possible if a smaller subspace with constant ground-state overlap can be identified and combined with quantum phase estimation.Source: §1.3 · p. 10

2 Preliminaries

The preliminaries set up fermionic modes and their Fock-space representation, then place impurity Hamiltonians in a form separating impurity, bath, and hybridization terms. They also state preprocessing assumptions used in the analysis.

2.1 Background on fermions

  • Fermionic modes obey the canonical anticommutation relations, and their Fock basis labels each mode by an occupation bit.Single-particle basis rotations induce corresponding changes of fermionic modes.Source: §2.1 · pp. 10–11

2.2 Preprocessing of the impurity Hamiltonian

  • The analysis assumes a polynomially bounded Hamiltonian norm and permits a strictly positive lower bound on bath single-particle energies.The ground state and thermal state at inverse temperature β are defined for the impurity Hamiltonian.Source: §2.2 · pp. 12–13
  • Preprocessing writes the Hamiltonian as impurity-only, bath-only, and hybridization terms, with a diagonal bath matrix and potentially nonorthogonal hybridization vectors.The bath quadratic term acts only on bath modes, while each hybridization term couples a bath mode to an odd-parity impurity operator.Source: §2.2 · p. 12

3 Bandwise Krylov representation

The section constructs a bandwise Krylov representation that gives impurity models a one-dimensional bath structure. It then enlarges the impurity to control its coupling to the residual bath and establishes a weighted-positivity property.

3.1 One-dimensional structure via block tridiagonalization

  • Krylov orthogonalization makes the bath matrix block tridiagonal, so each bath block couples only to neighboring blocks and the impurity couples to the first block.Each block has at most 2m modes.Source: Figure 1 · p. 14, §3.1 · p. 15

3.2 Bandwise Krylov basis

  • Partitioning the bath spectrum into logarithmically spaced bands and constructing Krylov bases within each yields a bandwise one-dimensional structure.The unpartitioned Krylov construction has simulation complexity exponential in the inverse lower energy bound when that bound is small.Source: §3.2 · p. 16

3.3 Bandwise hybridization form with an enlarged impurity

  • Including the first Krylov shell from each band in an enlarged impurity produces the bandwise hybridization form used thereafter.The enlargement is intended to reduce classical simulation cost by controlling the interaction strength between the enlarged impurity and residual bath.Source: §3.3 · pp. 17–18

3.4 Weighted positivity of the bath in the bandwise Krylov basis

  • The bandwise one-dimensional structure yields a weighted-positivity property for the bath under depth weights whose adjacent differences are bounded by one.The lemma states the property for each band and for 0 < λ ≤ 1/4.Source: §3.4 · pp. 18–19

4 Compression lemma and recursion for occupation statistics

The section develops a route from weighted residual-bath occupations to a compact support for the state of interest. It expresses the needed exponential-moment bounds through joint occupations and a commutator-based recursion.

4.1 Bounding the support via weighted occupation statistics

  • A bound on the exponential moment of depth-weighted residual-bath occupation gives an approximately supported, classically enumerable subspace.The subspace is polynomial-size when ω = 1/poly(n) and Tr(ρe^D/2) = poly(n); thermal applications restrict the bound to the thermally gapped region βω ≥ 9 log n.Source: §4.1 · pp. 20–21

4.2 Notation for joint occupations

  • The target exponential moment is further bounded using joint occupation statistics grouped by energy band.The notation tracks the number of selected bath modes in each band.Source: §4.2 · pp. 21–22

4.3 The commutator identity

  • The commutator identity separates bath-replacement terms of unchanged residual-bath degree from hybridization terms of lower degree.This triangular structure supports recursion from higher- to lower-order occupation quantities.Source: §4.3 · p. 23

4.4 A recursion formula for Fq with commutators

  • The recursion bounds the bath contribution using weighted positivity and bounds the hybridization source using Cauchy–Schwarz and ξℓ.The remaining commutator contribution is estimated separately for ground-state and thermal-state analyses.Source: §4.3 · p. 23, §4.4 · pp. 24–26

5 Efficient simulation for ground states

Ground-state simulation proceeds by compressing the state into an efficiently enumerable subspace of polynomial dimension, then estimating the energy of the projected Hamiltonian. The resulting classical algorithm estimates ground energy in polynomial time.

5.1 Compression of the ground state

  • Residual-bath occupation in the ground state decays exponentially with Krylov depth.This localization result underlies the ground-state compression.Source: §5.1 · p. 26
  • A ground state can be approximated using an efficiently enumerable subspace of dimension poly(n, δ^-1, J, ω^-1), whose projected Hamiltonian ground energy differs by at most ||H||δ.The compression statement applies to any ground state of the specified impurity Hamiltonian.Source: §5.1 · p. 27

5.2 Efficient classical algorithm for ground-energy estimation

  • A classical algorithm estimates the ground energy of an impurity model to additive error δ in time poly(n, δ^-1).The proof uses a compressed subspace and diagonalizes the Hamiltonian restricted to it.Source: §5.2 · p. 27

6 Efficient simulation for thermal states

This section develops efficient methods for simulating impurity-model thermal states, including classical estimation of thermal expectation values and partition functions and quantum preparation of thermal states, using compression with continuous-time quantum Monte Carlo or quantum belief propagation.

6.1 Compression of the thermal state

  • When βω ≥ 9 log n, the thermal state can be compressed to an efficiently enumerable subspace of dimension poly(n, β, J, δ^-1).The projected thermal state and partition function are close to their unprojected counterparts; the compression also applies with an even-parity M commuting with every residual-bath mode.Source: §6.1 · p. 30

6.2 The soft–hard decomposition

  • The soft–hard decomposition isolates active modes containing the impurity coupling, while the dark modes decouple; the impurity term acts on at most 2m fermionic modes.The section then partially compresses the active sector, whose subspace has dimension poly(n, β, J, δ^-1).Source: §6.2 · pp. 32–33

6.3 Efficient classical simulation via continuous-time quantum Monte Carlo

  • Compression and the soft–hard decomposition reduce the effective perturbation to βW = O(log n), enabling CT-QMC to achieve runtime polynomial in β.The CT-QMC approach truncates an imaginary-time interaction-picture expansion and estimates thermal expectation values and the partition function by sampling configurations.Source: §6.3 · pp. 33–34
  • For any β > 0, thermal expectation values of norm-at-most-one Hermitian Gaussian observables and the partition function are estimable by a randomized classical algorithm in time poly(n, β, J, ϵ^-1).Theorem 6.8 gives estimates of both quantities; the observable condition is stated for Gaussian observables.Source: §6.3 · p. 34
  • Each dark-sector factor is computable in polynomial time using Pfaffians of polynomial-size matrices, enabling classical estimates of thermal expectation values and the partition function.The argument uses the generalized Wick theorem [Lie68, BB69] and the standard Pfaffian formula for fermionic Gaussian traces [Kli14] [Bra05].Source: §6.3 · p. 35

6.4 Efficient thermal state preparation from quantum belief propagation

  • Given an efficient circuit for the purified Gibbs state of Href, QBP prepares the perturbed thermal state with complexity exponential in β∥V∥ and at most polynomial in other parameters.The result applies to the generic H0 + V scenario; the authors note prior generic-Hamiltonian work [HMS+22] had eO(β∥V∥/δ) scaling for trace-distance error δ, and identify QBP with.Source: §6.4 · p. 36
  • For impurity models, β∥V∥ = O(log n), while the reference Hamiltonian can be handled efficiently through compression.This structural condition makes the QBP preparation guarantee efficient for the impurity-model application.Source: §6.4 · p. 36
  • For quantum impurity models, a quantum algorithm prepares a state within trace-distance error δ of the thermal state in runtime poly(n, β, J, δ^-1).This guarantee holds for any β > 0 and 0 < δ < 1.Source: §6.4 · p. 36

7 Hardness of simulating dynamical properties

This section characterizes the complexity of simulating dynamical impurity properties, focusing on time-dependent correlation functions and nonequilibrium Green’s functions. It establishes classical hardness and quantum complexity results across infinite and nonzero temperatures, including finite-temperature BQP-hardness for inverse-polynomial additive approximation.

7.2 Statement of results

  • Problem 7.7 is DQC1-complete at β=0 and BQP-complete for β∈[Ω(1), poly(n)], with inverse-polynomial error and polynomial times, even for m=4 and single-site A and B.The Hamiltonian is assumed efficiently computable to inverse-polynomial precision, with coefficients bounded by 1.Source: §7.2 · p. 38

7.3 Universality of time-dependent impurity Hamiltonians

  • A single-ancilla construction encodes any n-qubit circuit V into an (n+1)-mode impurity unitary U=e^{iϕ}(V⊕V), preserving normalized trace exactly with polynomial overhead.The evolution takes t=O(n^2L), where L is the circuit length.Source: §7.3 · p. 39

7.4 DQC1-completeness at infinite temperature

  • At β=0, the correlation function is a normalized unitary trace, and two calls to Problem 7.7 recover its real and imaginary parts, reducing DQC1-complete trace estimation to the problem.The hardness reduction sets t′=0 and uses polynomial-size impurity evolutions.Source: §7.4 · pp. 41–42

7.5 BQP-completeness at finite temperature

  • At finite temperature, thermal-state preparation and a Hadamard test establish BQP containment, while thermal-bit concentration enables hardness from a constant nonzero inverse temperature.For constant bias, O(q) thermal qubits suffice to obtain q nearly pure qubits; the hardness argument fixes β=Θ(1).Source: §7.5 · pp. 42–44
  • At finite temperature, an inverse-polynomial additive approximation to the correlation function decides every quantum-circuit acceptance instance, proving BQP-hardness.The construction uses polynomial-size circuits on polynomially many fermionic modes.Source: §7.5 · p. 45

A.1 Canonical form of a quadratic Hamiltonian

  • An orthogonal canonical transformation diagonalizes the quadratic bath Hamiltonian into single-particle energies while preserving a bilinear impurity-bath coupling form.The appendix uses this form to derive Eq. (2.13).Source: §A.1 · p. 53

A.2 Handling zero eigenvalues of E0

  • Coupled zero-eigenvalue bath modes are absorbed into the impurity space, while uncoupled zero modes form a separate free-fermion sector, leaving E0 strictly positive on the remaining bath space.The uncoupled modes can be treated separately because the Hamiltonian acts as the identity on that sector.Source: §A.2 · p. 54

B.1 Counting and enumerating the set {x : D(x) ≤T}

The section bounds and enumerates strings whose weighted occupation number is at most T. Its enumeration prunes partial strings and runs in O(n|S|) time.

B.1 Counting and enumerating the set {x : D(x) ≤T}

  • χ bounds the maximum number of bath modes at a depth, summed across bands, plus the enlarged-impurity size.For depths below τ, each depth has at most χ modes; modes at depth d(i)−1 ≥ τ are counted with at most n modes.Source: §B.1 · p. 54
  • The counting proof replaces the hard cutoff with an exponential weight and factorizes the resulting weighted sum over modes.The enlarged-impurity modes and depth-1 modes each contribute a factor of 2, for a total factor at most 2^χ.Source: §B.1 · p. 54
  • The proof bounds the depth-grouped factors using log(1 + e^x) ≤ e^x and sets θ = 8.The low-depth sum is relaxed to range over all k ≥ 1.Source: §B.1 · p. 55
  • O(n|S|) time suffices to enumerate exactly the strings x with D(x) ≤ T by extending bitwise and discarding prefixes whose weighted occupation exceeds T.Nonnegative weights ensure that a discarded prefix cannot lead to a qualifying string.Source: §B.1 · p. 55

B.2 Proof of the commutator identity

The commutator identity is proved by applying the product rule and separating bath-replacement and hybridization contributions. Anticommutation signs restore the operator ordering in each contribution.

B.2 Proof of the commutator identity

  • The product rule reduces the commutator proof to treating two sums on the right-hand side separately.The sums correspond to bath replacement and hybridization contributions.Source: §B.2 · p. 55
  • The bath-replacement terms acquire a sign when annihilation operators are reordered, and summing them over r and j gives B_I.The sign follows from anticommutation of distinct-mode annihilation operators.Source: §B.2 · p. 55
  • The hybridization terms acquire a sign when Gℓ(ir)s is moved through residual-bath annihilation operators, and summing over r and s gives C_I.The enlarged-impurity modes are disjoint from the residual-bath modes.Source: §B.2 · p. 55

B.3 Recursion solution for the ground state

The ground-state recursion is solved by induction on total occupation number. The proof then uses the recursion solution in the subsequent theorem bound.

B.3 Recursion solution for the ground state

  • The proof establishes the solution to the recursion in Eq. (5.5) by induction on total occupation number q.It starts at q = 0 and assumes the claim for total degree |q| − 1.Source: §B.3 · p. 56
  • Applying Eq. (5.5) with the induction hypothesis and canceling a common factor proves the claimed recursion solution.The proof factors out the common term before cancellation.Source: §B.3 · p. 56
  • The argument sets λ = 1/4 and applies Eq. (4.13) with Eq. B.11; for any residual bath mode i, it sets q = eℓ(i) and recalls Eq. (3.16).Source: §B.3 · p. 56

B.4 Recursion solution for the thermal state

The thermal recursion is solved for positive ω by induction over multi-index occupation vectors. The proof then sums the resulting bounds to establish an upper bound on the stated quantity.

B.4 Recursion solution for the thermal state

  • For ω > 0, Lemma B.2 gives a solution to the thermal recursion for every occupation vector q.The frequencies satisfy ωℓ = 2^ℓω, and r ≤ q means rℓ ≤ qℓ for every ℓ.Source: §B.4 · p. 56
  • The proof establishes the thermal recursion solution by induction on total degree, starting with q = 0 and assuming the result for lower degrees.It applies Lemma 6.2 and the induction hypothesis to q and related vectors.Source: §B.4 · p. 57
  • Because αq−r ≤ αq, the right-hand side of Eq. (B.18) is bounded by αq times the right-hand side of Eq. (B.16), yielding the claim after division.The proof then sums over q and combines the resulting bounds to obtain the stated upper bound.Source: §B.4 · p. 57

B.5 Thermal state approximation by a projected Hamiltonian

The section studies approximating a thermal state using a Hamiltonian projected onto a subspace. It bounds the resulting partition-function error in terms of the inverse temperature, the coupling across the projection, and the stated approximation parameter.

B.5 Thermal state approximation by a projected Hamiltonian

  • The projected thermal state σP is defined from PHP restricted to the range of P.The section compares it with the thermal state of H.Source: §B.5 · p. 58
  • |Z − ZP| ≤ 4(1 + βθP)δ^1/4Z bounds the partition-function error for the projected Hamiltonian.Here θP is defined as ∥PH(I − P)∥.Source: §B.5 · p. 58
  • The block-diagonal Hamiltonian Hbd preserves the diagonal blocks of H, so each of its block-supported eigenvectors has the same expectation of H and Hbd.The argument uses this property to compare the corresponding thermal states and partition functions.Source: §B.5 · pp. 58–59
  • The partition functions satisfy ZP ≤ Zbd ≤ Z, supporting the comparison between the projected and full models.The section also relates ZP to Zbd through the weight of the projected block in the block-diagonal thermal state.Source: §B.5 · p. 59

C Continuous-time quantum Monte Carlo

The appendix introduces the decomposition used in its detailed algorithm and proof of Theorem 6.6. It specifies that the decomposition coefficients are real.

C Continuous-time quantum Monte Carlo

C.1 Imaginary-time interaction-picture expansion

The section expands e^−βH in an imaginary-time interaction picture around a reference Hamiltonian. It establishes convergence and gives a truncation order and associated partition-function accuracy.

C.1 Imaginary-time interaction-picture expansion

  • The imaginary-time interaction-picture expansion expresses e^−βH using ordered times and insertions of V around evolution under Href.It defines VI(τ) = e^τHref V e^−τHref.Source: §C.1 · p. 60
  • The truncated expansion uses K = O(βW + log(1/ϵ)) terms for precision parameter ϵ.The perturbation V has norm at most W.Source: §C.1 · p. 60
  • The expansion converges absolutely in trace norm.The ordered-time integration region has volume β^r/r! at order r.Source: §C.1 · p. 60
  • The truncated partition function satisfies ZK ≥ 15Z/16 and |ZK − Z| ≤ ϵZ/16.The section also bounds the error in the normalized expectation µK of a Hermitian observable with norm at most one.Source: §C.1 · p. 60

C.2 Continuous-time quantum Monte Carlo

The continuous-time quantum Monte Carlo method estimates thermal expectations and the partition function by sampling terms in the truncated interaction-picture expansion. The following Gibbs-state-preparation subsection describes a quantum belief propagation approach for Hamiltonians H = H0 + V.

C.2 Continuous-time quantum Monte Carlo

  • CT-QMC estimates the numerator and denominator using configurations from the expansion, with configuration evaluation bounded by Tcfg(K).The stated runtime is based on evaluating configurations of order at most K.Source: §C.2 · pp. 61, 63
  • Configurations are specified by an order r, perturbation labels, and ordered imaginary times, sampled using a truncated Poisson order and the weights |va|/W.The sampled times are sorted in descending order within [0, β].Source: §C.2 · p. 61
  • Each sampled configuration has bounded sample values |X| ≤ 1 and |Y| ≤ 1, enabling concentration bounds for their sample means.The proof uses Hoeffding’s inequality to control the estimates.Source: §C.2 · p. 62
  • The CT-QMC estimator’s total error is less than ϵ after combining its sampling estimate with the truncation bias bound.The proof also treats partition-function estimation.Source: §C.2 · pp. 62–63

D Gibbs state preparation via quantum belief propagation

The quantum belief propagation (QBP) operator

These parts develop quantum belief propagation methods for simulating impurity systems: constructing a block encoding of the QBP operator and using it to prepare the Gibbs state of a perturbed Hamiltonian from a purification of the original Hamiltonian. They describe approximation-error control and a mixed-state variant that trades space overhead for additional preparation rounds.

The quantum belief propagation (QBP) operator

  • Gaussian quadrature discretizes the integral defining Φ_r with exponentially convergent accuracy when V is positive semidefinite.The stated discretized approximation has error bounded by ε for a choice of quadrature size N; the exact bound is not visible in the supplied passages.Source: The quantum belief propagation (QBP)… · pp. 64, 66
  • A linear combination of N block encodings of e^(-itH_s)V e^(itH_s), weighted by quadrature weights, yields an approximate block encoding of Φ_s.The construction uses controlled queries at the quadrature nodes, with weights summing to at most one; its error combines quadrature error and input block-encoding error.Source: The quantum belief propagation (QBP)… · p. 66
  • The construction applies linear-combination-of-Hamiltonian-simulation methods to the positive-semidefinite generator derived from Φ_r to block encode the QBP evolution.The general simulation proposition gives normalization α = Θ(1) and ancilla overhead q + O(log(∥A∥L1) + log log ε^-1).Source: The quantum belief propagation (QBP)… · pp. 67, 70
  • Interpolating approximations to Φ_r between quadrature nodes enables time-dependent Hamiltonian simulation, whose resulting block encoding approximates the ideal evolution with error at most 2δ.The interpolation is piecewise linear, with the final interval held constant.Source: The quantum belief propagation (QBP)… · pp. 68–70
  • Theorem D.13 constructs a block encoding of the QBP operator from access to block encodings of e^(-itH_r)V e^(itH_r), subject to a bound on their error γ.The theorem assumes s ∈ (0, 1], β > 0, and bounds H_r over r ∈ [0, s]; the supplied passage does not show its full complexity expression.Source: The quantum belief propagation (QBP)… · p. 70
  • A mixed-Gibbs-state variant can reduce the space overhead by n qubits, but requires quadratically more rounds to prepare the state successfully.The stated protocol focuses on purified inputs and outputs because the mixed-state variant lacks amplitude amplification.Source: The quantum belief propagation (QBP)… · p. 72
  • Given exact block encodings of H0 and V and a circuit preparing the purification of the Gibbs state of H0, the theorem constructs a circuit outputting an approximation to the purification for H1.The theorem states gate and query complexity, but the supplied passage omits their expressions.Source: The quantum belief propagation (QBP)… · p. 72
  • The protocol uses fixed-point amplitude amplification; its success-branch amplitude is Ω(e^(-β∥V∥)), and choosing χ = Θ(ε) and δ = Θ(e^(-β∥V∥)ε) controls the final error.The proof shifts V to a positive semidefinite operator before applying the QBP construction and amplification.Source: The quantum belief propagation (QBP)… · p. 72
  • The final preparation complexity is O(L) times the cost of each η1 block encoding; the Br(t) components can be built with poly(λ0, λV, |t|) gates for |t| = e^O(β).The passage does not provide the omitted expression for L or the full block-encoding cost.Source: The quantum belief propagation (QBP)… · p. 73
Loading 2610.02167v1…