Appendix E
Selected Topics for Student Presentations
Although its history is relatively recent, quantum computing is already, by all standards, a very broad area of research. There is simply no way we can cover anything more than a relatively small fraction of its interesting topics. There are also many fascinating themes that are not exactly part of quantum computing per se, but are nevertheless closely related to it.
In this appendix, we list a number of suggestions for further exploration, covering some items we omitted from our text. It is our sincere hope that students will find them useful for their presentations or perhaps inspire them to select others that they can discover on their own.
Note to the student: Now it is your turn! The best way to really learn something is to teach it. There is no substitute for spending hours preparing a lecture and getting ideas straight so that you can present them. Knowing that other people will be asking you questions and learning from you will force you to understand the material at a deeper level.
You are urged to choose a subject from an area that you find interesting. Much time and energy is going to be spent learning, understanding, and preparing, so you might as well enjoy your choice from the start.
For each of these topics, there are many different levels on which you can go about making a presentation. You can present a superficial lecture in which the bare outline of the idea is discussed, or you can get into the “nitty-gritty” of the technical details. Obviously, the superficial route is the easier one, but not much will be gained from such an exercise. We urge you to understand and present a topic with the utmost detail and depth. A presentation with a lot of hand waving is noticeably deficient. In contrast, one with equations and nice diagrams demonstrates understanding and knowledge. Do not just throw a few equations on the blackboard: show how they are derived. Develop charts and diagrams. Obviously, if the presentation is done in a classroom setting, there are time considerations as well.
How do you go about preparing for such a task? The first thing to do is to look for a popular account of the topic. This can be in a nontechnical magazine or on Web page. Some of the subjects are historical; hence, a look into a few encyclopedias might be helpful. Many nontechnical articles have suggestions for further reading. Once an introductory article is understood, you should move on to deeper, more detailed material. This is the safest and most effective way for you to go forward in your research.
Note to the teacher: If you are going to insist that students make presentations, we recommend that they choose their topics as early as possible in the semester. The more time they are given to prepare, the better the presentation will be. One possible way of arranging this is to have your students give their presentations at the end of the semester. There is, however, another way. You can have students’ presentations scattered throughout the semester at the appropriate times. For example, when Chapter 4 is done, you might have a student lecture on the different ways of interpreting quantum theory (Presentation E.4.1). Before starting Shor’s algorithm, a student might make a presentation on RSA (Presentation E.6.4) or classical factoring algorithms (Presentation E.6.3). This will explain the importance of Shor’s algorithm and place it in its historical context. Having the presentations throughout the semester demands a lot of flexibility and juggling from the teacher and the students (they have to present them at the time you prefer) but it can be done.
We have found that some students get lost in the morass of literature on a subject (regrettably, in this Web-centered world, to many students “doing research” means going to Google’s home page). We suggest that a few weeks after the students choose their topics, a private meeting be held with each one during which they present the articles they plan to use. At that meeting, they can also be told how much depth is expected from their presentation.
Note on the presentations: For each topic discussed, we
give a short explanation of what the topic is and how it is related to quantum computing (when it is not obvious);
give a short list of possible subtopics to include in your presentation; and
recommend some starting places to look for information about the topic.
Our list is arranged to follow the chapters of the text. However, there are many items that could have easily fit in other places as well. It is important to realize that our list is in no way comprehensive. There are many other areas that we could have mentioned but did not. Feel free to find your own topic of choice.
E.1 COMPLEX NUMBERS
E.1.1 The History of Complex Numbers
We use complex numbers to help us describe parts of quantum theory. However, complex numbers have a long and distinguished history (they go back to the sixteenth century). At first they began as a mathematical curiosity, but as time went on, researchers progressively realized that complex numbers are ubiquitous and important.
Make sure your presentation contains the basic facts about some of the main players in this field and what their contribution was.
A good place to start is any of the many history of mathematics textbooks available, such as Eves (1976). Might we also suggest Mazur (2002) and Nahin (1998).
E.1.2 Geometry of the Complex Plane
In Section 1.3, we briefly introduced some basic complex functions, such as the exponential and polynomials. Maps from the complex plane to itself have a geometry: for instance, the map 
, where c0 is a constant complex number, represents a translation of the plane.
In this presentation you should describe in detail (with examples!) the geometry of simple complex maps, such as the square function, exponential, and inverse. Some of this can be presented nicely with a computer graphics presentation.
Any basic textbook in complex analysis will do, but perhaps the classic Geometry of Complex Numbers (Schwerdtfeger, 1980) is the best entry point.
E.1.3 The Riemannian Sphere and Möbius Transformations
The complex plane can be turned into a sphere! Indeed, by adding a point at infinity, we can identify the plane with the so-called Riemann sphere. This is a representation that is both pervasive and extremely fruitful in thinking of the complex domain. The Riemann sphere model is not static: some special complex maps turn into rotations of the sphere. We have briefly met such maps at the end of Chapter 1: the Möbius transformations.
In your presentation you should explicitly describe the charting map from the extended complex plane to the sphere in details, and then proceed to illustrate the basic rotations of the sphere (use examples!).
The same references of the previous item apply here (in fact, Presentations E.1.2 and E.1.3 could be done in sequence).
E.2 COMPLEX VECTOR SPACES
E.2.1 Matrices in Computer Graphics
Many of the ideas from linear algebra that we needed for quantum computing are also used for computer graphics. States of a graphical system are represented by vectors and two- and three-dimensional transformations are represented by matrices.
Assuming the linear algebra presented in Chapter 2, one can proceed with a nice presentation describing the way researchers who deal with computer graphics work with these ideas. A nice computer presentation is always pleasant.
A good place to start is any comprehensive computer graphics textbook.
E.2.2 History of Vector Spaces
Although the ideas of vector spaces in particular and linear algebra in general seem simple now, their development was a long and torturous path. The ideas of higher-dimensional vectors were greeted with skepticism and ridicule. Eventually the mathematics and physics communities saw the importance of these ideas and embraced them completely.
A nice presentation should include a mini biography of some of the main players and what they accomplished. A talk should include the work of Sir William Rowan Hamilton, Hermann Grassmann, Josia Gibbs, and several others.
A good place to start is one of the many history of mathematics textbooks available, such as Eves (1976). There is a also a fascinating history of this subject by Michael J. Crowe (1994), which is definitely worth the read.
E.3 THE LEAP FROM CLASSICAL TO QUANTUM
E.3.1 Huygens’ Principle and Wave Mechanics
The concept of interference has a long history. In 1678 the Dutch physicist Christiaan Huygens presented the wave theory of light, a model that dominated optics up to the discovery of quanta. In his revolutionary treatise, Huygens described the way a wave front propagates – the so-called Huygens’ principle. In the early 1900s the English physicist Thomas Young introduced the double-slit experiment, which we have encountered in Chapter 3. This seminal experiment validated the wave model of light.
In this presentation you should clearly articulate the evolution of wave mechanics from Huygens to Schrödinger, and illustrate with diagrams how it explains known optical phenomena such as refraction and interference.
References? Plenty. Any good physics text will do. But, if we have to recommend a single book, perhaps Wave Phenomena by D.H. Towne is the one (Towne, 1989).
E.3.2 Quantum Erasers
With the understanding of the double-slit experiment, one can move on to one of the most fascinating experiments at the cutting edge of research. In the double-slit experiment, the photon passes through both slits simultaneously. Now consider a way of “tagging” the photon so that we would know which slit the photon went through. Such a “tagging” would eliminate the interference phenomenon. Now consider what would happen if we had some type of way to “erase” or remove the “tag” once the photon passed the slits. In that case, the photon would have the interference phenomenon. The amazing part is that whether or not a photon will go into both slits will depend on whether the “eraser” is present after it passes through the slit(s).
A presentation should explain the types of tags and erasers used. Some nice diagrams are a good idea. There are also many variations and improvements to this experiment that should be discussed. This is also related to the Elitzur–Vaidman bomb-tester experiment.
There are many articles in popular science magazines. They can point to more technical articles.
E.4 BASIC QUANTUM THEORY
E.4.1 Interpreting Quantum Theory
There are many different schools of thought of how one should interpret some of the less classical aspects of quantum theory. Some examples of the more popular schools are Bohr’s Copenhagen interpretation, Everett’s many worlds interpretation, and Bohm’s wave function interpretation (to name a few). Many questions in the foundations of quantum theory come down to asking what really exists and what doesn’t, the so-called ontological issues. Other issues are the measurement problem and how should one interpret nonlocality.
A presentation should include several of these different schools and how they deal with a few of the foundational issues of quantum mechanics.
There are many popular books on the topic, e.g., Herbert (1987) or Pagels (1982). There are also a few great articles on the Web at the Stanford Encyclopedia of Philosophy. These articles should lead you to more detailed articles. Any of the books by Roger Penrose (1994, 1999, 2005) would be worth looking into.
E.4.2 The EPR Paradox
In 1935, Albert Einstein and two younger colleagues wrote a paper entitled “Can quantum-mechanical description of physical reality be considered complete?” Einstein, Podolsky, and Rosen (1935). In this short paper, the authors give a simple thought experiment in which they attempt to prove that quantum mechanics as we have it is incomplete. They do this by considering two particles “entangled” and going off in two directions. By measuring one particle, one can determine facts about the other particle without disturbing it.
A presentation should include the historical context of the thought experiment (Schrödinger’s observation about entanglement); conservation of momentum; Bohm’s version of the thought experiment (conservation of spin); how EPR relates to the tensor product of two Hilbert spaces; a discussion of hidden variables; and possible solutions to the paradox.
A nice place to start looking into this is a paper on Stanford Encyclopedia of Philosophy by Arthur Fine that is very readable. See also Pagels (1982). The original EPR paper is not too difficult.
E.4.3 Bell’s Theorem
In 1964, John Bell wrote a paper (Bell, 1964, reprinted in Bell, 1987) that took the EPR paradox one step further. Bell shows that by doing some statistical analysis on measurement of two entangled particles, one can show that quantum mechanics is fundamentally nonlocal.
A presentation should include the explanation of the terms local, nonlocal; what is the inequality; some variations of the inequality; Clause and Aspects experiments; and variations of the experiments.
There is a short discussion of Bell’s theorem in Section 9.4. There is much popular literature on this topic. Alas, much of it is silly and resorts to cheap “mysticism.” For two nice presentations, see Pagels (1982) and Gribbin (1984). That should get you started.
E.4.4 Kochen–Specker Theorem
This is one of the most powerful and shocking theorems in the foundations of quantum theory. Quantum mechanics says that before a measurement, a property is in a superposition of basic states. Only after a measurement is there a collapse to a basic state. One might be tempted to say that a property is really in an unknown basic state before a measurement and the observer finds what basic state it was in after measurement. The Kochen–Specker theorem shows that it is impossible for this to be true. Before a measurement, the spin of a particle is in a superposition until it is measured.
Begin by explaining why the theorem is important. The theorem is proven by looking at a graph-coloring problem. A formal proof of this statement would be too complicated. However, giving nice geometrical intuitive pictures would be helpful. Show that it is possible to color the graph in two dimensions and then show how “there is not enough room” in three dimensions. Kernaghan’s proof (Kernaghan, 1994) with 20 vectors is fairly easy to present.
Unfortunately, there is a dearth of easy literature on this important theorem. A good place to start looking is a nice article by Carsten Held in the Stanford Encyclopedia of Philosophy.
E.4.5 Schrödinger’s Cat
This is a thought experiment that shows that the quantum weirdness of the microworld can cross over into the macroworld. By looking at a fairly mischievous contraption where a cat is placed in a box with a radioactive particle that is in a superposition of being “half-way” alive and “half-way” dead, the cat is placed in a superposition of being “half-way” alive and dead.
A presentation should include the basic construction; some history of the thought experiment; some variations of the ideas; a discussion of “Wigner’s Friend”; and some possible answers to this puzzle. Do not harm any animals while making your presentation!
There are many popular articles and books that one can start looking into, e.g., Herbert (1987) and Gribbin (1984).
E.5 ARCHITECTURE
E.5.1 Maxwell’s Demon, Landauer’s Principle, and the Physics of Information
These are several ideas at the crossroads of information theory and statistical mechanics. Maxwell’s demon is a seeming paradox that shows that one can create energy with information. Landauer’s principle concerns itself with the relationship of energy and erasing information. Both of these ideas are the starting point to a field that is called the physics of information. The basic theme of this field is studying information from the physical point of view and studying physics from the informational point of view. One of their oft-quoted mottos is “It from bit,” i.e., the physical world is created from information. David Deutsch has taken this idea a little further and written a paper (available on the Web) titled “It from qubit.”
A presentation can be historical. Go through the major players in this story and the advances they made.
There are several papers by Charles H. Bennett and Rolf Landauer freely available on the Web, e.g., Bennett (1988) and Landauer (1991). David Deutsch’s “It from qubit” is available. There is also an excellent book titled Grammatical Man: Information, Entropy, Language and Life by Jeremy Campbell (1982). It is a popular history of information theory. Definitely worth reading!
E.5.2 Classical Reversible Computation
With the ideas about energy use and losing information, several researchers went on to develop machines that are reversible and theoretically do not use energy.
A presentation can show some basic circuits; some reversible algorithms; and a discussion of the actual physical implementations of reversible computations and some of the problems they had.
There are many popular articles that are good places to start. See also Bennett’s history of reversible computation (Bennett, 1988).
E.5.3 More Quantum Gates and Universal Quantum Gates
In the text we talked about several different quantum gates (Toffoli, controlled-NOT, Pauli, etc.). There are, however, many others.
A well-rounded presentation should include a list of new quantum gates, as well as their actions. For one-qubit gates, the geometry of their action on the Bloch sphere should be articulated (a large children’s ball and a magic marker is a must for this presentation!).
There are also many other results concerning which sets of gates form universal sets. Here, you should identify one or two universal sets and explicitly show how familiar gates can be obtained from them. For instance, how can you get a pair of qubits maximally entangled from your chosen universal set?
The best place to begin is Nielsen and Chuang (2000).
E.6 ALGORITHMS
E.6.1 Probabilistic Algorithms
Some of the algorithms given in our text have a probabilistic flavor to them. Many students might be unfamiliar with this programming paradigm. It turns out that for certain problems if one does some clever guessing, there are ways of solving algorithmic problems.
A presentation should contain a few different algorithms; what they solve; what is a classic deterministic algorithm to solve the same problem; a comparison of complexity issues. A few computer simulations are easy.
A nice place to start looking for such algorithms are in Chapter 5 of Corman et al. (2001). There is also a more theoretical discussion in Chapter 10 of Sipser (2005).
E.6.2 Hidden Subgroup Problem
All the algorithms presented in this text, besides Grover’s algorithm, can be stated as examples of a single computational problem. Some familiarity with basic group theory is necessary for the statement of this problem.
Definition E.6.1 (The Hidden Subgroup Problem). Given a group G and a set function f : G → S such that we are assured that there exists a subgroup 
such that f factors through the quotient G/H, i.e.,
or in other words, that f is constant on different cosets of G, the goal is to find H.
Notice that this is a computational problem and not really a mathematical problem. Mathematically, H is simply f −1( f (e)).
A presentation should include a statement and an explanation of the problem; how each of the algorithms in Chapter 6 (besides Grover’s) can be seen as an instance of the problem; methods used to solve the general problem.
A good place to begin is Nielsen and Chuang (2000) and Hirvensalo (2001).
E.6.3 Classical Factoring Algorithms
Shor’s algorithm is the first algorithm that can factor numbers in polynomial time. However, there are classical algorithms that factor large numbers. One of the algorithms is Pollard’s rho heuristic. There are several others.
The presentation should have a nice statement of the problem; some discussion of the mathematical preliminaries necessary to understand the algorithm; the algorithms themselves; and the expected running time of the algorithm. One should also discuss how large are the numbers that can successfully be factored by such an algorithm. A computer implementation would be nice.
A nice place to start looking for material is Section 31.9 of Corman et al. (2001).
E.6.4 Fourier Transforms
In the text, we mentioned the Fourier transform with its use in Shor’s algorithm. There are, however, many other uses for the Fourier transform in computer science. They are used for multiplying numbers more efficiently; they are used to find patterns; and many other tasks.
A presentation should go through different versions of the Fourier transform such as the discrete Fourier transform, the fast Fourier transform, the quantum Fourier transform. A discussion of complexity issues is also important. Mention algorithms that use Fourier transforms. A computer simulation of one or more algorithms is not hard.
A few good places to start looking are Chapter 7 of Baase (1988), Chapter 30 of Corman et al. (2001), or Chapter 2 of Dasgupta, Papadimitriou, and Vazirani (2006).
E.7 PROGRAMMING LANGUAGES
E.7.1 SQRAM: A Full-Fledged Quantum Assembler
As we wrote in Chapter 7, our q-assembler is just a toy language to introduce the basic concepts of q-programming. There is, however, at least one attempt to describe a concrete full-fledged quantum assembler that would run on a special type of QRAM, the so-called sequential QRAM, or SQRAM.
After carefully reading Nagarajan, Papanikolaou, and Williams (2005), you should present the SQRAM model in detail, as well as the language it supports. Perhaps you could write a few simple programs for illustration purposes, and describe how the SQRAM machine executes them.
Can you think of additional desirable features?
E.7.2 QCL and Q: A Comparison
The languages by Ömer and Bettelli are two successful attempts to design an imperative quantum language. They share a number of similarities, but also some difference in the basic design philosophy.
Your presentations should clearly describe the basic features of the two proposals, and make explicit their intent.
The main references are Ömer (2000) and Bettelli, Calarco, and Serafini (2001). In an interview in Rüdiger (2007), Ömer and Bettelli have presented their views on designing a quantum programming language.
E.7.3 Functional Quantum Programming: QML
As we mentioned in passing in Section 7.3, quite recently there was a new proposal of a quantum functional language, known as QML, which attempts to provide quantum control constructs. Try to present its syntax and discuss its quantum control features, particularly the “quantum if.” Do these constructs qualify for quantum control?
This presentation should be undertaken by students who have had some previous exposure to functional programming, and possibly to Haskell.
There is an entire Web site dedicated to this language, where you can find all necessary references (and more): http://sneezy.cs.nott.ac.uk/QML.
E.8 THEORETICAL COMPUTER SCIENCE
E.8.1 Primality Testing
Primality testing is concerned with telling if a given positive integer is a prime number or a composite number. With the knowledge of all the complexity classes mentioned in Sections 8.1 and 8.2, it is interesting to look at one problem and see how, over the past several decades, progress has been made in solving this problem. Although this problem is related to the factoring problem, it should not be confused with it. Obviously if a number is prime, there will not be any nontrivial factors. However, primality testing is a decision problem and factoring is a search problem.
A presentation should include some early results of primality testing, i.e., that it is in coNP (obvious) and NP (Pratt certificates) and then at least state some of the algorithms that show the problem is in the probabilistic polynomial time complexity classes. A presentation should conclude with the recent result that PRIMES is, in fact, in P.
Some early results are shown in Corman et al. (2001). There is a nice discussion of probabilistic complexity classes and primality testing in Papadimitriou (1994) and Sipser (2005). The result that PRIMES is in P is in Agrawal, Kayal, and Saxena (2004).
E.8.2 Quantum Finite Automata
One of the simplest types of computing machines is finite automaton. These are simple (virtual) devices that can recognize regular languages. Just as there is a generalization of a classical Turing machine to a quantum Turing machine, so too, there is a generalization of the notion of a classical finite automaton to a quantum finite automaton (QFA).
A presentation should include a clear definition of a QFA; a discussion of the different types of QFAs; what type of languages they recognize; their relationships with quantum Turing machines, quantum pushdown automata, and classical two-way finite automata.
Information for such a presentation will be mostly found in research articles easily found on xxx.lanl.gov.
E.8.3 QUANTUM ORACLE COMPUTATIONS
One of the more advanced topics in theoretical computer science is oracle computation; that is, the study of one type of computation “relative to” another. The extra knowledge given by an oracle changes the basic facts about complexity classes. For a given complexity class C and an oracle A, one constructs the complexity class CA. If A is a general member of a complexity class A, then we can discuss the complexity class CA. These new complexity classes are helpful in discussing the relative strength of complexity classes.
A presentation should start with some classical results of oracle computation. For example, there exists sets A and B such that
and move on to define what does it mean for a quantum Turing machine to have an oracle. Move on to list and perhaps prove some of the results. Explain what a random oracle is and why they are important.
A good place to start is the survey papers Cleve (1999); Fortnow (2003); Vazirani (2002).
E.9 CRYPTOGRAPHY
E.9.1 RSA
One of the earliest public key cryptographic protocols is RSA. This protocol is used throughout the World Wide Web and is the current standard on public key cryptographic systems. RSA uses the fact that multiplication is computationally “easy” and factoring is computationally “hard.”
The presentation should include a statement what the RSA protocol does; the mathematical preliminaries necessary to understand the protocol; how the protocol works; how the protocol would be destroyed if an efficient polynomial algorithm for factoring was found; and the present way it is implemented. A computer simulation is both easy and nice.
Many algorithms textbooks and discrete mathematics textbooks have chapters on the RSA protocol.
E.9.2 Quantum Authentication
How can one be sure that the message just received was indeed sent by the one who claims it? As it turns out, quantum cryptography can help. Again, just like in other areas, the magic of entanglement plays a major role.
An interesting paper by D. Richard Kuhn of NIST (Kuhn, 2003) can be used, both as a baseline and for the good references to related work.
E.10 INFORMATION THEORY
E.10.1 Quantum Games
Quantum games is a new area of research that straddles between game theory and quantum computing. It was started by David Meyer in 1999 as a coin flip game between Captain Picard of Enterprise Starship and Q, his “quantum opponent.” The catch is that a qubit is used as the quantum coin. Whereas Captain Picard is allowed only to apply classical flips, Q has a full range of quantum strategies at his disposal. Q always wins.
For the hands-on reader, this presentation could also be an opportunity to write a piece of quantum code. How about implementing a simulator of Meyer’s game?
You can begin by reading the enjoyable Physics World online article: Lee and Johnson (2002). At the end, you will find a number of references to get further along.
E.10.2 Quantum Entropy of Composite Systems
In Chapter 10, we have seen how quantum entropy measures the amount of order of a given quantum system. Suppose now you are looking at a composite quantum system S. There is a way to define the entropies of the subsystems if the entropy of S is known. They are called residual entropies. The interesting thing is that, unlike the classical case, the entropy of S can be smaller than the sum of the entropies of its parts. This is because of entanglement, a new form of order of the quantum world.
Your presentation should clearly articulate the notion of residual entropy and show an example of the above.
A good reference is the “Notes on quantum information theory” by Sam Lomonaco (1996). (Caveat: The level of math sophistication is a bit higher than the one of Chapter 10. This is a good presentation for a math-oriented class).
E.10.3 Quantum Error-Correcting Codes
The last section of Chapter 10 was just meant to whet your appetite. There is much more on the topic of quantum error-correction and error-detection, and thus a nice opportunity for a great presentation.
Start with the survey paper by Knill et al. (2002). Although the tone of the paper is rather informal, it is packed with good stuff. A suggestion would be to review the first three sections, and go on to Section 6, where techniques for constructing codes are presented, in particular stabilizer codes.
E.11 HARDWARE
E.11.1 Decoherence and the Emergence of the Classical World
In the first section we have introduced decoherence as a formidable opponent in our quest for quantum hardware. Decoherence is part of life, and it also has a bright side: it is perhaps the key to the emergence of the macroscopic physical world.
For this presentation, you can present the excellent survey paper (Zurek, 2003). A Google search with key words decoherence + classical world will provide other useful references (in particular, an excellent site is www.decoherence.info).
E.11.2 A Comparison of Extant Approaches to Quantum Hardware
In Chapter 11, we have briefly showcased a few approaches for quantum hardware. If this topic captivates you, it is worth preparing a presentation comparing all the known proposals to date. As we mentioned at the end of Section 11.3, NIST has a major ongoing effort toward implementing quantum devices, and it has made available a Quantum Roadmap (http://qist.lanl.gov/qcomp_map.shtml), divided into several sections, each dedicated to a specific proposal. As our introduction of nuclear magnetic resonance was sketchy at best, perhaps it could be your starting point (you should highlight its strengths and weaknesses).
E.11.3 Current Implementations of Quantum Cryptography
In Chapter 9 we familiarized ourselves with a few quantum cryptography protocols. But, where are we in real life? As it turns out, a number of experiments have been carried out. In fact, currently there are a few commercially available quantum cryptographic communicating devices.
In this presentation, you should showcase a few milestones and the roadmap for the future of quantum cryptography.
Where to start? A good entry point is the Quantum Cryptography Roadmap, available at the Los Alamos Laboratories’, Web site: http://qist.lanl.gov/qcryptmap.shtml. It is subdivided in several sections, each addressing a core method of QKD.