Is there any Grover like search algorithm for Quantum annealer?
Grover's search algorithm gives massive speed up in case of unstructured database search. Is there any similar algorithm for quantum annealer?
Grover's search algorithm gives massive speed up in case of unstructured database search. Is there any similar algorithm for quantum annealer?
Comments
Hi Aniruddha,
Grover's algorithm is proven to have a scalable speed-up over all possible classical methods when implemented on error corrected universal quantum computers (universal adiabatic computation, universal error corrected gate model, etc). Grover's algorithm is unfortunately not possible to formulate for the current generation D-wave quantum processors. Quantum annealing is known to allow exponential advantage over classical methods under some (for now impractical) implementations (e.g. a recent example https://arxiv.org/abs/2011.09495 with some review of the literature). It is possible to translate the type of decision problems that Grover's algorithm can answer, to the type of optimization problems that the quantum annealing algorithm can answer, but it is not known whether or how much solution quality would suffer from the translation.
However, quantum annealing with D-Wave devices has allowed for significant empirical speed up relative to some standard classical methods for optimization and sampling in a variety of settings (e.g. McGeoch and Wang Proceedings of the 2013 ACM Conference on Computing Frontiers (2013), King et al. Nature communications (2021)). It is an area of active research to determine if quantum annealing as currently implemented in our devices can realize a scaling advantage over all classical methods.
Please sign in to leave a comment.