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

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

Saber Dinpazhouh

Published Aug 1, 2025• 0 citations
OpenAlex

Abstract

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.

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

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

Joel Rajakumar, Jai Moondra, Bryan Gard +2 more

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.

arXiv:2011.08165•Physical Review A•Aug 5, 2022•8 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

Encodings of the weighted MAX k-CUT problem on qubit systems

Franz Georg Fuchs, Ruben Pariente Bassa, Frida Lien

The weighted MAX k -CUT problem involves partitioning a weighted undirected graph into k subsets, or colors, to maximize the sum of the weights of edges between vertices in different subsets. This problem has significant applications across multiple domains. This study explores encoding methods for MAX k -CUT on qubit systems by utilizing quantum approximate optimization algorithms (QAOA) and addressing the challenge of encoding integer values on quantum devices with binary variables. We examine various encoding schemes and evaluate the efficiency of these approaches. The study presents a systematic and resource-efficient method to implement the phase separation operator for the cost function of the MAX k -CUT problem. When encoding the problem into the full Hilbert space, we show the importance of encoding the colors in a balanced way. We also explore the option of encoding the problem into a suitable subspace by designing suitable state preparations and constrained mixers (LX- and Grover-mixer). Numerical simulations on weighted and unweighted graph instances demonstrate the effectiveness of these encoding schemes, particularly in optimizing circuit depth, approximation ratios, and computational efficiency.

arXiv:2411.08594•Frontiers in Quantum Science and Technology•Dec 4, 2025•0 citations

A Max K-Cut Implementation for QAOA in the Measurement Based Quantum Computing Formalism

Sebastiano Corli, Daniele Dragoni, Massimiliano Proietti +3 more

The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•12 citations

SOLVING THE MAX-CUT PROBLEM USING THE QASPA ALGORITHM

Д. О. САПОЖНИК

A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max-Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a single-qubit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system. After circuit execution, the qubits are measured in the standard computational basis, and the resulting probability distribution allows the selection of the most probable partition as an approximate solution to the problem. Experimental studies conducted on quantum processor simulators have demonstrated that the proposed algorithm achieves accuracy comparable to the Variational Quantum Approximate Optimization Algorithm (QAOA) while significantly reducing computation time due to the absence of iterative parameter optimization. Moreover, as the graph size increases, the algorithm's runtime grows considerably slower compared to classical brute-force approaches and QAOA, confirming its potential for solving medium-sized Max-Cut problems.

Bulletin of National Technical University KhPI Series System Analysis Control and Information Technologies•Dec 29, 2025•0 citations
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.
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 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{\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.
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.
The weighted MAX k -CUT problem involves partitioning a weighted undirected graph into k subsets, or colors, to maximize the sum of the weights of edges between vertices in different subsets. This problem has significant applications across multiple domains. This study explores encoding methods for MAX k -CUT on qubit systems by utilizing quantum approximate optimization algorithms (QAOA) and addressing the challenge of encoding integer values on quantum devices with binary variables. We examine various encoding schemes and evaluate the efficiency of these approaches. The study presents a systematic and resource-efficient method to implement the phase separation operator for the cost function of the MAX k -CUT problem. When encoding the problem into the full Hilbert space, we show the importance of encoding the colors in a balanced way. We also explore the option of encoding the problem into a suitable subspace by designing suitable state preparations and constrained mixers (LX- and Grover-mixer). Numerical simulations on weighted and unweighted graph instances demonstrate the effectiveness of these encoding schemes, particularly in optimizing circuit depth, approximation ratios, and computational efficiency.
The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.
A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max-Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a single-qubit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system. After circuit execution, the qubits are measured in the standard computational basis, and the resulting probability distribution allows the selection of the most probable partition as an approximate solution to the problem. Experimental studies conducted on quantum processor simulators have demonstrated that the proposed algorithm achieves accuracy comparable to the Variational Quantum Approximate Optimization Algorithm (QAOA) while significantly reducing computation time due to the absence of iterative parameter optimization. Moreover, as the graph size increases, the algorithm's runtime grows considerably slower compared to classical brute-force approaches and QAOA, confirming its potential for solving medium-sized Max-Cut problems.