The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm (VQA) ideal for noisy intermediate-scale quantum (NISQ) processors, and is highly successful in solving combinatorial optimization problems (COPs). It has been observed that the optimal parameters obtained from one instance of a COP can be transferred to another instance, resulting in generally good solutions for the latter. In this work, we propose a refinement scheme in which only a subset of QAOA layers is optimized following parameter transfer, with a focus on the Max-Cut problem. Our motivation is to reduce the complexity of the loss landscape when optimizing all the layers of high-depth QAOA circuits, as well as to reduce the optimization time. We investigate the potential hierarchical roles of different layers and analyze how the approximation ratio scales with increasing problem size. Our findings indicate that the selective layer optimization scheme offers a favorable trade-off between solution quality and computational time, and can be more beneficial than full optimization at a lower optimization time.
The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm (VQA) ideal for noisy intermediate-scale quantum (NISQ) processors, and is highly successful in solving combinatorial optimization problems (COPs). It has been observed that the optimal parameters obtained from one instance of a COP can be transferred to another instance, resulting in generally good solutions for the latter. In this work, we propose a refinement scheme in which only a subset of QAOA layers is optimized following parameter transfer, with a focus on the Max-Cut problem. Our motivation is to reduce the complexity of the loss landscape when optimizing all the layers of high-depth QAOA circuits, as well as to reduce the optimization time. We investigate the potential hierarchical roles of different layers and analyze how the approximation ratio scales with increasing problem size. Our findings indicate that the selective layer optimization scheme offers a favorable trade-off between solution quality and computational time, and can be more beneficial than full optimization at a lower optimization time.
Solving combinatorial optimization problems (COPs) is a promising application of quantum computation, with the Quantum Approximate Optimization Algorithm (QAOA) being one of the most studied quantum algorithms for solving them. However, multiple factors make the parameter search of the QAOA a hard optimization problem. In this work, we study transfer learning (TL), a methodology to reuse pre-trained QAOA parameters of one problem instance into different COP instances. This methodology can be used to alleviate the necessity of classical optimization to find good parameters for individual problems. To this end, we select small cases of the traveling salesman problem (TSP), the bin packing problem (BPP), the knapsack problem (KP), the weighted maximum cut (MaxCut) problem, the maximal independent set (MIS) problem, and portfolio optimization (PO), and find optimal β and γ parameters for p layers. We compare how well the parameters found for one problem adapt to the others. Among the different problems, BPP is the one that produces the best transferable parameters, maintaining the probability of finding the optimal solution above a quadratic speedup over random guessing for problem sizes up to 42 qubits and p = 10 layers. Using the BPP parameters, we perform experiments on IonQ Harmony and Aria, Rigetti Aspen-M-3, and IBM Brisbane of MIS instances for up to 18 qubits. The results indicate that IonQ Aria yields the best overlap with the ideal probability distribution. Additionally, we show that cross-platform TL is possible using the D-Wave Advantage quantum annealer with the parameters found for BPP. We show an improvement in performance compared to the default protocols for MIS with up to 170 qubits. Our results suggest that there are QAOA parameters that generalize well for different COPs and annealing protocols.
The capability of the quantum approximate optimization algorithm (QAOA) in solving combinatorial optimization problems has been intensively studied in recent years due to its application in the quantum-classical hybrid regime. Despite having difficulties that are innate in the variational quantum algorithms (VQA), such as barren plateaus and the local minima problem, QAOA remains one of the applications that is suitable for the recent noisy intermediate scale quantum (NISQ) devices. Recent works have shown that the performance of QAOA largely depends on the initial parameters, which motivate parameter initialization strategies to obtain good initial points for the optimization of QAOA. On the other hand, optimization strategies focus on the optimization part of QAOA instead of the parameter initialization. Instead of having absolute advantages, these strategies usually impose trade-offs to the performance of the optimization problems. One such example is the layerwise optimization strategy, in which the QAOA parameters are optimized layer by layer instead of the full optimization. The layerwise strategy costs less in total compared to the full optimization, in exchange of lower approximation ratio. In this work, we propose the iterative layerwise optimization strategy and explore the possibility for the reduction of optimization cost in solving problems with QAOA. Using numerical simulations, we found that by combining the iterative layerwise strategy with proper initialization strategies, the optimization cost can be significantly reduced in exchange for a minor reduction in the approximation ratio. We also show that in some cases, the approximation ratio given by the iterative layerwise strategy is even higher than that given by the full optimization.
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.
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.
In the Noisy Intermediate-Scale Quantum (NISQ) era, the Quantum Approximate Optimization Algorithm (QAOA) has attracted significant attention as an algorithm for solving combinatorial optimization problems that are classically intractable. Various modifications and training strategies have been proposed to enhance the performance of QAOA. However, as the circuit depth increases, existing methods encounter greater training difficulty and reach a barren plateau in performance improvements. In this paper, we propose the Smart Insert Layerwise QAOA (SIL QAOA) to overcome these challenges. In SIL QAOA, at each stage, a new layer is inserted into all possible positions; each circuit is independently optimized, and the parameter set from the circuit yielding the highest expectation value is adopted as the initial parameter for the next stage. Applying the proposed method to the MaxCut problem, we achieved up to approximately 11% higher approximation ratios compared to conventional Layerwise learning QAOA, while successfully mitigating early performance saturation observed at shallow depths. These results demonstrate the superior performance improvement capability of SIL QAOA. Furthermore, we also discuss its potential applicability to more complex optimization problems and deeper variational quantum circuits in future work.
Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary noisy intermediate-scale quantum (NISQ) era. The quantum approximate optimization algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of L quantum circuit layers within a corresponding Trotterized ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here we employ basin-hopping global optimization methods to navigate the energy landscapes for QAOA ansätze for various graphs, and analyze QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualizations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organization, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimization. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima. Published by the American Physical Society 2024