# AMS Short Course

## Quantum Computation and Quantum Information

#### January 3 (8:00 a.m. to 5:00 p.m.) - 4 (9:00 a.m. to 5:00 p.m.), 2009 Virginia Suite A, Lobby Level, Marriott Wardman Park Hotel (Location subject to change) <!-- /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-parent:""; margin:0pt; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman"; mso-fareast-font-family:"Times New Roman";} @page Section1 {size:612.0pt 792.0pt; margin:72.0pt 90.0pt 72.0pt 90.0pt; mso-header-margin:36.0pt; mso-footer-margin:36.0pt; mso-paper-source:0;} div.Section1 {page:Section1;} --> (Preceding the Joint Mathematics Meetings in Washington, DC)

Organized by Samuel J. Lomonaco, University of Maryland Baltimore County

It is planned that lecture notes will be available to those who register for this course. Advance registration fees are: member of the AMS-US$96; nonmember-US$130; student, unemployed, emeritus-US$44. On-site fees are: member of the AMS-US$130; nonmember-US$160; student, unemployed, emeritus-US$65. Detailed registration and housing information (including the registration form) can be found here after September 1, 2008.

For the latest up to date information on this AMS Short Course, please refer to the URL: http://www.csee.umbc.edu/~lomonaco/ams-short-course-2009.html.

### ►General Introduction

The Nobel Laureate Richard Feynman was one of the first individuals to observe that there is an exponential slow down when computers based on classical physics, i.e., classical computers, are used to simulate quantum systems. Richard Feynman then went on to suggest that it would be far better to use computers based on quantum mechanical principles, i.e., quantum computers, to simulate quantum systems. Such quantum computers should be exponentially faster than their classical counterparts.

Interest in quantum computation suddenly exploded when Peter Shor devised an algorithm for quantum computers that could factor integers in polynomial time. The fastest known algorithm for classical computers factors much more slowly, i.e., in superpolynomial time. Shor's algorithm meant that, if quantum computers could be built, then cryptographic systems based on integer factorization, e.g., RSA, could easily be broken. These cryptographic systems are currently extensively used in banking and in many other areas. Lov Grover then went on to create a quantum algorithm that could search data bases faster than anything possible on a classical computer. These algorithms are based on physical principles not implementable on classical computers, quantum superposition and quantum entanglement.

As a result, the race to build a quantum computer is on. But the mathematical, physical, and engineering challenges to do so are formidable, and are a worthy challenge for the best scientific minds. One of the chief obstacles to creating a quantum computer is quantum decoherence. By this we mean that quantum systems want to wander from their computational paths and quantum entangle with the rest of the environment.

This short course focuses on the mathematical challenges involved in the development of quantum computers, quantum algorithms, and quantum information, challenges worthy of the best mathematical minds. It is hoped that, as a result of this course, many mathematicians will be enticed into working on the grand challenge of quantum computation and information.

The short course will begin with an overview of quantum computation and information, given in an intuitive and conceptual style. No prior knowledge of quantum mechanics will be assumed.

In particular, the short course will begin with an introduction to the strange world of the quantum. Such concepts as quantum superposition, Heisenberg's uncertainty principle, the "collapse" of the wave function, and quantum entanglement (i.e., EPR pairs) will be introduced. This will also be interlaced with an introduction to Dirac notation, Hilbert spaces, unitary transformations, quantum measurement.

Some of the topics covered in the course will be:

1) Mathematical models of quantum computation

2) Quantum algorithms

3) Quantum information theory

4) Quantum error-correcting codes

5) Quantum complexity theory

6) The mathematical structure of quantum entanglement and locality

7) Topological quantum computing

8) Quantum knots

9) Implementation issues from a mathematical perspective

Each topic will be explained and illustrated with simple examples.

The course will end with a list of the grand challenges of quantum computation, i.e., a list of mathematical problems that must be solved to make to make the concept of a quantum computer a reality. This will be followed by a panel discussion on the topic "The Past, Present, and Future of Quantum Computation and Quantum Information".

### ►A Rosetta Stone for Quantum Computing

Samuel Lomonaco, University of Maryland Baltimore County (UMBC)

This talk will give an overview of quantum computing in an intuitive and conceptual fashion. No prior knowledge of quantum mechanics will be assumed.

The talk will begin with an introduction to the strange world of the quantum. Such concepts as quantum superposition, Heisenberg's uncertainty principle, the "collapse" of the wave function, and quantum entanglement (i.e., EPR pairs) are introduced. This part of the talk will also be interlaced with an introduction to Dirac notation, Hilbert spaces, unitary transformations, quantum measurement, and the density operator.

Simple examples will be given to explain and to illustrate such concepts as quantum measurement, quantum teleportation, quantum dense coding, and the first quantum algorithm, i.e., the Deutsch-Jozsa algorithm.

The PowerPoint slides for this talk will be posted at the URL: http://www.csee.umbc.edu/~lomonaco/Lectures.html.

References

[1] S. J. Lomonaco, A Rosetta Stone for quantum mechanics with an introduction to quantum mechanics, pages 3-65, in Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium, S. J. Lomonaco, ed., AMS PSAPM/58, 2002. http://arxiv.org/abs/quant-ph/0007045.

[2] S. J. Lomonaco and H. E. Brandt, (eds.), Quantum Computation and Information, AMS CONM/305, (2002).

[3] M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.

[4] M. A. Nielsen, Cluster-state quantum computation, http://arxiv.org/abs/quant-ph/0504097.

[5] A. Peres, Quantum Theory: Concepts and Methods, Kluwer, 1993.

[6] R. Raussendorf, D. E. Browne, and H. J. Briegel, Measurement-based quantum computation with cluster states, http://arxiv.org/abs/quant-ph/0301052.

[7] J. J. Sakuri, Modern Quantum Mechanics (revised edition), Addison-Wesley, 1994.

### ►Quantum Algorithms

Peter Shor, Massachusetts Institute of Technology

We will briefly review the quantum factoring and search algorithms, and then survey recent progress that has been made in quantum algorithms.

References

[1] Peter Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.

[2] Ronald deWolf, Quantum Computation and Shor's Factoring Algorithm.

[3] Lov Grover, A fast quantum mechanical algorithm for database search Grover's Algorithm: Quantum database search, http://arxiv.org/abs/quant-ph/0301079.

[4] Preskill's lecture notes, Chapter 6, http://www.theory.caltech.edu/~preskill/ph229/#lecture.

### ►Concentration of Measure Effects in Quantum Information

Patrick Hayden, McGill University

Quantum information theory studies methods for compressing, transmitting, correcting and encrypting data in a quantum mechanical world. From a mathematical perspective, however, it is in many ways the asymptotic theory of finite dimensional inner product spaces. In these high-dimensional spaces, concentration of measure effects are ubiquitous, and they lead to many surprising applications in the quantum information context. This course will survey some of the highlights, including how to send 2 qubits using only 1, how to encrypt a quantum message using almost no secret key, and how to beat the famous "teleportation" protocol.

References

[1] M. Ledoux,The Concentration of Measure Phenomenon, Amer. Math. Soc., 2001.

[2] P. Hayden, W. C. Leung, P. W. Shor, and A. Winter, Randomizing quantum states, Commun. Math. Phys. 250, no. 2, (2004), pp. 371-391.

[3] P. Hayden, W. C. Leung, and A. Winter, Aspects of generic entanglement, Commun. Math. Phys. 265, no. 1, (2006) pp. 95-117.

### ►Quantum Error Correction and Fault Tolerance

Daniel Gottesman, Perimeter Institute

Errors are likely to be a serious problem for quantum computers, both because they are built of small components and because qubits are inherently more vulnerable to error than classical bits because of processes such as decoherence. Consequently, to build a large quantum computer, we will likely need quantum error-correcting codes, which split up quantum states among a number of qubits in such a way that it is possible to correct for small errors. I will give an overview of the theory of quantum error correction and a brief discussion of fault-tolerant quantum computation, which applies quantum error-correcting codes to allow more reliable quantum computations. I will cover Shor's 9-qubit code, stabilizer codes, CSS codes, and the threshold theorem, which says that arbitrarily long reliable quantum computations are possible, provided the error rate per gate or time step is below some constant threshold value.

References

[1] D. Gottesman, An Introduction to Quantum Error Correction, in Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium, S. J. Lomonaco Jr., ed., Amer. Math. Soc., Providence, RI, 2002, pp. 221-235, quant-ph/0004072.

[2] ------ , Fault-tolerant quantum computation, Physics in Canada 63, No. 4, (Oct.-Dec. 2007), quant-ph/0701112.

[3] J. Preskill, Physics 219 lecture notes, Chapter 7, http://theory.caltech.edu/~preskill/ph229/.

[4] P. Aliferis, D. Gottesman, and J. Preskill, Quantum accuracy threshold for concatenated distance-3 codes, Quant. Information and Computation 6, No. 2, (2006), 97-165, quant-ph/0504218.

### ►Riemannian Geometry of Quantum Computation

Howard Brandt, U. S. Army Research Laboratory

An introduction is given to some recent developments in the differential geometry of quantum computation for which the quantum evolution is described by the special unitary unimodular group in 2^n dimensions, SU(2^n). Using the Lie algebra su(2^n), detailed derivations are given of a useful Riemannian geometry of SU(2^n), including the connection and the geodesic equation for minimal complexity quantum computations. Examples of some solutions to the geodesic equation are elaborated.

References

[1] M. A. Nielsen and I. L. Chuang, Quantum Information and Computation, Cambridge University Press, 2000.

[2] M. A. Nielsen, A geometric approach to quantum circuit lower bounds, Quantum Information and Computation 6 (2006), 213-262.

[3] M. R. Dowling and M. A. Nielsen, The geometry of quantum computation, (2006), arXiv: quant-ph/0701004.

[4] M. A. Naimark and A. I. Stern, Theory of Group Representations, Springer-Verlag, New York (1982).

[5] Mark R. Sepanski, Compact Lie Groups, Springer 2007.

[6] Walter Pfeifer,The Lie Algebras su(N), Birkhäuser, Basel, 2003.

[7] P. Petersen, Riemannian Geometry, 2nd Edition, Springer, New York, 2006.

[8] Bo-Yu Hou and Bo-Yuan Hou, Differential Geometry for Physicists, World Scientific, Singapore, 1997.

[9] H. E. Brandt, "Qubit Devices" in Quantum Computation, AMS Short Course, S. J. Lomonaco,ed., Proc. Symp. Appl. Math. 59, Amer. Math. Soc., Providence, RI, 2000.

[10] S. J. Lomonaco and H. E. Brandt, eds., Quantum computation and information, Contemp. Math. 305, Amer. Math. Soc., Providence, RI, 2000.

### ►Quantum Knots and Mosaics

Samuel Lomonaco, University of Maryland Baltimore County

In this talk, we give a precise and workable definition of a quantum knot system, the states of which are called quantum knots. This definition can be viewed as a blueprint for the construction of an actual physical quantum system.

Moreover, this definition of a quantum knot system is intended to represent the "quantum embodiment" of a closed knotted physical piece of rope. A quantum knot, as a state of this system, represents the state of such a knotted closed piece of rope, i.e., the particular spatial configuration of the knot tied in the rope. Associated with a quantum knot system is a group of unitary transformations, called the ambient group, which represents all possible ways of moving the rope around (without cutting the rope, and without letting the rope pass through itself.)

Of course, unlike a classical closed piece of rope, a quantum knot can exhibit non-classical behavior, such as quantum superposition and quantum entanglement. This raises some interesting and puzzling questions about the relation between topological and quantum entanglement. The knot type of a quantum knot is simply the orbit of the quantum knot under the action of the ambient group. We investigate quantum observables which are invariants of quantum knot type. We also study the Hamiltonians associated with the generators of the ambient group, and briefly look at the quantum tunneling of overcrossings into undercrossings.

A basic building block in this paper is a mosaic system which is a formal (rewriting) system for symbol strings. We conjecture that this formal system fully captures in an axiomatic way all of the properties of tame knot theory.

The PowerPoint slides for this talk will be posted at the URL: http://www.csee.umbc.edu/~lomonaco/Lectures.html.

References

[1] D. Aharonov, V. Jones, and Z. Landau, On the quantum algorithm for approximating the Jones polynomial, http://arxiv.org/abs/quant-ph/0511096.

[2] G. P. Collins, Computing with quantum knots,Sci. Amer., April, 2006, pp. 56-63.

[3] R. H. Crowell and R. H. Fox, Introduction to Knot Theory, Springer-Verlag, (1977).

[4] L. Jacak, P. Sitko, K. Wieczorek, and A. Wojs, Quantum Hall Systems: Braid Groups, Composite Fermions, and Fractional Charge, Oxford University Press, 2003.

[5] L. H. Kauffman and S. J. Lomonaco, Quantum knots, Proc. SPIE, (2004), http://arxiv.org/abs/quant-ph/0403228.

[6] L. H. Kauffman and S. J. Lomonaco Jr., q-Deformed spin networks, knot polynomials, and anyonic topological quantum computation, J. of Knot Theory 16, No. 3, (2007), pp. 267-332, http://xxx.lanl.gov/abs/quant-ph/0606114.

[7] ------ , Spin networks and anyonic topological computing, Proc. SPIE, Vol. 6244, (2006), http://xxx.lanl.gov/abs/quant-ph/0603131.

[8] L. H. Kauffman, Knots and Physics, (3rd edition), World Scientific, 2001.

[9] A. Yu. Kitaev, Fault-tolerant quantum computation by anyons, http://arxiv.org/abs/quant-ph/9707021.

[10] W. B. R. Lickorish, An Introduction to Knot Theory, Springer, 1997.

[11] S. J. Lomonaco and L. H. Kauffman, Quantum knots and mosaics, J. of Quantum Information Processing, April, 2008. http://arxiv.org/abs/0805.0339.

[12] S. J. Lomonaco, The modern legacies of Thomson's atomic vortex theory in classical electrodynamics, AMS PSAPM/51, Providence, RI, 1996, 145-166.

[13] S. J. Lomonaco and L. H. Kauffman, Topological quantum computing and the Jones polynomial, Proc. SPIE, Vol. 6244, (2006), http://xxx.lanl.gov/abs/quant-ph/0605004.

[14] S. J. Lomonaco Jr., Five dimensional knot theory, AMS CONM, vol. 20, (1984), pp. 249-270, http://www.cs.umbc.edu/~lomonaco/5knots/5knots.pdf.

[15] ------ , The homotopy groups of knots I. How to compute the algebraic 3-type, Pacific J. of Math. 95, No. 2, (1981), pp. 349-390.

[16] K. W. Madison, C. F. Wohlleben, and W. J. Dalibard, Vortex formation in a stirred Bose-Einstein condensate, Phys. Rev. Lett. 84, (2000), 806-809.

[17] K. Murasugi, Knot Theory and Its Applications, Birkhäuser, (1996).

[18] M. Rasetti and T. Regge, Vortices in He II, current algebras and quantum knots, Physica 80 A, North-Holland, (1975), 217-2333.

[19] S. D. Sarma, M. Freedman, and C. Nayak, Topologically protected qubits from a possible non-abelian fractional quantum Hall state, Phys. Rev. Letters 94(2005), pp. 166802-1-168802-4.

[20] P. W. Shor and Stephen P. Jordan, Estimating Jones polynomials is a complete problem for one clean qubit, http://arxiv.org/abs/0707.2831.

[21] X.-G. Wen, Quantum Field Theory of Many-Body Systems, Oxford Press, 2004.

### ►Topology and Quantum Computing

Louis H. Kauffman, University of Illinois at Chicago

This short course lecture will discuss relationships between the theory of knots and quantum computing. We will begin by describing a topological approach to the theory of teleportation. In this approach we use diagrammatic matrix algebra whose manipulations can be understood topologically. This serves as an introduction to the interactions of topology and quantum information theory. The lecture will then describe how diagrammatic matrix algebra is related to the construction of link invariants, solutions to the Yang-Baxter equation and representations of the braid group. We will introduce the bracket polynomial state model of the Jones polynomial in this context. We then discuss how the bracket model lies at the basis for the construction of unitary representations of the Artin braid group that are universal for quantum computation. The simplest example is the so-called Fibonacci model. We show how these representations can be used to construct quantum algorithms to compute colored Jones polynomials and the Witten-Reshetikhin-Turaev invariant. If there is time, we shall discuss relations among topological and quantum entanglement and concepts of quantum knots.

References

[1] S. J. Lomonaco and L. H. Kauffman, Quantum knots and mosaics, J. of Quantum Information Processing, April, 2008. http://arxiv.org/abs/0805.0339.

[2] L. H. Kauffman and S. J. Lomonaco, The Fibonacci model and the Temperley-Lieb algebra, http://arxiv.org/abs/0804.4304.

[3] ------ , 3-stranded quantum algorithm for the Jones polynomial, http://arxiv.org/abs/0706.0020.

[4] ------ , q-Deformed spin networks, knot polynomials and anyonic topological quantum computation, http://arxiv.org/abs/quant-ph/0606114.

[5] L. H. Kauffman, Knot diagrammatics, math.GN/0410329.

[6] L. H. Kauffman and S. J. Lomonaco, Quantum knots, http://arxiv.org/abs/quant-ph/0403228.

[7] ------ , Entanglement criteria--Quantum and topological, http://arxiv.org/abs/quant-ph/0304091.

[8] L. H. Kauffman, Quantum computing and the Jones polynomial, math.QA/0105255.

[9] ------ , Knots and Physics, World Scientific, 2001.

[10] L. H. Kauffman and S. Lins,Temperley-Lieb Recoupling Theory and Invariants of Three-Manifolds, Princeton University Press, 1996.

### ►Panel Discussion: The Grand Mathematical Challenges for Quantum Computation and Quantum Information

Panelists: H. Brandt, D. Gottesman, P. Hayden, L. Kauffman, S. Lomonaco, P. Shor.