pith. sign in

arxiv: 2606.23727 · v1 · pith:N5AZZONZnew · submitted 2026-06-19 · 🪐 quant-ph · cs.DS

Certifying Quantum Optimization and Circuit Cutting by Using Quantum-Classical Moment Duality

Pith reviewed 2026-06-26 13:53 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS
keywords quantum optimizationGoemans-Williamson relaxationSum-of-Squarescircuit cuttingMax-Cutvariational quantum algorithmsmoment matrixPauli correlations
0
0 comments X

The pith

The two-qubit Pauli-Z correlation matrix from any quantum state is always feasible for the classical Goemans-Williamson Max-Cut relaxation.

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

The paper shows that the matrix of two-qubit Pauli-Z correlations extracted from an arbitrary quantum state automatically satisfies the constraints of the classical degree-2 Sum-of-Squares semidefinite program. Because this matrix is therefore a valid input to the Goemans-Williamson relaxation, random-hyperplane rounding of the matrix produces a classical cut whose expected value is guaranteed to be at least the Goemans-Williamson factor times the quantum expectation value of the cut Hamiltonian. The same matrix also encodes the tensor-product structure of the underlying circuit, allowing a polynomial-time procedure that cuts the circuit into smaller pieces while supplying explicit error bounds on the reconstructed observables.

Core claim

Any quantum state ρ yields a two-qubit Pauli-Z moment matrix that lies inside the feasible set of the classical Goemans-Williamson semidefinite relaxation; rounding this matrix therefore certifies an expected cut value E[Cut] ≥ α_GW ⟨H⟩_ρ for every variational state, and the same matrix identifies tensor-product factorizations that permit rigorous circuit cutting.

What carries the argument

The two-qubit Pauli-Z correlation matrix extracted from a quantum state ρ, which is shown to be feasible for the classical Goemans-Williamson SDP relaxation.

If this is right

  • Every variational quantum optimization run on Max-Cut automatically receives a certified classical approximation ratio without requiring convergence to the ground state.
  • The moment matrix supplies a polynomial-time, correlation-based method to cut a quantum circuit into independent subcircuits together with explicit reconstruction error bounds.
  • The certification holds for any state produced by QAOA, VQPM, or any other variational procedure, independent of how close the state is to optimality.

Where Pith is reading between the lines

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

  • Classical SDP solvers could be seeded directly with quantum-estimated moment matrices to obtain hybrid certificates on larger instances.
  • When the quantum state is a product state the moment matrix reduces exactly to the classical relaxation, recovering the standard Goemans-Williamson guarantee as a special case.
  • The same correlation data might be used to certify other classical combinatorial problems whose SDP relaxations share the degree-2 Sum-of-Squares cone.

Load-bearing premise

The two-qubit Pauli-Z correlation matrix constructed from any quantum state lies inside the degree-2 Sum-of-Squares SDP cone.

What would settle it

A single quantum state whose measured two-qubit Pauli-Z correlations violate at least one constraint of the Goemans-Williamson SDP, or a variational run in which the rounded classical cut value is strictly less than α_GW times the observed quantum energy.

Figures

Figures reproduced from arXiv: 2606.23727 by Ammar Daskin.

Figure 1
Figure 1. Figure 1: Left: GW-rounded objective F(γ, β). Middle: QAOA energy EQAOA(γ, β). Right: optimal values. The GW-rounded bound is lower than the energy, yet respects the αGW guarantee. 0 5 10 15 20 25 30 35 Optimization Iterations 1.7 1.8 1.9 2.0 2.1 2.2 Expectation Value (Cut Size) QAOA State Trajectory & SoS Certificate Bounds on C4 GW-Rounded Bound F( , ) QAOA Energy E Analytical Floor GW E [PITH_FULL_IMAGE:figures/… view at source ↗
Figure 2
Figure 2. Figure 2: Continuous optimization trajectory of p=1 QAOA on C4. The GW-rounded cut FGW (blue) stays above the certified lower bound αGWEρ (dashed) at all iterations, even when the raw energy is poor. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: VQPM trajectory for a 12-qubit instance. The GW-rounded cut [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: (a) Scatter plot of the actual 2-norm error against the mutual information [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
read the original abstract

We establish a direct quantum-classical duality based on the degree-$2$ Sum-of-Squares (SoS) semidefinite programming cone: the matrix of two-qubit Pauli-$Z$ correlation functions obtained from \emph{any} quantum state $\rho$ is automatically a feasible point of the classical Goemans-Williamson (GW) relaxation. This observation provides a universal ``safety net'' for quantum optimization algorithms: applying GW random hyperplane rounding to the quantum-driven moment matrix yields a certified expected cut value $\mathbb{E}[\mathrm{Cut}] \ge \alpha_{\mathrm{GW}}\langle\mathcal{H}\rangle_\rho$, valid for every state produced by variational algorithms such as QAOA or the Variational Quantum Power Method (VQPM), regardless of convergence quality. We further show that the same moment matrix reveals the tensor-product structure of the underlying unitary circuit, enabling a polynomial-time, correlation-based circuit cutting procedure with rigorous error bounds. The framework is validated numerically on Max-Cut instances for variational quantum algorithms and on random states for circuit cutting, demonstrating that the cheap two-point correlation data are sufficient to locate near-optimal bipartitions and that the theoretical error bounds hold in practice.

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

0 major / 3 minor

Summary. The manuscript claims a quantum-classical duality based on the degree-2 Sum-of-Squares cone: for any quantum state ρ the two-qubit Pauli-Z correlation matrix C with entries C_ij = Tr(ρ Z_i Z_j) (C_ii=1) is feasible for the Goemans-Williamson SDP relaxation of Max-Cut. Consequently, GW random-hyperplane rounding applied to this matrix certifies E[Cut] ≥ α_GW ⟨H⟩_ρ for every variational state produced by QAOA or VQPM. The same matrix is further asserted to reveal tensor-product structure, enabling a polynomial-time correlation-based circuit-cutting procedure with rigorous error bounds. Numerical experiments on Max-Cut instances and random states are reported to confirm that the two-point data suffice to locate near-optimal bipartitions and that the error bounds hold in practice.

Significance. If the central duality holds, the result supplies a parameter-free, assumption-free certification mechanism that converts any quantum expectation value into a classical approximation guarantee via an off-the-shelf SDP rounding procedure. This is a direct, elementary link between quantum moment matrices and classical SDP relaxations that requires no additional fitting or convergence assumptions. The circuit-cutting application, if rigorously derived from the same matrix, would likewise be a useful byproduct for scalable quantum computation. The elementary positivity argument (x^T C x = Tr(ρ (∑ x_k Z_k)^2) ≥ 0) is a strength that makes the claim robust.

minor comments (3)
  1. [§2] §2 (or wherever the duality is stated): the explicit construction of the moment matrix from the Pauli-Z operators and the verification that it lies in the degree-2 SoS cone should be written out with the quadratic-form identity shown, even if elementary, to make the argument self-contained for readers unfamiliar with SoS.
  2. [circuit cutting section] The circuit-cutting section: the precise mapping from the correlation matrix to a tensor-product decomposition (or bipartition) and the derivation of the polynomial-time error bounds need an explicit algorithm box or pseudocode, together with the dependence of the error on the number of cuts.
  3. [numerical validation] Numerical section: the Max-Cut instances and random-state ensembles should report the distribution of the ratio E[Cut]/⟨H⟩_ρ across instances, not only selected examples, to substantiate the claim that the bounds hold in practice.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, for highlighting the elementary positivity argument, and for recommending minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The central claim is that any two-qubit Pauli-Z correlation matrix C_ij = Tr(ρ Z_i Z_j) (C_ii=1) from an arbitrary state ρ lies in the degree-2 SoS cone because x^T C x = Tr(ρ (∑ x_k Z_k)^2) ≥ 0 for all real x, with SDP objective exactly ⟨H⟩_ρ. This is an elementary positivity fact that directly implies the GW rounding guarantee E[Cut] ≥ α_GW ⟨H⟩_ρ with no fitted parameters, self-definitions, or load-bearing self-citations required. The abstract and skeptic analysis present the construction and duality explicitly as a direct consequence of the SoS membership; the derivation is self-contained against external mathematical benchmarks and exhibits none of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; the central claim rests on the standard properties of the degree-2 SoS cone and the definition of the two-qubit Pauli-Z moment matrix.

axioms (1)
  • standard math Degree-2 Sum-of-Squares SDP cone membership for the Pauli-Z moment matrix
    Invoked in the first sentence of the abstract as the basis for the duality.

pith-pipeline@v0.9.1-grok · 5736 in / 1274 out tokens · 44284 ms · 2026-06-26T13:53:46.812862+00:00 · methodology

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

46 extracted references · 6 linked inside Pith

  1. [1]

    Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995

    Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995

  2. [2]

    Semidefinite programming relaxations for semialgebraic problems.Mathematical pro- gramming, 96(2):293–320, 2003

    Pablo A Parrilo. Semidefinite programming relaxations for semialgebraic problems.Mathematical pro- gramming, 96(2):293–320, 2003

  3. [3]

    Global optimization with polynomials and the problem of moments.SIAM Journal on optimization, 11(3):796–817, 2001

    Jean B Lasserre. Global optimization with polynomials and the problem of moments.SIAM Journal on optimization, 11(3):796–817, 2001

  4. [4]

    Sum-of-squares proofs and the quest toward optimal algorithms.arXiv preprint arXiv:1404.5236, 2014

    Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms.arXiv preprint arXiv:1404.5236, 2014

  5. [5]

    Quantum circuit cutting: Complexity and optimization.arXiv preprint arXiv:2604.23700, 2026

    Yuval Idan, Eitan Zahavi, Elad Mentovich, Eliahu Cohen, and Shmuel Zaks. Quantum circuit cutting: Complexity and optimization.arXiv preprint arXiv:2604.23700, 2026

  6. [6]

    Rounding sum-of-squares relaxations

    Boaz Barak, Jonathan A Kelner, and David Steurer. Rounding sum-of-squares relaxations. InProceed- ings of the forty-sixth annual ACM symposium on Theory of computing, pages 31–40, 2014

  7. [7]

    Bounding the set of quantum correlations

    Miguel Navascu´ es, Stefano Pironio, and Antonio Ac´ ın. Bounding the set of quantum correlations. Physical Review Letters, 98(1):010401, 2007

  8. [8]

    A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations.New Journal of Physics, 10(7):073013, 2008

    Miguel Navascu´ es, Stefano Pironio, and Antonio Ac´ ın. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations.New Journal of Physics, 10(7):073013, 2008

  9. [9]

    Optimizing strongly interacting fermionic hamiltonians

    Matthew B Hastings and Ryan O’Donnell. Optimizing strongly interacting fermionic hamiltonians. In Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, pages 776–789, 2022

  10. [10]

    Field theory and the sum-of-squares for quantum systems.arXiv preprint arXiv:2302.14006, 2023

    Matthew B Hastings. Field theory and the sum-of-squares for quantum systems.arXiv preprint arXiv:2302.14006, 2023

  11. [11]

    Limitations and separations in the quantum sum-of-squares, and the quantum knapsack problem.arXiv preprint arXiv:2402.14752, 2024

    Matthew B Hastings. Limitations and separations in the quantum sum-of-squares, and the quantum knapsack problem.arXiv preprint arXiv:2402.14752, 2024. 16

  12. [12]

    Quantum simulation with sum-of-squares spectral amplification.Physical Review Letters, 136(11):110601, 2026

    Robbie King, Guang Hao Low, Ryan Babbush, Rolando D Somma, and Nicholas C Rubin. Quantum simulation with sum-of-squares spectral amplification.Physical Review Letters, 136(11):110601, 2026

  13. [13]

    Sum-of-squares inspired quantum metaheuristic for polynomial optimization with the hadamard test and approximate amplitude constraints.arXiv preprint arXiv:2408.07774, 2024

    Iria W Wang, Robin Brown, Taylor L Patti, Anima Anandkumar, Marco Pavone, and Susanne F Yelin. Sum-of-squares inspired quantum metaheuristic for polynomial optimization with the hadamard test and approximate amplitude constraints.arXiv preprint arXiv:2408.07774, 2024

  14. [14]

    Quantum entanglement, sum of squares, and the log rank conjecture

    Boaz Barak, Pravesh K Kothari, and David Steurer. Quantum entanglement, sum of squares, and the log rank conjecture. InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 975–988, 2017

  15. [15]

    Relaxations and exact solutions to quantum max cut via the algebraic structure of swap operators.Quantum, 8:1352, 2024

    Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J William Helton, and Igor Klep. Relaxations and exact solutions to quantum max cut via the algebraic structure of swap operators.Quantum, 8:1352, 2024

  16. [16]

    Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut

    Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. In Dimitris Achlioptas and L´ aszl´ o A. V´ egh, editors,Approximation, Ran- domization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 ofLeibniz International Proceedings in Informatics (L...

  17. [17]

    Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms

    Ojas Parekh and Kevin Thompson. Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors,48th Inter- national Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 102:1–1...

  18. [18]

    Optimizing quantum circuit parameters via sdp

    Eunou Lee. Optimizing quantum circuit parameters via sdp. In33rd International Symposium on Algo- rithms and Computation (ISAAC 2022), pages 48–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2022

  19. [19]

    An improved approximation algorithm for quantum max-cut on triangle-free graphs

    Robbie King. An improved approximation algorithm for quantum max-cut on triangle-free graphs. Quantum, 7:1180, 2023

  20. [20]

    An optimal product-state approximation for 2-local quantum hamil- tonians with positive terms.arXiv preprint arXiv:2206.08342, 2022

    Ojas Parekh and Kevin Thompson. An optimal product-state approximation for 2-local quantum hamil- tonians with positive terms.arXiv preprint arXiv:2206.08342, 2022

  21. [21]

    An improved quantum max cut approximation via maximum matching

    Eunou Lee and Ojas Parekh. An improved quantum max cut approximation via maximum matching. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), pages 105–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2024

  22. [22]

    Improved algorithms for quantum maxcut via partially entangled matchings

    Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved algorithms for quantum maxcut via partially entangled matchings. In33rd Annual European Symposium on Algorithms (ESA 2025), pages 101–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2025

  23. [23]

    An su (2)-symmetric semidefinite programming hierarchy for quantum max cut.arXiv preprint arXiv:2307.15688, 2023

    Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin Thompson, and Ojas Parekh. An su (2)-symmetric semidefinite programming hierarchy for quantum max cut.arXiv preprint arXiv:2307.15688, 2023

  24. [24]

    Product-state approximations to quantum states.Com- munications in Mathematical Physics, 342(1):47–80, 2016

    Fernando GSL Brandao and Aram W Harrow. Product-state approximations to quantum states.Com- munications in Mathematical Physics, 342(1):47–80, 2016

  25. [25]

    Quantum goemans-williamson algorithm with the hadamard test and approximate amplitude constraints.Quantum, 7:1057, 2023

    Taylor L Patti, Jean Kossaifi, Anima Anandkumar, and Susanne F Yelin. Quantum goemans-williamson algorithm with the hadamard test and approximate amplitude constraints.Quantum, 7:1057, 2023

  26. [26]

    Variational quantum algorithms for semidefinite programming.Quantum, 8:1374, 2024

    Dhrumil Patel, Patrick J Coles, and Mark M Wilde. Variational quantum algorithms for semidefinite programming.Quantum, 8:1374, 2024

  27. [27]

    Slack-variable approach for variational quantum semidefinite programming.Physical Review A, 112(2):022607, 2025

    Jingxuan Chen, Hanna Westerheim, Zo¨ e Holmes, Ivy Luo, Theshani Nuradha, Dhrumil Patel, Soorya Rethinasamy, Kathie Wang, and Mark M Wilde. Slack-variable approach for variational quantum semidefinite programming.Physical Review A, 112(2):022607, 2025. 17

  28. [28]

    Approximation algorithms for qma-complete problems.SIAM Journal on Computing, 41(4):1028–1050, 2012

    Sevag Gharibian and Julia Kempe. Approximation algorithms for qma-complete problems.SIAM Journal on Computing, 41(4):1028–1050, 2012

  29. [29]

    Quasiprobability decompositions with reduced sampling overhead.npj Quantum Information, 8(1):12, 2022

    Christophe Piveteau, David Sutter, and Stefan Woerner. Quasiprobability decompositions with reduced sampling overhead.npj Quantum Information, 8(1):12, 2022

  30. [30]

    Circuit knitting with classical communication.IEEE Transac- tions on Information Theory, 70(4):2734–2745, 2023

    Christophe Piveteau and David Sutter. Circuit knitting with classical communication.IEEE Transac- tions on Information Theory, 70(4):2734–2745, 2023

  31. [31]

    Circuit cutting with classical side information

    Christophe Piveteau, Lukas Schmitt, and David Sutter. Circuit cutting with classical side information. Physical Review Research, 7(3):033063, 2025

  32. [32]

    Understanding the scalability of circuit cutting techniques for practical quantum applications.arXiv preprint arXiv:2411.17756, 2024

    Songqinghao Yang and Prakash Murali. Understanding the scalability of circuit cutting techniques for practical quantum applications.arXiv preprint arXiv:2411.17756, 2024

  33. [33]

    Patterns for quantum circuit cutting

    Marvin Bechtold, Johanna Barzen, Martin Beisel, Frank Leymann, and Benjamin Weder. Patterns for quantum circuit cutting. InProceedings of the 30th Conference on Pattern Languages of Programs, pages 1–12, 2023

  34. [34]

    A quantum approximate optimization algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014

  35. [35]

    A variational eigenvalue solver on a photonic quantum processor

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Al´ an Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):4213, 2014

  36. [36]

    Quantum approximate optimization algorithm for maxcut: A fermionic view.Physical Review A, 97(2):022304, 2018

    Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approximate optimization algorithm for maxcut: A fermionic view.Physical Review A, 97(2):022304, 2018

  37. [37]

    The quantum approxi- mate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington- kirkpatrick model.arXiv preprint arXiv:2110.14206, 2021

    Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. The quantum approxi- mate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington- kirkpatrick model.arXiv preprint arXiv:2110.14206, 2021

  38. [38]

    Maxcut quantum approximate optimization algorithm performance guarantees for p¿ 1.Physical Review A, 103(4):042612, 2021

    Jonathan Wurtz and Peter Love. Maxcut quantum approximate optimization algorithm performance guarantees for p¿ 1.Physical Review A, 103(4):042612, 2021

  39. [39]

    Combinatorial optimization through variational quantum power method.Quantum Information Processing, 20(10):336, 2021

    Ammar Daskin. Combinatorial optimization through variational quantum power method.Quantum Information Processing, 20(10):336, 2021

  40. [40]

    From theory to practice: Analyzing variational quantum power method for quantum optimization of qubo problems.arXiv preprint arXiv:2505.12990, 2025

    Ammar Daskin. From theory to practice: Analyzing variational quantum power method for quantum optimization of qubo problems.arXiv preprint arXiv:2505.12990, 2025

  41. [41]

    Cambridge university press, 2018

    John Watrous.The theory of quantum information. Cambridge university press, 2018

  42. [42]

    Ammar Daskin. The quantum version of the shifted power method and its application inquadratic binary optimization.Turkish Journal of Electrical Engineering and Computer Sciences, 28(4):2088–2095, 2020

  43. [43]

    Simulating large quantum circuits on a small quantum computer.Physical review letters, 125(15):150504, 2020

    Tianyi Peng, Aram W Harrow, Maris Ozols, and Xiaodi Wu. Simulating large quantum circuits on a small quantum computer.Physical review letters, 125(15):150504, 2020

  44. [44]

    Quantum entanglement

    Ryszard Horodecki, Pawe l Horodecki, Micha l Horodecki, and Karol Horodecki. Quantum entanglement. Reviews of modern physics, 81(2):865–942, 2009

  45. [45]

    A simple min-cut algorithm.Journal of the ACM (JACM), 44(4):585–591, 1997

    Mechthild Stoer and Frank Wagner. A simple min-cut algorithm.Journal of the ACM (JACM), 44(4):585–591, 1997

  46. [46]

    Entangling power of quantum evolutions.Physical Review A, 62(3):030301, 2000

    Paolo Zanardi, Christof Zalka, and Lara Faoro. Entangling power of quantum evolutions.Physical Review A, 62(3):030301, 2000. 18