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:2011.08165 · Physical Review A

Generating target graph couplings for the quantum approximate optimization algorithm from native quantum hardware couplings

Joel Rajakumar, Jai Moondra, Bryan Gard, Swati Gupta, Creston D. Herold

Published Aug 5, 2022• 8 citations
arXivHTMLPDF

Abstract

We present methods for constructing any target coupling graph using limited global controls in an Ising-like quantum spin system. Our approach is motivated by implementing the quantum approximate optimization algorithm (QAOA) on trapped-ion quantum hardware to find approximate solutions to MaxCut. We present a mathematical description of the problem and provide approximately optimal algorithmic constructions that generate arbitrary unweighted coupling graphs with $n$ nodes in $O(n)$ global entangling operations and weighted graphs with $m$ edges in $O(m)$ operations. These upper bounds are not tight in general, and we formulate a mixed-integer program to solve the graph coupling problem to optimality. We perform numeric experiments on small graphs with $n\ensuremath{\le}8$ and show that optimal sequences, which use fewer operations, can be found using mixed-integer programs. Noisy simulations of MaxCut QAOA show that our implementation is less susceptible to noise than the standard gate-based compilation.

DOI
10.1103/physreva.106.022606

Related papers

Optimizing Cost Hamiltonian Compilation for Max-Cut QAOA on Unweighted Graphs Using Global Controls and Qubit Bit Flips

Saber Dinpazhouh, Illya V. Hicks

We study a cost Hamiltonian compilation problem for the quantum approximate optimization algorithm (QAOA) applied to the Max-Cut problem, focusing on trapped-ion quantum computers. Instead of standard compilation with CNOT and Rz gates, we employ global coupling operations and single-qubit bit flips. Prior work by Rajakumar et al. established that such a compilation is always possible. Minimizing operational error requires short operation sequences. The problem reduces to a low-rank semi-discrete decomposition of the graph's adjacency matrix, where the minimum achievable rank, the graph coupling number gc(G), represents the number of global control layers. Rajakumar et al. introduced the Union of Stars construction, proving gc(G) <= 3n - 2 for unweighted graphs with n vertices, and gave an O(m)-rank construction for weighted graphs. We concentrate on unweighted graphs. We derive structural properties of the compilation problem and show the Union of Stars method is order-optimal by proving a lower bound of gc(G) >= n - 1 for a family of graphs. We also improve the general upper bound to 2.5n + 2. For particular graph families -- cliques, perfect matchings, paths, and cycles -- we provide sharper bounds. Further, we reveal a link between the problem and Hadamard matrix theory. Finally, we introduce a compact mixed-integer programming (MIP) formulation that outperforms the previously studied exponential-size MIP.

arXiv:2509.00170•Aug 29, 2025•0 citations

Max-Cut QAOA Cost Hamiltonian Compilation for Unweighted Graphs Using Minimum Global Controls and Qubit Bit Flips

Saber Dinpazhouh

We study an operation compilation problem, associated with the hybrid quantum-classical algorithm, QAOA, for the max-cut problem on trapped-ion quantum computers. As opposed to the standard $CNOT$ and $R_z$ gate compilation of the cost Hamiltonian for QAOA, here the goal is to compile it to global coupling operations and individual qubit bit flips. Rajakumar et al have proposed this compilation and showed such a compilation exists for any graph. To mitigate operation error a short sequence of operations is desired. In essence, the problem is a low-rank semi-discrete matrix decomposition for the adjacency matrix of a given graph. The lowest possible rank for this decomposition is known as the graph coupling number, $gc(G)$, where $G$ is the input graph. They gave a combinatorial construction, named union of stars, with the rank of at most $3n-2$ for any unweighted graph with n vertices. They gave an $\mathcal{O}(m)$ construction for weighted graphs as well. Here we focus solely on the unweighted graphs. We extract important theoretical properties of the problem. Utilizing these properties we prove the order-optimality of the union of stars algorithm for unweighted graphs by introducing a family of graphs with a lower bound of n - 1 on their gc number. Additionally, we decrease the theoretical upper bound from $3n - 2$ to $2.5n + 2$ for any unweighted graph with n vertices. For specific graph families like cliques, perfect matching graphs, paths, and cycles, we find tighter bounds. Additionally, we propose a compact mixed integer program (MIP) which is competitive against their MIP formulation which has exponential size in the input graph. We also discover a beautiful connection of the problem with the Hadamard matrices.

•Aug 1, 2025•0 citations

Noisy intermediate-scale quantum computing algorithm for solving an n -vertex MaxCut problem with log( n ) qubits

Marko J. Rančić

Quantum computers are devices, which allow more efficient solutions of problems as compared to their classical counterparts.As the timeline to developing a quantum-error corrected computer is unclear, the quantum computing community has dedicated much attention to developing algorithms for currently available noisy intermediate-scale quantum computers (NISQ).Thus far, within NISQ, optimization problems are one of the most commonly studied and are quite often tackled with the quantum approximate optimization algorithm (QAOA).This algorithm is best known for computing graph partitions with a maximal separation of edges (MaxCut), but can easily calculate other problems related to graphs.Here, I present a novel quantum optimization algorithm, which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem.Such an improved performance allowed me to partition graphs with 32 nodes on publicly available 5 qubit gate-based quantum computers without any preprocessing such as division of the graph into smaller subgraphs.These results represent a 40% increase in graph size as compared to state-of-art experiments on gate-based quantum computers such as Google Sycamore.The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal simulators of quantum computers.Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with simulators of quantum computers, again without any predivision into smaller subproblems and a lower solution bound of 67.9% is achieved.The study presented here paves way to using powerful genetic optimizer in synergy with quantum computers.

arXiv:2110.10788•Physical Review Research•Feb 15, 2023•20 citations

A Variational Qubit-Efficient MaxCut Heuristic Algorithm

Yovav Tene-Cohen, Tomer Kelman, Ohad Lev +1 more

Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only $$O(\log N)$$ O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.

arXiv:2308.10383•npj Quantum Information•Feb 16, 2026•3 citations

An exponentially more efficient optimization algorithm for noisy quantum computers

Marko J. Rančić

Quantum computers are devices which allow the solution of problems unsolvable to their classical counterparts. As an error-corrected quantum computer is still a decade away the quantum computing community has dedicated much attention to developing algorithms for currently available Noisy Intermediate-Scale Quantum computers (NISQ). Thus far, within NISQ, optimization problems are one of the most commonly studied and are exclusively tackled with the Quantum Approximate Optimization Algorithm (QAOA). This algorithm predominantly computes graph partitions with a maximal separation of edges (MaxCut), but can also be modified to calculate other properties of graphs. Here, I present a novel quantum optimization algorithm which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem. Such an improved performance allowed me to partition a graphs 32 nodes on publicly available 5 qubit gate-based solid state quantum devices without any preprocessing such as division of the graph into smaller subgraphs. This results represent a 40% increase in graph size as compared to state-of-art experiments on solid state devices such as Google Sycamore. The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal quantum simulators. Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with quantum simulators, again without any pre-division into smaller subproblems and a lower solution bound of 67.9% is achieved.

•Oct 22, 2021•3 citations

Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations

Jai Moondra, Phillip C. Lotshaw, Greg Mohler +1 more

We develop new approximate compilation schemes that significantly reduce the expense of compiling the Quantum Approximate Optimization Algorithm (QAOA) for solving the Max-Cut problem. Our main focus is on compilation with trapped-ion simulators using Pauli- X operations and all-to-all Ising Hamiltonian H Ising evolution generated by Molmer-Sorensen or optical dipole force interactions, though some of our results also apply to standard gate-based compilations. Our results are based on principles of graph sparsification and decomposition; the former reduces the number of edges in a graph while maintaining its cut structure, while the latter breaks a weighted graph into a small number of unweighted graphs. Though these techniques have been used as heuristics in various hybrid quantum algorithms, there have been no guarantees on their performance, to the best of our knowledge. This work provides the first provable guarantees using sparsification and decomposition to improve quantum noise resilience and reduce quantum circuit complexity. For quantum hardware that uses edge-by-edge QAOA compilations, sparsification leads to a direct reduction in circuit complexity. For trapped-ion quantum simulators implementing all-to-all H I s i n g pulses, we show that for a ( 1 − ϵ ) factor loss in the Max-Cut approximation ( ϵ > 0 ) , our compilations improve the (worst-case) number of H I s i n g pulses from O ( n 2 ) to O ( n log ⁡ ( n / ϵ ) ) and the (worst-case) number of Pauli- X bit flips from O ( n 2 ) to O ( n log ⁡ ( n / ϵ ) ϵ 2 ) for n -node graphs. This is an asymptotic improvement for any constant ϵ > 0 . We demonstrate that significant improvements to the approximation ratio are obtained using decomposition in simulated trapped-ion experiments with dephasing noise. We further present a generic argument showing that sparsification results in an exponentially improved circuit fidelity lower bound in digital computing schemes based on one- and two-qubit gates, which are relevant to a wide variety of hardwares such as superconducting qubits and certain neutral atom or trapped ion setups, and more sophisticated noise models. We anticipate these approximate compilation techniques will be useful tools in a variety of future quantum computing experiments.

arXiv:2406.14330•Quantum•Aug 7, 2026•0 citations
We present methods for constructing any target coupling graph using limited global controls in an Ising-like quantum spin system. Our approach is motivated by implementing the quantum approximate optimization algorithm (QAOA) on trapped-ion quantum hardware to find approximate solutions to MaxCut. We present a mathematical description of the problem and provide approximately optimal algorithmic constructions that generate arbitrary unweighted coupling graphs with nnn nodes in O(n)O(n)O(n) global entangling operations and weighted graphs with mmm edges in O(m)O(m)O(m) operations. These upper bounds are not tight in general, and we formulate a mixed-integer program to solve the graph coupling problem to optimality. We perform numeric experiments on small graphs with n\ensuremath≤8n\ensuremath{\le}8n\ensuremath≤8 and show that optimal sequences, which use fewer operations, can be found using mixed-integer programs. Noisy simulations of MaxCut QAOA show that our implementation is less susceptible to noise than the standard gate-based compilation.
We study a cost Hamiltonian compilation problem for the quantum approximate optimization algorithm (QAOA) applied to the Max-Cut problem, focusing on trapped-ion quantum computers. Instead of standard compilation with CNOT and Rz gates, we employ global coupling operations and single-qubit bit flips. Prior work by Rajakumar et al. established that such a compilation is always possible. Minimizing operational error requires short operation sequences. The problem reduces to a low-rank semi-discrete decomposition of the graph's adjacency matrix, where the minimum achievable rank, the graph coupling number gc(G), represents the number of global control layers. Rajakumar et al. introduced the Union of Stars construction, proving gc(G) <= 3n - 2 for unweighted graphs with n vertices, and gave an O(m)-rank construction for weighted graphs. We concentrate on unweighted graphs. We derive structural properties of the compilation problem and show the Union of Stars method is order-optimal by proving a lower bound of gc(G) >= n - 1 for a family of graphs. We also improve the general upper bound to 2.5n + 2. For particular graph families -- cliques, perfect matchings, paths, and cycles -- we provide sharper bounds. Further, we reveal a link between the problem and Hadamard matrix theory. Finally, we introduce a compact mixed-integer programming (MIP) formulation that outperforms the previously studied exponential-size MIP.
We study an operation compilation problem, associated with the hybrid quantum-classical algorithm, QAOA, for the max-cut problem on trapped-ion quantum computers. As opposed to the standard CNOTCNOTCNOT and RzR_zRz​ gate compilation of the cost Hamiltonian for QAOA, here the goal is to compile it to global coupling operations and individual qubit bit flips. Rajakumar et al have proposed this compilation and showed such a compilation exists for any graph. To mitigate operation error a short sequence of operations is desired. In essence, the problem is a low-rank semi-discrete matrix decomposition for the adjacency matrix of a given graph. The lowest possible rank for this decomposition is known as the graph coupling number, gc(G)gc(G)gc(G), where GGG is the input graph. They gave a combinatorial construction, named union of stars, with the rank of at most 3n−23n-23n−2 for any unweighted graph with n vertices. They gave an O(m)\mathcal{O}(m)O(m) construction for weighted graphs as well. Here we focus solely on the unweighted graphs. We extract important theoretical properties of the problem. Utilizing these properties we prove the order-optimality of the union of stars algorithm for unweighted graphs by introducing a family of graphs with a lower bound of n - 1 on their gc number. Additionally, we decrease the theoretical upper bound from 3n−23n - 23n−2 to 2.5n+22.5n + 22.5n+2 for any unweighted graph with n vertices. For specific graph families like cliques, perfect matching graphs, paths, and cycles, we find tighter bounds. Additionally, we propose a compact mixed integer program (MIP) which is competitive against their MIP formulation which has exponential size in the input graph. We also discover a beautiful connection of the problem with the Hadamard matrices.
Quantum computers are devices, which allow more efficient solutions of problems as compared to their classical counterparts.As the timeline to developing a quantum-error corrected computer is unclear, the quantum computing community has dedicated much attention to developing algorithms for currently available noisy intermediate-scale quantum computers (NISQ).Thus far, within NISQ, optimization problems are one of the most commonly studied and are quite often tackled with the quantum approximate optimization algorithm (QAOA).This algorithm is best known for computing graph partitions with a maximal separation of edges (MaxCut), but can easily calculate other problems related to graphs.Here, I present a novel quantum optimization algorithm, which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem.Such an improved performance allowed me to partition graphs with 32 nodes on publicly available 5 qubit gate-based quantum computers without any preprocessing such as division of the graph into smaller subgraphs.These results represent a 40% increase in graph size as compared to state-of-art experiments on gate-based quantum computers such as Google Sycamore.The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal simulators of quantum computers.Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with simulators of quantum computers, again without any predivision into smaller subproblems and a lower solution bound of 67.9% is achieved.The study presented here paves way to using powerful genetic optimizer in synergy with quantum computers.
Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only O(log⁡N)O(\log N)O(logN) O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.
Quantum computers are devices which allow the solution of problems unsolvable to their classical counterparts. As an error-corrected quantum computer is still a decade away the quantum computing community has dedicated much attention to developing algorithms for currently available Noisy Intermediate-Scale Quantum computers (NISQ). Thus far, within NISQ, optimization problems are one of the most commonly studied and are exclusively tackled with the Quantum Approximate Optimization Algorithm (QAOA). This algorithm predominantly computes graph partitions with a maximal separation of edges (MaxCut), but can also be modified to calculate other properties of graphs. Here, I present a novel quantum optimization algorithm which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem. Such an improved performance allowed me to partition a graphs 32 nodes on publicly available 5 qubit gate-based solid state quantum devices without any preprocessing such as division of the graph into smaller subgraphs. This results represent a 40% increase in graph size as compared to state-of-art experiments on solid state devices such as Google Sycamore. The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal quantum simulators. Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with quantum simulators, again without any pre-division into smaller subproblems and a lower solution bound of 67.9% is achieved.
We develop new approximate compilation schemes that significantly reduce the expense of compiling the Quantum Approximate Optimization Algorithm (QAOA) for solving the Max-Cut problem. Our main focus is on compilation with trapped-ion simulators using Pauli- X operations and all-to-all Ising Hamiltonian H Ising evolution generated by Molmer-Sorensen or optical dipole force interactions, though some of our results also apply to standard gate-based compilations. Our results are based on principles of graph sparsification and decomposition; the former reduces the number of edges in a graph while maintaining its cut structure, while the latter breaks a weighted graph into a small number of unweighted graphs. Though these techniques have been used as heuristics in various hybrid quantum algorithms, there have been no guarantees on their performance, to the best of our knowledge. This work provides the first provable guarantees using sparsification and decomposition to improve quantum noise resilience and reduce quantum circuit complexity. For quantum hardware that uses edge-by-edge QAOA compilations, sparsification leads to a direct reduction in circuit complexity. For trapped-ion quantum simulators implementing all-to-all H I s i n g pulses, we show that for a ( 1 − ϵ ) factor loss in the Max-Cut approximation ( ϵ > 0 ) , our compilations improve the (worst-case) number of H I s i n g pulses from O ( n 2 ) to O ( n log ⁡ ( n / ϵ ) ) and the (worst-case) number of Pauli- X bit flips from O ( n 2 ) to O ( n log ⁡ ( n / ϵ ) ϵ 2 ) for n -node graphs. This is an asymptotic improvement for any constant ϵ > 0 . We demonstrate that significant improvements to the approximation ratio are obtained using decomposition in simulated trapped-ion experiments with dephasing noise. We further present a generic argument showing that sparsification results in an exponentially improved circuit fidelity lower bound in digital computing schemes based on one- and two-qubit gates, which are relevant to a wide variety of hardwares such as superconducting qubits and certain neutral atom or trapped ion setups, and more sophisticated noise models. We anticipate these approximate compilation techniques will be useful tools in a variety of future quantum computing experiments.