A quantum algorithm to count weighted ground states of classical spin Hamiltonians

Bhuvanesh Sundar; David T. Damanik; Kaden R. A. Hazzard; Leonardo Due\~nas-Osorio; Roger Paredes

REVIEW 3 major objections 3 minor 92 references

A quantum algorithm to count weighted ground states of classical spin Hamiltonians

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Modified QAOA and AQO count weighted ground states with user-set error and confidence.

desk verdict The importance-sampling construction is a real step forward, but Eq. (31) is off by a factor of M and Eq. (34) inverts the weight-moment dependence, so the counting protocol and the QAOA speedup as claimed don't survive. read the letter →

arxiv 1908.01745 v1 pith:LVH53GZD submitted 2019-08-05 quant-ph

Bhuvanesh Sundar , Roger Paredes , David T. Damanik , Leonardo Dueñas-Osorio , Kaden R. A. Hazzard This is my paper · ORCID

classification quant-ph

keywords quantumalgorithmsadiabaticoptimizationapproximateconstrainedsamplingandcountingedgecoversengineeringreliabilityweightedground-statecapture-recaptureestimation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper claims that by changing the initial state and the mixing Hamiltonian, AQO and QAOA can be turned from optimizers into importance samplers of ground states, enabling estimation of weighted ground-state counts with user-specified error and confidence. The key is that the modified evolution stays in a low-dimensional symmetric subspace, so every ground state is sampled with probability proportional to its weight. For edge-cover counting with small weights, the paper finds QAOA requires about $1/\sqrt{P}$ steps per iteration and total time that scales sub-quadratically better than optimal Monte Carlo; AQO does not beat the classical baseline. The counting protocol itself rests on a capture-recapture estimator that converts measured distinct-state and weight totals into $P$.

What carries the argument

The central object is the symmetric subspace $H_S$ spanned by $|\Phi_j\rangle = \sum_{\varphi: H_z(\varphi)=E_j} \sqrt{w(\varphi)}|\varphi\rangle / \sqrt{N_j^{(1)}}$, together with the mixing Hamiltonian $\hat H_x = -|\psi(0)\rangle\langle\psi(0)| = (U_0 - 1)/2$, where $|\psi(0)\rangle = \sum_\varphi \sqrt{w(\varphi)}|\varphi\rangle$ is the weighted initial state. This choice makes the projected Hamiltonian rank-one in $H_S$, so the spectrum is given by the algebraic equation $\sum_j N_j^{(1)}/(\beta E_j - \lambda) = 1/\alpha$, and the gap is bounded below by roughly $\sqrt{P}$; that gap bound sets $T_{\rm AQO} \sim 1/P$. The same subspace guarantees importance sampling at all times. The counting step is carried by the capture-recapture estimator $P \approx M(M-1)\langle R_M\rangle/(2(M-\langle Q_M\rangle))$, derived from truncated moments of the measured distinct-state count $Q_M$ and total weight $R_M$.

What would settle it

Substitute the paper's own expectations $\langle R_M\rangle = M P_2/P$ and $M - \langle Q_M\rangle \approx M(M-1)P_2/(2P^2)$ into Eq. (31). If the result is $P \approx M$ rather than $P$, the estimator is inconsistent with the derivation and the protocol as written fails to return the weighted count.

Watch

Extended reading notes

Core claim

The central claim is that replacing the usual transverse-field mixer with the rank-one projector $-|\psi(0)\rangle\langle\psi(0)|$ forces the evolution to stay in a symmetric subspace in which each ground state's amplitude remains proportional to the square root of its weight. As a result, after evolving to the ground-state manifold, computational-basis measurements are an importance sample of the weighted ground states, and a capture-recapture analysis of repeated measurements estimates the total weighted count $P$ with specified relative error and confidence. The paper derives an analytic AQO runtime $\sim 1/P$, finds numerically that QAOA's per-iteration depth scales as $1/\sqrt{P}$, and concludes that for small total ground-state weight QAOA's total time is sub-quadratically better than optimal Monte Carlo, while AQO is not.

Load-bearing premise

The load-bearing premise is that the capture-recapture estimator in Eq. (31) recovers the total weighted count from the measured number of distinct ground states and their total weight; if that estimator is inconsistent with the derivation, the counting protocol collapses.

Editorial extensions

If this is right

For edge-cover instances with small total weight on ground states, the total number of one- and two-qubit gates in the QAOA protocol grows with graph size more slowly than OMCS's CPU time, giving a sub-quadratic speedup at fixed error and confidence.
The importance-sampling property holds throughout the evolution, not only at the final time, so the same circuits can be stopped early or used for weighted sampling tasks beyond counting.
Because $\exp(-i\beta \hat H_z)$ can be implemented with polynomially many gates for Hamiltonians outside NP, the counting method reaches problems where Grover-oracle-based amplitude estimation cannot be applied.
The number of experimental repetitions needed for the statistical estimate scales as $\sqrt{|\ln\delta|}/\epsilon$ times $\sqrt{P_2/P^2}$, which is more favorable in $\epsilon$ and $\delta$ than classical OMCS's $|\ln\delta|/(P\epsilon^2)$.
If the QAOA variational parameters are nearly constant, as observed for many edge-cover instances, the parameter-search overhead can be $O(1)$ and the speedup survives; a greedy per-step search with overhead $T_{\rm QAOA}^2$ would erase it.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A direct substitution of the paper's own expectation values into the capture-recapture estimator $P \approx M(M-1)\langle R_M\rangle/(2(M-\langle Q_M\rangle))$ yields $P \approx M$ rather than $P$, which suggests the estimator as written is inconsistent; a corrected estimator using higher moments of $Q_M$ or a different ratio would be needed to make the protocol self-consistent.
The observed near-constancy of the optimal QAOA angles suggests a transferable-parameter heuristic: optimize $\alpha,\beta$ once on small instances and reuse them on larger graphs of the same family; this is not tested in the paper but is a natural consequence of the numerical trend.
The symmetric-subspace construction applies to any weight function, so the same machinery could estimate other ground-state moments $P_\mu$ for $\mu>1$ by reweighting, which the paper does not pursue.
For graph families where $P$ is classically computable in polynomial time, the reported speedup would not translate to practical advantage; the paper's claim matters most for #P-hard counting instances, where no efficient classical exact algorithm is known.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague —

Read arXiv:1908.01745. Bottom line: the core importance-sampling idea for AQO and QAOA is genuinely new and mostly well argued, but the paper’s central counting estimator is algebraically wrong, and the error breaks the main claim.

What it does well: The modification with Hx = −|ψ(0)⟩⟨ψ(0)| and initial state |ψ(0)⟩ restricts the evolution to a symmetric subspace in which the instantaneous wave function satisfies |⟨ψ(t)|g⟩|² / |⟨ψ(t)|g′⟩|² = w(g)/w(g′) for all ground states. The spectrum derivation leading to TAQO ~ 1/P is a real generalization of earlier Grover-oracle results, and the numerical QAOA scaling TQAOA ~ 1/√P is clearly presented. The edge-cover example is well chosen, and the paper is honest that AQO has no speedup.

Soft spots: The counting step doesn’t work as written. From the paper’s own Eqs. (29)–(30), ⟨R_M⟩ = M P₂/P and M − ⟨Q_M⟩ ≈ M(M−1)P₂/(2P²). Substituting into Eq. (31) gives P_est ≈ M P, not P. The correct inversion is P ≈ (M−1)⟨R_M⟩/[2(M−⟨Q_M⟩)], without the extra M. Since Algorithm 3 uses Eq. (31) directly, the reported estimate is too large by a factor equal to the number of ground-state measurements in the regime where the truncation is valid. This voids the relative-error guarantee in Eq. (6). Eq. (34) has a separate error: inverting Eq. (33) gives T_count ∝ P/√P₂, not √P₂/P. That inverts the weight-moment dependence and understates the counting overhead when P₂/P² < 1, which is exactly the regime where they claim a speedup. Because Table 1 and Fig. 1 compute total time from this estimator, the QAOA speedup comparison inherits both errors. The estimator looks fixable—remove the factor M and redo the T_count derivation—and the importance-sampling part may be salvageable, but the paper as submitted does not establish its main result.

The citation pattern looks appropriate; the distinction from Refs. [71–74] is clear and fair. This paper is for anyone working on quantum counting or constrained sampling algorithms. It deserves a serious referee, not a desk reject, because the construction is novel and the failure is a correctable algebraic error rather than a fundamentally wrong approach. But it should be rejected in its current form and revised. I wouldn’t cite the current version.

Referee Report

3 major / 3 minor

Summary. The paper presents modified adiabatic quantum optimization (AQO) and quantum approximate optimization (QAOA) protocols whose instantaneous wave function importance-samples the ground states of a classical spin Hamiltonian, i.e., |⟨g|ψ(t)⟩|² ∝ w(g). The authors then estimate the total weighted ground-state count P by repeated measurements and a classical capture-recapture analysis. They derive an analytical scaling for AQO, observe numerically T_QAOA ∼ 1/√P, and compare the total time against classical OMCS, claiming that AQO is not faster than OMCS while QAOA offers a sub-quadratic speedup for small-weight ground states. The concrete application is counting weighted edge covers on graphs.

Significance. The core idea—choosing the mixing Hamiltonian as a projector onto the initial state so that the symmetric subspace importance-samples ground states with prescribed weights—is elegant and potentially useful. The AQO spectral analysis in Sec. 3.2 appears sound and generalizes earlier results beyond Grover-type oracles. If the counting protocol and complexity claims were correct, the work would be a meaningful step toward NISQ-compatible ground-state counting. However, the central counting estimator and the reported complexity scaling contain algebraic errors that invalidate the main quantitative claims as written.

major comments (3)

[Sec. 3.4, Eq. (31)] Equation (31) does not follow from Eqs. (29) and (30). Substituting ⟨R_M⟩ = M P_2/P and M − ⟨Q_M⟩ ≈ M(M−1)P_2/(2P^2) into Eq. (31) gives P_est ≈ M·P, not P. The correct inversion is P ≈ (M−1)⟨R_M⟩/[2(M−⟨Q_M⟩)]. Because Algorithm 3 uses Eq. (31) verbatim, every reported estimate is too large by the number of ground-state measurements M, and the relative-error/confidence guarantee in Eq. (6) is void. This is the load-bearing step of the counting protocol, so the algorithm as written does not estimate P.
[Sec. 3.4, Eq. (34) and Table 1] Equation (34) has the P_2 dependence inverted. With S ∼ O(1), Eq. (33) gives M ∼ (√|ln δ|/ε)·P/√P_2, hence T_count ∼ M/(1−η²) ∝ P/√P_2 = √(P²/P_2). The printed expression √(P_2/P²) is the reciprocal. Table 1 and the total-time comparisons in Figs. 1(b)–(d) inherit this error, so the claimed speedups and the statement that AQO is slower than OMCS are not supported by the derived scaling.
[Appendix B, Eq. (B.1)] Equation (B.1) uses Mε as the half-width of the acceptance interval for Q_M, whereas the subsequent derivation and Eq. (32) require the half-width (M−⟨Q_M⟩)ε, as used in Eq. (B.2). As written, the confidence calculation is internally inconsistent; this should be corrected and the resulting S scaling re-derived.

minor comments (3)

[Algorithm 3, Step 5] In the 'if Q_M = M' branch, the instruction 'Go to Step 3' creates an infinite loop; it should read 'Go to Step 2' so that additional ground states are collected after M is doubled.
[Sec. 4, Fig. 1 caption] The comparison of physical CPU time for OMCS with a scaled gate count for QAOA is understandable, but the text should state clearly that constant factors are arbitrary and that the plotted 'total time' for QAOA excludes all classical post-processing and variational search overhead.
[Sec. 3.3] The claim of a sub-quadratic speedup relies on the assumption that constant variational parameters can be found with O(1) search cost; the authors explicitly note this does not hold for all instances, so the generality of the speedup remains an unproven empirical observation rather than a demonstrated result.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found: the AQO time bound and QAOA scaling are derived from the stated evolution, spectral analysis, and measurement statistics, not from the target count P.

full rationale

Walking the derivation chain: the target state |ψ_target⟩ is defined with normalization 1/√P, but P is not used as an input to the evolution; the initial state and H_x depend only on the known weight function w(g), and the importance-sampling property is proved from closure of the symmetric subspace rather than assumed. The AQO bound TAQO is derived analytically from the adiabatic theorem and an explicit spectral analysis of H_S(α,β), with Eq. (27) following from E0=0, E1=1, and Em−1=|V|; no parameter is fitted to the count P. The QAOA scaling TQAOA ∼ 1/√P is explicitly presented as a numerical observation (Fig. 4 and Table 1 caption: 'The scaling quoted for QAOA is found numerically'), and the variational angles are optimized against the ground-state occupation ⟨ψ|P_G|ψ⟩, not against the final count P, so the scaling is not a disguised fit of the target quantity. The capture-recapture estimator in Eq. (31) is inferred from the measured moments ⟨R_M⟩ and ⟨Q_M⟩; it does not insert the target P into the estimator, and no fitted parameter is renamed as a prediction. The algebraic inconsistency flagged in the skeptic headline (the apparent extra factor of M in Eq. (31), and the claimed mismatch in Eq. (34)) is a correctness issue, not a circularity: the estimator is not defined in terms of the target result. Self-citations [7,77] appear only in the engineering-reliability motivation and are not load-bearing for the algorithm or its complexity claims. Therefore no circular step is present, and the derivation is self-contained against external benchmarks.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The central scaling results rest on the adiabatic theorem and on the numerical observation for QAOA. The counting method additionally relies on the capture-recapture identities in Eq. (29), but the derived estimator Eq. (31) and the complexity formula Eq. (34) contain algebraic errors. No new physical entities or forces are introduced.

free parameters (3)

QAOA variational angles alpha_j, beta_j = instance-dependent; example alpha=0.78*pi, beta=0.12*pi
The QAOA circuit uses angle sequences optimized to maximize ground-state occupation. The claimed speedup assumes these angles are nearly constant and can be found in O(1) time, which is not proven for all instances.
eta (allowed ground-state infidelity) = arbitrary, e.g. 0.2 or 0.5 in numerics
User-chosen threshold defining when the evolved state is considered close enough to the ground-state space. It affects prefactors but not the leading scaling.
dt (discrete AQO time step) = 0.1 in numerical simulations
Trotter step size used in the discrete-time AQO simulation. The authors state the scaling is independent of dt for small enough dt.

assumptions (6)

standard math Adiabatic theorem as stated in Eq. (12)-(13) guarantees final state overlap with the ground-state space when the evolution is slow enough.
Invoked in Sec. 3.2 to justify that the final state lies in the ground-state space. The operator-norm condition is used to derive the T_AQO bound.
standard math Central limit theorem applies to sample means of Q_M and R_M for sufficiently large S.
Used in Appendix B to derive the confidence interval in Eq. (32). This is standard for large sample sizes.
domain assumption The weight function w is a normalized probability distribution over all computational basis states, and all ground-state weights are nonnegative.
Required for the interpretation of P as a weighted count and for the importance-sampling construction. Stated in Sec. 2.
domain assumption For the edge-cover problem, the ground-state energy is E0=0 and the first excited energy is E1=1, so the gap assumption E1-E0 = O(1) holds.
Used to simplify the AQO bound to Eq. (27). This is specific to the edge-cover Hamiltonian in Eq. (4).
ad hoc to paper QAOA variational parameters can be chosen constant across time steps with negligible search cost T_alpha_beta_search ~ O(1).
Explicitly assumed in Sec. 3.3 and Sec. 4 to obtain the sub-quadratic speedup. The authors note that the greedy search costs T^2_QAOA and gives no speedup.
ad hoc to paper The numerically observed scaling T_QAOA ~ 1/sqrt(P) holds asymptotically for large graphs and generalizes beyond the simulated ensembles.
Extrapolated from simulations on linear, grid, and random graphs. This is an empirical assumption, not a proven theorem.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A quantum algorithm to count weighted ground states of classical spin Hamiltonians." pith.science (2026). https://pith.science/paper/LVH53GZD

@misc{pith2026190801745,
  author       = {Pith},
  title        = {Pith review of: A quantum algorithm to count weighted ground states of classical spin Hamiltonians},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LVH53GZD}},
  note         = {Machine review of arXiv:1908.01745}
}

read the original abstract

Ground state counting plays an important role in several applications in science and engineering, from estimating residual entropy in physical systems, to bounding engineering reliability and solving combinatorial counting problems. While quantum algorithms such as adiabatic quantum optimization (AQO) and quantum approximate optimization (QAOA) can minimize Hamiltonians, they are inadequate for counting ground states. We modify AQO and QAOA to count the ground states of arbitrary classical spin Hamiltonians, including counting ground states with arbitrary nonnegative weights attached to them. As a concrete example, we show how our method can be used to count the weighted fraction of edge covers on graphs, with user-specified confidence on the relative error of the weighted count, in the asymptotic limit of large graphs. We find the asymptotic computational time complexity of our algorithms, via analytical predictions for AQO and numerical calculations for QAOA, and compare with the classical optimal Monte Carlo algorithm (OMCS), as well as a modified Grover's algorithm. We show that for large problem instances with small weights on the ground states, AQO does not have a quantum speedup over OMCS for a fixed error and confidence, but QAOA has a sub-quadratic speedup on a broad class of numerically simulated problems. Our work is an important step in approaching general ground-state counting problems beyond those that can be solved with Grover's algorithm. It offers algorithms that can employ noisy intermediate-scale quantum devices for solving ground state counting problems on small instances, which can help in identifying more problem classes with quantum speedups.

Figures

Figures reproduced from arXiv: 1908.01745 by the authors.

**Figure 1.** (Color online) Importance-sampling of ground states in AQO, and the scaling of total computational time for QAOA and OMCS. (a) Demonstration that the instantaneous wave function in AQO importance-samples the ground states of Hˆ z in Eq. (4). Solid lines plot |hg|ψ(t)i|2 , for all the ground states of Hˆ z encoding the edge cover problem for the paw graph—shown in the panel and described in [PITH_FULL_IMAGE:figures/… view at source ↗

**Figure 3.** Quantum circuits to prepare the initial quantum state and implement one discrete quantum evolution step, for the paw graph shown in (a). (a) Circuit to prepare the initial state |ψ(0)i [in Eq. (9)] for the weight function in Eq. (5), when the input state is |00 · · ·i. U = exp(−iσy sin−1 √q) is a one-qubit unitary operator. Preparing |ψ(0)i for more general weight functions is non-trivial. (b) Implementation of the … view at source ↗

**Figure 4.** (Color online) The number of discrete AQO steps TAQO/dt and the number of QAOA steps TQAOA in a numerical simulation of these algorithms, until the system reaches desired ground state occupation hψ(T)|Pˆ G|ψ(T)i = 1 − η 2 . (a) TAQO/dt (black squares) and TQAOA (blue circles) required to reach 1 − η 2 = 0.8, for q = sin2 (0.3π) on linear graphs. These two curves scale the same way with the system size as 1/P (black … view at source ↗

Figures from the paper (1 more)

**Figure 5.** Figure 5: (Color online) (a) The variationally optimized αj and βj in QAOA, and (b) the instantaneous projection hψ(j)|Pˆ G|ψ(j)i, for the random graph shown in the inset in (b). The points show the numerical results for α opt j and β opt j obtained from greedy optimization, whi…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

92 extracted references · 59 canonical work pages

[1]

Li W, Van Beek P and Poupart P 2006 Performing incremental Bayesian inference by dynamic model counting Proceedings of the National Conference on Artiﬁcial Intelligence vol 21 (Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999) p 1173

2006
[2]

Chavira M and Darwiche A 2008 Artif. Intell. 172 772–799

2008
[3]

Sang T, Beame P and Kautz H A 2005 Performing Bayesian inference by weighted model counting AAAI vol 5 pp 475–481

2005
[4]

Littman M L, Majercik S M and Pitassi T 2001 J. Automat. Reason. 27 251–296

2001
[5]

Davies J and Bacchus F 2007 Using more reasoning to improve# SAT solving Proceedings of the national conference on artiﬁcial intelligence vol 22 (Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999) p 185

2007
[6]

ICAPS pp 243–252

Domshlak C and Hoﬀmann J 2006 Fast probabilistic planning through weighted model counting. ICAPS pp 243–252

2006
[7]

Paredes R, Due˜ nas-Osorio L, Meel K S and Vardi M Y 2019 Reliab. Eng. Syst. Safe. 191 106472 ISSN 0951-8320 URL http://www.sciencedirect.com/science/article/pii/ S0951832018305209

2019
[8]

Khazaei J and Powell W B 2018 Energ. Syst. 9 277–303

2018

Show all 92 references

[9]

Weaver S A, Ray K J, Marek V W, Mayer A J and Walker A K 2014 Journal on Satisﬁability, Boolean Modeling and Computation 8 129–148

2014
[10]

Douglass A, King A D and Raymond J 2015 Constructing sat ﬁlters with a quantum annealer International Conference on Theory and Applications of Satisﬁability Testing (Springer) pp 104–120

2015
[11]

Azinovi´ c M, Herr D, Heim B, Brown E and Troyer M 2017 SciPost Phys. 2 013

2017
[12]

Biere A, Heule M and van Maaren H 2009 Handbook of satisﬁability vol 185 (IOS press)

2009
[13]

Kumar T K 2002 A model counting characterization of diagnoses Tech. rep. Stanford Univ CA Knowledge Systems Lab

2002
[14]

Today 59 24

Moessner R and Ramirez A P 2006 Phys. Today 59 24

2006
[15]

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

1986
[16]

Castellani T and Cavagna A 2005 J. Stat. Mech.: Theory E. 2005 P05012

2005
[17]

Balents L 2010 Nature 464 199

2010
[18]

Sadoc J F and Mosseri R 2006 Geometrical frustration (Cambridge University Press)

2006
[19]

Farhi E, Goldstone J, Gutmann S and Sipser M 2000 arXiv preprint quant-ph/0001106 A quantum algorithm to count weighted ground states of classical spin Hamiltonians 21

2000 arXiv
[20]

Informatics and Applications 45 99–116

de Falco D and Tamascelli D 2011 RAIRO-Theor. Informatics and Applications 45 99–116

2011
[21]

Farhi E, Goldstone J and Gutmann S 2014 arXiv preprint arXiv:1412.6062

2014 arXiv
[22]

Farhi E, Goldstone J and Gutmann S 2014 arXiv preprint arXiv:1411.4028

2014 arXiv
[23]

Venegas-Andraca S E, Cruz-Santos W, McGeoch C and Lanzagorta M 2018 Contemp. Phys. 59 174–197

2018
[24]

Das A and Chakrabarti B K 2005 Quantum annealing and related optimization methods vol 679 (Springer Science & Business Media)

2005
[25]

Santoro G E and Tosatti E 2006 J. Phys. A: Math. Gen. 39 R393

2006
[26]

Das A and Chakraborti B K 2008 Rev. Mod. Phys. 80 1061

2008
[27]

Albash T and Lidar D A 2018 Rev. Mod. Phys. 90 015002

2018
[28]

Finnila A B, Gomez M A, Sebenik C, Stenson C and Doll J D 1994 Chem. Phys. Lett. 219 343–348

1994
[29]

Kadowaki T and Nishimori H 1998 Phys. Rev. E 58 5355

1998
[30]

Santoro G E, Martoˇ n´ ak R, Tosatti E and Car R 2002Science 295 2427–2430
[31]

Cohen E and Tamir B 2015 Eur. Phys. J. Special Topics 224 89–110

2015
[32]

Albash T and Lidar D A 2018 Phys. Rev. X 8 031016

2018
[33]

Muthukrishnan S, Albash T and Lidar D A 2016 Phys. Rev. X 6 031010

2016
[34]

Hen I, Job J, Albash T, Ronnow T F, Troyer M and Lidar D A 2010 Phys. Rev. A 92 042325

2010
[35]

Denchev V S, Boixo S, Isakov S V, Ding N, Babbush R, Smelyanskiy V, Matrinis J M and Neven H 2016 Phys. Rev. X 6 031015

2016
[36]

Mandra S, Zhu Z, Wang W, Perdomo-Ortiz A and Katzgraber H G 2016 Phys. Rev. A 94 022337

2016
[37]

Farhi E and Harrow A W 2016 arXiv preprint arXiv:1602.07674

2016 arXiv
[38]

Zhou L, Wang S T, Choi S, Pichler H and Lukin M D 2018 arXiv preprint arXiv:1812.01041

2018 arXiv
[39]

Crooks G E 2018 arXiv preprint arXiv:1811.08419

2018 arXiv
[40]

Harrow A and Napp J 2019 arXiv preprint arXiv:1901.05374

2019 arXiv
[41]

Guerreschi G G and Smelyanskiy M 2017 arXiv preprint arXiv:1701.01450

2017 arXiv
[42]

Gily´ en A, Arunachalam S and Wiebe N 2019 Optimizing quantum optimization algorithms via faster quantum gradient computation Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Society for Industrial and Applied Mathematics) pp 1425– 1444

2019
[43]

Hadﬁeld S, Wang Z, O’Gorman B, Rieﬀel E G, Venturelli D and Biswas R 2019 Algorithms 12 34

2019
[44]

Peruzzo A, McClean J, Shadbolt P, Yung M H, Zhou X Q, Love P J, Aspuru-Guzik A and O’brien J L 2014 Nat. Commun. 5 4213

2014
[45]

Kokail C, Maier C, van Bijnen R, Brydges T, Joshi M K, Jurcevic P, Muschik C A, Silvi P, Blatt R, Roos C F and Zoller P 2019 Nature 569 355

2019
[46]

Pagano G, Bapat A, Becker P, Collins K S, De A, Hess P W, Kaplan H B, Kyprianidis A, Tan W L, Baldwin C, Brady L T, Deshpande A, Lui F, Jordan S, Gorshkov A V and Monroe C 2019 arXiv preprint arXiv:1906.02700

2019 arXiv
[47]

Moll N, Barkoutsos P, Bishop L S, Chow J M, Cross A, Egger D J, Filipp S, Fuhrer A, Gambetta J M, Ganzhorn M and Kandala A 2018 Quant. Sci. Tech. 3 030503

2018
[48]

Wecker D, Hastings M B and Troyer M 2016 Phys. Rev. A 94 022309

2016
[49]

Wecker D, Hastings M B and Troyer M 2015 Phys. Rev. A 92 042303

2015
[50]

Verdon G, Broughton M and Biamonte J 2017 arXiv preprint arXiv:1712.05304

2017 arXiv
[51]

Verdon G, Arrazola J M, Br´ adler K and Killoran N 2019 arXiv preprint arXiv:1902.00409

2019 arXiv
[52]

Hastings M B 2019 arXiv preprint arXiv:1905.07047

2019 arXiv
[53]

Wang Z, Rubin N C, Dominy J M and Rieﬀel E G 2019 arXiv preprint arXiv:1904.09314

2019 arXiv
[54]

Wang Z, Hadﬁeld S, Jiang Z and Rieﬀel E G 2018 Phys. Rev. A 97 022304

2018
[55]

Morales M E S, Tlyachev T and Biamonte J 2018 Phys. Rev. A 98 062333

2018
[56]

Mbeng G B, Fazio R and Santoro G 2019 arXiv preprint arXiv:1906.08948

2019 arXiv
[57]

Parrish R M, Iosue J T, Ozaeta A and McMahon P L 2019 arXiv preprint arXiv:1904.03206

2019 arXiv
[58]

Niu M Y, Lu S and Chuang I L 2019 arXiv preprint arXiv:1905.12134

2019 arXiv
[59]

Campbell E, Khurana A and Montanaro A 2019 Quantum 3 167 A quantum algorithm to count weighted ground states of classical spin Hamiltonians 22

2019
[60]

Akshay V, Philathong H, Morales M E S and Biamonte J 2019 arXiv preprint arXiv:1906.11259

2019 arXiv
[61]

Shaydulin R, Safro I and Larson J 2019 arXiv preprint arXiv:1905.08768

2019 arXiv
[62]

Bapat A and Jordan S 2018 arXiv preprint arXiv:1812.02746

2018 arXiv
[63]

Guerreschi G G and Matsuura A Y 2019 Sci. Rep. 9 6903

2019
[64]

Boixo S, Albash T, Spedalieri F M, Chancellor N and Lidar D A 2013 Nat. Commun. 4 2067

2013
[65]

K¨ onz M S, Mazzola G, Ochoa A J, Katzgraber H G and Troyer M 2018 arXiv preprint arXiv:1806.06081

2018 arXiv
[66]

Phys.: Conf

Matsuda Y, Nishimori H and Katzgraber H G 2009 J. Phys.: Conf. Series 143 012003

2009
[67]

King A D, Hoskinson E, Lanting T, Andriyash E and Amin M H 2016 Phys. Rev. A 93 052320

2016
[68]

Mandra S, Zhu Z and Katzgraber H G 2017 Phys. Rev. Lett. 118 070502

2017
[69]

Zhang B H, Wagenbreth G, Martin-Mayor V and Hen I 2017 Sci. Rep. 7 1044

2017
[70]

Katzgraber H G 2018 Quant. Sci. Tech. 3 030505

2018
[71]

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

2009
[72]

Hen I 2014 J. Phys. A: Math. Theor. 47 235304

2014
[73]

Van Dam W, Mosca M and Vazirani U 2001 How powerful is adiabatic quantum computation? Proceedings 2001 IEEE International Conference on Cluster Computing (IEEE) pp 279–287

2001
[74]

Roland J and Cerf N J 2002 Phys. Rev. A 65 042308

2002
[75]

Grover L K 1997 Phys. Rev. Lett. 79 325

1997
[76]

Akbari S and Oboudi M R 2013 Eur. J. Comb. 34 297–321

2013
[77]

Due˜ nas-Osorio L, Vardi M Y and Rojo J 2018 Struct. Saf. 75 110–118

2018
[78]

Karp R M and Luby M 1983 Monte-carlo algorithms for enumeration and reliability problems 24th Annual Symposium on Foundations of Computer Science (sfcs 1983) (IEEE) pp 56–64

1983
[79]

Dagum P, Karp R, Luby M and Ross S 2000 SIAM J. Comput. 29 1484–1496

2000
[80]

Brassard G, Høyer P and Tapp A 1998 Quantum counting International Colloquium on Automata, Languages, and Programming (Springer) pp 820–831

1998
[81]

Brassard G, Hoyer P, Mosca M and Tapp A 2002 Contemp. Math. 305 53–74

2002
[82]

Wie C R 2019 arXiv preprint 1907.08119

2019 arXiv
[83]

Aaronson S, Kothari R, Kretschmer W and Thaler J 2019 arXiv preprint arXiv:1904.08914

2019 arXiv
[84]

Grover L K 1998 Phys. Rev. Lett. 80 4329

1998
[85]

Zio E 2009 Reliab. Eng. Syst. Safe. 94 125–141

2009
[86]

Barenco A, Bennett C H, Cleve R, DiVincenzo D P, Margolus N, Shor P, Sleator T, Smolin J A and Weinfurter H 1995 Phys. Rev. A 52 3457

1995
[87]

Saeedi M and Pedram M 2013 Phys. Rev. A 87 062318

2013
[88]

from the French by G M Temmer (North-Holland)

Messiah A 1964 Quantum Mechanics; Trans. from the French by G M Temmer (North-Holland)

1964
[89]

Seber G A F 1973 Griﬃn, London

1973
[90]

Seber G A F 1986 Biometrics 267–292

1986
[91]

Lucas A 2014 Front. Phys. 2 5

2014
[92]

2019 Qiskit: An open-source framework for quantum computing Appendix Appendix A

Aleksandrowicz G et al. 2019 Qiskit: An open-source framework for quantum computing Appendix Appendix A. Proof of Eq. (29) Here, we derive expressions for⟨QM⟩ and⟨RM⟩. Conditioned on a measurement yielding a ground state, the probability of measuring |g⟩ is w(g)/P. Then the av...

2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Li W, Van Beek P and Poupart P 2006 Performing incremental Bayesian inference by dynamic model counting Proceedings of the National Conference on Artiﬁcial Intelligence vol 21 (Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999) p 1173

2006

[2] [2]

Chavira M and Darwiche A 2008 Artif. Intell. 172 772–799

2008

[3] [3]

Sang T, Beame P and Kautz H A 2005 Performing Bayesian inference by weighted model counting AAAI vol 5 pp 475–481

2005

[4] [4]

Littman M L, Majercik S M and Pitassi T 2001 J. Automat. Reason. 27 251–296

2001

[5] [5]

Davies J and Bacchus F 2007 Using more reasoning to improve# SAT solving Proceedings of the national conference on artiﬁcial intelligence vol 22 (Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999) p 185

2007

[6] [6]

ICAPS pp 243–252

Domshlak C and Hoﬀmann J 2006 Fast probabilistic planning through weighted model counting. ICAPS pp 243–252

2006

[7] [7]

Paredes R, Due˜ nas-Osorio L, Meel K S and Vardi M Y 2019 Reliab. Eng. Syst. Safe. 191 106472 ISSN 0951-8320 URL http://www.sciencedirect.com/science/article/pii/ S0951832018305209

2019

[8] [8]

Khazaei J and Powell W B 2018 Energ. Syst. 9 277–303

2018