Pith. sign in

REVIEW 3 major objections 5 minor 18 references

Towards Tensor-Network SAT-Solvers for Quantum-Classical Workflows

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

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

Pith's one-line read The paper claims that quadratisation from PUBO to QUBO is not a neutral transformation: auxiliary variables and pairwise couplings substantially degrade Max-3-SAT solution quality, while simulated annealing matches or outperforms DMRG acros

desk verdict Useful empirical baseline, but the quadratisation-harm conclusion needs sensitivity analysis and metadata before the broader claims can hold. read the letter →

arxiv 2608.02041 v1 pith:DPGZ2SLH submitted 2026-08-03 quant-ph

Benjamin Zec , Lukas Schmidbauer , Maja Franz , Wolfgang Mauerer This is my paper · ORCID
classification quant-ph
keywords Max-3-SATDMRGtensornetworksQUBOPUBOquadratisationsimulatedannealingHPC/QCintegration
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

Integrated HPC/QC systems need classical surrogates for quantum tasks, and this paper asks whether tensor-network ground-state search can serve as one for combinatorial optimisation. Using Max-3-SAT as a benchmark, it compares two compilation paths: a native higher-order Ising Hamiltonian (PUBO) and a quadratised quadratic Ising Hamiltonian (QUBO), both optimised by DMRG with simulated annealing as baseline. The paper claims that quadratisation is not a neutral step: the auxiliary variables and pairwise couplings it introduces substantially degrade solution quality and reliability relative to the native representation, while SA matches or outperforms DMRG on every tested instance. The reason offered is that SAT optima are classical product states, so DMRG's ability to capture entanglement gives no advantage here. The upshot is that surrogate selection in hybrid runtimes must be encoding- and instance-aware.

What carries the argument

The two-site DMRG algorithm optimises a matrix product state ansatz to minimise the energy of a matrix product operator encoded Ising Hamiltonian. The comparison hinges on two MPO constructions: one from the native degree-3 PUBO polynomial of Max-3-SAT and one from the degree-2 QUBO obtained by LSR quadratisation, which inserts auxiliary variables and pairwise couplings. The benchmark's control is a classical simulated-annealing baseline run on the same Ising models.

What would settle it

Run the identical benchmark on the same Max-3-SAT instances using LSR with p=0 or a different quadratisation scheme; if median QUBO deviation drops to near-zero and matches PUBO, then the encoding-degradation claim fails as stated.

Watch

Extended reading notes

Core claim

The central discovery is that the end-to-end transformation path matters more than the solver. On uniform random Max-3-SAT instances, converting the problem to QUBO via LSR with p=1 yields median ground-state deviations that grow from below 1% to 10-15% as the variable count grows past 12, whereas the PUBO encoding keeps deviations near zero across the entire tested range. SA matches or slightly beats DMRG in the quadratic encoding, and the gap widens with instance size; DMRG never exploits entanglement because the ground states are product states. The paper concludes that representing SAT as a quadratic Ising model is a poor surrogate choice when a native higher-order Ising formulation is a

Load-bearing premise

The entire QUBO-degradation conclusion rests on one quadratisation algorithm (LSR) at one parameter value (p=1); if other reductions produce better-conditioned quadratic forms, the observed gap may not be intrinsic to quadratisation.

Editorial extensions

If this is right

  • In a hybrid HPC/QC runtime, fallback and surrogate decisions should be made per encoding and per instance, not by solver type alone.
  • For Max-3-SAT, the native PUBO/Ising pipeline should be preferred over the quadratised QUBO pipeline when tensor-network solvers are used.
  • Simulated annealing, not DMRG, is the empirically better classical surrogate for this problem class.
  • Quadratisation overhead, not solver weakness, dominates the observed quality loss; improving DMRG implementations will not remove it.

Reading between the lines

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

  • The paper does not test this, but the encoding-dependence result suggests that compiler pipelines for quantum optimisation should expose representation choice as a tunable parameter for schedulers, not as a hidden implementation detail.
  • A direct extension would be Max-4-SAT or weighted Max-3-SAT, where quadratisation overhead grows and might either amplify or reverse the observed gap; the paper leaves that open.
  • Because the tested optima are classical product states, genuinely entangled ground-state problems remain a plausible regime where DMRG's bond-dimension advantage could reappear; the paper does not establish that.
  • If the result transfers to other NP-hard optimisation problems, it argues for benchmarking entire transformation chains before committing HPC/QC runtimes to one encoding.
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.

Referee Report

3 major / 5 minor

Summary. The paper addresses hybrid HPC/QC system design by evaluating classical tensor-network surrogates for quantum optimisation tasks. It compares two pipelines for solving Max-3-SAT: a native PUBO-to-Ising encoding and a QUBO-to-Ising encoding produced by the LSR quadratisation algorithm with parameter p=1. Both are represented as MPOs and optimised with a vanilla two-site DMRG, with simulated annealing as a classical baseline. Across random instances with 4-22 variables and 30-150 clauses, the authors measure deviation from the exact ground state and runtime over 100 randomised solver trials. The results show that the QUBO encoding leads to markedly larger median deviations that grow with instance size, while the PUBO encoding remains near zero; SA is consistently faster and at least as accurate as DMRG. The authors conclude that quadratisation is not a neutral transformation step and that surrogate selection in HPC/QC runtimes must be encoding- and instance-aware.

Significance. If robust, the empirical finding that quadratisation harms solution quality in tensor-network solvers would be practically important: it would caution against blind use of QUBO transformations in hybrid quantum-classical workflows and would justify encoding-aware runtime decisions. The paper is commendable for providing a reproduction package, using exact ground states for small n, and running 100 randomised trials per instance with both encodings corrected for Ising constants. The main weakness is that the generality of the conclusion rests on a single quadratisation parameter (p=1) and on unstated instance counts, which limits the strength of the claims as they currently stand.

major comments (3)
  1. [Section IV-C] The central claim that quadratisation degrades solution quality is based exclusively on LSR with p=1. The paper itself notes that p trades off the number of auxiliary variables against interaction-graph density; p=1 produces the densest QUBO interaction graph, which is the most unfavourable configuration for MPO bond dimensions and DMRG convergence. Without testing p=0 or intermediate values, or an independent quadratisation method, the headline conclusion may be an artifact of this parameter choice rather than a general property of quadratisation. Please add a sensitivity analysis over p (or at least p=0) and, if the degradation persists, report it; if not, restrict the conclusion to LSR p=1.
  2. [Section IV-A/Figure 2] The number of independently generated Max-3-SAT instances per (n,m) configuration is not stated. Figure 2 reports medians, interquartile ranges, and outliers, but no sample size is given. Since the empirical comparison is the core contribution, this information is essential to judge statistical reliability and reproducibility. Please specify the number of instances per configuration and, if feasible, release the instance set.
  3. [Section IV-C/IV-E] The manuscript does not state whether the LSR quadratisation is exact (i.e., whether penalty terms are introduced to enforce consistency between auxiliary and original variables) or how the 'Ising constant' correction accounts for the added auxiliary variables. If the QUBO Hamiltonian admits spurious states with energies below the legal-assignment optimum, the reported deviation against the PUBO ground state is not a valid measure of solver quality. Please clarify the equivalence proof or reference and describe the correction in detail.
minor comments (5)
  1. [Abstract] Typo: 'DMRGs advantages dont' should read 'DMRG's advantages don't'.
  2. [Section II] Grammar: 'Our notations follows' should be 'Our notation follows'.
  3. [Section IV-C] The sentence 'As each additional introduced variable doubles the search space, we fix p=1 in our automated pipeline used in our experiments' is redundant; consider simplifying to 'we fix p=1'.
  4. [Figure 2] The PUBO and QUBO panels use different y-axis scales (e.g., [0,2] vs [0,20]), which may visually exaggerate the difference. Please use a consistent scale or note the change in the caption.
  5. [References] Reference [8] is formatted as 'L. Schmidbauer et al.' with a missing space after the author name in the text; also check other references for formatting consistency.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper reports an empirical benchmark; the central comparison is not an input to itself.

full rationale

The paper's claim that quadratisation degrades solution quality is an empirical observation from running DMRG and SA on Max-3-SAT instances encoded via PUBO and via LSR-quadratised QUBO. No equation in the paper defines or fits a quantity in terms of the outcome it predicts. The LSR algorithm and parameter p=1 come from the authors' prior work, but they are used as a fixed tool, not fitted to the benchmark results, and no theorem from the prior work is invoked to explain away the observed degradation. The self-citations to [8,10] are bibliographic pointers to the transformation method and to parameter/path relations; they are not load-bearing in the sense of supplying the conclusion. The potential weakness that p=1 may not represent all quadratisation methods is a generality/robustness limitation, not a circularity: the paper does not claim to have tested all quadratisations, and its empirical data are independent of its conclusions. Therefore the derivation chain is self-contained and the circularity score is 0.

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

The paper introduces no new physical entities. It relies on established tensor-network formalism, the correctness of the LSR quadratisation from the authors' prior work, and the feasibility of brute-force exact minima as background assumptions.

free parameters (1)
  • LSR parameter p = 1
    Chosen by hand in Section IV-C to minimize the number of auxiliary variables; the paper does not sweep p, so conclusions about quadratisation quality rest on a single trade-off point.
assumptions (3)
  • domain assumption DMRG finds the best MPS approximation to the ground state within the allowed bond dimension when sweeps converge.
    Variational property of DMRG, Section II-B, used to justify comparing DMRG solutions to the exact ground state.
  • domain assumption The LSR quadratisation is an exact reduction: the optimal value of the QUBO with auxiliary variables equals the optimal value of the original PUBO after constant correction.
    Assumed from prior work [8]. Section IV-C uses LSR to build the QUBO; no independent verification is given.
  • domain assumption The exact global minimum is computable by exhaustive enumeration for n up to 22.
    Used in Section IV-E to compute deviation; the 2^n enumeration is feasible but not described in detail.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Towards Tensor-Network SAT-Solvers for Quantum-Classical Workflows." pith.science (2026). https://pith.science/paper/DPGZ2SLH

@misc{pith2026260802041,
  author       = {Pith},
  title        = {Pith review of: Towards Tensor-Network SAT-Solvers for Quantum-Classical Workflows},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DPGZ2SLH}},
  note         = {Machine review of arXiv:2608.02041}
}
read the original abstract

Integrated HPC/QC systems aim to combine classical high-performance computing with quantum processors, but cannot be reduced to mechanisms for dispatching quantum kernels. An integrated architecture must support aspects such as observability, which cannot be implemented using QPUs alone, as well as fallback execution and cost-aware decisions on whether to replace quantum tasks with classical surrogates. Such mechanisms must be approximate or benefit from problem structure to soften the inescapable exponential classical worst-case complexity. In this work, we study tensor-network ground-state search, as such a surrogate, for optimisation problems. This combines key quantum primitives with advanced classical simulation. It provides initial empirical indicators for surrogate selection criteria, and exposes end-to-end toolchain effects that may be missed when transformation steps are studied in isolation. We compare a native polynomial unconstrained optimisation to-higher-order-Ising and a quadratised quadratic unconstrained binary optimization to-quadratic-Ising formulation for Max-3-SAT. Both are encoded as matrix product operator and optimised using density matrix renormalisation group approaches, with simulated annealing (SA) as classical performance baseline. Our results show that quadratisation is not a neutral transformation step: auxiliary variables and pairwise couplings substantially degrade solution quality relative to the native higher-order representation, while SA matches or outperforms DMRG across all tested instances. Since the optima of Boolean satisfiability (SAT)-derived problems are classical product states, DMRGs advantages dont materialise here. These findings suggest that surrogate selection in HPC/QC runtimes must be encoding- and instance-aware and provide empirical groundwork for informed decisions on fallback strategies and architecture co-design.

Figures

Figures reproduced from arXiv: 2608.02041 by the authors.

Figure 1
Figure 1. We benchmark two transformation paths: MAX [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Optimisation performance of SA (green) and DMRG (yellow), grouped by number of SAT variables n and clause count m. Upper panels show runtime per instance: SA is consistently faster and DMRG scales with n in both encodings, where outliers reflect instances with increased bond dimension χ, driving up contraction cost. Lower panels show deviation from the ground state: the PUBO encoding keeps deviations near zero throu… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references

  1. [1]

    Arute, K

    F. Arute, K. Arya, R. Babbush, et al., Quantum supremacy using a programmable superconducting processor,Nature, 2019

    2019

  2. [2]

    E. T. Campbell, B. M. Terhal, and C. Vuillot, Roads towards fault- tolerant universal quantum computation,Nature, 2017

    2017

  3. [3]

    Elsharkawy, X.-T

    A. Elsharkawy, X.-T. M. To, P. Seitz, et al., Integration of quantum accelerators with high performance computing—a review of quantum programming tools,ACM TQC, 2025

    2025

  4. [4]

    E. Kaya, J. Echavarria, M. N. Farooqi, et al., A software platform to support disaggregated quantum accelerators, inSC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE, 2024

    2024

  5. [5]

    Schulz, M

    M. Schulz, M. Ruefenacht, D. Kranzlmuller, et al., Accelerating hpc with quantum computing: It is a software challenge too,Computing in Science and Engineering, 2022

    2022

  6. [6]

    Ramsauer and W

    R. Ramsauer and W. Mauerer, Towards system-level quantum- accelerator integration, inQCE, IEEE, 2025

    2025

  7. [7]

    Schollw ¨ock, The density-matrix renormalization group in the age of matrix product states,Annals of Physics, 2011

    U. Schollw ¨ock, The density-matrix renormalization group in the age of matrix product states,Annals of Physics, 2011

    2011

  8. [8]

    Schmidbauer, E

    L. Schmidbauer, E. Lobe, I. Schaefer, et al., It’s quick to be square: Fast quadratisation for quantum toolchains,ACM TQC, 2026

    2026

Show all 18 references
  1. [9]

    Gabor, M

    T. Gabor, M. L. Rosenfeld, C. Linnhoff-Popien, et al., How to approximate any objective function via quadratic unconstrained binary optimization, inSANER, IEEE, 2022

    2022

  2. [10]

    Schmidbauer and W

    L. Schmidbauer and W. Mauerer, Sat strikes back: Parameter and path relations in quantum toolchains, inQSW, IEEE, 2025

    2025

  3. [11]

    J. D. Biamonte, Nonperturbative k-body to two-body commuting conversion hamiltonians and embedding problem instances into ising spins,Physical Review A, 2008

    2008

  4. [12]

    Gabor, S

    T. Gabor, S. Zielinski, S. Feld, et al., Assessing solution quality of 3sat on a quantum annealing platform, inQuantum Technology and Optimization Problems. Springer International Publishing, 2019

    2019

  5. [13]

    R. Levy, E. Solomonik, and B. K. Clark, Distributed-memory dmrg via sparse and dense parallel tensor contractions, inSC20: Interna- tional Conference for HPC, Netw., Storage and Analysis, IEEE, 2020

    2020

  6. [14]

    Delgado and P

    A. Delgado and P. Date, Defining quantum-ready primitives for hybrid hpc-qc supercomputing: A case study in hamiltonian simulation, Frontiers in Computer Science, 2025

    2025

  7. [15]

    Thelen and W

    S. Thelen and W. Mauerer, Predict and conquer: Navigating algorithm trade-offs with quantum design automation, inQCE, IEEE, 2025

    2025

  8. [16]

    Thelen, H

    S. Thelen, H. Safi, and W. Mauerer, Approximating under the influence of quantum noise and compute power, inQCE, IEEE, 2024

    2024

  9. [17]

    Rovara, L

    D. Rovara, L. Burgholzer, and R. Wille, A framework for debugging quantum programs, inQSW, IEEE, 2025

    2025

  10. [18]

    Greiwe, T

    F. Greiwe, T. Kr ¨uger, and W. Mauerer, Effects of imperfections on quantum algorithms: A software engineering perspective, inQSW, IEEE, 2023

    2023

Pith tools

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