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:2510.08292

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

Haomu Yuan, Daniel Stilck França, I. A. Luchnikov, Egor Tiunov, Tobias Haug, Leandro Aolita

Published Oct 9, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2510.08292

Related papers

Speeding up the Goemans-Williamson randomized procedure by difference-of-convex optimization

Salloum, Hadi, Roland Hildebrand, Nguyen, Nhat Trung +4 more

We present a novel approach to accelerate the Goemans-Williamson (GW) randomized rounding procedure for quadratic unconstrained binary optimization (QUBO) problems. Instead of solving the conventional semi-definite programming (SDP) relaxation, which is computationally expensive, we employ a difference-of-convex (DC) optimization framework to efficiently approximate the SDP solution. The DC optimization produces candidate vectors that are then used within the GW randomized rounding scheme to generate high-quality binary solutions. Furthermore, we perform direct expectation minimization over manifolds of matrices with limited rank to further enhance the solution quality. Our method is benchmarked on real-world QUBO instances, including inverse kinematics problems, and compared against state-of-the-art solvers, such as quantum-inspired algorithms, demonstrating competitive approximation guarantees alongside substantial computational gains.

arXiv:2512.08852•Dec 9, 2025•0 citations

Faster quantum and classical SDP approximations for quadratic binary optimization

Fernando G. S. L. Brandão, Richard Kueng, Daniel Stilck França

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.

arXiv:1909.04613•Quantum•Jan 20, 2022•28 citations

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén +1 more

We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input matrix sparsity and $γ:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $γ^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$. For $γ=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic quantum advantage for generic sparse SDP solving.

quant-pharXiv:2609.40302•Oct 1, 2026•0 citations

Quantum speed-ups for solving semidefinite relaxations of polynomial optimization

Daniel Stilck França, Ngoc Hoang Anh Mai

We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let $f,g_1,\ldots,g_m$ be real polynomials in $n$ variables and $f^\star$ the infimum of $f$ over the semialgebraic set $S(g)=\{x: g_i(x)\ge 0\}$. Let $λ_k$ be the value of the order-$k$ Lasserre relaxation. Assume either (i) $f^\star=λ_k$ and the optimum is attained in the $\ell_1$-ball of radius $1/2$, or (ii) $S(g)$ lies in the simplex $\{x\ge 0: \sum_j x_j\le 1/2\}$, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates $λ_k$ to accuracy $\varepsilon>0$ with runtime, for fixed $k$, \[ O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), \] where $s_g$ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as $O(n^{3k}\mathrm{poly}(1/\varepsilon))$ even in the unconstrained case. As an example, we obtain an $O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})$ quantum algorithm for portfolio optimization, improving over the classical $O(n^{ω+1}\log(1/\varepsilon))$ bound with $ω\approx2.373$. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.

quant-pharXiv:2511.14389•Nov 19, 2025•0 citations

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

Taylor L. Patti, Jean Kossaifi, Animashree Anandkumar +1 more

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.

arXiv:2206.14999•Quantum•Jul 12, 2023•10 citations

Quantum optimisation algorithms and their applications

Haomu Yuan

This thesis is devoted to four modern quantum optimisation algorithms and their applications. In the first chapter, we provide a complete Quantum Approximate Optimisation Algorithm (QAOA) pipeline for the discrete global minimum-variance portfolio (DGMVP) problem. We introduce an ansatz with efficient initial-state preparation, new hard mixing operators satisfying the constraints of the DGMVP problem, and scalable cost operators utilising binary encoding of the qubits. Benchmarking the method with the most effective optimisation strategies---dual annealing and unfrozen layerwise optimisation---indicates a scaling advantage over classical methods in finding the global optimum of the DGMVP problem. In the second chapter, we show an end-to-end quantum/quantum-inspired Goemans-Williamson semidefinite programming (SDP) method for relaxing Quadratic Unconstrained Binary Optimisation (QUBO) problems and extracting their rounding energy. Our method identifies a class of QUBO instances that is effectively solvable in polylogarithmic time relative to the problem dimension, under the assumptions of Pauli sparsification of the QUBO cost matrix, reducibility of the diagonal constraints, and efficient evaluation of the corresponding Gibbs-state expectation values. Further, we identify the commuting 1D Hamiltonian and the Kronecker graph as practically important instances. Our numerical experiments show that our method solves the SDP and QUBO with up to $2^{50}$ variables for 1D Hamiltonian instances and achieves results competitive with the best classical solver for Kronecker graphs, giving strong evidence of the power of our algorithm. In the third chapter, we improve the current QAOA method with an iterative warm-start initial-state preparation method. We implement the $t$-th order statistic state as the warm-start initial state generated from each QAOA optimisation loop. We achieve an improved approximation ratio when solving the 3-regular MaxCut problem, and find that the worst-case approximation ratio converges to that of the best classical algorithm for $p=1$ QAOA. Additionally, our method achieves more favourable scaling than standalone QAOA, single-string warm-started QAOA, and a classical constrained-sampling approach when solving the DGMVP problem. In the fourth chapter, we provide a hard-constrained Grover adaptive search (GAS) method for fixed-sum quadratic binary optimisation problems, and an extension of the alternating direction method of multipliers (ADMM) framework for fixed-sum quartic binary optimisation. Our method guarantees at least a quadratic speed-up over the classical method, and exponentially reduces the gate count for solving fixed-sum binary optimisation when compared with the soft-constrained GAS in the fault-tolerant quantum computing regime. In summary, our contributions include efficient algorithms and novel frameworks that substantially improve performance and broaden the applicability of these quantum optimisation methods. The proposed methods exhibit favourable scaling behaviour and indicate potential quantum advantages in solving challenging optimisation problems, thereby motivating further research at the interface of quantum computing and optimisation.

•Jan 22, 2026•0 citations
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 present a novel approach to accelerate the Goemans-Williamson (GW) randomized rounding procedure for quadratic unconstrained binary optimization (QUBO) problems. Instead of solving the conventional semi-definite programming (SDP) relaxation, which is computationally expensive, we employ a difference-of-convex (DC) optimization framework to efficiently approximate the SDP solution. The DC optimization produces candidate vectors that are then used within the GW randomized rounding scheme to generate high-quality binary solutions. Furthermore, we perform direct expectation minimization over manifolds of matrices with limited rank to further enhance the solution quality. Our method is benchmarked on real-world QUBO instances, including inverse kinematics problems, and compared against state-of-the-art solvers, such as quantum-inspired algorithms, demonstrating competitive approximation guarantees alongside substantial computational gains.
We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.
We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved O~(n+m)\widetilde{O}(\sqrt{n}+\sqrt{m})O(n​+m​) dependence on matrix dimension nnn and constraint number mmm. Compared with the O~(mn)\widetilde{O}(mn)O(mn) runtime of existing classical methods, this suggests a quartic quantum speedup when m≈nm \approx nm≈n. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let sss denote the the input matrix sparsity and γ:=Rr/εγ:=Rr/\varepsilonγ:=Rr/ε capture dependence on the primal (R)(R)(R) and dual (r)(r)(r) radii as well as target accuracy (ε)(\varepsilon)(ε). When γ2≤min⁡{m,n/s}γ^2\leq\min\{m,n/s\}γ2≤min{m,n/s}, our solver runs in time O~(nsγ4.5+msγ2)\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)O(nsγ4.5+msγ2). For γ=O(1)γ=O(1)γ=O(1), this is O~((n+m)s)\widetilde{O}\left((n+m)s\right)O((n+m)s) and sublinear in the O(mns)O(mns)O(mns) input size. Similar to the quantum algorithms, this matches known lower bounds with respect to mmm and nnn, up to logarithmic factors. This implies that, with respect to dimensions mmm and nnn, there is no super-quadratic quantum advantage for generic sparse SDP solving.
We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let f,g1,…,gmf,g_1,\ldots,g_mf,g1​,…,gm​ be real polynomials in nnn variables and f⋆f^\starf⋆ the infimum of fff over the semialgebraic set S(g)={x:gi(x)≥0}S(g)=\{x: g_i(x)\ge 0\}S(g)={x:gi​(x)≥0}. Let λkλ_kλk​ be the value of the order-kkk Lasserre relaxation. Assume either (i) f⋆=λkf^\star=λ_kf⋆=λk​ and the optimum is attained in the ℓ1\ell_1ℓ1​-ball of radius 1/21/21/2, or (ii) S(g)S(g)S(g) lies in the simplex {x≥0:∑jxj≤1/2}\{x\ge 0: \sum_j x_j\le 1/2\}{x≥0:∑j​xj​≤1/2}, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates λkλ_kλk​ to accuracy ε>0\varepsilon>0ε>0 with runtime, for fixed kkk, O(nkε−4+nk/2ε−5),O ⁣(sg ⁣[nkε−4+ ⁣(nk+ ⁣∑i=1mnk−di)1/2 ⁣ε−5]), O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), O(nkε−4+nk/2ε−5),O(sg​[nkε−4+(nk+∑i=1m​nk−di​)1/2ε−5]), where sgs_gsg​ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as O(n3kpoly(1/ε))O(n^{3k}\mathrm{poly}(1/\varepsilon))O(n3kpoly(1/ε)) even in the unconstrained case. As an example, we obtain an O(nε−4+nε−5)O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})O(nε−4+n​ε−5) quantum algorithm for portfolio optimization, improving over the classical O(nω+1log⁡(1/ε))O(n^{ω+1}\log(1/\varepsilon))O(nω+1log(1/ε)) bound with ω≈2.373ω\approx2.373ω≈2.373. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.
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.
This thesis is devoted to four modern quantum optimisation algorithms and their applications. In the first chapter, we provide a complete Quantum Approximate Optimisation Algorithm (QAOA) pipeline for the discrete global minimum-variance portfolio (DGMVP) problem. We introduce an ansatz with efficient initial-state preparation, new hard mixing operators satisfying the constraints of the DGMVP problem, and scalable cost operators utilising binary encoding of the qubits. Benchmarking the method with the most effective optimisation strategies---dual annealing and unfrozen layerwise optimisation---indicates a scaling advantage over classical methods in finding the global optimum of the DGMVP problem. In the second chapter, we show an end-to-end quantum/quantum-inspired Goemans-Williamson semidefinite programming (SDP) method for relaxing Quadratic Unconstrained Binary Optimisation (QUBO) problems and extracting their rounding energy. Our method identifies a class of QUBO instances that is effectively solvable in polylogarithmic time relative to the problem dimension, under the assumptions of Pauli sparsification of the QUBO cost matrix, reducibility of the diagonal constraints, and efficient evaluation of the corresponding Gibbs-state expectation values. Further, we identify the commuting 1D Hamiltonian and the Kronecker graph as practically important instances. Our numerical experiments show that our method solves the SDP and QUBO with up to 2502^{50}250 variables for 1D Hamiltonian instances and achieves results competitive with the best classical solver for Kronecker graphs, giving strong evidence of the power of our algorithm. In the third chapter, we improve the current QAOA method with an iterative warm-start initial-state preparation method. We implement the ttt-th order statistic state as the warm-start initial state generated from each QAOA optimisation loop. We achieve an improved approximation ratio when solving the 3-regular MaxCut problem, and find that the worst-case approximation ratio converges to that of the best classical algorithm for p=1p=1p=1 QAOA. Additionally, our method achieves more favourable scaling than standalone QAOA, single-string warm-started QAOA, and a classical constrained-sampling approach when solving the DGMVP problem. In the fourth chapter, we provide a hard-constrained Grover adaptive search (GAS) method for fixed-sum quadratic binary optimisation problems, and an extension of the alternating direction method of multipliers (ADMM) framework for fixed-sum quartic binary optimisation. Our method guarantees at least a quadratic speed-up over the classical method, and exponentially reduces the gate count for solving fixed-sum binary optimisation when compared with the soft-constrained GAS in the fault-tolerant quantum computing regime. In summary, our contributions include efficient algorithms and novel frameworks that substantially improve performance and broaden the applicability of these quantum optimisation methods. The proposed methods exhibit favourable scaling behaviour and indicate potential quantum advantages in solving challenging optimisation problems, thereby motivating further research at the interface of quantum computing and optimisation.