Abstract The three-dimensional matching problem is a classic NP-complete problem in combinatorial optimization, with wide applications in resource allocation, task scheduling, and many other practical scenarios. Traditional algorithms for solving the three-dimensional matching problem face the challenge of high time complexity, making it difficult to solve large-scale problems within a reasonable time frame. To improve the solution efficiency, a quantum circuit solution based on the Quantum Approximate Optimization Algorithm (QAOA) is proposed. By constructing a mathematical model of the three-dimensional matching problem, the corresponding Hamiltonian expression is derived. A QAOA-based quantum circuit is designed and the parameters of the parameterized quantum gates are optimized using the classical optimization algorithm COBYLA. Simulation experiments are performed using IBM's quantum development framework Qiskit. The experimental results show that the solution to the three-dimensional matching problem can be obtained with 84% probability in polynomial time, verifying the feasibility and effectiveness of solving the three-dimensional matching problem based on the Quantum Approximate Optimization Algorithm.
Abstract The three-dimensional matching problem is a classic NP-complete problem in combinatorial optimization, with wide applications in resource allocation, task scheduling, and many other practical scenarios. Traditional algorithms for solving the three-dimensional matching problem face the challenge of high time complexity, making it difficult to solve large-scale problems within a reasonable time frame. To improve the solution efficiency, a quantum circuit solution based on the Quantum Approximate Optimization Algorithm (QAOA) is proposed. By constructing a mathematical model of the three-dimensional matching problem, the corresponding Hamiltonian expression is derived. A QAOA-based quantum circuit is designed and the parameters of the parameterized quantum gates are optimized using the classical optimization algorithm COBYLA. Simulation experiments are performed using IBM's quantum development framework Qiskit. The experimental results show that the solution to the three-dimensional matching problem can be obtained with 84% probability in polynomial time, verifying the feasibility and effectiveness of solving the three-dimensional matching problem based on the Quantum Approximate Optimization Algorithm.
Combinatorial optimization problems play a vital role in computer science and engineering, with applications in logistics, network design, finance, and resource allocation. However, many of these problems are NP-hard, making them computationally expensive to solve using classical optimization techniques, especially for large-scale instances. In recent years, quantum computing has emerged as a promising paradigm capable of addressing these limitations by leveraging quantum mechanical principles such as superposition and entanglement. This study investigates the application of quantum computing for solving combinatorial optimization problems, with a focus on algorithm design, complexity analysis, and real-world applicability. The research primarily employs the Quantum Approximate Optimization Algorithm (QAOA) and Grover's search algorithm to solve representative problems such as Max-Cut and the Knapsack problem. The performance of these algorithms is evaluated using key metrics including accuracy, execution time, and approximation ratio, and is compared with classical optimization techniques. The results demonstrate that QAOA is capable of generating near-optimal solutions, achieving accuracy levels of up to 93% for small problem instances. However, the study also highlights the challenges associated with current quantum systems, including noise, limited qubit availability, and increased execution time. Comparative analysis reveals that while classical methods remain more efficient for small-scale problems, quantum algorithms show significant potential for scalability and handling complex optimization tasks. The findings suggest that hybrid quantum-classical approaches offer a practical solution in the current Noisy Intermediate-Scale Quantum (NISQ) era. The study concludes that although quantum computing is still evolving, it holds strong potential for transforming combinatorial optimization in the future.
This paper proposes an application algorithm based on a quantum approximate optimization algorithm (QAOA) for wireless scheduling problems. QAOA is one of the promising hybrid quantum-classical algorithms to solve combinatorial optimization problems and it provides great approximate solutions to non-deterministic polynomial-time (NP) hard problems. QAOA maps the given problem into Hilbert space, and then it generates the Hamiltonian for the given objective and constraint. Then, QAOA finds proper parameters from the classical optimization loop in order to optimize the expectation value of the generated Hamiltonian. Based on the parameters, the optimal solution to the given problem can be obtained from the optimum of the expectation value of the Hamiltonian. Inspired by QAOA, a quantum approximate optimization for scheduling (QAOS) algorithm is proposed. The proposed QAOS designs the Hamiltonian of the wireless scheduling problem which is formulated by the maximum weight independent set (MWIS). The designed Hamiltonian is converted into a unitary operator and implemented as a quantum gate operation. After that, the iterative QAOS sequence solves the wireless scheduling problem. The novelty of QAOS is verified with simulation results implemented via Cirq and TensorFlow-Quantum.
Hybrid Quantum–Classical Optimization combines the advantages of quantum computing and classical optimization to address complex combinatorial optimization problems. The Quantum Approximate Optimization Algorithm (QAOA), as an outstanding Variational Quantum Algorithm (VQA), shows great potential in solving combinatorial optimization problems. Classical optimization methods play a crucial role in tuning the parameters of quantum circuits, affecting the algorithm’s convergence speed and solution quality. This paper designs and simulates QAOA circuits based on the Qiskit framework, focusing on comparing the performance of three classical optimizers— Adaptive Moment Estimation (Adam), Constrained Optimization BY Linear Approximations (COBYLA), and Simultaneous Perturbation Stochastic Approximation (SPSA)—in parameter optimization. Adam and SPSA perform more stably in deeper circuits, making them suitable for high-dimensional parameter spaces, whereas COBYLA tends to get trapped in local optima and exhibits greater fluctuations under limited iterations. The results further highlight the importance of classical optimizer selection and hyperparameter tuning in enhancing the performance of hybrid quantum–classical optimization algorithms.
The mission planning problem in command and control organization can be mapped into a combinatorial optimization problem with many variables and is difficult to solve. The traditional heuristic list planning method faces the problems of high time complexity and poor real-time response. For the mission planning problem in command and control organization, a quantum circuit solution scheme is proposed based on quantum approximate optimization algorithm in this work. Firstly, the mission planning problem is transformed into a typical combinatorial optimization problem, the exact coverage problem. Then, by constructing the corresponding mathematical model, the final state Hamiltonian expression of the quantum approximate optimization algorithm for the exact coverage problem is derived. The quantum circuit based on the quantum approximate optimization algorithm is designed. Finally the parameters in the quantum logic gate are optimized by the momentum gradient descent algorithm, and the simulation experiment is carried out by using the quantum software development environment of the Origin Quantum Computing Company. The simulation results show that the quantum circuit scheme can be used to solve the mission planning problem, reduce the time complexity of the algorithm, and improve the resource utilization to a certain extent. This work lays the foundation for further application of quantum algorithm to solving the mission planning problem in command and control organization.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising framework for combinatorial optimization, yet its performance is often hindered by the complexity of parameter optimization. In this work, we investigate phase relationships in Grover-QAOA (G-QAOA) for solving 3-SAT problems and introduce a novel phase matching condition that simplifies the optimization landscape. By aligning the phases of the problem and mixing Hamiltonians, our approach reduces the number of variational parameters from 2p to p, significantly lowering computational overhead. We further propose single-angle G-QAOA, an extension that enables additional parameter reduction. Numerical simulations demonstrate that our method achieves success probabilities comparable to those of standard G-QAOA while requiring fewer quantum circuit evaluations. These results highlight the potential of our proposed G-QAOA for practical implementation on near-term quantum hardware.
Abstract Quantum approximate optimization algorithm (QAOA) has shown promise in solving combinatorial optimization problems by providing quantum speedup on near-term gate-based quantum computing systems. However, QAOA faces challenges for high-dimensional problems due to the large number of qubits required and the complexity of deep circuits, limiting its scalability for real-world applications. In this study, we present a distributed QAOA (DQAOA), which leverages distributed computing strategies to decompose a large computational workload into smaller tasks that require fewer qubits and shallower circuits than are necessary to solve the original problem. These sub-problems are processed using a combination of high-performance and quantum computing resources. The global solution is iteratively updated by aggregating sub-solutions, allowing convergence toward the optimal solution. We demonstrate that DQAOA can handle considerably large-scale optimization problems (e.g., 1000-bit problem), achieving a high solution quality and short time-to-solution, outperforming existing strategies. Furthermore, we realize DQAOA on a quantum-centric supercomputing architecture, paving the way for practical applications of gate-based quantum computers in real-world optimization tasks. To extend DQAOA’s applicability to materials science, we further develop an active learning algorithm integrated with our DQAOA (AL-DQAOA), which involves machine learning, DQAOA, and active data production in an iterative loop. We successfully optimize photonic structures using AL-DQAOA, indicating that solving real-world optimization problems using gate-based quantum computing is feasible. We expect the proposed DQAOA to be applicable to a wide range of optimization problems and AL-DQAOA to find broader applications in material design.