Macquarie University
01whole.pdf (4.69 MB)

Quantum algorithmic techniques for fault-tolerant quantum computers

Download (4.69 MB)
posted on 2022-03-28, 10:20 authored by Mária Kieferová
Quantum computers have the potential to push the limits of computation in areas such as quantum chemistry, cryptography, optimization, and machine learning. Even though many quantum algorithms show asymptotic improvement compared to classical ones, the overhead of running quantum computers limits when quantum computing becomes useful. Thus, by optimizing components of quantum algorithms, we can bring the regime of quantum advantage closer. My work focuses on developing efficient subroutines for quantum computation. I focus specifically on algorithms for scalable, fault-tolerant quantum computers. While it is possible that even noisy quantum computers can outperform classical ones for specific tasks, high-depth and therefore fault-tolerance is likely required for most applications. In this thesis, I introduce three sets of techniques that can be used by themselves or as subroutines in other algorithms. The first components are coherent versions of classical sort and shuffle. We require that a quantum shuffle prepares a uniform superposition over all permutations of a sequence. The quantum sort is used within the shuffle and as well as in the next algorithm in this thesis. The quantum shuffle is an essential part of state preparation for quantum chemistry computation in first quantization. Second, I review the progress of Hamiltonian simulations and give a new algorithm for simulating time-dependent Hamiltonians. This algorithm scales polylogarithmic in the inverse error, and the query complexity does not depend on the derivatives of the Hamiltonian. A time-dependent Hamiltonian simulation was recently used for interaction picture simulation with applications to quantum chemistry. Next, I present a fully quantum Boltzmann machine. I show that our algorithm can train on quantum data and learn a classical description of quantum states. This type of machine learning can be used for tomography, Hamiltonian learning, and approximate quantum cloning.


Table of Contents

1. Introduction -- 2. Background -- 3. Quantum sort and shuffle -- 4. Simulation of time-dependent Hamiltonians -- 5. Training and tomography with quantum Boltzmann machines -- 6. Conclusion and future work -- Abbreviations -- References -- Appendices.


Degree carried out under a cotutelle program with the University of Waterloo. Empirical thesis. Bibliography: pages139-161

Awarding Institution

Macquarie University

Degree Type

Thesis PhD


PhD, Macquarie University, Faculty of Science and Engineering, Department of Physics and Astronomy

Department, Centre or School

Department of Physics and Astronomy

Year of Award


Principal Supervisor

Dominic Berry

Additional Supervisor 1

Michele Mosca

Additional Supervisor 2

Gavin Brennen


Copyright Mária Kieferová 2019. Copyright disclaimer:




1 online resource (xv, 166 pages) colour illustrations

Former Identifiers


Usage metrics

    Macquarie University Theses


    Ref. manager