The main results of this thesis fall in to two areas, firstly quantum reference frames as a resource for quantum computations and secondly quantum algorithms. The results relating to quantum references consider their scaling with a requirements to perform measurements, operations and computations with a certain fidelity. For the case of a directional frame, the central question considered is of how many operations or measurements can be performed with it before its fidelity falls below some threshold. This is found to scale as the square of the size of the reference frame under for a range of physically interesting cases. To prove that result a new general form for any rotationally invariant map. This could have many applications is comparing and classifying rotationally invariant behaviour of quantum systems. Phase references are also considered for the case of performing quantum computations under an energy conservation law. The restriction that the expected energy be conserved for large quantum computations is shown to be manageable in many different potential architectures. In the case of completing computations is an energy conserving subspace, the requirements for ancillas are sublinear in the number of qubits, and even in a circuit model implementation, the errors due to phase reference imperfections are shown to not limit the apparent algorithmic improvements of quantum computing over classical computing. \n \nA quantum walk for the novel concept of two entangled walkers is proposed and analyzed. A modest improvement is found in the scaling of the expected separation of the walkers over the separable case. It illustrates the potential for making use of particle statistic behaviour in algorithms. Lastly, the relation between discrete and continuous time models of quantum computing is explored through the analysis of a new algorithm for simulating the Hamiltonian behaviour of a black box unitary operation. The scaling of the number of calls to the unitary required to obtain a simulation correct to within a parameter ϵ is found, as is a case where the efficiency of the algorithm is superior to directly applying the unitary repeatedly. Applications of the algorithm are considered.
The main results of this thesis fall in to two areas, firstly quantum reference frames as a resource for quantum computations and secondly quantum algorithms. The results relating to quantum references consider their scaling with a requirements to perform measurements, operations and computations with a certain fidelity. For the case of a directional frame, the central question considered is of how many operations or measurements can be performed with it before its fidelity falls below some threshold. This is found to scale as the square of the size of the reference frame under for a range of physically interesting cases. To prove that result a new general form for any rotationally invariant map. This could have many applications is comparing and classifying rotationally invariant behaviour of quantum systems. Phase references are also considered for the case of performing quantum computations under an energy conservation law. The restriction that the expected energy be conserved for large quantum computations is shown to be manageable in many different potential architectures. In the case of completing computations is an energy conserving subspace, the requirements for ancillas are sublinear in the number of qubits, and even in a circuit model implementation, the errors due to phase reference imperfections are shown to not limit the apparent algorithmic improvements of quantum computing over classical computing. \n \nA quantum walk for the novel concept of two entangled walkers is proposed and analyzed. A modest improvement is found in the scaling of the expected separation of the walkers over the separable case. It illustrates the potential for making use of particle statistic behaviour in algorithms. Lastly, the relation between discrete and continuous time models of quantum computing is explored through the analysis of a new algorithm for simulating the Hamiltonian behaviour of a black box unitary operation. The scaling of the number of calls to the unitary required to obtain a simulation correct to within a parameter ϵ is found, as is a case where the efficiency of the algorithm is superior to directly applying the unitary repeatedly. Applications of the algorithm are considered.
Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we study the application of quantum computers to computational problems in science and engineering, and to combinatorial optimization problems. We outline the results below. Algorithms for scientific computing require modules, i.e., building blocks, implementing elementary numerical functions that have well-controlled numerical error, are uniformly scalable and reversible, and that can be implemented efficiently. We derive quantum algorithms and circuits for computing square roots, logarithms, and arbitrary fractional powers, and derive worst-case error and cost bounds. We describe a modular approach to quantum algorithm design as a first step towards numerical standards and mathematical libraries for quantum scientific computing. A fundamental but computationally hard problem in physics is to solve the time-independent Schrödinger equation. This is accomplished by computing the eigenvalues of the corresponding Hamiltonian operator. The eigenvalues describe the different energy levels of a system. The cost of classical deterministic algorithms computing these eigenvalues grows exponentially with the number of system degrees of freedom. The number of degrees of freedom is typically proportional to the number of particles in a physical system. We show an efficient quantum algorithm for approximating a constant number of low-order eigenvalues of a Hamiltonian using a perturbation approach. We apply this algorithm to a special case of the Schrödinger equation and show that our algorithm succeeds with high probability, and has cost that scales polynomially with the number of degrees of freedom and the reciprocal of the desired accuracy. This improves and extends earlier results on quantum algorithms for estimating the ground state energy. We consider the simulation of quantum mechanical systems on a quantum computer. We show a novel divide and conquer approach for Hamiltonian simulation. Using the Hamiltonian structure, we can obtain faster simulation algorithms. Considering a sum of Hamiltonians we split them into groups, simulate each group separately, and combine the partial results. Simulation is customized to take advantage of the properties of each group, and hence yield refined bounds to the overall simulation cost. We illustrate our results using the electronic structure problem of quantum chemistry, where we obtain significantly improved cost estimates under mild assumptions. We turn to combinatorial optimization problems. An important open question is whether quantum computers provide advantages for the approximation of classically hard combinatorial problems. A promising recently proposed approach of Farhi et al. is the Quantum Approximate Optimization Algorithm (QAOA). We study the application of QAOA to the Maximum Cut problem, and derive analytic performance bounds for the lowest circuit-depth realization, for both general and special classes of graphs. Along the way, we develop a general procedure for analyzing the performance of QAOA for other problems, and show an example demonstrating the difficulty of obtaining similar results for greater depth. We show a generalization of QAOA and its application to wider classes of combinatorial optimization problems, in particular, problems with feasibility constraints. We introduce the Quantum Alternating Operator Ansatz, which utilizes more general unitary operators than the original QAOA proposal. Our framework facilitates low-resource implementations for many applications which may be particularly suitable for early quantum computers. We specify design criteria, and develop a set of results and tools for mapping diverse problems to explicit quantum circuits. We derive constructions for several important prototypical problems including Maximum Independent Set, Graph Coloring, and the Traveling Salesman problem, and show appealing resource cost estimates for their implementations.
The simulation of quantum physical systems is expected to be an important application for quantum computers. The work presented in this dissertation aims to improve the resource requirements of quantum computers for solving simulation problems, by providing both novel quantum algorithms and improved implementations of existing ones. I present three main results that cover diverse aspects of simulation including equilibrium physics, the preparation of useful quantum states, and simulations based on classical stochastic processes. The results rely on established quantum algorithms and other recent techniques which I review. My first original contribution is a new quantum algorithm to sample from the thermal Gibbs state of quantum Hamiltonians. The complexity of this algorithm has an exponentially improved dependence on precision compared to an earlier quantum algorithm, and also provides polynomial improvements in other parameters. My second contribution is an improved algorithm to implement reflections about the eigenstates of unitary operators and Hamiltonians, an operation that can be used to prepare ground states of many-body Hamiltonians by quantum amplitude amplification. The improved algorithm for implementing reflections significantly reduces the number of ancilla qubits required over earlier implementations. The improvement relies in part on a novel quantum algorithm for efficiently preparing states with Gaussian-like amplitudes, which may have broad applications. I also prove a lower bound for implementing reflections, which shows that our algorithm is almost optimal. My third and final contribution regards quantum algorithms for classical stochastic processes, which are of importance in statistical physics. I present a quantum algorithm that estimates the average running time of a stochastic process, and provides a quadratic speed-up over a comparable classical algorithm.
This thesis addresses a number of problems within the emerging field of quantum information science. Quantum information science can be said to encompass the more-established disciplines of quantum computation and quantum information, as well as rather more recent attempts to apply concepts, tools and techniques from these disciplines to gain greater understanding of quantum systems in general. The role of entanglement — non-classical correlation — has been of particular interest to date. Part I contributes to this later goal. In particular, we establish a connection between the energy of a many-body quantum system and the idea of an entanglement witness from the theory of mixed-state entanglement. This connection allows mathematical results about entanglement witnesses to be translated into physical results about many-body quantum systems, specifically energy and temperature thresholds for entanglement. For the case of two qubits we are able to establish fairly detailed results about the behaviour of entanglement with temperature. We also study entanglement in systems of indistinguishable particles, where even the question of which quantum states should be regarded as entangled has been the subject of much controversy. We aim to clarify this issue by applying Wiseman and Vaccaro’s notion of entanglement of particles to a number of wellunderstood model systems. We discuss the advantages of the entanglement of particles approach compared with other methods in common use. Finally, we study the operational meaning of superselection rules in quantum physics, in particular the connection to the existence or not of an appropriate reference frame. We propose an experiment that aims to exhibit a coherent superposition of an atom and a molecule, apparently in violation of the commonly-accepted particle-number superselection rule. This result sheds light on the entanglement of particles approach to entanglement of indistinguishable particles. Part II returns to a fundamental question at the heart of quantum computation and quantum information, namely: how many quantum gates are required to perform a particular quantum computation? In other words, how efficiently can a quantum computer solve a particular computational problem? We establish a connection between this question and the field of Riemannian geometry. Intuitively, optimal quantum circuits correspond to “free-falling” along the shortest path between two points in a curved space. This opens up the possibility of using Riemannian geometry to study quantum computation, a possibility that was previously unknown. We provide explicit calculations of all the basic geometric quantities associated with the space, and give some preliminary results of applying geometric ideas to quantum computing. Finally, we explore more generally the connection between optimal control and quantum circuit complexity, of which the Riemannian metric described above can be viewed as a special case.
Quantum computing can provide speedups in solving many problems as the evolution of a quantum system is described by a unitary operator in an exponentially large Hilbert space. Such unitary operators change the phase of their eigenstates and make quantum algorithms fundamentally different from their classical counterparts. Based on this unique principle of quantum computing, we develop an algorithmic toolbox, quantum phase processing, that can directly apply arbitrary trigonometric transformations to eigenphases of a unitary operator. The quantum phase processing circuit is constructed simply, consisting of single-qubit rotations and controlled unitaries, typically using only one ancilla qubit. Besides the capability of phase transformation, quantum phase processing in particular can extract the eigeninformation of quantum systems by simply measuring the ancilla qubit, making it naturally compatible with indirect measurement. Quantum phase processing complements another powerful framework known as quantum singular value transformation and leads to more intuitive and efficient quantum algorithms for solving problems that are particularly phase related. As a notable application, we propose a quantum phase estimation algorithm without quantum Fourier transform, which requires the fewest ancilla qubits and matches the best performance so far. We further exploit the power of our method by investigating a plethora of applications in Hamiltonian simulation, entanglement spectroscopy, and quantum entropy estimation, demonstrating improvements or optimality for almost all cases.
In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist. With the purpose of finding new techniques to develop quantum algorithms, there has been an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development. We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators. In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive. Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require classical hardware and software.
In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist.
With the purpose of finding new techniques to develop quantum algorithms, there has been
an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development.
We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators.
In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive.
Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require
classical hardware and software.