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

Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, James Sud

quant-phSubmitted Apr 21, 2025• Announced Apr 22, 2025• Revised Oct 29, 2026 (v2)
v1 · Apr 21, 2025v2 · Oct 29, 2026
arXivHTMLPDF

Abstract

We introduce a $0.611$-approximation algorithm for Quantum MaxCut and a $\frac{1+\sqrt{5}}{4} \approx 0.809$-approximation algorithm for the EPR Hamiltonian of [arXiv:2209.02589]. A novel ingredient in both of these algorithms is to partially entangle pairs of qubits associated to edges in a matching, while preserving the direction of their single-qubit Bloch vectors. This allows us to interpolate between product states and matching-based states with a tunable parameter.

Comments
v2. fixed minor bug in QMC algorithm (does not affect algorithm performance) and remarked on improved approximation ratio under recent upper bounds

Related papers

Improved approximation algorithms for the EPR Hamiltonian

Nathan Ju, Ansh Nagda

The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2209.02589). We introduce a polynomial time $\frac{1+\sqrt{5}}{4}\approx 0.809$-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of $0.72$ (arXiv:2410.15544). As a special case, this also implies a $\frac{1+\sqrt{5}}{4}$-approximation for Quantum Max Cut on bipartite instances, improving upon the approximation ratio of $3/4$ that one can infer in a relatively straightforward manner from the work of Lee and Parekh (arXiv:2401.03616).

arXiv:2504.10712•Apr 14, 2025•0 citations

An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs

Robbie King

We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state. The SDP is used to choose the parameters of a variational quantum circuit. The entangled state is then represented as the quantum circuit applied to a product state. It achieves an approximation ratio of 0.582 on triangle-free graphs. The previous best algorithms of Anshu, Gosset, Morenz, and Parekh, Thompson achieved approximation ratios of 0.531 and 0.533 respectively. In addition, we study the EPR Hamiltonian, which we argue is a natural intermediate problem which isolates some key quantum features of local Hamiltonian problems. For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio 1/2 on all graphs.

arXiv:2209.02589•Quantum•Nov 9, 2023•11 citations

A 0.8395-approximation algorithm for the EPR problem

Anuj Apte, Eunou Lee, Kunal Marwaha +3 more

We give an efficient 0.8395-approximation algorithm for the EPR Hamiltonian. Our improvement comes from a new nonlinear monogamy-of-entanglement bound on star graphs and a refined parameterization of a shallow quantum circuit from previous works. We also prove limitations showing that current methods cannot achieve substantially better approximation ratios, indicating that further progress will require fundamentally new techniques.

quant-pharXiv:2512.09896•Leibniz international proceedings in informatics•Dec 11, 2025•0 citations

An improved Quantum Max Cut approximation via matching

Eunou Lee, Parekh, Ojas

Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.

arXiv:2401.03616•Jan 8, 2024•0 citations

An Improved Quantum Max Cut Approximation via Maximum Matching

Eunou Lee, Ojas Parekh

Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Eunou Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.

Leibniz international proceedings in informatics•Jan 1, 2024•0 citations

The Quantum Approximate Optimization Algorithm performance with low entanglement and high circuit depth

Rishi Sreedhar, Pontus Vikstål, Marika Svensson +3 more

Variational quantum algorithms constitute one of the most widespread methods for using current noisy quantum computers. However, it is unknown if these heuristic algorithms provide any quantum-computational speedup, although we cannot simulate them classically for intermediate sizes. Since entanglement lies at the core of quantum computing power, we investigate its role in these heuristic methods for solving optimization problems. In particular, we use matrix product states to simulate the quantum approximate optimization algorithm with reduced bond dimensions $D$, a parameter bounding the system entanglement. Moreover, we restrict the simulation further by deterministically sampling solutions. We conclude that entanglement plays a minor role in the MaxCut and Exact Cover 3 problems studied here since the simulated algorithm analysis, with up to $60$ qubits and $p=100$ algorithm layers, shows that it provides solutions for bond dimension $D \approx 10$ and depth $p \approx 30$. Additionally, we study the classical optimization loop in the approximated algorithm simulation with $12$ qubits and depth up to $p=4$ and show that the approximated optimal parameters with low entanglement approach the exact ones.

arXiv:2207.03404•Jul 7, 2022•8 citations
We introduce a 0.6110.6110.611-approximation algorithm for Quantum MaxCut and a 1+54≈0.809\frac{1+\sqrt{5}}{4} \approx 0.80941+5​​≈0.809-approximation algorithm for the EPR Hamiltonian of [arXiv:2209.02589]. A novel ingredient in both of these algorithms is to partially entangle pairs of qubits associated to edges in a matching, while preserving the direction of their single-qubit Bloch vectors. This allows us to interpolate between product states and matching-based states with a tunable parameter.
The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2209.02589). We introduce a polynomial time 1+54≈0.809\frac{1+\sqrt{5}}{4}\approx 0.80941+5​​≈0.809-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of 0.720.720.72 (arXiv:2410.15544). As a special case, this also implies a 1+54\frac{1+\sqrt{5}}{4}41+5​​-approximation for Quantum Max Cut on bipartite instances, improving upon the approximation ratio of 3/43/43/4 that one can infer in a relatively straightforward manner from the work of Lee and Parekh (arXiv:2401.03616).
We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state. The SDP is used to choose the parameters of a variational quantum circuit. The entangled state is then represented as the quantum circuit applied to a product state. It achieves an approximation ratio of 0.582 on triangle-free graphs. The previous best algorithms of Anshu, Gosset, Morenz, and Parekh, Thompson achieved approximation ratios of 0.531 and 0.533 respectively. In addition, we study the EPR Hamiltonian, which we argue is a natural intermediate problem which isolates some key quantum features of local Hamiltonian problems. For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio 1/2 on all graphs.
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Eunou Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.
Variational quantum algorithms constitute one of the most widespread methods for using current noisy quantum computers. However, it is unknown if these heuristic algorithms provide any quantum-computational speedup, although we cannot simulate them classically for intermediate sizes. Since entanglement lies at the core of quantum computing power, we investigate its role in these heuristic methods for solving optimization problems. In particular, we use matrix product states to simulate the quantum approximate optimization algorithm with reduced bond dimensions DDD, a parameter bounding the system entanglement. Moreover, we restrict the simulation further by deterministically sampling solutions. We conclude that entanglement plays a minor role in the MaxCut and Exact Cover 3 problems studied here since the simulated algorithm analysis, with up to 606060 qubits and p=100p=100p=100 algorithm layers, shows that it provides solutions for bond dimension D≈10D \approx 10D≈10 and depth p≈30p \approx 30p≈30. Additionally, we study the classical optimization loop in the approximated algorithm simulation with 121212 qubits and depth up to p=4p=4p=4 and show that the approximated optimal parameters with low entanglement approach the exact ones.