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

Depth Optimized Ansatz Circuit in QAOA for Max-Cut

Ritajit Majumdar, Debasmita Bhoumik, Dhiraj Madan, Dhinakaran Vinayagamurthy, Shesha Raghunathan, Susmita Sur‐Kolay

Published Oct 9, 2021• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2110.04637

Related papers

Optimizing Ansatz Design in QAOA for Max-cut

Ritajit Majumdar, Dhiraj Madan, Debasmita Bhoumik +3 more

Quantum Approximate Optimization Algorithm (QAOA) is studied primarily to find approximate solutions to combinatorial optimization problems. For a graph with $n$ vertices and $m$ edges, a depth $p$ QAOA for the Max-cut problem requires $2\cdot m \cdot p$ CNOT gates. CNOT is one of the primary sources of error in modern quantum computers. In this paper, we propose two hardware independent methods to reduce the number of CNOT gates in the circuit. First, we present a method based on Edge Coloring of the input graph that minimizes the the number of cycles (termed as depth of the circuit), and reduces upto $\lfloor \frac{n}{2} \rfloor$ CNOT gates. Next, we depict another method based on Depth First Search (DFS) on the input graph that reduces $n-1$ CNOT gates, but increases depth of the circuit moderately. We analytically derive the condition for which the reduction in CNOT gates overshadows this increase in depth, and the error probability of the circuit is still lowered. We show that all IBM Quantum Hardware satisfy this condition. We simulate these two methods for graphs of various sparsity with the \textit{ibmq\_manhattan} noise model, and show that the DFS based method outperforms the edge coloring based method, which in turn, outperforms the traditional QAOA circuit in terms of reduction in the number of CNOT gates, and hence the probability of error of the circuit.

arXiv:2106.02812•Jun 5, 2021•18 citations

RESEARCH AND DEVELOPMENT OF DEPTH OPTIMIZED CIRCUITS IN QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM

S. M. Gushanskiy, Viktor Potapov, Божич Владимир Иванович

One of the main challenges faced by researchers in the field of quantum computing is the problemof noise in quantum systems. Noise can significantly limit the performance of quantum algorithms.It is in this context that our research, aimed at the development and optimization of quantumalgorithms with a focus on depth, is updated. The depth of quantum circuits is one of the critical parametersin the development of quantum algorithms. Optimized circuits with improved depth have the potential to significantly reduce the impact of noise, which in turn should lead to improved efficiency.We aim to provide solutions that not only address technical constraints, but also provide practicalresults for quantum computing in the context of optimization problems. This study analyzes the use ofa quantum approximate optimization algorithm for solving complex combinatorial optimizationproblems. However, in the process of using this algorithm we encounter a serious limitation – noisein the quantum system, which significantly reduces its efficiency. To overcome the influence of noiseand improve the efficiency of quantum algorithms, several methods have been proposed. This paperpresents a greedy heuristic algorithm aimed at reducing the impact of noise. The main goal of thisalgorithm is to find a spanning tree of minimum height. This, in turn, reduces the overall depth ofquantum circuits and minimizes the number of CNOT gates, which is key to optimizing quantumcomputing. Through numerical analysis, it was demonstrated that the proposed greedy heuristicalgorithm is capable of significantly increasing the probability of successful completion of each iterationin the problem of finding the maximum cut in a graph by 10 times. Moreover, the study confirmsthat the average depth of the quantum circuit generated by the proposed heuristic algorithm is stilllinearly dependent on the size of the input data, but the slope of this linear dependence is reducedfrom 1 to 0.11 by using the proposed method.

Известия Южного федерального университета. Технические науки•Nov 12, 2023•0 citations

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

Design of quantum approximation optimization algorithm for the maximum cut problem

Yun-Jiang Wang, XI Huiming, XIAO Zhuoyan +2 more

The max-cut problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various fields, including statistical physics and image processing. However, except for some special cases, the MCP still encounters a non-deterministic polynomial complete problem (an NP-complete problem), and there is currently no known efficient classical algorithm that can solve it in polynomial time. The quantum approximate optimization algorithm (QAOA), as a pivotal algorithm in the noisy intermediate-scale quantum (NISQ) computing era, has shown significant potential for solving the MCP. However, due to the lack of quantum error correction, the reliability of computations in NISQ systems sharply declines as the circuit depth of the algorithm increases. Therefore, designing an efficient, shallow-depth, and low-complexity QAOA for the MCP is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.In this paper, according to the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the MCP. By enhancing the flexibility of quantum trial functions and improving the efficiency of Hilbert space exploration within a single iteration, we significantly improve the performance of QAOA on the MCP.We conduct extensive numerical simulations using the MindSpore quantum platform, and compare the proposed RY-layer-assisted QAOA with standard QAOA and its existing variants, including MA-QAOA and QAOA+. The experiments are performed on various graph types, including complete graphs, 3-regular graphs, 4-regular graphs, and random graphs with edge probabilities between 0.3 and 0.5. Our results show that the RY-layer-assisted QAOA achieves higher approximation ratios in all graph types, particularly in regular and random graphs, where traditional QAOA variants are difficult to implement. Moreover, the proposed method exhibits strong robustness as the graph size increases, and can maintain high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth than the standard QAOA and its variants, making it more suitable for NISQ devices with limited coherence times and high error rates.In conclusion, the RY-layer-assisted QAOA provides a promising approach for solving MCP in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, thus paving the way for developing more efficient and reliable quantum optimization algorithms.

Acta Physica Sinica•Jan 1, 2025•0 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

Multi-angle quantum approximate optimization algorithm

Rebekah Herrman, Phillip C. Lotshaw, James Ostrowski +2 more

The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.

arXiv:2109.11455•Scientific Reports•Apr 26, 2022•117 citations
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.
Quantum Approximate Optimization Algorithm (QAOA) is studied primarily to find approximate solutions to combinatorial optimization problems. For a graph with nnn vertices and mmm edges, a depth ppp QAOA for the Max-cut problem requires 2⋅m⋅p2\cdot m \cdot p2⋅m⋅p CNOT gates. CNOT is one of the primary sources of error in modern quantum computers. In this paper, we propose two hardware independent methods to reduce the number of CNOT gates in the circuit. First, we present a method based on Edge Coloring of the input graph that minimizes the the number of cycles (termed as depth of the circuit), and reduces upto ⌊n2⌋\lfloor \frac{n}{2} \rfloor⌊2n​⌋ CNOT gates. Next, we depict another method based on Depth First Search (DFS) on the input graph that reduces n−1n-1n−1 CNOT gates, but increases depth of the circuit moderately. We analytically derive the condition for which the reduction in CNOT gates overshadows this increase in depth, and the error probability of the circuit is still lowered. We show that all IBM Quantum Hardware satisfy this condition. We simulate these two methods for graphs of various sparsity with the \textit{ibmq\_manhattan} noise model, and show that the DFS based method outperforms the edge coloring based method, which in turn, outperforms the traditional QAOA circuit in terms of reduction in the number of CNOT gates, and hence the probability of error of the circuit.
One of the main challenges faced by researchers in the field of quantum computing is the problemof noise in quantum systems. Noise can significantly limit the performance of quantum algorithms.It is in this context that our research, aimed at the development and optimization of quantumalgorithms with a focus on depth, is updated. The depth of quantum circuits is one of the critical parametersin the development of quantum algorithms. Optimized circuits with improved depth have the potential to significantly reduce the impact of noise, which in turn should lead to improved efficiency.We aim to provide solutions that not only address technical constraints, but also provide practicalresults for quantum computing in the context of optimization problems. This study analyzes the use ofa quantum approximate optimization algorithm for solving complex combinatorial optimizationproblems. However, in the process of using this algorithm we encounter a serious limitation – noisein the quantum system, which significantly reduces its efficiency. To overcome the influence of noiseand improve the efficiency of quantum algorithms, several methods have been proposed. This paperpresents a greedy heuristic algorithm aimed at reducing the impact of noise. The main goal of thisalgorithm is to find a spanning tree of minimum height. This, in turn, reduces the overall depth ofquantum circuits and minimizes the number of CNOT gates, which is key to optimizing quantumcomputing. Through numerical analysis, it was demonstrated that the proposed greedy heuristicalgorithm is capable of significantly increasing the probability of successful completion of each iterationin the problem of finding the maximum cut in a graph by 10 times. Moreover, the study confirmsthat the average depth of the quantum circuit generated by the proposed heuristic algorithm is stilllinearly dependent on the size of the input data, but the slope of this linear dependence is reducedfrom 1 to 0.11 by using the proposed method.
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 max-cut problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various fields, including statistical physics and image processing. However, except for some special cases, the MCP still encounters a non-deterministic polynomial complete problem (an NP-complete problem), and there is currently no known efficient classical algorithm that can solve it in polynomial time. The quantum approximate optimization algorithm (QAOA), as a pivotal algorithm in the noisy intermediate-scale quantum (NISQ) computing era, has shown significant potential for solving the MCP. However, due to the lack of quantum error correction, the reliability of computations in NISQ systems sharply declines as the circuit depth of the algorithm increases. Therefore, designing an efficient, shallow-depth, and low-complexity QAOA for the MCP is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.In this paper, according to the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the MCP. By enhancing the flexibility of quantum trial functions and improving the efficiency of Hilbert space exploration within a single iteration, we significantly improve the performance of QAOA on the MCP.We conduct extensive numerical simulations using the MindSpore quantum platform, and compare the proposed RY-layer-assisted QAOA with standard QAOA and its existing variants, including MA-QAOA and QAOA+. The experiments are performed on various graph types, including complete graphs, 3-regular graphs, 4-regular graphs, and random graphs with edge probabilities between 0.3 and 0.5. Our results show that the RY-layer-assisted QAOA achieves higher approximation ratios in all graph types, particularly in regular and random graphs, where traditional QAOA variants are difficult to implement. Moreover, the proposed method exhibits strong robustness as the graph size increases, and can maintain high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth than the standard QAOA and its variants, making it more suitable for NISQ devices with limited coherence times and high error rates.In conclusion, the RY-layer-assisted QAOA provides a promising approach for solving MCP in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, thus paving the way for developing more efficient and reliable quantum optimization algorithms.
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.
The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.