Abstract At present, the quantum approximate optimization algorithm (QAOA) faces scalability challenges in high-dimensional combinatorial optimization problems due to exponentially growing computational costs and reachability deficits for noisy intermediate-scale quantum (NISQ) devices. This study focuses on the multiscale quantum approximate optimization algorithm (MQAOA), which integrates renormalization group (RG) transformations with QAOA to address these limitations. Based on the connections between the variables in the problem to be solved, the weighted maximal matching method is employed to generate a variable partitioning strategy guiding the RG transformation. This approach not only extends the applicability of MQAOA to satisfiability (SAT) problems — including those with three-body and higher-order interactions in the problem Hamiltonian — but also eliminates the algorithm’s sensitivity to problem density. Validations conducted on quantum simulators show that, after running two-round MQAOA, its capability is enhanced to identify optimal solutions with approximately 97% success probability as defined by the ground-state overlap for Max-2-SAT problems (78% success probability for Max-3-SAT problems). The results confirm the feasibility of MQAOA and establish it as a resource-efficient framework for complex combinatorial optimization problems, providing a pathway for NISQ-era deployment.
Abstract At present, the quantum approximate optimization algorithm (QAOA) faces scalability challenges in high-dimensional combinatorial optimization problems due to exponentially growing computational costs and reachability deficits for noisy intermediate-scale quantum (NISQ) devices. This study focuses on the multiscale quantum approximate optimization algorithm (MQAOA), which integrates renormalization group (RG) transformations with QAOA to address these limitations. Based on the connections between the variables in the problem to be solved, the weighted maximal matching method is employed to generate a variable partitioning strategy guiding the RG transformation. This approach not only extends the applicability of MQAOA to satisfiability (SAT) problems — including those with three-body and higher-order interactions in the problem Hamiltonian — but also eliminates the algorithm’s sensitivity to problem density. Validations conducted on quantum simulators show that, after running two-round MQAOA, its capability is enhanced to identify optimal solutions with approximately 97% success probability as defined by the ground-state overlap for Max-2-SAT problems (78% success probability for Max-3-SAT problems). The results confirm the feasibility of MQAOA and establish it as a resource-efficient framework for complex combinatorial optimization problems, providing a pathway for NISQ-era deployment.
The quantum approximate optimization algorithm (QAOA) is one of the canonical algorithms designed to find approximate solutions for combinatorial optimization problems on current noisy intermediate-scale quantum (NISQ) devices. The primary focus of ongoing research is to exhibit its speed advantage over classical algorithms. However, the performance of QAOA is restricted at lower depths, while higher depths are limited by current experimental techniques. We propose an algorithm that amalgamates the capabilities of QAOA and the real-space renormalization group transformation. Numerical simulations indicate that our proposed algorithm can deliver precise solutions for specific randomly generated instances using QAOA at shallow depths, even at the lowest depth. This algorithm is particularly suitable for current NISQ devices, offering the potential to demonstrate a quantum advantage.
The quantum approximate optimization algorithm (QAOA) is a promising method for solving certain classical combinatorial optimization problems on near-term quantum devices. When employing the QAOA to 3-SAT and Max-3-SAT problems, the quantum cost exhibits an easy-hard-easy or easy-hard pattern, respectively, as the clause density is changed. The quantum resources needed in the hard-region problems are out of reach for current noisy intermediate-scale quantum (NISQ) devices. We show by numerical simulations with up to 14 variables and analytical arguments that the adaptive-bias QAOA (ab-QAOA) greatly improves performance in the hard region of the 3-SAT problems and hard region of the Max-3-SAT problems. For similar accuracy, on average, ab-QAOA needs 3 levels for 10-variable 3-SAT problems as compared to 22 for QAOA. For 10-variable Max-3-SAT problems, the numbers are 7 levels and 62 levels. The improvement comes from a more targeted and more limited generation of entanglement during the evolution. We demonstrate that classical optimization is not strictly necessary in the ab-QAOA since local fields are used to guide the evolution. This leads us to propose an optimization-free ab-QAOA that can solve the hard-region 3-SAT and Max-3-SAT problems effectively with significantly fewer quantum gates as compared to the original ab-QAOA. Our work paves the way for realizing quantum advantages for optimization problems on NISQ devices.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.
The limited number of qubits is a major bottleneck in Quantum Approximate Optimization Algorithm (QAOA) for large-scale combinatorial optimization in the Noisy Intermediate-Scale Quantum (NISQ) era. To make progress, existing techniques rely on qubit reduction at the cost of information loss, hence leading to degraded computational performance. As a remedy, we propose the Equivalence-preserving Qubit Efficient QAOA (EQE-QAOA), which significantly reduces the required number of qubits without degrading the performance of QAOA. By exploiting intrinsic symmetries and conserved quantities, we first demonstrate that the QAOA dynamics are strictly confined to an invariant subspace of the Hilbert space. We subsequently prove that the evolution within this subspace is exactly equivalent to that of the full-scale system, achieving the same optimal solution as the original QAOA. Moreover, to reduce the number of qubits, we propose an isometric mapping that re-encodes the subspace into a space relying on fewer qubits. Furthermore, we derive the applicability conditions of EQE-QAOA and show that it is broadly applicable to large-scale combinatorial optimization problems, excluding only unconstrained problems with completely independent variables. Numerical simulations based on Max-Cut instances validate that EQE-QAOA significantly reduces qubit requirements and computational resources, while preserving exact optimization performance.
The solution of large-scale combinatorial optimization problems, which are exorbitantly complex and resource-consuming, is one of the most significant challenges that computing systems face. Traditional algorithms often provide suboptimal results when confronted with bigger issues. This research aims to bring attention to these problems by introducing the Extending Quantum Approximate Optimization Algorithm (EQAOA) framework, which improves scalability, parameter optimization, and error resilience. Fundamental to the EQAOA methodology is repeatedly optimizing solution states via adaptive-depth, parameter-tuned quantum circuits. EQAOA also employs the method of converting combinatorial problems into cost Hamiltonians. Similar problems are shown in the Max-Cut and Graph Coloring programs. The experiments were conducted on several benchmark circumstances using real NISQ hardware and quantum simulators. The enhanced EQAOA outperforms baseline versions in terms of convergence time and solution quality. The efficient integration of dynamic circuit depth with hybrid classical-quantum parameter approaches applied to increasingly complicated problem scenarios and yielded good results. According to the study's findings, applying the proposed QAOA extension to practical combinatorial contexts yields a quantum advantage. The future of this field is bright, with researchers aiming to improve its interaction with traditional optimizers and extend its usage to other practical optimization areas.
The quantum approximate optimization algorithm (QAOA) has emerged as a promising candidate for demonstrating quantum advantage on noisy intermediate-scale quantum (NISQ) devices. While various QAOA parameterization schemes exist, ranging from the original single-angle approach to the more expressive multi-angle quantum approximate optimization algorithm (MA-QAOA) and automorphic-angle quantum approximate optimization algorithm (AA-QAOA), each presents distinct trade-offs between expressiveness and classical optimization complexity. In this work, we introduce the k-interaction-angle quantum approximate optimization algorithm (kA-QAOA), a parameterization scheme that groups cost function terms by their k-body interaction order, providing a natural middle ground between parameter efficiency and solution quality. This approach is particularly well-suited for combinatorial optimization problems defined on hypergraphs, where multi-body interactions naturally arise in applications such as Boolean satisfiability and resource allocation with multi-party constraints. We benchmark kA-QAOA against standard single-angle quantum approximate optimization algorithm (SA-QAOA), MA-QAOA, and AA-QAOA on two problem classes: 3-uniform cyclic sign-alternating hypergraphs and random coefficient hypergraphs. Our results demonstrate that kA-QAOA achieves approximation ratios comparable to MA-QAOA while requiring significantly fewer function evaluations, thereby reducing quantum resource consumption.