2
Adiabatic Quantum Computing

Search algorithms are among the most important and fundamental algorithms in computer science, the most basic example being that of finding one special item among a list of N items. Classical algorithms are known to solve this problem in time proportional to the problem size, N, which becomes highly untractable when the latter grows large. In 1996, Grover   [117] devised a quantum algorithm to solve such search problems with a quadratic speedup, with the obvious caveat that quantum computers did not exist at the time. Soon after, Farhi, Goldstone, Gutmann and Sipser  [98] recast the Grover problem as a satisfiability problem in the context of quantum computation by adiabatic evolution.

Another class of problems hard to solve classically is that of combinatorial optimisation problems. The truck dispatching problem, originally proposed by Dantzig and Ramser  [78], searches the optimal routing of delivery trucks, and is a generalisation...

3
Quadratic Unconstrained Binary Optimisation

Undoubtedly, Quadratic Unconstrained Binary Optimisation (QUBO) is a flagship use case of quantum annealing. We only need to have a closer look at the name of this class of optimisation problems to see why:

• Quantum annealers operate on binary spin variables. It is straightforward to perform mapping between binary decision variables (represented by the logical qubits) and spin variables.
• The objective functions of quadratic optimisation problems have only linear and quadratic terms. This significantly simplifies the models and allows their embedding on existing quantum annealing hardware.
• Unconstrained optimisation means that although QUBO allows us to specify conditions that must be satisfied, they are not hard constraints. The violation of constraints is penalised through the additional terms in the QUBO objective function, but it is still possible to find solutions that violate specified constraints.

All these features make QUBO problems...

4
Quantum Boosting

In this chapter, we consider a quantum version of the classical boosting meta-algorithm – a family of machine learning algorithms that convert weak classifiers into strong ones. Classically, boosting consists of two main operations: i) adaptive (iterative) training of the weak classifiers, thus improving their individual performance, and ii) finding an optimal configuration of weights applied to the individual weak learners when combining them into a single strong one.

Adaptive learning consists of iterative re-weighting of the samples from the training dataset, forcing the model to improve its performance on the difficult-to-classify samples by giving them heavier weights. These weights are adjusted at each algorithm iteration. Arguably, the best-known and most successful example of such algorithms is the popular adaptive boosting (AdaBoost) model. It was first formulated in 1997 by Freund and Schapire   [107], whose work has been recognised...

5
Quantum Boltzmann Machine

As we saw in Chapters 3 and 4, quantum annealing can be used to solve hard optimisation problems. However, the range of possible applications of quantum annealing is much wider than that. In this chapter, we will consider two distinct but related use cases that go beyond solving optimisation problems: sampling and training deep neural networks. Specifically, we will focus on the Quantum Boltzmann Machine (QBM) – a generative model that is a direct quantum annealing counterpart of the classical Restricted Boltzmann Machine (RBM), and the Deep Boltzmann Machine (DBM) – a class of deep neural networks composed of multiple layers of latent variables with connections between the layers but not between units within each layer.

We start by providing detailed descriptions of the classical RBM, including the corresponding training algorithm. Due to the fact that an RBM operates on stochastic binary activation units, one can establish the correspondence...