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
• Hedy Lamar
• Ruth Lichterman
• Barbara Liskov
• Ada Lovelace
• Margaret Martonosi
• Kay McNulty
• Maryam Mirzakhani
• Mio Murao
• Kae Nemoto
• Emmy Noether
• Poppy Northcutt
• Keiko Okawa
• Jennifer Rexford
• Sally Ride
• Jacquiline Romero
• Mary Shaw
• Eve Schooler
• 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...)