Technical Summary: Certifying Quantum Optimization and Circuit Cutting by Using Quantum–Classical Moment Duality

1. Problem Statement

The paper addresses two critical challenges in near-term quantum computing:

1. Lack of Performance Certification: Variational Quantum Algorithms (VQAs) such as the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Power Method (VQPM) often lack rigorous, per-state performance guarantees. Their approximation ratios are frequently instance-dependent or rely on convergence to global optima, leaving a gap in certification for noisy or prematurely terminated runs.
2. Circuit Cutting Overhead: Decomposing large quantum circuits into smaller sub-circuits (circuit cutting) to run on limited hardware is NP-complete when seeking optimal bipartitions. Existing heuristics often rely on geometric assumptions or brute-force searches, lacking rigorous error bounds based on measurable correlation data.

The authors propose a unified framework leveraging a "quantum–classical moment duality" to solve both problems using only two-point Pauli-Z correlation data.

2. Methodology: The Quantum–Classical Moment Dictionary

The core methodology establishes a direct mapping between the physical properties of any quantum state and the classical Sum-of-Squares (SoS) relaxation space.

2.1 The Mapping

Let $\rho$ be an arbitrary quantum state (density matrix) on $n$ qubits. The authors define a mapping $\Phi$ that extracts single-qubit and two-qubit Pauli-Z expectation values to construct a matrix $Y_{\text{quantum}}$:
$$Y_{\text{quantum}} = \Phi(\rho) = \begin{pmatrix} 1 & \langle Z_1 \rangle_\rho & \cdots & \langle Z_n \rangle_\rho \\ \langle Z_1 \rangle_\rho & 1 & \cdots & \langle Z_1 Z_n \rangle_\rho \\ \vdots & \vdots & \ddots & \vdots \\ \langle Z_n \rangle_\rho & \langle Z_n Z_1 \rangle_\rho & \cdots & 1 \end{pmatrix}$$
where $\langle O \rangle_\rho = \text{Tr}(\rho O)$.

2.2 Theoretical Foundation

Theorem 2.1 (Rigorous Feasibility Retention): The paper proves that for any valid quantum state $\rho$, the resulting matrix $Y_{\text{quantum}}$ is always a feasible point of the classical degree-2 SoS cone (the Goemans–Williamson SDP relaxation).

• Proof Logic: The diagonal elements are 1 because $Z_i^2 = I$. The matrix is positive semidefinite (PSD) because for any vector $v$, $v^T Y_{\text{quantum}} v = \text{Tr}(\rho O_v^2)$, where $O_v$ is a Hermitian observable. Since $\rho$ and $O_v^2$ are PSD, their trace product is non-negative.

This observation creates a "universal safety net": the quantum state itself acts as an active optimization proxy within the continuous geometry of the semidefinite cone, requiring no active SDP solving.

3. Key Contributions

3.1 Universal Certification for Max-Cut

By establishing that $Y_{\text{quantum}}$ is feasible for the degree-2 SoS SDP, the authors apply the classical Goemans–Williamson (GW) random hyperplane rounding directly to the quantum-derived matrix.

• Result: For any state $\rho$ produced by a variational algorithm, the expected cut weight $E[\text{Cut}]$ obtained via GW rounding satisfies:
  $$E[\text{Cut}] \geq \alpha_{GW} \langle H \rangle_\rho$$
  where $\alpha_{GW} \approx 0.87856$ and $\langle H \rangle_\rho$ is the quantum expectation value of the Max-Cut Hamiltonian.
• Significance: This provides a certified lower bound on the approximation ratio for every state in the optimization trajectory, decoupling performance certification from algorithmic convergence. It remains valid even if the algorithm is noisy, trapped in local minima, or stopped early.

3.2 Correlation-Based Circuit Cutting

The same moment matrix captures the entanglement structure of the state, enabling a polynomial-time procedure to detect tensor-product decompositions of the underlying unitary $U$.

• Exact Detection: If a unitary $U$ factorizes as $A_S \otimes B_T$, the connected correlation $C_{ij} = \langle Z_i Z_j \rangle - \langle Z_i \rangle \langle Z_j \rangle$ vanishes for all $i \in S, j \in T$. The authors propose building a graph from thresholded correlations; disconnected components indicate exact cuts.
• Approximate Cutting: For states that are not exact product states, the method formulates a weighted minimum-cut problem using $|C_{ij}|$ as edge weights to find a bipartition that minimizes inter-partition correlations.
• Error Bounds: The paper provides rigorous error bounds quantifying the distance between the original state and the best product state approximation:
  • Single-probe: The distance is bounded by $\sqrt{I(S:T)}$, where $I(S:T)$ is the quantum mutual information.
  • Global Certification: Using the Choi state, the authors derive a bound on the operator norm distance $\|U - A_S \otimes B_T\|_\infty$, ensuring the decomposition holds for arbitrary inputs, not just the specific state prepared.

4. Results and Validation

The framework was validated numerically on two fronts:

1. Variational Algorithms (QAOA and VQPM):

   • QAOA ($p=1$ on 4-Cycle): The study demonstrated that the GW-rounded bound $F(\gamma, \beta)$ remains strictly above the analytic floor $\alpha_{GW} E_\rho$ throughout the optimization trajectory, even when the raw energy $E_\rho$ is sub-optimal.
   • VQPM: The method was applied to the Variational Quantum Power Method, including its "qubit locking" heuristic. The results showed that the moment-matrix certificate remains valid even after aggressive locking, providing a safety net against premature convergence. The certified lower bound consistently tracked the true performance, eventually converging to the exact Max-Cut value when the state reached a computational basis solution.

2. Circuit Cutting (Random States):

   • Using Haar-random states on $n=6$ qubits, the authors tested the correlation-based cut against exhaustive search.
   • Accuracy: The mutual information of the cuts found via the moment matrix ($I_Y$) coincided almost perfectly with the globally optimal mutual information ($I_{\text{best}}$) found by exhaustive search.
   • Error Bounds: The observed 2-norm errors between the true state and the reconstructed product state were consistently below the theoretical bound $\sqrt{I(S:T)}$.
   • Success Rate: For exact product states, the algorithm identified the correct tensor-product structure with 100% success across various subsystem sizes.

5. Significance and Claims

The paper claims a fundamental structural insight: the two-qubit Pauli-Z correlation matrix of any quantum state is automatically a feasible point of the classical degree-2 SoS cone.

This finding has three primary implications:

1. Passive Certification: Unlike prior works that actively solve SDPs to find bounds, this method uses the quantum device merely to generate measurement data. The certification is a passive, post-processing step that requires no additional quantum resources beyond standard energy estimation.
2. Decoupling Convergence from Certification: It provides a "safety net" for variational algorithms, guaranteeing a performance floor regardless of whether the classical optimizer has converged or if the hardware is noisy.
3. Efficient Circuit Cutting: It offers a geometry-agnostic, polynomial-time method for circuit cutting with rigorous error bounds derived directly from measurable two-point correlations, circumventing the NP-complete complexity of finding optimal cuts.

The authors position this work as a "universal safety net" that bridges quantum optimization and classical convex relaxation, providing rigorous guarantees for both the quality of the solution (Max-Cut) and the structure of the circuit (cutting) without requiring higher-order correlation measurements or complex tomography.