Return-Path: <rdv@sfc.wide.ad.jp>
X-Original-To: qirg@mail2.ietf.org
Delivered-To: qirg@mail2.ietf.org
Received: from localhost (localhost [127.0.0.1])
	by mail2.ietf.org (Postfix) with ESMTP id 6EF32127A8E30
	for <qirg@mail2.ietf.org>; Tue, 11 Aug 2026 02:18:20 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=ietf.org; s=ietf1;
	t=1786439900; bh=gzR9D0EC3wRMrldxZJem/MancHdOGwfAc5aGOOxOPBA=;
	h=Date:To:From:Subject;
	b=NlSLcxLLLmMMGXvJO1wkbB64naYsRWCW+Iy7NMrReOigKrAY7TvK0FkJjmHAX2G6S
	 fah74Yq6M15uq1zUW9WSUgQEuoK2dlmKHDc91g5uRSRW9SIftiBKkrBNb6XIjs8G0l
	 lPQDxBeF48vv2taLCLNX9rbfJbdOHYBgPqOAmY6s=
X-Virus-Scanned: amavisd-new at ietf.org
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level: 
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5
	tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
	DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_NONE=-0.0001,
	RCVD_IN_VALIDITY_RPBL_BLOCKED=0.001,
	RCVD_IN_VALIDITY_SAFE_BLOCKED=0.001, SPF_HELO_NONE=0.001,
	SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: mail2.ietf.org (amavisd-new); dkim=pass (2048-bit key)
	header.d=sfc.wide.ad.jp
Received: from mail2.ietf.org ([166.84.6.31])
	by localhost (mail2.ietf.org [127.0.0.1]) (amavisd-new, port 10024)
	with ESMTP id vAgFw6TjhRib for <qirg@mail2.ietf.org>;
	Tue, 11 Aug 2026 02:18:18 -0700 (PDT)
Received: from mail2.sfc.wide.ad.jp (mail2.sfc.wide.ad.jp [203.178.142.149])
	(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
	 key-exchange X25519 server-signature ECDSA (P-256) server-digest SHA256)
	(No client certificate requested)
	by mail2.ietf.org (Postfix) with ESMTPS id 245DF127A8E13
	for <qirg@irtf.org>; Tue, 11 Aug 2026 02:18:18 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=sfc.wide.ad.jp;
	s=mail2; t=1786439888;
	bh=gzR9D0EC3wRMrldxZJem/MancHdOGwfAc5aGOOxOPBA=;
	h=Date:To:From:Subject:From;
	b=iUR1xvb2qUuLL2UL7qg4P5MA0NrdsBCPHb/pf84QZdnP4nBZqA0IkCYNcprganx2f
	 quGkG5w6h+VG1yV2aQtdEF3ZcprMsA67JKt0l8oM8Je/2ZyRkvX9x4XiktwTjM5T4r
	 TmTHY2TOvVfKD0SiD1IZ/HZ9aU47JpuOXxWTVxgHAXwF78ItJCNNlUuoUIolzlqDB0
	 MEaUr78Xjn7NAfvhqi0i72xKwfE//pfO4RB8A+5lO9RYvQqQGQQMKvJnLuD/+EHaBK
	 a39zLW+DuOtdz1Km6JWottaPyTBeKkRoSY18XgydFn5daF/REhw4q4hzVaagoijIFN
	 msynWSAaTFXUg==
Received: from [192.168.3.112] (softbank060089151162.bbtec.net
 [60.89.151.162])
	(Authenticated sender: rdv@sfc.wide.ad.jp)
	by mail2.sfc.wide.ad.jp (Postfix) with ESMTPSA id 6AEE780350
	for <qirg@irtf.org>; Tue, 11 Aug 2026 18:18:08 +0900 (JST)
Message-ID: <aa69f4bc-37fa-4eb9-9904-1e46ec506a04@sfc.wide.ad.jp>
Date: Tue, 11 Aug 2026 18:18:06 +0900
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Content-Language: en-US
To: "qirg@irtf.org" <qirg@irtf.org>
From: Rod Van Meter <rdv@sfc.wide.ad.jp>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID-Hash: DJUB3TSLJAIE6VG64ZOXGITHTPSEKJDK
X-Message-ID-Hash: DJUB3TSLJAIE6VG64ZOXGITHTPSEKJDK
X-MailFrom: rdv@sfc.wide.ad.jp
X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency;
 loop; banned-address; member-moderation; header-match-qirg.irtf.org-0;
 nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size;
 news-moderation; no-subject; digests; suspicious-header
X-Mailman-Version: 3.3.9rc6
Precedence: list
Subject: =?utf-8?q?=5BQirg=5D_draft-cacciapuoti-qirg-quantum-native-architecture-01_?=
 =?utf-8?q?=26_Napoli_architecture_in_general?=
List-Id: Quantum Internet RG <qirg.irtf.org>
Archived-At: 
 <https://mailarchive.ietf.org/arch/msg/qirg/KgFuLSzgHuGeVA19kX_inlSE8us>
List-Archive: <https://mailarchive.ietf.org/arch/browse/qirg>
List-Help: <mailto:qirg-request@irtf.org?subject=help>
List-Owner: <mailto:qirg-owner@irtf.org>
List-Post: <mailto:qirg@irtf.org>
List-Subscribe: <mailto:qirg-join@irtf.org>
List-Unsubscribe: <mailto:qirg-leave@irtf.org>

Hi folks,

All of this is personal opinions, except for the bit on the use of the
word "forwarding".

I'm going to jump in here with some comments on this draft as
well. Sara and Marcello are probably still on vacation and so probably
can't reply soon, but I'm heading out on about six weeks of travel
myself (starting with a visit to my mother), and wanted to get this
out before I go.  Jessica, Caterina, Joaquin and Amar may have
independent responses to my comments here, of course.  (Minor
editorial note: this was mostly written with "they" rather than "you",
as if the authors aren't listening or responding.  My apologies if
that bothers you, but this is mostly addressed to a) myself and b) the
original authors.)

I mostly agree with Wojtek's comments on the I-D; I had written about
half of this before seeing his comments, and I think we're pretty well
aligned.  I especially agree with his comments on justification of
scalability, which I think will show up in my comments here.
https://mailarchive.ietf.org/arch/msg/qirg/Ppx5rAawj_cUAoVRQ6e0Co6A4MY/

I went deeper into the associated research papers because I wanted to
understand better where the ideas in the draft come from and where the
overall effort to create a specification might be going.  Of course
ideas and opinions change over time, so just because they wrote
something in a paper several years ago doesn't necessarily mean they
still think it's the best way to go.  (Or even a fresh paper may
represent an exploration of an alternative instead of a fleshing out
of a direct part of the architecture.)

With apologies, this is going to be VERY long (over 5,000 words). It
has taken me a lot of work, so I hope that in the end it helps push
forward the conversation on Quantum Network and Internet
architectures, including helping to identify what's common among some
of the candidates and what the differences are, based on differences
in assumptions about technological development as well as goals for
the system.

TL;DR:

* I think the main Napoli architecture is a 4G architecture, well beyond
   where the technology will take us for the foreseeable future. (The
   very latest major paper does have some 1G-like characteristics
   discussed more below.)
* The many-long-lived-tunnels method is interesting and bears a lot
   more research.  It could be a good choice for working around the
   "edges" of a dense core.
* Overall, I'm skeptical of packet-based quantum network
   architectures, but they bear further research and matching to
   projected technology development.  Lots of smart people disagree
   with me here.
* Personally, even if you accept the idea of packets for quantum
   networks, I don't think the in-band, all-quantum packet structure
   will be a good choice; I don't see any reason for the headers not to
   be carried over a coordinated classical channel, and carrying them
   in the quantum channel comes with a high cost.
* The dynamic kernel approach I like; I find it similar to our
   approach.  It's event-driven, and actions are compiled to physically
   appropriate actions locally and executed as independently as
   possible.
* The active-packet approach (either stamps or superposed addresses),
   which differs from our RuleSets in that they are carried in the
   quantum packets rather than stored as connection state at the
   routers, seems to me to be solving a non-problem, and the cost of the
   complexity and performance demands introduced are will be the wrong
   tradeoff.
* At the end of this tome, there is a little bit of a comparison to
   our architecture.

References I worked from to understand the Napoli architecture:

1. Angela Sara Cacciapuoti, Marcello Caleffi, Jessica Illiano, C. De
    Risi, A. Abane, Joaquin Chung
    Quantum-Native Architectural Tenets and Philosophy for the Quantum 
Internet
  https://datatracker.ietf.org/doc/draft-cacciapuoti-qirg-quantum-native-architecture/
2. Marcello's slides covering the -00 version of that draft
  https://datatracker.ietf.org/meeting/124/materials/slides-124-qirg-design-principles-for-the-quantum-internet-quantum-control-plane-caleffi-00
3. Sara's slides covering the -01 version of that draft
  https://datatracker.ietf.org/meeting/126/materials/slides-126-qirg-draft-cacciapuoti-qirg-quantum-native-architecture-01
4. Angela Sara Cacciapuoti, Jessica Illiano, Marcello Caleffi
    Quantum Internet Addressing
    IEEE Network
    https://arxiv.org/abs/2306.05982
5. Marcello Caleffi, Angela Sara Cacciapuoti
    Quantum Internet Architecture: Unlocking Quantum-Native Routing via
    Quantum Addressing
    IEEE Trans. Communications
    https://ieeexplore.ieee.org/document/11322738
6. Angela Sara Cacciapuoti, Marcello Caleffi
    A Quantum Internet Protocol Suite Beyond Layering
    IEEE Transactions on Network Science and Engineering
    https://doi.org/10.1109/TNSE.2026.3679795
7. Jessica Illiano, Marcello Caleffi, Antonio Manzalini, Angela Sara 
Cacciapuoti
    Quantum Internet Protocol Stack: a Comprehensive Survey
    https://arxiv.org/abs/2202.10894
    (n.b.: this survey doesn't cover their own architecture, and it's
    good but now rapidly becoming dated as a lot of work has come out
    in the last four years.  But if you need to get oriented, it's
    solid place to start.)

(I also skimmed a couple of others but didn't keep good notes on them.)

Let me oversimplify the assumptions, problem and architectural
decisions down to about six points:

-1. The key assumptions are that
-1.1 high-fidelity entanglement itself is plentiful; and
-1.2 execution of quantum programs at quantum nodes
    (including routers in the quantum network) is cheap, reliable
    and low latency.
0. The key challenge in designing quantum networks is achieving
    scalability in managing quantum entanglement.
0.1. Excessive per-connection state passing through central routers
    doesn't scale.
0.2. Path length has higher impact in quantum networks than in classical
    networks, so it is crucial to minimize the use of "stretched" paths
    that are longer than the minimal path between two nodes.
1. The unit of communication is the quantum packet, which is
    "forwarded" across entangled tunnels, although the stated goal is to
    create E2E entanglement for end nodes; I don't quite understand yet
    how forwarding and entanglement swapping interact in this
    architecture.
2a. Routers should maintain large numbers of long-lived virtual
    tunnels, which are multihop router-to-router connections that they
    continually restock with Bell pairs.  (n.b.: The authors don't
    usually use the term "tunnel", but I think it's helpful here, and
    they usually use the term EPR rather than Bell pair.)
2b. E2E connections are routed through these tunnels, minimizing the
    number of virtual hops and possibly applying other cost metrics.
3. The normal per-packet processing of headers, including selecting
    the nexthop, should all be done utilizing quantum computation.
4. Each quantum packet should carry "stamps", which are state for the
    processing of the packet itself.  The stamps essentially represent
    program fragments, processed via a Plan of Action constructed
    independently at each node along the path from the set of stamps.

There's a lot more to it than just this, but I think those capture the
essential ideas.  I wish I could better articulate this in terms of the
problems being solved, but I'm not sure I really can yet.

Let's set aside the <-1> assumptions for the moment, but they underlie
a lot of the following work, and represent probably the biggest
divergence from my own thinking.

The challenges in <0> above are reasonable concerns. Let's look at them:

<0.1> As it happens, I worry a lot less about the amount of classical state
needed to support a quantum connection (even in our rather active,
distributed computation-oriented architecture) than I do about the
availability of entanglement to be shared among a set of E2E
connections passing through a node, regardless of whether the
connection is designed to use classical state at routers or not. That
is, personally I think <-1.1> won't be a valid technological point for
a long time yet.

I did just a little asking around, and while the people I asked didn't
have published numbers yet, it seems that a router at an IXP can
expect to see several million IP flows passing through over the course
of a minute.  That's a lot, but the memory for connection state
wouldn't be a problem; the challenges would be doing the per-packet
processing at line rate, and managing buffer space properly if it is
anything other than FCFS.  With quantum event rates FAR lower (six
orders of magnitude? more?), the processing isn't the problem, but
buffer space management is indeed a big deal and an open area of
research.

<0.2> I agree, we should be working to minimize the amount of "work"
needed for each E2E connection.  That's one of the key metrics we
looked at back in our path selection paper
[https://arxiv.org/abs/1206.5655].  But I don't think that the
"stretching" of paths due to shortcomings in the addressing and
routing architecture are as big a concern as the Napoli team does.

One key reference they keep coming back to is
https://arxiv.org/abs/0708.2309.  That particular paper is
interesting, but doesn't seem to me to be very mainstream; it has some
2007 opinions about how the Internet was evolving that in the end seem
not to have happened over the last 20 years.

One of the authors of that is kc claffy, who is one of the most
important people in Internet measurement and (interesting side note to
me, at least!)  got her start during an extended visit to Japan and
whose first paper was with T. Asaba, Jun Murai and Osamu Nakamura.

Anyway, the Krioukov paper is on "compact routing", which is not a
term you will hear from Internet people much. What it appears to mean
is worrying about routing table growth and address aggregation for
routing purposes.  The canonical place to learn about that these days
is probably Geoff Huston's annual blog entries for APNIC, most
recently https://blog.apnic.net/2026/01/08/bgp-in-2025/
The IPv4 table is now a little over a million entries, which is a lot
but not the disaster it was feared to be twenty years ago.

The "compact routing" folks fear that keeping the routing table size
manageable means selecting suboptimal routes that result in
"stretching" a path.  AFAICT, this is in truth a non-issue in today's
Internet, but the Napoli team worries about it in their quantum
network design.

So, I think it's reasonable to expect that quantum networks can select
a "best" path for the foreseeable future.  The survey by Amar &
friends is great https://ieeexplore.ieee.org/document/10882978.  I
think the big question right now is not the abstract, graph-theoretic
problem of path selection, but instead how to integrate path selection
and resource management/access multiplexing.  We did some preliminary
work on that long ago
https://aqua.sfc.wide.ad.jp/publications/Aparicio-master-thesis.pdf
and some in the restricted environment of a data center network/LAN
just recently in https://arxiv.org/abs/2605.07295 (which will be
presented next month at IEEE QCE).  There are some other people out
there working on this, as well, and I'm falling behind on the
literature here; both the Napoli team and a couple of other things
I've read recently have references I hadn't seen before, such as
https://ieeexplore.ieee.org/document/10575563/.


** Quantum Packets **

<1> Quantum packets: here's where I get stuck most on understanding
the architecture.  With apologies to the authors, even after reading
the above, I'm not quite sure what constitutes a packet and how it
moves through the network.  Maybe my brain is working from too
different a point of view.  But the most up-to-date reference [6] is
also, happily, the most concrete on processing.  It provides some
information on how the metadata in the packet is created and updated,
how a packet is processed and how it moves through the network.

I am unclear on whether a packet is believed to be reliably delivered.
Some of the papers pay a lot of tribute to early datagram work from
the 1970s, so I think maybe the packets are assumed to be unreliable.
Moreover, somewhere they mentioned that since we are building E2E
entanglement, it's okay to drop some things because they aren't
carrying valuable data.  However, given how much work goes into each
packet, this might be a poor choice.

The figure from Sec. 5 of [1]:


+---------------------------------+----------------------------------+
   |       Quantum Header            |     Quantum Payload     |
+---------------------------------+----------------------------------+
   |   - Quantum Address |A>         |  - Entangled qubits |e_i>        |
   |   - Optional metadata           |   (bipartite or multipartite)    |
+---------------------------------+----------------------------------+

(Here's hoping the ASCII art figure survives modern mail writers &
readers.)

This is simplified and a little different from Fig. 3 in [5], which
includes:

header:
- src addr: x_i
- dst addr: x_j
- an array of address structures, |A> = |A_j^1>,|A_j^2>,|A_j^3>...
   **each of which is a weighted superposition of node addresses**
payload:
- an array of qubits: |e_1>,|e_2>,|e_3>...

Note that x_i and x_j are *classical*, single-valued addresses; any
given packet has exactly one source and one destination address.
However, these addresses are encoded in qubits, such that the entire
packet can all be viewed as a single block of qubits.

However, the next set of header fields (which I think is what is
called "metadata headers" or "meta-headers" in some of the papers and
in the figure above?) *is* in a weighted superposition.  This is very
likely the source of the confusion over whether or not the Napoli
architecture is proposing that destination addresses be in
superposition in a way that "splits" quantum amplitude over a set of
destinations, as at least some of the Innsbruck papers propose
(https://www.nature.com/articles/s41534-021-00472-5).

[Edit: I now think Fig. 3 of [5] is incorrect.  See more on this
below, but I'm keeping the description here just in case I'm wrong
about it being wrong, and to help others understand where I went wrong
if I'm right about it being wrong. (Confused yet?  So am I.)]

I'm a little unclear on whether |A> in the I-D figure above [1] is
supposed to be the same as |A> in [5].  I think not.

Focusing on the |A> from [5], it appears to be a *complete routing
table for the network*, carried *in the packet itself*.  This is a
striking design choice, with implications that echo through all of the
architecture.  I'm also not entirely certain I've understood it right.

Note that |A> is *not* a source route header, a la RFCs 5095
(deprecating part of RFC 2640), 6275, or 6554, or like SRv6 (described
in a whole plethora of RFCs including 8754).  I actually don't see why
this couldn't be a source route, which would simplify all of the
processing and allow this meta-header to be carried in the classical
channel.  If you don't like stateful connections and are worried about
path selection overhead, this can help, but it doesn't solve the
scalability problem of having most of the network nodes know a LOT
about the network topology; in fact in might make it worse.

But sticking with the proposed structure, here's what I understand
(which might be wrong).  (This idea is also tied up with the
many-tunnels notion, which we'll defer for a bit, so part of this is
oversimplified.)

Sec. II-D of [5] says, "[F]orwarding decisions...[are]...enabled by a
quantum header in the packet, as illustrated in Fig. 3, which carries
the quantum equivalent of source-destination addresses. This approach
generalizes 'next-hop' selection in the quantum realm by applying
appropriate quantum operations to quantum addresses in routing tables,
thereby eliminating classical header parsing."  Then the caption to
Fig. 3 says, "Quantum packet structure. The header carries quantum
information for the quantum routing logic, such as source-destination
quantum network address |x_i>, |x_j>, and quantum superpositions
|A_j>, representing set of quantum nodes introduced in Sec. IV-B,
while the payload carries entangled qubits (ebits) to be shared among
network nodes."

I now think that that description surrounding the packet structure in
Fig. 3 is wrong, that |A_j> is *held at the router nodes*, not
included in the packet.  Also note that the packet figure in the I-D
(the ASCII figure reproduced above) is simpler and does not appear to
include the routing information.

Assuming those qubits labeled ebits are locally buffered at the router
(as discussed next), I'm now back to not understanding what a "packet"
is in this architecture.


** Routing and Next Hop Selection **

So, proceeding from this point forward as if the routing info is held
at the router...

A router has a "quantum routing table", illustrated in Fig. 5 of
[5].  (They use "entanglement service provider", or "ESP", but as far
as I can tell an ESP is just a router, so I'll stick with the term
router here.)  This is Sec. IV-B, mentioned above as being where |A_j>
is defined.

They define a routing table entry (Fig. 5) as (I'm reordering fields
in a way that makes sense to me, not their order):

* the nexthop address (|v_j> in the figure; I am going to write it
   without the ket as v_j since it's effectively classical info)
* the matching condition, which is not simply a longest prefix, as
   in a UNIX-like or Internet-like FIB; it's a *SUPERPOSITION* of the
   addresses of the *NEIGHBORS* of v_j.  (recall v_j is our
   neighbor, so this is the neighbors of that neighbor)
* some "ebits": I believe these are the *actual* qubits that are
   entangled with the neighbor v_j!  The result of the routing lookup
   is not just "you should send to v_j", it's "here's a qubit entangled
   with v_j for you to use."  (Or, presumably, "here are enough qubits
   to send the entire packet to v_j.")  Thus, this isn't really a
   _routing_ table, it's a combined FIB and buffer management table!
   This is an important distinction.

I put "routing table" in quotes because it's not a RIB (routing
information base), and in fact I don't think it's exactly a FIB
(forwarding information base) either.  What I *think* it actually is,
is a combined FIB and buffer management subsystem.  This is also a bit
of a departure from other proposed architectures.

For every virtual neighbor a router has, there is an independent
routing table entry.  It's a little bit like an inverted FIB in a UNIX
system, where the lookup key is the dst addr, and the result is an
interface index or a neighbor's address, except that we have to scan
the entire table and query the node address superposition in order to
figure out if this particular neighbor is the right match.

The addresses being matched are *not* labeled |A_j> in Fig. 5, but in
Fig. 7 and Eqs. 36 & 37 they are.  So I guess we're on solid ground
here saying that the we're *NOT* doing source routing with the routing
table carried in the packet itself.

The next hop is selected from this table using Grover's quantum search
algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm. Sec. IV
of [5] covers this in detail.  I don't believe this is an effective
design choice, but I also don't think it's actually crucial to the
architecture so this isn't a showstopper criticism.  (It is, however,
one of the key points related to their claim that classical control
doesn't scale, which, as Wojtek pointed out, is claimed frequently but
not supported by any data or quantitative analysis I have seen in any
of the papers I have read.)

The proposed implementation of Grover will require hundreds of
long-lived, high-fidelity qubits and thousands or tens of thousands of
high-fidelity gates.  This essentially implies that each quantum
router is a full-fledged quantum computer, with a lot of memory and
quantum error correction.  This is one of the primary reasons I say
this is a 4G architecture.  It assumes an even stronger
repeater/router node than the 3G architecture.

I spent a long time studying the circuit they propose, but in the end
the key point for our purposes is that it selects a virtual neighbor
and a buffered qubit or qubits that are entangled with that neighbor.

Addressing point <2a> & <2b>:

The "virtual neighbors" are what I am calling tunnel endpoints. As
best I can tell, the set of neighbors for each node is intended to be
long-lived.  Although other researchers have proposed dynamic
entanglement swapping with set of perpetually-changing neighbors that
must be tracked (which I think is impractical), I think in the Napoli
architecture tunnels are perpetually "recharged" with entanglement so
that there are always Bell pairs available.

What I have called tunnels, they call virtual neighbors with
"activated entanglement-proximity", and the topology on top of that
they call the "artificial topology".  In [5] II-D, they refer to
"artificial topology maintenance" which requires them to "continuously
regenerate virtual links" as they are depleted by forwarding.

Under the assumption that entanglement is readily made, this seems
like a potentially good choice.  It can be used to simplify routing
around/across a dense network core.  It's trying to solve the problem
of potentially needing to understand the entire Internet topology,
which is a crucial issue.

As I understand it, if the network consists of n_e routers, each
router has O(sqrt{n_e}) neighbors.  Although they use O(.) notation, I
believe the intended constant factor is 1, so if you have 100 routers,
each has ten neighbors; if you have 100,000,000 routers, each has
10,000 neighbors.  10K tunnels/neighbors sounds like a lot, but in
classical terms it's really not; when I was at Network Alchemy around
the year 2000, we built a VPN gateway that used a single Pentium CPU
and was designed to handle 30,000 IPsec tunnels.  Sufficient
production of entanglement, availability of buffer memory, and
multiplexing across the tunnels instead are the challenges, which
aren't really addressed by the Grover routing table lookup.

The key idea behind this particular number is to make every
router-router pair be one or two virtual hops away as often as
possible, and effectively never more than three.  This is especially
crucial for the Grover lookup, which they have designed to search
across the set of neighbors-of-neighbors.  If each router has
0(sqrt{n_e}) neighbors, then the set of neighbors-of-neighbors is
O(sqrt{n_e}^2) = O(n_e).

However, intelligent selection of the set of neighbors is tricky. If
they are selected so that each added tunnel adds a new node to the
topology, of course it will be cycle-free, and you will end up with a
tree that is exactly n_e - 1 links.

If instead they are selected at random (with replacement), then the
topology graph will contain triangles and larger cycles.  A little
calculation shows that as n_e --> infinity, P(distance > 2) --> 1/e =
~36%.  That would be a problematically large probability in their
scheme.

[5] III invests a lot of effort in discussing path cost and proving
various constraints on a couple of variants in selection, but TBH I
get lost in how the path cost is used to select neighbors.  Every node
creates a tunnel/virtual link with every node with an entanglement
cost (deliberately left undefined here, but could be e.g. time to make
a Bell pair) below a certain threshold, plus some set of other nodes
in the network that I think are randomly chosen.  To me, this scheme
seems to require a LOT of classical knowledge about the complete
network topology, including the ability to efficiently determine the
set of nodes below that threshold and the ability to select other
nodes in the network at random.

Moreover, this results in network-wide total work to create and
maintain sqrt{n_e} tunnels * n_e nodes = n_e^{3/2} total virtual
links.  If n_e = 10^8, then this is 10^12 total tunnels in the
network, the vast majority of which will never be used.

Instead, it seems crucial to *design* the physical and virtual
topology to match physical constraints, traffic demands and
organizational needs.

Which is, in fact, what the Internet's three-tier scheme of LAN
(spanning tree), IGP (OSPF, ISIS, or iBGP), and EGP (eBGP) does. It's
known to be imperfect, but as an existence proof for a network
consisting of a lot of routers acting autonomously, it's hard to beat.

Our QRNA (https://www.nii.ac.jp/pi/n8/8_65.pdf,
https://doi.org/10.1145/3610251.3610556,
https://arxiv.org/abs/2112.07092) attempts to provide similar
recursive isolation of topology by creating connection-based tunnels
across individual networks (ASes or equivalent).

And with all of this I'm once again lost as to the expected semantics
of a "packet".  Sometimes it feels like a locally-held data structure
that is guiding the development of E2E Bell pairs, sometimes it feels
like a datagram that does get transferred (teleported, most likely)
hop to hop along the path.  In either case, I'm unclear on how the
"packet" gets from the end node to the router (where our discussion
has been centered), how many qubits of payload it contains, and lots
of details about the supporting classical signalling (which still
seems to be necessary).

The 1G, 2G, 3G taxonomy (https://www.nature.com/articles/srep20463) is
about increasingly demanding management of errors (photon loss, state
& gate errors, decoherence).  The Napoli architecture assumes:

* high entanglement rate
* high fidelity entanglement
* high availability of quantum memory at routers
* low-latency, high-speed quantum computation

So while it's not fully accurate to classify this architecture in the
same way, I think it's fair to call it a post-3G network.  I'll just
settle for 4G for the moment.

...and the next extension to the architecture actually *DOES* deal
with both errors and with classical messaging.  The newest paper,
"Beyond Layering" [6], introduces "stamps" attached to packets. Each
stamp represents a requested piece of functionality, such as
purification.  These stamps seem to be about halfway in between our
RuleSets and David Tennenhouse's IP Capsules from the 1990s (predating
and in some ways heralding SDN), 
https://dl.acm.org/doi/abs/10.1145/231699.231701.

This one is such a departure from the others that it doesn't even
mention virtual links or address superposition or routing, though its
main example does talk about teleporting over a two-hop overlay. It's
much more focused on the concrete tasks necessary for processing a
single request.  It still doesn't really take up the issue of a
connection, and doesn't discuss multiplexed use of entanglement
resources.

See [6] Fig. 4.  This is an incredibly helpful figure for
understanding the lower-level architecture they propose.  The
Initiator (I'm very happy to see the use of this term rather than
"source") creates a Plan of Action (PoA) for the packet.  The PoA is
only held locally, and is generated separately at each node for each
packet, but its core is translated into a set of Stamps are requests
for specific actions.  Stamps are carried in the packet itself, and
can include things like:

* LINK_PR
   (purification request? not sure)
* ACT_FORWARD
* ACT_HOLD
* (local SWAP at the intermediate node isn't part of the plan decided
   by the Initiator?)
* CONSUME_TP
   (complete the teleportation?)

Classical messages can be emitted, and can trigger further actions at
the receiving ends.

There are some details here that can be quibbled about, but the basic
structure of the PoA is good.  However, as noted above, I think this
should be done using (classical) state at routers along the path,
rather than being incorporated into the quantum packet.

I still don't fully understand the packet format, including how many
qubits are in the header and in the payload.  The payload seems to be
intended to carry halves of Bell pairs from the Initiator, or possibly
an intermediate node in the path, to the destination (what we would
call "Responder" in connection setup, but they don't have that
notion).

One issue is that the Stamps are to be carried in the quantum packet,
which means they are likely to consume a lot of quantum bandwidth and
demand high-fidelity carriage, otherwise the Stamps will become
corrupted.

I would like this design a lot better if the quantum header were
simply turned into a classical header.  Then we would have a simple
argument about the locus of state, whether it should be distributed or
localized to a single node.  I think this argument will come down to
how much work turns out to be absolutely necessary in the middle of a
path as the technology develops.  If we do wind up really needing
purification and anything other than straight-up entanglement swapping
in more than one or two places in the path, I think we will wind up
with the distributed connection.  That's the way I think of our
architecture.

To extend the comparison a little more with our QRNA/RuleSet
architecture (https://arxiv.org/abs/2112.07092
https://arxiv.org/abs/2112.07093 https://arxiv.org/abs/1904.08605):

* Plan of Action (PoA): like our RuleSet, describes a sequence of
   things that should happen.  Our RuleSets are stateful, defined by
   the Responder during connection setup, and live through the
   connection.  Napoli PoA is ephemeral, defined locally for a packet
   and lives only until that packet processing at the local node is
   complete (which could actually be until the E2E transaction is
   complete).
* Dynamic Kernel: like our RuleSet Engine.
* Stamps: like our Rules.  Each Rule of ours contains a Condition
   Clause and an Action Clause.  Stamps likewise wait for some
   condition to be fulfilled before they can be "committed".
* The biggest difference is our full-path, fully distributed but
   asynchronous *computation* which results in creation of E2E
   entanglement, versus their emphasis on trying to be closer to
   hop-by-hop and to carry less state at intermediate nodes.  Given
   that an entire PoA can't be retired until the local resources can be
   reclaimed, this is maybe not as big a difference as it first seems.

Overall, except for the need for high-fidelity bandwidth to carry the
Stamps in-band, this is a 1G architecture, I think, and much more
implementable than the 4G stuff in the first half of this message.
One open agenda item, from my point of view, is improving the
integration of those two sets, assuming that is indeed the Napoli
plan.

-----

Okay, that's more than enough for now.  Just a few minor notes to
close things out:

* The "orthogonal subspace" of the address encoding seems to be
   unnecessary, and might even rest on some misunderstanding of
   encoding data in quantum states?
* The term "ebit" is already defined with a different meaning, long
   ago.  See early Bennett papers.  Let's not run around redefining
   terms unless necessary.
* As anybody hanging around QIRG can tell you, I dislike the use of
   the term "forwarding" unless you're really literally forwarding a
   packet to another node.
* In Sec. 4 of the I-D, we have "This section extends Section 5 of
   [RFC9340].</par> The Quantum Internet is an entanglement-packet
   switching network,..." that wording gives the impression that 9340
   defines the Quantum Internet as a packet-based network, which it
   does not. I recommend you reword it to be clear that packet-based is
   your proposal (though I think not completely original).

Whew!

I think I now have a moderate understanding of the overall Napoli
architecture.  I'm not sure yet how they overall want to move forward,
but it's great to see the architectural ideas becoming more concrete.

I'm off to West Virginia to see family, then Korea for a workshop,
Indonesia for work, then back home, then I'll see Sara, Joaquin and
others in Toronto!  So I'll likely be even worse than usual about
responding to email, but I'll try to keep up.

Happy August, y'all,

--Rod


