The Quantum Computing Book From the Future

I just received my copy of this book from the future. How do I know it's from the future? It's copyright 2025!

We will catch up to the book and join it in 2025 in just a few weeks, but even once we do, an important truth will remain: this book is very nearly perfect. (At least, as far as I can tell after spending only an hour with it.)

The level of explanation is Just Right. Lots of intuition and basic descriptions of equipment, supported by the right number and level of equations.

Majify, Wilson and Laflamme, Building Quantum Computers: A Practical Introduction is exactly the book I have been looking for. It covers, in up-to-date but not excessively detailed fashion, the important basic technologies of NMR, linear optical, ion trap and superconducting quantum systems. At first I wondered why NMR, which no one is really using these days, but it gives them a great pedagogical opportunity to explain nuclear spin, Larmor precession, RF control pulses and techniques for suppressing errors at the physical level, so it works.

I said it's almost perfect; there are a couple of things I wish it had or had more of. It doesn't cover quantum dots or neutral atoms, both technologies of long standing that had not shown as much progress as the others over the last decade until about the last two years, where they have shown important advances. Even for a book from the future, those advances are probably too new for the authors to have had time to create full chapters on them. Oh, and color centers such as nitrogen vacancy in diamond (NV diamond), but those are currently being used more for communication than computation. Also, since this is a textbook for a course of limited duration, I'm sure they had to make hard choices about what to include and what to defer to later study. And while the book has some nice sketches of hardware systems and a few photos, unfortunately the black and white reproductions aren't great, many of the figures don't indicate scale, and most importantly would love to have twice as many of them. But all of that is easily remedied by showing additional photos and diagrams in class.

In short, the authors have knocked this out of the park. As far as I am concerned, as long as availability is reasonable, this book is IT for explaining quantum computing hardware until it becomes unusably outdated -- something that is hopefully in the distant future, as befits a book from the future itself.

Siam Quantum Science and Technology 2024

My life isn't going to suck for the next four days at the inaugural Siam Quantum Science and Technology conference in Krabi, Thailand. I'm giving the Wednesday keynote speech on Modular Quantum Systems.

I spent a couple of days in Bangkok on my way down here, giving talks at Chulalongkorn University and Mahidol University. I'll spend one more there on my way home at the end of the week.

Can AI "Beat" Quantum Computing?

 Google DeepMind recently hosted an in-person event featuring Demis Hassibis and other Nobel laureates, and a few days ago they posted the videos on YouTube. The whole hour-long video I watched is well worth it; I haven't gotten around to watching the others yet.

Hassibis expresses some thoughtful opinions on quantum computing and the value of quantum computers relative to AI. He's a smart guy, and while he comes from a pro-AI point of view, he has been talking to the right people and learning a lot about quantum, so it's worth taking what he says seriously. From right around 10:00 to around 14:05 Hassabis says, in essence, that he thinks that all of the important real world problems have enough structure that they can be solved classically, and so the challenge is "just" to "pre-compute" a model that lets you find it, and AI will be good at that. Therefore, maybe in practice AI will outperform quantum computers at solving problems we care about.  (He doesn't claim anything that contradicts what's known about computational complexity classes; more about that below.)

It's a very interesting conception, and I have always held something much like that as a caveat in the back of my mind.

Interestingly, one of the things we have known about quantum computers for some time is that we gain at most a polynomial speedup over classical computers when there is NO structure to the problem. But that is an extremely general result.

We also know that there are problems where we can get provable exponential speedups for exact solutions, and that some problems admit only exact solutions. And so the question is, how big is that window where quantum's advantage is practical?

AI is pushing the boundaries of classical models for systems, allowing its heuristics to be very effective in real world-type problems. So will it push quantum into a tightly confined corner where it is left to play with toy problems ad esoteric problems with no value?

I sent (a somewhat rougher form of) the above to my pal Suzanne Woolf, who thoughtfully responded:

I like this idea very much, just because I hadn't thought of it but now that you've articulated it, it's embarrassingly obvious. Problem-solving of any kind is so often a matter of framing the question so it can be answered with the tools you have available (or can invent-- didn't Leibniz and Newton invent calculus at more or less the same time?)

But color me skeptical about the limits on adaptability of AI, especially LLMs. I think the problems they have-- "hallucinations," GIGO, computational intensity-- are fundamental: you can give the genius toddler all of the dictionaries, encyclopedias, collections of literary works from the Bible and Japanese mythology to Shakespeare to Agatha Christie and Martha Wells, and daily newspapers across the world for months on end-- but it's still a toddler.

I'm not necessarily going to argue that judgment requires self-awareness, and that's a hard limit, but I could probably be persuaded.

Stay tuned...

Nobel Prize in Physics to...Hopfield and Hinton for Artificial Neural Networks?!?

 You have probably heard by now, but about twelve hours ago the Nobel Prize in Physics was awarded to John J. Hopfield and Geoffrey E. Hinton “for foundational discoveries and inventions that enable machine learning with artificial neural networks”. To say that this prize is surprising is an epic understatement. It's also causing some consternation and even anger in some quarters. I don't normally feel qualified to comment on the Nobels, but in this case let me record just a few thoughts that are enhanced by conversations with and social media postings by a few friends.

Hopfield was faculty at Caltech when I was there, but was oriented more toward biology at the time, and I wasn't aware enough to take the really important and interesting classes. He taught a class on neural networks early during my time, which a few of my friends took but I didn't. In 1981-83, he, Carver Mead, and Richard Feynman taught a triple-listed Bi/CS/Ph course that was reportedly wild.  I'm sorry I missed that! (I did take Feynman's class later, in 1985-86, that was a direct descendant of that class. We learned a little about neural networks, and in fact a couple of friends and I implemented one in C, though it wasn't very good. That class changed how I view the process of computation, and indirectly led me into quantum computing several decades later.)

One of my closest friends took a class Hinton co-taught back in the early 80s at CMU. She said it was fascinating, all the way back then.

On the prize itself, at least one of my physicist friends is angry. Paraphrasing, it's not physics and why should we be celebrating things that detract from human accomplishment? I don't agree with the latter, but the former will be the basis of bar arguments for a long time to come.

My opinion? Hmm...

It's not even entirely clear to me, after watching the press conference, whether the prize is being awarded for neural networks being physics, or changing the way people do physics. The former figured prominently in the press conference, as they talked about Boltzmann machines.  Yes, Hopfield and Hinton both used ideas from their background in physics, but to me this seems to be a bit of a stretch. The committee also talked about the latter, about the use of neural nets in doing physics. In that case, why not the inventor of the supercomputer, or the laptop?  The inventors of the Intel 4004 microprocessor (Faggin, Hoff, Mazor and Shima), most often cited as the world's first microprocessor, are all still alive. The invention of extreme ultraviolet photolithography is also another good candidate.

I've heard funny takes on this prize, including that the tech bro billionaires bribed the committee.  My own is that it was ranked voting in the committee and everybody refused to budge on their first choice but somehow they all ranked AI high enough that in the end Hopfield and Hinton had the most points and everyone on the committee went, "wait, what???" But they couldn't undo the decision.

That, or they were all angry that Hopfield was left off of Hinton's 2018 Turing Award, shared with Bengio and LeCun. (Speaking of which, I said that Hinton was the first to receive both the Turing Award and a Nobel, but that's not true -- Herb Simon did it first! Interestingly, both Simon and Hinton were on the faculty at CMU.)

I do think it's okay that the committee is stretching the definition of "physics"; they have done that before, with prizes for information technology. But with only a single prize awarded each year in physics, there are many, many discoveries, and discoverers, out there waiting for the public recognition they most definitely deserve. There are other prizes for computing, of course, notably the Turing Award. So while a broad look at how physics has changed society is a good thing, but I think it would be okay to say, "Nah, they already have a prize in their main area, that should be enough."

But in the end, it's recognition of the importance of machine learning, neural networks and ultimately artificial intelligence in our lives already, a fact that will continue to grow. And if it gives Hinton (and others) more of a platform for and recognition of his (and their) reservations about where we are headed with AI, all of that's a good thing. It's a necessary conversation we need to be having, now.

Finally, the score so far for the science prizes this year:

• White men from elite institutions: 4
• Everyone else: 0

We'll see when the Chemistry prize is announced this evening if the rest of the world gets skunked again!

Strength

A friend of mine on Facebook said they think the U.S. needs a strong leader, and that Donald Trump is that person.

I disagree. Trump is not strong.

Calling your opponent "mentally retarded" is not strong.

Stoking fear and hatred of immigrants instead of asking "what brings people to our shores, and how can we help them get the same opportunities we have had?" is not strong.

Bragging about not paying overtime is not strong.

Failing to pay the arenas where you have held rallies is not strong.

Refusing to admit losing an election is not strong.

Being obsessed with and afraid of sharks is neither particularly strong nor particularly weak, but failing to recognize their importance to the ecosystem is definitely not strong.

Nuking hurricanes is not strong.

Threatening to jail your political opponents and reporters who write stories you don't like is not strong.

Speaking of reporters, mocking a talented reporter who happens to have a physical impairment is not strong.

Mocking those with different accents, dress, speech patterns, body types or other differences is not strong; very likely those people speak multiple languages, have a broader experience of the world, and still struggle every day in a culture not their childhood one -- those people, they are strong.

Allowing yourself to simply take as your own opinion the opinion of whoever talked to you last is not strong.

Torpedoing a bipartisan deal on the southern border simply to allow the situation to fester long enough to become a campaign issue is not strong.

Failing to stand up to extremists in your own party is not strong.

Giving Putin whatever he wants is not strong.

Insulting women, assaulting women and taking away their constitutional rights most definitely is not strong.

I could go on.

But finally, attempting to overthrow the U.S. government and install yourself as some sort of petty tyrant because you are not strong enough to lose with grace is weak and cowardly.

Donald Trump is the opposite of strong in every way.

Spelunking CACM, vol. 21 (1978): Cray-1, RSA, CSP, and more, more, more!

WOW, the January issue is a must-read!

 It's chock full of papers on some of the most important architectures, both contemporary and historical, in a special issue, though at a glance I don't see an introduction. (But I don't see the front matter in the Digital Library...hmmm?)

• The Manchester Mark I and Atlas. 'Nuff said. Know your history, kids. Interesting that these two bracket the transistor computer, first developed at Manchester.
• MU5: This one, I wasn't familiar with, but it's from Manchester, one of the most important places in computer architecture history. Manchester's accomplishments include building the world's first transistor computer. (Wait, didn't I just say that?)
• Sperry-UNIVAC 1100: a still-active family of 36-bit mainframes (36 bits???), the first of which were vacuum tubes, later transistorized ones with SSI and MSI (I presume). Although the names in the series followed the 11xx convention, the later ones weren't compatible with the earlier ones. Interestingly, this architecture used ones-complement integer arithmetic instead of twos-complement, so it's theoretically possible to have both +0 and -0 values. Like the DECsystem-10 below, it supported unlimited indirect addressing.
• DECsystem 10: TOPS-20 systems, the next generation of this system, were workhorses at USC/ISI when I first worked in the computer center there. This architecture has a couple of clever, elegant features: essentially a single addressing mode, where the registers are the lowest handful of addresses, and indirection, where any pointer you follow has a bit that says, "Treat this one as pointer instead of the data you're looking for, and follow it." Yes, that could recurse. The OS was innovative, too. Oh, and did I mention that this marvelous has a word length of...36 bits?!? (Didn't I just say that?)  And that a byte can one of several sizes, with 7 and 9 bits being the most common?
• The Cray-1: the most important supercomputer in history, perhaps, and a beautiful, elegant piece of work. Check out that gorgeous image at the top of this posting. Freon liquid cooling, chained 64-bit floating point vector operations working from vector registers, bipolar memory chips, dual-rail encoding to reduce fluctuation in power and signal noise, and the totally 1970s naugahyde love seat around its set-of-wedges circular design. 138 sustained megaFLOPS, what performance! Fastest machine in the world.

I'm tempted to just stop here and declare victory after January, but I suppose I should at least glance through the other issues...let's see, another report on status of women and minorities in CS faculty...

Ahem. Ah. Let's see, this might be important:

The RSA (Rivest-Shamir-Adelman) public key cryptosystem. Yeah, I'd say that's worth mentioning. Oh, and then Merkle, too. And at the end of the year Needham-Shroeder. A good year for cryptography.

Backus's Turing Award lecture. Want to think about programming languages? Read this first.

It was also an incredible year for the theory of distributed systems. Lamport on Time, clocks, and the ordering of events in distributed systems. One of the classic, classic papers in distributed systems. I still have my students read this, almost half a century later. Tony Hoare's Communicating Sequential Processes. Another of the classic, classic papers. And Per Brinch Hansen's own model for distributed programming. His affiliation is listed as USC, but I never met him; I have no idea when he left USC.

My sister's dog likes to lie on her back and just wallow.  I'm tempted to do that while reading all of these fantastic papers!

Spelunking CACM's Second Decade

 As you know, I am working my way through Communications of the ACM, beginning to end, stopping to read a handful of articles from each year. These aren't necessarily the papers with the highest citations, but instead things that catch my eye from the point of view of the 2020s.  A full two years ago I finished the first decade of CACM; now I have finished the second, so let's index them. (Hmm, I've fallen out of the habit of giving them descriptive names, I should go back to that.)

• Spelunking CACM, vol. 11 (1968): Operating Systems Bonanza and Ethics, but not the ARPAnet!
• Spelunking CACM, Vol. 12 (1969): CAD, encouraging(?) minority participation in computing, and discrete event simulation
• Spelunking CACM, Vol. 13 (1970): Nucleus, Bloom filters and magnetic tape
• Spelunking CACM, Vol. 14 (1971): Flynn's taxonomy
• Spelunking CACM, Vol. 15 (1972): Hough transforms, Dijkstra on correctness
• Spelunking CACM: Some Thoughts on Operating Systems (a "special issue" posting)
• Spelunking CACM, Vol. 16 (1973): threaded code and too many PhDs
• Spelunking CACM, Vol. 17 (1974): Clipping Polygons, Parallelism, and UNIX
• Spelunking CACM (1975): Phong Shading
• Spelunking CACM (1976): PhD production, data flow
• Spelunking CACM, Vol. 20 (1977): Certifying information flow, an early network routing protocol

Spelunking CACM, Vol. 20 (1977)

I have finally reached my twentieth article in this series! It's probably time for another summary, but first let's do the things that caught my eye in 1977. This was the year that "Star Wars" (with the simple title) came out. I was eleven. I probably wasn't yet particularly aware of computers and computing, but I was already a fan of "Star Trek" and of the space program (which was in the Apollo-Soyuz/space shuttle interlude at the time).

When I first skimmed the contents for 1977, I flagged eighteen articles for further investigation. For a systems person like me, there was a lot to catch the eye. I've winnowed it down, but if you look there are still more good papers than just these.

If you're interested in data about demographics and numbers of students in CS, there is a report following on from the previous year.  What's depressing is not how bad it was in 1976, but how bad our diversity remains today.

As long as we're on the topic of education, it was already possible in 1977 to put together a survey of 200 publications on CS ed. ACM's first curriculum committee issued its report in 1968, though, and SIGCSE was founded in 1970, so it should be no surprise. The CS GRE was also introduced recently and analyzed in CACM.

Dorothy Denning and Peter Denning give an elegant description of how to certify information flow in programs for security purposes. Consider, for example, the simple statement

If the variables y and x are in separate security classes, then there is a potentially unauthorized information flow between the classes. After the execution of this statement, the value of y will equal the value of x, whether we considered that acceptable or not. The Dennings go on to discuss a complete method for static, compile-time analysis of this information flow.

Morgan and Levin provided a mathematical means of assigning files to network nodes to optimize overall system performance. The eye-catching hypercube with cut planes at the top of this blog posting is taken from the article. They even consider multiple copies of the files in the networks, and divide traffic into "query" and "update" and consider them separately. They recognize that assigning the files to the nodes is an exponentially complex problem, and provide some heuristics for avoiding searching the entire space.

Speaking of networks, Tajibnapis developed a routing protocol for the MERIT network in Michigan. His article on TIP was originally submitted in 1974, and finally published in 1977. To me, the NETCHANGE protocol specifying the message contents for routing protocols sounds a lot like RIP, which was developed quite a bit later. However, TIP doesn't seem to have had a lot of impact; I'm not sure why. Of course, even by 1974 Dijkstra's shortest path first algorithm was fifteen years old, and there was quite a flowering of work on routing in the mid-1970s, so it's likely that there was other, similar work. MERIT would go on to be a pivotal place for networking research for decades to come.

In operating systems work, Lamport wrote about readers and writers, which I still teach about in my OS class today. Fundamental stuff, though this article is a little...rococo in its notation, I think.

Parallel computing was in its earliest phase of trendiness. While I associate a lot of theory of correctness in parallel programming to K. Mani Chandy, there is a paper here on how to prove parallel programs correct, using Susan Owicki's techniques and an implementation of Dijkstra's on-the-fly garbage collector as the example. As author David Gries says,

Building a program with little regard to correctness and then debugging it to find errors is even more folly for parallel programs than it is for sequential programs.

Word.

And finally, if you want some history to go with your history, there are Rabin's and Scott's Turing Award lectures, given for their work on nondeterministic automata some years prior.

Lynn Conway

I was in a Starbucks when I saw Dave Farber's message on his IP mailing list saying that Lynn Conway had passed away, and I said out loud, "Oh, no!" and started crying. She was a hero and an icon, and stands high in our technical pantheon.

Of course, every person has the fundamental human right to live as they are, as they understand themselves to be, and the rest of us get no say in who they are. Saying, "It's okay that Freddie Mercury was gay, he was an amazing singer and artist," fundamentally misunderstands this. The vast majority of LGBTQ+ people are perfectly ordinary people, and that is perfectly fine. Margo Selzer said, "It is not the job of the underrepresented to solve underrepresentation," and the same is true for other aspects of life as a minority. It's the job of the majority to change ourselves to be accepting; no minority should be required to step up and be a hero. So, Lynn "owed" no one her work as an activist; it was a role she chose late in life, and we should be grateful for it.

FWIW, it took IBM 52 years to get around to apologizing for firing her (falling just short of the 55 years it took the UK government to apologize for chemically castrating Alan Turing for being gay).
https://www.nytimes.com/2020/11/21/business/lynn-conway-ibm-transgender.html

As it happens, I was talking to a couple of students yesterday about citation counts for researchers in computer science and electrical engineering, and we found a website where the top researcher has half a million citations. You won't find Lynn's name on a list like that, and yet I would put her contribution far above almost everyone on such a list. She received dozens of awards, but far fewer than she deserved, IMO. There would BE no "chip industry" without her.  Pretty much everything else in our research field and our entire industry...is secondary.

Wikipedia tells me that IEEE Solid-State Circuits Magazine published a special issue on her career in 2012. I didn't know that, but it was well deserved. Her own reminiscences are worth reading -- every sentence.
https://ieeexplore.ieee.org/document/6392995
https://ai.eecs.umich.edu/people/conway/Memoirs/VLSI/Lynn_Conway_VLSI_Reminiscences.pdf

We all owe her a tremendous debt. Write her name in the history books, and then go and pay it forward. I'll tell my Computer Architecture class and my quantum computing research group about her tomorrow. I didn't know her in person, but I probably won't be able to keep my eyes dry.

[written right after hearing about her passing, posted a couple of weeks later.]

[edit: obituaries:

• New York Times
  
• Washington Post
  
• IEEE Spectrum
  
• University of Michigan
  

]

Gordon Bell

 Gordon Bell has passed away.

Gordon was one of the most important computer architects of all time. He designed, co-designed or was executive lead in charge of most of Digital Equipment Corporation's key machines in its heyday, from the initial PDP-1 to the VAX-11, in two stints working for the company. Although he wrote the seminal description of the PDP-11, perhaps the most influential minicomputer of all time, I don't think he had much to do with that design or with the PDP-10, and by the time of the Alpha he had already left DEC for good. But still, much of the company's design sensibilities grew from him.

I learned a great deal from the book he coauthored on computer engineering, using all of the DEC machines as examples. Most of the chapters were coauthored by Gordon and other members of the various technical teams. (Wow, I paid ten bucks for my copy at a DECUS in 1986, but even the Kindle version now goes for a hundred bucks?!?)

He also established the Gordon Bell Prize for accomplishments in parallel computing. One of the recent prizes was for simulation of quantum mechanics, though nothing to do with quantum computing.

RIP Gordon, thanks for the machines and for being such an important advocate of parallel computing.

Questions about QKD

 I think quantum key distribution is fascinating, but unlikely by itself to serve as reason enough to build a Quantum Internet. Keeping in mind that I am not directly a QKD researcher, in my opinion there are several major hurdles limiting adoption of QKD today:

• Range of QKD is limited (until we build a multihop, long-distance network).
• Boxes are expensive, not robust, and require a lot of operational expertise.
• Attacking QKD deployments is trivial; it's designed to detect eavesdroppers, so by its very nature acting as an eavesdropper is equivalent to launching a DoS attack.
• Interoperability, standards and global operational confidence are still works in progress.
• Market pull is still limited, because the problem it solves -- generating shared random or near-random bits secure enough to be used as encryption keys(*) -- still isn't tops on the list of pain points for Chief Security Officers, AND there is a classical solution in the offing (PQC) that requires "only" software and protocols, no new hardware.
• Latency to start up a connection is orders of magnitude too high to be useful at e.g. the HTTPS level, so it has at best a specific and limited role in systems, e.g. network-to-network IPSec tunnels.

With that in mind, I recently had a discussion with a QKD researcher about how to evaluate new ideas in the area. We came up with about thirteen questions/concerns/metrics answering the question, "What do we want to improve?":

1. Steady-state key generation rate
2. Robustness against noise
3. Fraction of raw resources dedicated to detecting an eavesdropper
4. Robustness against some known attack (e.g., detector blinding or entangling with qubits)
5. Required classical communication bandwidth/latency
6. Simplicity of quantum hardware implementation
7. Startup time
8. Preconditions (e.g., pre-shared key for authentication)
9. Classical resources required, esp. randomness
10. Ease of integration into classical security systems
11. Ability to use in a heterogeneous quantum network environment (e.g., full end nodes with memory v. measurement-only end nodes)
12. Demands on or benefits to quantum network operations (e.g., link tomography or network routing)
13. Extension to multi-party protocols

Simply playing with ideas, such as "I found this cool thing while looking at quantum graph states...", is great, and important, and that's where highly original stuff comes from. But if you bring me an idea about QKD, I'm pretty likely going to ask which of the above things it improves, or if you think it has value for some additional reason.

(*) John Mattsson of Ericsson pointed out on the QIRG mailing list that it's not accurate to say the bits are used as keys. Instead, bits from any TRNG (true, or hardware, random number generator) are actually further processed through a KDF (key derivation function) or CSPRNG (cryptographically secure pseudo-random number generator), which is then fed to AEAD (authenticated encryption with associated data) before the key that is actually used is complete and finalized. He recommends a German government document on the topic.

Some Technical Women I Admire

I frequently have need of a list of women whose technical work I admire, so I finally decided to list some of them here. I'm not going to do all of your homework for you; you'll need to look them up yourself. Most of the older ones are fairly obvious names, and have Wikipedia pages. A few aren't famous...yet.

• Fran Bilas
• Anne Broadbent
• kc claffy
• Lynn Conway
• Agnes Meyer Driscoll
• Deborah Estrin
• Elizabeth Smith Friedman
• Yvonne Gao
• Mary Hall
• Margaret Hamilton
• Betty Holberton
• Grace Hopper 
• Mary Jackson
• Mae Jemison
• Betty Jean Jennings
• Katherine Johnson
• Kanchana Kanchanasut
• Elham Kashefi
• Sukumal Kitisin
• Hedy Lamar
• Ruth Lichterman
• Barbara Liskov
• Ada Lovelace
• Margaret Martonosi
• Kay McNulty
• Maryam Mirzakhani
• Mio Murao
• Kae Nemoto
• Emmy Noether
• Poppy Northcutt
• Tracy Northup
• Keiko Okawa
• Jennifer Rexford
• Sally Ride
• Jacquiline Romero
• Mary Shaw
• Eve Schooler
• Kunwadee Sripanidkulchai
• Donna Strickland
• Dorothy Vaughn
• Marlyn Wescoff
• Suzanne Woolf
• Lixia Zhang
• and, of course, my own women students and colleagues!

Note that, of course (as with men), it's possible for someone to do amazing, important technical work but still not be a good person. However, of the ones here I know personally, I will say I admire almost all of them as people as well as scientists/technologists.

A Bundle of New Quantum Internet / Interconnect Papers

A whole pile of our #QuantumInternet engineering papers hit the arXiv yesterday! I'll try to give just a short summary of each paper, so this post doesn't get insanely long. We are currently building a testbed quantum network, so a lot of this material addresses problems we are facing now or will in the very near future. We have three papers on use of entangled photon pair sources (EPPS nodes, in our lingo), a low-level engineering paper on getting the timing right, a paper on how to construct and use efficient switches, and a paper looking a little farther into the future at advanced techniques using complex, many-photon entangled states.

First up, a paper by Soon (all of these papers were highly collaborative in both research and writing, but I will identify each of them by the first author) on design and simulation of a particular link type, using entangled photon pair sources in the middle of the link as above. We call these MSM, or memory-source-memory, links. This kind of link was explored by Cody Jones back in the day, but not fully simulated (or implemented), which of course leaves holes in the needed protocol design and the possibility of dynamic effects that don't show up in an initial analysis. Interestingly, carefully throttling the entanglement attempt rate results in better throughput, a rather unexpected effect. We call the problem the mutual latch-fail phenomenon.
https://arxiv.org/abs/2405.09861

Soon followed that up immediately with a second paper on how longer, multi-hop paths behave when the links are different types. Reassuringly, paths where most of the links are one type but one is different seem to perform as well as completely homogeneous paths. This boosts our confidence that heterogeneous networks will work, and that introducing new technologies won't be a forklift/flag day upgrade.
https://arxiv.org/abs/2405.09862

Those first two apply pretty broadly to different types of network deployments: data center, LAN, WAN. In a third, related paper, Paolo Fittipaldi of Frédéric Grosshans' group simulated a particular subtype of MSM links: satellite! The figure above is probably too small to read here, so I recommend you actually read the paper. But with what we believe are realistic parameters, distribution of several entangled Bell pairs per second while the satellite is visible seems achievable. Performance is largely driven by the photon loss and latency (of course), but also (perhaps less obviously) by the amount of memory available at the ground stations. Extending this to examine the behavior of applications that use such a link, satellite-to-satellite connections, and networks that extra into metropolitan areas around the ground stations will make for interesting work.
https://arxiv.org/abs/2405.07589

Those first three make a pretty good set if you are interested in how entangled photon pair sources will behave in networks.

Since we are talking about preparing for heterogeneity, let me stick in a placeholder here for another paper that should appear momentarily. Poramet has done good work on how to combine purification and error correction in networks. Stay tuned for the paper.

Photons are most useful in our plans when they are entangled with something else (a memory or another photon), and come together in pairs so that we can measure them together, a technique known as entanglement swapping achieved via Bell state analysis or Bell state measurement. To accomplish this, we need good overlap of the arrival times of the photons, which we achieve by changing the length of the path that one photon follows. The basic idea is obvious, but it takes work to get the details right, and our team with Mori-san as first author worked them out. Rob Thew's gang is doing related work; see Secs. VII & VIII of a paper of theirs. We weren't aware of this particular paper before writing ours, but I think there is still value in the engineering analysis we present on tradeoffs in different possible configurations, both for single-hop and multi-hop paths.
https://arxiv.org/abs/2405.09881

Given that we are trying to bring photons together in pairs, in order to connect more than two nodes we need some sort of switch, a problem that Marii has taken charge of. I have been interested in topologies for interconnections since first being exposed to the Caltech Cosmic Cube, back in the days of stone tablets. It turns out that the problem of matching pairs is different enough from the ordinary all-to-all reordering of inputs to outputs to give us the opportunity to optimize the design compared to Clos, Beneš, and other interconnects and sorting networks. Every optimization we can make will reduce photon loss, which is our biggest enemy. We have reduced the number of switch points by about a factor of two compared to basic designs, focusing on layouts restricted to a plane for photonic chip implementation, and we think our designs are optimal. The only related work we could find was Drost et al., who used exhaustive search to solve the problem up to 10x10, but without a general solution and without considering whether the network can be reduced to a plane. Next, we need to extend our results to include non-planar designs suitable for connecting discrete switches, and prepare to implement this in a photonic chip.
https://arxiv.org/abs/2405.09860

Finally, the most technically obscure of the topics on the menu, Naphan's work on repeater graph states (RGSes). The challenge is that photons get lost, but the no cloning theorem and work related to quantum error correction tells us that we can't successfully reconstruct a quantum state if we lose more than half the photons. But with RGS, originally found by Azuma-san and with extensive work by the group of Sophia Economou, if you create a complex entangled state and can make quick decisions about the choice of what to do with the photons you do get, then you can handle losing certain subsets of photons. The theory is great, but implementing networks using these states isn't going to be easy, even aside from the physics problem of generating them correctly. Naphan has found ways to reduce the required classical communication by three (decimal) orders of magnitude. We continue to make progress toward practical implementation!
https://arxiv.org/abs/2405.09876

Whew! That's a ton of work, and we hope that it all helps bring closer the day when we can deploy quantum networks for production use, as a system interconnect for a multicomputer, in the data center, and in LANs, MANs, WANs and ultimately intercontinental quantum networks.

Oh, did I mention that the first authors of three of the above papers are undergraduates who just entered their third (junior) year? Bet you'll have trouble picking out which ones. Our students are amazing (both the undergrads and grad students).

Thanks for reading this long posting, and let us know if you have comments!

Important CS/CE Papers of Recent Years

What are your nominations for papers of the last decade (or so), ones that will show up in textbooks or change the fabric of what we do and how for decades to come?

Here are a few candidates my team (mostly quantum folks) and I came up with. Although I initially phrased it as "of the last decade", some took the liberty of going back a little farther, and I personally followed on from that with a few suggestions of my own.

• 2008: Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System (pseudonymous; for better or worse, its impact cannot be denied)
• 2009: Jacobson et al., Networking named content (PARC; this deeply influential idea was first publicly presented at Google, in a 2006 talk that is available on YouTube) 
• 2009: Craig Gentry, Fully homomorphic encryption using ideal lattices (IBM)
• 2009: Broadbent, Fitzsimons, Kashefi, Universal blind quantum computation (Waterloo, Edinburgh)
• 2012: Krizhevsky, Sutskever, Hinton, ImageNet Classification with Deep Convolutional Neural Networks (Toronto; a review in 2015 by a different but overlapping set of authors is also highly cited)
• 2014: Barends et al., Superconducting quantum circuits at the surface code threshold for fault tolerance (Google)
• 2017: Vaswani et al., Attention is All You Need (Google Brain/Google Research; geez, cited 120,000 times as of May 2024, according to Google Scholar)
• 2018: Silver et al., A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play (Google; I considered citing the earlier paper, which is cited more often, but this one is the more complete victory, and the more complete from-scratch learning system, and marks the end point of this particular path of research)
• 2020: Zhengfeng Ji, Natarajan, Vidick, Wright, Henry Yuen, MIP* = RE (UT Sydney, Caltech, UT Austin, Toronto; this is almost entirely beyond my ability to comprehend)
• Scott Aaronson blog post
• CACM article (with a good technical introduction)
• the whole 223-page shebang (still unpublished, AFAIK)

(n.b.: I consider this to still be an open discussion, but am publishing so that people can comment)

IEEE QCNC

 Two papers accepted (out of two submitted) for the inaugural IEEE QCNC. Both on quantum networking, one on error management and one on links using entangled photon pair sources. See you in Kanazawa in July!

Spelunking CACM (1976)

 

Above are two tables from a report on production and employment of CS Ph.D.s in the U.S. I fear those ratios have not changed as much as they should in the intervening half century. One or two new Black CS PhDs a year. Typically single digits for women. And, of course, it was the 1970s, so the categories of minorities of interest were Females, Blacks, and Foreigners; my apologies to those who find the categorization offensive, which most people will by modern standards.  I have heard that the percentage of women PhDs was higher in 1980 than today, but it was clearly bad in the early 1970s. Pursuing a more complete comparison is a task for another time, but just a few months later CACM had an additional article on the status of women and minorities in CS. Read them both.

Allen and Cocke talked about directed graphs as representations of control flow and possible data modification in programs. I don’t think this is the introduction of the concept of data flow; certainly control flow and flow charts are much older than the mid-1970s. The paper does list work by Kennedy, Aho and Ullman on liveness and data flow. I don’t quite understand how they break loops and how they define “intervals”, which are roughly akin to small functions with a single entry point. But this is an important concept in understanding "liveness" of data, dependency in computation, and how to schedule operations. Without work like this, concepts as varied as garbage collection, caching and out-of-order instruction execution have no theoretical foundation.

Oliver Smoot presented a report on a WIPO meeting on protecting software. It wasn't the first such meeting; the UN authorized a group back in 1971.

Lampson and Sturgis have a beautiful (of course) paper, a retrospective on an OS designed at Berkeley. Of course they had the benefit of hindsight, but as always, they clearly laid out goals for the system, a philosophy, an analysis of what they thought was possible, then the system itself, and importantly, provide extensive discussion of what went wrong both technically and in project management. This paper alone could be a great model for how to write about computer systems.

Keller talked about formal proofs of parallel programs, two years before Hoare's CSP.

Perhaps the highest impact of year was Metcalfe and Boggs on a little idea called Ethernet. They cite an earlier paper by Farber in the Feb. 1975 issue of Datamation magazine.

The number of papers I want to talk about each year continues to grow. I'll have to be more selective, so I can go back to doing deeper dives.

Seven IEEE Quantum Week Submissions!

 Hi y'all, I'm back!

Have spent the last two months in travel, start of academic year work, and especially with my head buried in pushing out some important research. As a result, we have have submitted not one, two, three, four, five, or even six papers, but SEVEN research papers (one company collaboration, one collaboration with France, one collaboration with Kanazawa as part of our Moonshot work, and four from AQUA at SFC; one appllication, one systems, and five communications papers) to IEEE Quantum Week. Oh, and a workshop proposal.

Add in that we have three other papers under review (two conference, one magazine), and counting that workshop proposal, I have eleven things under review right now. Geez. And I wonder why I'm tired...

Hoping to get caught up on some reading and writing during upcoming Golden Week holidays. I get a couple of days off! (But first, that urgent email...)