This chapter covers quantum algorithmic primitives for loading classical data into a quantum algorithm. These primitives are important in many quantum algorithms, and they are especially essential for algorithms for big-data problems in the area of machine learning. We cover quantum random access memory (QRAM), an operation that allows a quantum algorithm to query a classical database in superposition. We carefully detail caveats and nuances that appear for realizing fast large-scale QRAM and what this means for algorithms that rely upon QRAM. We also cover primitives for preparing arbitrary quantum states given a list of the amplitudes stored in a classical database, and for performing a block-encoding of a matrix, given a list of its entries stored in a classical database.

This chapter covers the multiplicative weights update method, a quantum algorithmic primitive for certain continuous optimization problems. This method is a framework for classical algorithms, but it can be made quantum by incorporating the quantum algorithmic primitive of Gibbs sampling and amplitude amplification. The framework can be applied to solve linear programs and related convex problems, or generalized to handle matrix-valued weights and used to solve semidefinite programs.

This chapter covers quantum algorithmic primitives related to linear algebra. We discuss block-encodings, a versatile and abstract access model that features in many quantum algorithms. We explain how block-encodings can be manipulated, for example by taking products or linear combinations. We discuss the techniques of quantum signal processing, qubitization, and quantum singular value transformation, which unify many quantum algorithms into a common framework.

In the Preface, we motivate the book by discussing the history of quantum computing and the development of the field of quantum algorithms over the past several decades. We argue that the present moment calls for adopting an end-to-end lens in how we study quantum algorithms, and we discuss the contents of the book and how to use it.

This chapter covers the quantum adiabatic algorithm, a quantum algorithmic primitive for preparing the ground state of a Hamiltonian. The quantum adiabatic algorithm is a prominent ingredient in quantum algorithms for end-to-end problems in combinatorial optimization and simulation of physical systems. For example, it can be used to prepare the electronic ground state of a molecule, which is used as an input to quantum phase estimation to estimate the ground state energy.

This chapter covers quantum linear system solvers, which are quantum algorithmic primitives for solving a linear system of equations. The linear system problem is encountered in many real-world situations, and quantum linear system solvers are a prominent ingredient in quantum algorithms in the areas of machine learning and continuous optimization. Quantum linear systems solvers do not themselves solve end-to-end problems because their output is a quantum state, which is one of its major caveats.

This chapter presents an introduction to the theory of quantum fault tolerance and quantum error correction, which provide a collection of techniques to deal with imperfect operations and unavoidable noise afflicting the physical hardware, at the expense of moderately increased resource overheads.

This chapter covers the quantum algorithmic primitive called quantum gradient estimation, where the goal is to output an estimate for the gradient of a multivariate function. This primitive features in other primitives, for example, quantum tomography. It also features in several quantum algorithms for end-to-end problems in continuous optimization, finance, and machine learning, among other areas. The size of the speedup it provides depends on how the algorithm can access the function, and how difficult the gradient is to estimate classically.

This chapter covers quantum algorithms for numerically solving differential equations and the areas of application where such capabilities might be useful, such as computational fluid dynamics, semiconductor chip design, and many engineering workflows. We focus mainly on algorithms for linear differential equations (covering both partial and ordinary linear differential equations), but we also mention the additional nuances that arise for nonlinear differential equations. We discuss important caveats related to both the data input and output aspects of an end-to-end differential equation solver, and we place these quantum methods in the context of existing classical methods currently in use for these problems.

This chapter covers the quantum algorithmic primitive of approximate tensor network contraction. Tensor networks are a powerful classical method for representing complex classical data as a network of individual tensor objects. To evaluate the tensor network, it must be contracted, which can be computationally challenging. A quantum algorithm for approximate tensor network contraction can provide a quantum speedup for contracting tensor networks that satisfy certain conditions.

This chapter provides an overview of how to perform quantum error correction using the surface code, which is the most well-studied quantum error correcting code for practical quantum computation. We provide formulas for the code distance—which determines the resource overhead when using the surface code—as a function of the desired logical error rate and underlying physical error rate. We discuss several decoders for the surface code and the possibility of experiencing the backlog problem if the decoder is too slow.

This chapter covers quantum tomography, a quantum algorithmic primitive that enables a quantum algorithm to learn a full classical description of a quantum state. Generally, the goal of a quantum tomography procedure is to obtain this description using as few copies of the state as possible. The optimal number of copies may depend on what kind of measurements are allowed and what error metric is being used, and in most cases, quantum tomography procedures have been developed with provably optimal complexity.

This chapter covers the potential use of quantum algorithms for cryptanalysis, that is, the breaking and weakening of cryptosystems. We discuss Shor’s algorithm for factoring and discrete logarithm, which render widely used public-key cryptosystems vulnerable to attack, given access to a sufficiently large-scale quantum computer. We present resource estimates from the literature for running Shor’s algorithm, and we discuss the outlook for postquantum cryptography, which aims to replace existing cryptosystems while being resistant to quantum attack. We also cover quantum approaches for weakening the security of cryptosystems based on Grover’s search algorithm.

This chapter covers the quantum algorithmic primitive of Hamiltonian simulation, which aims to digitally simulate the evolution of a quantum state forward in time according to a Hamiltonian. There are several approaches to Hamiltonian simulation, which are best suited to different situations. We cover approaches for time-independent Hamiltonian simulation based on product formulas, the randomized compiling approach called qDRIFT, and quantum signal processing. We also discuss a method that leverages linear combination of unitaries and truncation of Taylor and Dyson series, which is well suited for time-dependent Hamiltonian simulation

This chapter provides an overview of how to perform a universal set of logical gates on qubits encoded with the surface code, via a procedure called lattice surgery. This is the most well-studied approach for practical fault-tolerant quantum computation. We perform a back-of-the-envelope end-to-end resource estimation for the number of physical qubits and total runtime required to run a quantum algorithm in this paradigm. This provides a method for converting logical resource estimates for quantum algorithms into physical resource estimates.