<p>Given a graph <i>G</i>(<i>V</i>,&#xa0;<i>E</i>), a dominating set <i>D</i> is a subset of <i>V</i> in which every vertex not in <i>D</i> is adjacent to at least one vertex in <i>D</i>. The concept of Efficient Domination (ED) introduces a variation of domination in a graph, ensuring that every vertex is dominated by exactly one vertex from the dominating set. This concept has been extended to Bi-Efficient Domination (BED), where each vertex is dominated by exactly two vertices in the dominating set. This paper presents a QUBO formulation for the efficient domination problem and transforms it into a Hamiltonian that is well-suited for quantum computing. The approach leverages the Quantum Approximate Optimization Algorithm (QAOA) to solve the problem. Additionally, the paper presents the results of a similar quantum-based approach applied to the bi-efficient domination problem, showcasing the effectiveness of quantum techniques. By bridging graph theory and quantum computing, this work provides a foundation for leveraging quantum algorithms to solve complex domination problems.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Efficient domination problem: a quantum computing approach

  • K. A. Vidya,
  • K. Venugopal

摘要

Given a graph G(VE), a dominating set D is a subset of V in which every vertex not in D is adjacent to at least one vertex in D. The concept of Efficient Domination (ED) introduces a variation of domination in a graph, ensuring that every vertex is dominated by exactly one vertex from the dominating set. This concept has been extended to Bi-Efficient Domination (BED), where each vertex is dominated by exactly two vertices in the dominating set. This paper presents a QUBO formulation for the efficient domination problem and transforms it into a Hamiltonian that is well-suited for quantum computing. The approach leverages the Quantum Approximate Optimization Algorithm (QAOA) to solve the problem. Additionally, the paper presents the results of a similar quantum-based approach applied to the bi-efficient domination problem, showcasing the effectiveness of quantum techniques. By bridging graph theory and quantum computing, this work provides a foundation for leveraging quantum algorithms to solve complex domination problems.