Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Entropy

Solving the Independent Domination Problem by the Quantum Approximate Optimization Algorithm

Haoqian Pan, Changhong Lü

Published Dec 5, 2024• 4 citations
Publisher

Abstract

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.

DOI
10.3390/e26121057

Related papers

Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm

Haoqian Pan, Changhong Lü

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.

arXiv:2410.17227•Oct 22, 2024•0 citations

Application of the Quantum Approximate Optimization Algorithm in Solving the Total Domination Problem

Haoqian Pan, Yuan, Hang, Changhong Lü +3 more

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.

arXiv:2411.00364•Nov 1, 2024•0 citations

Exploring the Potential of Quantum Approximate Optimization Algorithm in Tackling the Perfect Domination Problem

Haoqian Pan, Changhong Lü, Yuqing Zheng +1 more

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.

arXiv:2411.12608•Nov 19, 2024•0 citations

A Tutorial on Quantum Approximate Optimization Algorithm (QAOA): Fundamentals and Applications

Jaeho Choi, Joongheon Kim

Over the past few years, many researchers around the world have been keen to know the potential and efficiency of quantum computers. The researchers have focused on specific issues that classical computers cannot solve or issues that quantum computers can handle in a better way. Among these various attractive research topics in quantum computers, this paper introduces the Quantum Approximate Optimization Algorithm (QAOA) which guarantees relatively considerable performances in many combinatorial optimization problems. For the comprehensive understanding of QAOA, this paper also describes the approximate optimization, the Quantum Alternating Operator Ansatz, and applications. Besides the theories of QAOA and Quantum Alternating Operator Ansatz, this paper explains the applications of QAOA to major combinatorial optimization problems such as maximum cut (MaxCut) problem and the max-independent set (MIS) problem.

International Conference on Information and Communication Technology Convergence (ICTC)•Oct 1, 2019•121 citations

A Tutorial on Quantum Approximate Optimization Algorithm for Maximum Independent Set Problem

Mingyu Yang, Fang Gao, Guojian Wu +2 more

In the past few years, quantum computers and quantum algorithms have shown advantages compared to their classical counterparts. In combinatorial optimization problems, quantum approximate optimization algorithm(QAOA) has good performance. This paper focuses on the application of QAOA to one combinational problem called maximum independent set(MIS). Two different Hamiltonian construction methods are employed in this algorithm using IBM Qiskit. It is shown that the key is to design proper Hamiltonians to map the solution to the feasible states of the Hilbert space.

Chinese Control Conference (CCC)•Jul 26, 2021•3 citations

Edge-based quantum approximate optimization algorithm for MAX-CUT problem

Youngjin Seo, Jun Heo

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.

Quantum Information Processing•Sep 23, 2025•1 citation
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.
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.
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.
Over the past few years, many researchers around the world have been keen to know the potential and efficiency of quantum computers. The researchers have focused on specific issues that classical computers cannot solve or issues that quantum computers can handle in a better way. Among these various attractive research topics in quantum computers, this paper introduces the Quantum Approximate Optimization Algorithm (QAOA) which guarantees relatively considerable performances in many combinatorial optimization problems. For the comprehensive understanding of QAOA, this paper also describes the approximate optimization, the Quantum Alternating Operator Ansatz, and applications. Besides the theories of QAOA and Quantum Alternating Operator Ansatz, this paper explains the applications of QAOA to major combinatorial optimization problems such as maximum cut (MaxCut) problem and the max-independent set (MIS) problem.
In the past few years, quantum computers and quantum algorithms have shown advantages compared to their classical counterparts. In combinatorial optimization problems, quantum approximate optimization algorithm(QAOA) has good performance. This paper focuses on the application of QAOA to one combinational problem called maximum independent set(MIS). Two different Hamiltonian construction methods are employed in this algorithm using IBM Qiskit. It is shown that the key is to design proper Hamiltonians to map the solution to the feasible states of the Hilbert space.
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.