Pith. sign in

REVIEW 4 major objections 5 minor 64 references

Pauli Correlation Encoding (PCE), a quantum heuristic, admits fully classical realisations in which every encoded correlation is polynomial-time computable; these dequantised versions match or beat a quantum PCE baseline on four benchmarks.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-01 09:57 UTC pith:D2VSRWDX

load-bearing objection Solid, worthwhile: two new classically simulable PCE constructions with honest benchmarks; the IQP-PCE efficiency claim is loosely supported on inverse-precision scaling but nothing fatal. the 4 major comments →

arxiv 2607.20409 v1 pith:D2VSRWDX submitted 2026-07-22 quant-ph

Efficiently Simulable Pauli Correlation Encoding

Daniele Lizzio Bosco , Gabriel Matos , Chen-Yu Liu , Frederic Rapp , Fabian Finger , Enrico Rinaldi , Konstantinos Meichanetzidis This is my paper
classification quant-ph
keywords Pauli Correlation Encodingfree-fermionic circuitsmatchgatesIQP circuitsdequantisationbinary optimisationclassical simulabilitycombinatorial optimisation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Pauli Correlation Encoding (PCE) is a heuristic framework for binary optimisation that encodes each classical variable in the sign of a Pauli expectation value on a small quantum register; the paper's project is to show that the whole pipeline—training, decoding, repair, local search—can run classically in polynomial time when the ansatz and observables form a compatible pair. It instantiates this with free-fermionic PCE (FF-PCE, matchgate circuits read out through the Majorana covariance matrix) and IQP-PCE (commuting X-rotations with Z-word observables), and argues that PCE is therefore best understood as a correlation-based optimisation framework with both quantum and dequantised realisations. A sympathetic reader would care because this gives a dequantised baseline: a quantum PCE implementation must beat these classically simulable versions, not just generic classical solvers. Empirically, the simulable variants deliver approximation ratios above 0.96 on many MaxCut and Max3SAT instances, scale to thousands of variables, and match or beat a linear-entangling quantum PCE baseline under a fixed optimisation budget. The paper itself notes that the IQP-PCE efficiency claim relies on a fixed-precision runtime bound for the classical estimator; if that bound worsens sharply with inverse precision, IQP-PCE would not meet the paper's own Definition 1.

Core claim

The central claim is that efficiently simulable Pauli Correlation Encoding exists, in the precise sense of Definition 1: a classical algorithm that, for every encoded Pauli observable and every inverse-polynomial precision, outputs an estimate of the expectation value in polynomial time in the number of qubits and the inverse precision. The paper instantiates this with two compatible ansatz–observable pairs. In free-fermionic PCE, the ansatz is a matchgate circuit implementing a fermionic Gaussian unitary, and the encoded variables are the upper-triangular entries of the 2n×2n Majorana covariance matrix, which evolves as M = O M0 O^T and is read out in O(n^3) classical operations. In IQP-PCE

What carries the argument

The load-bearing mechanism is the notion of a compatible ansatz–observable pair: efficient simulability is not a property of the circuit family alone, but of the pair consisting of the parameterised ansatz and the chosen Pauli encoding. For FF-PCE, the machinery is the Majorana covariance matrix M_pq = -i/2 ⟨[γ_p,γ_q]⟩, propagated as M = O M0 O^T with O ∈ SO(2n), whose entries are exactly the quadratic Pauli observables; this yields a quadratic qubit compression and an O(n^3) classical update. For IQP-PCE, the machinery is the algebra of commuting X generators plus the Van den Nest estimator, which evaluates Z-word expectations in classical polynomial time (as used in the IQPopt framework);

Load-bearing premise

For IQP-PCE, the claim of polynomial-time simulability rests on the unverified assumption that the Van den Nest estimator for Z-word expectation values runs in time polynomial in the inverse precision for every parameter setting and every encoded observable; the paper only cites a fixed-precision linear scaling, and Definition 1 demands inverse-polynomial precision, so if the runtime grows badly with 1/epsilon, IQP-PCE would not meet its own definition.

What would settle it

Measure the wall-clock time of the Van den Nest/IQPopt estimator for an n-qubit IQP circuit and a single-qubit Z word at additive precisions epsilon = 10^-k for increasing k (e.g., k = 1..6) and fixed n; if the time grows faster than any polynomial in 1/epsilon, or if a concrete family of circuits and observables requires exponential-in-n time to reach inverse-polynomial precision, the efficient-simulability claim for IQP-PCE fails its Definition 1.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Quantum PCE implementations must now be benchmarked against these dequantised baselines; a practical quantum advantage has to beat FF-PCE and IQP-PCE on solution quality or time-to-solution, not just generic classical solvers.
  • The same PCE pipeline—encoding, relaxed loss, sign decoding, repair, local search—works unchanged with classically computed correlations, so hybrid refinements like warm-starting a quantum ansatz with FF-PCE parameters become natural next tests.
  • The performance gap between IQP-PCE's strong MaxCut results and its weak MIS and MDKP results shows that the alignment of the correlation model with problem structure matters more than raw ansatz expressivity.
  • Because FF-PCE reads variables directly from a fermionic Gaussian covariance matrix, all higher-order correlations are fixed by Wick's theorem; the benchmark results indicate that these two-point correlations already carry substantial optimisation-relevant structure.
  • The Gset experiments (up to 5000 nodes) show that classically simulable PCE variants achieve approximation ratios of 0.97–0.99 on most uniform and skew instance classes, comparable to or better than the quantum PCE results reported in earlier work.

Where Pith is reading between the lines

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

  • I would extend the paper's dequantisation argument to other expectation-based variational heuristics (e.g., QAOA-style ansätze, VQE-like loops): any parameterised family whose gates and observables form a classically tractable pair should be compared at equal footing with its quantum version, not only against classical solvers.
  • A testable prediction of the paper's framing is that even simpler simulable ansätze—Clifford circuits, constant-depth circuits, or tensor-network states—may also give usable PCE correlations on MaxCut and similar problems; a systematic 'simulability hierarchy' would map where quantum expressivity actually starts to matter.
  • The IQP-PCE weakness on constrained problems suggests that its 1-encoding plus graph-structured generators cannot natively represent cardinality or objective-vs-feasibility tradeoffs; an all-to-all or higher-weight encoding might recover some of that, which could be probed by re-running MDKP with a problem-adapted generator set.
  • The paper's own warm-start suggestion could be turned into a decisive experiment: train FF-PCE or IQP-PCE classically, then add one non-simulable layer and see if the optimisation quality improves beyond what the simulable part already reaches; if not, the practical headroom for quantum PCE is small.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper introduces 'efficiently simulable Pauli Correlation Encoding' (PCE), a classical variant of the PCE quantum optimisation framework. In standard PCE, binary variables are decoded from signs of Pauli expectation values; the authors replace the generic quantum ansatz with two circuit families whose relevant expectation values can be computed classically: free-fermionic (matchgate) circuits (FF-PCE) and IQP circuits (IQP-PCE). A formal definition (Definition 1, Sec. III A) requires that, for every inverse-polynomial precision, all encoded Pauli expectations be computable in polynomial time in n and 1/epsilon. FF-PCE is implemented via Majorana covariance-matrix propagation with O(n^3) cost per loss evaluation. IQP-PCE is claimed to be efficient via the Van den Nest estimator as used in Ref. [20] (Sec. III.C.b). The paper reports benchmarks on MaxCut, Maximum Independent Set, Multi-Dimensional Knapsack, and Max3SAT, with sizes up to thousands of variables, and compares against a linear-entangling PCE baseline. The main conclusion is that PCE is a correlation-based optimisation framework with both quantum and dequantised realisations, and that quantum PCE should be benchmarked against such simulable baselines.

Significance. If the central formal claim — that both FF-PCE and IQP-PCE satisfy Definition 1 — is correct, the paper provides a useful dequantised baseline for PCE, analogous to free-fermion and IQP dequantisations in other variational settings. The FF-PCE construction is mathematically clean, with an explicit covariance-matrix algorithm and a clear quadratic compression. The benchmark suite is broad (four NP-hard problem families plus a LABS appendix), and the paper is commendably explicit about the empirical nature of its performance claims and about the role of local search. The formal Definition 1 is a valuable contribution in itself. However, the IQP-PCE side of the central claim rests on a single cited estimator whose precision dependence is not established in this manuscript, and the numerical evaluation has methodological caveats (hyperparameter tuning on MaxCut, heuristic reference optima, and a resource-unmatched baseline comparison). These issues are fixable in revision, but they currently prevent the paper from fully supporting its stated conclusion.

major comments (4)
  1. [Sec. III.A (Def. 1) and Sec. III.C.b] Definition 1 requires, for every inverse-polynomial precision epsilon=1/poly(n), a classical algorithm running in poly(n,1/epsilon) and achieving error <= epsilon. The support for IQP-PCE is only Sec. III.C.b, which states that Z-word expectations can be estimated to inverse-polynomial precision in classical polynomial time, but then quotes Ref. [20] only for fixed-precision scaling O(m(n+r)). No runtime dependence on 1/epsilon is derived or cited, so the manuscript does not establish that IQP-PCE meets Def. 1. The implementation description in Appendix A2.b ('estimated with 1000 shots') suggests a fixed-precision estimator, which would not satisfy the definition for epsilon much smaller than 1/sqrt(1000). Please add an explicit bound on 1/epsilon (or otherwise prove Def. 1), or revise the formal claim to match what is actually demonstrated.
  2. [Appendix A1, Eq. (A2)] The hyperparameters alpha=sqrt(m), beta=m/2 were selected by grid search on the average raw approximation ratio over 4 random MaxCut graphs of size 50 to 200, and then transferred to all problems, including the MaxCut experiments in Sec. IV.A and the Gset experiments in Sec. IV.B. MaxCut performance is therefore in-sample with respect to hyperparameter selection, and the transfer to MIS, MDKP, and Max3SAT is not validated out-of-sample. The text in Appendix D calls these values 'problem-independent', but the evidence does not support that. Please provide out-of-sample hyperparameter selection (e.g., per-problem validation) or a sensitivity analysis showing that the conclusions are robust to the choice of these values.
  3. [Sec. IV.A, Fig. 2] The approximation ratio is defined as the returned value divided by the optimal value of the instance, but the MaxCut reference values are obtained with the Burer-Monteiro heuristic from pymqlib, not with an exact solver. If the heuristic returns a cut below the true optimum, the reported ratios are inflated, and the statement that empirical ratios exceed the Goemans–Williamson bound and the 0.941 hardness threshold is not a valid comparison: those are worst-case guarantees, while the denominator here is a heuristic lower bound on the optimum. Please use exact or best-known reference values, or clearly label the ratios as ratios to a heuristic reference and remove the implicit guarantee comparison.
  4. [Sec. IV.A.c, Fig. 3] The comparison with linear-entangling PCE is not resource-matched. Table I shows that for n=200, the linear PCE baseline uses 8 qubits and 822 gates, while IQP-PCE uses 200 qubits and 300 gates, and FF-PCE uses 11 qubits and 462 gates. The baseline is also trained with COBYLA (10,000 iterations) while the proposed models use Adam with a two-stage budget. The sentence 'for a fixed optimisation procedure (e.g., loss evaluation), the different models perform similarly' is not supported, as neither the procedure nor the resources are fixed. Please either match the optimisation protocol and resource counts, or rephrase the conclusion to acknowledge that the comparison is at fixed solution-quality level only, not at fixed cost.
minor comments (5)
  1. [Sec. III.B.b] The set I_n used to assign variables to covariance observables is not defined. Please specify which pairs (p_a,q_a) are selected, or at least state that any fixed assignment of m pairs to strict-upper-triangular indices works.
  2. [Appendix A2.b] The phrase 'estimated with 1000 shots' in a classically simulable IQP solver is confusing. If these are samples from a classical stochastic estimator, please state this explicitly and explain how the number of shots relates to the precision required by Definition 1.
  3. [Sec. IV.D] The sentence 'FF-PCE obtained for each m/n ratio a better satisfied clause ratio than other heuristic algorithms' overstates the evidence, since the only 'other heuristic' shown in Fig. 6 is the Greedy baseline. Please say 'than the Greedy baseline'.
  4. [Sec. IV.A.a] The comparison of empirical ratios with the Goemans–Williamson 0.878 guarantee and the Håstad 0.941 hardness threshold should be reworded; the empirical ratios are against a heuristic reference, so the worst-case guarantee comparison is not formally meaningful.
  5. [General] No code repository or random seeds are provided. The paper relies on stochastic optimisation with multiple restarts; please include seeds, instance files, or a code link to allow reproduction of Figures 2–8.

Circularity Check

0 steps flagged

No circularity: the dequantised PCE constructions are checked against external classical-simulation results, and the benchmark claims are empirical rather than self-referential.

full rationale

I walked the derivation chain from Definition 1 through the two instantiations and found no step in which a claimed prediction is equal by construction to its input. Definition 1 is a formal criterion, not a derived result; it is applied, not presupposed. FF-PCE satisfies it by standard free-fermion algebra: the encoded variables are entries of the Majorana covariance matrix propagated as M = O M0 O^T with O(n^3) cost, and the ansatz decomposition is supported by external matchgate theory (Refs. 14, 30, 31, 33) even though Ref. 16 is a self-citation. IQP-PCE relies on the Van den Nest estimator as stated in external Refs. 20, 38, 39; the paper's own contribution is the compatible ansatz-encoding pair, not the estimator. The fixed-precision O(m(n+r)) statement in Sec. III.C.b leaves the 1/eps dependence of the runtime unstated relative to Definition 1's poly(n,1/eps) requirement; that is a documentation/verification gap, not circularity, because the target claim is not used to define the runtime. Hyperparameters alpha = sqrt(m), beta = m/2 (Appendix A1) are grid-searched on small MaxCut instances, but the reported quantities are held-out benchmark approximation ratios, not the fitted constants themselves; no fitted parameter is renamed as a prediction. The comparisons with linear-entangling PCE and with GSet, MDKP, and Max3SAT are empirical, and no equation in the paper reduces to its own output. The minor self-citations are not load-bearing: the load-bearing simulation facts are external and independently checkable.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 0 invented entities

The paper's mathematical contribution rests on standard free-fermion/IQP simulation facts; the main free choices are hyperparameters (alpha, beta, lambda) and ansatz layer counts, fit on MaxCut. No new physical entities are introduced.

free parameters (4)
  • alpha = sqrt(m) = sqrt(m)
    Loss relaxation sharpness; selected via grid search on average raw approximation ratio over 4 random MaxCut graphs (sizes 50-200), then applied to all benchmarks (Appendix A1).
  • beta = m/2 = m/2
    Regularisation strength; selected in the same grid search on MaxCut and transferred to all problems (Appendix A1).
  • lambda = 1.5 = 1.5
    Penalty weight for MIS and MDKP feasibility constraints; chosen by hand with no reported tuning procedure (Sec. IV A b, IV C).
  • LFF = 2*nFF = 2*nFF
    Number of matchgate ansatz layers; heuristic choice, not derived (Appendix A2 a). A layer count of n suffices for full fermionic Gaussian expressivity, so this is a tuned hyperparameter.
axioms (5)
  • standard math Fermionic Gaussian unitaries act linearly on Majorana operators and the covariance matrix propagates as M = O M0 O^T.
    Used in Sec. III B to justify FF-PCE's polynomial-time classical evaluation; standard free-fermion theory from Refs. [13-16].
  • standard math All higher-order correlators of a fermionic Gaussian state are determined by the covariance matrix via Wick's theorem, so restricting FF-PCE to quadratic observables loses no independent variable degrees of freedom.
    Sec. III B b; standard result from Refs. [15,34].
  • domain assumption The Van den Nest algorithm (as implemented in iqpopt) estimates IQP Z-word expectation values to inverse-polynomial additive precision in polynomial time, with cost claimed O(m(n+r)) at fixed precision.
    Sec. IIIC b and Def. 1; the paper relies on external implementation/scaling reports [20,39] and does not prove the precision dependence.
  • ad hoc to paper Graph-structured IQP generators (two-body terms on the problem graph) are an effective inductive bias for MaxCut-like objectives; for MDKP all-to-all two-body terms are used.
    Sec. IIIC a; heuristic choice not derived, and the paper's own results show IQP-PCE degrades on MIS/Max3SAT.
  • domain assumption Benchmark reference values are reliable (Gurobi/MaxSAT exact for small instances; Burer-Monteiro/best-known for MaxCut; SAC-94 references).
    Sec. IV; if reference values are stale or heuristic, approximation ratios could be systematically optimistic.

pith-pipeline@v1.3.0-alltime-deepseek · 85 in / 11754 out tokens · 97574 ms · 2026-08-01T09:57:16.642811+00:00 · methodology

0 comments
read the original abstract

Pauli Correlation Encoding (PCE) is a heuristic framework for binary optimisation that encodes classical variables into many-body Pauli observables. While PCE requires fewer qubits than other approaches, it relies on estimating a large number of Pauli expectation values whose signs determine the variables' values, which can incur substantial measurement overhead. Here, we introduce efficiently simulable PCE, a class of dequantised PCE realisations where all expectation values needed can be computed efficiently classically. We instantiate this idea using free-fermionic evolutions, realised by matchgate circuits, and Instantaneous Quantum Polynomial (IQP) circuits. On MaxCut, Maximum Independent Set, Multi-Dimensional Knapsack, and Max3SAT benchmarks, these methods produce high-quality solutions across problem sizes ranging from tens to thousands of variables. Our results show that PCE is naturally understood as a correlation-based optimisation framework with both quantum and classically simulable realisations. This yields a dequantised baseline for evaluating future quantum PCE implementations.

Figures

Figures reproduced from arXiv: 2607.20409 by Chen-Yu Liu, Daniele Lizzio Bosco, Enrico Rinaldi, Fabian Finger, Frederic Rapp, Gabriel Matos, Konstantinos Meichanetzidis.

Figure 1
Figure 1. Figure 1: FIG. 1: Schematic comparison between standard PCE and efficiently simulable PCE. (a) In standard PCE, binary [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: Results on random [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: Comparison between FF-PCE, IQP-PCE, and a linear-entangling PCE baseline on random [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4: Results on selected instances classes from GSet, corresponding to G1-G5, G11-G13, G14-G17, G23, G35, and [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5: Results on the SAC-94 Multi-Dimensional Knapsack Problem benchmark. Instances are grouped by family: [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6: Results over all instances of Max3SAT benchmark [ [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7: Results over all instances of Max3SAT benchmark [ [PITH_FULL_IMAGE:figures/full_fig_p015_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8: Approximate LABS performance measured by the normalised merit factor [PITH_FULL_IMAGE:figures/full_fig_p023_8.png] view at source ↗

discussion (0)

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

Reference graph

Works this paper leans on

64 extracted references · 12 linked inside Pith

  1. [1]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph]

    Pith/arXiv arXiv 2014

  2. [2]

    A. E. Moylett, N. Linden, and A. Montanaro, Quantum speedup of the traveling-salesman problem for bounded- degree graphs, Phys. Rev. A95, 032323 (2017)

    2017

  3. [3]

    Z. Zhou, Y. Du, X. Tian, and D. Tao, Qaoa-in-qaoa: Solving large-scale maxcut problems on small quantum machines, Phys. Rev. Appl.19, 024027 (2023)

    2023

  4. [4]

    Liu and H.-S

    C.-Y. Liu and H.-S. Goan, Hybrid gate-based and an- nealing quantum computing for large-size ising problems (2022), arXiv:2208.03283 [quant-ph]

    Pith/arXiv arXiv 2022

  5. [5]

    Tan, M.-A

    B. Tan, M.-A. Lemonde, S. Thanasilp, J. Tangpanitanon, andD.G.Angelakis,Qubit-efficientencodingschemesfor binary optimisation problems, Quantum5, 454 (2021)

    2021

  6. [6]

    Tilly, H

    J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y. Li, E. Grant, L. Wossnig, I. Rungger, G. H. Booth, and J. Tennyson, The variational quantum eigensolver: A re- view of methods and best practices, Physics Reports986, 1–128 (2022)

    2022

  7. [7]

    Sciorilli, L

    M. Sciorilli, L. Borges, T. L. Patti, D. García-Martín, G. Camilo, A. Anandkumar, and L. Aolita, Towards large-scalequantumoptimizationsolverswithfewqubits, Nature Communications16, 476 (2025)

    2025

  8. [8]

    Wecker, M

    D. Wecker, M. B. Hastings, and M. Troyer, Progress to- wards practical quantum variational algorithms, Phys. Rev. A92, 042303 (2015)

    2015

  9. [9]

    J. R. McClean, J. Romero, R. Babbush, and A. Aspuru- Guzik, The theory of variational hybrid quantum- classical algorithms, New Journal of Physics18, 023023 (2016)

    2016

  10. [10]

    Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Sta- tistical Association58, 13 (1963)

    W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Sta- tistical Association58, 13 (1963)

    1963

  11. [11]

    Majsak, D

    J. Majsak, D. McNulty, and M. Oszmaniec, A simple and efficient joint measurement strategy for estimating fermionic observables and hamiltonians, npj Quantum Information11, 61 (2025)

    2025

  12. [12]

    Alonso, C

    F. Alonso, C. Samprón, J. Veiga, M. M. Juane, and A. Gómez, Benchmark of pauli correlation encoding for different optimisation problems (2026), arXiv:2606.18914 [quant-ph]

    Pith/arXiv arXiv 2026

  13. [13]

    B. M. Terhal and D. P. DiVincenzo, Classical simulation of noninteracting-fermion quantum circuits, Phys. Rev. A65, 032325 (2002)

    2002

  14. [14]

    Jozsa and A

    R. Jozsa and A. Miyake, Matchgates and classi- cal simulation of quantum circuits, Proceedings of the Royal Society A: Mathematical, Physi- 16 cal and Engineering Sciences464, 3089 (2008), https://royalsocietypublishing.org/rspa/article- pdf/464/2100/3089/742753/rspa.2008.0189.pdf

    arXiv 2008

  15. [15]

    Surace and L

    J. Surace and L. Tagliacozzo, Fermionic Gaussian states: an introduction to numerical approaches, SciPost Phys. Lect. Notes , 54 (2022)

    2022

  16. [16]

    Matos, C

    G. Matos, C. N. Self, Z. Papić, K. Meichanetzidis, and H. Dreyer, Characterization of variational quantum algo- rithms using free fermions, Quantum7, 966 (2023)

    2023

  17. [17]

    M. J. Bremner, R. Jozsa, and D. J. Shepherd, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, Proceedings of the Royal Society A: Mathematical, Physical and Engineer- ing Sciences467, 459–472 (2010)

    2010

  18. [18]

    Leontica and D

    S. Leontica and D. Amaro, Exploring the neighborhood of 1-layer qaoa with instantaneous quantum polynomial circuits, Phys. Rev. Res.6, 013071 (2024)

    2024

  19. [19]

    Gince, J.-M

    J. Gince, J.-M. Pagé, M. Armenta, A. Sarkar, and S. Kourtis, Fermionic machine learning, in2024 IEEE In- ternational Conference on Quantum Computing and En- gineering (QCE), Vol. 01 (2024) pp. 1672–1678

    2024

  20. [20]

    Recio-Armengol, S

    E. Recio-Armengol, S. Ahmed, and J. Bowles, Train on classical, deploy on quantum: scaling generative quantum machine learning to a thousand qubits (2026), arXiv:2503.02934 [quant-ph]

    arXiv 2026

  21. [21]

    C.-Y. Liu, L. Placidi, E. Brunner, and E. Rinaldi, Toward generative quantum utility via correlation-complexity map (2026), arXiv:2603.06440 [cs.LG]

    Pith/arXiv arXiv 2026

  22. [22]

    Benchmarking Quantum Machine Learning with MatchCake | PennyLane Blog — penny- lane.ai,https://pennylane.ai/blog/2026/06/ benchmarking-quantum-machine-learning-with-matchcake, [Accessed 12-06-2026]

    2026

  23. [23]

    J. Li, X. Yang, X. Peng, and C.-P. Sun, Hybrid quantum- classical approach to quantum optimal control, Phys. Rev. Lett.118, 150503 (2017)

    2017

  24. [24]

    Mitarai, M

    K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Quan- tum circuit learning, Phys. Rev. A98, 032309 (2018)

    2018

  25. [25]

    Gottesman, The heisenberg representation of quan- tum computers (1998), arXiv:quant-ph/9807006 [quant- ph]

    D. Gottesman, The heisenberg representation of quan- tum computers (1998), arXiv:quant-ph/9807006 [quant- ph]

    Pith/arXiv arXiv 1998

  26. [26]

    Aaronson and D

    S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Phys. Rev. A70, 052328 (2004)

    2004

  27. [27]

    Jordan and E

    P. Jordan and E. Wigner, Über das paulische äquivalen- zverbot, Zeitschrift für Physik47, 631 (1928)

    1928

  28. [28]

    E. Lieb, T. Schultz, and D. Mattis, Two soluble models of an antiferromagnetic chain, Annals of Physics16, 407 (1961)

    1961

  29. [29]

    Chapman and S

    A. Chapman and S. T. Flammia, Characterization of solvable spin models via graph invariants, Quantum4, 278 (2020)

    2020

  30. [30]

    L. G. Valiant, Quantum circuits that can be simulated classically in polynomial time, SIAM J. Comput.31, 1229 (2002)

    2002

  31. [31]

    D’Alessandro, Introduction to quantum control and dynamics (2007)

    D. D’Alessandro, Introduction to quantum control and dynamics (2007)

    2007

  32. [32]

    Knill, Fermionic linear optics and matchgates (2001), arXiv:quant-ph/0108033 [quant-ph]

    E. Knill, Fermionic linear optics and matchgates (2001), arXiv:quant-ph/0108033 [quant-ph]

    Pith/arXiv arXiv 2001

  33. [33]

    Kökcü, D

    E. Kökcü, D. Camps, L. Bassman Oftelie, J. K. Freericks, W. A. de Jong, R. Van Beeumen, and A. F. Kemper, Al- gebraic compression of quantum circuits for hamiltonian evolution, Phys. Rev. A105, 032420 (2022)

    2022

  34. [34]

    G. C. Wick, The evaluation of the collision matrix, Phys. Rev.80, 268 (1950)

    1950

  35. [35]

    S. J. Elman, A. Chapman, and S. T. Flammia, Free fermions behind the disguise, Communications in Math- ematical Physics388, 969 (2021)

    2021

  36. [36]

    Chapman, S

    A. Chapman, S. J. Elman, and R. L. Mann, A uni- fied graph-theoretic framework for free-fermion solvabil- ity (2023), arXiv:2305.15625 [quant-ph]

    Pith/arXiv arXiv 2023

  37. [37]

    G. H. Golub and C. F. Van Loan,Matrix Computations, 4th ed. (Johns Hopkins University Press, 2013)

    2013

  38. [38]

    Nest, Simulating quantum computers with probabilis- tic methods, arXiv preprint arXiv:0911.1624 (2009)

    M. Nest, Simulating quantum computers with probabilis- tic methods, arXiv preprint arXiv:0911.1624 (2009)

    Pith/arXiv arXiv 2009

  39. [39]

    Armengol and J

    E. Armengol and J. Bowles, Iqpopt: Fast optimization of instantaneous quantum polynomial circuits in jax (2026), arXiv:2501.04776 [quant-ph]

    Pith/arXiv arXiv 2026

  40. [40]

    Burer and R

    S. Burer and R. D. C. Monteiro, A nonlinear program- mingalgorithmforsolvingsemidefiniteprogramsvialow- rank factorization, Mathematical Programming95, 329 (2003)

    2003

  41. [41]

    Accessed 2026-07-06

    aboev, pymqlib: Python interface for MQLib, python in- terface for MQLib library including heuristics for combi- natorial optimization. Accessed 2026-07-06

    2026

  42. [42]

    Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual (2026)

    2026

  43. [43]

    D. P. Kingma and J. Ba, Adam: A method for stochastic optimization (2017), arXiv:1412.6980 [cs.LG]

    Pith/arXiv arXiv 2017

  44. [44]

    M. X. Goemans and D. P. Williamson, Improved approx- imation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM42, 1115–1145 (1995)

    1995

  45. [45]

    Håstad, Some optimal inapproximability results, J

    J. Håstad, Some optimal inapproximability results, J. ACM48, 798–859 (2001)

    2001

  46. [46]

    Lucas, Ising formulations of many np prob- lems, Frontiers in PhysicsVolume 2 - 2014, 10.3389/fphy.2014.00005 (2014)

    A. Lucas, Ising formulations of many np prob- lems, Frontiers in PhysicsVolume 2 - 2014, 10.3389/fphy.2014.00005 (2014)

    arXiv 2014

  47. [47]

    Alimonti and V

    P. Alimonti and V. Kann, Some apx-completeness re- sults for cubic graphs, Theor. Comput. Sci.237, 123–134 (2000)

    2000

  48. [48]

    M. J. D. Powell, A direct search optimization method that models the objective and constraint functions by lin- ear interpolation, inAdvances in Optimization and Nu- merical Analysis, edited by S. Gomez and J.-P. Hennart (Springer Netherlands, Dordrecht, 1994) pp. 51–67

    1994

  49. [49]

    Puchinger, G

    J. Puchinger, G. Raidl, and U. Pferschy, The multidi- mensional knapsack problem: Structure and algorithms, INFORMS Journal on Computing22, 250 (2010)

    2010

  50. [50]

    Accessed 2026

    SAC94 Suite: Collection of Multiple Knapsack Problems, CMU Artificial Intelligence Repository (1993), version 13-JUL-93. Accessed 2026

    1993

  51. [51]

    ai/datasets/hamlib-max-3-sat(2026),accessed: 2026- 06-30

    PennyLane, HamLib: Max-3-SAT,https://pennylane. ai/datasets/hamlib-max-3-sat(2026),accessed: 2026- 06-30

    2026

  52. [52]

    N. P. Sawaya, D. Marti-Dafcik, Y. Ho, D. P. Tabor, D. Bernal, A. B. Magann, S. Premaratne, P. Dubey, A. Matsuura, N. Bishop, W. A. de Jong, S. Ben- jamin, O. D. Parekh, N. Tubman, K. Klymko, and D. Camps, Hamlib: A library of hamiltonians for benchmarking quantum algorithms and hardware (2023), arXiv:2306.13126 [quant-ph]

    Pith/arXiv arXiv 2023

  53. [53]

    Ignatiev, A

    A. Ignatiev, A. Morgado, and J. Marques-Silva, Rc2: an efficient maxsat solver, Journal on Satisfiability, Boolean Modeling and Computation11, 53 (2019)

    2019

  54. [54]

    Ignatiev, A

    A. Ignatiev, A. Morgado, and J. Marques-Silva, PySAT: A Python toolkit for prototyping with SAT oracles, in SAT(2018) pp. 428–437

    2018

  55. [55]

    J.-S. Kim, A. McCaskey, B. Heim, M. Modani, S. Stan- 17 wyck, and T. Costa, Cuda quantum: The platform for integrated quantum-classical computing, in2023 60th ACM/IEEE Design Automation Conference (DAC) (2023) pp. 1–4

    2023

  56. [56]

    Sharma and H

    M. Sharma and H. C. Lau, A comparative study of quantum optimization techniques for solving com- binatorial optimization benchmark problems (2025), arXiv:2503.12121 [quant-ph]

    Pith/arXiv arXiv 2025

  57. [57]

    Shaydulin, C

    R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y. Sun, Y. Alexeev, J. M. Dreiling, J. P. Gaebler, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. V. Horst, S. Hu, J. Johansen, M. Math- eny, T. Mengle, M. Mills, S. A. Moses, B. Neyenhuis, P. Siegfried, R. Yalovetzky, and M. Pistoia,...

    2024

  58. [58]

    Sciorilli, G

    M. Sciorilli, G. Camilo, T. O. Maciel, A. Can- abarro, L. Borges, and L. Aolita, A competitive nisq and qubit-efficient solver for the labs problem (2026), arXiv:2506.17391 [quant-ph]. 18 Appendix A: Technical Details Thisappendixsummarisestheimplementationdetailsusedintheexperiments. Allmodelsfollowthesamehigh-level PCE pipeline, based on the information...

    arXiv 2026

  59. [59]

    ThereforeL(reg) acts as smoothness/scale regulariser for the continuous PCE relaxation

    Hyperparameters selection In each experiment, the target loss is of the form L(θ) =f(tanh(α⟨Π⟩)) +βL (reg),(A1) wherefin the target function (including the penalty component in constrained problems), andL(reg) is the regulari- sation loss obtained from 1 m Pm i=1 s2 i 2 .Sinces 2 i is small when the relaxed variable is close to zero and large when it is c...

  60. [60]

    FF-PCEThe matchgate ansatz consists of alternating layers of single-qubitR Z rotations and nearest- neighbourR XX rotations

    Models implementation a. FF-PCEThe matchgate ansatz consists of alternating layers of single-qubitR Z rotations and nearest- neighbourR XX rotations. In the implemented solver, the number of layers is fixed to LFF = 2nFF.(A3) Each layer containsnFF parameters for theRZ rotations andn FF −1parameters for theR XX rotations. Hence the total number of FF-PCE ...

  61. [61]

    All reported solutions are obtained from the decoded expectation signs

    Decoding, repair, and local search. All reported solutions are obtained from the decoded expectation signs. For MaxCut, the decoded partition is scored directly by summing the weights of cut edges. For MIS, the selected set is repaired before scoring: while the set contains an edge with both endpoints selected, one endpoint of the violating edge is remove...

    2000

  62. [62]

    By definition, these are contained in the space of all diagonal unitary matrices in theXbasis

    Number of gates to reach maximum expressivity In this section, we characterise the maximum expressivity of the unitaries generated by the IQP ansatz. By definition, these are contained in the space of all diagonal unitary matrices in theXbasis. Since conjugation byH⊗n mapsXstrings toZstrings, we work in the computational basis throughout this section. We ...

  63. [63]

    For nqubits, the maximum number of variables that can be assigned without algebraic constraints isn

    Maximum number of independent variable assignments When choosing the encoding for the problem variables into Pauli strings for IQP-PCE, one must ensure that the corresponding expectations are not overly constrained (or that such constraints respect those of the problem). For nqubits, the maximum number of variables that can be assigned without algebraic c...

  64. [64]

    They label distinct computational-basis states because ther ℓ are linearly independent: if P ℓ aℓrℓ = P ℓ bℓrℓ, taking the inner product withtj givesa j =b j for everyj. Moreover,Z tj has eigenvalue(−1) aj on the basis state labelled bya, since tj · kX ℓ=1 aℓrℓ ! = kX ℓ=1 aℓδjℓ =a j (mod 2).(E8) It follows that ⟨Ztj ⟩θ = cos2 θj −sin 2 θj = cos(2θj).(E9) ...