Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2206.14999 · Quantum

Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints

Taylor L. Patti, Jean Kossaifi, Animashree Anandkumar, Susanne F. Yelin

Published Jul 12, 2023• 10 citations
arXivHTMLPDF

Abstract

Semidefinite programs are optimization methods with a wide array of applications, such as approximating difficult combinatorial problems. One such semidefinite program is the Goemans-Williamson algorithm, a popular integer relaxation technique. We introduce a variational quantum algorithm for the Goemans-Williamson algorithm that uses only n+1 qubits, a constant number of circuit preparations, and poly(n) expectation values in order to approximately solve semidefinite programs with up to N=2n variables and M∼O(N) constraints. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit, a technique known as the Hadamard Test. The Hadamard Test enables us to optimize the objective function by estimating only a single expectation value of the ancilla qubit, rather than separately estimating exponentially many expectation values. Similarly, we illustrate that the semidefinite programming constraints can be effectively enforced by implementing a second Hadamard Test, as well as imposing a polynomial number of Pauli string amplitude constraints. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems, including MaxCut. Our method exceeds the performance of analogous classical methods on a diverse subset of well-studied MaxCut problems from the GSet library.

DOI
10.22331/q-2023-07-12-1057

Related papers

Exponential Speed-ups for Structured Goemans-Williamson relaxations via Quantum Gibbs States and Pauli Sparsity

Haomu Yuan, Daniel Stilck França, I. A. Luchnikov +3 more

Quadratic Unconstrained Binary Optimization (QUBO) problems are prevalent in various applications and are known to be NP-hard. The seminal work of Goemans and Williamson introduced a semidefinite programming (SDP) relaxation for such problems, solvable in polynomial time that upper bounds the optimal value. Their approach also enables randomized rounding techniques to obtain feasible solutions with provable performance guarantees. In this work, we identify instances of QUBO problems where matrix multiplicative weight methods lead to quantum and quantum-inspired algorithms that approximate the Goemans-Williamson SDP exponentially faster than existing methods, achieving polylogarithmic time complexity relative to the problem dimension. This speedup is attainable under the assumption that the QUBO cost matrix is sparse when expressed as a linear combination of Pauli strings satisfying certain algebraic constraints, and leverages efficient quantum and classical simulation results for quantum Gibbs states. We demonstrate how to verify these conditions efficiently given the decomposition. Additionally, we explore heuristic methods for randomized rounding procedures and extract the energy of a feasible point of the QUBO in polylogarithmic time. While the practical relevance of instances where our methods excel remains to be fully established, we propose heuristic algorithms with broader applicability and identify Kronecker graphs as a promising class for applying our techniques. We conduct numerical experiments to benchmark our methods. Notably, by utilizing tensor network methods, we solve an SDP with $D = 2^{50}$ variables and extract a feasible point which is certifiably within $0.15\%$ of the optimum of the QUBO through our approach on a desktop, reaching dimensions millions of times larger than those handled by existing SDP or QUBO solvers, whether heuristic or rigorous.

arXiv:2510.08292•Oct 9, 2025•0 citations

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

Ammar Daskin

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 $ρ$ 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 $α_{\text{GW}} \langle \mathcal{H} \rangle_ρ$, 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.

quant-pharXiv:2606.23727•Jun 22, 2026•0 citations

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

Ammar Daskin

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.

•Jun 19, 2026•0 citations

Enhanced Distributed Variational Quantum Eigensolver for Large-Scale MaxCut Problem

Yuefeng Lin, Kun Wang, Qinyuan Zheng +6 more

MaxCut is a canonical NP-hard combinatorial optimization problem in graph theory with broad applications ranging from physics to bioinformatics. Although variational quantum algorithms offer promising new approaches that may eventually outperform classical schemes, they suffer from resource constraints and trainability issues such as barren plateaus, making large-scale instances intractable on noisy intermediate-scale quantum devices. In this paper, we propose an enhanced distributed variational quantum eigensolver for large-scale MaxCut problems, which extends our prior distributed variational quantum eigensolver framework by integrating a novel hybrid classical-quantum perturbation strategy, enhances optimization scalability and efficiency. Our algorithm solves weighted MaxCut instances with up to 1000 vertices using only 10 qubits, and numerical results indicate that it consistently outperforms the Goemans-Williamson algorithm. We further employ a warm-start initialization strategy, seeding the algorithm with high-quality solutions from the Goemans-Williamson algorithm, with results confirming that the optimal classical solution can be effectively further improved. The practical utility of the proposed algorithm is further validated through its application to haplotype phasing on genome sequencing data of the human ABCA1 gene, producing high-quality haplotypes that rival those obtained by the Goemans-Williamson algorithm with $10^6$ projections. These results establish the proposed algorithm as a scalable, NISQ-compatible framework for near-term quantum-enhanced large-scale combinatorial optimization.

quant-pharXiv:2512.22056•Dec 29, 2025•0 citations

Warm-starting quantum optimization

Daniel J. Egger, Jakub Mareček, Stefan Woerner

There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.

arXiv:2009.10095•Quantum•Jun 17, 2021•269 citations

Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives

Iria W. Wang, Robin Brown, Taylor L. Patti +3 more

Many practically important NP-hard optimization problems are inherently higher-order polynomial optimizations, which are typically addressed using approximation algorithms. Classical relaxations express polynomial objectives over a polynomial basis and solve the resulting quadratic objective as a semidefinite program, which can significantly inflate problem size and degrade approximation behavior. Variational quantum analogues to classical semidefinite programs (vQSDPs) are near-term formulations geared towards quadratic objectives. We introduce Product-State Lifting (PSL), a simple product-register encoding that upgrades any vQSDP with basis-state encoding to tackle k -degree polynomial optimization. This upgrade requires only a linear increase in resources with constraints constant in k . As a worked example, we pair PSL with the recently-proposed vQSDP with the Hadamard test and approximate amplitude constraints [Quantum 7, 1057 (2023)], and outline an application to Max- k SAT. PSL maintains the device-friendly structure of vQSDPs while making polynomial degree a linear resource parameter, offering a general path from quadratic to polynomial optimization without the constraint growth typical of classical relaxations.

arXiv:2408.07774•Quantum•Apr 21, 2026•0 citations
Semidefinite programs are optimization methods with a wide array of applications, such as approximating difficult combinatorial problems. One such semidefinite program is the Goemans-Williamson algorithm, a popular integer relaxation technique. We introduce a variational quantum algorithm for the Goemans-Williamson algorithm that uses only n+1 qubits, a constant number of circuit preparations, and poly(n) expectation values in order to approximately solve semidefinite programs with up to N=2n variables and M∼O(N) constraints. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit, a technique known as the Hadamard Test. The Hadamard Test enables us to optimize the objective function by estimating only a single expectation value of the ancilla qubit, rather than separately estimating exponentially many expectation values. Similarly, we illustrate that the semidefinite programming constraints can be effectively enforced by implementing a second Hadamard Test, as well as imposing a polynomial number of Pauli string amplitude constraints. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems, including MaxCut. Our method exceeds the performance of analogous classical methods on a diverse subset of well-studied MaxCut problems from the GSet library.
Quadratic Unconstrained Binary Optimization (QUBO) problems are prevalent in various applications and are known to be NP-hard. The seminal work of Goemans and Williamson introduced a semidefinite programming (SDP) relaxation for such problems, solvable in polynomial time that upper bounds the optimal value. Their approach also enables randomized rounding techniques to obtain feasible solutions with provable performance guarantees. In this work, we identify instances of QUBO problems where matrix multiplicative weight methods lead to quantum and quantum-inspired algorithms that approximate the Goemans-Williamson SDP exponentially faster than existing methods, achieving polylogarithmic time complexity relative to the problem dimension. This speedup is attainable under the assumption that the QUBO cost matrix is sparse when expressed as a linear combination of Pauli strings satisfying certain algebraic constraints, and leverages efficient quantum and classical simulation results for quantum Gibbs states. We demonstrate how to verify these conditions efficiently given the decomposition. Additionally, we explore heuristic methods for randomized rounding procedures and extract the energy of a feasible point of the QUBO in polylogarithmic time. While the practical relevance of instances where our methods excel remains to be fully established, we propose heuristic algorithms with broader applicability and identify Kronecker graphs as a promising class for applying our techniques. We conduct numerical experiments to benchmark our methods. Notably, by utilizing tensor network methods, we solve an SDP with D=250D = 2^{50}D=250 variables and extract a feasible point which is certifiably within 0.15%0.15\%0.15% of the optimum of the QUBO through our approach on a desktop, reaching dimensions millions of times larger than those handled by existing SDP or QUBO solvers, whether heuristic or rigorous.
We establish a direct quantum--classical duality based on the degree-222 Sum-of-Squares (SoS) semidefinite programming cone: the matrix of two-qubit Pauli-ZZZ correlation functions obtained from \textbf{any} quantum state ρρρ 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 αGW⟨H⟩ρα_{\text{GW}} \langle \mathcal{H} \rangle_ραGW​⟨H⟩ρ​, 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.
We establish a direct quantum--classical duality based on the degree-222 Sum-of-Squares (SoS) semidefinite programming cone: the matrix of two-qubit Pauli-ZZZ 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 E[Cut]≥αGW⟨H⟩ρ\mathbb{E}[\mathrm{Cut}] \ge \alpha_{\mathrm{GW}}\langle\mathcal{H}\rangle_\rhoE[Cut]≥αGW​⟨H⟩ρ​, 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.
MaxCut is a canonical NP-hard combinatorial optimization problem in graph theory with broad applications ranging from physics to bioinformatics. Although variational quantum algorithms offer promising new approaches that may eventually outperform classical schemes, they suffer from resource constraints and trainability issues such as barren plateaus, making large-scale instances intractable on noisy intermediate-scale quantum devices. In this paper, we propose an enhanced distributed variational quantum eigensolver for large-scale MaxCut problems, which extends our prior distributed variational quantum eigensolver framework by integrating a novel hybrid classical-quantum perturbation strategy, enhances optimization scalability and efficiency. Our algorithm solves weighted MaxCut instances with up to 1000 vertices using only 10 qubits, and numerical results indicate that it consistently outperforms the Goemans-Williamson algorithm. We further employ a warm-start initialization strategy, seeding the algorithm with high-quality solutions from the Goemans-Williamson algorithm, with results confirming that the optimal classical solution can be effectively further improved. The practical utility of the proposed algorithm is further validated through its application to haplotype phasing on genome sequencing data of the human ABCA1 gene, producing high-quality haplotypes that rival those obtained by the Goemans-Williamson algorithm with 10610^6106 projections. These results establish the proposed algorithm as a scalable, NISQ-compatible framework for near-term quantum-enhanced large-scale combinatorial optimization.
There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
Many practically important NP-hard optimization problems are inherently higher-order polynomial optimizations, which are typically addressed using approximation algorithms. Classical relaxations express polynomial objectives over a polynomial basis and solve the resulting quadratic objective as a semidefinite program, which can significantly inflate problem size and degrade approximation behavior. Variational quantum analogues to classical semidefinite programs (vQSDPs) are near-term formulations geared towards quadratic objectives. We introduce Product-State Lifting (PSL), a simple product-register encoding that upgrades any vQSDP with basis-state encoding to tackle k -degree polynomial optimization. This upgrade requires only a linear increase in resources with constraints constant in k . As a worked example, we pair PSL with the recently-proposed vQSDP with the Hadamard test and approximate amplitude constraints [Quantum 7, 1057 (2023)], and outline an application to Max- k SAT. PSL maintains the device-friendly structure of vQSDPs while making polynomial degree a linear resource parameter, offering a general path from quadratic to polynomial optimization without the constraint growth typical of classical relaxations.