Quantum Dominance

Haoqian Pan, Changhong Lü

With the development of quantum computing, the use of quantum algorithms to solve combinatorial optimization problems on quantum computers has become a major research focus. The Quadratic Unconstrained Binary Optimization (QUBO) model serves as a bridge between combinatorial optimization problems and quantum computers, and is a prerequisite for these studies. In combinatorial optimization problems, the Domination Problem (DP) is related to many practical issues in the real world, such as the fire station problem, social network theory, and so on. Additionally, the DP has numerous variants, such as independent DP, total DP, k-domination, and so forth. However, there is a scarcity of quantum computing research on these variant problems. A possible reason for this is the lack of research on QUBO modeling for these issues. This paper investigates the QUBO modeling methods for the classic DP and its variants. Compared to previous studies, the QUBO modeling method we propose for the classic DP can utilize fewer qubits. This will lower the barrier for solving DP on quantum computers. At the same time, for many variants of DP problems, we provide their QUBO modeling methods for the first time. Our work will accelerate the entry of DP into the quantum era.

John Bechhoefer

Renata Wong, Weng-Long Chang, Wen‐Yu Chung +1 more

A dominating set of a graph [Formula: see text] is a subset U of its vertices V, such that any vertex of G is either in U, or has a neighbor in U. The dominating-set problem is to find a minimum dominating set in G. Dominating sets are of critical importance for various types of networks/graphs, and find therefore potential applications in many fields. Particularly, in the area of communication, dominating sets are prominently used in the efficient organization of large-scale wireless ad hoc and sensor networks. However, the dominating set problem is also a hard optimization problem and thus currently is not efficiently solvable on classical computers. Here, we propose a biomolecular and a quantum algorithm for this problem, where the quantum algorithm provides a quadratic speedup over any classical algorithm. We show that the dominating set problem can be solved in [Formula: see text] queries by our proposed quantum algorithm, where n is the number of vertices in G. We also demonstrate that our quantum algorithm is the best known procedure to date for this problem. We confirm the correctness of our algorithm by executing it on IBM Quantum's qasm simulator and the Brooklyn superconducting quantum device. And lastly, we show that molecular solutions obtained from solving the dominating set problem are represented in terms of a unit vector in a finite-dimensional Hilbert space.

Amanda Gefter

Michael Anderson

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.