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

International Conference on Parallel Architectures and Compilation Techniques (PACT)

Recompiling QAOA Circuits on Various Rotational Directions

Enhyeok Jang, Dongho Ha, Seungwoo Choi, Youngmin Kim, Jaewon Kwon, Yongju Lee, Sungwoo Ahn, H J Kim, Won Woo Ro

Published Oct 11, 2024• 6 citations
Publisher

Abstract

The quantum approximate optimization algorithm (QAOA) is introduced to efficiently solve combinatorial optimization problems. Despite the promise of QAOA, the cost of executing QAOA circuits at scale for quantum advantage may still be excessive for the near-future quantum device. We observe the increasing overhead of QAOA circuit execution in the native gate translation. To execute QAOA circuits on a real quantum computing device, Hamiltonians composed of predefined specific rotations (e.g., ZZ and X) should be decomposed into finite native gates. By adopting rotational combinations that utilize native gates more directly than the standard QAOA circuit model, the execution cost on real quantum devices can be reduced. In this study, we propose Racoon (Rotational Space Virtualization for QAOA Ansatz), an algorithm-hardware co-design approach that revisits the synthesis conditions of QAOA circuits and selects alternative candidates with different rotational combinations. Our analysis of six commercial quantum processors demonstrates that applying Racoon to QAOA circuits for the 4-node Sherrington-Kirkpatrick model reduces the number of native gates by an average of 23% and up to 79%. Consequently, using Racoon results in 43% fewer training epochs, 41% lower training energy consumption, and a 6% improvement in inference on average compared to standard QAOA. Racoon consistently reduces circuit depth as the number of qubits and layers increases, achieving 123 × more circuit depth reduction compared to the recently proposed Depth First Search (DFS)-based method. Furthermore, we confirm that Racoon’s method can be extended to State-of-The-Art QAOAs with modified ansätze and to the variational quantum eigensolver (VQE).

DOI
10.1145/3656019.3676899

Related papers

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•6 citations

Variational Ansatz preparation to avoid CNOT-gates on noisy quantum devices for combinatorial optimizations

Tsukasa Miki, Ryo Okita, Moe Shimada +2 more

The variational quantum eigensolver (VQE), which is a quantum–classical hybrid approach, has latent powers to leverage near-term quantum devices by effectively managing a limited number of qubits with finite coherent lifetimes. While it is generally argued that the quantum approximate optimization algorithm (QAOA), which is a special case of VQE with a variational Ansatz based on the adiabatic theorem, may enable practical applications of noisy quantum devices for classical combinatorial optimizations, the strategy to improve the performance of this algorithm by increasing the circuit depth conflicts with the limited coherence time of near-term quantum devices. Here, we introduce strategies involving the VQE to reduce the circuit resources required for solving combinatorial optimizations. Our concept of a parameterized quantum circuit allows the Ansatz preparation to be achieved by only single-qubit operation. We find that the variational Ansatz without controlled X-gates leads to quick convergence in a classical subroutine used to determine the variational parameters. In addition, the variational Ansatz with optimized parameters maintains performance over the problem sizes both on the numerical simulation and IBM 27-qubit processor “ibm_kawasaki.” Therefore, the variational Ansatz introduced in this study has several advantages considering the total calculation time and performance scaling over the problem sizes. We also show that the variational Ansatz consisting of a lower number of gate operations than that of QAOA can approximate the eigenstates of diagonal Hamiltonians with high accuracy. We illustrate our ideas with a maximum-cut problem and show that near-term quantum applications may be feasible using short-depth circuits.

AIP Advances•Mar 1, 2022•16 citations

Circuit Compilation Methodologies for Quantum Approximate Optimization Algorithm

Mahabubul Alam, Abdullah Ash Saki, Swaroop Ghosh

The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid algorithm to solve hard combinatorial optimization problems. The multi-qubit CPHASE gates used in the quantum circuit for QAOA are commutative i.e., the order of the gates can be altered without changing the output state. This re-ordering leads to the execution of more gates in parallel and a smaller number of additional SWAP gates to compile the QAOA-circuit. Consequently, the circuit-depth and cumulative gate-count become lower which is beneficial for circuit execution time and noise resilience. A less number of gates indicates a lower accumulation of gate-errors, and a reduced circuit-depth means less decoherence time for the qubits. However, finding the best-ordered circuit is a difficult problem and does not scale well with circuit size. This paper presents four generic methodologies to optimize QAOA-circuits by exploiting gate re-ordering. We demonstrate a reduction in gate-count by ≈23.0% and circuit-depth by ≈53.0% on average over a conventional approach without incurring any compilation-time penalty. We also present a variation-aware compilation which enhances the compiled circuit success probability by ≈62.7% for the target hardware over the variation unaware approach. A new metric, Approximation Ratio Gap (ARG), is proposed to validate the quality of the compiled QAOA-circuit instances on actual devices. Hardware implementation of a number of QAOA instances shows ≈25.8% improvement in the proposed metric on average over the conventional approach on ibmq 16 melbourne.

IEEE/ACM International Symposium on Microarchitecture (MICRO)•Oct 1, 2020•78 citations

Transferring linearly fixed QAOA angles: performance and real device results

Ryo Sakai, Hiromichi Matsuyama, Wai-Hong Tam +1 more

Quantum Approximate Optimization Algorithm (QAOA) enables solving combinatorial optimization problems on quantum computers by optimizing variational parameters for quantum circuits. We investigate a simplified approach that combines linear parameterization with parameter transferring, reducing the parameter space to just 4 dimensions regardless of the number of layers. This simplification draws inspiration from quantum annealing schedules providing both theoretical grounding and practical advantages. We compare this combined approach with standard QAOA and other parameter setting strategies such as INTERP and FOURIER, which require computationally demanding incremental layer-by-layer optimization. Notably, previously known methods like INTERP and FOURIER yield parameters that can be well fitted by linear functions, which supports our linearization strategy. Our analysis reveals that for the random Ising model, cost landscapes in this reduced parameter space demonstrate consistent structural patterns across different problem instances. Our experiments extend from classical simulation to actual quantum hardware implementation on IBM's Eagle processor, demonstrating the approach's viability on current NISQ devices. Furthermore, the numerical results indicate that parameter transferability primarily depends on the energy scale of problem instances, with normalization techniques improving transfer quality. Most of our numerical experiments are conducted on the random Ising model, while problem-dependence is also investigated across other models. A key advantage of parameter transferring is the complete elimination of instance-specific classical optimization overhead, as pre-trained parameters can be directly applied to other problem instances, reducing classical optimization costs by orders of magnitude for deeper circuits.

arXiv:2504.12632•Apr 17, 2025•7 citations

Optimized SWAP networks with equivalent circuit averaging for QAOA

Akel Hashim, Rich Rines, Victory Omole +6 more

The SWAP network is a qubit routing sequence that can be used to efficiently execute the Quantum Approximate Optimization Algorithm (QAOA). Even with a minimally connected topology on an $n$-qubit processor, this routing sequence enables $\mathcal{O}({n}^{2})$ operations to execute in $\mathcal{O}(n)$ steps. In this work, we optimize the execution of SWAP networks for QAOA through two techniques. First, we take advantage of an overcomplete set of native hardware operations [including 150-ns controlled-$\frac{\ensuremath{\pi}}{2}$ phase gates with up to 99.67(1)% fidelity] to decompose the relevant quantum gates and SWAP networks in a manner which minimizes circuit depth and maximizes gate cancellation. Second, we introduce equivalent circuit averaging, which randomizes over degrees of freedom in the quantum circuit compilation to reduce the impact of systematic coherent errors. Our techniques are experimentally validated at the Advanced Quantum Testbed through the execution of QAOA circuits for finding the ground state of two- and four-node Sherrington-Kirkpatrick spin-glass models with various randomly sampled parameters. We observe a $\ensuremath{\sim}60%$ average reduction in error (total variation distance) for QAOA of depth $p=1$ on four transmon qubits on a superconducting quantum processor.

arXiv:2111.04572•Physical Review Research•Jul 11, 2022•47 citations

Compiler Optimizations for QAOA

Yuchen Zhu, Yidong Zhou, Jinglei Cheng +4 more

The Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising candidates for achieving quantum advantage over classical computers. However, existing compilers lack specialized methods for optimizing QAOA circuits. There are circuit patterns inside the QAOA circuits, and current quantum hardware has specific qubit connectivity topologies. Therefore, we propose Coqa to optimize QAOA circuit compilation tailored to different types of quantum hardware. Our method integrates a linear nearest-neighbor (LNN) topology and efficiently map the patterns of QAOA circuits to the LNN topology by heuristically checking the interaction based on the weight of problem Hamiltonian. This approach allows us to reduce the number of SWAP gates during compilation, which directly impacts the circuit depth and overall fidelity of the quantum computation. By leveraging the inherent patterns in QAOA circuits, our approach achieves more efficient compilation compared to general-purpose compilers. With our proposed method, we are able to achieve an average of 30% reduction in gate count and a 39x acceleration in compilation time across our benchmarks.

arXiv:2408.08365•Oct 27, 2024•8 citations
The quantum approximate optimization algorithm (QAOA) is introduced to efficiently solve combinatorial optimization problems. Despite the promise of QAOA, the cost of executing QAOA circuits at scale for quantum advantage may still be excessive for the near-future quantum device. We observe the increasing overhead of QAOA circuit execution in the native gate translation. To execute QAOA circuits on a real quantum computing device, Hamiltonians composed of predefined specific rotations (e.g., ZZ and X) should be decomposed into finite native gates. By adopting rotational combinations that utilize native gates more directly than the standard QAOA circuit model, the execution cost on real quantum devices can be reduced. In this study, we propose Racoon (Rotational Space Virtualization for QAOA Ansatz), an algorithm-hardware co-design approach that revisits the synthesis conditions of QAOA circuits and selects alternative candidates with different rotational combinations. Our analysis of six commercial quantum processors demonstrates that applying Racoon to QAOA circuits for the 4-node Sherrington-Kirkpatrick model reduces the number of native gates by an average of 23% and up to 79%. Consequently, using Racoon results in 43% fewer training epochs, 41% lower training energy consumption, and a 6% improvement in inference on average compared to standard QAOA. Racoon consistently reduces circuit depth as the number of qubits and layers increases, achieving 123 × more circuit depth reduction compared to the recently proposed Depth First Search (DFS)-based method. Furthermore, we confirm that Racoon’s method can be extended to State-of-The-Art QAOAs with modified ansätze and to the variational quantum eigensolver (VQE).
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 variational quantum eigensolver (VQE), which is a quantum–classical hybrid approach, has latent powers to leverage near-term quantum devices by effectively managing a limited number of qubits with finite coherent lifetimes. While it is generally argued that the quantum approximate optimization algorithm (QAOA), which is a special case of VQE with a variational Ansatz based on the adiabatic theorem, may enable practical applications of noisy quantum devices for classical combinatorial optimizations, the strategy to improve the performance of this algorithm by increasing the circuit depth conflicts with the limited coherence time of near-term quantum devices. Here, we introduce strategies involving the VQE to reduce the circuit resources required for solving combinatorial optimizations. Our concept of a parameterized quantum circuit allows the Ansatz preparation to be achieved by only single-qubit operation. We find that the variational Ansatz without controlled X-gates leads to quick convergence in a classical subroutine used to determine the variational parameters. In addition, the variational Ansatz with optimized parameters maintains performance over the problem sizes both on the numerical simulation and IBM 27-qubit processor “ibm_kawasaki.” Therefore, the variational Ansatz introduced in this study has several advantages considering the total calculation time and performance scaling over the problem sizes. We also show that the variational Ansatz consisting of a lower number of gate operations than that of QAOA can approximate the eigenstates of diagonal Hamiltonians with high accuracy. We illustrate our ideas with a maximum-cut problem and show that near-term quantum applications may be feasible using short-depth circuits.
The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid algorithm to solve hard combinatorial optimization problems. The multi-qubit CPHASE gates used in the quantum circuit for QAOA are commutative i.e., the order of the gates can be altered without changing the output state. This re-ordering leads to the execution of more gates in parallel and a smaller number of additional SWAP gates to compile the QAOA-circuit. Consequently, the circuit-depth and cumulative gate-count become lower which is beneficial for circuit execution time and noise resilience. A less number of gates indicates a lower accumulation of gate-errors, and a reduced circuit-depth means less decoherence time for the qubits. However, finding the best-ordered circuit is a difficult problem and does not scale well with circuit size. This paper presents four generic methodologies to optimize QAOA-circuits by exploiting gate re-ordering. We demonstrate a reduction in gate-count by ≈23.0% and circuit-depth by ≈53.0% on average over a conventional approach without incurring any compilation-time penalty. We also present a variation-aware compilation which enhances the compiled circuit success probability by ≈62.7% for the target hardware over the variation unaware approach. A new metric, Approximation Ratio Gap (ARG), is proposed to validate the quality of the compiled QAOA-circuit instances on actual devices. Hardware implementation of a number of QAOA instances shows ≈25.8% improvement in the proposed metric on average over the conventional approach on ibmq 16 melbourne.
Quantum Approximate Optimization Algorithm (QAOA) enables solving combinatorial optimization problems on quantum computers by optimizing variational parameters for quantum circuits. We investigate a simplified approach that combines linear parameterization with parameter transferring, reducing the parameter space to just 4 dimensions regardless of the number of layers. This simplification draws inspiration from quantum annealing schedules providing both theoretical grounding and practical advantages. We compare this combined approach with standard QAOA and other parameter setting strategies such as INTERP and FOURIER, which require computationally demanding incremental layer-by-layer optimization. Notably, previously known methods like INTERP and FOURIER yield parameters that can be well fitted by linear functions, which supports our linearization strategy. Our analysis reveals that for the random Ising model, cost landscapes in this reduced parameter space demonstrate consistent structural patterns across different problem instances. Our experiments extend from classical simulation to actual quantum hardware implementation on IBM's Eagle processor, demonstrating the approach's viability on current NISQ devices. Furthermore, the numerical results indicate that parameter transferability primarily depends on the energy scale of problem instances, with normalization techniques improving transfer quality. Most of our numerical experiments are conducted on the random Ising model, while problem-dependence is also investigated across other models. A key advantage of parameter transferring is the complete elimination of instance-specific classical optimization overhead, as pre-trained parameters can be directly applied to other problem instances, reducing classical optimization costs by orders of magnitude for deeper circuits.
The SWAP network is a qubit routing sequence that can be used to efficiently execute the Quantum Approximate Optimization Algorithm (QAOA). Even with a minimally connected topology on an nnn-qubit processor, this routing sequence enables O(n2)\mathcal{O}({n}^{2})O(n2) operations to execute in O(n)\mathcal{O}(n)O(n) steps. In this work, we optimize the execution of SWAP networks for QAOA through two techniques. First, we take advantage of an overcomplete set of native hardware operations [including 150-ns controlled-$\frac{\ensuremath{\pi}}{2}$ phase gates with up to 99.67(1)% fidelity] to decompose the relevant quantum gates and SWAP networks in a manner which minimizes circuit depth and maximizes gate cancellation. Second, we introduce equivalent circuit averaging, which randomizes over degrees of freedom in the quantum circuit compilation to reduce the impact of systematic coherent errors. Our techniques are experimentally validated at the Advanced Quantum Testbed through the execution of QAOA circuits for finding the ground state of two- and four-node Sherrington-Kirkpatrick spin-glass models with various randomly sampled parameters. We observe a $\ensuremath{\sim}60%$ average reduction in error (total variation distance) for QAOA of depth p=1p=1p=1 on four transmon qubits on a superconducting quantum processor.
The Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising candidates for achieving quantum advantage over classical computers. However, existing compilers lack specialized methods for optimizing QAOA circuits. There are circuit patterns inside the QAOA circuits, and current quantum hardware has specific qubit connectivity topologies. Therefore, we propose Coqa to optimize QAOA circuit compilation tailored to different types of quantum hardware. Our method integrates a linear nearest-neighbor (LNN) topology and efficiently map the patterns of QAOA circuits to the LNN topology by heuristically checking the interaction based on the weight of problem Hamiltonian. This approach allows us to reduce the number of SWAP gates during compilation, which directly impacts the circuit depth and overall fidelity of the quantum computation. By leveraging the inherent patterns in QAOA circuits, our approach achieves more efficient compilation compared to general-purpose compilers. With our proposed method, we are able to achieve an average of 30% reduction in gate count and a 39x acceleration in compilation time across our benchmarks.