Comparison of NSP solution - Classical vs Quantum
Hi,
I am trying to understand how Quntum is better suited for solving the Nurse Scheduling Problem against Classical.
Is there any paper available to which studies performance of classical algorithm for this problem?
I have read "Ikeda and others" on NSP using Quantum, so want to compare their work against some work in the classical computing filed.
Regards,
Somankar Biswas
Comments
Hello,
It is very difficult to compare a Quantum approach to a Classical approach.
Please keep in mind that not all schedules will be more efficient to solve on a Quantum Annealer.
Looking at the paper you referenced (https://arxiv.org/pdf/1904.12139.pdf), number [16] (https://link.springer.com/book/10.1007%2F11593577) talks about Automated Timetabling, and [15] (https://arxiv.org/pdf/1506.08479.pdf) references another Quantum implementation of Job Shop Scheduling, which might have some interesting resources in the bibliography. Taking a quick look at these links, [35] (https://www.sciencedirect.com/science/article/pii/0166218X94902046) and [43] (https://onlinelibrary.wiley.com/doi/10.1002/1099-1425(200101/02)4:1%3C53::AID-JOS59%3E3.0.CO;2-Y) look helpful as well.
Also a search of scholarly articles on scheduling or other famous problems similar to NSP could also turn up some valuable resources.
Our suggestion would be to use the hybrid solvers and compare results of those with classical algorithms on both smaller and larger scale problems.
Note that quantum-hybrid is aimed at producing high quality results quickly, rather than reaching true optimum values.
This paper gives an idea of how to compare:
https://arxiv.org/abs/2109.07876
Hopefully this is helpful.
Please sign in to leave a comment.