The problem considered in this thesis is the following: We are given a Hamiltonian H and time t, and our goal is to approximately implement the unitary operator e^{-iHt} with an efficient quantum algorithm. We present an efficient algorithm for simulating sparse Hamiltonians. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian acts, this algorithm uses (d^2(d+log^* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log^* N)||Ht||)^{1+o(1)}. In terms of the parameter t, these algorithms are essentially optimal due to a no--fast-forwarding theorem. In the second part of this thesis, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, and rule out generic simulations taking time o(||Ht||), even though ||H|| is not a unique measure of the size of a dense Hamiltonian H. We also present a stronger limitation ruling out the possibility of generic simulations taking time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walks cannot be dramatically improved in general. We also show some positive results about simulating structured Hamiltonians efficiently.

The problem considered in this thesis is the following: We are given a Hamiltonian H and time t, and our goal is to approximately implement the unitary operator e^{-iHt} with an efficient quantum algorithm. We present an efficient algorithm for simulating sparse Hamiltonians. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian acts, this algorithm uses (d^2(d+log^* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log^* N)||Ht||)^{1+o(1)}. In terms of the parameter t, these algorithms are essentially optimal due to a no--fast-forwarding theorem. In the second part of this thesis, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, and rule out generic simulations taking time o(||Ht||), even though ||H|| is not a unique measure of the size of a dense Hamiltonian H. We also present a stronger limitation ruling out the possibility of generic simulations taking time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walks cannot be dramatically improved in general. We also show some positive results about simulating structured Hamiltonians efficiently.

Abstract Iris The power of quantum computing lies in its ability to perform certain calculations and solve complex problems exponentially faster than classical computers. This potential has profound implications for a wide range of fields, including particle physics. This thesis lays a fundamental foundation for understanding quantum computing. Particular emphasis is placed on the intricate process of quantum gate decomposition, an elementary lynchpin that underpins the development of quantum algorithms and plays a crucial role in this research. In particular, this concerns the implementation of quantum algorithms designed to simulate the dynamic evolution of multi-particle quantum systems - so-called Hamiltonian simulations. The concept of quantum gate decomposition is introduced and linked to quantum circuit optimisation. The decomposition of quantum gates plays a crucial role in fault-tolerant quantum computing in the sense that an optimal implementation of a quantum gate is essential to efficiently perform a quantum simulation, especially for near-term quantum computers. Part of this thesis aims to propose a new explicit tensorial notation of quantum computing. Two notations are commonly used in the literature. The first is the Dirac notation and the other standard formalism is based on the so-called computational basis. The main disadvantage of the latter is the exponential growth of vector and matrix dimensions and the fact that it hides some relevant quantum properties of the operations by increasing the apparent number of independent variables. A third possible notation is introduced here, which describes qubit states as tensors and quantum gates as multilinear or quasi-multilinear maps. Some advantages for the detection of separable and entangled systems and for measurement techniques are also shown. Finally, this thesis demonstrates the advantage of quantum computing in the description of multi-particle quantum systems by proposing a quantum algorithm to simulate collective neutrino oscillations. Collective flavour oscillations of neutrinos due to forward neutrino-neutrino scattering provide an intriguing many-body system for time evolution simulations on a quantum computer. These phenomena are of particular interest in extreme astrophysical settings such as core-collapse supernovae, neutron star mergers and the early universe. A detailed description of the physical phenomena and environments in which collective flavor oscillations occur is first reported, and the derivation of the Hamiltonian governing the evolution of flavor oscillations is detailed. The aim is to reproduce this evolution using a quantum algorithm. To manage the computational complexity, we use the Trotter approximation of the time evolution operator, which mitigates the exponential growth of circuit complexity. The quantum algorithm was designed to work on a trapped-ion based testbed (the theory of which is presented in detail). After machine-aware optimisation, the quantum circuit implementing the algorithm was run on the real quantum machine 'Quantinuum', and the results are presented and discussed.