In the excitement surrounding quantum information-processing, many proposals have been made to use it for classical computational tasks that are believed to be "hard". Such problems are found in applied fields such as scheduling, logistics, optimization, etc.
In 2020 a competition between platforms to solve a benchmark combinatorial optimization problem was organized [1]. The result was that a classical algorithm from the spin glass community running on classical hardware was superior, by many orders of magnitude. It also had better scaling, i.e. out-competes other approaches better and better, the larger the problem instance [2]. A physical theory of why that should be so has already been published [3].
I will present the problem, the outcome of the competition, and the physical theory that explains it. I will also discuss what I think this implies for quantum computing.
Note: none of the technical work on which this talk is based is my own. One of the co-authors of [2] has however indicated that he would participate on zoom, and would be available to discuss after the talk.
The seminar will be given in hybrid format, on-line at
https://kth-se.zoom.us/j/68888238166
References:
[1] 3-regular 3-XORSAT planted solutions benchmark of classical and quantum heuristic optimizers" Kowalsky et al, Quantum Science and Technology (2022) [arXiv:2103.08464]
[2] M. Bernaschi et al EPL 133 60005 (2021)
[3] M. Bellitti et al Phys. Rev. Research 3 043015 (2021)