Runtime complexity of optimization algorithms on D-wave Quantum Annealer
Consider a classical algorithm which has O(n^2) time complexity for problem statement X. If we can solve the same problem(X) using D-wave QPU , then how to calculate the time complexity for this method?
Comments
Hello,
Problems that are O(n^2) are not very well suited to the QPU.
They have to be quite large to become impractical for classical computers, in which case they will not be able to fit onto the QPU.
If they are small enough to fit they can be solved trivially with classical computing.
One could try solving large O(n^2) problems using the HSS, which can take up to 10,000 variables.
Here are some links to the documentation:
https://www.dwavesys.com/sites/default/files/14-1039A-A_D-Wave_Hybrid_Solver_Service_An_Overview.pdf
https://support.dwavesys.com/hc/en-us/articles/360043978293
https://docs.ocean.dwavesys.com/en/latest/overview/hybrid.html?highlight=Hybrid%20Solver%20Service#leap-hybrid-solvers
https://docs.ocean.dwavesys.com/projects/system/en/latest/reference/samplers.html?highlight=leaphybridsampler#leaphybridsampler
For this reason, a more suitable problem would be one that is O(2^n).
Here are some papers that might be of interest:
https://arxiv.org/abs/1701.04579
https://arxiv.org/abs/1502.02098
https://arxiv.org/abs/1508.05087
https://arxiv.org/abs/1912.01759
These papers go over some information on compute time and performance of the QPU on various problems.
Unfortunately time complexity and time to solution are not generally compatible concepts.
I hope this was helpful.
Please feel free to ask follow-up questions.
Please sign in to leave a comment.