Quantum computers are well suited to solve some complex problems that would take classical computers a long time to solve, or not at all. A frequently cited example is cracking encrypted messages, although some popular renditions of this task are not entirely plausible. Another such example is optimization problems that aim to find the best possible solution - for example, the fastest route on a map given a traffic situation or an appropriate use of a budget. And it is optimization algorithms that are the focus of the new study. It maps different approaches to optimisation and offers comparisons between them as well as predictions for future developments.
The authors also highlight the biggest challenges in the field. "To take advantage of quantum computing, a lot of research will still need to be done. "Experiments, work with real technologies and verification of our hypotheses in practice will be crucial. That is why I am glad that we have companies like IBM in the group, which develop quantum computers, understand them, and willingly share their knowledge with us, " he adds. This allows Dr Jakub Mareček's group to use IBM Q computers, which have up to 1121 qubits, for research purposes.
So far, however, even IBM Q computers are not able to keep qubits coherent long enough to outperform the best available classical computers. They can solve convex optimization problems, where local optima are global optima, in dimensions of 1020 and larger, which researchers estimate quantum computers will not yet be able to solve in the next decade. But in a study in Nature Reviews Physics, the researchers identify areas where quantum computers could soon outperform the best classical computers, particularly in dealing with nonconvex optimization problems and optimization problems with uncertainty.
The study is the result of several years of collaboration between experts across disciplines such as mathematics, computer science and physics. In addition to FEE CTU, the academic community in the group includes the Massachusetts Institute of Technology (MIT), the Swiss Federal Institute of Technology Lausanne (EPFL), the Technical University of Berlin, and others. E.ON, Erste Bank, HSBC, IBM and Volkswagen are also involved in the research.
