New advances in quantum approximation optimization algorithm research by Hongyuan Quantum and CSU research team
Recently, a team of researchers from the University of Science and Technology of China (USTC) has made recent progress in the Quantum Approximate Optimization Algorithm (QAOA). The research demonstrates that the S-QAOA algorithm (Shortcuts to Quantum Approximate Optimization Algorithm) is ideal for solving combinatorial optimization problems using noise-laden quantum computers at this stage. This research further advances the application of quantum computing to combinatorial optimization problems.
The paper is available at: https://arxiv.org/abs/2112.10943
Combinatorial optimization problems have a wide range of real-life applications, for example, many problems in logistics, scheduling, finance, and other fields are combinatorial optimization problems. And many combinatorial optimization problems correspond to classical algorithms with high complexity, which makes it difficult for classical computers to find the optimal solutions to these problems quickly when the problem size is large. Therefore, it is important to use quantum computing to accelerate the solution of combinatorial optimization problems, where the well-known QAOA algorithm is expected to achieve exponential speedups in the solution of combinatorial optimization problems.
In the noise-containing intermediate-scale (NISQ) quantum era, the number of reliable quantum operations is limited by quantum noise (which currently includes quantum decoherence, rotational errors, etc.). As a result, there is an interest in hybrid quantum-classical algorithms, which can optimize parameters in the quantum line with the help of classical optimizers to choose the optimal evolutionary path to reduce the quantum line depth. One of the more well-known classes of hybrid quantum-classical algorithms is the Quantum Approximate Optimization Algorithm (QAOA), designed to find the ground state of the target Hamiltonian quantity, which promises to bring exponential speed-ups to the solution of approximate solutions to combinatorial optimization problems.
In theory, QAOA can yield better approximate solutions if the quantum line is deep enough. However, since errors due to quantum noise accumulate with increasing quantum line depth, the performance of QAOA actually decreases when the quantum line depth is large. Therefore, demonstrating the benefits of the QAOA algorithm on current quantum computers is a challenging task, and reducing the line depth of the QAOA algorithm is important to demonstrate the benefits of the QAOA algorithm on current stage quantum computers.
In order to reduce the depth of quantum circuits, researchers have proposed a new idea called "Shortcuts to QAOA": (S-QAOA). Firstly, additional two-body interactions are considered in S-QAOA, and double gates associated with YY interactions are added to the quantum circuit to compensate for non-adiabatic effects, thus accelerating the quantum annealing process and speeding up the optimization of QAOA; secondly, the parametric degrees of freedom of two-body interactions (including ZZ interactions and YY interactions) are released to enhance the representation capability of the quantum circuit, thus reducing the depth of the quantum circuit. The numerical simulation results show that S-QAOA can obtain better results in the case of shallower quantum lines compared with QAOA.
Application of S-QAOA to the u3R-MaxCut problem (Figure 1) and the w3R-MaxCut problem (Figure 2). The graphs show how the success rate of the three algorithms varies with the number of algorithm layers: blue data points indicate the QAOA algorithm, pink data points indicate that only parametric degrees of freedom are released on top of the QAOA algorithm, and green data points indicate the S-QAOA algorithm (i.e., in addition to releasing parametric degrees of freedom, a YY two-body interaction is introduced into the line). The S-QAOA algorithm yields higher success rates for a given line depth, especially for the more difficult to optimize the w3R-MaxCut problem.
The researchers have improved the QAOA algorithm by introducing more two-body interactions and releasing parametric degrees of freedom, reducing the depth of the line required for the QAOA algorithm and making it more suitable for noisy quantum computers at this stage. The algorithm uses the principle of STA (Shortcuts to adiabaticity), so the researchers call it "Shortcuts to QAOA".
In S-QAOA, parameter degrees of freedom are released by further optimization of parameters with larger gradients, but it is worth exploring whether there is a better way to select the most important parameters for optimization," said the Hongyuan quantum researchers. We will study more cases in our next work to validate and refine our ideas. We hope that our approach will provide new methods and ideas for achieving quantum superiority as early as possible."
Paper Link: https://mp.weixin.qq.com/s/6SL4tqbKu3HDvsMsUeSjkQ
