Using Quantum Algorithms to Solve the Independent Domination Problem
Author Information
Author(s): Pan Haoqian, Lu Changhong, Yuan Xiao, Zhang Xiaoming, Koczor Bálint
Primary Institution: East China Normal University
Hypothesis
Can the Quantum Approximate Optimization Algorithm effectively solve the Independent Domination Problem?
Conclusion
The study demonstrates that the Quantum Approximate Optimization Algorithm can effectively address the Independent Domination Problem with improved computational efficiency compared to classical methods.
Supporting Evidence
- The QAOA was applied to the Independent Domination Problem for the first time.
- The results showed that the QAOA can outperform classical algorithms in terms of computational complexity.
- Multiple parameter settings were tested to evaluate the robustness of the QAOA.
- The study provided insights into the relationship between QAOA parameters and solution quality.
Takeaway
This study shows that a special quantum computer method can help solve a tricky math problem about finding the smallest group of friends in a network who can connect everyone else.
Methodology
The study transformed the Independent Domination Problem into a QUBO model and applied the Quantum Approximate Optimization Algorithm to solve it.
Limitations
The study did not test the QAOA on a real quantum computer and did not optimize the quantum circuits used.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website