Abstract Noisy intermediate-scale quantum (NISQ) devices are restricted by their limited number of qubits and their short decoherence times. An approach addressing these problems is quantum circuit cutting. It decomposes the execution of a large quantum circuit into the execution of multiple smaller quantum circuits with additional classical postprocessing. Since these smaller quantum circuits require fewer qubits and gates, they are more suitable for NISQ devices. To investigate the effect of quantum circuit cutting in a quantum algorithm targeting NISQ devices, we design two experiments using the quantum approximate optimization algorithm (QAOA) for the Maximum Cut (MaxCut) problem and conduct them on state-of-the-art superconducting devices. Our first experiment studies the influence of circuit cutting on the objective function of QAOA, and the second evaluates the quality of results obtained by the whole algorithm with circuit cutting. The results show that circuit cutting can reduce the effects of noise in QAOA, and therefore, the algorithm yields better solutions on NISQ devices.
Abstract Noisy intermediate-scale quantum (NISQ) devices are restricted by their limited number of qubits and their short decoherence times. An approach addressing these problems is quantum circuit cutting. It decomposes the execution of a large quantum circuit into the execution of multiple smaller quantum circuits with additional classical postprocessing. Since these smaller quantum circuits require fewer qubits and gates, they are more suitable for NISQ devices. To investigate the effect of quantum circuit cutting in a quantum algorithm targeting NISQ devices, we design two experiments using the quantum approximate optimization algorithm (QAOA) for the Maximum Cut (MaxCut) problem and conduct them on state-of-the-art superconducting devices. Our first experiment studies the influence of circuit cutting on the objective function of QAOA, and the second evaluates the quality of results obtained by the whole algorithm with circuit cutting. The results show that circuit cutting can reduce the effects of noise in QAOA, and therefore, the algorithm yields better solutions on NISQ devices.
Noisy intermediate-scale quantum (NISQ) devices with limited qubit count and connectivity limit the scale of quantum circuits that can be executed. Circuit cutting methods simulate larger quantum computers by decomposing large circuits into small subcircuits that can be executed on NISQ hardware. Existing circuit cutting methods only consider the qubit count of the target hardware for finding the locations of cuts on the circuits. This can result in deeper subcircuits after mapping on the hardware. Fidelity decays exponentially with circuit depth and diminishes the quality of execution. We propose a circuit-cutting framework that reduces variance in the depth of subcircuits after mapping to the hardware. Our method formulates the initial circuit cutting as a multi-objective optimization problem based on an evolutionary search method with the number of cuts and the maximum depth of individual routed subcircuits as fitness objectives. This method is implemented as an extension to the existing Qiskit Circuit Cutting Addon, which allows for integration in existing flows. Our approach achieves reductions in routed subcircuit depth of up to 9.9% across benchmark circuits compared with baseline methods.
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.
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.
In recent years, significant progress has been made in building quantum computers by several companies. Despite the progress, these noisy intermediate-scale quantum (NISQ) computers still suffer from several noises and errors such as measurement errors, multi-qubit gate errors, and worse, short decoherence times. Though quantum computer vendors are releasing better quantum computers in terms of Quantum Volume, the quantum device still remains far from quantum supremacy in practical problems. The Quantum Approximate Optimization Algorithm (QAOA) was suggested to potentially demonstrate a computational advantage in combinatorial optimization problems on NISQ computers. In this paper, we optimize the QAOA circuits and to scale the problem size on IBM quantum processors. In addition, we study the effect of the length of the QAOA ansatz on IBM quantum processors and discuss optimal implementation methods for scalable QAOA. We test our implementations on the MaxCut problems.
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.
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.