Introduction to Quantum Information and Computation for Chemistry

Sabre Kais

Department of Chemistry and Physics, Purdue University, 560 Oval Drive, West Lafayette, IN 47907, USA; Qatar Environment & Energy Research Institute (QEERI), Doha, Qatar; Santa Fe Institute, Santa Fe, NM 87501, USA

I. Introduction

The development and use of quantum computers for chemical applications has the potential for revolutionary impact on the way computing is done in the future [1–7]. Major challenge opportunities are abundant (see next fifteen chapters). One key example is developing and implementing quantum algorithms for solving chemical problems thought to be intractable for classical computers. Other challenges include the role of quantum entanglement, coherence, and superposition in photosynthesis and complex chemical reactions. Theoretical chemists have encountered and analyzed these quantum effects from the view of physical chemistry for decades. Therefore, combining results and insights from the quantum information community with those of the chemical physics community might lead to a fresh understanding of important chemical processes. In particular, we will discuss the role of entanglement in photosynthesis, in dissociation of molecules, and in the mechanism with which birds determine magnetic north. This chapter is intended to survey some of the most important recent results in quantum computation and quantum information, with potential applications in quantum chemistry. To start with, we give a comprehensive overview of the basics of quantum computing (the gate model), followed by introducing quantum simulation, where the phase estimation algorithm (PEA) plays a key role. Then we demonstrate how PEA combined with Hamiltonian simulation and multiplicative inversion can enable us to solve some types of linear systems of equations described by . Then our subject turns from gate model quantum computing (GMQC) to adiabatic quantum computing (AQC) and topological quantum computing, which have gained increasing attention in the recent years due to their rapid progress in both theoretical and experimental areas. Finally, applications of the concepts of quantum information theory are usually related to the powerful and counter intuitive quantum mechanical effects of superposition, interference, and entanglement.

Throughout history, man has learned to build tools to aid computation. From abacuses to digital microprocessors, these tools epitomize the fact that laws of physics support computation. Therefore, a natural question arises: “Which physical laws can we use for computation?” For a long period of time, questions such as this were not considered relevant because computation devices were built exclusively based on classical physics. It was not until the 1970s and 1980s when Feynmann [8], Deutsch [9], Benioff [10], and Bennett [11] proposed the idea of using quantum mechanics to perform calculation that the possibility of building a quantum computing device started to gain some attention.

What they conjectured then is what we call today a quantum computer. A quantum computer is a device that takes direct advantage of quantum mechanical phenomena such as superposition and entanglement to perform calculations [12]. Because they compute in ways that classical computers cannot, for certain problems quantum algorithms provide exponential speedups over their classical counterparts. As an example, in solving problems related to factoring large numbers [13] and simulation of quantum systems [14–28], quantum algorithms are able to find the answer exponentially faster than classical algorithms. Recently, it has also been proposed that a quantum computer can be useful for solving linear systems of equations with exponential speedup over the best-known classical algorithms [29]. In the problem of factoring large numbers, the quantum exponential speedup is rooted in the fact that a quantum computer can perform discrete Fourier transform exponentially faster than classical computers [12]. Hence, any algorithm that involves Fourier transform as a subroutine can potentially be sped up exponentially on a quantum computer. For example, efficient quantum algorithms for performing discrete sine and cosine transforms using quantum Fourier transform have been proposed [30]. To illustrate the tremendous power of the exponential speedup with concrete numbers, consider the following example: the problem of factoring a 60-digit number takes a classical computer 3 × 1011 years (about 20 times the age of universe) to solve, while a quantum computer can be expected to factor a 60-digit number within 10−8 seconds. The same order of speedup applies for problems of quantum simulation.

In chemistry, the entire field has been striving to solve a number of “Holy Grail” problems since their birth. For example, manipulating matter on the atomic and molecular scale, economic solar splitting of water, the chemistry of consciousness, and catalysis on demand are all such problems. However, beneath all these problems is one common problem, which can be dubbed as the “Mother of All Holy Grails: exact solution of the Schrödinger equation. Paul Dirac pointed out that with the Schrödinger equation, “the underlying physical laws necessary for the mathematical theory of a large part of physics and the whole of chemistry are thus completely known and the difficulty is only that the exact application of these laws leads to equations much too complicated to be soluble” [31]. The problem of solving the Schrödinger equation is fundamentally hard [32, 33] because as the number of particles in the system increases, the dimension of the corresponding Hilbert space increases exponentially, which entails exponential amount of computational resource.

Faced with the fundamental difficulty of solving the Schrödinger equations exactly, modern quantum chemistry is largely an endeavor aimed at finding approximate methods. Ab initio methods [34] (Hartree–Fock, Moller–Plesset, coupled cluster, Green's function, configuration interaction, etc.), semi-empirical methods (extended Huckel, CNDO, INDO, AM1, PM3, etc.), density functional methods [35] (LDA, GGA, hybrid models, etc.), density matrix methods [36], algebraic methods [37] (Lie groups, Lie algebras, etc.), quantum Monte Carlo methods [38] (variational, diffusion, Green's function forms, etc.), and dimensional scaling methods [39] are all products of such effort over the past decades. However, all the methods devised so far have to face the challenge of unreachable computational requirements as they are extended to higher accuracy to larger systems. For example, in the case of full CI calculation, for N orbitals and m electrons there are ways to allocate electrons among orbitals. Doing full configuration interaction (FCI) calculations for methanol (CH3OH) using 6-31G (18 electrons and 50 basis functions) requires about 1017 configurations. This task is impossible on any current computer. One of the largest FCI calculations reported so far has about 109 configurations (1.3 billion configurations for Cr2 molecules [40]).

However, due to exponential speedup promised by quantum computers, such simulation can be accomplished within only polynomial amount of time, which is reasonable for most applications. As we will show later, using the phase estimation algorithm, one is able to calculate eigenvalues of a given Hamiltonian H in time that is polynomial in O(log N), where N is the size of the Hamiltonian. So in this sense, quantum computation and quantum information will have enormous impact on quantum chemistry by enabling quantum chemists and physicists to solve problems beyond the processing power of classical computers.

The importance of developing quantum computers derives not only from the discipline of quantum physics and chemistry alone, but also from a wider context of computer science and the semiconductor electronics industry. Since 1946, the processing power of microprocessors has doubled every year simply due to the miniaturization of basic electronic components on a chip. The number of transistors on a single integrated circuit chip doubled every 18 months, which is a fact known as Moore's law. This exponential growth in the processing power of classical computers has spurred revolutions in every area of science...