Quantum algorithms: A survey of some recent results

François Le Gall

Abstract This article surveys recent developments in the field of quantum distributed algorithms. We first explain the results by Le Gall and Magniez (PODC 2018) and Le Gall, Nishimura and Rosmanis (STACS 2019), which introduced quantum distributed algorithms faster than classical distributed algorithms in two central models of distributed computing. We then describe other recent developments in quantum distributed computing.

Melinda Andrews, Joseph Stephen Dulny, Andrew N. Glaudell +6 more

Usha Rani J, Ganesan Anandhi

Stephen P. Jordan, Yi-Kai Liu

Some recently discovered quantum algorithms have resulted in complete breaks of cryptosystems previously expected to be secure against quantum attack. Although several strong candidates for postquantum cryptography remain standing, continued attention to quantum algorithms for cryptanalysis is warranted. Here we survey these recent developments, focusing on those most likely to be of relevance to cryptanalysis.

Andrew Drucker, Ronald de Wolf

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (nonquantum) areas. In this paper we survey these results and the quantum toolbox they use.

Peter Høyer