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 FeldarXiv 2024 · DOI · arXiv

Abstract

QAOA is a quantum algorithm for solving combinatorial optimization problems by searching for the minimizing solution vector $x$ of a QUBO problem $x^TQx$. The number of two-qubit CNOT gates in a QAOA circuit scales linearly with the number of non-zero couplings in $Q$, leading to significant depth and high error rates on NISQ hardware. We present the concept of semi-symmetries in QUBO matrices and an algorithm for identifying and factoring them out into ancilla qubits. Semi-symmetries are prevalent in standard formulations of problems like Maximum Clique, Hamilton Cycles, and Vertex Cover. We demonstrate that our modified QUBO matrix $Q_{mod}$ preserves the energy spectrum of the original $Q$. Experimental results show reductions in couplings by up to 49% and circuit depth by up to 41%.

Introduction

The Quantum Approximate Optimization Algorithm (QAOA) is a primary candidate for demonstrating quantum advantage in the near term. However, its practical utility is limited by circuit depth. In the QUBO (Quadratic Unconstrained Binary Optimization) framework, every interaction or "coupling" between variables requires two-qubit CNOT gates. On current hardware, these gates are noisy and slow; excessive depth often causes the quantum state to decohere before a solution is reached.

While previous research has explored using full symmetries to simplify circuits, such symmetries are rare in real-world problem instances. This paper introduces a more flexible and common structure called semi-symmetry to address the depth bottleneck.

Methods: Factoring Semi-Symmetries

The proposed algorithm identifies and exploits redundant connections through a multi-step process:

  1. Identify Conflicting Qubits: The algorithm first locates pairs of qubits that cannot both be "1" in a valid solution, a common constraint in NP-hard problems.
  2. Detect Semi-Symmetries: It checks if these conflicting qubits share connections to at least three other qubits. This condition is far more frequent than full qubit-permutation symmetry.
  3. Ancilla Factoring: Instead of connecting both original qubits to every shared neighbor, the algorithm introduces an ancilla qubit to represent the state of the pair. Shared connections are moved to this ancilla, reducing the total number of couplings.
QUBO matrix $Q_{mod}$ after factoring out a semi-symmetry using an ancilla qubit.

Theoretical Foundation: Energy Landscape Preservation

A critical requirement for this transformation is that it must not "break" the underlying optimization problem. The authors mathematically prove that $Q_{mod}$ preserves the energy levels of the original problem for all valid solutions. For invalid solutions, the energy is guaranteed not to decrease, ensuring the quantum computer still converges toward the correct global minimum.

Comparison of the energy spectrum between the original QUBO $Q$ and the modified $Q_{mod}$ across various bitstrings.

This approach represents a strategic trade-off: using additional space (ancilla qubits) to save time (circuit depth). In the NISQ era, where coherence time is the scarcest resource, using spare qubits to compress gate operations is a highly effective optimization.

Experimental Results

The algorithm was evaluated on five classic NP-hard problems: Maximum Clique, Hamilton Cycles, Graph Coloring, Vertex Cover, and Graph Isomorphism. Using a budget of up to 29 ancilla qubits, the researchers achieved:

  • Coupling Reduction: Non-zero couplings were reduced by up to 49%.
  • Circuit Depth Reduction: Total depth after transpilation was reduced by up to 41%.
  • Problem Scaling: The best performance was observed in Hamilton Cycles (41% reduction), while even the most challenging case, Graph Coloring, saw a 33.5% reduction in depth for large instances.

Conclusion and Future Work

Factoring out semi-symmetries provides a robust path toward running deeper QAOA instances on near-term hardware. While the current study assumes flexible qubit connectivity, future work will focus on adapting these techniques for specific hardware topologies where SWAP gate overhead might impact gains. Additionally, benchmarking these factored circuits on actual noisy hardware will be essential to quantify the real-world improvement in solution quality.

Summary updated

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\%$.
BibTeX
@misc{nulein2024reducing,
  author = {Jonas Nüßlein and Leo Sünkel and Jonas Stein and Tobias Rohe and Daniëlle Schuman and Claudia Linnhoff‐Popien and Sebastian Feld},
  title = {{Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries}},
  year = {2024},
  eprint = {2411.08824},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.08824},
}
Figure