Quantum Algorithms and Quantum Entanglement Barbara Terhal Abstract: %Nr: DS-1999-04 %Title: Quantum Algorithms and Quantum Entanglement %Author: Barbara M. Terhal Quantum Information Processing is an interdisciplinary field of research at the crossroads of physics and computer science. The computer science aspect is expressed by the fact that the main application of the research lies in computers, information processing and communication. The physics aspect relies on the use of quantum mechanics and quantum mechanical phenomena to enhance this computational and information processing power. The physical basis of the successful digital technology that has emerged since the 1960s has undergone few changes. The developments in semiconductor technology have enabled us to build smaller and faster CPU and memory chips. This trend is accompanied by similar progress in the technology of magnetic storage and retrieval. When extrapolating the current trend of miniaturization of silicon chips to the future, we may expect to reach an atomic level around the year 2020. At this scale quantum mechanics is an indispensable tool in describing the phenomena of nature. Scaling of the current computer architecture to this regime will be severely limited by the problem of heat generation. With these considerations in mind, the notion of intrinsically reversible quantum computing arises naturally. Essential properties of quantum mechanical systems such as the superposition principle, interference and quantum entanglement lie at the basis at this proposal for a new technology. Over the past 15 years researchers in this field have found that the use of quantum bits, as opposed to 'classical' bits, can present many advantages and that quantum information is unlike classical information in many respects. In terms of computational power the most striking achievement is the factoring quantum algorithm developed by Peter Shor (see Section 2.1.1). A quantum computer can factor a number N in time polynomially related to the size of the input, i.e. O(log N ), whereas the best classical algorithm takes exponential time. Another example is the quantum key distribution protocol invented by Charlies Bennett and Gilles Brassard in 1982. The protocol enables two parties to construct a shared secret random (classical) key by transmission of quantum states and classical states over a channel on which potential eavesdroppers may be listening. The physical realizability of a quantum information processor is an issue which presents a major challenge to physicists. On the theoretical side, the field has seen the development of quantum error correcting codes and faulttolerant computation which are sine qua nons for the ultimate feasibility of a quantum computer. On the experimental side, we are at the stage of creating and manipulating 1-4 qubits in a variety of physical systems such a liquid state NMR, ions in a trap, cavity QED and solid state quantum dots. Thesis ------ The two main topics of this thesis are Quantum Algorithms and Quantum Entanglement. What problems does a quantum computer solve faster than a classical machine? In Chapter 2, we consider three types of problems. The first problem is the determination of the mean value of a given function over a sample set, where the function is presented as an oracle. We show in Section 2.2.1 that a square-root speed up, compared to a classical setting, can be obtained by applying the method of generalized counting which is based from Grover's quantum search algorithm. The second set of problems (Section 2.3) considers information retrieval from a database. We show that classical information theoretic bounds are invalid in a quantum setting and we show how to apply a single query quantum algorithm to the problem of coin weighing. Our last problem, iterated function application, is an oracle problem for which we prove that a quantum computer does not provide a speed-up (Section 2.4). In Chapters 3 and 4 we investigate how to perform physical simulations of quantum systems on a quantum computer. In Chapter 3, we consider how to (space) efficiently implement an arbitary superoperator on a qubit system. We prove that, contrary to a prior conjecture, there are superoperators which need at least an additional two qubit system to be implemented. Our proof uses the computer algebra technique of Gr"obner bases to determine that a system of nonlinear equations does not have a solution. In Chapter 4, we study the problem of computing correlations functions and preparing a thermal equilibrium state of a physical system on a quantum computer. In Section 4.1 we determine a quantum algorithm which, given a local Hamiltonian and a temperature, provably converges to the thermal equilibrium state of the corresponding Hamiltonian. The algorithm constitutes the first example of a quantum algorithm based on a quantum Markov chain. In Section 4.2.3 we prove several general properties of quantum Markov chains which lie at the basis of a theory of quantum Markov chains for quantum computational purposes. In Sections 4.2.7 and 4.2.8 we study the properties of the quantum algorithm by a numerical simulation. In Section 4.3 an alternative quantum algorithm for thermal equilibration is presented which uses Kitaev's eigenvalue-estimation routine. In Section 4.4 we show that given the ability to create an approximation of the thermal equilibrium state, the estimation of time-dependent correlation functions can be efficiently (polynomial time) carried out on a quantum computer. In Chapter 5 we report on several results in studying fundamental properties of quantum mechanical systems. One of the crucial properties of quantum systems is their capacity to be entangled. In Section 5.2 we summarize several features of the emerging theory of entanglement, in particular the relation with positive linear maps. Quantum entanglement can be a source of non-locality as expressed by (a violation of) a Bell inequality. The violation of a Bell inequality indicates that the statistics of outcomes of local measurements on, for example, a maximally entangled state, cannot be described by a local hidden variable theory. The question of interest is whether all entangled states violate a Bell inequality, and are therefore 'non-local' in this way. In Section 5.3 we show that the problem of deciding whether a state violates a Bell inequality and the problem of deciding whether a state is entangled are very similar problems in convex geometry. The problems are however not identical. We prove under what restrictions of the local hidden variable theory the two criteria do coincide. Quantum entanglement is a resource in quantum information theory. Sharing of quantum entanglement enables parties to perform (quantum) information processing tasks (quantum teleportation, transmission of classical data etc.) which are impossible or can only be carried out with less efficieny without the use of entanglement. It is therefore of great importance to develop a classification of different types of quantum entanglement in terms of its ability to enhance quantum information processing. This entanglement classification is derived from considering the properties of the set of quantum operations that do not enhance entanglement; this is the set of local quantum operations and classical communication. In Section 5.4 a class of entangled states is constructed which are not convertible (by local quantum operations and classical communication) to a set of maximally entangled states. The entanglement of these states is called bound, since the entanglement of these states is locked away and cannot be fruitfully used for information processing. Few examples of this type of entanglement were previously known; we develop a construction method that gives rise to many examples of bound entanglement. The method introduces new concepts such as unextendible and uncompletable product bases, for which we find a useful representation by means of a (orthogonality) graph. The interest in these basis is twofold. On the one hand they give rise to the aforementioned bound entangled states (Section 5.4.3). On the other hand we prove that the states in an uncompletable product basis have the feature of not being locally distinguishable, even though these are mutually orthogonal product states (Section 5.4.5). In this way, they form a new illustration of the phenomenon of nonlocality without entanglement. In Section 5.5 we show how an unextendible product basis can be used to construct indecomposable positive linear maps. The problem of finding (indecomposable) positive linear maps has been notoriously hard; the method developed in this thesis offers a construction which generates a whole new family of positive linear maps and is amenable to further generalizations.