Perfect Domination Problem (PDP), a canonical challenge in combinatorial optimization, finds critical applications in real-world systems such as error-correcting codes, wireless communication networks, and social networks. Decades of research have firmly established its NP-completeness across numerous graph classes. Motivated by rapid advances in quantum computing, significant effort has recently been directed toward quantum algorithms for NP-complete problems, most notably the Quantum Approximate Optimization Algorithm (QAOA). Nonetheless, the applicability and efficacy of quantum approaches to the PDP remain entirely unexplored. This paper initiates the first systematic investigation of the PDP via QAOA. We evaluate solution quality on three benchmark instances of 6, 7, and 8 vertices using 15-18 qubits on a quantum simulator, examining more than 400 distinct parameter configurations. Experimental results confirm the algorithm's effectiveness and expose discernible trends in parameter selection. These outcomes substantiate QAOA's viability for the PDP and mark a seminal step toward situating this classical problem within the quantum-computing paradigm.
Perfect Domination Problem (PDP), a canonical challenge in combinatorial optimization, finds critical applications in real-world systems such as error-correcting codes, wireless communication networks, and social networks. Decades of research have firmly established its NP-completeness across numerous graph classes. Motivated by rapid advances in quantum computing, significant effort has recently been directed toward quantum algorithms for NP-complete problems, most notably the Quantum Approximate Optimization Algorithm (QAOA). Nonetheless, the applicability and efficacy of quantum approaches to the PDP remain entirely unexplored. This paper initiates the first systematic investigation of the PDP via QAOA. We evaluate solution quality on three benchmark instances of 6, 7, and 8 vertices using 15-18 qubits on a quantum simulator, examining more than 400 distinct parameter configurations. Experimental results confirm the algorithm's effectiveness and expose discernible trends in parameter selection. These outcomes substantiate QAOA's viability for the PDP and mark a seminal step toward situating this classical problem within the quantum-computing paradigm.
Recent advancements in quantum computing have spurred substantial research into the application of quantum algorithms to combinatorial optimization problems. Among these challenges, the Total Domination Problem (TDP) emerges as a classic and critical paradigm in the field. For a graph G(V, E), TDP entails finding a minimal subset D subset of V that contains no isolated vertices, where every vertex not in D has at least one neighbor in D. TDP finds extensive applications across domains such as computer networks, social networks, and communications. Since the latter half of the last century, research efforts have focused on establishing its NP-completeness and developing solution algorithms, which have become foundational to combinatorial mathematics. Despite this rich history, the application of quantum algorithms to TDP remains largely underexplored. In this study, we present a pioneering application of the Quantum Approximate Optimization Algorithm (QAOA) to tackle TDP, evaluating its efficacy across a diverse set of parameters. This paper proves that the upper bound on the number of qubits required to solve TDP is 2|V| + |V| log_2( (2|E|)/|V| - 1 ). Our experimental findings demonstrate that QAOA is effective in addressing TDP: under most parameter combinations, it successfully computes a valid total dominating set (TDS). However, the algorithm's performance in identifying the optimal TDS is contingent upon specific parameter choices, revealing a significant bias in the distribution of effective parameter points. This research contributes valuable insights into the potential of quantum algorithms for solving TDP and lays a solid groundwork for future investigations in this area.
In the wake of quantum computing advancements and quantum algorithmic progress, quantum algorithms are increasingly being employed to address a myriad of combinatorial optimization problems. Among these, the Independent Domination Problem (IDP), a derivative of the Domination Problem, has practical implications in various real-world scenarios. Despite this, existing classical algorithms for the IDP are plagued by high computational complexity, and quantum algorithms have yet to tackle this challenge. This paper introduces a Quantum Approximate Optimization Algorithm (QAOA)-based approach to address the IDP. Utilizing IBM's qasm_simulator, we have demonstrated the efficacy of the QAOA in solving the IDP under specific parameter settings, with a computational complexity that surpasses that of classical methods. Our findings offer a novel avenue for the resolution of the IDP.
In the wake of quantum computing advancements and quantum algorithmic progress, quantum algorithms are increasingly being employed to address a myriad of combinatorial optimization problems. Among these, the Independent Domination Problem (IDP), a derivative of the Domination Problem, has practical implications in various real-world scenarios. Despite this, existing classical algorithms for IDP are plagued by high computational complexity, and quantum algorithms have yet to tackle this challenge. This paper introduces a Quantum Approximate Optimization Algorithm (QAOA)-based approach to address the IDP. Utilizing IBM's qasm_simulator, we have demonstrated the efficacy of QAOA in solving IDP under specific parameter settings, with a computational complexity that surpasses that of classical methods. Our findings offer a novel avenue for the resolution of IDP.
Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.
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.
Quantum computing promises solutions to classically difficult and new-found problems through controlling the subtleties of quantum computing. The Quantum Approximate Optimisation Algorithm (QAOA) is a recently proposed quantum algorithm designed to tackle difficult combinatorial optimisation problems utilising both quantum and classical computation. The hybrid nature, generality and typically low gate-depth make it a strong candidate for near-term implementation in quantum computing. Finding the practical limits of the algorithm is currently an open problem. Until now, no tools to facilitate the design and validation of probabilistic quantum optimisation algorithms such as the QAOA on a non-trivial scale exist. Graph similarity is a long standing classically difficult problem withstanding decades of research from academia and industry. Determining the maximal edge overlap between all possible node label permutations is an NP-Complete task and provides an apt measure of graph similarity. We introduce a novel quantum optimisation simulation package facilitating investigation of all constituent components of the QAOA from desktop to cluster scale using graph similarity as an example. Our simulation provides flexibility and performance. We investigate eight classical optimisation methods each at six levels of decomposition. Moreover an encoding for permutation based problems such as graph similarity through edge overlap to the QAOA allows for significant quantum memory savings at the cost of additional operations. This compromise extends into the classical portion of the algorithm as the inclusion of infeasible solutions creates a challenging cost-function landscape. We present performance analysis of our simulation and of the QAOA setting a precedent for investigating and validating numerous other difficult problems to the QAOA as we move towards realising practical quantum computation.