Spelunking CACM, Vol. 22 (1979): Cheriton and Denning

 Maybe it's just me, but after the huge set of world-changing things in 1978's CACM, it seems like not so much in 1979. Also, in minor grumbles, I didn't find a picture I liked in either of the papers I decided to cover.

One that inevitably caught my eye because of the first author is David Cheriton's Thoth. It's a complete, though fairly simple, OS, designed and built with the goal of being portable across machine architectures. It includes (and depends on) a compiler for a custom language. The language is apparently named "Eh", but they refer to it as "the base language" throughout the paper. It's a descendant of B & BCPL, which should put it closer to C than not, but the syntax is actually rather different. It assumes that integer pointers are themselves consecutive integers; the language doesn't support the notion of a byte pointer, because at least one of the machines they wanted to target didn't support byte pointers.

The file system is a tree that supports UNIX-like mount points, cleverly called "grafts", but otherwise the file naming seems like something from a parallel universe, when viewed from 2025. Among other things, the root of the FS is called "*", so "*/src" refers to what in UNIX terms would be "/src".

There is a function for creating a "process", but its first argument is a pointer to a function. Their "processes" are actually closer to modern threads, and share an address space. The OS includes support for multiple address spaces; the set of "processes" in one address space is a "team". Support for multiple teams can be compiled in or out, assuming the hardware has an MMU and virtual memory.

There is no support for multiprocessors, though they claim and I believe that it wouldn't be too hard in the OS itself. A process runs until it blocks, so multitasking is cooperative.

They achieved the goal of portability of software and the OS; Thoth ran on both the Data General Nova 2 (released in 1973, already not a new machine by the time of this paper) and the TI 990/10, both 16-bit machines, and so Thoth was designed around those limitations despite the goal of portability. I think it's arguable whether the system would meet the goal of portability to a later architecture; I would say it was focused on that pair of specific systems rather than truly working toward a system with open-ended future portability.

Overall, maybe not so much to write home about, though Cheriton's later work on V is claimed to be a "successor" to Thoth, and is of huge importance in the history of distributed systems.

Of note for similar reasons is Dorothy Denning's proposal for a hardware gadget that does RSA encryption and allows a PC to encrypt data it sends to a centralized file server (CF), as well as to securely exchange files with another PC via the CF. Some of the functions appear to be transparent to the PC, others don't. Ultimately using RSA as the only encryption mechanism is computationally intensive, although at the time, according to Denning, Rivest himself claimed there would soon be high-performance hardware implementations.

There were a few other things here in there in 1979, but nothing that really compels me to talk about. As always, of course, my primary strength is the systems work; I can't comment as fluidly or recognize the importance as clearly when dealing with algorithms and theory.

(On a personal note, I think 1979 was the year I got my TRS-80 Model 1, using a Zilog Z80 16-bit CPU. A simple and interesting machine.)

Happy New Year!

 

Sunset over fishing boats, Zaimokuza, Kamakura, Dec. 29, 2024

First, goodbye to 2024. What an amazing year globally in quantum! More to say about that in a future posting (or editorial for TQE). It was also a great year for AQUA. Highlights were going seven-for-seven for QCE2024 papers (well, 5 directly from AQUA and 2 led by collaborators) and Q-Fly. I also managed to visit the (European) Alps twice and southern Thailand once, for conferences.

I also did a thing or two for my soul; the most important was a nine-day road trip with my wife through western Honshu. Longest two-person vacation since our first kid was born more than a quarter-century ago.

However, I don't think I saw any live music, opera, theater or performing arts last year, except for an hour of Irish music in a pub in Dublin. That needs to be corrected in 2025!

I think I read thirty books this year, which is my goal each year, a very achievable number. (How many books you read doesn't really matter; there's no way to read any detectable fraction of the good books published in a year. Just read and enjoy.) In 2023, Kettle Bottom and Demon Copperhead (both coincidentally set in Appalachia) hit me hard.  But I don't think any of this year's readings will leave a mark on my soul.

Im movies, "Past Lives", "Perfect Days" and "Dune Part 2" are very different films, and each will stay with me for a long time. The first two were officially released in 2023, but I think I saw them both in 2024. "Past Lives" is about the ache for the paths not taken, while still acknowledging that the path taken is who we are. I sobbed all the way through it. "Perfect Days" likewise is about the choices we make and the life we make for ourselves. "Dune" is, well, Dune.

And of course we can't ignore the cataclysmic event of November 5. It's incumbent on us all to do what we can to help keep the world together.

On to 2025. Hoping I can find (well, make myself find) better work/life balance, while achieving the things I want. Let's roll!

Quantum Computer Architecture Work in Japan

 A couple of weeks ago, I attended The First Fault Tolerant Quantum Architecture Kenkyuukai, held in Takamatsu, Shikoku, Japan. I came away very optimistic about the future of the field in Japan. There is a good cohort of talented, ambitious, (mostly) young researchers:

• Yutaka Tabuchi, RIKEN
• Teruo Tanimoto, Kyushu (Kyuudai)
• Makoto Negoro, Osaka (Handai)
• Yosuke Ueno, RIKEN
• Ilkwon Byun, Kyushu
• Yasunari Suzuki, NTT
• Shota Nagayama, Keio/Mercari
• Takahiko Satoh, Keio

All but Shota and Takahiko were in Takamatsu and gave good talks. A selection of some of the recent architecture papers from this gang (most recent first, except ours last):

• Yosuke Ueno, Taku Saito, Teruo Tanimoto, Yasunari Suzuki, Yutaka Tabuchi, Shuhei Tamate, Hiroshi Nakamura, High-Performance and Scalable Fault-Tolerant Quantum Computation with Lattice Surgery on a 2.5D Architecture, arXiv:2411.17519 (not yet peer reviewed?). Conducts a detailed analysis of the hazards in execution of lattice surgery (an important architecture analysis technique imported from classical computer architecture), and proposes an architecture with a few extra qubits (hence the 2.5D) that substantially short-circuits some of the key bottlenecks.
• F Battistel, C Chamberland, K Johar, R W J Overwater, F Sebastiano, L Skoric, Y Ueno and M Usman, Real-time decoding for fault-tolerant quantum computing: progress, challenges and outlook (Nano Futures 2023). As advertised, useful info.
• Ilkwon Byun, Junpyo Kim, Dongmoon Min, Ikki Nagaoka, Kosuke Fukumitsu, Iori Ishikawa, Teruo Tanimoto, Masamitsu Tanaka, Koji Inoue, Jangwoo Kim, XQsim: modeling cross-technology control processors for 10+K qubit quantum computers (ISCA 2022). This team is right concerned about the scalability of classical control systems, so they have developed a simulator that assesses this. They have also proposed a control processor that is reportedly capable of handling 2D surface code for up to 59,000 physical qubits, depicted in diagrams that will make circuit lovers swoon.
• Yosuke Ueno, Masaaki Kondo, Masamitsu Tanaka, Yasunari Suzuki, Yutaka Tabuchi, QECOOL: On-Line Quantum Error Correction with a Superconducting Decoder for Surface Code (DAC 2021). Architecture, simulation and analysis (especially power) for a classical superconducting processor to sit near a surface code solid-state system such as a transmon processor using lattice surgery; I assume it would probably also work for quantum dot. This is one of those papers that I wish I had gotten the chance to be involved in.
• Daisuke Sakuma, Amin Taherkhani, Tomoki Tsuno, Toshihiko Sasaki, Hikaru Shimizu, Kentaro Teramoto, Andrew Todd, Yosuke Ueno, Michal Hajdušek, Rikizo Ikuta, Rodney Van Meter, Shota Nagayama, An Optical Interconnect for Modular Quantum Computers, arXiv:2412.09299 -- our brand-new paper! We're pretty proud of this one. See my recent blog post.

For more papers, see their respective Google Scholar profiles, linked above. Also, don't forget to look up the other collaborators (mostly physicists) I didn't name in the list at the top.

And the senior leadership, all with proper backgrounds in classical computer architecture:

• Hideharu Amano, Keio / U. Tokyo (one of Japan's most important classical computer architecture researchers)
• Koji Inoue, Kyushu (not old, but senior)
  
• Shigeru Yamashita, Ritsumeikan
• Masaaki Kondo, Keio (bridging the generations)
• rdv (not yet officially old, but not very far from it)

There are also quite a few theoretical physicists besides just those linked to above who are keeping Japan on the quantum map. I'll do a separate posting about them sometime.

There is a serious shortcoming here: all of the above (including yours truly) are (or at least present as) men. Out of about fifty-five people in the room, exactly one is (or at least presents as) a woman, a Keio undergrad (from Satoh's lab, not mine). Without solving this problem, on top of the human rights issue, Japan is throwing away half its brainpower and an even larger fraction of its creativity (due to the homogeneity and groupthink of a cluster of men, all with similar backgrounds and skills), at a time when demographics show it can ill afford to.

An Optical Interconnect for Modular Quantum Computers

 

Here's our latest paper! Our biggest effort of the year, or more correctly, two years of work supported by 20 years of learning and doing. There are "only" a dozen authors on this, but there are about 150 people in the Shota Nagayama Moonshot project doing supporting and related work.

This paper combines experimental demonstration of our network prototype (the portions in pink in the figure), insight into network topology (both the larger diagram here and some more complex diagrams in the paper), and an operation scheduling and performance estimation tool (not shown) to help us evaluate where we are and where we need to be.

Slightly paraphrasing the paper,

The current focus of modular quantum system research is the link and connection layers. This is a necessary first step towards building more complex systems. However, in order to bring us closer to scalable and robust distributed quantum systems, there is a pressing need for deeper understanding of higher-layer concepts such as switching network architectures, and their impact on the performance when executing large-scale quantum computation. The time for such studies has come.

We have dubbed our interconnect "Q-Fly", following on from butterfly, k-ary n-fly, Dragonfly, Dragonfly+, Slimfly, Polarfly, etc. Designing this was a deeper task than the final diagram reveals, and involves balancing the number of Bell state analyzers and the number of inter-group connections to accommodate both expected traffic patterns and link fault tolerance while maintaining minimal-length paths.

Of course one of the questions is how this Dragonfly-inspired network compares to a fat tree. In the technology we are working with, node-to-node connections are created by routing one photon from each node to a shared Bell State Analyzer (BSA).  It turns out that effective placement of the BSAs in the network is critical, and that doing a good job of that in a fat tree is harder than for our Q-Fly. The physical construction to allow some traffic to avoid going through the root of the tree is complex and involves inefficient pools of BSAs distributed awkwardly in the network. The Q-Fly design is much cleaner, and minimizes the number of switches each photon passes through even in large networks. We have to worry about every switch, since we can't afford to lose photons any more often than absolutely necessary. This principle led us to the Q-Fly mantra,

Every decibel matters.

Of course I'm riding high on finishing (well, almost -- we still have to get the paper through peer review) this paper, but as of right now I'd rate this the most important paper of my career to date.

Below is one of the early sketches on the whiteboard.

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.