Fault tolerant quantum algorithms

Abstract

The framework of this thesis is fault-tolerant quantum algorithms, which can roughly be divided into the following non-disjoint families: a) Grover’s algorithm and quantum walks, b) Shor’s algorithm and hidden subgroup problems, c) quantum simulation algorithms, d) quantum linear algebra, and e) variational quantum algorithms. All of them are covered, to some extent, in this thesis. 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 this chapter, we present our Ref. [62], where we explore the heuristic use of quantum Metropolis and quantum walk algorithms for solving anNP-hard problem. This method has been suggested as an avenue to digitally simulate quantum annealing and preparing ground states of many-body Hamiltonians. In the third chapter, in contrast, we turn to the exponential advantages promisedby 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...El marco conceptual de esta tesis son los algoritmos cuánticos tolerantes a fallos, que pueden dividirse aproximadamente en las siguientes clases no mutuamente excluyentes :a) algoritmo de Grover y paseos cuánticos, b) algoritmo de Shor y problemas de subgrupos ocultos, c) algoritmos de simulación cuántica, d) álgebra lineal cuántica, ye) algoritmos cuánticos variacionales. Todos ellos se tratan, en cierta medida, en esta tesis. El algoritmo de Grover y los paseos cuánticos se explican en el capítulo 2. Comenzamos destacando el papel central que juegan las rotaciones en los algoritmos cuánticos, explicando el de Grover, por qué es óptimo, y cómo puede ser extendido. Las subrutinas clave explicadas en esta área son la amplificación de la amplitud y los paseos cuánticos, que serán partes importantes de otros algoritmos. En este capítulo presentamos nuestra Ref. [62], donde exploramos el uso heurístico de los algoritmos de Metrópolis y paseos cuánticos para resolver problemas NP-difíciles. De hecho, este método ha sido sugerido como una vía para simular digitalmente el método conocido como ‘quantum annealing’,y la preparación de estados fundamentales de Hamiltonianos ‘many-body’.En el tercer capítulo, en cambio, nos centramos en las ventajas exponenciales que promete la transformada de Fourier en el contexto del problema de los subgrupos ocultos. Sin embargo, dado que esta aplicación está restringida a la criptografía, más adelante exploramos su uso en problemas de álgebra lineal cuántica. Aquí explicamos el desarrollo del algoritmo cuántico original para la resolución de sistemas lineales de ecuaciones, sus mejoras, y finalmente las técnicas de ‘descuantización’ que a menudo restringen la ventaja cuántica a polinómica...