Solving the Independent Domination Problem by the Quantum Approximate Optimization Algorithm

Area of Science:

• Quantum Computing
• Combinatorial Optimization
• Algorithm Development

Background:

• Quantum algorithms are increasingly used for combinatorial optimization problems.
• The Independent Domination Problem (IDP) has practical applications but suffers from high classical computational complexity.
• Quantum algorithms have not yet been extensively applied to the IDP.

Purpose of the Study:

• To introduce a Quantum Approximate Optimization Algorithm (QAOA)-based method for solving the Independent Domination Problem (IDP).
• To evaluate the efficacy and computational complexity of the proposed QAOA approach for the IDP.

Main Methods:

• Development and implementation of a QAOA-based algorithm tailored for the IDP.
• Utilizing IBM's qasm_simulator for computational experiments.
• Analysis of computational complexity in comparison to classical algorithms.

Main Results:

• Demonstrated the efficacy of the QAOA in solving the IDP under specific parameter settings.
• Achieved a computational complexity superior to existing classical methods for the IDP.
• Validated the QAOA approach using a quantum computing simulator.

Conclusions:

• The QAOA presents a viable and efficient quantum approach for the Independent Domination Problem.
• This research opens new avenues for quantum computation in solving complex optimization problems.
• The findings highlight the potential of quantum algorithms to overcome limitations of classical methods.