pith. sign in

arxiv: 2503.07720 · v2 · submitted 2025-03-10 · 🪐 quant-ph · cond-mat.stat-mech· cs.DS

Counting with the quantum alternating operator ansatz

Julien Drapeau , Shreya Banerjee , Stefanos Kourtis This is my paper

Pith reviewed 2026-05-23 00:01 UTC · model grok-4.3

classification 🪐 quant-ph cond-mat.stat-mechcs.DS
keywords variational quantum algorithmsapproximate countingQAOA#P-hard problems#NAE3SAT#1-in-3SATquantum samplingtensor network simulation
0
0 comments X

The pith

VQCount uses QAOA sampling to approximate #P-hard solution counts with exponentially fewer samples than prior methods.

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

The paper introduces VQCount, a variational algorithm that treats QAOA as a sampler over solution states for hard counting problems. It proves that this approach requires exponentially fewer samples than earlier techniques to reach any desired multiplicative approximation to the exact count. Simulations on small instances of positive #NAE3SAT and positive #1-in-3SAT show that the method can outperform both classical rejection sampling and Grover-based quantum counting by balancing success probability against distribution uniformity. The work therefore positions shallow variational circuits as a practical route to approximate counting on #P-hard instances.

Core claim

By generating samples from a QAOA-prepared distribution and invoking the known equivalence between random sampling and approximate counting, VQCount achieves a multiplicative approximation to the exact solution count of #P-hard problems while using exponentially fewer samples than previous sampling-based approaches; tensor-network simulations confirm that both the standard QAOA and its Grover-mixer variant can realize this gain on synthetic positive #NAE3SAT and positive #1-in-3SAT instances through an observed tradeoff between per-sample success probability and sampling uniformity.

What carries the argument

QAOA acting as a solution sampler that produces a biased distribution over satisfying assignments, combined with the classical equivalence that converts the number of samples needed for multiplicative approximation into a function of the distribution's success probability.

If this is right

  • Arbitrary multiplicative approximation factors become reachable with far fewer total circuit executions than in prior variational or quantum counting schemes.
  • A practical tradeoff exists between QAOA success probability and output uniformity that can be tuned to improve overall counting efficiency.
  • Shallow circuits suffice to demonstrate measurable gains over naive rejection sampling on the tested #P-hard problems.
  • The same sampling-based reduction applies to both the original QAOA mixer and the Grover-mixer variant.

Where Pith is reading between the lines

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

  • The approach may extend to other #P-complete problems whose solution sets admit efficient classical verification once a candidate is drawn.
  • If the observed uniformity-success tradeoff persists at larger scales, hybrid classical post-processing of QAOA samples could become a standard subroutine for approximate enumeration tasks.
  • The exponential sample reduction would remain useful even if the underlying QAOA distribution is only mildly biased, provided the bias stays above a problem-dependent threshold.

Load-bearing premise

A distribution over solutions generated by QAOA can be substituted into the classical sampling-to-counting reduction while still delivering the claimed exponential reduction in sample count.

What would settle it

An explicit family of #NAE3SAT instances for which the number of QAOA samples required to reach a fixed multiplicative error does not decrease exponentially with circuit depth or problem size.

Figures

Figures reproduced from arXiv: 2503.07720 by Julien Drapeau, Shreya Banerjee, Stefanos Kourtis.

Figure 1
Figure 1. Figure 1: An example of the self-reducibility tree in the [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: QAOA solution sampler before (a) and after [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example of the mapping to the Ising model [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: VQCount performance with depth p = 3 QAOA (blue circles) and GM-QAOA (red squares) circuits for NAE3SAT instances at α = 1 (left panels) and α = 2 (right panels). Solid and dotted lines represent the mean and median, respectively. Shaded regions show the standard error of the mean. (a,b) Maximal nonuniformity throughout the self-reduction. The JVV algorithm requires the nonuniformity to be at most O(n −1 )… view at source ↗
Figure 5
Figure 5. Figure 5: Number of post-selected samples needed to [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: VQCount performance as a function of depth [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Impact of fixing qubits throughout the self-reduction on the sampling with depth [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: Number of post-selected samples needed to [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗
Figure 8
Figure 8. Figure 8: Scaling behavior of VQCount with QAOA cir [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 10
Figure 10. Figure 10: Count accuracy obtained by increasing the [PITH_FULL_IMAGE:figures/full_fig_p013_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Number of solutions (a) and sampling efficiency (b) to achieve an error tolerance [PITH_FULL_IMAGE:figures/full_fig_p014_11.png] view at source ↗
read the original abstract

We introduce a variational algorithm based on the quantum alternating operator ansatz (QAOA) for the approximate solution of computationally hard counting problems. Our algorithm, dubbed VQCount, is based on the equivalence between random sampling and approximate counting and employs QAOA as a solution sampler. We first prove that VQCount improves upon previous work by reducing exponentially the number of samples needed to obtain an approximation within an arbitrary small multiplicative factor of the exact count. Using tensor network simulations, we then study the typical performance of VQCount with shallow circuits on synthetic instances of two #P-hard problems, positive #NAE3SAT and positive #1-in-3SAT. We employ the original quantum approximate optimization algorithm version of QAOA, as well as the Grover-mixer variant which guarantees a uniform solution probability distribution. We observe a tradeoff between QAOA success probability and sampling uniformity, which we exploit to achieve an empirical efficiency gain over both naive rejection sampling and Grover-based quantum counting. Our results highlight the potential and limitations of variational algorithms for approximate counting.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The manuscript introduces VQCount, a variational QAOA-based algorithm for approximate counting on #P-hard problems. It claims a proof that the method exponentially reduces the number of samples needed to achieve an arbitrary-small multiplicative approximation to the exact count, by using QAOA as a solution sampler and leveraging the random-sampling/approximate-counting equivalence. Tensor-network simulations on shallow circuits for synthetic positive #NAE3SAT and positive #1-in-3SAT instances compare the standard QAOA and Grover-mixer variants, report a success-probability vs. uniformity tradeoff, and claim empirical efficiency gains over rejection sampling and Grover-based quantum counting.

Significance. If the claimed proof is rigorous and the observed empirical gains hold beyond the synthetic instances, the work would provide a concrete variational route to approximate counting with potential exponential sample-complexity improvement over classical baselines. The explicit comparison of mixer variants and the focus on controlled synthetic benchmarks are strengths; reproducible tensor-network code or parameter-free derivations would further strengthen the contribution.

major comments (2)
  1. [Abstract, §3] Abstract and §3 (proof section): the claimed exponential reduction in samples for arbitrary-small multiplicative approximation requires that a QAOA-generated distribution (even with Grover mixer) can be substituted into the random-sampling/approximate-counting equivalence while preserving the stated factor. The abstract itself notes a tradeoff between success probability and uniformity on shallow circuits; if the proof assumes an ideal or sufficiently uniform sampler whose properties are not guaranteed by the variational optimization for the target #P-hard instances, the exponential improvement does not follow for the regimes studied in the tensor-network simulations.
  2. [§4] §4 (simulation results): the reported efficiency gain over baselines is presented as empirical evidence supporting the approach, yet the central proof claim is independent of these results. Without explicit verification that the observed distributions achieve the multiplicative factor required by the sampling-counting equivalence (e.g., via direct comparison of estimated vs. exact counts on the synthetic instances), the simulations do not corroborate the load-bearing theoretical claim.
minor comments (2)
  1. [§3] Notation for the multiplicative approximation factor and the precise definition of 'arbitrary small' should be introduced with an equation in the proof section for clarity.
  2. [§4] Figure captions for the tensor-network results should explicitly state the circuit depth, number of instances, and error bars to allow direct assessment of the tradeoff.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. We address each major comment below, providing clarifications on the scope of the proof and the role of the simulations.

read point-by-point responses

  1. Referee: [Abstract, §3] Abstract and §3 (proof section): the claimed exponential reduction in samples for arbitrary-small multiplicative approximation requires that a QAOA-generated distribution (even with Grover mixer) can be substituted into the random-sampling/approximate-counting equivalence while preserving the stated factor. The abstract itself notes a tradeoff between success probability and uniformity on shallow circuits; if the proof assumes an ideal or sufficiently uniform sampler whose properties are not guaranteed by the variational optimization for the target #P-hard instances, the exponential improvement does not follow for the regimes studied in the tensor-network simulations.

    Authors: The proof in §3 shows an exponential reduction in the number of samples required for an arbitrary-small multiplicative approximation, provided the sampler satisfies the conditions of the random-sampling/approximate-counting equivalence (specifically, a known or bounded bias relative to the uniform distribution over solutions). For the Grover-mixer variant, uniformity is guaranteed by construction for any choice of variational parameters, so the equivalence applies directly once a non-zero success probability is achieved. The variational optimization then maximizes this success probability, yielding the stated exponential improvement over classical baselines. The tradeoff between success probability and uniformity mentioned in the abstract applies only to the standard QAOA mixer on shallow circuits; it does not affect the Grover-mixer case used to establish the proof. We will revise the abstract and §3 to state these conditions more explicitly and to distinguish the two mixer variants. revision: partial

  2. Referee: [§4] §4 (simulation results): the reported efficiency gain over baselines is presented as empirical evidence supporting the approach, yet the central proof claim is independent of these results. Without explicit verification that the observed distributions achieve the multiplicative factor required by the sampling-counting equivalence (e.g., via direct comparison of estimated vs. exact counts on the synthetic instances), the simulations do not corroborate the load-bearing theoretical claim.

    Authors: The simulations in §4 are presented as an empirical study of typical performance on shallow circuits for the chosen synthetic instances, separate from the theoretical proof. They demonstrate concrete efficiency gains in sampling time relative to rejection sampling and Grover-based quantum counting, arising from the observed success-probability versus uniformity tradeoff. We agree that these results do not include a direct verification that the VQCount-derived estimates achieve the precise multiplicative factor guaranteed by the equivalence on the synthetic instances. In a revised version we will add such a verification (comparing estimated versus exact counts) for the small instances where exact enumeration is feasible, to better connect the empirical results to the theoretical claim. revision: yes

Circularity Check

0 steps flagged

Proof of exponential sample reduction presented as independent; no load-bearing self-citation or definitional reduction in abstract or claims

full rationale

The paper states a proof that VQCount reduces samples exponentially via the random-sampling/approximate-counting equivalence applied to a QAOA sampler, followed by separate tensor-network simulations on #P-hard instances. No quoted equations reduce the claimed multiplicative approximation factor to a fitted parameter, self-citation chain, or ansatz smuggled from prior author work. The equivalence is invoked as an external fact, and the proof is described as improving on previous work without reducing to the simulation results or variational optimization details. This yields a minor score for possible unexamined assumptions in the proof but no exhibited circularity by the required standards.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; the central assumption is the sampling-to-counting equivalence and the effectiveness of QAOA as a sampler. No free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption Equivalence between random sampling and approximate counting allows QAOA output to deliver the claimed multiplicative approximation
    Explicitly stated as the foundation of VQCount in the abstract.

pith-pipeline@v0.9.0 · 5717 in / 1143 out tokens · 38455 ms · 2026-05-23T00:01:41.666820+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages · 3 internal anchors

  1. [1]

    Variational quantum al- gorithms

    M. Cerezo, Andrew Arrasmith, Ryan Bab- bush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. “Variational quantum al- gorithms”. Nature Reviews Physics3, 625– 644 (2021)

    work page 2021

  2. [2]

    Quan- tum annealing initialization of the quantum approximateoptimizationalgorithm

    Stefan H. Sack and Maksym Serbyn. “Quan- tum annealing initialization of the quantum approximateoptimizationalgorithm”. Quan- tum 5, 491 (2021)

    work page 2021

  3. [3]

    Quantum Approxi- mate Optimization with Hard and Soft Con- straints

    Stuart Hadfield, Zhihui Wang, Eleanor G. Rieffel, Bryan O’Gorman, Davide Venturelli, and Rupak Biswas. “Quantum Approxi- mate Optimization with Hard and Soft Con- straints”. In Proceedings of the Second In- ternational Workshop on Post Moores Era Supercomputing. Pages 15–21. (2017)

    work page 2017

  4. [4]

    The computational complexity of linear optics

    Scott Aaronson and Alex Arkhipov. “The computational complexity of linear optics”. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing. Pages 333–342. (2011)

    work page 2011

  5. [5]

    On the com- plexity and verification of quantum random circuit sampling

    Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. “On the com- plexity and verification of quantum random circuit sampling”. Nature Physics15, 159– 163 (2019)

    work page 2019

  6. [6]

    On the hardness of approximate reasoning

    Dan Roth. “On the hardness of approximate reasoning”. Artificial Intelligence82, 273– 302 (1996)

    work page 1996

  7. [7]

    Performing Bayesian inference by weighted model counting

    Tian Sang, Paul Bearne, and Henry Kautz. “Performing Bayesian inference by weighted model counting”. In Proceedings of the 20th National Conference on Artificial Intel- ligence. Volume 1, pages 475–481. (2005)

    work page 2005

  8. [8]

    Hailfinder: A Bayesian system for fore- casting severe weather

    Bruce Abramson, John Brown, Ward Ed- wards, Allan Murphy, and Robert L. Win- kler. “Hailfinder: A Bayesian system for fore- casting severe weather”. International Jour- nal of Forecasting12, 57–71 (1996). 13 101 102 103 Number of solutions NAE3SAT(a) α 1 2 101 4 × 100 6 × 100 2 × 101 1-in-3SAT(b) α 2/3 6 8 10 12 14 16 18 20 Number of variables 101 2 × 100...

    work page 1996

  9. [9]

    The Complexity of Enu- meration and Reliability Problems

    Leslie G. Valiant. “The Complexity of Enu- meration and Reliability Problems”. SIAM Journal on Computing8, 410–421 (1979)

    work page 1979

  10. [10]

    Counting- based reliability estimation for power- transmission grids

    Leonardo Duenas-Osorio, Kuldeep Meel, RogerParedes, andMosheVardi. “Counting- based reliability estimation for power- transmission grids”. In Proceedings of the AAAI Conference on Artificial Intelligence. Volume 31, pages 4488–4494. (2017)

    work page 2017

  11. [11]

    Polynomial-time approximation algo- rithms for the Ising model

    Mark Jerrum and Alistair Sinclair. “Polynomial-time approximation algo- rithms for the Ising model”. SIAM Journal on Computing22, 1087–1116 (1993)

    work page 1993

  12. [12]

    Quantitative Verification of Neural Net- works and Its Security Applications

    Teodora Baluta, Shiqi Shen, Shweta Shinde, Kuldeep S. Meel, and Prateek Saxena. “Quantitative Verification of Neural Net- works and Its Security Applications”. In Pro- ceedings of the 2019 ACM SIGSAC Confer- ence on Computer and Communications Se- curity. Pages 1249–1264. (2019)

    work page 2019

  13. [13]

    Quantum ampli- tudeamplificationandestimation

    Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. “Quantum ampli- tudeamplificationandestimation”. InQuan- tum Computation and Information (Wash- ington, DC, 2000). Volume 305, pages 53–74. Amer. Math. Soc., Providence, RI (2002)

    work page 2000

  14. [14]

    Simpler quantum count- ing

    Chu-Ryang Wie. “Simpler quantum count- ing”. Quantum Information and Computa- tion 19, 0967–0983 (2019)

    work page 2019

  15. [15]

    Quan- tum Approximate Counting, Simplified

    Scott Aaronson and Patrick Rall. “Quan- tum Approximate Counting, Simplified”. In 2020 Symposium on Simplicity in Algo- rithms (SOSA). Pages 24–32. Society for Industrial and Applied Mathematics (2020)

    work page 2020

  16. [16]

    A Fast Quantum Mechani- cal Algorithm for Database Search

    Lov K. Grover. “A Fast Quantum Mechani- cal Algorithm for Database Search”. In Pro- ceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. Pages 212–219. (1996)

    work page 1996

  17. [17]

    A quantum al- gorithm to count weighted ground states of classical spin Hamiltonians

    Bhuvanesh Sundar, Roger Paredes, David T. Damanik, Leonardo Dueñas-Osorio, and Kaden R. A. Hazzard. “A quantum al- gorithm to count weighted ground states of classical spin Hamiltonians” (2019). arXiv:1908.01745

    work page arXiv 2019

  18. [18]

    Grover- 14 QAOA for 3-SAT: Quadratic speedup, fair-sampling, and parameter clustering

    Zewen Zhang, Roger Paredes, Bhuvanesh Sundar, David Quiroga, Anastasios Kyril- lidis, Leonardo Duenas-Osorio, Guido Pagano, and Kaden R A Hazzard. “Grover- 14 QAOA for 3-SAT: Quadratic speedup, fair-sampling, and parameter clustering”. Quantum Science and Technology 10, 015022 (2024)

    work page 2024

  19. [19]

    Random generation of com- binatorial structures from a uniform distri- bution

    Mark R. Jerrum, Leslie G. Valiant, and Vi- jay V. Vazirani. “Random generation of com- binatorial structures from a uniform distri- bution”. Theoretical Computer Science43, 169–188 (1986)

    work page 1986

  20. [20]

    From the Quantum Approximate Optimization Algo- rithm to a Quantum Alternating Operator Ansatz

    Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Ven- turelli, and Rupak Biswas. “From the Quantum Approximate Optimization Algo- rithm to a Quantum Alternating Operator Ansatz”. Algorithms12, 34 (2019)

    work page 2019

  21. [21]

    A Quantum Approximate Optimization Algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A Quantum Approx- imate Optimization Algorithm” (2014). arXiv:1411.4028

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  22. [22]

    Grover Mixers for QAOA: Shifting Com- plexity from Mixer Design to State Prepa- ration

    Andreas Bärtschi and Stephan Eidenbenz. “Grover Mixers for QAOA: Shifting Com- plexity from Mixer Design to State Prepa- ration”. In 2020 IEEE International Confer- ence on Quantum Computing and Engineer- ing (QCE). Pages 72–82. (2020)

    work page 2020

  23. [23]

    Fast counting with tensor networks

    StefanosKourtis, ClaudioChamon, Eduardo Mucciolo, and Andrei E. Ruckenstein. “Fast counting with tensor networks”. SciPost Physics 7, 060 (2019)

    work page 2019

  24. [24]

    Efficient Contrac- tion of Large Tensor Networks for Weighted Model Counting through Graph Decomposi- tions

    Jeffrey M. Dudek, Leonardo Dueñas-Osorio, and Moshe Y. Vardi. “Efficient Contrac- tion of Large Tensor Networks for Weighted Model Counting through Graph Decomposi- tions” (2020). arXiv:1908.04381

    work page arXiv 2020

  25. [25]

    Par- allel Weighted Model Counting with Tensor Networks

    Jeffrey M. Dudek and Moshe Y. Vardi. “Par- allel Weighted Model Counting with Tensor Networks” (2021). arXiv:2006.15512

    work page arXiv 2021

  26. [26]

    Quantum Computation and Quantum In- formation: 10th Anniversary Edition

    Michael A. Nielsen and Isaac L. Chuang. “Quantum Computation and Quantum In- formation: 10th Anniversary Edition”. Cam- bridge University Press. (2011)

    work page 2011

  27. [27]

    Ap- proximate counting, uniform generation and rapidly mixing Markov chains

    Alistair Sinclair and Mark Jerrum. “Ap- proximate counting, uniform generation and rapidly mixing Markov chains”. Information and Computation82, 93–133 (1989)

    work page 1989

  28. [28]

    How Hard is It to Marry at Random? (On the Approximation of the Permanent)

    Andrei Z. Broder. “How Hard is It to Marry at Random? (On the Approximation of the Permanent)”. In Proceedings of the Eigh- teenth Annual ACM Symposium on Theory of Computing. Pages 50–58. (1986)

    work page 1986

  29. [29]

    The Power of Self-Reducibility: Selectivity, Information, and Approximation

    Lane A. Hemaspaandra. “The Power of Self-Reducibility: Selectivity, Information, and Approximation”. In Complexity and Approximation: In Memory of Ker-I Ko. Pages 19–47. Springer InternationalPublish- ing (2020)

    work page 2020

  30. [30]

    Ising formulations of many NP problems

    Andrew Lucas. “Ising formulations of many NP problems”. Frontiers in Physics2 (2014)

    work page 2014

  31. [31]

    Creating superpositions that correspond to efficiently integrable probability distributions

    Lov Grover and Terry Rudolph. “Creating superpositions that correspond to efficiently integrable probability distributions” (2002). arXiv:quant-ph/0208112

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  32. [32]

    Adi- abatic Quantum State Generation and Sta- tistical Zero Knowledge

    Dorit Aharonov and Amnon Ta-Shma. “Adi- abatic Quantum State Generation and Sta- tistical Zero Knowledge”. In Proceedings of the Thirty-Fifth Annual ACM Sympo- sium on Theory of Computing. Pages 20–29. (2003)

    work page 2003

  33. [33]

    Performance upper bound of a Grover-mixer quantum alternat- ing operator ansatz

    Ningyi Xie, Jiahua Xu, Tiejin Chen, Xin- wei Lee, Yoshiyuki Saito, Nobuyoshi Asai, and Dongsheng Cai. “Performance upper bound of a Grover-mixer quantum alternat- ing operator ansatz”. Physical Review A 111, 012401 (2025)

    work page 2025

  34. [34]

    Ground-statestatis- tics from annealing algorithms: Quantum versus classical approaches

    Yoshiki Matsuda, Hidetoshi Nishimori, and HelmutG.Katzgraber. “Ground-statestatis- tics from annealing algorithms: Quantum versus classical approaches”. New Journal of Physics 11, 073021 (2009)

    work page 2009

  35. [35]

    Exponentially Bi- ased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field DrivingHamiltonians

    Salvatore Mandrà, Zheng Zhu, and Hel- mut G. Katzgraber. “Exponentially Bi- ased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field DrivingHamiltonians”. PhysicalReviewLet- ters 118, 070502 (2017)

    work page 2017

  36. [36]

    Fair Sampling Error Analysis on NISQ Devices

    John Golden, Andreas Bärtschi, Daniel O’Malley, and Stephan Eidenbenz. “Fair Sampling Error Analysis on NISQ Devices”. ACM Transactions on Quantum Computing 3, 8:1–8:23 (2022)

    work page 2022

  37. [37]

    The phase transition in 1-in-k SAT and NAE 3- SAT

    Dimitris Achlioptas, Arthur Chtcherba, Gabriel Istrate, and Cristopher Moore. “The phase transition in 1-in-k SAT and NAE 3- SAT”. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algo- rithms. Pages 721–722. (2001)

    work page 2001

  38. [38]

    Phase diagram of the 1- in-3 satisfiability problem

    Jack Raymond, Andrea Sportiello, and Lenka Zdeborová. “Phase diagram of the 1- in-3 satisfiability problem”. Physical Review E 76, 011101 (2007)

    work page 2007

  39. [39]

    Statistical Physics of Hard Optimization Problems

    Lenka Zdeborová. “Statistical Physics 15 of Hard Optimization Problems” (2008). arXiv:0806.4112

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  40. [40]

    Hyper- optimized tensor network contraction

    Johnnie Gray and Stefanos Kourtis. “Hyper- optimized tensor network contraction”. Quantum 5, 410 (2021)

    work page 2021

  41. [41]

    Quimb: A python package for quantum information and many-body calculations

    Johnnie Gray. “Quimb: A python package for quantum information and many-body calculations”. Journal of Open Source Soft- ware 3, 819 (2018)

    work page 2018

  42. [42]

    SciPy 1.0: Fundamental algorithms for sci- entific computing in Python

    Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C. J. Carey, İlhan Polat, Yu Feng, Eric W. ...

    work page 2020

  43. [43]

    GANAK: A Scalable Probabilistic Exact Model Counter

    Shubham Sharma, Subhajit Roy, Mate Soos, and Kuldeep S. Meel. “GANAK: A Scalable Probabilistic Exact Model Counter”. In Pro- ceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19. Pages 1169–1176. (2019)

    work page 2019

  44. [44]

    An Ex- tensible SAT-solver

    Niklas Eén and Niklas Sörensson. “An Ex- tensible SAT-solver”. In Theory and Appli- cations of Satisfiability Testing. Pages 502–

    work page

  45. [45]

    Pre- dicting learnt clauses quality in modern SAT solvers

    Gilles Audemard and Laurent Simon. “Pre- dicting learnt clauses quality in modern SAT solvers”. In Proceedings of the 21st Interna- tional Joint Conference on Artificial Intelli- gence. Pages 399–404. (2009)

    work page 2009

  46. [46]

    PySAT: A Python Toolkit for Prototyping with SAT Oracles

    AlexeyIgnatiev, AntonioMorgado, andJoao Marques-Silva. “PySAT: A Python Toolkit for Prototyping with SAT Oracles”. In The- ory and Applications of Satisfiability Testing – SAT 2018. Pages 428–437. (2018)

    work page 2018

  47. [47]

    Train- ing Variational Quantum Algorithms Is NP-Hard

    Lennart Bittel and Martin Kliesch. “Train- ing Variational Quantum Algorithms Is NP-Hard”. Physical Review Letters 127, 120502 (2021)

    work page 2021

  48. [48]

    Feeding the multitude: A polynomial-time algorithm to improve sampling

    Andrew J. Ochoa, Darryl C. Jacob, Salva- tore Mandrà, and Helmut G. Katzgraber. “Feeding the multitude: A polynomial-time algorithm to improve sampling”. Physical Review E99, 043306 (2019). 16

    work page 2019