Название: Quantum Algorithms: A Survey of Applications and End-to-end Complexities
Автор: Alexander M. Dalzell, Sam McArdle, Mario Berta
Издательство: Cambridge University Press
Год: 2025
Страниц: 436
Язык: английский
Формат: pdf (true), epub
Размер: 10.1 MB

The 1994 discovery of Shor's quantum algorithm for integer factorization―an important practical problem in the area of cryptography―demonstrated quantum computing's potential for real-world impact. Since then, researchers have worked intensively to expand the list of practical problems that quantum algorithms can solve effectively. This book surveys the fruits of this effort, covering proposed quantum algorithms for concrete problems in many application areas, including quantum chemistry, optimization, finance, and Machine Learning. For each quantum algorithm considered, the book clearly states the problem being solved and the full computational complexity of the procedure, making sure to account for the contribution from all the underlying primitive ingredients. Separately, the book provides a detailed, independent summary of the most common algorithmic primitives. It has a modular, encyclopedic format to facilitate navigation of the material and to provide a quick reference for designers of quantum algorithms and quantum computing researchers.

Computation and communication are secured by cryptography. The attempt to break security is known as cryptanalysis, which has its own set of algorithms. Historically, both cryptography and cryptanalysis considered classical, polynomial-time algorithms as the only realistic ones. The advent of quantum computation forces us to consider attacks via quantum algorithms. Generally, we want to know what is the best algorithm for cryptanalysis, in order to understand the effect on the cryptosystem in the worst case. Quantum attacks can void the security of widely used cryptosystems. More broadly, quantum cryptanalysis can reduce a cryptosystem’s security, such that it becomes more expensive to implement in a secure manner. While the properties of quantum mechanics can also be used to devise more secure cryptosystems (e.g., quantum key distribution), we consider this area of cryptography to be outside the scope of the present discussion on quantum algorithms.

There has been significant recent interest in exploring the interplay between quantum computing and machine learning. Quantum resources and quantum algorithms have been studied in all major parts of the traditional Machine Learning pipeline: (i) the dataset, (ii) data processing and analysis, (iii) the Machine Learning model leading to a hypothesis family, and (iv) the learning algorithm. In this chapter, we predominantly focus on quantum approaches for the latter three categories—that is, here we mostly consider quantum algorithms applied to classical data. These approaches include algorithms hinging on the quantum linear system solver (or quantum linear algebra more generally) as the source for possible quantum speedup over classical learning algorithms. These also include quantum neural networks (using the framework of variational quantum algorithms) and quantum kernels, where the classical Machine Learning model is replaced with a quantum model. Additionally, in this chapter, we discuss quantum algorithms that aim to speed up data analysis tasks, namely, tensor principal component analysis (TPCA) and topological data analysis.






ОТСУТСТВУЕТ ССЫЛКА/ НЕ РАБОЧАЯ ССЫЛКА ЕСТЬ РЕШЕНИЕ, ПИШЕМ СЮДА!