Certifying Quantum Optimization and Circuit Cutting by Using Quantum-Classical Moment Duality
Pith reviewed 2026-06-26 13:53 UTC · model grok-4.3
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.
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
- 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
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.
Referee Report
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)
- [§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.
- [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.
- [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
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
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
axioms (1)
- standard math Degree-2 Sum-of-Squares SDP cone membership for the Pauli-Z moment matrix
Reference graph
Works this paper leans on
-
[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
1995
-
[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
2003
-
[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
2001
-
[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
Pith/arXiv arXiv 2014
-
[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
Pith/arXiv arXiv 2026
-
[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
2014
-
[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
2007
-
[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
2008
-
[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
2022
-
[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
arXiv 2023
-
[11]
Matthew B Hastings. Limitations and separations in the quantum sum-of-squares, and the quantum knapsack problem.arXiv preprint arXiv:2402.14752, 2024. 16
arXiv 2024
-
[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
2026
-
[13]
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
Pith/arXiv arXiv 2024
-
[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
2017
-
[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
2024
-
[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...
2019
-
[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...
2021
-
[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
2022
-
[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
2023
-
[20]
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
arXiv 2022
-
[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
2024
-
[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
2025
-
[23]
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
Pith/arXiv arXiv 2023
-
[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
2016
-
[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
2023
-
[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
2024
-
[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
2025
-
[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
2012
-
[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
2022
-
[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
2023
-
[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
2025
-
[32]
Songqinghao Yang and Prakash Murali. Understanding the scalability of circuit cutting techniques for practical quantum applications.arXiv preprint arXiv:2411.17756, 2024
arXiv 2024
-
[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
2023
-
[34]
A quantum approximate optimization algorithm
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014
Pith/arXiv arXiv 2014
-
[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
2014
-
[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
2018
-
[37]
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
arXiv 2021
-
[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
2021
-
[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
2021
-
[40]
Ammar Daskin. From theory to practice: Analyzing variational quantum power method for quantum optimization of qubo problems.arXiv preprint arXiv:2505.12990, 2025
Pith/arXiv arXiv 2025
-
[41]
Cambridge university press, 2018
John Watrous.The theory of quantum information. Cambridge university press, 2018
2018
-
[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
2088
-
[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
2020
-
[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
2009
-
[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
1997
-
[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
2000
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.