Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation Algorithm

Xin Wang

TL;DR

This paper introduces the Quantum Qubit Rotation Algorithm (QQRA) for solving the Max-cut problem on near-term quantum computers. QQRA achieves high accuracy and trainability by using simple single-qubit rotations, effectively trading expressiveness for a more robust optimization landscape, free from barren plateaus.

What Problem Does This Paper Address?

Near-term quantum computers, known as NISQ devices, hold promise for solving complex problems, but they face significant limitations due to noise and limited qubit coherence. Variational Quantum Algorithms (VQAs) are a leading approach to leverage these devices, but they grapple with two major challenges: expressibility (the ability of the quantum circuit to represent complex solutions) and trainability (the ease with which the circuit's parameters can be optimized). A common issue is the "barren plateau" phenomenon, where gradients become vanishingly small, making training extremely difficult. This paper specifically targets the Max-cut problem, a fundamental combinatorial optimization task, and aims to find a VQA that balances expressibility and trainability effectively.

Methods

The paper proposes a novel algorithm called the Quantum Qubit Rotation Algorithm (QQRA). Unlike more complex VQAs like QAOA, QQRA's quantum circuits are built solely from single-qubit rotation gates applied to each qubit. The parameters to be optimized are the rotation angles of these gates. The core idea is that for combinatorial optimization problems like Max-cut, where solutions are bit strings, a high degree of circuit expressiveness might not be necessary. Instead, this expressiveness can be traded for improved trainability. The authors argue that this simpler ansatz avoids the barren plateau problem, allowing for efficient training. They also analyze the Hessian matrix of the cost function to demonstrate the trainability of the parameters.

Datasets

The paper does not introduce new datasets. Instead, it evaluates the QQRA algorithm on various types of graphs, including:

  • 3-regular graphs
  • Cycle graphs
  • Complete graphs
  • Turán graphs

These are standard graph structures used for benchmarking optimization algorithms.

Key Insights and Ideas

  • Trading Expressiveness for Trainability: The central insight is that for problems with discrete, bit-string solutions (like Max-cut), one can sacrifice some circuit expressiveness to gain significantly better trainability. This is a crucial strategy for NISQ algorithms.
  • Barren Plateau Avoidance: By using only single-qubit rotations, QQRA circumvents the barren plateau problem that plagues deeper, more complex quantum circuits, leading to more reliable optimization.
  • Simplicity and Implementability: The QQRA's circuit structure is inherently simpler, making it more amenable to implementation on current NISQ hardware compared to more intricate VQAs.
  • High Approximation Ratio: The algorithm is shown to achieve an approximation ratio close to 1 for the Max-cut problem, meaning it can find solutions very close to the optimal one.

Key Results

  • Superior Performance to QAOA: In simulations, QQRA consistently outperforms the Quantum Approximate Optimization Algorithm (QAOA) for the Max-cut problem, especially as the depth of QAOA increases and trainability degrades. QQRA quickly converges to high-quality solutions.
  • Competitive with Classical Algorithms: QQRA demonstrates strong performance compared to the classical Goemans-Williamson (GW) algorithm. While GW excels on cycle graphs, QQRA is superior on 3-regular, complete, and Turán graphs. In simulations, QQRA was able to find the exact max-cut for 3-regular and complete graphs.
  • Approximation Ratio: For complete graphs, QQRA achieves an approximation ratio that approaches 1 as the number of vertices increases.
  • Efficient Training: The parameters in QQRA can be trained without encountering barren plateaus, leading to a more robust and efficient optimization process.

Limitations and Future Work

  • Focus on Max-cut: The current study is focused specifically on the Max-cut problem. The authors suggest that it would be interesting to explore the applicability of QQRA to other combinatorial problems that can be expressed in terms of bit strings.
  • Simulation-Based: The results are primarily based on numerical simulations. While promising, real-world performance on actual NISQ hardware would require further experimental validation.
  • "End Solution" Definition: The paper defines an "end solution" when parameters are either 0 or π. While this simplifies identification of local extrema, it might limit the exploration of the full parameter space.

The authors propose that QQRA's success in trading expressiveness for trainability in combinatorial optimization problems makes it a promising avenue for future research on other NP-hard problems.

Summary updated

Abstract

Optimizing parameterized quantum circuits promises efficient use of near-term quantum computers to achieve the potential quantum advantage. However, there is a notorious tradeoff between the expressibility and trainability of the parameter ansatz. We find that in combinatorial optimization problems, since the solutions are described by bit strings, one can trade the expressiveness of the ansatz for high trainability. To be specific, by focusing on the max-cut problem we introduce a simple yet efficient algorithm named Quantum Qubit Rotation Algorithm (QQRA). The quantum circuits are comprised with single-qubit rotation gates implementing on each qubit. The rotation angles of the gates can be trained free of barren plateaus. Thus, the approximate solution of the max-cut problem can be obtained with probability close to 1. To illustrate the effectiveness of QQRA, we compare it with the well known quantum approximate optimization algorithm and the classical Goemans-Williamson algorithm.
BibTeX
@misc{wang2021efficiently,
  author = {Xin Wang},
  title = {{Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation Algorithm}},
  year = {2021},
  eprint = {2110.08016},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.08016},
}
Figure