| Popis: |
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... |
