aiqbench analysis
This research establishes a rigorous quantum-classical duality using Sum-of-Squares semidefinite programming to provide certified lower bounds for variational optimization algorithms like QAOA, regardless of their convergence quality. Furthermore, the study leverages two-qubit correlation data to enable polynomial-time circuit cutting with provable error bounds, offering practical tools for scaling near-term quantum hardware.
Certifying Quantum Optimization and Circuit Cutting by Using Quantum-Classical Moment Duality
arXiv:2606.23727v2 Announce Type: replace 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 \textbf{any} quantum state $\rho$ is automatically a feasible point of the classical Goemans--Williamson (GW) relaxation. This observation provides a universal safety net for variational quantum optimization algorithms: applying GW random hyperplane rounding to the quantum-driven moment matrix yields a certified expected cut value bounded below by $\alpha_{\text{GW}} \langle \mathcal{H} \rangle_\rho$, which holds for every state generated by variational algorithms such as the Quantum Alternating Operator Ansatz (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 algorithms and on random states for circuit cutting, demonstrating that two-point correlation data are sufficient to locate near-optimal bipartitions while theoretical error bounds hold in practice.
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 \textbf{any} quantum state $\rho$ is automatically a feasible point of the classical Goemans--Williamson (GW) relaxation. This observation provides a universal safety net for variational quantum optimization algorithms: applying GW random hyperplane rounding to the quantum-driven moment matrix yields a certified expected cut value bounded below by $\alpha_{\text{GW}} \langle \mathcal{H} \rangle_\rho$, which holds for every state generated by variational algorithms such as the Quantum Alternating Operator Ansatz (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 algorithms and on random states for circuit cutting, demonstrating that two-point correlation data are sufficient to locate near-optimal bipartitions while theoretical error bounds hold in practice.
submitted; feedback welcome! simulation code is available at this https URL
Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)
arXiv:2606.23727 [quant-ph]
(or arXiv:2606.23727v2 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2606.23727 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 274 words
