Abstract In the noisy intermediate-scale quantum (NISQ) era, quantum approximate optimisation algorithms are important tools for solving NP-hard problems such as combinatorial optimisation. However, most QAOA implementations ignore the inherent noise in quantum circuit environments. This study proposes a noisy quantum approximate optimisation algorithm (NQAOA) and analyses its performance under noisy conditions through numerical simulations. We compare the approximate ratios (AR) of various graphs under different optimisation strategies and noise conditions, and assess the impact of circuit depth, node count, edge count, and noise coefficient on the maximum cut (MaxCut). Experimental results show that noise leads to overfitting, and the approximate ratio ( AR ) exhibits fluctuating changes as the edge count e increases. The AR values under ideal conditions and the expected results are both superior to those under noisy conditions. This study is the first to systematically integrate multiple types of quantum noise into the QAOA framework, quantitatively analysing the synergistic effects of noise type, optimiser performance, and graph structure. Through theoretical derivations and numerical simulations, we established linear/exponential theoretical boundaries for AR decay related to noise coefficients, providing a critical reference for designing noise-resistant quantum optimisation algorithms on NISQ devices.
Abstract In the noisy intermediate-scale quantum (NISQ) era, quantum approximate optimisation algorithms are important tools for solving NP-hard problems such as combinatorial optimisation. However, most QAOA implementations ignore the inherent noise in quantum circuit environments. This study proposes a noisy quantum approximate optimisation algorithm (NQAOA) and analyses its performance under noisy conditions through numerical simulations. We compare the approximate ratios (AR) of various graphs under different optimisation strategies and noise conditions, and assess the impact of circuit depth, node count, edge count, and noise coefficient on the maximum cut (MaxCut). Experimental results show that noise leads to overfitting, and the approximate ratio ( AR ) exhibits fluctuating changes as the edge count e increases. The AR values under ideal conditions and the expected results are both superior to those under noisy conditions. This study is the first to systematically integrate multiple types of quantum noise into the QAOA framework, quantitatively analysing the synergistic effects of noise type, optimiser performance, and graph structure. Through theoretical derivations and numerical simulations, we established linear/exponential theoretical boundaries for AR decay related to noise coefficients, providing a critical reference for designing noise-resistant quantum optimisation algorithms on NISQ devices.
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.
Variational quantum algorithms are leading candidates for practical utilisation on noisy intermediate-scale quantum (NISQ) processors, but accumulating noise bounds the usefulness of circuit depths. For the quantum approximate optimisation algorithm (QAOA), this trade-off has mostly been addressed by searching for the best depth for a given device. In this work, we consider the inverse question: how much noise each depth can tolerate. Using GPU-accelerated noisy QAOA simulations for MaxCut on three graph families with 6 to 18 vertices, depths up to 10 and three noise channels, we fit the approximation ratios with a generalised logistic surface. We propose the effective noise threshold as the inflection boundary of the logistic surfaces, a noise boundary separating reliable and unreliable QAOA approximation regimes. In general, the threshold decreases as depth rises, indicating that deeper circuits demand for stricter noise requirement for reliable approximation. Its best and worst values over depth divide the noise axis into three regions: every depth remains effective, depth must be chosen with care, or no depth induces effective optimisation. Assessing on the ibm_marrakesh processor, although modelled gate errors understate factual noise, the threshold modeling remains beneficial in informing qualitative depth-dependence structure and identifying dominating noise channel in noisy QAOA.
Quantum computers are devices, which allow more efficient solutions of problems as compared to their classical counterparts.As the timeline to developing a quantum-error corrected computer is unclear, the quantum computing community has dedicated much attention to developing algorithms for currently available noisy intermediate-scale quantum computers (NISQ).Thus far, within NISQ, optimization problems are one of the most commonly studied and are quite often tackled with the quantum approximate optimization algorithm (QAOA).This algorithm is best known for computing graph partitions with a maximal separation of edges (MaxCut), but can easily calculate other problems related to graphs.Here, I present a novel quantum optimization algorithm, which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem.Such an improved performance allowed me to partition graphs with 32 nodes on publicly available 5 qubit gate-based quantum computers without any preprocessing such as division of the graph into smaller subgraphs.These results represent a 40% increase in graph size as compared to state-of-art experiments on gate-based quantum computers such as Google Sycamore.The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal simulators of quantum computers.Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with simulators of quantum computers, again without any predivision into smaller subproblems and a lower solution bound of 67.9% is achieved.The study presented here paves way to using powerful genetic optimizer in synergy with quantum computers.
Quantum computers are devices which allow the solution of problems unsolvable to their classical counterparts. As an error-corrected quantum computer is still a decade away the quantum computing community has dedicated much attention to developing algorithms for currently available Noisy Intermediate-Scale Quantum computers (NISQ). Thus far, within NISQ, optimization problems are one of the most commonly studied and are exclusively tackled with the Quantum Approximate Optimization Algorithm (QAOA). This algorithm predominantly computes graph partitions with a maximal separation of edges (MaxCut), but can also be modified to calculate other properties of graphs. Here, I present a novel quantum optimization algorithm which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem. Such an improved performance allowed me to partition a graphs 32 nodes on publicly available 5 qubit gate-based solid state quantum devices without any preprocessing such as division of the graph into smaller subgraphs. This results represent a 40% increase in graph size as compared to state-of-art experiments on solid state devices such as Google Sycamore. The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal quantum simulators. Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with quantum simulators, again without any pre-division into smaller subproblems and a lower solution bound of 67.9% is achieved.
Multi-angle quantum approximate optimization algorithm (ma-QAOA) has been proposed as an alternative to regular QAOA for solving optimization problems using noisy intermediate scale quantum (NISQ) hardware. Here, we first implement QAOA and ma-QAOA algorithms to solve MaxCut on weighted and unweighted versions of the Erdős–Rényi (ER) and random cubic (RC) graphs of 6 and 10 nodes. Quantum circuit parameters are updated iteratively through classical feedback with the quantum circuit for forward pass modelled on Qiskit simulator without noise models. Then, the quantum circuit for the final run with updated parameters is implemented on Qiskit simulator without noise models, Qiskit simulator with experimentally benchmarked noise models (fake back-end), and also on actual experimental quantum hardware (IBM’s 127-qubit quantum processor ibm brisbane). We show that for most graph instances, ma-QAOA performs better than QAOA (in terms of approximation ratio (AR)) and needs less stages in the quantum circuit for all three aforementioned methods. Finally, we extend our results up to 14-node RC graphs while restricting ourselves to Qiskit simulation without noise (both for parameter update and final run) and show that for most instances, ma-QAOA again needs much less stages compared to QAOA to obtain reasonable AR.
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