Grover Binary Search for Discrete Quantum Optimization

Grover Binary Search for Discrete Quantum

Contemporary quantum algorithms, being efficient theoretically, fail to run on real QPUs. One reason for these failures is the algorithm’s probabilistic nature, which is amplified by imperfections in hardware implementation. Grover search is such a probabilistic method, which enables other methods in quantum optimization and machine learning. In this work we improve the theoretical worst case complexity of Grover Adaptive Search by replacing iterations with binary search. We observe in the experiments that our method shows better success rate in general, and is sufficiently better for a specific type of optimization landscapes with plateaus.

Read the article


Ayaz Baykov (Innopolis University,

Stanislav Protasov (Innopolis University,

in Proceedings of the Third International Conference Nonlinearity,Information and Robotics 2022, August 24, 2022