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

• URL: http://arxiv.org/abs/2606.23727v1
• Date: Fri, 19 Jun 2026 12:48:36 GMT
• Title: Certifying Quantum Optimization and Circuit Cutting by Using Quantum-Classical Moment Duality
• Abstract summary: We establish a direct quantum-classical duality based on the degree-$2$ Sum-of-Squares semidefinite programming cone.<n>We show that the same moment matrix reveals the tensor-product structure of the underlying unitary circuit.<n>The framework is validated on Max-Cut instances for variational quantum algorithms and on random states for circuit cutting.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $ρ$ 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 α_{\mathrm{GW}}\langle\mathcal{H}\rangle_ρ$, 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.

Related papers

• Orthogonal Quantum Krylov Diagonalisation [35.18016233072556]
  Existing quantum Krylov approaches rely on non-orthogonal Krylov bases, requiring overlap-matrix regularization.<n>We introduce an Orthogonal Quantum Krylov Diagonalization (OQKD) framework that reformulates the classical Lanczos at the operator level.
  arXiv  Detail & Related papers  (2026-07-10T14:49:53Z)
• Basis Adaptive Algorithm for Quantum Many-Body Systems on Quantum Computers [2.4713653282916126]
  A new basis adaptive algorithm is introduced to efficiently find the ground-state properties of quantum many-body systems.<n>We benchmark this approach on the spin-1/2 XXZ chain up to 24 qubits using the IBM Heron processor.
  arXiv  Detail & Related papers  (2025-12-14T16:34:19Z)
• Explicit Formulas for Estimating Trace of Reduced Density Matrix Powers via Single-Circuit Measurement Probabilities [10.43657724071918]
  We propose a universal framework to simultaneously estimate the traces of the $2$nd to the $n$th powers of a reduced density matrix.<n>We develop two algorithms: a purely quantum method and a hybrid quantum-classical approach combining Newton-Girard iteration.<n>We explore various applications including the estimation of nonlinear functions and the representation of entanglement measures.
  arXiv  Detail & Related papers  (2025-07-23T01:41:39Z)
• Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach [36.05085942729295]
  This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm, which replaces the random sampling used in classicalNPG estimators with a deterministic gradient estimation approach.<n>The proposed QNPG algorithm achieves a sample complexity of $tildemathcalO(epsilon-1.5)$ for queries to the quantum oracle, significantly improving the classical lower bound of $tildemathcalO(epsilon-2)$ for queries to the Markov Decision Process (MDP)
  arXiv  Detail & Related papers  (2025-01-27T17:38:30Z)
• Sample-Efficient Estimation of Nonlinear Quantum State Functions [5.641998714611475]
  We introduce the quantum state function (QSF) framework by extending the SWAP test via linear combination of unitaries and parameterized quantum circuits.<n>Our framework enables the implementation of arbitrarily normalized degree-$n$ functions of quantum states with precision.<n>We apply QSF for developing quantum algorithms for fundamental tasks, including entropy, fidelity, and eigenvalue estimations.
  arXiv  Detail & Related papers  (2024-12-02T16:40:17Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
  arXiv  Detail & Related papers  (2023-09-19T22:53:17Z)
• Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
  An ideal state preparation protocol can be characterized by being easily generated classically. We propose a method that meets these requirements by introducing a variant of the iterative qubit coupled cluster (iQCC) We demonstrate the algorithm's correctness in ground-state simulations and extend our study to complex systems like the titanium-based compound Ti(C5H5)(CH3)3 with a (20, 20) active space.
  arXiv  Detail & Related papers  (2022-11-18T20:31:10Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Automatic quantum circuit encoding of a given arbitrary quantum state [0.0]
  We propose a quantum-classical hybrid algorithm to encode a given arbitrarily quantum state onto an optimal quantum circuit. The proposed algorithm employs as an objective function the absolute value of fidelity $F = langle 0 vert hatmathcalCdagger vert Psi rangle$. We experimentally demonstrate that a quantum circuit generated by the AQCE algorithm can indeed represent the original quantum state reasonably on a noisy real quantum device.
  arXiv  Detail & Related papers  (2021-12-29T12:33:41Z)
• K-sparse Pure State Tomography with Phase Estimation [1.2183405753834557]
  Quantum state tomography (QST) for reconstructing pure states requires exponentially increasing resources and measurements with the number of qubits. QST reconstruction for any pure state composed of the superposition of $K$ different computational basis states of $n$bits in a specific measurement set-up is presented.
  arXiv  Detail & Related papers  (2021-11-08T09:43:12Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.