  The framework of this thesis is fault-tolerant quantum algorithms. Grover's
algorithm and quantum walks are described in Chapter 2. We start by
highlighting the central role that rotations play in quantum algorithms,
explaining Grover's, why it is optimal, and how it may be extended. Key
subroutines explained in this area are amplitude amplification and quantum
walks, which will constitute useful parts of other algorithms.
  In the third chapter, in contrast, we turn to the exponential advantages
promised by the Fourier transform in the context of the hidden subgroup
problem. However, since this application is restricted to cryptography, we
later explore its use in quantum linear algebra problems. Here we explain the
development of the original quantum linear solver algorithm, its improvements,
and finally the dequantization techniques that would often restrict the quantum
advantage to polynomial.
  Chapter 4 is concerned with quantum simulation. We will review classical
quantum chemistry techniques, and then focus on Hamiltonian simulation and
ground state preparation as the key problems to be solved. Hamiltonian
simulation, in particular, will enable the use of quantum phase estimation
which computes the eigenvalues or energies of a given quantum state.
  Given the tradition of our group with error correction, we could not end this
thesis without dedicating a final chapter to this topic. Here we explain the
most important quantum error correction codes, the surface and color codes, and
one extension of the latter, gauge color codes. They will show the complexity
of implementing non-Clifford quantum gates, therefore validating their
consideration as the bottleneck metric.
