Wednesday, June 29, 2022

Icons for Quantum Network Nodes

 The set of icons we created for quantum network nodes, for use in network diagrams, simulators, etc., are available Creative Commons license. Use and share! Communication will be simpler if we all use the same icons. It will be easier for others to quickly grasp what we mean when we show them a diagram.

PNGs with either white or transparent background are available at

Tuesday, June 21, 2022

For My Nephew

 My nephew just finished his frosh year in college, and wants to study...astrophysics?  Not entirely sure yet, but the college where he is has only a basic physics degree anyway. He seems a little lost on what to study, so this posting is a personal one, for him, but feel free to read on if you're in the same situation.

Okay kiddo,

It sounds like you have done the basics of mechanics and geometric optics, but I'm not actually sure what else in physics. I know you haven't done Maxwell's equations and quantum mechanics, but what about special relativity and introductory thermodynamics (statistical physics)? And in math, I know you've done "calculus", by which I gather you mean functions, limits, and integration and differentiation of a single variable. Good start, but we've got a long ways to go.

Despite our conversations, it seems like you don't have a clear picture yet of the curriculum, or even the broad structure of knowledge, in math and physics.  (And since I'm a computer engineer, all of this is from that perspective, of course.) So the first thing to do is to get oriented on what you really need.

Here are a few things to help you understand the structure of the body of knowledge, which should help you figure out what classes to take (or what to study on your own).


For a basic physics degree, you are going to need the following math:
  • Linear Algebra. Multiplying vectors and matrices, solving systems of equations via Gaussian elimination, linear and affine transformations, and eigenvalues and eigenvectors, at least. You'll also be exponentiating matrices ($e^A$, where $A$ is a matrix) in quantum mechanics, and that's easiest if you can diagonalize a matrix. You can start with my linear algebra videos, but there are lots of resources on the web. I recommend the Georgia Tech Interactive Linear Algebra online, interactive textbook. That's pretty deep, you won't need it all right away, but it's there for a reason. There is also an entire 20-hour lecture course posted as two videos in YouTube, by Prof. Jim Hefferon; I haven't watched it, so I don't know how good it is, but the comments and likes are very positive. Khan Academy has an LA course. 3 Blue 1 Brown is one of the best things on the web, and they have Essence of Linear Algebra available (full course here). In short, there are many excellent, free resources available.
  • Probability, both discrete and continuous. Probability distributions, conditional probability, Bayes' Theorem, moments of distributions. For continuous, you'll need integration, so continuous comes after basic calculus.
  • Statistics. I think most physics majors get away with just what they learn in a probability class unless they specialize in statistical mechanics and thermodynamics.
  • Ordinary differential equations (ODEs). You said you've seen that $f'(x) = f(x)$ is solved only by the function $f(x) = e^x$, so you've seen the start of a very deep field.
  • Partial differential equations (PDEs). Next step: derivatives in multiple dimensions. These are equations involving symbols like $\frac{\partial x}{\partial t}$. I first hit this when doing Maxwell's equations; I think it's pretty common for that to happen, but it means you're dealing with both a new math tool and important ideas in physics at the same time, so studying basics of PDEs first is a good idea.
  • Transforms and signal processing are a big deal; you might run into Fourier, Laplace, Z and other transforms. (This is different from the linear and affine transforms above.) Often, these are tools for solving ODEs or PDEs, and might show up in an Applied Math class in your college.
  • Later, you might get into more specialized topics like number theory, group theory, and graph theory. Group theory, for example, shows up in particle physics. The basics of graph theory you can learn very early, actually, and they are critical in computer science but maybe not as much in physics.
I'm sure you can find as much stuff on the later topics as I found for LA.


Surprisingly, I'm a little less comfortable talking about what basic physics you should study. Let's talk first about optics, since it's one of my favorite parts of physics, demonstrates broadly useful concepts, and happens to be what we are working on for our quantum communications research.

From among the courses we have created already, if you want the basic physics, and to minimize the quantum communications portions, these steps would be very good follow-on to your work on geometric optics. They are a bit idiosyncratic relative to an ordinary course on optics, naturally focusing on what we need for quantum communications, but they will still carry you a long way.
  • OQC, Lesson 5: Coherent Light and Single Photons, leading up to a quick quantitative intro to lasers.
  • OQC, Lesson 6.1-6.2: Interference, group and phase velocity quick introduction to constructive and destructive interference and the notions of group and phase velocity, a distinction that is crucial to understand.
  • OQC, Lesson 7: Waveguides discusses the most important means of guiding light, of which the most famous type is, of course, optical fibers. Total up to here is about two hours worth of video, you can do this in the time it would take you to watch one soccer match.
  • And then most of our entire module From Classical to Quantum Light, which is about 10 hours of material covering wave equations, Fourier analysis, Maxwell's equations governing how electromagnetic waves work both in a vacuum and in materials, and then into more on single photons and the like, including how detectors work. You might want to taper off when you get to the single photon stuff and defer that for after you have had basic quantum mechanics, so let's say you should do the first ten lessons of that, 45 minutes each, so about 7.5 hours.
  • Among the remaining important topics to learn about are how holograms work, more on polarization, and a lot about antenna design. A good optics course will cover these things.
From the above video on the map of physics, you should have some idea of the basic list of topics:
  • mechanics
  • waves
  • optics
  • special relativity
  • electricity & magnetism
  • introductory quantum mechanics
  • thermodynamics
That much you should take as an engineering or physics student of any sort. If you major in physics, you'll add advanced QM, particle physics, general relativity and some other topics to that list.

Given your interest in soccer, you might consider studying biomechanics, which is a bit of a specialized area and interdisciplinary, so a little biology will help, too. You should check out Professor Ohgi's Sports Dynamics and Informatics Lab as a possible destination for grad school. He works with people up to the level of Olympic athletes to understand the forces and dynamics of athletic performance. Studying some computer science before joining his lab would also be helpful.

Enough for now. Go watch those introductory things to get oriented, then study some linear algebra and probability while you watch our online courses on optics and quantum computing and communications.

Sunday, June 12, 2022

Spelunking CACM, vol. 9 (1966): Eliza (and now 2022's LaMDA)

 Eliza has arrived. Eliza, who is a few months older than I am, is inarguably one of the seminal events in computing history. It's just about the only program created in the 1960s that most of us can still spontaneously name. It helped to spur my own interest in computing.

My first computer was a Radio Shack TRS-80 Model I. I also got a book with programs in it, which meant copying the programs in by hand. (Good training for catching syntax errors!)  One of those programs was called Eliza, though I suspect the BASIC version in my book was pretty different, and probably much simpler, than the 1966 version created by Joseph Weizenbaum in SLIP, a language adding list processing features to FORTRAN.

Eliza works by parsing input text into tokens and finding an important phrase (where phrases are delimited by commas or periods) based on the key word in the phrase, using a list of important words that was created by hand. Then it replaces the primary verb or subject in the phrase with one of a set of stock phrases. If you type in "I love my dog," Eliza might respond, "Tell me why you love your dog." Does mean it has any idea at all what a dog is, it just found a simple pattern and followed it.

My TRS-80 was at home, but the high school also had one, and friends of mine also enjoyed playing with Eliza. And what do high school boys want to talk about? Sex and scatalogical things and bad language, of course. You could make Eliza say some pretty hilarious things that way, by the standards of high school boys.

And now, 56 years later, we have a Google engineer and AI ethicist arguing that an intellectual descendant of Eliza has become sentient.

Chat bots have evolved tremendously since then, and are generally connected to a backend system of some sort, so that they can provide airline assistance or what have you. Often, they are connected to a neural net-based AI both for parsing the language and creating the responses. Generally speaking, no one believes they are actually sentient, but the responses will sometimes appear so insightful that your hair stands up on the back of your neck.

My skeptic's nature and my own very limited experience with chat bots cause me to lean toward siding with the Googlers who said there is no evidence that it's sentient, and plenty of evidence against it. But we are now clearly entering the realm where it will get harder and harder to tell, and the stakes of the arguments will continue to grow. Research into AI ethics grows more crucial every day.

Monday, June 06, 2022

Spelunking CACM, vol. 8 (1965): debugging, peephole optimization, and an undergraduate curriculum

(Click on the image if it isn't large enough to read.)

Overall, 1965 seemed like an "ordinary" year at CACM. I didn't see any papers that really caught my eye as some sort of extraordinary event. (Stay tuned for 1966 for that.) But there are a few things of interest, of course.

By 1965, the idea of wide-area networks was definitely in the air. Paul Baran was publishing RAND reports on the key ideas of packet switching (although I'm not sure when those became publicly available), and the ARPANET project would kick off in 1966. But connections between computers were still much more an idea than a reality, and so I.R. Neilsen had a CACM paper on a 5kHz modem for "callup" connections for exchanging medical data.

Evans and Darley presented DEBUG, which worked with other tools to allow smooth insertion of new lines of assembly while debugging a program, preventing what we now call "spaghetti code". DDT already existed for the PDP-1 at this point. I find this early history of debugging intriguing, since I have a Ph.D. student working on debugging for quantum programs now.

Maybe the most interesting trend is a pair of papers (is two enough for a trend?) on optimizing compilers. In June, Nievergelt presented "On the Automatic Simplification of Computer Programs", which proposed a set of backend techniques for individual optimizations to a stream of instructions. The paper enumerates limitations on the use of the proposed techniques, which interesting included the constraint that programs not be self-modifying, evidence that that idea was already in use.

Then in July, McKeeman gave us "Peephole Optimization". He implies that the technique is known but known and "simple" but "often neglected", and also that he is coining the term "peephole optimization" in this paper. Again implemented for the PDP-1, the explanation is clear but limited, being just over a page.

But maybe the most interesting thing as an artifact is the report from the ACM Curriculum Committee on Computer Science titled "An Undergraduate Program in Computer Science-- Preliminary Recommendations". Some earlier papers on education appeared in prior years, but I think this is the first actual organized recommendation from ACM itself. Here was the status at the time:

At the time of this writing, in the United States, doctorates can be sought at more than 15 universities, master's degrees at more than 30, baccalaureates in at least 17 colleges, and a sizeable number of other colleges and universities are presently planning or considering departments of computer science.

Impressive. I didn't know there were that many before I was born.

At the top of this post is the key table. Each of the sixteen courses there has a several-paragraph description that is well worth reading. I'm particularly intrigued that Graph Theory was already recognized as an important element in the curriculum. I am working to introduce a Graph Theory class for undergrads at our campus, for many purposes including economics, social sciences, etc., not just CS.

Each course in that table is assumed to be a U.S. 3-semester-hour course consisting of 3 hours/week x 15 weeks = 45 hours of in-class time and probably 2x that in lab or homework time for a total of, oh, 130-140 hours of work and learning. If you take just the nine "Required" plus "Highly Recommended Electives" courses, you're well over a thousand hours of time invested.  Add the seven "Other Electives", and a university that provided them all (noted in the text to be a difficult task), and you have about 2,100 hours of time. And that's not even counting the "Supporting" courses, let alone any arts and social sciences classes required. In short, this is a pretty thorough and ambitious major!

Saturday, June 04, 2022






Tuesday, May 31, 2022

Peak Digital

 Random topic for your end-of-year brain break: I predict that we are at #PeakDigital, within a decade or so. Beyond that, we will have the #SecondQuantumRevolution and the #AnalogRenaissance. The idea of (classical) binary-only data processing will come to seem...quaint.

We will learn to create, process, store, transmit and correct analog data in myriad forms. Same with digital and continuous-variable quantum. All at fidelity and reliability that far exceed vinyl records, film, wax cylinders, differential analyzers and tide calculation machines, allowing essentially infinite rounds of processing and transmission with no detectable degradation.

It will be far faster and more efficient than digital computation, and after some teething pains will come to be seen as flexible and reliable.

People will talk of a quartet of information paradigms -- classical and quantum; digital/discrete and analog/continuous.

Information theory and computational complexity will merge completely.

And the kicker? P ?= NP turns out to be irrelevant, as complexity turns out to be a continuum instead of discrete classes, a topography of hills and valleys, and whether you roll downhill toward polynomial or exponential is a microscopic different on a ridge.

Now, do you think I actually believe this will work out exactly this way? I'll hedge my bets and keep my cards face down. But this might provoke some conversation. What do *YOU* think information will look like in, say, 2075?

Saturday, May 28, 2022

From Classical to Quantum Optics Course on YouTube

The Japanese government is funding a group of us, led by Prof. Kae Nemoto (now at Okinawa Institute of Science and Technology), to create an undergraduate quantum computing (engineering?) curriculum. We are calling it Quantum Academy. As of this writing, getting the full experience requires registering for a class at one of the participating institution, but we are making our share of the work available as Creative Commons, CC-BY-SA. Each module is intended to be 1 unit that will satisfy MEXT, about ten to twelve hours of face time with faculty, plus reading & homework. (Most Japanese university courses are two units, a total of 40-50 hours of work, about half the size of a U.S. course.)

Our contribution this year is the module From Classical to Quantum Optics. Actually, technically, that link will take you to our YouTube channel's playlists, which includes not only that module but also last year's Overview of Quantum Communications. Moreover, there are both English and 日本語 versions available! Michal Hajdušek created the materials and the English videos, while I did the Japanese videos.

My apologies, but we are still working on subtitles, especially for Japanese. If anyone would like to do subtitles in another language, please let us know, we are very interested!

Eventually, edited transcripts will be available in book form, as well. Patience, please!

The module begins with the classical wave equation, Fourier analysis, and Maxwell's Laws, then gets into single photons. It follows on nicely from Overview of Quantum Communications, where we talked mostly about qubits as abstract things, but also covered the critical technology of waveguides such as optical fibers, without fully justifying why light can be guided that way. Here, Maxwell's equations and the wave equation shore up that foundation. Here's the outline:

From Classical to Quantum Light

Prerequisites: Overview of Quantum Communications, Linear Algebra, Probability

Prerequisites/co-requisites: Differential Equations, Introductory Partial Differential Equations, Introductory Quantum Mechanics, Classical Optics

Recommended next courses: Quantum Internet (coming in 2023)

An Early, Relatively Complete Quantum Computer Design

 Based on a Twitter thread by yours truly, about research with Thaddeus Ladd and Austin Fowler back in 2009.

In the context of an ongoing #QuantumArchitecture #QuantumComputing project, today we reviewed some of my old work. I believe that in 2009 this was the most complete architectural study in the world.

We started with a technology (optically controlled quantum dots in silicon nanophotonics), an error correction scheme (the then-new surface code) and a workload/goal (factoring a 2048-bit number).

We considered everything.

Optimized implementation of Peter Shor's algorithm (at least the arithmetic, the expensive part). (More recent work by Archimedes Pavlidis and by Craig Gidney goes beyond where we were in 2009.)

How many logical qubits do we need? 6n = 12K.

How many logical Toffoli gates? A LOT.

So how low a residual logical gate error can we allow?

Given that, and a proposed physical gate error rate, how much distillation do we need? How much should we allow for "wiring", channels to move the logical qubits around?

We ended up with 65% of the space on the surface code lattice for distillation, 25% for wiring, and only 10% for the actual data.

From here, we estimated the code distance needed. High, but not outrageous, in our opinion. (More on that below.)

With micron-sized dots and waveguides, we had already grokked that a multi-chip system was necessary. So we already knew we were looking at at least a two-level system for the surface code lattice, with some stabilizers measured fast and others slow.

We worked through various designs, and wound up with one with several different types of connections between neighbors. See the labels on the right ("W connection", "C connection", etc.) in this figure from the paper. This is the system design.

Turns out each type has a different connection rate and a different fidelity, so we need purification on the Bell pairs created between ancillary dots, before we can use them for the CNOT gates for stabilizer measurements. This could mean that portions of the lattice run faster and portions run slower.

Oh, and an advance in this architecture that I think is under-appreciated: the microarchitecture is designed to work around nonfunctional dots and maintain a complete lattice. I have slides on that, but sadly they didn't make it into the paper, but see Sec. 2.1.

Put it all together, and it's an enormous system. How big?

Six billion qubits.

So if you have heard somewhere that it takes billions of qubits to factor a large number, this might be where it started. But that was always a number with a lot of conditions on it. You really can't just toss out a number, you have to understand the system top to bottom.

Your own system will certainly vary.

The value in this paper is in the techniques used to design and analyze the system.

You have to lay out the system in all its tedious detail, like in this table that summarizes the design.

That lattice constant in the table, btw, is one edge of a surface code hole, so the actual code distance is 4x that, or d = 56. We were aiming for just a factor of three below the surface code threshold, and for a huge computation. These days, most people will tell you hardware needs to be 10x better than threshold for QEC to be feasible. If not, you end up with numbers like these.

You can pretty much guess who did what. Austin Fowler (then in Waterloo, now at Google) did the QEC analysis. Thaddeus Ladd (then at Stanford with Yoshi Yamamoto, now at HRL) did the quantum dot analysis and simulation. I brought the arithmetic expertise and overall system view. We all worked super hard on the chip layout and how all the pieces fit together to make a system.

These things are beasts, with so many facets of the design problem, that we need all hands to make them work!

Quoted/Cited in the Press

 A couple of places that the press has quoted me or cited my research recently, on Quantum Internet stuff. (This blog posting is more for my own reference than anything else.  Feel free to ignore it.)

  • Physics World on the Hanson group's new paper, showing two-hop teleportation after entanglement swapping in NV diamond.
  • Nikkei talking about Quantum Internet and about our work,  but not directly quoting me.  (In Japanese, and behind a paywall.)