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

Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries

Jonas Nüßlein, Leo Sünkel, Jonas Stein, Tobias Rohe, Daniëlle Schuman, Claudia Linnhoff–Popien, Sebastian Feld

Published Nov 13, 2024• 0 citations
arXivHTMLPDF

Abstract

QAOA is a quantum algorithm for solving combinatorial optimization problems. It is capable of searching for the minimizing solution vector $x$ of a QUBO problem $x^TQx$. The number of two-qubit CNOT gates in the QAOA circuit scales linearly in the number of non-zero couplings of $Q$ and the depth of the circuit scales accordingly. Since CNOT operations have high error rates it is crucial to develop algorithms for reducing their number. We, therefore, present the concept of \textit{semi-symmetries} in QUBO matrices and an algorithm for identifying and factoring them out into ancilla qubits. \textit{Semi-symmetries} are prevalent in QUBO matrices of many well-known optimization problems like \textit{Maximum Clique}, \textit{Hamilton Cycles}, \textit{Graph Coloring}, \textit{Vertex Cover} and \textit{Graph Isomorphism}, among others. We theoretically show that our modified QUBO matrix $Q_{mod}$ describes the same energy spectrum as the original $Q$. Experiments conducted on the five optimization problems mentioned above demonstrate that our algorithm achieved reductions in the number of couplings by up to $49\%$ and in circuit depth by up to $41\%$.

DOI
10.48550/arxiv.2411.08824

Related papers

Reducing QUBO Density by Factoring out Semi-Symmetries

Jonas Nüßlein, Leo Sünkel, Jonas Stein +6 more

Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing are prominent approaches for solving combinatorial optimization problems, such as those formulated as Quadratic Unconstrained Binary Optimization (QUBO). These algorithms aim to minimize the objective function $x^T Q x$, where $Q$ is a QUBO matrix. However, the number of two-qubit CNOT gates in QAOA circuits and the complexity of problem embeddings in Quantum Annealing scale linearly with the number of non-zero couplings in $Q$, contributing to significant computational and error-related challenges. To address this, we introduce the concept of \textit{semi-symmetries} in QUBO matrices and propose an algorithm for identifying and factoring these symmetries into ancilla qubits. \textit{Semi-symmetries} frequently arise in optimization problems such as \textit{Maximum Clique}, \textit{Hamilton Cycles}, \textit{Graph Coloring}, and \textit{Graph Isomorphism}. We theoretically demonstrate that the modified QUBO matrix $Q_{\text{mod}}$ retains the same energy spectrum as the original $Q$. Experimental evaluations on the aforementioned problems show that our algorithm reduces the number of couplings and QAOA circuit depth by up to $45\%$. For Quantum Annealing, these reductions also lead to sparser problem embeddings, shorter qubit chains and better performance. This work highlights the utility of exploiting QUBO matrix structure to optimize quantum algorithms, advancing their scalability and practical applicability to real-world combinatorial problems.

arXiv:2412.17841•International Conference on Agents and Artificial Intelligence (ICAART)•Jan 1, 2025•1 citation

Optimized QAOA ansatz circuit design for two-body Hamiltonian problems

Ritajit Majumdar, Dhiraj Madan, Debasmita Bhoumik +3 more

Quantum Approximate Optimization Algorithm (QAOA) is a prospective candidate for providing quantum advantage in finding approximate solutions to optimization problems using near-term quantum devices. In this paper, the goal is to reduce the number of CNOT gates and the depth of quantum ansatz circuits for QAOA. First, we present a generalized QAOA formulation for any Hamiltonian that involves upto two-body interactions, as a graph. The circuit realization of the depth-p QAOA requires $2mp$ CNOT gates where the graph for the Hamiltonian has n vertices and m edges. Presently, a CNOT gate is one of the primary sources of error. We propose a graph-theoretic algorithm which can eliminate $n-1$ CNOTs from the QAOA ansatz while retaining functional equivalence with the original circuit. This improves upon previously proposed Depth First Search (DFS) method by restricting the increase in depth of the circuit, which was a drawback of the method, by $\simeq 84.8\%$ for Erdős-Renyi graphs. Finally, if the underlying connectivity (hardware coupling map) and the initial qubit placement for a hardware are known, then we present how to extend the greedy heuristic method in order to obtain a functionally equivalent circuit with $\simeq 5\%$; fewer SWAP gates for Erdős-Renyi graphs.

International Conference on VLSI Design•Jan 6, 2024•5 citations

Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm

James Ostrowski, Rebekah Herrman, Travis S. Humble +1 more

The quantum approximate optimization algorithm (QAOA) is a method of approximately solving combinatorial optimization problems. While QAOA is developed to solve a broad class of combinatorial optimization problems, it is not clear which classes of problems are best suited for it. One factor in demonstrating quantum advantage is the relationship between a problem instance and the circuit depth required to implement the QAOA method. As errors in NISQ devices increases exponentially with circuit depth, identifying lower bounds on circuit depth can provide insights into when quantum advantage could be feasible. Here, we identify how the structure of problem instances can be used to identify lower bounds for circuit depth for each iteration of QAOA and examine the relationship between problem structure and the circuit depth for a variety of combinatorial optimization problems including MaxCut and MaxIndSet. Specifically, we show how to derive a graph, $G$, that describes a general combinatorial optimization problem and show that the depth of circuit is at least the chromatic index of $G$. By looking at the scaling of circuit depth, we argue that MaxCut, MaxIndSet, and some instances of Vertex Covering and Boolean satisifiability problems are suitable for QAOA approaches while Knapsack and Traveling Sales Person problems are not.

arXiv:2008.01820•Aug 4, 2020•2 citations

QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem

Yiren Lu, Guojing Tian, Xiaoming Sun

Maximum cut (Max-Cut) problem is one of the most important combinatorial optimization problems because of its various applications in real life, and recently Quantum Approximate Optimization Algorithm (QAOA) has been widely employed to solve it. However, as the size of the problem increases, the number of qubits required will become larger. With the aim of saving qubits, we propose a coupling framework for designing QAOA circuits to solve larger-scale Max-Cut problem. This framework relies on a classical algorithm that approximately solves a certain variant of Max-Cut, and we derive an approximation guarantee theoretically, assuming the approximation ratio of the classical algorithm and QAOA. Furthermore we design a heuristic approach that fits in our framework and perform sufficient numerical experiments, where we solve Max-Cut on various $24$-vertex Erdős-Rényi graphs. Our framework only consumes $18$ qubits and achieves $0.9950$ approximation ratio on average, which outperforms the previous methods showing $0.9778$ (quantum algorithm using the same number of qubits) and $0.9643$ (classical algorithm). The experimental results indicate our well-designed quantum-classical coupling framework gives satisfactory approximation ratio while reduces the qubit cost, which sheds light on more potential computing power of NISQ devices.

arXiv:2307.15260•Jul 28, 2023•3 citations

Depth Optimized Ansatz Circuit in QAOA for Max-Cut

Ritajit Majumdar, Debasmita Bhoumik, Dhiraj Madan +3 more

While a Quantum Approximate Optimization Algorithm (QAOA) is intended to provide a quantum advantage in finding approximate solutions to combinatorial optimization problems, noise in the system is a hurdle in exploiting its full potential. Several error mitigation techniques have been studied to lessen the effect of noise on this algorithm. Recently, Majumdar et al. proposed a Depth First Search (DFS) based method to reduce $n-1$ CNOT gates in the ansatz design of QAOA for finding Max-Cut in a graph G = (V, E), |V| = n. However, this method tends to increase the depth of the circuit, making it more prone to relaxation error. The depth of the circuit is proportional to the height of the DFS tree, which can be $n-1$ in the worst case. In this paper, we propose an $O(Δ\cdot n^2)$ greedy heuristic algorithm, where $Δ$ is the maximum degree of the graph, that finds a spanning tree of lower height, thus reducing the overall depth of the circuit while still retaining the $n-1$ reduction in the number of CNOT gates needed in the ansatz. We numerically show that this algorithm achieves nearly 10 times increase in the probability of success for each iteration of QAOA for Max-Cut. We further show that although the average depth of the circuit produced by this heuristic algorithm still grows linearly with n, our algorithm reduces the slope of the linear increase from 1 to 0.11.

arXiv:2110.04637•Oct 9, 2021•3 citations

An Introduction to the Quantum Approximate Optimization Algorithm

Alessandro Giovagnoli

The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.

quant-pharXiv:2511.18377•Nov 25, 2025•0 citations
QAOA is a quantum algorithm for solving combinatorial optimization problems. It is capable of searching for the minimizing solution vector xxx of a QUBO problem xTQxx^TQxxTQx. The number of two-qubit CNOT gates in the QAOA circuit scales linearly in the number of non-zero couplings of QQQ and the depth of the circuit scales accordingly. Since CNOT operations have high error rates it is crucial to develop algorithms for reducing their number. We, therefore, present the concept of \textit{semi-symmetries} in QUBO matrices and an algorithm for identifying and factoring them out into ancilla qubits. \textit{Semi-symmetries} are prevalent in QUBO matrices of many well-known optimization problems like \textit{Maximum Clique}, \textit{Hamilton Cycles}, \textit{Graph Coloring}, \textit{Vertex Cover} and \textit{Graph Isomorphism}, among others. We theoretically show that our modified QUBO matrix QmodQ_{mod}Qmod​ describes the same energy spectrum as the original QQQ. Experiments conducted on the five optimization problems mentioned above demonstrate that our algorithm achieved reductions in the number of couplings by up to 49%49\%49% and in circuit depth by up to 41%41\%41%.
Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing are prominent approaches for solving combinatorial optimization problems, such as those formulated as Quadratic Unconstrained Binary Optimization (QUBO). These algorithms aim to minimize the objective function xTQxx^T Q xxTQx, where QQQ is a QUBO matrix. However, the number of two-qubit CNOT gates in QAOA circuits and the complexity of problem embeddings in Quantum Annealing scale linearly with the number of non-zero couplings in QQQ, contributing to significant computational and error-related challenges. To address this, we introduce the concept of \textit{semi-symmetries} in QUBO matrices and propose an algorithm for identifying and factoring these symmetries into ancilla qubits. \textit{Semi-symmetries} frequently arise in optimization problems such as \textit{Maximum Clique}, \textit{Hamilton Cycles}, \textit{Graph Coloring}, and \textit{Graph Isomorphism}. We theoretically demonstrate that the modified QUBO matrix QmodQ_{\text{mod}}Qmod​ retains the same energy spectrum as the original QQQ. Experimental evaluations on the aforementioned problems show that our algorithm reduces the number of couplings and QAOA circuit depth by up to 45%45\%45%. For Quantum Annealing, these reductions also lead to sparser problem embeddings, shorter qubit chains and better performance. This work highlights the utility of exploiting QUBO matrix structure to optimize quantum algorithms, advancing their scalability and practical applicability to real-world combinatorial problems.
Quantum Approximate Optimization Algorithm (QAOA) is a prospective candidate for providing quantum advantage in finding approximate solutions to optimization problems using near-term quantum devices. In this paper, the goal is to reduce the number of CNOT gates and the depth of quantum ansatz circuits for QAOA. First, we present a generalized QAOA formulation for any Hamiltonian that involves upto two-body interactions, as a graph. The circuit realization of the depth-p QAOA requires 2mp2mp2mp CNOT gates where the graph for the Hamiltonian has n vertices and m edges. Presently, a CNOT gate is one of the primary sources of error. We propose a graph-theoretic algorithm which can eliminate n−1n-1n−1 CNOTs from the QAOA ansatz while retaining functional equivalence with the original circuit. This improves upon previously proposed Depth First Search (DFS) method by restricting the increase in depth of the circuit, which was a drawback of the method, by ≃84.8%\simeq 84.8\%≃84.8% for Erdős-Renyi graphs. Finally, if the underlying connectivity (hardware coupling map) and the initial qubit placement for a hardware are known, then we present how to extend the greedy heuristic method in order to obtain a functionally equivalent circuit with ≃5%\simeq 5\%≃5%; fewer SWAP gates for Erdős-Renyi graphs.
The quantum approximate optimization algorithm (QAOA) is a method of approximately solving combinatorial optimization problems. While QAOA is developed to solve a broad class of combinatorial optimization problems, it is not clear which classes of problems are best suited for it. One factor in demonstrating quantum advantage is the relationship between a problem instance and the circuit depth required to implement the QAOA method. As errors in NISQ devices increases exponentially with circuit depth, identifying lower bounds on circuit depth can provide insights into when quantum advantage could be feasible. Here, we identify how the structure of problem instances can be used to identify lower bounds for circuit depth for each iteration of QAOA and examine the relationship between problem structure and the circuit depth for a variety of combinatorial optimization problems including MaxCut and MaxIndSet. Specifically, we show how to derive a graph, GGG, that describes a general combinatorial optimization problem and show that the depth of circuit is at least the chromatic index of GGG. By looking at the scaling of circuit depth, we argue that MaxCut, MaxIndSet, and some instances of Vertex Covering and Boolean satisifiability problems are suitable for QAOA approaches while Knapsack and Traveling Sales Person problems are not.
Maximum cut (Max-Cut) problem is one of the most important combinatorial optimization problems because of its various applications in real life, and recently Quantum Approximate Optimization Algorithm (QAOA) has been widely employed to solve it. However, as the size of the problem increases, the number of qubits required will become larger. With the aim of saving qubits, we propose a coupling framework for designing QAOA circuits to solve larger-scale Max-Cut problem. This framework relies on a classical algorithm that approximately solves a certain variant of Max-Cut, and we derive an approximation guarantee theoretically, assuming the approximation ratio of the classical algorithm and QAOA. Furthermore we design a heuristic approach that fits in our framework and perform sufficient numerical experiments, where we solve Max-Cut on various 242424-vertex Erdős-Rényi graphs. Our framework only consumes 181818 qubits and achieves 0.99500.99500.9950 approximation ratio on average, which outperforms the previous methods showing 0.97780.97780.9778 (quantum algorithm using the same number of qubits) and 0.96430.96430.9643 (classical algorithm). The experimental results indicate our well-designed quantum-classical coupling framework gives satisfactory approximation ratio while reduces the qubit cost, which sheds light on more potential computing power of NISQ devices.
While a Quantum Approximate Optimization Algorithm (QAOA) is intended to provide a quantum advantage in finding approximate solutions to combinatorial optimization problems, noise in the system is a hurdle in exploiting its full potential. Several error mitigation techniques have been studied to lessen the effect of noise on this algorithm. Recently, Majumdar et al. proposed a Depth First Search (DFS) based method to reduce n−1n-1n−1 CNOT gates in the ansatz design of QAOA for finding Max-Cut in a graph G = (V, E), |V| = n. However, this method tends to increase the depth of the circuit, making it more prone to relaxation error. The depth of the circuit is proportional to the height of the DFS tree, which can be n−1n-1n−1 in the worst case. In this paper, we propose an O(Δ⋅n2)O(Δ\cdot n^2)O(Δ⋅n2) greedy heuristic algorithm, where ΔΔΔ is the maximum degree of the graph, that finds a spanning tree of lower height, thus reducing the overall depth of the circuit while still retaining the n−1n-1n−1 reduction in the number of CNOT gates needed in the ansatz. We numerically show that this algorithm achieves nearly 10 times increase in the probability of success for each iteration of QAOA for Max-Cut. We further show that although the average depth of the circuit produced by this heuristic algorithm still grows linearly with n, our algorithm reduces the slope of the linear increase from 1 to 0.11.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.