Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Addressable Quantum Gates

Addressable Quantum Gates PABLO ARRIGHI, Université Paris-Saclay, INRIA, CNRS, LMF, France and IXXI, Lyon, France CHRISTOPHER CEDZICH, Quantum Technology Group, Heinrich Heine Universität Düsseldorf, Univer- sitätsstr. 1, 40225 Düsseldorf, Germany MARIN COSTES, ULYSSE RÉMOND, and BENOÎT VALIRON, Université Paris-Saclay, CNRS, Centrale Supélec, LMF, 91190 Gif-sur-Yvette, France We extend the circuit model of quantum computation so that the wiring between gates is soft-coded within registers inside the gates. The addresses in these registers can be manipulated and put into superpositions. This aims at capturing indeinite causal orders and making their geometrical layout explicit: we express the quantum switch and the polarizing beam-splitter within the model. In this context, our main contribution is a full characterization of the anonymity constraints. Indeed, the names used as addresses should not matter beyond the wiring they describe, i.e. quantum evolutions should commute with łrenamingsž. We show that these quantum evolutions can still act non-trivially upon the names. We specify the structure of łnameblindž matrices. CCS Concepts: · Theory of computation→ Quantum computation theory. Additional Key Words and Phrases: models of distributed quantum computing, anonymous, identity-oblivious, alpha equiva- lence, name-invariance, covariance, markovian dynamic graphs, timed quantum circuits, clocked quantum circuits, quantum causal graph dynamics, quantum controllable quantum circuits, quantum FPGA. 1 INTRODUCTION The standard paradigm for quantum computation is the coprocessor model. In this model, quantum evolution is controlled by a purely classical device Ða conventional computer. Quantum computation is described as the list of elementary instructions Ðthe quantum gatesÐ sent to the coprocessor: the so-called quantum circuit. This representation has long been thought of as the most viable model of quantum computation, and it has been successful in realizing sizeable complexity gains on numerous useful algorithms. Several other models of quantum computation have been designed to ofer other quantum computing possibili- ties, compared to the usual circuits (wire/gate) vision Ðnotably : one-way computing 29], quantum [ walks23 [ ], adiabatic computing 1], hybrid [ models and many more, some of which already proved their practical use time and time again. However, even when sticking to the wire/gate point of view, one quickly notices that in the coprocessor model only the data is quantum. The control low, i.e., the order in which the gates are to be applied, is classically determined and deinite. In other words, the wiring between the gates is ixed and, albeit quantum, the data lows through the circuit in a deinite, classical manner. Quantum mechanics allows for more:10in ] it [ was argued by constructing a new elementary circuit, the so- called quantum ł switchž, that classically ordered gates are not the only possible paradigm of quantum computation. Instead, the quantum switch behaves like quantum a test: given a qubit � and a single instance of gates � and � , Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for proit or commercial advantage and that copies bear this notice and the full citation on the irst page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). © 2023 Copyright held by the owner/author(s). 2643-6817/2023/2-ART https://doi.org/10.1145/3581760 ACM Trans. Quantum Comput. 2 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron the operationSwitch(�)(� )(�) realizes |0⟩ ⊗ |�⟩ ↦−→ |0⟩ ⊗ (�� |�⟩), � � (1) |1⟩ ⊗ |�⟩ ↦−→ |1⟩ ⊗ (�� |�⟩). � � Adding the quantum switch to a circuit renders the orders ofindeinite gates [10, 21, 26]: the order in which � and � are applied depends on the state of the contr ł olž qubit �. Hence, addingSwitch enables dataand computation to be in superposition. Notably, the quantum switch is not realizable in the coprocessor model, when only one instance�ofand � is available 10]. Y[et, it was shown to be realizable in experiments 19, 28, 30 [ , 31]. Moreover, it allows for gains in terms of communication 9, 22, 35] and [ algorithmic complexity compared to textbook circuits [2]. In the recent years, several attempts have been made to encompass indeinite causal orders within a consistent model of quantum computing. A considerable strand of works focuses on the compositionality of indeinite causal orders, via sums of diagrams in the process theory of quantum mechanics 36], or higher-or [ der circuits featuring type annotations for that speciic purp 6], ose some [ for routing per subspace32[], other to enforce the time-ordering of packets 27].[ In all these proposals however, the low of information may be superposed, but it remains static. A more recent strand of works works by distinguishing data qubits from external control qubits [11, 34]. The latter are used to encode the order in which gates are to be applied upon the former. Because the control qubits can be manipulated coherently and conditionally, the low of information is both dynamical and quantum, i.e. łsecond-quantisedž in the language of [11]. In this paper we introduce a new model of quantum computation, not by extending textbook quantum circuits in a ad hoc manner (e.g. adding quantum switches 2], p [ olarizing beam splitters 7, 12] [etc.) but by introducing a single new principle encompassing all of these constructs and hopefully more. The basic idea is that gates are no longer hardwired to one another. Instead, the wiring is soft-coded: each gate contains a register storing addresses of the gates it targets. We therefore call such gates Addressable Quantum Gates (AQG). Those address registers are quantum, hence target addresses can be superposed, and so output data may be sent to diferent places, in a superposition. Moreover, addresses can interact with the data and be entangled with it. Thereby, addresses may be sent to other gates in anAddressable Quantum Circuit(AQC), which naturally leads to evolving superpositions of causal orders. That is, in contrast to the models 6, 27 in , 32 [ , 36] that also encompass indeinite causal orders, our model allows for quantum dynamic routing. Furthermore, compar34 ed] w toe[allow for vacuum states and the increased compositionality that follows. Moreover, we express the geometry not through external control qubits, but via address registers placed directly within each gates, which allows for a clearer geometrical layout, in the spirit of process algebras. Besides naturally encompassing indeinite causal orders, the AQC model also extends distributed quantum computing in several aspects. Historically, the search for distributed models of quantum computing has mainly focused on static networks and on classically evolving netw 20]. orks Recently [ , the notion of a Quantum Causal Graph Dynamics (QCGD)5[] has borne the premises of a fully quantum distributed model of computation, where the connectivity of the network is allowed to evolve coherently and ind itself in a superposition. The corresponding mathematical framework 4], ho [ wever, is rather abstract and axiomatic. A model of computation should be constructive. This is the case of the hands-on, bottom up approach presented here: we provide a concrete, composable model of distributed quantum computation featuring local synchronous updates as in the Local model, as well as quantum evolving connectivity in the spirit of classical markovian graph dynamics models [13]. Classically it is well-known that the computing power of distributed algorithms crucially depends on the availability of a unique identiier at18 each ]. Frno omdea[more physical point of view, we may indeed consider that these identiiers, a.k.a., łnamesž are iducial, serving just to describe the network or laying out a coordinate system upon it, when really only the geometry should matter. The limitations brought by this requirement (cf. ACM Trans. Quantum Comput. Addressable quantum gates • 3 ‘anonymous networks’ [16], ‘identiier-oblivious’ algorithms 17] in distribute [ d computing, ‘renaming-invariance’ [3] or ‘covariance’ in the Physics literature) are thoroughly studied here in the context of our model. We remark that the questions of 1) the actual gain over the textbook quantum circuit model brought by indeinite causal orders in general and the quantum switch in particular, and 2) whether the current physical implementations of the quantum switch actually realize this gain, is subject of ongoing scientiic discussions. Perhaps one of the strongest attempts to settle this debate is the notion of the time-delocalized system implementation of indeinite causal order developed in 25, [33]. To some extent, the controversy surrounding this łgainž has to do with how the gain is deined and quantiied. For instance, we could be counting the number of łusagesž of gates as in standard oracle complexity. Likewise, we could be counting the number of łphysical implementations" of gates, supposing that each of them requires much experimental care. It is not obvious that the quantum switch, at least in its current experimental implementations, provides any łusage gainž. It does if we only count as łusagež the number of times the gate is traversed by data, but it is not clear why one should not count those times it is traversed by the łvacuum statež [ 11]. On the other hand, it seems clear that, contrary to standard quantum circuits, these experiments factor out the number of physical implementations of gates. In that sense, our model provides some clariication, because each physical implementation of a gate is in one-to-one correspondence with one addressable quantum gate: the reusing of physically implemented resources is made explicit. We leave for future work question whether AQC implementations of indeinite causal orders correspond to (or help express) time-delocalized implementations. Our contributions are the following: • A novel computational paradigm Ðcalle Addrdessable Quantum Circuits Ð generalizing textbook quantum circuits, so as to make the low of information quantum (Sect. 2). • Showing that this quantum low of information allows for indeinite causal order. We demonstrate this below by encoding the quantum switch and the polarizing beam splitter (Sect. 3). • A restriction of the model so that the actual names used as addresses do not matter beyond the wiring they describe, i.e. ‘disallowing pointer arithmetic’ in the manner of Java... • ...which led us to solve the following linear algebra question as a natural byproduct: say that a matrix acts on the Hilbert space spanned by|���...⟩, |���...⟩, |���...⟩ in a way that commutes with renaming � into� etc. What is this matrix allowed to do? Can it still create superpositions? We provide a full, constructive characterization of such łnameblindž matrices. Whilst strongly structured, they still admit non-trivial behaviors. It is our main technical contribution (Sect. 4). • The compositionality of the model is formalized (Appendix D). The physicality of the model is discussed with comparison with other frameworks (Section 5). Notations are summarized in Appendix F. 2 THE MODEL Quantum algorithms, whether they are distributed or not, are consist of two steps. Firstly, a quantum circuit is operated on the input quantum data Ð possibly in an iterative fashion. In the second step, the resulting quantum state is measured.Addressable Quantum Circuits(AQCs) represent a novel description of the irst part. More precisely, each iteration of an AQC is one step of propagation of quantum data in the circuit, where gates can be applied in a superposition. Such physical locations in the laboratory are abstracte sectors in d into the AQC formalism. Each sector is uniquely identiiedaddr by an ess taken in a inite set AÐsee Def. A.1. Several sectors can be grouped together to formgates, which determine the level of granularity at which łlocalž gateunitar operators y are applied. These concepts are formally introduced in this section. To establish familiarity, we encode the usual Bell state creation circuit as an AQC. This requires four sectors withAaddr = {esses 1, 2, 3, 4} Ðsee Fig. 1a. ACM Trans. Quantum Comput. 4 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron 1 2 3 4 |0⟩ |00⟩+|11⟩ |0⟩ (a) Bell state creation as a textbook quantum circuit 2 3 H 4 1 I I I (b) Bell state creation as an addressable quantum circuit Fig. 1. Dashed boxes represent sectors. (a) Textbook quantum circuits require a background layer that implies a time ordering, here shown explicitly in light purple. (b) The AQC formalism frees the information flow from the background surface. Each sector has a target space, holding a target address, as represented by the arrows. Addresses could have been taken in any other integer set instead. 2.1 Addresses and sectors In the following H denotes the Hilbert space whose canonical orthonormal basis {|�⟩} is. To each address we X �∈X associate a sector, i.e. a connectable device which stores quantum data. The main novel feature of our formalism is its ability to manipulate and superpose addresses, and thus the connectivity between sectors. To this end, each sector has a target address space H to determine where the output data is to be sent. Additionally, it can store other addresses in its stored address spaces H . By locally acting on these spaces we may shule addresses, possibly into a superposition. Deinition 2.1 (Target address space, stored address space).Let the set of addressesA be a inite set of integers. ≤1 ? A target address space is a Hilbert space H , where T ≡ {�|� ∈ A } = � is the set of words onA of length at most 1. In contrast, basis states of stor a ed address space H can contain multiple addresses, but each address at most once. Thus,H is a Hilbert space speciieW d by≡ {� = � ···� |� ∈ A,� ≠ � ∀�, �} = A , the set of W 1 � � � � words on A with all diferent letters. −� Example 2.2. WithA = {2, 3}, the vector (|2⟩ + � |3⟩ + |3 2⟩ + |2 3⟩)/2 is a valid stateHof . For the Bell state creation circuit, just like for any textbook quantum circuit encoding, the stored address spaces are unused and the target address spaces remain ixed. Specifying the target addresses for each sector makes the underlying background layer redundant: we might just as well dismantle the circuit as in Fig. 1b. In other examples with dynamically evolving wirings, the circuit may even be in a superposition of several arrow conigurations Ðsee e.g. Fig. 4b. Such superpositions of wirings induce superpositions of orders of applications of gates on the quantum data stored inH : Deinition 2.3 (Data space).Let D be a inite set of possible data values. The set of words on data of length at ≤� most � is denoted byQ = D . SinceD is inite, soQis . The Hilbert spaceH is referred to as data a space. ACM Trans. Quantum Comput. Addressable quantum gates • 5 Each sector contains two storage spaces : one for the input and one for the output, and both can store addresses and data. Each of these subspaces may be empty, in which case we denote its state�.by Sectors with empty data spaces correspond to vacuum states [11]. The purpose of such output and input spaces is explicitated in Sec. 2.3. Deinition 2.4 (Input and output space, sector space).An input (resp. output) spaceis a Hilbert space H (resp. H ) of the formH ⊗H . A sector space is a Hilbert space of the form H = H ⊗H ⊗H . To each address O W Q S T I O � ∈ A is associated a sector spaceH . We write basis states of input (resp. output) spaces|�,as �⟩ (resp. |�,�⟩ ), where � ∈ W and � ∈ Q. Basis I O ′ ′ states of a sector may be expressed as|�⟩ |�⟩ |�⟩ |� ⟩ |� ⟩ ∈ H ⊗ H ⊗ H ⊗ H ⊗ H or, by T W Q W Q T I O I O � � � � ′ ′ reordering the tensor factors as|�⟩ |�⟩ |� ⟩ |�⟩ |� ⟩ ∈ H ⊗H ⊗H ⊗H ⊗H Ðsee Fig 2. T W W Q Q T I O � O � � � � I O H H W W � � H H Q Q Q � � Fig. 2. (a) A sector. (b) Stored addresses vs. quantum data. (c) Input vs. output spaces. When all output (resp. input) spaces are empty, we only represent the input (resp. output) spaces, as in Fig. 4b. Example 2.5. WithA = {1, 2, 3, 4} as in Fig. 1a andQ = {00, 01, 10, 11,�}, the states |�,10⟩, |3,�⟩ and |23, 11⟩ are basis states forH andH . E.g. |�,11⟩ + |2,�⟩ and |2, 11⟩ are orthogonal. I O Moreover, |3⟩ |2, 01⟩ |�,�⟩ is a basis stateH of . T I O The state of the quantum system at any point of its evolution is described by a sum of tensor products of states of each of its sectors. E.g. in the beginning of the execution of the Bell state creation circuit Ðsee Fig. 1a, the quantum system is in the state|� ⟩: 1 1 1 � � � � |� ⟩ = |2⟩ ⊗ |� , 00 ⟩ ⊗ |� ,� ⟩ (sector 1) T I � 2 2 2 � � � � ⊗ |3⟩ ⊗ |� ,� ⟩ ⊗ |� ,� ⟩ (sector 2) T I � (2) 3 3 3 � � � � ⊗ |4⟩ ⊗ |� ,� ⟩ ⊗ |� ,� ⟩ (sector 3) I � 4 4 4 � � � � ⊗ |�⟩ ⊗ |� ,� ⟩ ⊗ |� ,� ⟩ (sector 4) I � 2.2 Addressable Gates A gate is composed of multiple sectors, and thus can receive information from and send information to multiple sources and destinations. This grouping of sectors into gates deines a notion of locality for the evolution: during a łscattering stepž a gate acts upon its constituent sectors with a local unitary. Deinition 2.6 (Gates, Gate Operators).A gate � is a (non-empty) subset of a set of addressesA, and the set of � � gates G is a partitionAof . The gate space of a gate� consists of|�| sectors and is given byH = H . A �∈� S � � � gate operator on � ∈ G is a unitar�y : H → H which preserves the addresses of the target and stored spaces, ′ ′ ′ ′ ′ i.e⟨.� � | � |� �⟩ ≠ 0 implies that � has the same letters as�, where � and � (resp. �,� ) list all target and stored addresses (resp. all data) in sectors�.of ACM Trans. Quantum Comput. 6 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron In general, gates act as the identity on the empty state �. The gate operators of the Bell state creation circuit are given by {1} {4} {2} {3} � = � = � , � = �((� ⊗ �) ⊗ � ), � = �(Cnot ⊗ � ), (3) I O I O where � swaps the input and output systems. Note that neither data nor addresses are manipulated in se 1ctors and 4, yet they are required to compose this AQC with other AQCs Ðsee Sect. D. The overall state space of an AQC is the tensor product of its sector spaces together with an additional global condition: to guarantee the reversibility of the transport step that will be deined below, we require that each address appears at most once. Deinition 2.7 (Skeleton, Addressable Quantum Circuit). A skeleton � is a tuple(A,G,Q,�) where: • A is the set of addresses, • G is the set of gates, • Q is the set of data Ðconsisting of words on data of length at �most , • � is a function associating a gate operator � to each gate � ∈ G. This speciies the sector spacesH as = H ⊗H ⊗H ⊗H ⊗H . S T W Q W Q The circuit Hilbert spaceH is deined as H restricted to superpositions of basis states where addresses �∈A appear at most once. An Addressable Quantum Circuitis a tuple� ,(|�⟩) that speciies both the dynamics and the current state, i.e�. is a skeleton and|�⟩ is a state ofH. For example, consider the skeleton of the Bell state creation circuit shown in Fig. 1b. It is A = speciied by {1, 2, 3, 4},G = {{1},{2},{3},{4}},Q induced byD = {0, 1} and � = 2, and � as in(3). In Ex. 2.9 below we choose the initial state of (2). Reordering tensor factors as above, we|�obtain ⟩ = |2, 3, 4,�⟩ |00,�,�,�⟩ |�,�,�,�⟩ . T I O 2.3 Evolution The overall evolution alternates a scattering step during which the gate operators are applied to their respective gates, and a transport step that swaps the output space of each sector with the input space of the sector it targets. The evolution is unitary i.e. it does not involve measurements. O I O I � � � � ′ ′ ′ ′ |�⟩ |� ⟩ |�⟩ |� ⟩ |�⟩ |�⟩ |� ⟩ |� ⟩ |�⟩ |�⟩ |�⟩ |�⟩ ′ ′ ′ ′ |�⟩ |� ⟩ |�⟩ |�⟩ |�⟩ |� ⟩ |� ⟩ |� ⟩ (a) Sectors�and �before the transport step. (b) Sectors�and �ater the transport step. Fig. 3. Efect of the transport step upon two connected sectors Ðsee example A.2. Here and elsewhere in the paper arrows represent the content of each target space. If the state of the target space is a superposition of multiple addresses, one arrow points to each target. Deinition 2.8 (Evolution).An addressable quantum circuit ((A,G,Q,�),|�⟩) evolves in one time step into the ′ ′ addressable quantum circuit ((A,G,Q,�),|� ⟩), where |� ⟩ = � |�⟩ with� = �� and: � � Scattering � is the application of� , i.e. the gate operators� are applied simultaneously on their corre- sponding gate spaces. ACM Trans. Quantum Comput. Addressable quantum gates • 7 Transport � is a permutation of basis states, extended linearly H. The to permutation maps synchronously each � � � � � � triple of the form |�⟩ |�⟩ |�⟩ to|�⟩ |�⟩ |�⟩ , leaving the rest (of the basis state) unchanged. That is, the T O T O I I � � � � � � � � � � transport step maps a basis state|�⟩ |� ⟩ |� ⟩ ⊗ |�⟩ |� ⟩ |� ⟩ ⊗ |�⟩ to |�⟩ |� ⟩ |� ⟩ ⊗ � � T � I O � �∉{�,�} T � I � T I O � � � |�⟩ |� ⟩ |� ⟩ ⊗ |�⟩ . Colloquially, when Se �targets ctor Sector �, �’s output space is swapped � � �∉{�,�} T I O with�’s input space Ðsee Fig. 3. The necessity of the requirement that each address appears at most once becomes clear now: it is essential for the transport step to be well-deined by avoiding that a sector is targeted by more than one other sector, as the output space of a sector�are swapped with the input space of the sector targeted�by . The addresses stored in output and input spaces, referencing some future sector that would be addressed later, low throughout the system just as the quantum data does. It is only required to store in input or output spaces the addresses of the sectors that will be addressed by a quantum superposition of diferent sectors. Example 2.9. Let us describe step-by-step the Bell state creation circuit of Fig. 1. We drop the stored address space which are always empty. In Ex. A.3 we further break down the evolution� into and � . The blue and red terms (and, later, arrows Ðsee Fig. 5) are superposed, and get entangled: |2, 3, 4,�⟩ ⊗ |00,�,�,�⟩ ⊗ |�,�,�,�⟩ T I O −→ |2, 3, 4,�⟩ ⊗ |�,00,�,�⟩ ⊗ |�,�,�,�⟩ T I O −→ |2, 3, 4,�⟩ ⊗ |�,�,00,�⟩ + |�,�,10,�⟩ ⊗ |�,�,�,�⟩ T I I O −→ |2, 3, 4,�⟩ ⊗ |�,�,�00 , ⟩ + |�,�,�11 , ⟩ ⊗ |�,�,�,�⟩ � T I I O −→ |2, 3, 4,�⟩ ⊗ |�,�,�,�⟩ ⊗ |�,�,�00 , ⟩ + |�,�,�11 , ⟩ (∗) T I O O −→ |2, 3, 4,�⟩ ⊗ |�,�,�,�⟩ ⊗ |�,�,00,�⟩ + |�,�,11,�⟩ T I O O ··· The inite execution of usual circuits corresponds to a inite sequence of iterations in the otherwise potentially ininite evolution of AQCs. E.g. in order to match the corresponding textbook circuit, the AQC above needs to be stopped after step (∗). 2.4 Composability of AQC The fact that the connectivity of gates is soft-coded in the AQC model, leaves room for several ways of composing AQCs. In Appendix. D we propose formal deinitions for: Parallel composition of AQCs, corresponding to executing them in parallel without interaction. Concatenation of AQCs, corresponding to successively applying them to the quantum data. Connection of AQCs, alllowing for a more general connectivity without assuming an intrinsic (temporal) order between AQCs. The last of these even allows for indeinite causal order. For now let us show how indeinite causal order may happen within one AQC. 3 WHAT CAN IT DO? Using the Bell state creation circuit as a guiding example, we illustrated how textbook quantum circuits can be implemented in this framework. We argued that textbook quantum circuits only require hardwired one-sector gates in the sense that the connectivity of the graph is static and deinite H is , i.e in . a ixed basis state and H andH are empty. W W � � ACM Trans. Quantum Comput. 8 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron As argued in the introduction, there exist physical devices that allow for superpositions of causal orders. These devices lie beyond the scope of hardwired circuits, in that they cannot be described by the textbook circuit framework without extending the workspace or waiving knowledge about the internal workings of the gates by using all-encompassing gates. We now describe how such causal superpositions arise naturally by superposing addresses in AQCs. 3.1 The quantum switch The quantum switch described (1) inapplies unitaries � and� to � qubits in a superposition of causal orders that depends on a control qubit Ðsee Fig. 4a. We can encode Switch as the AQC of Fig. 4b, wherA e = {1, 2, 3, 4, 5, 6}, ≤� +1 G = {{1},{2, 5},{3},{4},{6}}, and Q = {0, 1} contains� controlled qubits plus one control qubit. The gates {3} and {4} apply unitary operators � and � to the � controlled qubits, whereas the gate {2, 5} implements the quantum switch itself. 1 1 2 5 As initial state we cho|�ose⟩ = |2⟩ |��⟩ |345⟩ |6⟩ , where |�⟩ = � |0⟩+ �|1⟩ ∈ H denotes the control 0 D T Q W T � � qubit and|�⟩ are the � controlled qubits. All non speciied spaces are empty, i.e. they ar|e�⟩in . state 1 3 5 1 2 3 5 6 � � � ��� 1 . . . . � � ��� 0 . . |�⟩ QS 2 4 6 . . . . � � � . . |�⟩ � � � (a) Textbook-like representation of the uantum Switch.(b) AQC representation of the uantum Switch during its execution. Red and blue data and targets are superposed. Fig. 4. Superposing causal orders by superposing addresses. Let us explain the behavior of this AQC, see Fig. 5. For the sake of brevity, when specifying scatterings by their action on basis states, non-represented spaces are understood to be empty, i.e. in�.state Moreover, scatterings are understood to act as the identity on unspeciied basis states.2Seinitially ctor contains addresses {2,5} 3, 4 and 5 as output stored addresses. When the data enters this sector, the gate operator� superposes 2 2 the addresses 3 or 4 in the target space (Fig. 5a) according to the control qubit,|�⟩e.g.|345⟩ |��⟩ ↦→ T W Q O I 2 2 2 2 2 2 � |3⟩ |45⟩ |�0⟩ + �|4⟩ |35⟩ |�1⟩ . It is then transported to sectors3 (resp. 4) as shown in Fig. 5b. T W Q T W Q O O O O There, � (resp. � ) is applied, and the target space of the respective sector is illed by the irst address of the stored address space (Fig. 5d). The data continues its journey, and � (resp. � ) is applied in Se4ctor (resp. 3). The two branches meet in Sector5 (4b). The data halts here, while the target addresses fold back and the quantum switch reverts to its former, non entangled state. Then all data low to Se 6. ctor The mathematical details are found in Appendix A.2. The addresses low back within the AQC from steps 5 to 8. This means that the addresses low from the input space of a targeted sector to the output space of a targeting sector. These steps are essential to guarantee that the data can interfere outside of the AQC, i.e. that no intrication remains between quantum data and the quantum switch. It is crucial to note that one cannot initialize this AQC with the addr 6,ess which of Seis ctoralways accessed from Sector5, in the input or output spaces of Sector 2, since otherwise the AQC would still be entangled with the output data after the addresses lowed back. ACM Trans. Quantum Comput. Addressable quantum gates • 9 {3} {4} The gate operators � and � act both on a single sector spaceH as they are one-sector gates. Both can be decomposed into 1) a gate acting onH handling the swaps between the subspaces of the sector � ( in S 34 ≤� +1 Appendix A.2.1), and 2) a gate applying � or � on the respective data spaceH , where Q = Q . The Q O 3 4 subsystems whose causal order is in superposition are therHeforand e H , see also25 [ ]. In other words, the Q Q O O gate applies � (or � ) on a state consisting 0ofqubits or� + 1 qubits.� (or � ) is any unitary acting�onqubits as it does not take into account the irst qubit, i.e., the control qubit that was used in{2the , 5}gate . We refer the reader to Appendix A.2.1 for details. 3.2 The polarizing beam spliter In a Polarizing Beam Splitter (PBS), birefringent material separates an incident beam according to its polarization Ðsee Fig. 6a. A transmitted photon moves toward a device denoted by A that rotates the polarization angle of the light, and after that, moves toward a similar device denoted by B that rotates the polarization in a diferent way. By using two PBS, the relected version of the photon encounters B irst, then A. The end result of the polarization in this case is diferent. There are two quantum paths: either A occurs before B, or B occurs before A, yielding an indeinite causal order. Indeinite causal orders are related to the time order of the evolution of the underlying quantum system. In the irst case, A causally inluences B so that if A had not occurred, then B’s input and output would be totally diferent. Conversely, in the second case, B causally inluences A. PBS are thus used in the literature to implement indeinite causal 7, 12or , 21 ders ], as [ in PBS the physical location of quantum data is itself quantum. Therefore, AQCs are well-suited to represent such devices, unlike textbook circuits which are ignorant towards locations. Here, we consider a PBS where horizontally polarized photons (� ) pass through the bifringent material, while vertically polarize(�d) ones are relected without phase shift. Photons as the physical carriers of data are represented by Fock states with a inite number of particles, and are further distinguished by their polarization. We represent this PBS as an AQC((A,G,Q,�),|� ⟩), withD = {0 , 1 , . . .� } × {0 , 1 , . . .� } for some 0 � � � � � � ≤1 integer� being the total number of photons present in the cirQcuit, = D , A = {1, . . ., 8}, and G = {1,2,3,4} {{1, 2, 3, 4},{5},{6},{7},{8}}. The irst gate� corresponds to the PBS itself, as shown in Fig. 6a. Sectors 5− 8 provide the context in which the the PBS is evolving and thus play the same role as the 1 and Sectors 4 of the Bell state creation AQC and the Sectors 1 and 6 in theSwitch AQC. In this AQC, photons can enter the {1,2,3,4} PBS from any direction. The gate operator � makes them travel to the right sector depending on their polarization (Fig. 6a). They exit or enter the PBS during the transport step (Fig. 6b). � �−4 � We choose the initial state |� ⟩ = |�− 4⟩ |�⟩ |� ⟩ where the |� ⟩ represent entry photons Ðsee 0 � � T T �=5 Q Fig. 6b, or a superposition of such |� ⟩. The content of the target spaces entails that each entry of the PBS may communicate only with the sector in front of it. {1,2,3,4} The gate operator of the PBS gate� acts on general states of the Sectors 1 to 4 as 4 4 Ì Ì {1,2,3,4} � : |�+ 4⟩ |� ⟩ |� ⟩ ↦−→ |�+ 4⟩ |� ⟩ |� ⟩ , (4) T � � � � T �(�) ℎ(�) � � �=1 �=1 where � (resp. ℎ) is the function associating to a sector’s vertical (resp. horizontal) polarization the sector indicated in Fig. 6a: �(�) = �mod 2+ 1+ 2⌊�/2⌋ and ℎ(�) = (�+ 1) mod 4+ 1. ACM Trans. Quantum Comput. 10 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron 1 3 5 1 3 5 � � � � � � � (0+1) � � � � � 2 4 6 2 4 6 345 � � 345 � � O O � � � � (0+1) � � (a) Step 1|� ⟩ (b) Step 2|� ⟩ = �� |� ⟩ 0 2 0 1 3 5 1 3 5 � � � � 45 � � � � � � � 0 2 4 6 2 4 6 � � � � 45+35 35 � (0+1) � � � � 1 � (c) Step 2.5:|� ⟩ = �|� ⟩ (d) Step 3|� ⟩ = �� |� ⟩ 2.5 2 3 2 Output spaces. 1 3 5 1 3 5 � � � � � ��� 1 � �� 1 � � � ��� 0 2 4 6 2 4 6 � � � � � � �� 0 � � � � (e) Step 4 (f) Step 5 1 3 5 � � 6 1 3 5 5 6 ��� � 1 ��� ��� ��� 2 4 6 2 4 6 � � � � 5 � � � � � 0 1 (g) Step 6: Output spaces. (h) Step 7: Output spaces. 1 3 5 1 3 5 � � � � � ��� ��� 1 � � � � ��� ��� 0 2 4 6 2 4 6 � � � � 45+35 345 � � � � � 0+1 (i) Step 8: Output spaces. (j) Step 8.5: Output spaces. 1 3 5 � � � � � � 2 4 6 345 � � ��� 1 � � ��� 0 (k) Step 9 Fig. 5. Each step corresponds to one application of the global evolution operator � = ��. The step�.5 for any integer� corresponds to applying the operator� to the state of step �. The control qubit|�is⟩ = � |0⟩ + �|1⟩. Blue represents a scalar coeficient of� before the basis state, red represents a coeficient�of and black represents1. When nothing is specified in caption, only input spaces are represented, whereas "Output spaces" in caption indicates that only the output spaces are represented. AO in subscript (as in Figs. 5a, 5b, and 5k) indicates that a specific element is in the output space. ACM Trans. Quantum Comput. Addressable quantum gates • 11 2 6 � � � � 5 1 3 7 � � � � 1 3 � � � � � � 5 7 � � (a) Polarizing Beam Spliter (b) The PBS AQC, represented with addresses around it Fig. 6. � and � indicate dataspaces corresponding to photons of horizontal (resp. vertical polarization). The dashed square represents the multi-sector PBS gate. ACM Trans. Quantum Comput. 12 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron 4 RENAMINGS So far, in our model a single arbitrarily chosen integer serves both as a name and as the address of a sector. Without further restrictions, this can lead to physically odd behavior: For example, one easily constructs gate operators whose action is controlled by the address stored in the target address space, see Fig. 7. This is quite strange, since in our model we wish to think of sectors merely as diferent physical locations and of addresses as just encoding the underlying geometry, i.e. the wirings of the gates. A standard way to implement this independence is to require invariance renamings under, i.e. under permuta- tions of addresses. This is akin to requesting identiier-obliviousness in distribute 17]. W dealgorithms call a gate[ operator renaming-invariant , or simply nameblindif it commutes with all such permutations. For instance, after {1} renaming� ↦→ � + 100 mod |A|, the gate operator � that was applied at location {1} is applied at location {101 mod |A|}. Thus, as renamings reshule łphysical locationsž and their associated gate operators, renaming invariance is a global condition. In Sect. 4.1, after a detour via a larger Hilbert space in which physical locations and their addresses are explicitly separated, we deduce an equivalent but local condition on gate operators. 2 2 � � 1 1 � � � � 3 3 � � � � Q Q � � � � � � (a) When Sector1 targets Sector 2, it applies� . (b) When Sector1 targets Sector 3, it applies� . Q Q � � Fig. 7. Example of a gate operator that applies diferent operators depending on the targeted sector and is hence not łrenaming invariantž. Formally this operator could be writen as|2⟩⟨2| ⊗ � + |3⟩⟨3| ⊗ � . T Q T Q � � A practical advantage of working with nameblind gate operators is the reduced number of cases to be speciied. For instance, a gate operator manipulating 6 addresses acts over 6!× 7 basis states of the address spaces if the target space is empty (ordering the six addresses and separating them amongst input and output) 6×plus 6! such basis states if the target space is occupied, which gives a9360 total Ðseeof Appendix A.1. If the gate operator is nameblind, it suices to specify its behaviour 13 basis on states (ixing an order of the addresses and distributing them target, input and output) cases to specify it entirely. Renaming invariance is thus a very restrictive condition, and one may wonder whether it leaves any room for superposing addresses at all. Surprisingly, it does. We will fully characterize the structure of nameblind gate operators in Sect. 4.2. An instructive analogy to renaming invariance from daily life is that of postal delivery, where a letter has to be delivered to a certain house with some house number. This house number is fairly arbitrary and might change due to bureaucratic processes. To guarantee the success of the mailman, when that happens, one has to make that change consistently, i.e. also on the letter and even in the phone books. In other words, if only the house number changes, the letter will not arrive. Below, we further distinguish renamings into łinternalž and eł xternalž ones w.r.t. a gate. Such renamings can be thought of as changing the house number only in a particular street and everywhere except in that street, respectively. We remark that the idea of invariance under renamings of pointers is standard in the realm of classical programming languages. For instance, it is standard to consider pointers (or references) as opaque in high-level programming languages such as Java, or OCaml. From a semantics perspective, one way to model such opaque ACM Trans. Quantum Comput. Addressable quantum gates • 13 names is to use nominal sets: a variable that is precisely invariant under renaming. Unlike for nominal sets, the set of names in the current setting is inite. 4.1 Named AQC In the formalism of AQC we use addresses in two distinct ways, with two diferent notations. Take for instance � � � � the state of a single sector |�⟩ = |�⟩ |�⟩ |�⟩ . On the one hand, addresses are łphysical locationsž. This is T W Q denoted by the superscript�(think of it like a house). On the other hand, addresses are also used to target the low of information. Those are�the (think of it like the address of another house on an envelope) �and (think the of it like an address book from which the gate operator can choose). These are denoted as states of certain registers. In order to discuss renamings in the AQC context, we need to carefully separate the two uses of addresses, and put them on an equal footing. We achieve this by extending the Hilbert space by a łname spacež that is induced � � � � � � � byN ≡ T . Letting|�⟩ |�⟩ |�⟩ ↦→ |�⟩ |�⟩ |�⟩ |�⟩ leads to the modiied formalism which we refer to as T W Q T W Q N Named Addressable Quantum Circuit(NAQC) Ðsee B.1. In that larger space, when we rename addresses, we no longer need to modify the order in which the corresponding sectors occur. Renamings act locally upon each sector without shuling them around: Ì Ì � � � � � |��⟩ |�⟩ = |�(�)�⟩ |�(�)⟩ . In other words, superscript�is the physical location (the house) at which� awill gate always be applied, before and after a renaming.|�(�)⟩ is the name of the physical location (the number on the house). Any occurrence of �(�) within some|�(�)�⟩ still points toward the same physical location (address of the house). The identiication between AQC and NAQC thus extends to � � � � � � � |�⟩ |�⟩ |�⟩ ⇐⇒ {|�(�)⟩ |�(�)⟩ |�⟩ |�(�)⟩ | � is a renaming } (5) T W Q T W Q N i.e. each AQC� is associated to the equivalence class NAQCs whose renaming into the canonical name and then projection in the AQC space yields � . Deinition 4.1 (Renaming and nameblind NAQC). A bijection ovA er is callerdenaming a . It naturally extends pointwiseW to and T , and linearlyHto ,H , and to any Hilbert space by acting non-trivially only on its W T address (and name) spaces. We call a renaming � external to a gate� if it acts trivially �, i.e.on if � ∈ � ⇒ �(�) = �, i.e. it only manipulates external addresses � ∈ A\�. Moreover, we call an NAQC((A,G,Q,�,N),|�⟩) nameblind if� commutes with every renaming �, i.e. if �� = ��. � � Nameblindness can be tested locally on each gate by demanding ∀� ∈thatG,�� = � �. This allows us to lift the notion of nameblindness back to AQCs: Theorem 4.2 (Nameblind AQC). Equivalence classes of nameblind NAQCs w.r.t. renaming are isomorphic to � � AQCs ((A,G,Q,�),|�⟩) for which for all� inG, and for all renamings� external to �, � � = �� . Such AQCs are therefore referred to as thenameblind AQCs. Summarizing, an AQC is nameblind if its gate operators commute with all external renamings. Next, we show that such gate operators are made of blocks of ‘nameblind matrices’, i.e. matrices that commute with all renamings, and study the structure of these. 4.2 Nameblind matrices Gate operators � of nameblind AQCs, calle nameblind d gate operators, manipulate all external addresses in the same manner, yet may do so in a non-trivial way. For instanc � may e, choose to swap one for the other, or not, in ACM Trans. Quantum Comput. 14 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron a superposition, as shown by the general form of nameblind unitary matrices over two addresses: cos(�) ±�sin(�) �� � (�,�) = � ±�sin(�) cos(�) understood as acting overSpan{|� �⟩ ,|� �⟩} with any�,� ∈ A, � ≠ �. Note that the data register of the gate space can readily be used to control these angles, e.g. we could �|�let �⟩ = (� (� ,� ) |�⟩) ⊗ |�⟩: + � � {2,5} Example 4.3. The action of the switch gate � in the cases shown in Fig. 5c is describ�ed(�by,� ) |�⟩ + � � with control angles: � = � = 0 when the control qubit �in is 0, and� = � = when the control qubit �in is � � � � 1, followed by a swap of input and output data spaces. Keeping this in mind, we now turn our attention towards matrices � addr overesses, which commute with all renamings. Such matrices act on the vector space whose canonical basisis identiied with the words of length � on the alphabet{1 . . .�}, i.e�. addresses between 1 and �. Moreover, we sort this canonical basis in ascending lexicographic order,{i.e 1 2·.··(� − 1) �, 1 2···� (� − 1), . . ., � (� − 1)··· 2 1.} Theorem 4.4 ((�,�)-nameblind matrices). Matrices on states containing all � addresses which commute with all renamings, i.e(.�,�)-nameblind matrices , are of the following form: � � � � � � � � � � � . . . 1 2 1 3 2 1 © ª � � � �� � � �� . . . ­ 1 1 2 1 1 ® ­ ® �� � �� � ­ 1 1 1 ® ­ ® ­ ® �� � � �� � ­ ® 1 2 1 1 2 ­ ® ­ ® ­�� � � . ® 1 2 3 ­ ® « ¬ where the blocks act on �− 1 addresses, � is any(�− 1,�− 1)-nameblind matrix,� is the renaming�↔ �+ 1, and � (see Sect. C.3) commutes with� (see Sect. C.1) for each�= 2, 3, ...,� − 2. By forcing the partially-nameblind� matrix to be nameblind, inductively so, one obtains a convenient subfamily of(�,�)-nameblind matrices, built from exactly two smaller matrices of the same subfamily. Even though they are of size�!× �!, these have onlyO(2 ) degrees of freedom. This makes these matrices easy to construct in practice. Corollary 4.5 (Pure nameblind matrices). A pure nameblind matrix on� addresses is a matrix of the following form : � � � � � � � � � � � . . . 1 2 1 3 2 1 © ª � � � � � . . . ­ 2 ® ­ ® � � � � ­ 1 ® ­ ® ­ ® � � � � � ­ 1 2 2 ® ­ ® ­ ® � � � � . ­ ® 1 2 3 ­ ® « ¬ where � and � are pure nameblind matrices on(� − 1) addresses and the � are as in Thm. 4.4. All pure nameblind matrices are also nameblind. Our main goal is to characterize gate operators, which do not necessarily act on the full address space of an AQC. As gate operators never create nor suppress addresses, we can consider separately all lengths of address ACM Trans. Quantum Comput. Addressable quantum gates • 15 |�⟩ |1�⟩ |�⟩ , |�⟩ |�1⟩ |�⟩ , |�⟩ |�⟩ |1⟩ , |�⟩ |1⟩ |�⟩ , T I O T I O T I O T I O |�⟩ |�⟩ |1�⟩ , |�⟩ |�⟩ |�1⟩ , |1⟩ |�⟩ |�⟩ , |1⟩ |�⟩ |�⟩ , T I O T I O T I O T I O |�⟩ |1⟩ |�⟩ , |�⟩ |�⟩ |1⟩ T I O T I O {1} Fig. 8. Consider a gate operator� acting over one external address� plus its own address. Its state space can be organized into the above ten ‘nameblind’ subspaces which should be interprete � d=asSpan {|�⟩ |1�⟩ |�⟩ }, �∈A\{1} T I O � = Span {|�⟩ |�1⟩ |�⟩ }, etc. Knowing in which of these subspaces � we are, � fully determines a basis state. 2 � T I O �∈A\{1} That is, basis states can be identified with the tuple (� ,�). All states within one of such subspaces evolve in the same manner {1} under the action�of . Therefore, it sufices to describe the action of the gate operator on a general|�state ⟩ to describe its action on all the true basis states |� ⟩ ⊗ |�⟩. words. For instance, withA = {1, 2, 3}, we consider independently the action of a gate operator on words of length 2, i.e. on the subset{12, 21, 13, 31, 23, 32} Let � be a nameblind matrix acting on wordsA in of size� ≤ � = |A|, meaning that� is a nameblind matrix on a set of external addresses, some of which may not be present in the basis state. Such matrices, which we additionally require to neither create nor suppress addresses are calle (�,� )-nameblind d a matrix. They are characterized as follows: Proposition 4.6 ((�,� )-nameblind matrices). Let � be a (�,� )-nameblind matrix. When sorting the basis irst by which addresses are present and then by lexicographical order�, can be written as � where � is a A ⊂ A (� !)-dimensional(�,� )-nameblind matrix as in Thm. 4.4. 4.3 Gate Operators of a nameblind AQC In practice, gate operators do not manipulate basis states solely composed of addresses. Basis states also contain data, separators between (T , I and O) spaces and between the diferent sectors. Moreover, recall from Thm. 4.2 that the gate operators of a nameblind AQC need only commute with external renamings. Still, they can be organized as blocks of nameblind matrices acting on well-identiied subspaces, as in Fig. 8, 9 and 12. A nameblind gate operator � can be written using only blocks of the form given by Thm. 4.4: 2|�| • First, we decompose the large gate space into |� | subspaces for each possible basis state of the dataspace. For each couple of basis states|� (⟩ ,|� ⟩) ∈ H we denote � the block of� which maps states with 0 1 � →� 2|�| 0 1 data |� ⟩ to states with data|� ⟩. 0 1 • Then we regroup states according to their number of external addresses � and the set of internal addresses A contained in their address spaces. Fig. 8 exempliies the subspace deine A d=by{1} and � = 1. ��� ��� Since both parameters are preserved by� and �, any � is block-diagonal in this basis. � →� 0 1 • By also ixing positions � and� for internal and external addresses, we can deine even smaller subspaces ��� �� preserved by renamings (but not by S). The blocks corresponding to this subspaces(�ar ,�e−|�|)-nameblind matrices (Prop. 4.6) Ðsee Appendix C.5 . They are illustrated in Fig. 9b and correspond to the diferent subspaces described in Fig. 8. • Finally we know that these (�,� − |�|)-nameblind matrices are block diagonal over subspaces deined by a set of� external addresses (Prop. 4.6), and only contain the same (�,� )-nameblind matrix in each block (in Fig. 9, each blo�ck denotes such a matrix). Indeed, these operators act the same way whatever the �,� names of external addresses are, because we made such addresses indistinguishable. These results are proved in full detail in Appendix C.5 together with Prop. 4.7, which states formally that a gate operator can be decomposed into(�,�)-nameblind matrices for some �. ACM Trans. Quantum Comput. 16 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron Proposition 4.7 (Decomposition of gate operators into (�,� )-nameblind matrices). Let � be a gate operator on a set of addressesA. Suppose that it commutes with all renamings on external addresses. Consider any words on quantum data � and � , internal addressesA ⊆ � with positions� and � , external addresses 0 1 ��� ��� ��� 1 2 A ⊆ A\� with positions� and � . The action of� between states corresponding to these parameters �� �� �� 1 2 � , is a(�,� )-nameblind matrix, where� = |A |. �� A ,A ,� →� ,� →� ,� →� ��� �� 0 1 ��� ��� �� �� 1 2 1 2 � 0 0 � 0 0 � 0 0 1,1 1,2 1,� © ª . . . ­ . . . ® 0 . 0 0 . 0 . . . 0 . 0 ­ ® ­ ® 0 0 � 0 0 � 0 0 � ­ 1,1 1,2 1,� ® ­ ® � 0 0 � 0 0 � 0 0 ­ 2,1 2,2 2,� ® ­ ® . . . ­ ® . . . 0 . 0 0 . 0 . . . 0 . 0 ­ ® � 0 . . . 0 1 ­ ® 0 0 � 0 0 � 0 0 � © ª ­ 2,1 2,2 2,� ® � = ­ ® 0 � . . . 0 � ­ 2 ® ­ ® ­ ® ­ ® � = � →� . . . 0 1 . . . . ­ ® ­ . ® . . . . . . . . ­ . . . . ® ­ . . . ® ­ ® ­ ® 0 0 . . . � « �(�,� ) ¬ ­ ® ­ � 0 0 � 0 0 � 0 0 ® �, 1 �, 2 �,� ­ ® ­ . . . ® . . . ­ . . . ® 0 0 0 0 . . . 0 0 0 0 � 0 0 � 0 0 � « �, 1 �, 2 �,� ¬ (a) Block � of a gate operator (b) Detailed representation of the blocks � of Fig. 9a. If� corresponds to � →� � � 0 1 subspaces with � external addresses, the� are(�,�)-nameblind matrices. �,� Fig. 9. To each pair of values � ,� in the data space corresponds a block� of the gate operator. This block � 0 1 � →� � →� 0 1 0 1 may be divided into sub-blocks � acting on subspaces having a given set of internal addresses A and a given number of � ��� external addresses� Ðsee Fig. 9a. Non-diagonal sub-blocks are zero because gate operators preserve these parameters. The diagonal sub-blocks are divided into(�,� )-nameblind matrices on more addresses than the ones presentÐsee Prop. 4.6 for details. Those(�,� )-nameblind matrices are then split into(�,� )-nameblind matrices, yielding Prop. 4.7. Example 4.8. In Sect. 3, all gate operators are nameblind. As an example, let us argue that the gate operator of {2,5} {2,5} the Switch � from Sect. 3.1 commutes with any renaming ovA er= {1, 2, 3, 4, 5, 6}. � is controlled by many inputs, therefore proving renaming invariance in all cases speciied in Appendix A.2 would be cumbersome. Instead, we focus on the irst case - the one leading to Fig. 5a. . It explains how states of the subspace K = ′ 2 5 {2,5} {|��� ⟩ |��⟩ |�⟩ ∈ H } evolve: W Q T 2 ′ 2 5 |�⟩ |�� ,��⟩ |�⟩ if� = 0 {2,5} ′ 2 2 5 T O � |��� ⟩ |��⟩ |�⟩ = (6) W Q T 2 O 2 ′ 5 |�⟩ |�� ,��⟩ |�⟩ if� = 1 T O T ′ 2 5 To see that this operator is nameblind, we consider an element of the |���form ⟩ |�1⟩ |�⟩ inK and a W Q T renaming�: 2 2 {2,5} ′ 2 5 2 ′ 5 �� |��� ⟩ |�1⟩ |�⟩ = |�(�)⟩ |�(�)�(� ),��⟩ |�(�)⟩ W Q T T O T {2,5} ′ 2 5 = � |�(�)�(�)�(� )⟩ |�1⟩ |�(�)⟩ W Q T O I ′ 2 2 {2,5} 5 = � � |��� ⟩ |�1⟩ |�⟩ . Q T O I {2,5} Similar calculations for the other cases show the nameblindness � . of 5 RELATED WORKS In the following, we discuss links between our model and other approaches to indeinite causal orders in the literature. ACM Trans. Quantum Comput. Addressable quantum gates • 17 Quantum Causal Graph Dynamics (QCGD).Another approach to represent indeinite causal orders is to shun away from the circuit formalism and take inspiration from cellular automata. The QCGD 5] featur framees work [ quantum superpositions of graphs evolving synchronously according to unitary local rules. Each vertex has a local quantum state and communicates with other vertices via ports. Compared to AQCs, vertices have replaced gates and edges have replaced wires. Like QCGD, our model is able to represent a quantum superposition of diferent graphs (the graphs of connectivity between gates). The interdiction of non-causal evolution in QCGD may appear as contradictory with the sudden appearance of an edge in the AQC between nodes of diferent gates Ð for instance, when an address suddenly goes from the input address space to the target. However, by encoding address spaces into port names, one may simulate this seemingly non-causal edge appearance at the cost of having a larger number of ports. We can therefore encode any AQC into a QCGD (see Appendix E). Quantum circuits with quantum control of causal order One . way is to allow higher-order circuits, with supermaps encoding of quantum control 34],[ in a way that generalizes the quantum switch. All thus far known physically realizable coherent control of orderings can be expressed within this QC-QC formalism. Notice that these supermaps cannot reuse the same black box twice, as causality is not handled as in AQCs. PBS calculus. A second proposal uses a graphical language inspired by PBS to express causal ordering of general, non unitary quantum channels 7,[12]. The PBS diagram formalism 12] is [ a graphical language modeling coherent control of "puriied channels" 7], i.e [ . unitary matrices enhanced with ancillæ from an environment, to represent CPTP maps. It provides completeness theorems for coherent quantum control. This control is obtained by having the PBS as a primitive of this graphical language. Similar to AQC, the physical location of quantum data is itself quantum. However, unlike AQC in the PBS calculus wires are ixed. Routed quantum circuits (RQC).A third idea consists in building a process15the ] which ory [ allows for superposi- tion of paths32[]. RQC [32] is an extension of the quantum circuit formalism which allows for communication in a superposition of paths 11].[ In this work, the authors describe sectorial constraints to study causal decomposition [24] of the used unitaries. In this purpose they partition Hilbert spaces into sectors, over which they describe with a relation Ðcalled a routeÐ which sectors are causally connected. This is reminiscent of our model as each sector’s target may be understood as a speciic sectorial constraint. However the formalism 32] doof es not [ allow for a dynamical rewiring of the circuit. Causal Boxes. A fourth way is to admit superpositions of temporal orders of messages Causal with Boxes [27]. Causality is ensured by enforcing that each new message depends on messages labelled with lower time tags. This allows for implementations of systems as the quantum switch or a the control of an unknown unitary. Our model bears similarity 27],tofor [ instance the input and output spaces of sectors are analogous to the input and output wires of causal boxes. Nevertheless, unlike 27] wher [ e circuits are ixed, our model is inherently bycausal construction, despite the dynamical aspect of the wiring structure. Quantum Shannon Theory with superposition of trajectories. The paper [11] extends the usual Quantum Shannon Theory by allowing trajectories of the information carriers to be superposed. A separation between trajectory and internal quantum information is enforced similar to our separation between addresses and data. If "phase kickback"14 [ ] were to be used to encode supplementary information in the trajectories, they would become part of the message, and the standard Quantum Shannon Theory would be suicient to express the communication protocol. In the AQC formalism, all external addresses are handled in the same way. This ensures that the phase kickback only arises from things such as the number of addresses and their position, but never from their value. 6 CONCLUSION Summary. We introduced Addressable Quantum Circuits (AQC), which consist of łgatesž that are themselves divided into łsectorsž. Each sector contains dataž ł and ładdressesž. The evolution decomposes into two steps. During the ‘scattering step’, each gate applies a local unitary operator over the data and addresses of its constituent ACM Trans. Quantum Comput. 18 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron sectors. During the ‘transport step’, each sector holding an address within its ‘target space’, swaps the content of its ‘output space’ with that of the ‘input space’ of the target sector. We showed how indeinite causal orders and superpositions of paths emerge naturally in this formalism, by encoding the quantum switch and the polarizing beam splitter. Operations that manipulate addresses raised the question of their fundamental nature. If we require addresses to represent purely geometrical data, we must restrict such operations by demanding that they are indistinguishable. Hence our focus on ‘nameblind’ AQCs, i.e. those whose scattering step commute with ‘renamings’ of addresses. Through a detour via the sub-formalism of Named AQC, we derived local conditions on the gates of AQCs for it to be nameblind. The gates must commute with renamings over ‘external addresses’, i.e. those addresses which do not pertain to the gate. We were able to give the general form(�of,�the )-‘nameblind matrices’ (i.e. acting only over lists of addresses and commuting with every renaming) irst, and then show that gates are blockwise decomposable into these. In the appendices we studied composability, and encoding within Quantum Causal Graph Dynamics (QCGD). Altogether this provides a concrete, composable model of distributed quantum computing, featuring quantum evolutions of connectivity in the spirit of classical markovian graph 13], and dynamics a thorough [ understanding of the limitations brought by renaming invariance in the spirit of classical identiier-obliviousness [17]. Perspectives.The structure of nameblind matrices and gates might simplify even further if combined with the unitary condition. Further comparison with related models could also be fruitful: Are AQCs equivalent, in terms of their expressiveness, to quantum channels extended with vacuum states 11]? Could [ an expressive process language be devised that would encompass AQC, including their dynamical 8]? asp Weepr ctsov[ed that each AQC can be simulated by a QCGD, but is the converse simulation always possible? This last question would help us establish a form of completeness of AQCs within in-principle physically realisable dynamics over quantum causal orders. ACKNOWLEDGMENTS We thank Cyril Branciard and Michel Quercia for insightful discussions and Pascal Baßler for carefully reading the manuscript. This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) ś 441423094 and the German Federal Ministry of Education and Research (BMBF) within the funding program quantum ł technologies ś from basic research to marketž via the joint project MIQRO under the grant number 13N15522. This publication was made possible through the support of the ID# 61466 grant from the John Templeton Foundation, as part of the łThe Quantum Information Structure of Spacetime (QISS)ž Project (qiss.fr). The opinions expressed in this publication are those of the author(s) and do not necessarily relect the views of the John Templeton Foundationż. REFERENCES [1] Tameem Albash and Daniel A. Lidar. 2018. Adiabatic quantum computation. Reviews of Modern Physics 90, 1 (2018). arXiv:1611.04471 [2] Mateus Araújo, Fabio Costa, and Časlav Brukner. 2014. Computational Advantage from Quantum-Controlled OrderingPof hys. Gates. Rev. Lett. 113 (2014), 250402. Issue 25. arXiv:1401.8127 [3] Pablo Arrighi, Marios Christodoulou, and Amélia Durbec. 2020. On quantum superpositions of graphs. arXiv:2010.13579 [4] Pablo Arrighi, Amélia Durbec, and Matt Wilson. 2021. Quantum networks theory. (2021). arXiv:2110.10587 [5] Pablo Arrighi and Simon Martiel. 2017. Quantum causal graph dynamics. Phys. Rev. D 96, 2 (2017), 024026. arXiv:1607.06700 [6] Alessandro Bisio and Paolo Perinotti. 2019. Theoretical framework for higher-order quantum Proceethe dings ory.of the Royal Society A: Mathematical, Physical and Engineering Sciences 475, 2225 (may 2019), 20180706. https://doi.org/10.1098/rspa.2018.0706 [7] Cyril Branciard, Alexandre Clément, Mehdi Mhalla, and Simon Perdrix. 2021. Coherent control and distinguishability of quantum channels via PBS-diagrams. arXiv:2103.02073 [8] Esteban Castro-Ruiz, Flaminia Giacomini, and Časlav Brukner. 2018. Dynamics of Quantum Causal Phys. Structur Rev. Xes.8 (2018), 011047. Issue 1. arXiv:1710.03139 ACM Trans. Quantum Comput. Addressable quantum gates • 19 [9] Giulio Chiribella, Manik Banik, Some Sankar Bhattacharya, Tamal Guha, Mir Alimuddin, Arup Roy, Sutapa Saha, Sristy Agrawal, and Guruprasad Kar. 2021. Indeinite causal order enables perfect quantum communication with zero capacityNe channels. w Journal of Physics23, 3 (2021), 033039. arXiv:1810.10457 [10] Giulio Chiribella, Giacomo Mauro D’Ariano, Paolo Perinotti, and Benoit Valiron. 2013. Quantum computations without deinite causal structure. Phys. Rev. A 88, 2 (2013), 022318. arXiv:0912.0195 [11] Giulio Chiribella and Hlér Kristjánsson. 2019. Quantum Shannon theory with superpositionsPof hys.traje Revctories. . A 475 (2019). arXiv:1812.05292 [12] Alexandre Clément and Simon Perdrix. 2020. PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 170) . Prague, Czech Republic, 24:1ś24:14. arXiv:2002.09387 [13] Andrea Clementi, Riccardo Silvestri, and Luca Trevisan. 2015. Information spreading in dynamic Distribute graphs. d Computing 28, 1 (2015), 55ś73. [14] Richard Cleve, Artur Ekert, and Chiara Macchiavello. 1997. Quantum Algorithms RePvisite . R. Soc.d.London. In 339ś354. arXiv:quant- ph/9708016 [15] Bob Coecke and Aleks Kissinger. 2017. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning . Cambridge University Press. [16] Yuval Emek, Christoph Pister, Jochen Seidel, and Roger Wattenhofer. 2014. Anonymous networks: randomization= 2-hop coloring. In Proceedings of the 2014 ACM symposium on Principles of distributed computing . 96ś105. [17] Pierre Fraigniaud, Magnús M Halldórsson, and Amos Korman. 2012. On the impact of identiiers on local International decision. In Conference On Principles Of Distributed Systems . Springer, 224ś238. [18] Pierre Fraigniaud, Juho Hirvonen, and Jukka Suomela. 2018. Node labels in local Theor deetical cision. Computer Science751 (2018), 61ś73. [19] Nicolai Friis, Vedran Dunjko, Wolfgang Dür, and Hans J. Briegel. 2014. Implementing quantum control for unknown Phys. subroutines. Rev. A 89 (2014), 030303. Issue 3. arXiv:1401.8128 [20] Simon J. Gay and Rajagopal Nagarajan. 2005. Communicating Quantum Processes. ProIn ceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Long Beach, California, USA (POPL ) ’05). Association for Computing Machinery, New York, NY, USA, 145ś157. arXiv:quant-ph/0409052 [21] Kaumudibikash Goswami, Christina Giarmatzi, Michael Kewming, Fabio Costa, Cyril Branciard, Jacqueline Romero, and Andrew G. White. 2018. Indeinite Causal Order in a Quantum Switch. Phys. Rev. Lett. 121, 9 (2018). arXiv:1803.04302 [22] Philippe Allard Guérin, Adrien Feix, Mateus Araújo, and Časlav Brukner. 2016. Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication. Phys. Rev. Lett. 117, 10 (2016), 100502. arXiv:1605.07372 [23] J. Kempe. 2003. Quantum random walks: an introductory overvieContemp w. orary Physics44, 4 (2003), 307ś327. arXiv:quant-ph/0303081 [24] Robin Lorenz and Jonathan Barrett. 2021. Causal and compositional structure of unitary transformations. Quantum 5 (2021), 511. arXiv:2001.07774 [25] Ognyan Oreshkov. 2019. Time-delocalized quantum subsystems and operations: on the existence of processes with indeinite causal structure in quantum mechanics. Quantum 3 (2019), 206. arXiv:1801.07594 [26] Ognyan Oreshkov, Fabio Costa, and Časlav Brukner. 2012. Quantum correlations with no causalNat. order Commun. . 3 (2012), 1092. arXiv:1105.4464 [27] Christopher Portmann, Christian Matt, Ueli Maurer, Renato Renner, and Bjorn Tackmann. 2017. Causal Boxes: Quantum Information- Processing Systems Closed under Composition. IEEE T. Inform. Theory63, 5 (2017), 3277ś3305. arXiv:1512.02240 [28] Lorenzo M. Procopio, Amir Moqanaki, Mateus Araújo, Fabio Costa, Irati Alonso Calafell, Emma G. Dowd, Deny R. Hamel, Lee A. Rozema, Časlav Brukner, and Philip Walther. 2015. Experimental superposition of orders of quantum Naturegates. Communications6, 1 (2015). arXiv:1412.4006 [29] Robert Raussendorf, Daniel Browne, and Hans Briegel. 2002. The one-way quantum computerśa non-network model of quantum computation.Journal of Modern Optics49, 8 (2002), 1299ś1306. arXiv:quant-ph/0108118 [30] Giulia Rubino, Lee A. Rozema, Adrien Feix, Mateus Araújo, Jonas M. Zeuner, Lorenzo M. Procopio, Časlav Brukner, and Philip Walther. 2017. Experimental veriication of an indeinite causal Science order Advances . 3, 3 (2017). arXiv:1608.01683 [31] Márcio Taddei, Jaime Cariñe, Daniel Martinez, Tania García, Nayda Guerrero, Alastair Abbott, Mateus Araújo, Cyril Branciard, Esteban Gómez, Stephen Walborn, Leandro Aolita, and Gabrela Lima. 2021. Computational Advantage from the Quantum Superposition of Multiple Temporal Orders of PhotonicPRX Gates. Quantum 2 (2021), 010320. Issue 1. arXiv:2002.07817 [32] Augustin Vanrietvelde, Hlér Kristjánsson, and Jonathan Barrett. 2021. Routed quantum cir Quantum cuits. 5 (2021), 503. arXiv:2011.08120 [33] Julian Wechs, Cyril Branciard, and Ognyan Oreshkov. 2022. Existence of processes violating causal inequalities on time-delocalised subsystems. (2022). arXiv:2201.11832 [34] Julian Wechs, Hippolyte Dourdent, Alastair A. Abbott, and Cyril Branciard. 2021. Quantum circuits with classical versus quantum control of causal order. arXiv:2101.08796 ACM Trans. Quantum Comput. 20 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron [35] Kejin Wei, Nora Tischler, Si-Ran Zhao, Yu-Huai Li, Juan Miguel Arrazola, Yang Liu, Weijun Zhang, Hao Li, Lixing You, Zhen Wang, Yu-Ao Chen, Barry C. Sanders, Qiang Zhang, Geof J. Pryde, Feihu Xu, and Jian-Wei Pan. 2019. Experimental Quantum Switching for Exponentially Superior Quantum Communication Comple Physical xityRe . view Letters122, 12 (2019). arXiv:1810.10238 [36] Matt Wilson and Giulio Chiribella. 2020. A Diagrammatic Approach to Information Transmission in Generalised Switches. arXiv:2003.08224 ACM Trans. Quantum Comput. Addressable quantum gates • 21 A ADDRESSABLE QUANTUM CIRCUITS A.1 Details on the model Several notions are introduced in this paper. For a summary of notations Ðsee Sect. F. This section provides details on Sect. 2. Addresses. In the core of the paper the stored address spaces and the target spaces were deined in words. More formally, we have Deinition A.1 (Addresses).The set of addressesA is a inite subsetNof . Moreover, we denote byW = A = ? 1 {� . . .� |� ∈ A,� ≠ � ∀�, �} the set of words ofnon-repeating addresses, and by T = A = {� | � ∈ A }∪{�} 1 � � � � the set of words of length at most one. When � addresses are in a sector space, a gate operator can map them to any superposition of(the 2� + 1)�! diferent states : • if the target space is empty, there ar � e+ 1 possibilities for the number of addresses in the input space (the others are in the output space) and�! diferent ways to order them. • if the target space is non-empty, the � − 1 remaining addresses are to be distributed between input and output space: any number of addresses from0 to � − 1 can be in the input space, and as above, there ar�e! diferent ways to order them order. When � addresses are in a sector space, and additionally the gate operator nameblind is , there are only2� + 1 diferent possibilities counted as above but up to reordering. It suices to specify the behaviour of the gate operator on one of each of those(2�+1) possibilities, to have them speciied on all the corr�esp ! reonding ordered possibilities, by renaming invariance Ðsee Fig. 8. Flipping gates. To prepare the transport to a targeted sector, many gate operators push some of their content to the output spaces after manipulating it. This is achieved by lipping operations, which are in some sense necessary since gates whose scattering unitary is the identity �are merely as a łmirrorž, i.e. they relect incoming data. In the example of the Bell state creation circuit in (3) the input and output spaces are lipped by ′ ′ ′ ′ � : |�⟩ |�,�⟩ |� ,� ⟩ ↦−→ |�⟩ |� ,� ⟩ |�,�⟩ . T T I O I O Other possibilities are lipping only the data spaces, i.e. ′ ′ ′ ′ � : |�⟩ |�,�⟩ |� ,� ⟩ ↦−→ |�⟩ |�,� ⟩ |� ,�⟩ , data T I O T I O or more sophisticated lips that are conditioned on the state of the sector. Evolution. Like in Def. 2.8, the example below uses the following convention on|�the⟩ states indicates : that the space � ∈ {T,I,O} of the sector� ∈ A is in the state|�⟩. Example A.2. Efect of the transport step� withA = {1, 2}: Without basis reordering : 1 1 1 1 1 1 |2⟩ |�,� ⟩ |�,�⟩ |2⟩ |�,� ⟩ |1,� ⟩ 1 1 2 T I � T I � −→ 2 2 2 2 2 2 |�⟩ |1,� ⟩ |�,�⟩ |�⟩ |�,�⟩ |�,�⟩ T � T � I I With basis reordering of Sect. 2.1: |2,�⟩ |(�,� ),(1,� )⟩ |(�,�),(�,�)⟩ T 1 2 � −→ |2,�⟩ |(�,� ),(�,�)⟩ |(1,� ),(�,�)⟩ � 1 2 T I � The address 1 and data � were in the input space of the sector 2, and � transports them to the output space of sector 1, because sector 1 targeted sector 2. ACM Trans. Quantum Comput. 22 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron Example A.3. The Bell state creation circuit evolves very simply Ð missing the obvious coeicient here and not writing target spaces (as they do not change) and empty spaces : 1 1 2 2 3 |00⟩ → |00⟩ → |00⟩ → (|0⟩ + |1⟩) |0⟩ → (|0⟩ + |1⟩) |0⟩ � � � � I O I O I 3 3 4 4 4 4 4 4 → |00⟩ + |11⟩ → |00⟩ + |11⟩ → |00⟩ + |11⟩ → |00⟩ + |11⟩ , � � � � O O I I O O O O where the lack of a target address in sector 4 causes the data to stay there during the last transport step. A.2 Details of the uantum Switch A.2.1 Definition. The description of the quantum switch in Sect. 3.1 can be completed by specifying some gate operators � . Their action on the addresses is as follows: {1} {6} {3} {4} � = � = � , � = � · � , � = � · � . 34 � 34 � Here, � applies the gate � to the irst� bits of data, i.e. on all data except the control qubit, and |�⟩ |�⟩ |�⟩ ←→ |�⟩ |��⟩ |�⟩ T W T W Q Q O O I I � = |�⟩ |�⟩ |�⟩ ←→ |�⟩ |�⟩ |�⟩ T W Q T W Q O I O I {2,5} ′ − The gate operator � , the efect of which is detailed in A.2.2, acts as follo�ws ,�(,wher �∈ Ae, � ∈ A , �∈ D, � ∈ D and, as usual, states that are omitted correspond �to): 2 ′ 5 |�⟩ |�� ,��⟩ |�⟩ if� = 0 {2,5} ′ 2 5 T O T � |��� ⟩ |��⟩ |�⟩ = (7) W Q T 2 ′ 2 5 O I |�⟩ |�� ,��⟩ |�⟩ if� = 1 T O {2,5} 2 5 5 2 5 5 5 � |�⟩ |�⟩ |��⟩ = |�⟩ |�⟩ |�⟩ |�⟩ (8) T T T Q W Q Q I O I O ′ 5 5 |��� ⟩ |�⟩ |��⟩ if� = 0 {2,5} 2 ′ 2 5 W T Q � |�⟩ |�� ⟩ |�⟩ |�,�⟩ = (9) T W Q O ′ 2 5 O 5 |��� ⟩ |�⟩ |��⟩ if� = 1 T Q O O {2,5} We ensure unitarity �of by specifying a reciprocal version of the equations above: 2 ′ 2 5 ′ 2 2 5 {2,5} � |�⟩ |�� ,�0⟩ |�⟩ = |��� ⟩ |�0⟩ |�⟩ O W T T Q T O I • reciprocal version of (7): 2 2 2 ′ 5 ′ 2 5 {2,5} � |�⟩ |�� ,�1⟩ |�⟩ = |��� ⟩ |�1⟩ |�⟩ T O T W Q T {2,5} 2 5 5 5 2 2 5 5 2 • of (8):� |�⟩ |�⟩ |�⟩ |�⟩ |�⟩ = |�⟩ |�⟩ |��⟩ |�⟩ T W Q Q W T T Q W O I O I 2 2 ′ 5 5 {2,5} 2 ′ 2 5 |��� ⟩ |�⟩ |�0⟩ = � |�⟩ |�� ⟩ |0⟩ |�,�⟩ W T Q T W Q O O O O O • and of (9): ′ 2 5 5 2 ′ 2 2 5 {2,5} |��� ⟩ |�⟩ |�1⟩ = � |�⟩ |�� ⟩ |1⟩ |�,�⟩ W W O T Q T O Q O O O These three reciprocal cases are not useful in usual executions of the quantum switch, where they have zero {2,5} {2,5} amplitude. On all other basis � states,acts as the identity. This fully deines � . {2,5} A.2.2 Correctness. The evolution of the quantum switch is displayed in Fig. 5. Since �the opis erator the most interesting gate operator, let us describe its action in detail. In the scattering 2, it after actsstep as in (7). In step 5, it acts as in (8), which allows the remaining data to wait in the output space of sector 5. Most importantly, the control qubit lows back into the circuit, allowing the addresses to return to their initial positions in steps 6-9. In step 8, they łmergež back together, according to (9). The data then lows out of sector 5 into the outgoing bufer sector 6, and can be processed further by concatenated AQCs (see Sect. D.3) as the quantum switch is not entangled with the data anymore Ðsee e.g. 5j. ACM Trans. Quantum Comput. Addressable quantum gates • 23 That is, at the end of Fig. 5, the data has been delivered, and the quantum switch has folded back into its initial coniguration. In Step 9 the inal state of the data��space |�⟩|is 1⟩ +�� |�⟩|0⟩ (when omitting scalar coeicients). This matches the behaviour described in (1), which proves correctness. {2,5} As a inal remark, note that according to Thm. 4.2 the nameblindness � ofonly would have required commutation with renamings over the setexternal of addresses {1, 3, 4, 6}. Yet, we proved in Sect. 4.3 that it also holds for the addresses{2, 5}. B NAMED AQC To prove the results on the nameblindness of the main text, we disentangle the notions of physical locations and łnamesž as arbitrary labels of sectors. This amounts to extending the Hilbert spaces we work with by a łname space,ž i.e. an additional address space, which allows us to carefully distinguish between instances of AQCs with diferently chosen labelings. There are also other ways to describe a geometry than resorting to arbitrary names, e.g. working modulo isomorphism which, however, results in signalling problems [3]. B.1 Definition of an NAQC Here we deine formally every notion useName d ford AQC (NAQC) which difers from that used for AQC. Deinition B.1 (Named sector space).Let �be the index of a sector. The Hilbert space H = H ⊗H ⊗H ⊗H T I O N is referred to as name a d sector space, withH a copy ofH referred to as thename space. N A ˆ ˆ Deinition B.2 (Named circuit space). The circuit spaceH of an NAQC is the subspace of H such that �∈A each address appears at most once in the combined target, input and output spaces, and exactly once in the name spaces. In the NAQC formalism, target spaces H no longer target physical locations (a position as factor in the tensor product H ). Instead, it targets the name� ∈ A of that physical location, as occurring in some name space H of some sector. A gate� = {� ,� , . . .,� }, on the other hand, consists of the sectors at the physical locations N 1 2 � {� ,� , . . .,� }. 1 2 � Deinition B.3 (Named gate space).The named gate space of a gate� consists of|�| named sector spaces, i.e. it is � � ˆ ˆ given byH = H . �∈� � � ˆ ˆ Deinition B.4 (Named gate operator).A named gate operator on � ∈ G is a unitar�y : H → H which preserves the addresses of the target and stored spaces as in Def. 2.6, and separately the name space stays unchanged. − � � ˆ ˆ For any name � ∈ A , we denote byH := H ⊗ |�⟩ the subspace ofH spanned by the basis states that ˆ � ˆ give the name� to the gate �. ClearlyH, is the smallest Hilbert space containing H . Moreover, since gate operators by deinition preserve the name of the gate space, they are of the form � = � , i.e. named gate � � operators are block-diagonal with blo � cks acting on and preservingH . � � � � � � Deinition B.5 (NAQC transport).The named transport � maps synchronously|�⟩ |�⟩ ⊗ |�⟩ |�⟩ to T O I N � � � � |�⟩ |�⟩ ⊗ |�⟩ |�⟩ , leaving the other sector constituents unchanged. That�is, swaps the output space O I N of a sector with the input space of the sector withname the it targets, i.e. whenever a sector �targets a name �, �’s output space is swapped with the input space of the sector with �name . B.2 Renaming NAQCs − − Let � be a name, i.e. an elementA in. We call a renaming �, i.e. a permutationA of ACM Trans. Quantum Comput. 24 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron • external for �, if � acts as the identity over each address �in . • internal for�, if� acts as the identity over each addressA in\ �. • mixed for�, if� is a composition of disjoint swaps fully speciied by two equal (� ,size � ) dwher setse 1 2 � takes its elements in � and � takes its elements in A \ �. � swaps the irst element of � for the 1 2 1 natural order overN with the irst element�of, the second with the second and so on). On elements of A \ (� ∪ � ), � acts as the identity. 1 2 9 2 5 4 8 |�⟩ |89⟩ |24⟩ |�⟩ |�⟩ W W W W W 0 1 2 3 4 5 6 7 8 9 10 (a) An NAQC . . . 2 4 5 8 9 |�⟩ |92⟩ |48⟩ |�⟩ |�⟩ W W W W W 0 1 2 3 4 5 6 7 8 9 10 (b) . . . renamed so that each gate space is named with the canonical name. Fig. 10. An NAQC represented over a grid. HereA = {2, 4, 5, 8, 9}. Inside of each sector (big white boxes) we can find the content of the stored address space. Gray boxes represent the content of the name space. Example B.6. Consider the circuit in Fig. 10a. We focus here on the gate space {4,5} which has the 25.name Then • � isexternal because it only swaps external addresses. 4↔8 • � is the only non-trivial internal renaming for this state. 2↔5 • � ismixed because it swaps external with internal addresses in an ordered fashion. 5↔9,2↔4 • � is neither internal nor mixed nor external. 5↔4,2↔9 Distinguishing these particular types of renamings is useful because any � can renaming be uniquely decom- posed into a mixed, an internal and an external renaming with respect to a giv �.en The name basic idea to construct this decomposition is to irst apply a mixed renaming to bring all�the (�)letters into the ofgate space, then use an internal renaming to ensure that the gate space is name �(�d), and inally adjust the addresses that are not in� with an external renaming. Let us deine � the renaming changing the wor�dto �, and not �→� changing other letters. Proposition B.7 (Decomposition of renamings). (1) Let � and � be names of same length. There is a unique renaming � = �� such that � is mixed for� and � �→� is internal for� (�). (2) Let � be a renaming and� be an element ofA Ðsee Def. A.1. There exists exactly one pair of renamings such that: � = �� �→� ACM Trans. Quantum Comput. Addressable quantum gates • 25 where � = �(�) and � is external for�. Proof. For any name � = � � . . . � ∈ A we writeSET(�) = {� , � , . . ., � } and note that it is invariant 1 2 � 1 2 � under renamings that are external and internal�.for (1) Let � : A → A be a renaming, and take� as the renaming that swaps elements of SET(�) \ SET(�(�)) with elements of SET(�(�)) \ SET(�) and is mixed for �. Note that SET(� (�)) = SET(�(�)), and that � is unique since we have that SET(� (�)) = SET(���(�)). Similarly,�take as the renaming such that for every integer 0 < � < |�| + 1 �: A → A, � (�) ↦→ �(�) , � � and which is internal� for (�). Since��(�) = ���(�) for all � external for��(�), � is the only possible choice. Together, this gives a unique decomposition � = �� . �→� −1 −1 (2) This follows from deining � = �� � which is unique since it is the only renaming that guarantees � = ��� . Moreover, � is (trivially) external ��(�for ), since���(�) = �(�) = ��(�), where the last equality is by construction of� in the proof of (1). □ Example B.8 (Decomposition of renamings). Consider the renaming � on the circuit of Fig. 10a, which 2→9→8,4↔5 4 5 4 5 maps the gate space state |2⟩ |89⟩ |5⟩ |24⟩ to |9⟩ |28⟩ |4⟩ |95⟩ . We decompose it with respect to N N N N W W W W the name � = 25: • Since�(�) = 94, the mixed renaming constructed in the above proof � is = � , which results in the 5↔9,2↔4 4 5 state |4⟩ |85⟩ |9⟩ |42⟩ . N N W W • Then, �= � is the only possible internal renaming that reorders the name of the gate space, which is 9↔4 4 5 thus in the state|9⟩ |85⟩ |4⟩ |92⟩ . N N W W • Finally � =, � reorders the external addresses to match the desired ones. 2→5→8 Next, we relate AQCs to NAQCs with speciically chosen gate names, called the canonical name Ðsee Fig. 10b. To this end, consider a named gate spaceH with� = |�| sectors. Its basis states are of the form |� � ⟩|� ⟩ � � � N �∈� �increasing This state giv�esnames � to the sectors inside the gate space, thus we say that this state givesname the � = � � . . . � to the gate � = � � . . .� with� < � < . . . < � . � � � 1 2 � 1 2 � 1 2 � Deinition B.9 (Canonical name).Consider a gate� = {� ,� ,� , . . .,� }. The canonical nameof� is� = � � � . . .� 1 2 3 � 1 2 3 � with� < � < ··· < � . The basis states ofH take the form: 1 2 � � |� � ⟩|�⟩ �∈� ′ � By this deinition, the basis states H of are in one-to-one correspondence with those of the gate space H of an AQC (Sect. 2), i.e. |� � ⟩ . �∈� Choosing a canonical name means choosing a representative for each equivalence class w.r.t. renamings Ð see (5). Thus the subspace H of the named circuit space H is isomorphic to the circuitH space . �∈� �(�) ACM Trans. Quantum Comput. 26 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron Finally, we describe those gate operators which act the same way whatever the name of the gate is. This relects the idea that the action at a physical location (a house) should not depend on the arbitrary choice of name for that location (the number on the house), which is iducial. Since such gate operators do not depend on the internal addresses in the name spaces of gate space, we call them łinternally-blindž: Deinition B.10 (Internally-blind gate operators).Let � be a gate with� sectors and canonical name � ∈ A . The � − ′ named gate operator � is calle internally-blind d if for any � ∈ A with|�| = � and for any state|�⟩ ∈ H : � � −1 � |�⟩ = � � � |�⟩ . �→� � � �→� Internally-blind named gate operators are completely determined by their � . Inblo theck next section we show that renaming invariance imposes further constraints on this block. B.3 Proof of Theorem 4.2 The concept of NAQC introduced above allows us to prove that nameblind AQCs and nameblind NAQCs are isomorphic. To do so, we show that nameblindness of an NAQC is equivalent to it being internally-blind, i.e. fully determined by its action over the canonical name (see Def. B.10), and commuting with renamings that are external for the canonical name. We show that internally-blind operators that commute with external renamings are nameblind: Lemma B.11 (Commutation with mixed and internal renamings). Let � be an internally-blind gate operator, � the canonical name of�, and � ∈ A a name of size|�|. If� commutes with every renaming external to �, then for all� ∈ A with|�| = |�| and any |�⟩ ∈ H � � � � |�⟩ = � � |�⟩ . �→� �→� Proof. Let � as in Prop. B.7. Let� be the renaming deined by �→� −1 � = � � � �→� �→� �→� Since�� = �, it is external�for . We have: � � |�⟩ = � � |�⟩ (Diagonal blockwise) �→� �→� −1 = � � � � |�⟩ (Internally-blind) �→� �→� � �→� −1 = � � �� |�⟩ (Deinition�of ) �→� � �→� −1 = � �� � |�⟩ (Hypothesis) �→� � �→� −1 = � � � � |�⟩ (Deinition�of ) �→� �→� � �→� = � � |�⟩ (Internally-blind) �→� � = � � |�⟩ (Diagonal blockwise) �→� Lemma B.12 (Commutation with external renamings). Let � be a internally-blind gate operator�, the canonical name of�, and � ∈ A a name of size|�|. If� commutes with every external renaming, then for all external renamings� and all |�⟩ ∈ H : � � � � |�⟩ = �� |�⟩ . Proof. Let � be a renaming external for �. Let � be the renaming deined by: ′ −1 � = � �� �→� �→� ′ ′ � is external for � so we have for each state|�⟩ ∈ H : ACM Trans. Quantum Comput. Addressable quantum gates • 27 � � |�⟩ = � � |�⟩ −1 = � � � � |�⟩ (Internally-blind) �→� � �→� ′ −1 ′ = � � � � |�⟩ (Deinition�of ) �→� � �→� ′ −1 = � � � � |�⟩ (Hypothesis) �→� � �→� −1 = �� � � |�⟩ �→� � �→� = �� |�⟩ ˆ � � Theorem B.13 (Characterization of renaming invariance). LetH be a named gate space, � be a named � � gate operator and � the canonical name of�. � is renaming invariant if and only � if is internally-blind and � � � commutes with every renaming� external for�, i.e� � = �� . � � � � Proof. [⇒] : Let � be a nameblind gate operator. Since by hypothesis � commutes with all renamings, it obviously commutes with the external ones, and so does the�blo . Tck o show that � is internally-blind, � � consider a renaming � . Renaming invariance� ofimplies that � � = � � , and hence for every name �→� � �→� �→� � of� and for each state|�⟩ ∈ H we have � � −1 � |�⟩ = � � � |�⟩ , �→� � � �→� which is a restatement of internal-blindness. [⇐] : Let� be an internally-blind gate operator such � that commutes with all external renamings. Consider a renaming� and a name � ∈ A of size|�|. Then, for every state|�⟩ ∈ H : � � � � |�⟩ = � ��� |�⟩ (by Prop. B.7) = �� �� |�⟩ (by Lem. B.12) = ���� |�⟩ (by Lem. B.11) = �� |�⟩ , i.e�. is renaming invariant. □ Thm. B.13 states that the named gate operator � of a nameblind NAQC is fully characterized by its � action over the gates with canonical names, and that these must commute with external renamings. From Def. B.9 it follows that the evolution of an NAQC over gates with canonical names is isomorphic to that of an AQC. Thus, the set of nameblind NAQCs is isomorphic to the set of AQCs whose gate operators commute with external renamings. Therefore, Thm. 4.2 follows from Thm. B.13. Proof of Thm. 4.2. Let us consider a nameblind NA(QC(A,G,Q,�,N),|�⟩|�⟩), its scattering � commutes with every renaming �, i.e�.� = ��. The isomorphic nameblind Addressable Quantum Cir((cuit A,G,isQ,� ),|�⟩), where � is deined as a scattering where each gate operator � is of the form � of Thm. B.13. Reciprocally, � � � given a nameblind AQC, as each gate operator � commutes with external renamings, � = � is a nameblind named gate operator that can be used to specify a nameblind NAQC. □ ACM Trans. Quantum Comput. 28 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron C CHARACTERIZATION OF NAMEBLIND OPERATORS Nameblind gate operators consist of blocks of nameblind matrices (see Prop. 4.7), which will be characterized inductively in this appendix. Below, when representing such operators over � eaxternal list of addresses as matrices, we implicitly use the basis of words sorted in lexicographically ascending order, i.e. {12 . . .(� − 1)�, 12 . . .�(� − 1), . . .,�(� − 1) . . . 21}. (10) In this basis, the irst (� − 1)! words begin with letter 1, the next (� − 1)! words begin with letter 2 etc. We often partition matrices acting on�!this -dimensional Hilbert space � into blocks, each acting between two (� − 1)!-dimensional Hilbert spaces, each being spanned by words starting with the same letter. C.1 Adjacent transpositions Let � be an integer and let us consider � ∈ {1, . . .,�−1}. We call the renaming � which swaps� and �+1 and acts as the identity otherwiseadjacent an transpositionon words of� addresses at �. Adjacent transpositions generate the group of renamings, such that any renaming can be written as a product of such adjacent transpositions. Commuting with all adjacent transpositions is therefore equivalent to commuting with all renamings. Lemma C.1. In the basis(10) the matrix of an adjacent transposition � has the form � �+ 1 ↓ ↓ � 0 . . . �−1 © ª . . . . ­ ® . . ­ ® ­ . ® . . ­ ® . � �−1 ­ ® ­ ® � = (11) 0 � ← � ­ ® ­ ® � 0 ← � + 1 ­ ® ­ ® . . ­ ® � . ­ ® ­ ® . . . . ­ ® . . « ¬ . . . 0 � where � is the adjacent transposition matrix on words�of− 1 addresses at �. Proof. We consider the lines before and after�th theline separately: The addresses after�the th block line correspond to � letter words that begin with a letter bigger�.than Amongst the remaining � − 1 letters,� is still the �th letter in ascending lexicographic order. Thus, to transp � and ose� + 1 we must apply� . The lines before the �th line, correspond �toletter words starting with a letter smaller �. Thus, than amongst the remaining � − 1 letters,� is still(�the− 1)-th letter in ascending lexicographic order. Therefore, the correct matrix to apply�is . □ �−1 C.2 Nameblind operators We now prove Theorem 4.4, which we restate here for the convenience of the reader : ACM Trans. Quantum Comput. Addressable quantum gates • 29 Theorem 4.4. (�,�)-nameblind matrices have exactly the form � � � � � � � � � � � . . . 1 2 1 3 2 1 © ª � � � �� � � �� . . . ­ 1 1 2 1 1 ® ­ ® �� � �� � ­ 1 1 1 ® ­ ® ­ ® � = (12) �� � � �� � ­ 1 2 1 1 2 ® ­ ® ­ ® �� � � . ­ ® 1 2 3 ­ ® « ¬ where � is a(�−1,�−1)-nameblind matrix and� is any matrix which commutes with � for each�in{2, 3, ...,�−1}, whose characterization is given in Prop. C.2 Proof. Let � be a matrix of size �!× �! written blockwise with blocks of(� − size 1)!× (� − 1)! as � � . . . � � . . . � 1,1 1,2 1,� 1,�+1 1,� © ª . . . . . ­ ® . . . . . . ­ . . . . . ® ­ ® ­ � � . . . � � . . . � ® �,1 �,2 �,� �,�+1 �,� � = ­ ® . ­� � . . . � � . . . � ® �+1,1 �+1,2 �+1,� �+1,�+1 �+1,� ­ ® . . . . ­ ® . . . . . ­ . . . . ® � � . . . � � . . . � �,1 �,2 �,� �,�+1 �,� « ¬ Since every renaming can be written as a product of adjacent transpositions, commuting with all renamings is equivalent to commuting with all adjacent transpositions. � is Thus, nameblind�if � = �� for all � ∈ � � {1 . . .� − 1} with� as in (11), i.e. if the following matrices are equal�:for every � � � � . . . � � � � . . . � � �−1 1,1 �−1 1,2 �−1 1,� �−1 1,�+1 �−1 1,� © ª ­ ® � � � � . . . � � � � . ­ 2,1 2,2 ® �−1 �−1 �−1 2,� �−1 2,�+1 ­ ® . . . . . ­ ® . . . . . . . . . . ­ ® ­ ® � � = � � . . . � � . . . � ­ ® �+1,1 �+1,2 �+1,� �+1,�+1 �+1,� ­ ® � � . . . � � . . . � ­ ® �,1 �,2 �,� �,�+1 �,� ­ ® . . . . ­ ® . . . . ­ . . . . ® � � . . . . . . � � � � . . . � � � �,1 � �,� � �,�+1 � �,� « ¬ � � � � . . . � � . . . � � 1,1 �−1 1,2 �−1 1,�+1 1,� 1,� � © ª ­ ® � � � � . . . � � . ­ ® 2,1 �−1 2,2 �−1 2,�+1 2,� ­ ® . . . . . ­ ® . . . . . ­ . . . . . ® ­ ® �� = ­ � � � � . . . � � . . . � � ® �,1 �−1 �,2 �−1 �,�+1 �,� �,� � ­ ® ­� � � � . . . � � . . . � � ® �+1,1 �−1 �+1,2 �−1 �+1,�+1 �+1,� �+1,� � ­ ® . . . . ­ ® . . . . ­ . . . . ® � � . . . . . . � � . . . � � « �,1 �−1 �,�+1 �,� �,� � ¬ This gives three types of conditions which we distinguish by their color in the matrices above: ACM Trans. Quantum Comput. 30 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron Blue conditions . For each �∈ {1, . . .,� − 1}: � = � , i.e. all diagonal blocks are equal. �,� �+1,�+1 � = � , i.e. the matrix is blockwise-symmetric near the diagonal. �,�+1 �+1,� We will henceforth write the diagonal blo � :=cks � asand we set � := � . 1,1 1,2 Green conditions . Consider a row�, a column�and an adjacent transposition � . The green conditions from commutation with � are equivalent to: Above the diagonal, i.e �<.� < � + 1 < �: – � = � � , i.e one step to the right corresponds to right multiplication with . �,�+1 �−1 �,� – � = � � , i.e the(� + 1)-th element of column �is equal �to times the�-th element. �+1,� �,� � � Below the diagonal,�i.e < �. < � + 1 < �: – � = � � , i.e. the(� + 1)-th element of line �is equal �to times the�-th element. �,�+1 � �,� � – � = � � , i.e. the(� + 1)-th element of column �is equal �to times the�-th element. �+1,� �,� �−1 �−1 This has to hold for�all which gives the general form � of given in Thm. 4.4, because we can deduce all blocks from� and � , but the conditions on the blocks are yet to be derived. 1,1 1,2 Black conditions.From the diagonal conditions in the top-left and bottom-right quadrant we immediately deduce that � commutes with all � for0 < �< � − 1, i.e�. is nameblind. Similarly � commutes , with all � for � � 2 < �< � − 1. Thus, in the basis (10) � has the form (12). Let us now show the converse, i.e. that any matrix � as speciied in Thm. 4.4 is nameblind. By deinition, it satisies the blue and green conditions, and it only remains to check that it also meets the requirements of the black conditions. To this end, consider a�bloabckove the diagonal, i.e �<. �, which is symmetric with the �,� case where it is below. By (12) this block is given by � = � . . . � �� . . . � . �,� �−2 1 1 �−1 To satisfy the top-left and bottom-right conditions, this block has to commute � with for all � such that �−1 ′ ′ � < � < �, and with� for all � such that � + 1 < �, i.e. it has to commute with � for all � ∈ � := � � {1, . . .,�− 2}∪{�, . . .,�− 2}. Explicitly, we need to show that� for ∈ � � . . . � �� . . . � � = � � . . . � �� . . . � . �−2 1 1 �−1 � � �−2 1 1 �−1 Rearranging this we obtain � = � . . . � � � . . . � �� . . . � � � . . . � 1 �−2 � �−2 1 1 �−1 � �−1 1 ⇔ � = � . . . � � � . . . � � . . . � � � . . . � � 1 �−2 � �−2 1 1 �−1 � �−1 1 ⇔ � = � . . . � � � . . . � � � . . . � � 1 �−2 � �−2 � � �−1 1 ⇔ � = � . . . � � � � . . . � � . . . � � 1 �−2 � � �−2 � �−1 1 ⇔ � = � . . . � � . . . � � 1 �−1 �−1 1 where the irst equivalence comes from premise�that commutes with renamings that preserve the letter 1 (since {� , . . ., � } generates this family of renamings) which � . . . � � � . . . � does since� is diferent 2 �−1 1 �−1 � �−1 1 from� and �− 1, and the third comes from the fact that two transpositions with disjoint support commute. Moreover, since� � = � the right side of the last equation indeed�.gives � � To verify the top-right and bottom-left conditions, consider� a blo with ck�< �, and a �< � < �− 1. Since �,� the conditions for this quadrant are symmetric, this is suicient. This block has � to � satisfy = � � . We �,� � �−1 �,� calculate: � � = � . . . � �� . . . � � (1) �,� � �−2 1 1 �−1 � ACM Trans. Quantum Comput. Addressable quantum gates • 31 = � . . . � �� � . . . � (2) �−2 1 � 1 �−1 = � . . . � � � � � . . . � �� . . . � (3) �−2 �+1 � �−1 � �−2 1 1 �−1 = � . . . � � � � � . . . � �� . . . � (4) �−2 �+1 �−1 � �−1 �−2 1 1 �−1 = � � . . . � � � � . . . � �� . . . � (5) �−1 �−2 �+1 � �−1 �−2 1 1 �−1 = � � (6) �−1 �,� where as above we used that transpositions with disjoint support commute and ��that= � � since� > 1. � � The non-trivial step in the forth equality is to realize � � �that = � � � = (� − 1 � + 1). �−1 � �−1 � �−1 � Thus, all black conditions are satisied by the blo � of cks theofgeneral form given in Thm. 4.4, which implies that � indeed is nameblind. □ C.3 Partially-nameblind operators The matrix� of Thm. 4.4 is łpartially-nameblindž in the sense that it commutes with all renamings which preserve the irst� addresses in lexicographical order. We denote the set of such matrices B , wher by e � indicates the total number of addresses. Proposition C.2 (Characterization of partially-nameblind matrices). partially-nameblind matrices � ∈ B are exactly those matrices which can be written as � = � � � � . . . � � � � � � � . . . 1,1 1,� � �+1 � 1 1 1 © ª � � � ­ ® � . . . � � � � � � � . . . 2,1 2,� � �+1 � 2 2 2 ­ ® . . ­ . ® . . . ­ . ® . . ­ ® � � � ­ ® � . . . � � � � � � � . . . �,1 �,� � �+1 � � � � ­ ® � � ­ ® � . . . � � � � � . . . �+1 1 � ­ ® � � ­ ® � � . . . � � � � � �� . . . � � �+1 �+1 ­ 1 ® � � ­ ® � � � . . . � � � �� � �� � � �+1 � �+1 �+1 �+1 �+1 ­ 1 � ® ­ ® . . ­ . . . ® . �� � . ­ �+1 �+2 ® ­ ® « ¬ �−1 � � �−1 �−1 where � ∈ B , � , � and � are inB , and � is inB . �,� �−1 � � �+1 Proof. As above, we use blue, green and top-left black conditions, which for matrices B howein ver have to be satisied only for � < �. Conversely, we have to check that matrices of this form satisfy the black conditions. First, we consider blocks �−1 � in the top-left or bottom-right corner �< . If� + 1 and �< � + 1 we just have to check that � is inB , �,� �,� �−1 which is the case by deinition. If�> � and �> �, the proof of Thm. 4.4 applies. Thus, we only have to consider the�<case � + 1, �> � since the other one follows by symmetry. In this case the block is given as � = � . . . � � , �,� �−2 � and we have to verify that it commutes with � for all � such that �< � < �, and with� for all � such that �−1 � � + 1 < � + 1 < �, i.e. that it commutes with � for each� ∈ {�,�− 2} as {� + 1, . . .,�− 2} is empty. Since these transpositions have disjoint support, this is straightforward to see. Next, pick� in the top-right or bottom-left corner. Since the top-right and bottom-left conditions are �,� symmetric it is suicient to consider the�<case �. Moreover, if�> � again the previous proof applies, so we ACM Trans. Quantum Comput. 32 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron only consider �< � + 1 < � + 2 < �. We have to show that � � = � � for all � < �− 1. Indeed, �,� � �−1 �,� � � = � . . . � � � �,� �−2 � � � = � . . . � � � . . . � � �−2 � �−1 � � = � . . . � � � . . . � � �−2 �−1 � �−1 � = � � . . . � � . . . � � �−2 � �−1 � �−1 = � � �−1 �,� This ends the proof that all black conditions are satisied by matrices of the general form given in Prop. C.2, and thus we have proved the desired equivalence. □ C.4 (�,� )-nameblind matrices C.4.1 Proof of Prop. 4.6. Consider a(�,� )-nameblind matrix � ; � = |A | is the number of external addresses, �� and � ≤ � is the number of addresses present in any state handled� by . � is an operator over words on� addresses chosen among �. In the following, we will use the basis of such words, not sorted in lexicographic ascending order as in{12 . . .(� −1)�, 12 . . .(� −1)(� +1), . . .,� . . .(�−� +2)(�−� ),� . . .(�−� +2)(�−� +1)}, but instead sorted irst by what addresses are present, and then by lexicographical ascending order, i.e. {12 . . .(� − 1)�, 12 . . .� (� − 1), . . .,� . . .(� − � + 1)(� −� + 2),� . . .(� −� + 2)(� − � + 1)}. Note that if � < �, � acts on basis states with less addresses than all external addresses. Let us sho�w that can be written blockwise with (�,� )-nameblind matrices (see Thm. 4.4). This state space is partitioned according to the A set (of size � ) of what addresses are actually present, each subspace being calleHd Ð for some A ⊂ A . As � does neither create nor suppress addresses, it is also A �� block diagonal (in the particular ordering we chose). Lemma C.3 proves that all these blocks are equal. Next, we show that all blocks are nameblind. To this end, consider a set of addr B with essescorresponding ˆ ˆ ˆ block� which maps words fromH toH , whereH is the corresponding subspace. Then, for any renaming B B B B ˆ ˆ � manipulating addresses within H , and any � ∈ H : B B ��� = �� �, ��� = � ��, B B as �� ∈ H . The left sides of these equalities agre�e since is nameblind. Therefor � e,is nameblind, and as it B B is acting on words of size � on � addresses, it is(�,� )-nameblind. C.4.2 Lemma - Block equality. The basis states of(a�,� )-nameblind matrix � are ordered according to which addresses A are present. For the sake of simplicity of demonstrating Lem. C.3, we further specify the order between such address sets. Let A be a subset ofA of size � . We deine its sizeas the integer corresponding �� to the indicator function (understood as little-endian binary number), and �(Anote ). For itinstance, with A = {1, 2, . . ., 6}: �� 1 2 3 �({2, 3, 4}) = ���(011100) = 2 + 2 + 2 = 14 0 1 4 �({1, 2, 5}) = ���(110010) = 2 + 2 + 2 = 17 Note that only the binary numbers with � bits set to1 will be represented. The order between inite address sets is then simply the usual order between their sizes. ACM Trans. Quantum Comput. Addressable quantum gates • 33 . . . < |011100⟩ ↔ {2, 3, 4} . . . < |011100⟩ < |110010⟩ ↔ {1, 2, 5} |011100⟩ < |110010⟩−����� < |101010⟩ ↔ {1, 3, 5} |110010⟩ < |101010⟩−�������������� < |011010⟩ ↔ {2, 3, 5} |101010⟩ < |011010⟩ < |100110⟩ ↔ {1, 4, 5} |011010⟩ < |100110⟩ < |010110⟩ ↔ {2, 4, 5} |100110⟩ < |010110⟩ < |001110⟩ ↔ {3, 4, 5} |010110⟩ < |001110⟩ < |110001⟩ ↔ {1, 2, 6} |001110⟩ < |110001⟩ < . . . |110001⟩ < . . . (a) Writing address sets as binary numbers to determine their(b) Efect of the renaming : when is each case used. size. Fig. 11. Order and types of successive basis blocks, by writing the imageAof by the Indicator functionAofas a binary number. The patern identified byB or B is then represented as colored numbers. �,�+1 �,�+1 Lemma C.3. Let � be a gate of an AQC with address spaceA. Write� in the basis sorted by: (1) First, according to the size� of address sets Ðsee above. (2) Second, for each group of addresses, the words are sorted in lexicographical increasing order. Then S is blockwise diagonal with blocks corresponding to which addresses are present, and each of those blocks are equal. Proof. Consider the set of external addresses A = {� , . . .,� } ⊂ A of the gate operator� , and two �� 1 �−|�| ′ ′ successive sets of addressesA = {� . . .� } ⊆ A and A = {� . . .� } ⊆ A (both ordered as speciied in � 1 � �� �+1 �� the lemma and as seen in Fig. 11). Then, extract the smallest continuous varying B parts = {� ,� , . . .,� } �,�+1 � �+1 �+� ′ ′ ′ and B = {� , . . .,� } Ð also ordered the same way. Note that if� = � : �,�+1 � �+� B = {� ,� , . . .,� } �,�+1 � �+1 �+� � = � �+� +1 �+� We deine now a renaming� so that∀�,�(� ) = � . As a consequence, � always results in a identity block �+� �+� in the block column corresponding to the irst state and in the line of the second state Ðas this renaming preserves the relative order of such words on addresses. The renaming� is deined with the following case distinction: - Incrementation IfB is of the form{� }, then B is{� }. � is deined as the transposition swapping �,�+1 � �+1 �,�+1 � and � . � �+1 - Carry Else�, = 1. Then B = {� = � ,� ,� , . . .,� ,� } consists of� successive numbers inA �,�+1 � � �+1 �+2 �+� −1 �+� �� ′ ′ ′ with� > 0, and B = {� = � ,� , . . .,� ,� = � }. Therefore,� is deined as : 1 2 � −1 �+� +1 �,�+1 1 �+� (1) ∀� ∈ {1, . . ., �− 1},�(� ) = � � �+� (2) ∀� ∈ {�, . . ., �+ � − 1},�(� ) = � � �−�+1 ′ ′ (3) �(� ) = �(� ) = � = � , �(� ) = � �+� �+� �+� +1 �+� �+� �+� (4) �(�) = � for any other� ∈ A The property ∀�,�(� ) = � entails that �Π = Π , therefore :Π ��Π = � and Π ��Π = � . As �+� � �+1 �+1 � � �+1 � �+1 �+� �� = �� we have � = � . □ � �+1 ACM Trans. Quantum Comput. 34 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron C.5 From gate operators to(�,�)-nameblind matrices |�⟩ |���⟩ |�⟩ , |�⟩ |��⟩ |�⟩ , |�⟩ |�⟩ |��⟩ , |�⟩ |�⟩ |���⟩ , T I O T I O T I O T I O |�⟩ |��⟩ |�⟩ , |�⟩ |�⟩ |�⟩ , |�⟩ |�⟩ |��⟩ . T I O T I O T I O Fig. 12. The 7 subspaces with 3 external addresses of a one sector gate �,�,.and � represent a position of an address, spanned by any possible external address like in Fig. 8. Each one of the 49 blocks delimited by these subspaces contains a nameblind matrix. Proposition 4.7 (Decomposition of gate operators into (�,� )-nameblind matrices). Consider� a gate operator on addresses A which commutes with every external renaming. Consider any words on quantum data � & � , internal addressesA ⊆ � with positions� & � , external addresses A ⊆ A\� with positions� 1 ��� ��� ��� �� �� 1 2 1 & � . The action of� between states corresponding to these parameters� is a �� A ,A ,� →� ,� →� ,� →� ��� �� 0 1 ��� ��� �� �� 1 2 1 2 (�,� )-nameblind matrix with � = |A |. �� � � Proof. Let � be a gate and � = � a nameblind gate operator. First we decompose the large gate space H into 2|�| |Q | subspaces for each possible basis state of the dataspace. For each couple of basis|� states ⟩ ,|� ⟩ ∈ H 2|�| 0 1 we denote by � the block of� which maps states with data|� ⟩ to states with data|� ⟩. Since� is nameblind � →� 0 1 0 1 we have : Π ��|�⟩|� ⟩ = � � |�⟩|� ⟩ . � 0 � →� 0 1 0 1 On the other hand: Π ��|�⟩|� ⟩ = Π �� |�⟩|� ⟩ � 0 � 0 1 1 = �� |�⟩|� ⟩ � →� 0 0 1 where Π is the projector onto the subspace with data state � . These equalities imply that each block must � 1 commute with renamings. Furthermore, each � is block diagonal over subspaces � deined by a number of external addresses � →� � 0 1 � ∈ {0, . . .,|A \ �|} and a set of internal addresses A ⊆ �, because both parameters are preserved by �. We ��� cannot derive constraints between those diagonal blocks, since the subspaces � are preserved by renamings and gate operators. Then, we further divide the � subspaces into subspaces characterized by a ixed position for each internal addresses ofA , and � "slots" for external addresses. We enumerate these subspaces (see Figs. 8 and 12) and ��� denote them byH . Moreover, we write� = Π � where � is projection �ofontoH . Its coeicients are � � � [�,�] H H � � the same as the block of� in (block) column �and (block) line �. Let us show that this block is nameblind. Consider two subspacesH (corresponding to the block column/line �in�) and H (column/line �), and a � � renaming� that is external for �. We may for instance takeH with states of the form|���⟩ , where � ∈ � and �,� span all external addresses. The block � sp of ecifying what partH of goes toH is� . Let |w⟩ ∈ H be a � � � [�,�] state. On one hand, as |w⟩ and � |w⟩ both belong toH , they are handled by the same block column �of� (they are in the same subspace, as� does not modify or change the position �, of and make no internal address appear): Π (��|w⟩) = � � |w⟩ � [�,�] On the other hand : Π (��|w⟩) = Π (�� |w⟩) � � ACM Trans. Quantum Comput. Addressable quantum gates • 35 ︁ ︁ = Π ( � |�(� )⟩ + � |�(� )⟩) � � � � ∈H � ∉H � � = �( � |� ⟩) � ∈H = �� |w⟩ , [�,�] where in the third line we used�that preserves subspaces and thus commutes withΠ . As a consequence, for all |w⟩ ,� we have � � |w⟩ = �� |w⟩, and therefore� is nameblind. [�,�] [�,�] [�,�] Therefore, if a gate operator commutes with every renaming on external addresses, its matrix representation can be written blockwise with nameblind matrices. Vice versa, if a gate operator � can be partitioned blockwise as above into nameblind matrices, we can write ︁ ︁ ︁ ︁ ︁ ︁ �� = � � = � � = � � = ��. [�,�] [�,�] [�,�] � � � � � � When handling the nameblind blo � cks , we may simply consider that � is acting on a state of the form [�,�] |� . . .� ⟩ where � are external addresses, and ignore the internal addresses and the speciic subspaces in which 1 � � are the external addresses, as those does not change. Therefore, by Prop. 4.6 these operators are isomorphic to (�,� )-nameblind matrices and can hence be written blockwise (�,�)-nameblind as matrices by Thm. 4.4. D COMPOSING AQCS Several ways of composing AQCs are possible. Here we deine: Parallel composition of AQCs corresponds to executing them in parallel without interaction. Concatenation of AQCs corresponds to successively applying them to the quantum data. Connection of AQCs is also deined, and allows for a more general connectivity without assuming an intrinsic (temporal) order between AQCs. D.1 Parallel composition The simplest combination of AQCs is parallel composition, which intuitively means executing them both side by side, separately: Deinition D.1 (Parallel composition). Let A,B be two disjunct address sets, and let � and � be the corre- A B ≤� ≤� sponding AQC with skeletons � = (A,G ,D ,� ) and � = (B,G ,D ,� ) and states |� ⟩ and |� ⟩. A A A B B B A B A B ≤� +� Theirparallel composition� || � is deined as((A∪B,G ∪G ,Q ,� ),|� ⟩), whereQ = (D ∪D ) A B A B C C C C A B � ′ � and the scattering� applies �to∈ G the trivial extension � of� fromA to A ∪B and fromQ to Q , C A A C A A and similarly� ∈ forG . By trivial extension, we mean that � ∈if G , then � acts as the identity on addressesB ofand on data of Q \Q . C A D.2 Connection Explicitly including the sectors 1 and 4 in the Bell state creation circuit (see 1Fig. and 1) 6 of or se the ctors quantum switch (see Fig. 4a) helps distinguishing where the data is coming from and where it is going to. AQC are ininitely evolving systems and, as such, may not be perfectly itted to express inite computations. However, these sectors, which at irst sight seem superluous, provide a uniied template to portray inite quantum circuits, ACM Trans. Quantum Comput. 36 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron possibly followed by a measurement. In other words, they are useful to determine beginning and endpoint of a inite computation, and we use them as sectors where we place our initial data in and take the inal data out. Moreover, the presence of these sectors becomes crucial as soon as we want to compose AQCs and make them interact. Indeed, we will do so by identifying the outgoing sectors of an AQC, with the ingoing sectors of another. The following deinition paves the road to composing AQCs, by making it explicit which sectors can be identiied. Deinition D.2 (Ingoing and outgoing bufer sectors). Let ((A,G,Q,�),|�⟩) be an AQC and � ∈ A be an address. We call the sector�atan ingoing bufer sectorif • � does not occur in|�⟩, i.e. the sector cannot be targeted during the evolution, • {�} ∈ G, and {�} • � = � (the lip ś see A.1). Similarly, we call the se�ctor an outgoing at bufer sectorif • |�⟩ = |�⟩ ⊗ |�⟩, i.e. the state of the sector� is initially empty, • {�} ∈ G, and {�} • � = �. As a consequence, it is possible to łmergež outgoing with ingoing sectors into a single sector having the address of the outgoing bufer sector and the internal state of the ingoing bufer sector, for an example see Fig. 13b. merged bufer sector outgoing bufer sector ingoing bufer sector 1 3 7 1 3 7 5 9 5 6 9 � � 2 4 8 2 4 8 � � � � � A B � ⊙ � A {6},{5} B (a) Sector5 is empty, Sector6 is targeted by no one. (b) Sectors5 and 6 are merged. Fig. 13. Concatenating two AQCs� and � along {6} and {5}. In the end, sector5 is no longer an outgoing bufer sector A B and sector6 does not exist anymore. Deinition D.3 (Connection of AQCs). Let � ∈ N and � . . .� be AQCs with corresponding sets of addresses 1 � A . . .A so that∀�≠ �,A ∩A = ∅ and skeletons� = (A ,G ,Q ,� ). Moreover, let|�⟩ be the tensor product 1 � � � � � � � � of their (initial) states, I and andO the sets of their ingoing and outgoing bufer sectors. I =Let{� , . . .,� } ⊆ � � 1 � Ð Ð � � I and O = {� , . . .,� } ⊆ O such that I∩ O = ∅. The connection of� . . .� along (I, O) is denoted � 1 � � 1 � �=1 �=1 � = Conn(I, O,{� . . .� }) = ((A ,G ,Q ,� ),|� ⟩) 1 � C C C C C where � � Ð Ð • A = A \ I and G = G \{{�},�∈ I} is the set of addresses of � with corresponding gate C � C � �=1 �=1 set, Ë Ë Ë � � � • |� ⟩ = |� ⟩ ⊗ |� ⟩ when |�⟩ is of the form |� ⟩ , with the general case following by linear C � � � �=1 �∈A \O extension. ACM Trans. Quantum Comput. Addressable quantum gates • 37 � � Ð Í ≤� ≤� � • Q = ( D ) , where � = � and those � are such that Q = D . � � � � � �=1 �=1 • � is the trivial extension�ofasall in Def. D.1. � � The connection of an AQC with the trivial AQC, which consists only of a single empty sector, is the identity operation, given how ingoing and outgoing bufers are merged. Moreover, note that parallel composition is a special type of connection, where the connecting I and Osectors are empty, i.e. � || � = Conn(∅,∅,{� ,� }). A B A B With such a general notion of connection, one may connect an AQCs to form a loop, or even connect an AQC to itself Conn ( (I, O,{� })). The resulting AQC may be an evolving structure with neither ingoing nor outgoing bufers. Such constructions are of course not very physical, since they lack a way for quantum data to enter and or exit, and thus cannot be connected to any other AQC: For an AQC to correspond to a quantum circuit, it has to include at least one ingoing and one outgoing bufer. However, the AQC model as presented in this paper allows for the deinition of more general systems, without an input or an output node. Intuitively, such AQC are not physically implementable as a circuit in a satisfying way, as they lack a way for quantum data to enter and to exit it. They are still causal structures, as the evolution is driven by local reversible rules and gates may be applied on no data, i.e. vacuum states11 [ ]; no causality problem arises if some data enters the same sector twice during the ininite evolution. The alternative to composition with ingoing and outgoing bufers would have been to manipulate op ł en AQCž, i.e. featuring addresses that correspond to no sector, and then plugging these open AQCs together. This causes several problems however, as the transport step may be undeined, and renaming only one of the open AQCs may change the nature of the composition. D.3 Concatenation Another type of connection is a concatenation � :⊙ � = Conn(I, O,{� ,� }), where I only contains A I,O B A B addresses fromB and O only address fromA. Concatenation satisies some kind of associativity property: for all input (resp�.,output) � , � ,�sets : 1 2 � ∩ � = ∅ ⇒ (� ⊙ �) ⊙ � = � ⊙ (� ⊙ �). 1 2 � ,� �,� � ,� �,� 1 2 1 2 Without the condition to the left, the equality on the right holds, but may also be meaningless, as some sectors might have disappeared during the irst operation to be applied, or simply not be outgoing or ingoing anymore. Notice that similar to causal b27 oxes ] and [ contrary to quantum combs, the concatenation of two AQCs is an AQC. Example D.4. Let us concatenate the quantum switch� deined in Sect. 3.1 and the Bell state creation circuit � of Fig. 1 with address sets A = {1, 2, 3, 4, 5, 6} and B = {7, 8, 9, 0}, respectively. As unitaries in the quantum switch, take the Pauli gates � = � and � = � on a single qubit. Moreover, to facilitate matters|w � e⟩take = |�⟩ as initial state of the quantum switch so that after concatenation data is only present at the beginning of the Bell state creation circuit. We show in detail the steps of the evolution � and � concatenate of d along� = {0} and � = {1} in Fig. 14, wher�e⊙ � = Conn(�, �,{�,�}). �,� ACM Trans. Quantum Comput. 38 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron 1 3 5 � � � 7 8 9 � � � � � � 2 4 � � 345 � � � � � (a) Initial state of the concatenation � ⊙ � of the Bell state creation circuit and the quantum switch. �,� 1 3 5 � � � 7 8 9 (00+11) � � � � � 2 4 6 � � � 345 � � � � � (b) State of� ⊙ � ater the Bell state circuit. �,� 1 3 5 � � � 7 8 9 � � � � � � 2 4 6 � � � 345 � � � � (10−01) (c) łFinalž state of � ⊙ � ater the uantum Switch AQC. A global phase �is omited. �,� Fig. 14. Evolution of � ⊙ � , concatenation of two AQCs of Ex. D.4, with initial state 00 �,� Remark D.1. Outgoing bufer sectors correspond to the physical locations where the quantum data is measured. We do not discuss the possibility of measuring sectors here, yet it is straightforward to see how to do that. To represent a circuit with deinite beginning and end, one would execute the AQC until quantum data reaches an outgoing sector. E RELATION BETWEEN AQC AND QCGD Another approach to represent indeinite causal orders is to shun away from the circuit formalism and take inspiration from cellular automata. The QCGD frame 5] featur work [es quantum superpositions of graphs evolving synchronously according to unitary local rules. Each vertex has a local quantum state and communicates with other vertices via ports. Compared to AQCs, vertices have replaced gates and edges have replaced wires. Like QCGD, our model is able to represent a quantum superposition of diferent graphs (the graphs of connectivity between gates). The interdiction of non-causal evolution in QCGD may appear as contradictory with the sudden appearance of an edge in the AQC between nodes of diferent gates Ð for instance, when an address suddenly goes from the input address space to the target. However, by encoding address spaces into port names, one may simulate this seemingly non-causal edge appearance at the cost of having a larger number of ports Ðsee below . We can therefore encode any AQC into a QCGD. The reverse simulation is a challenging open problem. Encoding of AQC into the QCGD formalism. A gate operator can be encoded on local unitary rewritings, and multi-sector gates are implemented by connecting its sectors to a central common vertex, via a certain �. port A minor diiculty is that in an AQC, a sector may suddenly target seemingly faraway sector, whereas in a QCGD, vertices may only connect to closeby vertices. However, when an AQC does this, it is because the faraway sector’s address is a stored address. Therefore, we must encode stored address spaces as QCGD edges. ACM Trans. Quantum Comput. �� �� �� Addressable quantum gates • 39 � � {3} � � τ � � � � 1 2 {2,5} 5 6 � � {1} {6} 4 {4} Fig. 15. Ports of a sector verte�x, Fig. 16. Simplified representation of the encoding as a QCGD of the where A = {� ,� , . . .,� }. quantum switch. Notice that ports are not represented. Red nodes are 1 2 � gate-vertices, white nodes are sector-vertices. Red edges use the ports � , black edges link the target port τ to the entry port �, blue edges link output p�orts ��to entry ports�. For clarity purposes, the translation presented here3�has+ 1 ports and � + � vertices for an AQC with � sectors and � gates, but smaller, less trivial encodings are possible. Deinition E.1 (Encoding into QCGDLet ). � = ((A,G,Q,�),|�⟩) be an AQC. In the canonical basis of the circuit space|�,⟩ = � |� ⟩, where each � is a basis state. The superposition of quantum graphs �(�) = |G⟩ = � � � � � |G ⟩ encodes � , where each G is deined as follows: � � � � � • The set of vertices isV: = {� | � ∈ A} ∪ {� | � ∈ G} where the vertices{� | � ∈ A} represent the � � � sectors, while the vertices {� | � ∈ G} represent the gates and will be used to regroup all sectors of a same gate. • Each vertex has ports � = {� | � ∈ A}∪{�}∪{τ,�� ,�� , . . .,�� ,���,���, . . .,��� }. � 1 2 |A| 1 2 |A| The ports{� | � ∈ A} are used by the gate-vertices to connect to their sector-vertices and reciprocally. The ports {τ,�� ,�� , . . .,�� ,���,���, . . .,��� } are used to represent the target space, the input address 1 2 |A| 1 2 |A| space and the output address space of the sectors. Any edge from those ports is connected to the entry port � of the corresponding addressed sector-vertex. • The set of labels depends on|� ⟩. Each sector � having a quantum data space containing the state � ′ ′ |�⟩ |� ⟩ sees its corresponding verte�x being labelled(with �,� ). Each vertex � is labelled�with . � � Q Q � ′ � • The set of edges depends on|� ⟩. Each sector� having an address space containing the state |�⟩ |�⟩ |� ⟩ I O sees its corresponding verte�x have the following edges : {{� : ��,� : �} | ∀� ∈ �} � � � � ′ ′ ′ {{� : ���,� : �} | ∀� ∈ � } � � � � {� : τ,� : �} Moreover, each sector � is in a gate �, embodied by the edge : {� : � ,� : � } � � � � ACM Trans. Quantum Comput. ��� ��� ��� . 40 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron Remark E.1. The condition "address appear at most once in an AQC" in Def. 2.7 ensures that at most one edge uses the port � of any vertex. Deinition E.2 (Evolution of Encoding). The operator � = � � is the following quantum causal graph dynamic � � acting on|G ⟩ by changing the labels and edges of vertices according to the labels and edges of łnearbyž vertices: • � implements the transport step. It applies synchronously for ever{y�edge : τ,� : �} the following � � � evolution: – (Swap of input and output address spaces)For any �,�∈ [1 . . .|A|], the edges {� : �� ,� : �} disappear � � � and are replaced by{� : ���,� : �}, while edges{� : ���,� : �} disappear and become edges � � � � � � {� : �� ,� : �} � � � – (Swap of input and output data spaces)Let � be the second part of the label of verte � .xLet � be the irst part of the label of verte � .xAfter applying � , the second part of the label of verte � xbecomes �, and � � � the irst part of the label of verte � bxecomes � . • � implements the scattering step. It is synchronously applied�on∈evV ery of label � , corresponding � � to the gate � ∈ G, and can be explained by the following substeps : (1) Remember that the vertices{� | � ∈ �} are exactly the neighbours of verte � x. One builds the state of � � the equivalent AQC-gate space : � � |�⟩ = |�⟩ , �∈� where each |�⟩ is build from the quantum labelled graph: – The target space is|�⟩ if there is an edge {� : τ,� : �}. Else, it|is �⟩. � � – The input address space contains the (potentially empty)�w=or�d . . .� where, for each edge 1 |A| {� : ��,� : �}, � = �. If there exists no such edge for some �∈ [1 . . .|A|], the corresponding� is � � � � � equal to�. – The output address space is illed like the input address space, by replacing �� byeaver ��y� in the � � line above. ′ � ′ � – Let (�,� ) be the label of verte � x. The input and output address spaces of sector� are |�⟩ |� ⟩ . Q Q (2) � (obtained from the label of verte � ) is x applied to the gate space |�⟩ , which therefore becomes �∈� � � ′ � |� ⟩ = � |�⟩ �∈� (3) The edges and labels are rewritten from the state |� ⟩ , using the construction explained in step 1 (and Def. E.1). in the other directionÐthis time constructing the subgraph (or potentially a superposition of subgraphs) from the gate space. Proposition E.3 (Eqivalence of Evolution of Encoding). Let � be an AQC. Then �(�� ) = ��(�) where � = � � implements the AQC evolution operator� = �� and with� as in Def. E.1. � � F NOTATIONS Let S be a inite set. We denote by� inite strings with alphab S, i.e et �. = � � . . .� with� ∈ S. Moreover, � 1 2 � � denotes the empty string. Words of addresses written as letters with overlines �) may b(e of length 0. Letters without overline �) r(epresent words of length 1. From a inite setS we construct the Hilbert spaceH = C = { � |�⟩ ,� ∈ C} with scalar product⟨�|�⟩ = � ′. In other words, to each element�∈ S is associated a unit � � �,� �∈S vector |�⟩, such that the family (|�⟩) is the canonical orthonormal basis H .of IfS were countably ininite, �∈S S we would have ensured square-summability by taking H = ℓ (S). The other notations used in the paper are summarized in Tab. 1 on the next page. ACM Trans. Quantum Comput. Addressable quantum gates • 41 Notation Deinition Occurrence A A set of addresses, namely, a inite subsetNof . Def. 2.1 G A set of gates, namely, a partition of some A. Def. 2.6 T A set containing all addresses and the empty addr �,ess called set ofDef. 2.1 targets. W The set of words on addresses where no address repeats.W = Def. {� . . .� |� ∈ A,� ≠ � ∀�, �} 2.1&A.1 1 � � � � � A list of addresses. It usually denotes an element W orofW ⊗W. Def. 2.1 D A inite set, called set of data values. Def. 2.3 ≤� Q The set of data words of length at most � for some� ∈ Nś i.e.Q = D . Def. 2.3 � An element inQ. Def. 2.3 ∀S,H The Hilbert space constructed from any set S as speciied in Sect. F Sect. F H Hilbert space onT called target space. Def. 2.1 H Hilbert space onW called stored address space. Def. 2.1 H Hilbert space onQ called data space. Def. 2.3 H Input space. It is the tensor product ofH andH . Def. 2.4 � W Q H Output space. It is the tensor product ofH andH . Def. 2.4 � W Q H The sector space associated to�. It is the tensor product ofH ,H and Def. 2.4&2.6 T � H . � � � H The sector space associated to a gate� ⊂ A :H = H Def 2.6 �∈� H Circuit spaceH. = H Def. 2.7 �∈A |�⟩ A basis state ofH . Eq. 5 |�,�⟩ A basis state ofH . Ex. 2.9 |�,�⟩ A basis state ofH . Eq. 7 |�,�⟩ A basis state of the output space of sector �. Eq. 2 |�,� ⟩ A basis state ofH ⊗H . Eq. 5 W W W � � |�,� ⟩ A basis state ofH ⊗H . Eq. 5 Q Q Q � � |�⟩ A basis state of the i-th sector space. It can be decomposed either asDef. : 2.8 � � � � � ′ ′ � ′ ′ |�⟩ |�,�⟩ |� ,� ⟩ or as : |�⟩ |�,� ⟩ |�,� ⟩ O W Q T I T |�⟩ Where � ∈ {T,W,Q} is the corresponding space of the �-th sector. Def. 2.8 |32⟩ The state |3 2⟩ (ketśthreeśtwo), while being distinct from the state Ex. 2.2 |32⟩ (ketśthirtyśtwo), is always written as|32⟩ . This causes no confu- sion, as only address sets with fewer than ten addresses are used in this paper. � The scattering step. Def. 2.8 � The transport step. Def. 2.8 � � = ��, the global evolution operator. Def. 2.8 Table 1. Notations used in the paper ACM Trans. Quantum Comput. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Quantum Computing Association for Computing Machinery

Addressable Quantum Gates

Download PDF
41 pages

Loading next page...
 
/lp/association-for-computing-machinery/addressable-quantum-gates-EwuehCVRrt
Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Copyright held by the owner/author(s).
ISSN
2643-6809
eISSN
2643-6817
DOI
10.1145/3581760
Publisher site
See Article on Publisher Site

Abstract

PABLO ARRIGHI, Université Paris-Saclay, INRIA, CNRS, LMF, France and IXXI, Lyon, France CHRISTOPHER CEDZICH, Quantum Technology Group, Heinrich Heine Universität Düsseldorf, Univer- sitätsstr. 1, 40225 Düsseldorf, Germany MARIN COSTES, ULYSSE RÉMOND, and BENOÎT VALIRON, Université Paris-Saclay, CNRS, Centrale Supélec, LMF, 91190 Gif-sur-Yvette, France We extend the circuit model of quantum computation so that the wiring between gates is soft-coded within registers inside the gates. The addresses in these registers can be manipulated and put into superpositions. This aims at capturing indeinite causal orders and making their geometrical layout explicit: we express the quantum switch and the polarizing beam-splitter within the model. In this context, our main contribution is a full characterization of the anonymity constraints. Indeed, the names used as addresses should not matter beyond the wiring they describe, i.e. quantum evolutions should commute with łrenamingsž. We show that these quantum evolutions can still act non-trivially upon the names. We specify the structure of łnameblindž matrices. CCS Concepts: · Theory of computation→ Quantum computation theory. Additional Key Words and Phrases: models of distributed quantum computing, anonymous, identity-oblivious, alpha equiva- lence, name-invariance, covariance, markovian dynamic graphs, timed quantum circuits, clocked quantum circuits, quantum causal graph dynamics, quantum controllable quantum circuits, quantum FPGA. 1 INTRODUCTION The standard paradigm for quantum computation is the coprocessor model. In this model, quantum evolution is controlled by a purely classical device Ða conventional computer. Quantum computation is described as the list of elementary instructions Ðthe quantum gatesÐ sent to the coprocessor: the so-called quantum circuit. This representation has long been thought of as the most viable model of quantum computation, and it has been successful in realizing sizeable complexity gains on numerous useful algorithms. Several other models of quantum computation have been designed to ofer other quantum computing possibili- ties, compared to the usual circuits (wire/gate) vision Ðnotably : one-way computing 29], quantum [ walks23 [ ], adiabatic computing 1], hybrid [ models and many more, some of which already proved their practical use time and time again. However, even when sticking to the wire/gate point of view, one quickly notices that in the coprocessor model only the data is quantum. The control low, i.e., the order in which the gates are to be applied, is classically determined and deinite. In other words, the wiring between the gates is ixed and, albeit quantum, the data lows through the circuit in a deinite, classical manner. Quantum mechanics allows for more:10in ] it [ was argued by constructing a new elementary circuit, the so- called quantum ł switchž, that classically ordered gates are not the only possible paradigm of quantum computation. Instead, the quantum switch behaves like quantum a test: given a qubit � and a single instance of gates � and � , Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for proit or commercial advantage and that copies bear this notice and the full citation on the irst page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). © 2023 Copyright held by the owner/author(s). 2643-6817/2023/2-ART https://doi.org/10.1145/3581760 ACM Trans. Quantum Comput. 2 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron the operationSwitch(�)(� )(�) realizes |0⟩ ⊗ |�⟩ ↦−→ |0⟩ ⊗ (�� |�⟩), � � (1) |1⟩ ⊗ |�⟩ ↦−→ |1⟩ ⊗ (�� |�⟩). � � Adding the quantum switch to a circuit renders the orders ofindeinite gates [10, 21, 26]: the order in which � and � are applied depends on the state of the contr ł olž qubit �. Hence, addingSwitch enables dataand computation to be in superposition. Notably, the quantum switch is not realizable in the coprocessor model, when only one instance�ofand � is available 10]. Y[et, it was shown to be realizable in experiments 19, 28, 30 [ , 31]. Moreover, it allows for gains in terms of communication 9, 22, 35] and [ algorithmic complexity compared to textbook circuits [2]. In the recent years, several attempts have been made to encompass indeinite causal orders within a consistent model of quantum computing. A considerable strand of works focuses on the compositionality of indeinite causal orders, via sums of diagrams in the process theory of quantum mechanics 36], or higher-or [ der circuits featuring type annotations for that speciic purp 6], ose some [ for routing per subspace32[], other to enforce the time-ordering of packets 27].[ In all these proposals however, the low of information may be superposed, but it remains static. A more recent strand of works works by distinguishing data qubits from external control qubits [11, 34]. The latter are used to encode the order in which gates are to be applied upon the former. Because the control qubits can be manipulated coherently and conditionally, the low of information is both dynamical and quantum, i.e. łsecond-quantisedž in the language of [11]. In this paper we introduce a new model of quantum computation, not by extending textbook quantum circuits in a ad hoc manner (e.g. adding quantum switches 2], p [ olarizing beam splitters 7, 12] [etc.) but by introducing a single new principle encompassing all of these constructs and hopefully more. The basic idea is that gates are no longer hardwired to one another. Instead, the wiring is soft-coded: each gate contains a register storing addresses of the gates it targets. We therefore call such gates Addressable Quantum Gates (AQG). Those address registers are quantum, hence target addresses can be superposed, and so output data may be sent to diferent places, in a superposition. Moreover, addresses can interact with the data and be entangled with it. Thereby, addresses may be sent to other gates in anAddressable Quantum Circuit(AQC), which naturally leads to evolving superpositions of causal orders. That is, in contrast to the models 6, 27 in , 32 [ , 36] that also encompass indeinite causal orders, our model allows for quantum dynamic routing. Furthermore, compar34 ed] w toe[allow for vacuum states and the increased compositionality that follows. Moreover, we express the geometry not through external control qubits, but via address registers placed directly within each gates, which allows for a clearer geometrical layout, in the spirit of process algebras. Besides naturally encompassing indeinite causal orders, the AQC model also extends distributed quantum computing in several aspects. Historically, the search for distributed models of quantum computing has mainly focused on static networks and on classically evolving netw 20]. orks Recently [ , the notion of a Quantum Causal Graph Dynamics (QCGD)5[] has borne the premises of a fully quantum distributed model of computation, where the connectivity of the network is allowed to evolve coherently and ind itself in a superposition. The corresponding mathematical framework 4], ho [ wever, is rather abstract and axiomatic. A model of computation should be constructive. This is the case of the hands-on, bottom up approach presented here: we provide a concrete, composable model of distributed quantum computation featuring local synchronous updates as in the Local model, as well as quantum evolving connectivity in the spirit of classical markovian graph dynamics models [13]. Classically it is well-known that the computing power of distributed algorithms crucially depends on the availability of a unique identiier at18 each ]. Frno omdea[more physical point of view, we may indeed consider that these identiiers, a.k.a., łnamesž are iducial, serving just to describe the network or laying out a coordinate system upon it, when really only the geometry should matter. The limitations brought by this requirement (cf. ACM Trans. Quantum Comput. Addressable quantum gates • 3 ‘anonymous networks’ [16], ‘identiier-oblivious’ algorithms 17] in distribute [ d computing, ‘renaming-invariance’ [3] or ‘covariance’ in the Physics literature) are thoroughly studied here in the context of our model. We remark that the questions of 1) the actual gain over the textbook quantum circuit model brought by indeinite causal orders in general and the quantum switch in particular, and 2) whether the current physical implementations of the quantum switch actually realize this gain, is subject of ongoing scientiic discussions. Perhaps one of the strongest attempts to settle this debate is the notion of the time-delocalized system implementation of indeinite causal order developed in 25, [33]. To some extent, the controversy surrounding this łgainž has to do with how the gain is deined and quantiied. For instance, we could be counting the number of łusagesž of gates as in standard oracle complexity. Likewise, we could be counting the number of łphysical implementations" of gates, supposing that each of them requires much experimental care. It is not obvious that the quantum switch, at least in its current experimental implementations, provides any łusage gainž. It does if we only count as łusagež the number of times the gate is traversed by data, but it is not clear why one should not count those times it is traversed by the łvacuum statež [ 11]. On the other hand, it seems clear that, contrary to standard quantum circuits, these experiments factor out the number of physical implementations of gates. In that sense, our model provides some clariication, because each physical implementation of a gate is in one-to-one correspondence with one addressable quantum gate: the reusing of physically implemented resources is made explicit. We leave for future work question whether AQC implementations of indeinite causal orders correspond to (or help express) time-delocalized implementations. Our contributions are the following: • A novel computational paradigm Ðcalle Addrdessable Quantum Circuits Ð generalizing textbook quantum circuits, so as to make the low of information quantum (Sect. 2). • Showing that this quantum low of information allows for indeinite causal order. We demonstrate this below by encoding the quantum switch and the polarizing beam splitter (Sect. 3). • A restriction of the model so that the actual names used as addresses do not matter beyond the wiring they describe, i.e. ‘disallowing pointer arithmetic’ in the manner of Java... • ...which led us to solve the following linear algebra question as a natural byproduct: say that a matrix acts on the Hilbert space spanned by|���...⟩, |���...⟩, |���...⟩ in a way that commutes with renaming � into� etc. What is this matrix allowed to do? Can it still create superpositions? We provide a full, constructive characterization of such łnameblindž matrices. Whilst strongly structured, they still admit non-trivial behaviors. It is our main technical contribution (Sect. 4). • The compositionality of the model is formalized (Appendix D). The physicality of the model is discussed with comparison with other frameworks (Section 5). Notations are summarized in Appendix F. 2 THE MODEL Quantum algorithms, whether they are distributed or not, are consist of two steps. Firstly, a quantum circuit is operated on the input quantum data Ð possibly in an iterative fashion. In the second step, the resulting quantum state is measured.Addressable Quantum Circuits(AQCs) represent a novel description of the irst part. More precisely, each iteration of an AQC is one step of propagation of quantum data in the circuit, where gates can be applied in a superposition. Such physical locations in the laboratory are abstracte sectors in d into the AQC formalism. Each sector is uniquely identiiedaddr by an ess taken in a inite set AÐsee Def. A.1. Several sectors can be grouped together to formgates, which determine the level of granularity at which łlocalž gateunitar operators y are applied. These concepts are formally introduced in this section. To establish familiarity, we encode the usual Bell state creation circuit as an AQC. This requires four sectors withAaddr = {esses 1, 2, 3, 4} Ðsee Fig. 1a. ACM Trans. Quantum Comput. 4 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron 1 2 3 4 |0⟩ |00⟩+|11⟩ |0⟩ (a) Bell state creation as a textbook quantum circuit 2 3 H 4 1 I I I (b) Bell state creation as an addressable quantum circuit Fig. 1. Dashed boxes represent sectors. (a) Textbook quantum circuits require a background layer that implies a time ordering, here shown explicitly in light purple. (b) The AQC formalism frees the information flow from the background surface. Each sector has a target space, holding a target address, as represented by the arrows. Addresses could have been taken in any other integer set instead. 2.1 Addresses and sectors In the following H denotes the Hilbert space whose canonical orthonormal basis {|�⟩} is. To each address we X �∈X associate a sector, i.e. a connectable device which stores quantum data. The main novel feature of our formalism is its ability to manipulate and superpose addresses, and thus the connectivity between sectors. To this end, each sector has a target address space H to determine where the output data is to be sent. Additionally, it can store other addresses in its stored address spaces H . By locally acting on these spaces we may shule addresses, possibly into a superposition. Deinition 2.1 (Target address space, stored address space).Let the set of addressesA be a inite set of integers. ≤1 ? A target address space is a Hilbert space H , where T ≡ {�|� ∈ A } = � is the set of words onA of length at most 1. In contrast, basis states of stor a ed address space H can contain multiple addresses, but each address at most once. Thus,H is a Hilbert space speciieW d by≡ {� = � ···� |� ∈ A,� ≠ � ∀�, �} = A , the set of W 1 � � � � words on A with all diferent letters. −� Example 2.2. WithA = {2, 3}, the vector (|2⟩ + � |3⟩ + |3 2⟩ + |2 3⟩)/2 is a valid stateHof . For the Bell state creation circuit, just like for any textbook quantum circuit encoding, the stored address spaces are unused and the target address spaces remain ixed. Specifying the target addresses for each sector makes the underlying background layer redundant: we might just as well dismantle the circuit as in Fig. 1b. In other examples with dynamically evolving wirings, the circuit may even be in a superposition of several arrow conigurations Ðsee e.g. Fig. 4b. Such superpositions of wirings induce superpositions of orders of applications of gates on the quantum data stored inH : Deinition 2.3 (Data space).Let D be a inite set of possible data values. The set of words on data of length at ≤� most � is denoted byQ = D . SinceD is inite, soQis . The Hilbert spaceH is referred to as data a space. ACM Trans. Quantum Comput. Addressable quantum gates • 5 Each sector contains two storage spaces : one for the input and one for the output, and both can store addresses and data. Each of these subspaces may be empty, in which case we denote its state�.by Sectors with empty data spaces correspond to vacuum states [11]. The purpose of such output and input spaces is explicitated in Sec. 2.3. Deinition 2.4 (Input and output space, sector space).An input (resp. output) spaceis a Hilbert space H (resp. H ) of the formH ⊗H . A sector space is a Hilbert space of the form H = H ⊗H ⊗H . To each address O W Q S T I O � ∈ A is associated a sector spaceH . We write basis states of input (resp. output) spaces|�,as �⟩ (resp. |�,�⟩ ), where � ∈ W and � ∈ Q. Basis I O ′ ′ states of a sector may be expressed as|�⟩ |�⟩ |�⟩ |� ⟩ |� ⟩ ∈ H ⊗ H ⊗ H ⊗ H ⊗ H or, by T W Q W Q T I O I O � � � � ′ ′ reordering the tensor factors as|�⟩ |�⟩ |� ⟩ |�⟩ |� ⟩ ∈ H ⊗H ⊗H ⊗H ⊗H Ðsee Fig 2. T W W Q Q T I O � O � � � � I O H H W W � � H H Q Q Q � � Fig. 2. (a) A sector. (b) Stored addresses vs. quantum data. (c) Input vs. output spaces. When all output (resp. input) spaces are empty, we only represent the input (resp. output) spaces, as in Fig. 4b. Example 2.5. WithA = {1, 2, 3, 4} as in Fig. 1a andQ = {00, 01, 10, 11,�}, the states |�,10⟩, |3,�⟩ and |23, 11⟩ are basis states forH andH . E.g. |�,11⟩ + |2,�⟩ and |2, 11⟩ are orthogonal. I O Moreover, |3⟩ |2, 01⟩ |�,�⟩ is a basis stateH of . T I O The state of the quantum system at any point of its evolution is described by a sum of tensor products of states of each of its sectors. E.g. in the beginning of the execution of the Bell state creation circuit Ðsee Fig. 1a, the quantum system is in the state|� ⟩: 1 1 1 � � � � |� ⟩ = |2⟩ ⊗ |� , 00 ⟩ ⊗ |� ,� ⟩ (sector 1) T I � 2 2 2 � � � � ⊗ |3⟩ ⊗ |� ,� ⟩ ⊗ |� ,� ⟩ (sector 2) T I � (2) 3 3 3 � � � � ⊗ |4⟩ ⊗ |� ,� ⟩ ⊗ |� ,� ⟩ (sector 3) I � 4 4 4 � � � � ⊗ |�⟩ ⊗ |� ,� ⟩ ⊗ |� ,� ⟩ (sector 4) I � 2.2 Addressable Gates A gate is composed of multiple sectors, and thus can receive information from and send information to multiple sources and destinations. This grouping of sectors into gates deines a notion of locality for the evolution: during a łscattering stepž a gate acts upon its constituent sectors with a local unitary. Deinition 2.6 (Gates, Gate Operators).A gate � is a (non-empty) subset of a set of addressesA, and the set of � � gates G is a partitionAof . The gate space of a gate� consists of|�| sectors and is given byH = H . A �∈� S � � � gate operator on � ∈ G is a unitar�y : H → H which preserves the addresses of the target and stored spaces, ′ ′ ′ ′ ′ i.e⟨.� � | � |� �⟩ ≠ 0 implies that � has the same letters as�, where � and � (resp. �,� ) list all target and stored addresses (resp. all data) in sectors�.of ACM Trans. Quantum Comput. 6 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron In general, gates act as the identity on the empty state �. The gate operators of the Bell state creation circuit are given by {1} {4} {2} {3} � = � = � , � = �((� ⊗ �) ⊗ � ), � = �(Cnot ⊗ � ), (3) I O I O where � swaps the input and output systems. Note that neither data nor addresses are manipulated in se 1ctors and 4, yet they are required to compose this AQC with other AQCs Ðsee Sect. D. The overall state space of an AQC is the tensor product of its sector spaces together with an additional global condition: to guarantee the reversibility of the transport step that will be deined below, we require that each address appears at most once. Deinition 2.7 (Skeleton, Addressable Quantum Circuit). A skeleton � is a tuple(A,G,Q,�) where: • A is the set of addresses, • G is the set of gates, • Q is the set of data Ðconsisting of words on data of length at �most , • � is a function associating a gate operator � to each gate � ∈ G. This speciies the sector spacesH as = H ⊗H ⊗H ⊗H ⊗H . S T W Q W Q The circuit Hilbert spaceH is deined as H restricted to superpositions of basis states where addresses �∈A appear at most once. An Addressable Quantum Circuitis a tuple� ,(|�⟩) that speciies both the dynamics and the current state, i.e�. is a skeleton and|�⟩ is a state ofH. For example, consider the skeleton of the Bell state creation circuit shown in Fig. 1b. It is A = speciied by {1, 2, 3, 4},G = {{1},{2},{3},{4}},Q induced byD = {0, 1} and � = 2, and � as in(3). In Ex. 2.9 below we choose the initial state of (2). Reordering tensor factors as above, we|�obtain ⟩ = |2, 3, 4,�⟩ |00,�,�,�⟩ |�,�,�,�⟩ . T I O 2.3 Evolution The overall evolution alternates a scattering step during which the gate operators are applied to their respective gates, and a transport step that swaps the output space of each sector with the input space of the sector it targets. The evolution is unitary i.e. it does not involve measurements. O I O I � � � � ′ ′ ′ ′ |�⟩ |� ⟩ |�⟩ |� ⟩ |�⟩ |�⟩ |� ⟩ |� ⟩ |�⟩ |�⟩ |�⟩ |�⟩ ′ ′ ′ ′ |�⟩ |� ⟩ |�⟩ |�⟩ |�⟩ |� ⟩ |� ⟩ |� ⟩ (a) Sectors�and �before the transport step. (b) Sectors�and �ater the transport step. Fig. 3. Efect of the transport step upon two connected sectors Ðsee example A.2. Here and elsewhere in the paper arrows represent the content of each target space. If the state of the target space is a superposition of multiple addresses, one arrow points to each target. Deinition 2.8 (Evolution).An addressable quantum circuit ((A,G,Q,�),|�⟩) evolves in one time step into the ′ ′ addressable quantum circuit ((A,G,Q,�),|� ⟩), where |� ⟩ = � |�⟩ with� = �� and: � � Scattering � is the application of� , i.e. the gate operators� are applied simultaneously on their corre- sponding gate spaces. ACM Trans. Quantum Comput. Addressable quantum gates • 7 Transport � is a permutation of basis states, extended linearly H. The to permutation maps synchronously each � � � � � � triple of the form |�⟩ |�⟩ |�⟩ to|�⟩ |�⟩ |�⟩ , leaving the rest (of the basis state) unchanged. That is, the T O T O I I � � � � � � � � � � transport step maps a basis state|�⟩ |� ⟩ |� ⟩ ⊗ |�⟩ |� ⟩ |� ⟩ ⊗ |�⟩ to |�⟩ |� ⟩ |� ⟩ ⊗ � � T � I O � �∉{�,�} T � I � T I O � � � |�⟩ |� ⟩ |� ⟩ ⊗ |�⟩ . Colloquially, when Se �targets ctor Sector �, �’s output space is swapped � � �∉{�,�} T I O with�’s input space Ðsee Fig. 3. The necessity of the requirement that each address appears at most once becomes clear now: it is essential for the transport step to be well-deined by avoiding that a sector is targeted by more than one other sector, as the output space of a sector�are swapped with the input space of the sector targeted�by . The addresses stored in output and input spaces, referencing some future sector that would be addressed later, low throughout the system just as the quantum data does. It is only required to store in input or output spaces the addresses of the sectors that will be addressed by a quantum superposition of diferent sectors. Example 2.9. Let us describe step-by-step the Bell state creation circuit of Fig. 1. We drop the stored address space which are always empty. In Ex. A.3 we further break down the evolution� into and � . The blue and red terms (and, later, arrows Ðsee Fig. 5) are superposed, and get entangled: |2, 3, 4,�⟩ ⊗ |00,�,�,�⟩ ⊗ |�,�,�,�⟩ T I O −→ |2, 3, 4,�⟩ ⊗ |�,00,�,�⟩ ⊗ |�,�,�,�⟩ T I O −→ |2, 3, 4,�⟩ ⊗ |�,�,00,�⟩ + |�,�,10,�⟩ ⊗ |�,�,�,�⟩ T I I O −→ |2, 3, 4,�⟩ ⊗ |�,�,�00 , ⟩ + |�,�,�11 , ⟩ ⊗ |�,�,�,�⟩ � T I I O −→ |2, 3, 4,�⟩ ⊗ |�,�,�,�⟩ ⊗ |�,�,�00 , ⟩ + |�,�,�11 , ⟩ (∗) T I O O −→ |2, 3, 4,�⟩ ⊗ |�,�,�,�⟩ ⊗ |�,�,00,�⟩ + |�,�,11,�⟩ T I O O ··· The inite execution of usual circuits corresponds to a inite sequence of iterations in the otherwise potentially ininite evolution of AQCs. E.g. in order to match the corresponding textbook circuit, the AQC above needs to be stopped after step (∗). 2.4 Composability of AQC The fact that the connectivity of gates is soft-coded in the AQC model, leaves room for several ways of composing AQCs. In Appendix. D we propose formal deinitions for: Parallel composition of AQCs, corresponding to executing them in parallel without interaction. Concatenation of AQCs, corresponding to successively applying them to the quantum data. Connection of AQCs, alllowing for a more general connectivity without assuming an intrinsic (temporal) order between AQCs. The last of these even allows for indeinite causal order. For now let us show how indeinite causal order may happen within one AQC. 3 WHAT CAN IT DO? Using the Bell state creation circuit as a guiding example, we illustrated how textbook quantum circuits can be implemented in this framework. We argued that textbook quantum circuits only require hardwired one-sector gates in the sense that the connectivity of the graph is static and deinite H is , i.e in . a ixed basis state and H andH are empty. W W � � ACM Trans. Quantum Comput. 8 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron As argued in the introduction, there exist physical devices that allow for superpositions of causal orders. These devices lie beyond the scope of hardwired circuits, in that they cannot be described by the textbook circuit framework without extending the workspace or waiving knowledge about the internal workings of the gates by using all-encompassing gates. We now describe how such causal superpositions arise naturally by superposing addresses in AQCs. 3.1 The quantum switch The quantum switch described (1) inapplies unitaries � and� to � qubits in a superposition of causal orders that depends on a control qubit Ðsee Fig. 4a. We can encode Switch as the AQC of Fig. 4b, wherA e = {1, 2, 3, 4, 5, 6}, ≤� +1 G = {{1},{2, 5},{3},{4},{6}}, and Q = {0, 1} contains� controlled qubits plus one control qubit. The gates {3} and {4} apply unitary operators � and � to the � controlled qubits, whereas the gate {2, 5} implements the quantum switch itself. 1 1 2 5 As initial state we cho|�ose⟩ = |2⟩ |��⟩ |345⟩ |6⟩ , where |�⟩ = � |0⟩+ �|1⟩ ∈ H denotes the control 0 D T Q W T � � qubit and|�⟩ are the � controlled qubits. All non speciied spaces are empty, i.e. they ar|e�⟩in . state 1 3 5 1 2 3 5 6 � � � ��� 1 . . . . � � ��� 0 . . |�⟩ QS 2 4 6 . . . . � � � . . |�⟩ � � � (a) Textbook-like representation of the uantum Switch.(b) AQC representation of the uantum Switch during its execution. Red and blue data and targets are superposed. Fig. 4. Superposing causal orders by superposing addresses. Let us explain the behavior of this AQC, see Fig. 5. For the sake of brevity, when specifying scatterings by their action on basis states, non-represented spaces are understood to be empty, i.e. in�.state Moreover, scatterings are understood to act as the identity on unspeciied basis states.2Seinitially ctor contains addresses {2,5} 3, 4 and 5 as output stored addresses. When the data enters this sector, the gate operator� superposes 2 2 the addresses 3 or 4 in the target space (Fig. 5a) according to the control qubit,|�⟩e.g.|345⟩ |��⟩ ↦→ T W Q O I 2 2 2 2 2 2 � |3⟩ |45⟩ |�0⟩ + �|4⟩ |35⟩ |�1⟩ . It is then transported to sectors3 (resp. 4) as shown in Fig. 5b. T W Q T W Q O O O O There, � (resp. � ) is applied, and the target space of the respective sector is illed by the irst address of the stored address space (Fig. 5d). The data continues its journey, and � (resp. � ) is applied in Se4ctor (resp. 3). The two branches meet in Sector5 (4b). The data halts here, while the target addresses fold back and the quantum switch reverts to its former, non entangled state. Then all data low to Se 6. ctor The mathematical details are found in Appendix A.2. The addresses low back within the AQC from steps 5 to 8. This means that the addresses low from the input space of a targeted sector to the output space of a targeting sector. These steps are essential to guarantee that the data can interfere outside of the AQC, i.e. that no intrication remains between quantum data and the quantum switch. It is crucial to note that one cannot initialize this AQC with the addr 6,ess which of Seis ctoralways accessed from Sector5, in the input or output spaces of Sector 2, since otherwise the AQC would still be entangled with the output data after the addresses lowed back. ACM Trans. Quantum Comput. Addressable quantum gates • 9 {3} {4} The gate operators � and � act both on a single sector spaceH as they are one-sector gates. Both can be decomposed into 1) a gate acting onH handling the swaps between the subspaces of the sector � ( in S 34 ≤� +1 Appendix A.2.1), and 2) a gate applying � or � on the respective data spaceH , where Q = Q . The Q O 3 4 subsystems whose causal order is in superposition are therHeforand e H , see also25 [ ]. In other words, the Q Q O O gate applies � (or � ) on a state consisting 0ofqubits or� + 1 qubits.� (or � ) is any unitary acting�onqubits as it does not take into account the irst qubit, i.e., the control qubit that was used in{2the , 5}gate . We refer the reader to Appendix A.2.1 for details. 3.2 The polarizing beam spliter In a Polarizing Beam Splitter (PBS), birefringent material separates an incident beam according to its polarization Ðsee Fig. 6a. A transmitted photon moves toward a device denoted by A that rotates the polarization angle of the light, and after that, moves toward a similar device denoted by B that rotates the polarization in a diferent way. By using two PBS, the relected version of the photon encounters B irst, then A. The end result of the polarization in this case is diferent. There are two quantum paths: either A occurs before B, or B occurs before A, yielding an indeinite causal order. Indeinite causal orders are related to the time order of the evolution of the underlying quantum system. In the irst case, A causally inluences B so that if A had not occurred, then B’s input and output would be totally diferent. Conversely, in the second case, B causally inluences A. PBS are thus used in the literature to implement indeinite causal 7, 12or , 21 ders ], as [ in PBS the physical location of quantum data is itself quantum. Therefore, AQCs are well-suited to represent such devices, unlike textbook circuits which are ignorant towards locations. Here, we consider a PBS where horizontally polarized photons (� ) pass through the bifringent material, while vertically polarize(�d) ones are relected without phase shift. Photons as the physical carriers of data are represented by Fock states with a inite number of particles, and are further distinguished by their polarization. We represent this PBS as an AQC((A,G,Q,�),|� ⟩), withD = {0 , 1 , . . .� } × {0 , 1 , . . .� } for some 0 � � � � � � ≤1 integer� being the total number of photons present in the cirQcuit, = D , A = {1, . . ., 8}, and G = {1,2,3,4} {{1, 2, 3, 4},{5},{6},{7},{8}}. The irst gate� corresponds to the PBS itself, as shown in Fig. 6a. Sectors 5− 8 provide the context in which the the PBS is evolving and thus play the same role as the 1 and Sectors 4 of the Bell state creation AQC and the Sectors 1 and 6 in theSwitch AQC. In this AQC, photons can enter the {1,2,3,4} PBS from any direction. The gate operator � makes them travel to the right sector depending on their polarization (Fig. 6a). They exit or enter the PBS during the transport step (Fig. 6b). � �−4 � We choose the initial state |� ⟩ = |�− 4⟩ |�⟩ |� ⟩ where the |� ⟩ represent entry photons Ðsee 0 � � T T �=5 Q Fig. 6b, or a superposition of such |� ⟩. The content of the target spaces entails that each entry of the PBS may communicate only with the sector in front of it. {1,2,3,4} The gate operator of the PBS gate� acts on general states of the Sectors 1 to 4 as 4 4 Ì Ì {1,2,3,4} � : |�+ 4⟩ |� ⟩ |� ⟩ ↦−→ |�+ 4⟩ |� ⟩ |� ⟩ , (4) T � � � � T �(�) ℎ(�) � � �=1 �=1 where � (resp. ℎ) is the function associating to a sector’s vertical (resp. horizontal) polarization the sector indicated in Fig. 6a: �(�) = �mod 2+ 1+ 2⌊�/2⌋ and ℎ(�) = (�+ 1) mod 4+ 1. ACM Trans. Quantum Comput. 10 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron 1 3 5 1 3 5 � � � � � � � (0+1) � � � � � 2 4 6 2 4 6 345 � � 345 � � O O � � � � (0+1) � � (a) Step 1|� ⟩ (b) Step 2|� ⟩ = �� |� ⟩ 0 2 0 1 3 5 1 3 5 � � � � 45 � � � � � � � 0 2 4 6 2 4 6 � � � � 45+35 35 � (0+1) � � � � 1 � (c) Step 2.5:|� ⟩ = �|� ⟩ (d) Step 3|� ⟩ = �� |� ⟩ 2.5 2 3 2 Output spaces. 1 3 5 1 3 5 � � � � � ��� 1 � �� 1 � � � ��� 0 2 4 6 2 4 6 � � � � � � �� 0 � � � � (e) Step 4 (f) Step 5 1 3 5 � � 6 1 3 5 5 6 ��� � 1 ��� ��� ��� 2 4 6 2 4 6 � � � � 5 � � � � � 0 1 (g) Step 6: Output spaces. (h) Step 7: Output spaces. 1 3 5 1 3 5 � � � � � ��� ��� 1 � � � � ��� ��� 0 2 4 6 2 4 6 � � � � 45+35 345 � � � � � 0+1 (i) Step 8: Output spaces. (j) Step 8.5: Output spaces. 1 3 5 � � � � � � 2 4 6 345 � � ��� 1 � � ��� 0 (k) Step 9 Fig. 5. Each step corresponds to one application of the global evolution operator � = ��. The step�.5 for any integer� corresponds to applying the operator� to the state of step �. The control qubit|�is⟩ = � |0⟩ + �|1⟩. Blue represents a scalar coeficient of� before the basis state, red represents a coeficient�of and black represents1. When nothing is specified in caption, only input spaces are represented, whereas "Output spaces" in caption indicates that only the output spaces are represented. AO in subscript (as in Figs. 5a, 5b, and 5k) indicates that a specific element is in the output space. ACM Trans. Quantum Comput. Addressable quantum gates • 11 2 6 � � � � 5 1 3 7 � � � � 1 3 � � � � � � 5 7 � � (a) Polarizing Beam Spliter (b) The PBS AQC, represented with addresses around it Fig. 6. � and � indicate dataspaces corresponding to photons of horizontal (resp. vertical polarization). The dashed square represents the multi-sector PBS gate. ACM Trans. Quantum Comput. 12 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron 4 RENAMINGS So far, in our model a single arbitrarily chosen integer serves both as a name and as the address of a sector. Without further restrictions, this can lead to physically odd behavior: For example, one easily constructs gate operators whose action is controlled by the address stored in the target address space, see Fig. 7. This is quite strange, since in our model we wish to think of sectors merely as diferent physical locations and of addresses as just encoding the underlying geometry, i.e. the wirings of the gates. A standard way to implement this independence is to require invariance renamings under, i.e. under permuta- tions of addresses. This is akin to requesting identiier-obliviousness in distribute 17]. W dealgorithms call a gate[ operator renaming-invariant , or simply nameblindif it commutes with all such permutations. For instance, after {1} renaming� ↦→ � + 100 mod |A|, the gate operator � that was applied at location {1} is applied at location {101 mod |A|}. Thus, as renamings reshule łphysical locationsž and their associated gate operators, renaming invariance is a global condition. In Sect. 4.1, after a detour via a larger Hilbert space in which physical locations and their addresses are explicitly separated, we deduce an equivalent but local condition on gate operators. 2 2 � � 1 1 � � � � 3 3 � � � � Q Q � � � � � � (a) When Sector1 targets Sector 2, it applies� . (b) When Sector1 targets Sector 3, it applies� . Q Q � � Fig. 7. Example of a gate operator that applies diferent operators depending on the targeted sector and is hence not łrenaming invariantž. Formally this operator could be writen as|2⟩⟨2| ⊗ � + |3⟩⟨3| ⊗ � . T Q T Q � � A practical advantage of working with nameblind gate operators is the reduced number of cases to be speciied. For instance, a gate operator manipulating 6 addresses acts over 6!× 7 basis states of the address spaces if the target space is empty (ordering the six addresses and separating them amongst input and output) 6×plus 6! such basis states if the target space is occupied, which gives a9360 total Ðseeof Appendix A.1. If the gate operator is nameblind, it suices to specify its behaviour 13 basis on states (ixing an order of the addresses and distributing them target, input and output) cases to specify it entirely. Renaming invariance is thus a very restrictive condition, and one may wonder whether it leaves any room for superposing addresses at all. Surprisingly, it does. We will fully characterize the structure of nameblind gate operators in Sect. 4.2. An instructive analogy to renaming invariance from daily life is that of postal delivery, where a letter has to be delivered to a certain house with some house number. This house number is fairly arbitrary and might change due to bureaucratic processes. To guarantee the success of the mailman, when that happens, one has to make that change consistently, i.e. also on the letter and even in the phone books. In other words, if only the house number changes, the letter will not arrive. Below, we further distinguish renamings into łinternalž and eł xternalž ones w.r.t. a gate. Such renamings can be thought of as changing the house number only in a particular street and everywhere except in that street, respectively. We remark that the idea of invariance under renamings of pointers is standard in the realm of classical programming languages. For instance, it is standard to consider pointers (or references) as opaque in high-level programming languages such as Java, or OCaml. From a semantics perspective, one way to model such opaque ACM Trans. Quantum Comput. Addressable quantum gates • 13 names is to use nominal sets: a variable that is precisely invariant under renaming. Unlike for nominal sets, the set of names in the current setting is inite. 4.1 Named AQC In the formalism of AQC we use addresses in two distinct ways, with two diferent notations. Take for instance � � � � the state of a single sector |�⟩ = |�⟩ |�⟩ |�⟩ . On the one hand, addresses are łphysical locationsž. This is T W Q denoted by the superscript�(think of it like a house). On the other hand, addresses are also used to target the low of information. Those are�the (think of it like the address of another house on an envelope) �and (think the of it like an address book from which the gate operator can choose). These are denoted as states of certain registers. In order to discuss renamings in the AQC context, we need to carefully separate the two uses of addresses, and put them on an equal footing. We achieve this by extending the Hilbert space by a łname spacež that is induced � � � � � � � byN ≡ T . Letting|�⟩ |�⟩ |�⟩ ↦→ |�⟩ |�⟩ |�⟩ |�⟩ leads to the modiied formalism which we refer to as T W Q T W Q N Named Addressable Quantum Circuit(NAQC) Ðsee B.1. In that larger space, when we rename addresses, we no longer need to modify the order in which the corresponding sectors occur. Renamings act locally upon each sector without shuling them around: Ì Ì � � � � � |��⟩ |�⟩ = |�(�)�⟩ |�(�)⟩ . In other words, superscript�is the physical location (the house) at which� awill gate always be applied, before and after a renaming.|�(�)⟩ is the name of the physical location (the number on the house). Any occurrence of �(�) within some|�(�)�⟩ still points toward the same physical location (address of the house). The identiication between AQC and NAQC thus extends to � � � � � � � |�⟩ |�⟩ |�⟩ ⇐⇒ {|�(�)⟩ |�(�)⟩ |�⟩ |�(�)⟩ | � is a renaming } (5) T W Q T W Q N i.e. each AQC� is associated to the equivalence class NAQCs whose renaming into the canonical name and then projection in the AQC space yields � . Deinition 4.1 (Renaming and nameblind NAQC). A bijection ovA er is callerdenaming a . It naturally extends pointwiseW to and T , and linearlyHto ,H , and to any Hilbert space by acting non-trivially only on its W T address (and name) spaces. We call a renaming � external to a gate� if it acts trivially �, i.e.on if � ∈ � ⇒ �(�) = �, i.e. it only manipulates external addresses � ∈ A\�. Moreover, we call an NAQC((A,G,Q,�,N),|�⟩) nameblind if� commutes with every renaming �, i.e. if �� = ��. � � Nameblindness can be tested locally on each gate by demanding ∀� ∈thatG,�� = � �. This allows us to lift the notion of nameblindness back to AQCs: Theorem 4.2 (Nameblind AQC). Equivalence classes of nameblind NAQCs w.r.t. renaming are isomorphic to � � AQCs ((A,G,Q,�),|�⟩) for which for all� inG, and for all renamings� external to �, � � = �� . Such AQCs are therefore referred to as thenameblind AQCs. Summarizing, an AQC is nameblind if its gate operators commute with all external renamings. Next, we show that such gate operators are made of blocks of ‘nameblind matrices’, i.e. matrices that commute with all renamings, and study the structure of these. 4.2 Nameblind matrices Gate operators � of nameblind AQCs, calle nameblind d gate operators, manipulate all external addresses in the same manner, yet may do so in a non-trivial way. For instanc � may e, choose to swap one for the other, or not, in ACM Trans. Quantum Comput. 14 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron a superposition, as shown by the general form of nameblind unitary matrices over two addresses: cos(�) ±�sin(�) �� � (�,�) = � ±�sin(�) cos(�) understood as acting overSpan{|� �⟩ ,|� �⟩} with any�,� ∈ A, � ≠ �. Note that the data register of the gate space can readily be used to control these angles, e.g. we could �|�let �⟩ = (� (� ,� ) |�⟩) ⊗ |�⟩: + � � {2,5} Example 4.3. The action of the switch gate � in the cases shown in Fig. 5c is describ�ed(�by,� ) |�⟩ + � � with control angles: � = � = 0 when the control qubit �in is 0, and� = � = when the control qubit �in is � � � � 1, followed by a swap of input and output data spaces. Keeping this in mind, we now turn our attention towards matrices � addr overesses, which commute with all renamings. Such matrices act on the vector space whose canonical basisis identiied with the words of length � on the alphabet{1 . . .�}, i.e�. addresses between 1 and �. Moreover, we sort this canonical basis in ascending lexicographic order,{i.e 1 2·.··(� − 1) �, 1 2···� (� − 1), . . ., � (� − 1)··· 2 1.} Theorem 4.4 ((�,�)-nameblind matrices). Matrices on states containing all � addresses which commute with all renamings, i.e(.�,�)-nameblind matrices , are of the following form: � � � � � � � � � � � . . . 1 2 1 3 2 1 © ª � � � �� � � �� . . . ­ 1 1 2 1 1 ® ­ ® �� � �� � ­ 1 1 1 ® ­ ® ­ ® �� � � �� � ­ ® 1 2 1 1 2 ­ ® ­ ® ­�� � � . ® 1 2 3 ­ ® « ¬ where the blocks act on �− 1 addresses, � is any(�− 1,�− 1)-nameblind matrix,� is the renaming�↔ �+ 1, and � (see Sect. C.3) commutes with� (see Sect. C.1) for each�= 2, 3, ...,� − 2. By forcing the partially-nameblind� matrix to be nameblind, inductively so, one obtains a convenient subfamily of(�,�)-nameblind matrices, built from exactly two smaller matrices of the same subfamily. Even though they are of size�!× �!, these have onlyO(2 ) degrees of freedom. This makes these matrices easy to construct in practice. Corollary 4.5 (Pure nameblind matrices). A pure nameblind matrix on� addresses is a matrix of the following form : � � � � � � � � � � � . . . 1 2 1 3 2 1 © ª � � � � � . . . ­ 2 ® ­ ® � � � � ­ 1 ® ­ ® ­ ® � � � � � ­ 1 2 2 ® ­ ® ­ ® � � � � . ­ ® 1 2 3 ­ ® « ¬ where � and � are pure nameblind matrices on(� − 1) addresses and the � are as in Thm. 4.4. All pure nameblind matrices are also nameblind. Our main goal is to characterize gate operators, which do not necessarily act on the full address space of an AQC. As gate operators never create nor suppress addresses, we can consider separately all lengths of address ACM Trans. Quantum Comput. Addressable quantum gates • 15 |�⟩ |1�⟩ |�⟩ , |�⟩ |�1⟩ |�⟩ , |�⟩ |�⟩ |1⟩ , |�⟩ |1⟩ |�⟩ , T I O T I O T I O T I O |�⟩ |�⟩ |1�⟩ , |�⟩ |�⟩ |�1⟩ , |1⟩ |�⟩ |�⟩ , |1⟩ |�⟩ |�⟩ , T I O T I O T I O T I O |�⟩ |1⟩ |�⟩ , |�⟩ |�⟩ |1⟩ T I O T I O {1} Fig. 8. Consider a gate operator� acting over one external address� plus its own address. Its state space can be organized into the above ten ‘nameblind’ subspaces which should be interprete � d=asSpan {|�⟩ |1�⟩ |�⟩ }, �∈A\{1} T I O � = Span {|�⟩ |�1⟩ |�⟩ }, etc. Knowing in which of these subspaces � we are, � fully determines a basis state. 2 � T I O �∈A\{1} That is, basis states can be identified with the tuple (� ,�). All states within one of such subspaces evolve in the same manner {1} under the action�of . Therefore, it sufices to describe the action of the gate operator on a general|�state ⟩ to describe its action on all the true basis states |� ⟩ ⊗ |�⟩. words. For instance, withA = {1, 2, 3}, we consider independently the action of a gate operator on words of length 2, i.e. on the subset{12, 21, 13, 31, 23, 32} Let � be a nameblind matrix acting on wordsA in of size� ≤ � = |A|, meaning that� is a nameblind matrix on a set of external addresses, some of which may not be present in the basis state. Such matrices, which we additionally require to neither create nor suppress addresses are calle (�,� )-nameblind d a matrix. They are characterized as follows: Proposition 4.6 ((�,� )-nameblind matrices). Let � be a (�,� )-nameblind matrix. When sorting the basis irst by which addresses are present and then by lexicographical order�, can be written as � where � is a A ⊂ A (� !)-dimensional(�,� )-nameblind matrix as in Thm. 4.4. 4.3 Gate Operators of a nameblind AQC In practice, gate operators do not manipulate basis states solely composed of addresses. Basis states also contain data, separators between (T , I and O) spaces and between the diferent sectors. Moreover, recall from Thm. 4.2 that the gate operators of a nameblind AQC need only commute with external renamings. Still, they can be organized as blocks of nameblind matrices acting on well-identiied subspaces, as in Fig. 8, 9 and 12. A nameblind gate operator � can be written using only blocks of the form given by Thm. 4.4: 2|�| • First, we decompose the large gate space into |� | subspaces for each possible basis state of the dataspace. For each couple of basis states|� (⟩ ,|� ⟩) ∈ H we denote � the block of� which maps states with 0 1 � →� 2|�| 0 1 data |� ⟩ to states with data|� ⟩. 0 1 • Then we regroup states according to their number of external addresses � and the set of internal addresses A contained in their address spaces. Fig. 8 exempliies the subspace deine A d=by{1} and � = 1. ��� ��� Since both parameters are preserved by� and �, any � is block-diagonal in this basis. � →� 0 1 • By also ixing positions � and� for internal and external addresses, we can deine even smaller subspaces ��� �� preserved by renamings (but not by S). The blocks corresponding to this subspaces(�ar ,�e−|�|)-nameblind matrices (Prop. 4.6) Ðsee Appendix C.5 . They are illustrated in Fig. 9b and correspond to the diferent subspaces described in Fig. 8. • Finally we know that these (�,� − |�|)-nameblind matrices are block diagonal over subspaces deined by a set of� external addresses (Prop. 4.6), and only contain the same (�,� )-nameblind matrix in each block (in Fig. 9, each blo�ck denotes such a matrix). Indeed, these operators act the same way whatever the �,� names of external addresses are, because we made such addresses indistinguishable. These results are proved in full detail in Appendix C.5 together with Prop. 4.7, which states formally that a gate operator can be decomposed into(�,�)-nameblind matrices for some �. ACM Trans. Quantum Comput. 16 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron Proposition 4.7 (Decomposition of gate operators into (�,� )-nameblind matrices). Let � be a gate operator on a set of addressesA. Suppose that it commutes with all renamings on external addresses. Consider any words on quantum data � and � , internal addressesA ⊆ � with positions� and � , external addresses 0 1 ��� ��� ��� 1 2 A ⊆ A\� with positions� and � . The action of� between states corresponding to these parameters �� �� �� 1 2 � , is a(�,� )-nameblind matrix, where� = |A |. �� A ,A ,� →� ,� →� ,� →� ��� �� 0 1 ��� ��� �� �� 1 2 1 2 � 0 0 � 0 0 � 0 0 1,1 1,2 1,� © ª . . . ­ . . . ® 0 . 0 0 . 0 . . . 0 . 0 ­ ® ­ ® 0 0 � 0 0 � 0 0 � ­ 1,1 1,2 1,� ® ­ ® � 0 0 � 0 0 � 0 0 ­ 2,1 2,2 2,� ® ­ ® . . . ­ ® . . . 0 . 0 0 . 0 . . . 0 . 0 ­ ® � 0 . . . 0 1 ­ ® 0 0 � 0 0 � 0 0 � © ª ­ 2,1 2,2 2,� ® � = ­ ® 0 � . . . 0 � ­ 2 ® ­ ® ­ ® ­ ® � = � →� . . . 0 1 . . . . ­ ® ­ . ® . . . . . . . . ­ . . . . ® ­ . . . ® ­ ® ­ ® 0 0 . . . � « �(�,� ) ¬ ­ ® ­ � 0 0 � 0 0 � 0 0 ® �, 1 �, 2 �,� ­ ® ­ . . . ® . . . ­ . . . ® 0 0 0 0 . . . 0 0 0 0 � 0 0 � 0 0 � « �, 1 �, 2 �,� ¬ (a) Block � of a gate operator (b) Detailed representation of the blocks � of Fig. 9a. If� corresponds to � →� � � 0 1 subspaces with � external addresses, the� are(�,�)-nameblind matrices. �,� Fig. 9. To each pair of values � ,� in the data space corresponds a block� of the gate operator. This block � 0 1 � →� � →� 0 1 0 1 may be divided into sub-blocks � acting on subspaces having a given set of internal addresses A and a given number of � ��� external addresses� Ðsee Fig. 9a. Non-diagonal sub-blocks are zero because gate operators preserve these parameters. The diagonal sub-blocks are divided into(�,� )-nameblind matrices on more addresses than the ones presentÐsee Prop. 4.6 for details. Those(�,� )-nameblind matrices are then split into(�,� )-nameblind matrices, yielding Prop. 4.7. Example 4.8. In Sect. 3, all gate operators are nameblind. As an example, let us argue that the gate operator of {2,5} {2,5} the Switch � from Sect. 3.1 commutes with any renaming ovA er= {1, 2, 3, 4, 5, 6}. � is controlled by many inputs, therefore proving renaming invariance in all cases speciied in Appendix A.2 would be cumbersome. Instead, we focus on the irst case - the one leading to Fig. 5a. . It explains how states of the subspace K = ′ 2 5 {2,5} {|��� ⟩ |��⟩ |�⟩ ∈ H } evolve: W Q T 2 ′ 2 5 |�⟩ |�� ,��⟩ |�⟩ if� = 0 {2,5} ′ 2 2 5 T O � |��� ⟩ |��⟩ |�⟩ = (6) W Q T 2 O 2 ′ 5 |�⟩ |�� ,��⟩ |�⟩ if� = 1 T O T ′ 2 5 To see that this operator is nameblind, we consider an element of the |���form ⟩ |�1⟩ |�⟩ inK and a W Q T renaming�: 2 2 {2,5} ′ 2 5 2 ′ 5 �� |��� ⟩ |�1⟩ |�⟩ = |�(�)⟩ |�(�)�(� ),��⟩ |�(�)⟩ W Q T T O T {2,5} ′ 2 5 = � |�(�)�(�)�(� )⟩ |�1⟩ |�(�)⟩ W Q T O I ′ 2 2 {2,5} 5 = � � |��� ⟩ |�1⟩ |�⟩ . Q T O I {2,5} Similar calculations for the other cases show the nameblindness � . of 5 RELATED WORKS In the following, we discuss links between our model and other approaches to indeinite causal orders in the literature. ACM Trans. Quantum Comput. Addressable quantum gates • 17 Quantum Causal Graph Dynamics (QCGD).Another approach to represent indeinite causal orders is to shun away from the circuit formalism and take inspiration from cellular automata. The QCGD 5] featur framees work [ quantum superpositions of graphs evolving synchronously according to unitary local rules. Each vertex has a local quantum state and communicates with other vertices via ports. Compared to AQCs, vertices have replaced gates and edges have replaced wires. Like QCGD, our model is able to represent a quantum superposition of diferent graphs (the graphs of connectivity between gates). The interdiction of non-causal evolution in QCGD may appear as contradictory with the sudden appearance of an edge in the AQC between nodes of diferent gates Ð for instance, when an address suddenly goes from the input address space to the target. However, by encoding address spaces into port names, one may simulate this seemingly non-causal edge appearance at the cost of having a larger number of ports. We can therefore encode any AQC into a QCGD (see Appendix E). Quantum circuits with quantum control of causal order One . way is to allow higher-order circuits, with supermaps encoding of quantum control 34],[ in a way that generalizes the quantum switch. All thus far known physically realizable coherent control of orderings can be expressed within this QC-QC formalism. Notice that these supermaps cannot reuse the same black box twice, as causality is not handled as in AQCs. PBS calculus. A second proposal uses a graphical language inspired by PBS to express causal ordering of general, non unitary quantum channels 7,[12]. The PBS diagram formalism 12] is [ a graphical language modeling coherent control of "puriied channels" 7], i.e [ . unitary matrices enhanced with ancillæ from an environment, to represent CPTP maps. It provides completeness theorems for coherent quantum control. This control is obtained by having the PBS as a primitive of this graphical language. Similar to AQC, the physical location of quantum data is itself quantum. However, unlike AQC in the PBS calculus wires are ixed. Routed quantum circuits (RQC).A third idea consists in building a process15the ] which ory [ allows for superposi- tion of paths32[]. RQC [32] is an extension of the quantum circuit formalism which allows for communication in a superposition of paths 11].[ In this work, the authors describe sectorial constraints to study causal decomposition [24] of the used unitaries. In this purpose they partition Hilbert spaces into sectors, over which they describe with a relation Ðcalled a routeÐ which sectors are causally connected. This is reminiscent of our model as each sector’s target may be understood as a speciic sectorial constraint. However the formalism 32] doof es not [ allow for a dynamical rewiring of the circuit. Causal Boxes. A fourth way is to admit superpositions of temporal orders of messages Causal with Boxes [27]. Causality is ensured by enforcing that each new message depends on messages labelled with lower time tags. This allows for implementations of systems as the quantum switch or a the control of an unknown unitary. Our model bears similarity 27],tofor [ instance the input and output spaces of sectors are analogous to the input and output wires of causal boxes. Nevertheless, unlike 27] wher [ e circuits are ixed, our model is inherently bycausal construction, despite the dynamical aspect of the wiring structure. Quantum Shannon Theory with superposition of trajectories. The paper [11] extends the usual Quantum Shannon Theory by allowing trajectories of the information carriers to be superposed. A separation between trajectory and internal quantum information is enforced similar to our separation between addresses and data. If "phase kickback"14 [ ] were to be used to encode supplementary information in the trajectories, they would become part of the message, and the standard Quantum Shannon Theory would be suicient to express the communication protocol. In the AQC formalism, all external addresses are handled in the same way. This ensures that the phase kickback only arises from things such as the number of addresses and their position, but never from their value. 6 CONCLUSION Summary. We introduced Addressable Quantum Circuits (AQC), which consist of łgatesž that are themselves divided into łsectorsž. Each sector contains dataž ł and ładdressesž. The evolution decomposes into two steps. During the ‘scattering step’, each gate applies a local unitary operator over the data and addresses of its constituent ACM Trans. Quantum Comput. 18 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron sectors. During the ‘transport step’, each sector holding an address within its ‘target space’, swaps the content of its ‘output space’ with that of the ‘input space’ of the target sector. We showed how indeinite causal orders and superpositions of paths emerge naturally in this formalism, by encoding the quantum switch and the polarizing beam splitter. Operations that manipulate addresses raised the question of their fundamental nature. If we require addresses to represent purely geometrical data, we must restrict such operations by demanding that they are indistinguishable. Hence our focus on ‘nameblind’ AQCs, i.e. those whose scattering step commute with ‘renamings’ of addresses. Through a detour via the sub-formalism of Named AQC, we derived local conditions on the gates of AQCs for it to be nameblind. The gates must commute with renamings over ‘external addresses’, i.e. those addresses which do not pertain to the gate. We were able to give the general form(�of,�the )-‘nameblind matrices’ (i.e. acting only over lists of addresses and commuting with every renaming) irst, and then show that gates are blockwise decomposable into these. In the appendices we studied composability, and encoding within Quantum Causal Graph Dynamics (QCGD). Altogether this provides a concrete, composable model of distributed quantum computing, featuring quantum evolutions of connectivity in the spirit of classical markovian graph 13], and dynamics a thorough [ understanding of the limitations brought by renaming invariance in the spirit of classical identiier-obliviousness [17]. Perspectives.The structure of nameblind matrices and gates might simplify even further if combined with the unitary condition. Further comparison with related models could also be fruitful: Are AQCs equivalent, in terms of their expressiveness, to quantum channels extended with vacuum states 11]? Could [ an expressive process language be devised that would encompass AQC, including their dynamical 8]? asp Weepr ctsov[ed that each AQC can be simulated by a QCGD, but is the converse simulation always possible? This last question would help us establish a form of completeness of AQCs within in-principle physically realisable dynamics over quantum causal orders. ACKNOWLEDGMENTS We thank Cyril Branciard and Michel Quercia for insightful discussions and Pascal Baßler for carefully reading the manuscript. This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) ś 441423094 and the German Federal Ministry of Education and Research (BMBF) within the funding program quantum ł technologies ś from basic research to marketž via the joint project MIQRO under the grant number 13N15522. This publication was made possible through the support of the ID# 61466 grant from the John Templeton Foundation, as part of the łThe Quantum Information Structure of Spacetime (QISS)ž Project (qiss.fr). The opinions expressed in this publication are those of the author(s) and do not necessarily relect the views of the John Templeton Foundationż. REFERENCES [1] Tameem Albash and Daniel A. Lidar. 2018. Adiabatic quantum computation. Reviews of Modern Physics 90, 1 (2018). arXiv:1611.04471 [2] Mateus Araújo, Fabio Costa, and Časlav Brukner. 2014. Computational Advantage from Quantum-Controlled OrderingPof hys. Gates. Rev. Lett. 113 (2014), 250402. Issue 25. arXiv:1401.8127 [3] Pablo Arrighi, Marios Christodoulou, and Amélia Durbec. 2020. On quantum superpositions of graphs. arXiv:2010.13579 [4] Pablo Arrighi, Amélia Durbec, and Matt Wilson. 2021. Quantum networks theory. (2021). arXiv:2110.10587 [5] Pablo Arrighi and Simon Martiel. 2017. Quantum causal graph dynamics. Phys. Rev. D 96, 2 (2017), 024026. arXiv:1607.06700 [6] Alessandro Bisio and Paolo Perinotti. 2019. Theoretical framework for higher-order quantum Proceethe dings ory.of the Royal Society A: Mathematical, Physical and Engineering Sciences 475, 2225 (may 2019), 20180706. https://doi.org/10.1098/rspa.2018.0706 [7] Cyril Branciard, Alexandre Clément, Mehdi Mhalla, and Simon Perdrix. 2021. Coherent control and distinguishability of quantum channels via PBS-diagrams. arXiv:2103.02073 [8] Esteban Castro-Ruiz, Flaminia Giacomini, and Časlav Brukner. 2018. Dynamics of Quantum Causal Phys. Structur Rev. Xes.8 (2018), 011047. Issue 1. arXiv:1710.03139 ACM Trans. Quantum Comput. Addressable quantum gates • 19 [9] Giulio Chiribella, Manik Banik, Some Sankar Bhattacharya, Tamal Guha, Mir Alimuddin, Arup Roy, Sutapa Saha, Sristy Agrawal, and Guruprasad Kar. 2021. Indeinite causal order enables perfect quantum communication with zero capacityNe channels. w Journal of Physics23, 3 (2021), 033039. arXiv:1810.10457 [10] Giulio Chiribella, Giacomo Mauro D’Ariano, Paolo Perinotti, and Benoit Valiron. 2013. Quantum computations without deinite causal structure. Phys. Rev. A 88, 2 (2013), 022318. arXiv:0912.0195 [11] Giulio Chiribella and Hlér Kristjánsson. 2019. Quantum Shannon theory with superpositionsPof hys.traje Revctories. . A 475 (2019). arXiv:1812.05292 [12] Alexandre Clément and Simon Perdrix. 2020. PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 170) . Prague, Czech Republic, 24:1ś24:14. arXiv:2002.09387 [13] Andrea Clementi, Riccardo Silvestri, and Luca Trevisan. 2015. Information spreading in dynamic Distribute graphs. d Computing 28, 1 (2015), 55ś73. [14] Richard Cleve, Artur Ekert, and Chiara Macchiavello. 1997. Quantum Algorithms RePvisite . R. Soc.d.London. In 339ś354. arXiv:quant- ph/9708016 [15] Bob Coecke and Aleks Kissinger. 2017. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning . Cambridge University Press. [16] Yuval Emek, Christoph Pister, Jochen Seidel, and Roger Wattenhofer. 2014. Anonymous networks: randomization= 2-hop coloring. In Proceedings of the 2014 ACM symposium on Principles of distributed computing . 96ś105. [17] Pierre Fraigniaud, Magnús M Halldórsson, and Amos Korman. 2012. On the impact of identiiers on local International decision. In Conference On Principles Of Distributed Systems . Springer, 224ś238. [18] Pierre Fraigniaud, Juho Hirvonen, and Jukka Suomela. 2018. Node labels in local Theor deetical cision. Computer Science751 (2018), 61ś73. [19] Nicolai Friis, Vedran Dunjko, Wolfgang Dür, and Hans J. Briegel. 2014. Implementing quantum control for unknown Phys. subroutines. Rev. A 89 (2014), 030303. Issue 3. arXiv:1401.8128 [20] Simon J. Gay and Rajagopal Nagarajan. 2005. Communicating Quantum Processes. ProIn ceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Long Beach, California, USA (POPL ) ’05). Association for Computing Machinery, New York, NY, USA, 145ś157. arXiv:quant-ph/0409052 [21] Kaumudibikash Goswami, Christina Giarmatzi, Michael Kewming, Fabio Costa, Cyril Branciard, Jacqueline Romero, and Andrew G. White. 2018. Indeinite Causal Order in a Quantum Switch. Phys. Rev. Lett. 121, 9 (2018). arXiv:1803.04302 [22] Philippe Allard Guérin, Adrien Feix, Mateus Araújo, and Časlav Brukner. 2016. Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication. Phys. Rev. Lett. 117, 10 (2016), 100502. arXiv:1605.07372 [23] J. Kempe. 2003. Quantum random walks: an introductory overvieContemp w. orary Physics44, 4 (2003), 307ś327. arXiv:quant-ph/0303081 [24] Robin Lorenz and Jonathan Barrett. 2021. Causal and compositional structure of unitary transformations. Quantum 5 (2021), 511. arXiv:2001.07774 [25] Ognyan Oreshkov. 2019. Time-delocalized quantum subsystems and operations: on the existence of processes with indeinite causal structure in quantum mechanics. Quantum 3 (2019), 206. arXiv:1801.07594 [26] Ognyan Oreshkov, Fabio Costa, and Časlav Brukner. 2012. Quantum correlations with no causalNat. order Commun. . 3 (2012), 1092. arXiv:1105.4464 [27] Christopher Portmann, Christian Matt, Ueli Maurer, Renato Renner, and Bjorn Tackmann. 2017. Causal Boxes: Quantum Information- Processing Systems Closed under Composition. IEEE T. Inform. Theory63, 5 (2017), 3277ś3305. arXiv:1512.02240 [28] Lorenzo M. Procopio, Amir Moqanaki, Mateus Araújo, Fabio Costa, Irati Alonso Calafell, Emma G. Dowd, Deny R. Hamel, Lee A. Rozema, Časlav Brukner, and Philip Walther. 2015. Experimental superposition of orders of quantum Naturegates. Communications6, 1 (2015). arXiv:1412.4006 [29] Robert Raussendorf, Daniel Browne, and Hans Briegel. 2002. The one-way quantum computerśa non-network model of quantum computation.Journal of Modern Optics49, 8 (2002), 1299ś1306. arXiv:quant-ph/0108118 [30] Giulia Rubino, Lee A. Rozema, Adrien Feix, Mateus Araújo, Jonas M. Zeuner, Lorenzo M. Procopio, Časlav Brukner, and Philip Walther. 2017. Experimental veriication of an indeinite causal Science order Advances . 3, 3 (2017). arXiv:1608.01683 [31] Márcio Taddei, Jaime Cariñe, Daniel Martinez, Tania García, Nayda Guerrero, Alastair Abbott, Mateus Araújo, Cyril Branciard, Esteban Gómez, Stephen Walborn, Leandro Aolita, and Gabrela Lima. 2021. Computational Advantage from the Quantum Superposition of Multiple Temporal Orders of PhotonicPRX Gates. Quantum 2 (2021), 010320. Issue 1. arXiv:2002.07817 [32] Augustin Vanrietvelde, Hlér Kristjánsson, and Jonathan Barrett. 2021. Routed quantum cir Quantum cuits. 5 (2021), 503. arXiv:2011.08120 [33] Julian Wechs, Cyril Branciard, and Ognyan Oreshkov. 2022. Existence of processes violating causal inequalities on time-delocalised subsystems. (2022). arXiv:2201.11832 [34] Julian Wechs, Hippolyte Dourdent, Alastair A. Abbott, and Cyril Branciard. 2021. Quantum circuits with classical versus quantum control of causal order. arXiv:2101.08796 ACM Trans. Quantum Comput. 20 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron [35] Kejin Wei, Nora Tischler, Si-Ran Zhao, Yu-Huai Li, Juan Miguel Arrazola, Yang Liu, Weijun Zhang, Hao Li, Lixing You, Zhen Wang, Yu-Ao Chen, Barry C. Sanders, Qiang Zhang, Geof J. Pryde, Feihu Xu, and Jian-Wei Pan. 2019. Experimental Quantum Switching for Exponentially Superior Quantum Communication Comple Physical xityRe . view Letters122, 12 (2019). arXiv:1810.10238 [36] Matt Wilson and Giulio Chiribella. 2020. A Diagrammatic Approach to Information Transmission in Generalised Switches. arXiv:2003.08224 ACM Trans. Quantum Comput. Addressable quantum gates • 21 A ADDRESSABLE QUANTUM CIRCUITS A.1 Details on the model Several notions are introduced in this paper. For a summary of notations Ðsee Sect. F. This section provides details on Sect. 2. Addresses. In the core of the paper the stored address spaces and the target spaces were deined in words. More formally, we have Deinition A.1 (Addresses).The set of addressesA is a inite subsetNof . Moreover, we denote byW = A = ? 1 {� . . .� |� ∈ A,� ≠ � ∀�, �} the set of words ofnon-repeating addresses, and by T = A = {� | � ∈ A }∪{�} 1 � � � � the set of words of length at most one. When � addresses are in a sector space, a gate operator can map them to any superposition of(the 2� + 1)�! diferent states : • if the target space is empty, there ar � e+ 1 possibilities for the number of addresses in the input space (the others are in the output space) and�! diferent ways to order them. • if the target space is non-empty, the � − 1 remaining addresses are to be distributed between input and output space: any number of addresses from0 to � − 1 can be in the input space, and as above, there ar�e! diferent ways to order them order. When � addresses are in a sector space, and additionally the gate operator nameblind is , there are only2� + 1 diferent possibilities counted as above but up to reordering. It suices to specify the behaviour of the gate operator on one of each of those(2�+1) possibilities, to have them speciied on all the corr�esp ! reonding ordered possibilities, by renaming invariance Ðsee Fig. 8. Flipping gates. To prepare the transport to a targeted sector, many gate operators push some of their content to the output spaces after manipulating it. This is achieved by lipping operations, which are in some sense necessary since gates whose scattering unitary is the identity �are merely as a łmirrorž, i.e. they relect incoming data. In the example of the Bell state creation circuit in (3) the input and output spaces are lipped by ′ ′ ′ ′ � : |�⟩ |�,�⟩ |� ,� ⟩ ↦−→ |�⟩ |� ,� ⟩ |�,�⟩ . T T I O I O Other possibilities are lipping only the data spaces, i.e. ′ ′ ′ ′ � : |�⟩ |�,�⟩ |� ,� ⟩ ↦−→ |�⟩ |�,� ⟩ |� ,�⟩ , data T I O T I O or more sophisticated lips that are conditioned on the state of the sector. Evolution. Like in Def. 2.8, the example below uses the following convention on|�the⟩ states indicates : that the space � ∈ {T,I,O} of the sector� ∈ A is in the state|�⟩. Example A.2. Efect of the transport step� withA = {1, 2}: Without basis reordering : 1 1 1 1 1 1 |2⟩ |�,� ⟩ |�,�⟩ |2⟩ |�,� ⟩ |1,� ⟩ 1 1 2 T I � T I � −→ 2 2 2 2 2 2 |�⟩ |1,� ⟩ |�,�⟩ |�⟩ |�,�⟩ |�,�⟩ T � T � I I With basis reordering of Sect. 2.1: |2,�⟩ |(�,� ),(1,� )⟩ |(�,�),(�,�)⟩ T 1 2 � −→ |2,�⟩ |(�,� ),(�,�)⟩ |(1,� ),(�,�)⟩ � 1 2 T I � The address 1 and data � were in the input space of the sector 2, and � transports them to the output space of sector 1, because sector 1 targeted sector 2. ACM Trans. Quantum Comput. 22 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron Example A.3. The Bell state creation circuit evolves very simply Ð missing the obvious coeicient here and not writing target spaces (as they do not change) and empty spaces : 1 1 2 2 3 |00⟩ → |00⟩ → |00⟩ → (|0⟩ + |1⟩) |0⟩ → (|0⟩ + |1⟩) |0⟩ � � � � I O I O I 3 3 4 4 4 4 4 4 → |00⟩ + |11⟩ → |00⟩ + |11⟩ → |00⟩ + |11⟩ → |00⟩ + |11⟩ , � � � � O O I I O O O O where the lack of a target address in sector 4 causes the data to stay there during the last transport step. A.2 Details of the uantum Switch A.2.1 Definition. The description of the quantum switch in Sect. 3.1 can be completed by specifying some gate operators � . Their action on the addresses is as follows: {1} {6} {3} {4} � = � = � , � = � · � , � = � · � . 34 � 34 � Here, � applies the gate � to the irst� bits of data, i.e. on all data except the control qubit, and |�⟩ |�⟩ |�⟩ ←→ |�⟩ |��⟩ |�⟩ T W T W Q Q O O I I � = |�⟩ |�⟩ |�⟩ ←→ |�⟩ |�⟩ |�⟩ T W Q T W Q O I O I {2,5} ′ − The gate operator � , the efect of which is detailed in A.2.2, acts as follo�ws ,�(,wher �∈ Ae, � ∈ A , �∈ D, � ∈ D and, as usual, states that are omitted correspond �to): 2 ′ 5 |�⟩ |�� ,��⟩ |�⟩ if� = 0 {2,5} ′ 2 5 T O T � |��� ⟩ |��⟩ |�⟩ = (7) W Q T 2 ′ 2 5 O I |�⟩ |�� ,��⟩ |�⟩ if� = 1 T O {2,5} 2 5 5 2 5 5 5 � |�⟩ |�⟩ |��⟩ = |�⟩ |�⟩ |�⟩ |�⟩ (8) T T T Q W Q Q I O I O ′ 5 5 |��� ⟩ |�⟩ |��⟩ if� = 0 {2,5} 2 ′ 2 5 W T Q � |�⟩ |�� ⟩ |�⟩ |�,�⟩ = (9) T W Q O ′ 2 5 O 5 |��� ⟩ |�⟩ |��⟩ if� = 1 T Q O O {2,5} We ensure unitarity �of by specifying a reciprocal version of the equations above: 2 ′ 2 5 ′ 2 2 5 {2,5} � |�⟩ |�� ,�0⟩ |�⟩ = |��� ⟩ |�0⟩ |�⟩ O W T T Q T O I • reciprocal version of (7): 2 2 2 ′ 5 ′ 2 5 {2,5} � |�⟩ |�� ,�1⟩ |�⟩ = |��� ⟩ |�1⟩ |�⟩ T O T W Q T {2,5} 2 5 5 5 2 2 5 5 2 • of (8):� |�⟩ |�⟩ |�⟩ |�⟩ |�⟩ = |�⟩ |�⟩ |��⟩ |�⟩ T W Q Q W T T Q W O I O I 2 2 ′ 5 5 {2,5} 2 ′ 2 5 |��� ⟩ |�⟩ |�0⟩ = � |�⟩ |�� ⟩ |0⟩ |�,�⟩ W T Q T W Q O O O O O • and of (9): ′ 2 5 5 2 ′ 2 2 5 {2,5} |��� ⟩ |�⟩ |�1⟩ = � |�⟩ |�� ⟩ |1⟩ |�,�⟩ W W O T Q T O Q O O O These three reciprocal cases are not useful in usual executions of the quantum switch, where they have zero {2,5} {2,5} amplitude. On all other basis � states,acts as the identity. This fully deines � . {2,5} A.2.2 Correctness. The evolution of the quantum switch is displayed in Fig. 5. Since �the opis erator the most interesting gate operator, let us describe its action in detail. In the scattering 2, it after actsstep as in (7). In step 5, it acts as in (8), which allows the remaining data to wait in the output space of sector 5. Most importantly, the control qubit lows back into the circuit, allowing the addresses to return to their initial positions in steps 6-9. In step 8, they łmergež back together, according to (9). The data then lows out of sector 5 into the outgoing bufer sector 6, and can be processed further by concatenated AQCs (see Sect. D.3) as the quantum switch is not entangled with the data anymore Ðsee e.g. 5j. ACM Trans. Quantum Comput. Addressable quantum gates • 23 That is, at the end of Fig. 5, the data has been delivered, and the quantum switch has folded back into its initial coniguration. In Step 9 the inal state of the data��space |�⟩|is 1⟩ +�� |�⟩|0⟩ (when omitting scalar coeicients). This matches the behaviour described in (1), which proves correctness. {2,5} As a inal remark, note that according to Thm. 4.2 the nameblindness � ofonly would have required commutation with renamings over the setexternal of addresses {1, 3, 4, 6}. Yet, we proved in Sect. 4.3 that it also holds for the addresses{2, 5}. B NAMED AQC To prove the results on the nameblindness of the main text, we disentangle the notions of physical locations and łnamesž as arbitrary labels of sectors. This amounts to extending the Hilbert spaces we work with by a łname space,ž i.e. an additional address space, which allows us to carefully distinguish between instances of AQCs with diferently chosen labelings. There are also other ways to describe a geometry than resorting to arbitrary names, e.g. working modulo isomorphism which, however, results in signalling problems [3]. B.1 Definition of an NAQC Here we deine formally every notion useName d ford AQC (NAQC) which difers from that used for AQC. Deinition B.1 (Named sector space).Let �be the index of a sector. The Hilbert space H = H ⊗H ⊗H ⊗H T I O N is referred to as name a d sector space, withH a copy ofH referred to as thename space. N A ˆ ˆ Deinition B.2 (Named circuit space). The circuit spaceH of an NAQC is the subspace of H such that �∈A each address appears at most once in the combined target, input and output spaces, and exactly once in the name spaces. In the NAQC formalism, target spaces H no longer target physical locations (a position as factor in the tensor product H ). Instead, it targets the name� ∈ A of that physical location, as occurring in some name space H of some sector. A gate� = {� ,� , . . .,� }, on the other hand, consists of the sectors at the physical locations N 1 2 � {� ,� , . . .,� }. 1 2 � Deinition B.3 (Named gate space).The named gate space of a gate� consists of|�| named sector spaces, i.e. it is � � ˆ ˆ given byH = H . �∈� � � ˆ ˆ Deinition B.4 (Named gate operator).A named gate operator on � ∈ G is a unitar�y : H → H which preserves the addresses of the target and stored spaces as in Def. 2.6, and separately the name space stays unchanged. − � � ˆ ˆ For any name � ∈ A , we denote byH := H ⊗ |�⟩ the subspace ofH spanned by the basis states that ˆ � ˆ give the name� to the gate �. ClearlyH, is the smallest Hilbert space containing H . Moreover, since gate operators by deinition preserve the name of the gate space, they are of the form � = � , i.e. named gate � � operators are block-diagonal with blo � cks acting on and preservingH . � � � � � � Deinition B.5 (NAQC transport).The named transport � maps synchronously|�⟩ |�⟩ ⊗ |�⟩ |�⟩ to T O I N � � � � |�⟩ |�⟩ ⊗ |�⟩ |�⟩ , leaving the other sector constituents unchanged. That�is, swaps the output space O I N of a sector with the input space of the sector withname the it targets, i.e. whenever a sector �targets a name �, �’s output space is swapped with the input space of the sector with �name . B.2 Renaming NAQCs − − Let � be a name, i.e. an elementA in. We call a renaming �, i.e. a permutationA of ACM Trans. Quantum Comput. 24 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron • external for �, if � acts as the identity over each address �in . • internal for�, if� acts as the identity over each addressA in\ �. • mixed for�, if� is a composition of disjoint swaps fully speciied by two equal (� ,size � ) dwher setse 1 2 � takes its elements in � and � takes its elements in A \ �. � swaps the irst element of � for the 1 2 1 natural order overN with the irst element�of, the second with the second and so on). On elements of A \ (� ∪ � ), � acts as the identity. 1 2 9 2 5 4 8 |�⟩ |89⟩ |24⟩ |�⟩ |�⟩ W W W W W 0 1 2 3 4 5 6 7 8 9 10 (a) An NAQC . . . 2 4 5 8 9 |�⟩ |92⟩ |48⟩ |�⟩ |�⟩ W W W W W 0 1 2 3 4 5 6 7 8 9 10 (b) . . . renamed so that each gate space is named with the canonical name. Fig. 10. An NAQC represented over a grid. HereA = {2, 4, 5, 8, 9}. Inside of each sector (big white boxes) we can find the content of the stored address space. Gray boxes represent the content of the name space. Example B.6. Consider the circuit in Fig. 10a. We focus here on the gate space {4,5} which has the 25.name Then • � isexternal because it only swaps external addresses. 4↔8 • � is the only non-trivial internal renaming for this state. 2↔5 • � ismixed because it swaps external with internal addresses in an ordered fashion. 5↔9,2↔4 • � is neither internal nor mixed nor external. 5↔4,2↔9 Distinguishing these particular types of renamings is useful because any � can renaming be uniquely decom- posed into a mixed, an internal and an external renaming with respect to a giv �.en The name basic idea to construct this decomposition is to irst apply a mixed renaming to bring all�the (�)letters into the ofgate space, then use an internal renaming to ensure that the gate space is name �(�d), and inally adjust the addresses that are not in� with an external renaming. Let us deine � the renaming changing the wor�dto �, and not �→� changing other letters. Proposition B.7 (Decomposition of renamings). (1) Let � and � be names of same length. There is a unique renaming � = �� such that � is mixed for� and � �→� is internal for� (�). (2) Let � be a renaming and� be an element ofA Ðsee Def. A.1. There exists exactly one pair of renamings such that: � = �� �→� ACM Trans. Quantum Comput. Addressable quantum gates • 25 where � = �(�) and � is external for�. Proof. For any name � = � � . . . � ∈ A we writeSET(�) = {� , � , . . ., � } and note that it is invariant 1 2 � 1 2 � under renamings that are external and internal�.for (1) Let � : A → A be a renaming, and take� as the renaming that swaps elements of SET(�) \ SET(�(�)) with elements of SET(�(�)) \ SET(�) and is mixed for �. Note that SET(� (�)) = SET(�(�)), and that � is unique since we have that SET(� (�)) = SET(���(�)). Similarly,�take as the renaming such that for every integer 0 < � < |�| + 1 �: A → A, � (�) ↦→ �(�) , � � and which is internal� for (�). Since��(�) = ���(�) for all � external for��(�), � is the only possible choice. Together, this gives a unique decomposition � = �� . �→� −1 −1 (2) This follows from deining � = �� � which is unique since it is the only renaming that guarantees � = ��� . Moreover, � is (trivially) external ��(�for ), since���(�) = �(�) = ��(�), where the last equality is by construction of� in the proof of (1). □ Example B.8 (Decomposition of renamings). Consider the renaming � on the circuit of Fig. 10a, which 2→9→8,4↔5 4 5 4 5 maps the gate space state |2⟩ |89⟩ |5⟩ |24⟩ to |9⟩ |28⟩ |4⟩ |95⟩ . We decompose it with respect to N N N N W W W W the name � = 25: • Since�(�) = 94, the mixed renaming constructed in the above proof � is = � , which results in the 5↔9,2↔4 4 5 state |4⟩ |85⟩ |9⟩ |42⟩ . N N W W • Then, �= � is the only possible internal renaming that reorders the name of the gate space, which is 9↔4 4 5 thus in the state|9⟩ |85⟩ |4⟩ |92⟩ . N N W W • Finally � =, � reorders the external addresses to match the desired ones. 2→5→8 Next, we relate AQCs to NAQCs with speciically chosen gate names, called the canonical name Ðsee Fig. 10b. To this end, consider a named gate spaceH with� = |�| sectors. Its basis states are of the form |� � ⟩|� ⟩ � � � N �∈� �increasing This state giv�esnames � to the sectors inside the gate space, thus we say that this state givesname the � = � � . . . � to the gate � = � � . . .� with� < � < . . . < � . � � � 1 2 � 1 2 � 1 2 � Deinition B.9 (Canonical name).Consider a gate� = {� ,� ,� , . . .,� }. The canonical nameof� is� = � � � . . .� 1 2 3 � 1 2 3 � with� < � < ··· < � . The basis states ofH take the form: 1 2 � � |� � ⟩|�⟩ �∈� ′ � By this deinition, the basis states H of are in one-to-one correspondence with those of the gate space H of an AQC (Sect. 2), i.e. |� � ⟩ . �∈� Choosing a canonical name means choosing a representative for each equivalence class w.r.t. renamings Ð see (5). Thus the subspace H of the named circuit space H is isomorphic to the circuitH space . �∈� �(�) ACM Trans. Quantum Comput. 26 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron Finally, we describe those gate operators which act the same way whatever the name of the gate is. This relects the idea that the action at a physical location (a house) should not depend on the arbitrary choice of name for that location (the number on the house), which is iducial. Since such gate operators do not depend on the internal addresses in the name spaces of gate space, we call them łinternally-blindž: Deinition B.10 (Internally-blind gate operators).Let � be a gate with� sectors and canonical name � ∈ A . The � − ′ named gate operator � is calle internally-blind d if for any � ∈ A with|�| = � and for any state|�⟩ ∈ H : � � −1 � |�⟩ = � � � |�⟩ . �→� � � �→� Internally-blind named gate operators are completely determined by their � . Inblo theck next section we show that renaming invariance imposes further constraints on this block. B.3 Proof of Theorem 4.2 The concept of NAQC introduced above allows us to prove that nameblind AQCs and nameblind NAQCs are isomorphic. To do so, we show that nameblindness of an NAQC is equivalent to it being internally-blind, i.e. fully determined by its action over the canonical name (see Def. B.10), and commuting with renamings that are external for the canonical name. We show that internally-blind operators that commute with external renamings are nameblind: Lemma B.11 (Commutation with mixed and internal renamings). Let � be an internally-blind gate operator, � the canonical name of�, and � ∈ A a name of size|�|. If� commutes with every renaming external to �, then for all� ∈ A with|�| = |�| and any |�⟩ ∈ H � � � � |�⟩ = � � |�⟩ . �→� �→� Proof. Let � as in Prop. B.7. Let� be the renaming deined by �→� −1 � = � � � �→� �→� �→� Since�� = �, it is external�for . We have: � � |�⟩ = � � |�⟩ (Diagonal blockwise) �→� �→� −1 = � � � � |�⟩ (Internally-blind) �→� �→� � �→� −1 = � � �� |�⟩ (Deinition�of ) �→� � �→� −1 = � �� � |�⟩ (Hypothesis) �→� � �→� −1 = � � � � |�⟩ (Deinition�of ) �→� �→� � �→� = � � |�⟩ (Internally-blind) �→� � = � � |�⟩ (Diagonal blockwise) �→� Lemma B.12 (Commutation with external renamings). Let � be a internally-blind gate operator�, the canonical name of�, and � ∈ A a name of size|�|. If� commutes with every external renaming, then for all external renamings� and all |�⟩ ∈ H : � � � � |�⟩ = �� |�⟩ . Proof. Let � be a renaming external for �. Let � be the renaming deined by: ′ −1 � = � �� �→� �→� ′ ′ � is external for � so we have for each state|�⟩ ∈ H : ACM Trans. Quantum Comput. Addressable quantum gates • 27 � � |�⟩ = � � |�⟩ −1 = � � � � |�⟩ (Internally-blind) �→� � �→� ′ −1 ′ = � � � � |�⟩ (Deinition�of ) �→� � �→� ′ −1 = � � � � |�⟩ (Hypothesis) �→� � �→� −1 = �� � � |�⟩ �→� � �→� = �� |�⟩ ˆ � � Theorem B.13 (Characterization of renaming invariance). LetH be a named gate space, � be a named � � gate operator and � the canonical name of�. � is renaming invariant if and only � if is internally-blind and � � � commutes with every renaming� external for�, i.e� � = �� . � � � � Proof. [⇒] : Let � be a nameblind gate operator. Since by hypothesis � commutes with all renamings, it obviously commutes with the external ones, and so does the�blo . Tck o show that � is internally-blind, � � consider a renaming � . Renaming invariance� ofimplies that � � = � � , and hence for every name �→� � �→� �→� � of� and for each state|�⟩ ∈ H we have � � −1 � |�⟩ = � � � |�⟩ , �→� � � �→� which is a restatement of internal-blindness. [⇐] : Let� be an internally-blind gate operator such � that commutes with all external renamings. Consider a renaming� and a name � ∈ A of size|�|. Then, for every state|�⟩ ∈ H : � � � � |�⟩ = � ��� |�⟩ (by Prop. B.7) = �� �� |�⟩ (by Lem. B.12) = ���� |�⟩ (by Lem. B.11) = �� |�⟩ , i.e�. is renaming invariant. □ Thm. B.13 states that the named gate operator � of a nameblind NAQC is fully characterized by its � action over the gates with canonical names, and that these must commute with external renamings. From Def. B.9 it follows that the evolution of an NAQC over gates with canonical names is isomorphic to that of an AQC. Thus, the set of nameblind NAQCs is isomorphic to the set of AQCs whose gate operators commute with external renamings. Therefore, Thm. 4.2 follows from Thm. B.13. Proof of Thm. 4.2. Let us consider a nameblind NA(QC(A,G,Q,�,N),|�⟩|�⟩), its scattering � commutes with every renaming �, i.e�.� = ��. The isomorphic nameblind Addressable Quantum Cir((cuit A,G,isQ,� ),|�⟩), where � is deined as a scattering where each gate operator � is of the form � of Thm. B.13. Reciprocally, � � � given a nameblind AQC, as each gate operator � commutes with external renamings, � = � is a nameblind named gate operator that can be used to specify a nameblind NAQC. □ ACM Trans. Quantum Comput. 28 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron C CHARACTERIZATION OF NAMEBLIND OPERATORS Nameblind gate operators consist of blocks of nameblind matrices (see Prop. 4.7), which will be characterized inductively in this appendix. Below, when representing such operators over � eaxternal list of addresses as matrices, we implicitly use the basis of words sorted in lexicographically ascending order, i.e. {12 . . .(� − 1)�, 12 . . .�(� − 1), . . .,�(� − 1) . . . 21}. (10) In this basis, the irst (� − 1)! words begin with letter 1, the next (� − 1)! words begin with letter 2 etc. We often partition matrices acting on�!this -dimensional Hilbert space � into blocks, each acting between two (� − 1)!-dimensional Hilbert spaces, each being spanned by words starting with the same letter. C.1 Adjacent transpositions Let � be an integer and let us consider � ∈ {1, . . .,�−1}. We call the renaming � which swaps� and �+1 and acts as the identity otherwiseadjacent an transpositionon words of� addresses at �. Adjacent transpositions generate the group of renamings, such that any renaming can be written as a product of such adjacent transpositions. Commuting with all adjacent transpositions is therefore equivalent to commuting with all renamings. Lemma C.1. In the basis(10) the matrix of an adjacent transposition � has the form � �+ 1 ↓ ↓ � 0 . . . �−1 © ª . . . . ­ ® . . ­ ® ­ . ® . . ­ ® . � �−1 ­ ® ­ ® � = (11) 0 � ← � ­ ® ­ ® � 0 ← � + 1 ­ ® ­ ® . . ­ ® � . ­ ® ­ ® . . . . ­ ® . . « ¬ . . . 0 � where � is the adjacent transposition matrix on words�of− 1 addresses at �. Proof. We consider the lines before and after�th theline separately: The addresses after�the th block line correspond to � letter words that begin with a letter bigger�.than Amongst the remaining � − 1 letters,� is still the �th letter in ascending lexicographic order. Thus, to transp � and ose� + 1 we must apply� . The lines before the �th line, correspond �toletter words starting with a letter smaller �. Thus, than amongst the remaining � − 1 letters,� is still(�the− 1)-th letter in ascending lexicographic order. Therefore, the correct matrix to apply�is . □ �−1 C.2 Nameblind operators We now prove Theorem 4.4, which we restate here for the convenience of the reader : ACM Trans. Quantum Comput. Addressable quantum gates • 29 Theorem 4.4. (�,�)-nameblind matrices have exactly the form � � � � � � � � � � � . . . 1 2 1 3 2 1 © ª � � � �� � � �� . . . ­ 1 1 2 1 1 ® ­ ® �� � �� � ­ 1 1 1 ® ­ ® ­ ® � = (12) �� � � �� � ­ 1 2 1 1 2 ® ­ ® ­ ® �� � � . ­ ® 1 2 3 ­ ® « ¬ where � is a(�−1,�−1)-nameblind matrix and� is any matrix which commutes with � for each�in{2, 3, ...,�−1}, whose characterization is given in Prop. C.2 Proof. Let � be a matrix of size �!× �! written blockwise with blocks of(� − size 1)!× (� − 1)! as � � . . . � � . . . � 1,1 1,2 1,� 1,�+1 1,� © ª . . . . . ­ ® . . . . . . ­ . . . . . ® ­ ® ­ � � . . . � � . . . � ® �,1 �,2 �,� �,�+1 �,� � = ­ ® . ­� � . . . � � . . . � ® �+1,1 �+1,2 �+1,� �+1,�+1 �+1,� ­ ® . . . . ­ ® . . . . . ­ . . . . ® � � . . . � � . . . � �,1 �,2 �,� �,�+1 �,� « ¬ Since every renaming can be written as a product of adjacent transpositions, commuting with all renamings is equivalent to commuting with all adjacent transpositions. � is Thus, nameblind�if � = �� for all � ∈ � � {1 . . .� − 1} with� as in (11), i.e. if the following matrices are equal�:for every � � � � . . . � � � � . . . � � �−1 1,1 �−1 1,2 �−1 1,� �−1 1,�+1 �−1 1,� © ª ­ ® � � � � . . . � � � � . ­ 2,1 2,2 ® �−1 �−1 �−1 2,� �−1 2,�+1 ­ ® . . . . . ­ ® . . . . . . . . . . ­ ® ­ ® � � = � � . . . � � . . . � ­ ® �+1,1 �+1,2 �+1,� �+1,�+1 �+1,� ­ ® � � . . . � � . . . � ­ ® �,1 �,2 �,� �,�+1 �,� ­ ® . . . . ­ ® . . . . ­ . . . . ® � � . . . . . . � � � � . . . � � � �,1 � �,� � �,�+1 � �,� « ¬ � � � � . . . � � . . . � � 1,1 �−1 1,2 �−1 1,�+1 1,� 1,� � © ª ­ ® � � � � . . . � � . ­ ® 2,1 �−1 2,2 �−1 2,�+1 2,� ­ ® . . . . . ­ ® . . . . . ­ . . . . . ® ­ ® �� = ­ � � � � . . . � � . . . � � ® �,1 �−1 �,2 �−1 �,�+1 �,� �,� � ­ ® ­� � � � . . . � � . . . � � ® �+1,1 �−1 �+1,2 �−1 �+1,�+1 �+1,� �+1,� � ­ ® . . . . ­ ® . . . . ­ . . . . ® � � . . . . . . � � . . . � � « �,1 �−1 �,�+1 �,� �,� � ¬ This gives three types of conditions which we distinguish by their color in the matrices above: ACM Trans. Quantum Comput. 30 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron Blue conditions . For each �∈ {1, . . .,� − 1}: � = � , i.e. all diagonal blocks are equal. �,� �+1,�+1 � = � , i.e. the matrix is blockwise-symmetric near the diagonal. �,�+1 �+1,� We will henceforth write the diagonal blo � :=cks � asand we set � := � . 1,1 1,2 Green conditions . Consider a row�, a column�and an adjacent transposition � . The green conditions from commutation with � are equivalent to: Above the diagonal, i.e �<.� < � + 1 < �: – � = � � , i.e one step to the right corresponds to right multiplication with . �,�+1 �−1 �,� – � = � � , i.e the(� + 1)-th element of column �is equal �to times the�-th element. �+1,� �,� � � Below the diagonal,�i.e < �. < � + 1 < �: – � = � � , i.e. the(� + 1)-th element of line �is equal �to times the�-th element. �,�+1 � �,� � – � = � � , i.e. the(� + 1)-th element of column �is equal �to times the�-th element. �+1,� �,� �−1 �−1 This has to hold for�all which gives the general form � of given in Thm. 4.4, because we can deduce all blocks from� and � , but the conditions on the blocks are yet to be derived. 1,1 1,2 Black conditions.From the diagonal conditions in the top-left and bottom-right quadrant we immediately deduce that � commutes with all � for0 < �< � − 1, i.e�. is nameblind. Similarly � commutes , with all � for � � 2 < �< � − 1. Thus, in the basis (10) � has the form (12). Let us now show the converse, i.e. that any matrix � as speciied in Thm. 4.4 is nameblind. By deinition, it satisies the blue and green conditions, and it only remains to check that it also meets the requirements of the black conditions. To this end, consider a�bloabckove the diagonal, i.e �<. �, which is symmetric with the �,� case where it is below. By (12) this block is given by � = � . . . � �� . . . � . �,� �−2 1 1 �−1 To satisfy the top-left and bottom-right conditions, this block has to commute � with for all � such that �−1 ′ ′ � < � < �, and with� for all � such that � + 1 < �, i.e. it has to commute with � for all � ∈ � := � � {1, . . .,�− 2}∪{�, . . .,�− 2}. Explicitly, we need to show that� for ∈ � � . . . � �� . . . � � = � � . . . � �� . . . � . �−2 1 1 �−1 � � �−2 1 1 �−1 Rearranging this we obtain � = � . . . � � � . . . � �� . . . � � � . . . � 1 �−2 � �−2 1 1 �−1 � �−1 1 ⇔ � = � . . . � � � . . . � � . . . � � � . . . � � 1 �−2 � �−2 1 1 �−1 � �−1 1 ⇔ � = � . . . � � � . . . � � � . . . � � 1 �−2 � �−2 � � �−1 1 ⇔ � = � . . . � � � � . . . � � . . . � � 1 �−2 � � �−2 � �−1 1 ⇔ � = � . . . � � . . . � � 1 �−1 �−1 1 where the irst equivalence comes from premise�that commutes with renamings that preserve the letter 1 (since {� , . . ., � } generates this family of renamings) which � . . . � � � . . . � does since� is diferent 2 �−1 1 �−1 � �−1 1 from� and �− 1, and the third comes from the fact that two transpositions with disjoint support commute. Moreover, since� � = � the right side of the last equation indeed�.gives � � To verify the top-right and bottom-left conditions, consider� a blo with ck�< �, and a �< � < �− 1. Since �,� the conditions for this quadrant are symmetric, this is suicient. This block has � to � satisfy = � � . We �,� � �−1 �,� calculate: � � = � . . . � �� . . . � � (1) �,� � �−2 1 1 �−1 � ACM Trans. Quantum Comput. Addressable quantum gates • 31 = � . . . � �� � . . . � (2) �−2 1 � 1 �−1 = � . . . � � � � � . . . � �� . . . � (3) �−2 �+1 � �−1 � �−2 1 1 �−1 = � . . . � � � � � . . . � �� . . . � (4) �−2 �+1 �−1 � �−1 �−2 1 1 �−1 = � � . . . � � � � . . . � �� . . . � (5) �−1 �−2 �+1 � �−1 �−2 1 1 �−1 = � � (6) �−1 �,� where as above we used that transpositions with disjoint support commute and ��that= � � since� > 1. � � The non-trivial step in the forth equality is to realize � � �that = � � � = (� − 1 � + 1). �−1 � �−1 � �−1 � Thus, all black conditions are satisied by the blo � of cks theofgeneral form given in Thm. 4.4, which implies that � indeed is nameblind. □ C.3 Partially-nameblind operators The matrix� of Thm. 4.4 is łpartially-nameblindž in the sense that it commutes with all renamings which preserve the irst� addresses in lexicographical order. We denote the set of such matrices B , wher by e � indicates the total number of addresses. Proposition C.2 (Characterization of partially-nameblind matrices). partially-nameblind matrices � ∈ B are exactly those matrices which can be written as � = � � � � . . . � � � � � � � . . . 1,1 1,� � �+1 � 1 1 1 © ª � � � ­ ® � . . . � � � � � � � . . . 2,1 2,� � �+1 � 2 2 2 ­ ® . . ­ . ® . . . ­ . ® . . ­ ® � � � ­ ® � . . . � � � � � � � . . . �,1 �,� � �+1 � � � � ­ ® � � ­ ® � . . . � � � � � . . . �+1 1 � ­ ® � � ­ ® � � . . . � � � � � �� . . . � � �+1 �+1 ­ 1 ® � � ­ ® � � � . . . � � � �� � �� � � �+1 � �+1 �+1 �+1 �+1 ­ 1 � ® ­ ® . . ­ . . . ® . �� � . ­ �+1 �+2 ® ­ ® « ¬ �−1 � � �−1 �−1 where � ∈ B , � , � and � are inB , and � is inB . �,� �−1 � � �+1 Proof. As above, we use blue, green and top-left black conditions, which for matrices B howein ver have to be satisied only for � < �. Conversely, we have to check that matrices of this form satisfy the black conditions. First, we consider blocks �−1 � in the top-left or bottom-right corner �< . If� + 1 and �< � + 1 we just have to check that � is inB , �,� �,� �−1 which is the case by deinition. If�> � and �> �, the proof of Thm. 4.4 applies. Thus, we only have to consider the�<case � + 1, �> � since the other one follows by symmetry. In this case the block is given as � = � . . . � � , �,� �−2 � and we have to verify that it commutes with � for all � such that �< � < �, and with� for all � such that �−1 � � + 1 < � + 1 < �, i.e. that it commutes with � for each� ∈ {�,�− 2} as {� + 1, . . .,�− 2} is empty. Since these transpositions have disjoint support, this is straightforward to see. Next, pick� in the top-right or bottom-left corner. Since the top-right and bottom-left conditions are �,� symmetric it is suicient to consider the�<case �. Moreover, if�> � again the previous proof applies, so we ACM Trans. Quantum Comput. 32 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron only consider �< � + 1 < � + 2 < �. We have to show that � � = � � for all � < �− 1. Indeed, �,� � �−1 �,� � � = � . . . � � � �,� �−2 � � � = � . . . � � � . . . � � �−2 � �−1 � � = � . . . � � � . . . � � �−2 �−1 � �−1 � = � � . . . � � . . . � � �−2 � �−1 � �−1 = � � �−1 �,� This ends the proof that all black conditions are satisied by matrices of the general form given in Prop. C.2, and thus we have proved the desired equivalence. □ C.4 (�,� )-nameblind matrices C.4.1 Proof of Prop. 4.6. Consider a(�,� )-nameblind matrix � ; � = |A | is the number of external addresses, �� and � ≤ � is the number of addresses present in any state handled� by . � is an operator over words on� addresses chosen among �. In the following, we will use the basis of such words, not sorted in lexicographic ascending order as in{12 . . .(� −1)�, 12 . . .(� −1)(� +1), . . .,� . . .(�−� +2)(�−� ),� . . .(�−� +2)(�−� +1)}, but instead sorted irst by what addresses are present, and then by lexicographical ascending order, i.e. {12 . . .(� − 1)�, 12 . . .� (� − 1), . . .,� . . .(� − � + 1)(� −� + 2),� . . .(� −� + 2)(� − � + 1)}. Note that if � < �, � acts on basis states with less addresses than all external addresses. Let us sho�w that can be written blockwise with (�,� )-nameblind matrices (see Thm. 4.4). This state space is partitioned according to the A set (of size � ) of what addresses are actually present, each subspace being calleHd Ð for some A ⊂ A . As � does neither create nor suppress addresses, it is also A �� block diagonal (in the particular ordering we chose). Lemma C.3 proves that all these blocks are equal. Next, we show that all blocks are nameblind. To this end, consider a set of addr B with essescorresponding ˆ ˆ ˆ block� which maps words fromH toH , whereH is the corresponding subspace. Then, for any renaming B B B B ˆ ˆ � manipulating addresses within H , and any � ∈ H : B B ��� = �� �, ��� = � ��, B B as �� ∈ H . The left sides of these equalities agre�e since is nameblind. Therefor � e,is nameblind, and as it B B is acting on words of size � on � addresses, it is(�,� )-nameblind. C.4.2 Lemma - Block equality. The basis states of(a�,� )-nameblind matrix � are ordered according to which addresses A are present. For the sake of simplicity of demonstrating Lem. C.3, we further specify the order between such address sets. Let A be a subset ofA of size � . We deine its sizeas the integer corresponding �� to the indicator function (understood as little-endian binary number), and �(Anote ). For itinstance, with A = {1, 2, . . ., 6}: �� 1 2 3 �({2, 3, 4}) = ���(011100) = 2 + 2 + 2 = 14 0 1 4 �({1, 2, 5}) = ���(110010) = 2 + 2 + 2 = 17 Note that only the binary numbers with � bits set to1 will be represented. The order between inite address sets is then simply the usual order between their sizes. ACM Trans. Quantum Comput. Addressable quantum gates • 33 . . . < |011100⟩ ↔ {2, 3, 4} . . . < |011100⟩ < |110010⟩ ↔ {1, 2, 5} |011100⟩ < |110010⟩−����� < |101010⟩ ↔ {1, 3, 5} |110010⟩ < |101010⟩−�������������� < |011010⟩ ↔ {2, 3, 5} |101010⟩ < |011010⟩ < |100110⟩ ↔ {1, 4, 5} |011010⟩ < |100110⟩ < |010110⟩ ↔ {2, 4, 5} |100110⟩ < |010110⟩ < |001110⟩ ↔ {3, 4, 5} |010110⟩ < |001110⟩ < |110001⟩ ↔ {1, 2, 6} |001110⟩ < |110001⟩ < . . . |110001⟩ < . . . (a) Writing address sets as binary numbers to determine their(b) Efect of the renaming : when is each case used. size. Fig. 11. Order and types of successive basis blocks, by writing the imageAof by the Indicator functionAofas a binary number. The patern identified byB or B is then represented as colored numbers. �,�+1 �,�+1 Lemma C.3. Let � be a gate of an AQC with address spaceA. Write� in the basis sorted by: (1) First, according to the size� of address sets Ðsee above. (2) Second, for each group of addresses, the words are sorted in lexicographical increasing order. Then S is blockwise diagonal with blocks corresponding to which addresses are present, and each of those blocks are equal. Proof. Consider the set of external addresses A = {� , . . .,� } ⊂ A of the gate operator� , and two �� 1 �−|�| ′ ′ successive sets of addressesA = {� . . .� } ⊆ A and A = {� . . .� } ⊆ A (both ordered as speciied in � 1 � �� �+1 �� the lemma and as seen in Fig. 11). Then, extract the smallest continuous varying B parts = {� ,� , . . .,� } �,�+1 � �+1 �+� ′ ′ ′ and B = {� , . . .,� } Ð also ordered the same way. Note that if� = � : �,�+1 � �+� B = {� ,� , . . .,� } �,�+1 � �+1 �+� � = � �+� +1 �+� We deine now a renaming� so that∀�,�(� ) = � . As a consequence, � always results in a identity block �+� �+� in the block column corresponding to the irst state and in the line of the second state Ðas this renaming preserves the relative order of such words on addresses. The renaming� is deined with the following case distinction: - Incrementation IfB is of the form{� }, then B is{� }. � is deined as the transposition swapping �,�+1 � �+1 �,�+1 � and � . � �+1 - Carry Else�, = 1. Then B = {� = � ,� ,� , . . .,� ,� } consists of� successive numbers inA �,�+1 � � �+1 �+2 �+� −1 �+� �� ′ ′ ′ with� > 0, and B = {� = � ,� , . . .,� ,� = � }. Therefore,� is deined as : 1 2 � −1 �+� +1 �,�+1 1 �+� (1) ∀� ∈ {1, . . ., �− 1},�(� ) = � � �+� (2) ∀� ∈ {�, . . ., �+ � − 1},�(� ) = � � �−�+1 ′ ′ (3) �(� ) = �(� ) = � = � , �(� ) = � �+� �+� �+� +1 �+� �+� �+� (4) �(�) = � for any other� ∈ A The property ∀�,�(� ) = � entails that �Π = Π , therefore :Π ��Π = � and Π ��Π = � . As �+� � �+1 �+1 � � �+1 � �+1 �+� �� = �� we have � = � . □ � �+1 ACM Trans. Quantum Comput. 34 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron C.5 From gate operators to(�,�)-nameblind matrices |�⟩ |���⟩ |�⟩ , |�⟩ |��⟩ |�⟩ , |�⟩ |�⟩ |��⟩ , |�⟩ |�⟩ |���⟩ , T I O T I O T I O T I O |�⟩ |��⟩ |�⟩ , |�⟩ |�⟩ |�⟩ , |�⟩ |�⟩ |��⟩ . T I O T I O T I O Fig. 12. The 7 subspaces with 3 external addresses of a one sector gate �,�,.and � represent a position of an address, spanned by any possible external address like in Fig. 8. Each one of the 49 blocks delimited by these subspaces contains a nameblind matrix. Proposition 4.7 (Decomposition of gate operators into (�,� )-nameblind matrices). Consider� a gate operator on addresses A which commutes with every external renaming. Consider any words on quantum data � & � , internal addressesA ⊆ � with positions� & � , external addresses A ⊆ A\� with positions� 1 ��� ��� ��� �� �� 1 2 1 & � . The action of� between states corresponding to these parameters� is a �� A ,A ,� →� ,� →� ,� →� ��� �� 0 1 ��� ��� �� �� 1 2 1 2 (�,� )-nameblind matrix with � = |A |. �� � � Proof. Let � be a gate and � = � a nameblind gate operator. First we decompose the large gate space H into 2|�| |Q | subspaces for each possible basis state of the dataspace. For each couple of basis|� states ⟩ ,|� ⟩ ∈ H 2|�| 0 1 we denote by � the block of� which maps states with data|� ⟩ to states with data|� ⟩. Since� is nameblind � →� 0 1 0 1 we have : Π ��|�⟩|� ⟩ = � � |�⟩|� ⟩ . � 0 � →� 0 1 0 1 On the other hand: Π ��|�⟩|� ⟩ = Π �� |�⟩|� ⟩ � 0 � 0 1 1 = �� |�⟩|� ⟩ � →� 0 0 1 where Π is the projector onto the subspace with data state � . These equalities imply that each block must � 1 commute with renamings. Furthermore, each � is block diagonal over subspaces � deined by a number of external addresses � →� � 0 1 � ∈ {0, . . .,|A \ �|} and a set of internal addresses A ⊆ �, because both parameters are preserved by �. We ��� cannot derive constraints between those diagonal blocks, since the subspaces � are preserved by renamings and gate operators. Then, we further divide the � subspaces into subspaces characterized by a ixed position for each internal addresses ofA , and � "slots" for external addresses. We enumerate these subspaces (see Figs. 8 and 12) and ��� denote them byH . Moreover, we write� = Π � where � is projection �ofontoH . Its coeicients are � � � [�,�] H H � � the same as the block of� in (block) column �and (block) line �. Let us show that this block is nameblind. Consider two subspacesH (corresponding to the block column/line �in�) and H (column/line �), and a � � renaming� that is external for �. We may for instance takeH with states of the form|���⟩ , where � ∈ � and �,� span all external addresses. The block � sp of ecifying what partH of goes toH is� . Let |w⟩ ∈ H be a � � � [�,�] state. On one hand, as |w⟩ and � |w⟩ both belong toH , they are handled by the same block column �of� (they are in the same subspace, as� does not modify or change the position �, of and make no internal address appear): Π (��|w⟩) = � � |w⟩ � [�,�] On the other hand : Π (��|w⟩) = Π (�� |w⟩) � � ACM Trans. Quantum Comput. Addressable quantum gates • 35 ︁ ︁ = Π ( � |�(� )⟩ + � |�(� )⟩) � � � � ∈H � ∉H � � = �( � |� ⟩) � ∈H = �� |w⟩ , [�,�] where in the third line we used�that preserves subspaces and thus commutes withΠ . As a consequence, for all |w⟩ ,� we have � � |w⟩ = �� |w⟩, and therefore� is nameblind. [�,�] [�,�] [�,�] Therefore, if a gate operator commutes with every renaming on external addresses, its matrix representation can be written blockwise with nameblind matrices. Vice versa, if a gate operator � can be partitioned blockwise as above into nameblind matrices, we can write ︁ ︁ ︁ ︁ ︁ ︁ �� = � � = � � = � � = ��. [�,�] [�,�] [�,�] � � � � � � When handling the nameblind blo � cks , we may simply consider that � is acting on a state of the form [�,�] |� . . .� ⟩ where � are external addresses, and ignore the internal addresses and the speciic subspaces in which 1 � � are the external addresses, as those does not change. Therefore, by Prop. 4.6 these operators are isomorphic to (�,� )-nameblind matrices and can hence be written blockwise (�,�)-nameblind as matrices by Thm. 4.4. D COMPOSING AQCS Several ways of composing AQCs are possible. Here we deine: Parallel composition of AQCs corresponds to executing them in parallel without interaction. Concatenation of AQCs corresponds to successively applying them to the quantum data. Connection of AQCs is also deined, and allows for a more general connectivity without assuming an intrinsic (temporal) order between AQCs. D.1 Parallel composition The simplest combination of AQCs is parallel composition, which intuitively means executing them both side by side, separately: Deinition D.1 (Parallel composition). Let A,B be two disjunct address sets, and let � and � be the corre- A B ≤� ≤� sponding AQC with skeletons � = (A,G ,D ,� ) and � = (B,G ,D ,� ) and states |� ⟩ and |� ⟩. A A A B B B A B A B ≤� +� Theirparallel composition� || � is deined as((A∪B,G ∪G ,Q ,� ),|� ⟩), whereQ = (D ∪D ) A B A B C C C C A B � ′ � and the scattering� applies �to∈ G the trivial extension � of� fromA to A ∪B and fromQ to Q , C A A C A A and similarly� ∈ forG . By trivial extension, we mean that � ∈if G , then � acts as the identity on addressesB ofand on data of Q \Q . C A D.2 Connection Explicitly including the sectors 1 and 4 in the Bell state creation circuit (see 1Fig. and 1) 6 of or se the ctors quantum switch (see Fig. 4a) helps distinguishing where the data is coming from and where it is going to. AQC are ininitely evolving systems and, as such, may not be perfectly itted to express inite computations. However, these sectors, which at irst sight seem superluous, provide a uniied template to portray inite quantum circuits, ACM Trans. Quantum Comput. 36 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron possibly followed by a measurement. In other words, they are useful to determine beginning and endpoint of a inite computation, and we use them as sectors where we place our initial data in and take the inal data out. Moreover, the presence of these sectors becomes crucial as soon as we want to compose AQCs and make them interact. Indeed, we will do so by identifying the outgoing sectors of an AQC, with the ingoing sectors of another. The following deinition paves the road to composing AQCs, by making it explicit which sectors can be identiied. Deinition D.2 (Ingoing and outgoing bufer sectors). Let ((A,G,Q,�),|�⟩) be an AQC and � ∈ A be an address. We call the sector�atan ingoing bufer sectorif • � does not occur in|�⟩, i.e. the sector cannot be targeted during the evolution, • {�} ∈ G, and {�} • � = � (the lip ś see A.1). Similarly, we call the se�ctor an outgoing at bufer sectorif • |�⟩ = |�⟩ ⊗ |�⟩, i.e. the state of the sector� is initially empty, • {�} ∈ G, and {�} • � = �. As a consequence, it is possible to łmergež outgoing with ingoing sectors into a single sector having the address of the outgoing bufer sector and the internal state of the ingoing bufer sector, for an example see Fig. 13b. merged bufer sector outgoing bufer sector ingoing bufer sector 1 3 7 1 3 7 5 9 5 6 9 � � 2 4 8 2 4 8 � � � � � A B � ⊙ � A {6},{5} B (a) Sector5 is empty, Sector6 is targeted by no one. (b) Sectors5 and 6 are merged. Fig. 13. Concatenating two AQCs� and � along {6} and {5}. In the end, sector5 is no longer an outgoing bufer sector A B and sector6 does not exist anymore. Deinition D.3 (Connection of AQCs). Let � ∈ N and � . . .� be AQCs with corresponding sets of addresses 1 � A . . .A so that∀�≠ �,A ∩A = ∅ and skeletons� = (A ,G ,Q ,� ). Moreover, let|�⟩ be the tensor product 1 � � � � � � � � of their (initial) states, I and andO the sets of their ingoing and outgoing bufer sectors. I =Let{� , . . .,� } ⊆ � � 1 � Ð Ð � � I and O = {� , . . .,� } ⊆ O such that I∩ O = ∅. The connection of� . . .� along (I, O) is denoted � 1 � � 1 � �=1 �=1 � = Conn(I, O,{� . . .� }) = ((A ,G ,Q ,� ),|� ⟩) 1 � C C C C C where � � Ð Ð • A = A \ I and G = G \{{�},�∈ I} is the set of addresses of � with corresponding gate C � C � �=1 �=1 set, Ë Ë Ë � � � • |� ⟩ = |� ⟩ ⊗ |� ⟩ when |�⟩ is of the form |� ⟩ , with the general case following by linear C � � � �=1 �∈A \O extension. ACM Trans. Quantum Comput. Addressable quantum gates • 37 � � Ð Í ≤� ≤� � • Q = ( D ) , where � = � and those � are such that Q = D . � � � � � �=1 �=1 • � is the trivial extension�ofasall in Def. D.1. � � The connection of an AQC with the trivial AQC, which consists only of a single empty sector, is the identity operation, given how ingoing and outgoing bufers are merged. Moreover, note that parallel composition is a special type of connection, where the connecting I and Osectors are empty, i.e. � || � = Conn(∅,∅,{� ,� }). A B A B With such a general notion of connection, one may connect an AQCs to form a loop, or even connect an AQC to itself Conn ( (I, O,{� })). The resulting AQC may be an evolving structure with neither ingoing nor outgoing bufers. Such constructions are of course not very physical, since they lack a way for quantum data to enter and or exit, and thus cannot be connected to any other AQC: For an AQC to correspond to a quantum circuit, it has to include at least one ingoing and one outgoing bufer. However, the AQC model as presented in this paper allows for the deinition of more general systems, without an input or an output node. Intuitively, such AQC are not physically implementable as a circuit in a satisfying way, as they lack a way for quantum data to enter and to exit it. They are still causal structures, as the evolution is driven by local reversible rules and gates may be applied on no data, i.e. vacuum states11 [ ]; no causality problem arises if some data enters the same sector twice during the ininite evolution. The alternative to composition with ingoing and outgoing bufers would have been to manipulate op ł en AQCž, i.e. featuring addresses that correspond to no sector, and then plugging these open AQCs together. This causes several problems however, as the transport step may be undeined, and renaming only one of the open AQCs may change the nature of the composition. D.3 Concatenation Another type of connection is a concatenation � :⊙ � = Conn(I, O,{� ,� }), where I only contains A I,O B A B addresses fromB and O only address fromA. Concatenation satisies some kind of associativity property: for all input (resp�.,output) � , � ,�sets : 1 2 � ∩ � = ∅ ⇒ (� ⊙ �) ⊙ � = � ⊙ (� ⊙ �). 1 2 � ,� �,� � ,� �,� 1 2 1 2 Without the condition to the left, the equality on the right holds, but may also be meaningless, as some sectors might have disappeared during the irst operation to be applied, or simply not be outgoing or ingoing anymore. Notice that similar to causal b27 oxes ] and [ contrary to quantum combs, the concatenation of two AQCs is an AQC. Example D.4. Let us concatenate the quantum switch� deined in Sect. 3.1 and the Bell state creation circuit � of Fig. 1 with address sets A = {1, 2, 3, 4, 5, 6} and B = {7, 8, 9, 0}, respectively. As unitaries in the quantum switch, take the Pauli gates � = � and � = � on a single qubit. Moreover, to facilitate matters|w � e⟩take = |�⟩ as initial state of the quantum switch so that after concatenation data is only present at the beginning of the Bell state creation circuit. We show in detail the steps of the evolution � and � concatenate of d along� = {0} and � = {1} in Fig. 14, wher�e⊙ � = Conn(�, �,{�,�}). �,� ACM Trans. Quantum Comput. 38 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron 1 3 5 � � � 7 8 9 � � � � � � 2 4 � � 345 � � � � � (a) Initial state of the concatenation � ⊙ � of the Bell state creation circuit and the quantum switch. �,� 1 3 5 � � � 7 8 9 (00+11) � � � � � 2 4 6 � � � 345 � � � � � (b) State of� ⊙ � ater the Bell state circuit. �,� 1 3 5 � � � 7 8 9 � � � � � � 2 4 6 � � � 345 � � � � (10−01) (c) łFinalž state of � ⊙ � ater the uantum Switch AQC. A global phase �is omited. �,� Fig. 14. Evolution of � ⊙ � , concatenation of two AQCs of Ex. D.4, with initial state 00 �,� Remark D.1. Outgoing bufer sectors correspond to the physical locations where the quantum data is measured. We do not discuss the possibility of measuring sectors here, yet it is straightforward to see how to do that. To represent a circuit with deinite beginning and end, one would execute the AQC until quantum data reaches an outgoing sector. E RELATION BETWEEN AQC AND QCGD Another approach to represent indeinite causal orders is to shun away from the circuit formalism and take inspiration from cellular automata. The QCGD frame 5] featur work [es quantum superpositions of graphs evolving synchronously according to unitary local rules. Each vertex has a local quantum state and communicates with other vertices via ports. Compared to AQCs, vertices have replaced gates and edges have replaced wires. Like QCGD, our model is able to represent a quantum superposition of diferent graphs (the graphs of connectivity between gates). The interdiction of non-causal evolution in QCGD may appear as contradictory with the sudden appearance of an edge in the AQC between nodes of diferent gates Ð for instance, when an address suddenly goes from the input address space to the target. However, by encoding address spaces into port names, one may simulate this seemingly non-causal edge appearance at the cost of having a larger number of ports Ðsee below . We can therefore encode any AQC into a QCGD. The reverse simulation is a challenging open problem. Encoding of AQC into the QCGD formalism. A gate operator can be encoded on local unitary rewritings, and multi-sector gates are implemented by connecting its sectors to a central common vertex, via a certain �. port A minor diiculty is that in an AQC, a sector may suddenly target seemingly faraway sector, whereas in a QCGD, vertices may only connect to closeby vertices. However, when an AQC does this, it is because the faraway sector’s address is a stored address. Therefore, we must encode stored address spaces as QCGD edges. ACM Trans. Quantum Comput. �� �� �� Addressable quantum gates • 39 � � {3} � � τ � � � � 1 2 {2,5} 5 6 � � {1} {6} 4 {4} Fig. 15. Ports of a sector verte�x, Fig. 16. Simplified representation of the encoding as a QCGD of the where A = {� ,� , . . .,� }. quantum switch. Notice that ports are not represented. Red nodes are 1 2 � gate-vertices, white nodes are sector-vertices. Red edges use the ports � , black edges link the target port τ to the entry port �, blue edges link output p�orts ��to entry ports�. For clarity purposes, the translation presented here3�has+ 1 ports and � + � vertices for an AQC with � sectors and � gates, but smaller, less trivial encodings are possible. Deinition E.1 (Encoding into QCGDLet ). � = ((A,G,Q,�),|�⟩) be an AQC. In the canonical basis of the circuit space|�,⟩ = � |� ⟩, where each � is a basis state. The superposition of quantum graphs �(�) = |G⟩ = � � � � � |G ⟩ encodes � , where each G is deined as follows: � � � � � • The set of vertices isV: = {� | � ∈ A} ∪ {� | � ∈ G} where the vertices{� | � ∈ A} represent the � � � sectors, while the vertices {� | � ∈ G} represent the gates and will be used to regroup all sectors of a same gate. • Each vertex has ports � = {� | � ∈ A}∪{�}∪{τ,�� ,�� , . . .,�� ,���,���, . . .,��� }. � 1 2 |A| 1 2 |A| The ports{� | � ∈ A} are used by the gate-vertices to connect to their sector-vertices and reciprocally. The ports {τ,�� ,�� , . . .,�� ,���,���, . . .,��� } are used to represent the target space, the input address 1 2 |A| 1 2 |A| space and the output address space of the sectors. Any edge from those ports is connected to the entry port � of the corresponding addressed sector-vertex. • The set of labels depends on|� ⟩. Each sector � having a quantum data space containing the state � ′ ′ |�⟩ |� ⟩ sees its corresponding verte�x being labelled(with �,� ). Each vertex � is labelled�with . � � Q Q � ′ � • The set of edges depends on|� ⟩. Each sector� having an address space containing the state |�⟩ |�⟩ |� ⟩ I O sees its corresponding verte�x have the following edges : {{� : ��,� : �} | ∀� ∈ �} � � � � ′ ′ ′ {{� : ���,� : �} | ∀� ∈ � } � � � � {� : τ,� : �} Moreover, each sector � is in a gate �, embodied by the edge : {� : � ,� : � } � � � � ACM Trans. Quantum Comput. ��� ��� ��� . 40 • Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron Remark E.1. The condition "address appear at most once in an AQC" in Def. 2.7 ensures that at most one edge uses the port � of any vertex. Deinition E.2 (Evolution of Encoding). The operator � = � � is the following quantum causal graph dynamic � � acting on|G ⟩ by changing the labels and edges of vertices according to the labels and edges of łnearbyž vertices: • � implements the transport step. It applies synchronously for ever{y�edge : τ,� : �} the following � � � evolution: – (Swap of input and output address spaces)For any �,�∈ [1 . . .|A|], the edges {� : �� ,� : �} disappear � � � and are replaced by{� : ���,� : �}, while edges{� : ���,� : �} disappear and become edges � � � � � � {� : �� ,� : �} � � � – (Swap of input and output data spaces)Let � be the second part of the label of verte � .xLet � be the irst part of the label of verte � .xAfter applying � , the second part of the label of verte � xbecomes �, and � � � the irst part of the label of verte � bxecomes � . • � implements the scattering step. It is synchronously applied�on∈evV ery of label � , corresponding � � to the gate � ∈ G, and can be explained by the following substeps : (1) Remember that the vertices{� | � ∈ �} are exactly the neighbours of verte � x. One builds the state of � � the equivalent AQC-gate space : � � |�⟩ = |�⟩ , �∈� where each |�⟩ is build from the quantum labelled graph: – The target space is|�⟩ if there is an edge {� : τ,� : �}. Else, it|is �⟩. � � – The input address space contains the (potentially empty)�w=or�d . . .� where, for each edge 1 |A| {� : ��,� : �}, � = �. If there exists no such edge for some �∈ [1 . . .|A|], the corresponding� is � � � � � equal to�. – The output address space is illed like the input address space, by replacing �� byeaver ��y� in the � � line above. ′ � ′ � – Let (�,� ) be the label of verte � x. The input and output address spaces of sector� are |�⟩ |� ⟩ . Q Q (2) � (obtained from the label of verte � ) is x applied to the gate space |�⟩ , which therefore becomes �∈� � � ′ � |� ⟩ = � |�⟩ �∈� (3) The edges and labels are rewritten from the state |� ⟩ , using the construction explained in step 1 (and Def. E.1). in the other directionÐthis time constructing the subgraph (or potentially a superposition of subgraphs) from the gate space. Proposition E.3 (Eqivalence of Evolution of Encoding). Let � be an AQC. Then �(�� ) = ��(�) where � = � � implements the AQC evolution operator� = �� and with� as in Def. E.1. � � F NOTATIONS Let S be a inite set. We denote by� inite strings with alphab S, i.e et �. = � � . . .� with� ∈ S. Moreover, � 1 2 � � denotes the empty string. Words of addresses written as letters with overlines �) may b(e of length 0. Letters without overline �) r(epresent words of length 1. From a inite setS we construct the Hilbert spaceH = C = { � |�⟩ ,� ∈ C} with scalar product⟨�|�⟩ = � ′. In other words, to each element�∈ S is associated a unit � � �,� �∈S vector |�⟩, such that the family (|�⟩) is the canonical orthonormal basis H .of IfS were countably ininite, �∈S S we would have ensured square-summability by taking H = ℓ (S). The other notations used in the paper are summarized in Tab. 1 on the next page. ACM Trans. Quantum Comput. Addressable quantum gates • 41 Notation Deinition Occurrence A A set of addresses, namely, a inite subsetNof . Def. 2.1 G A set of gates, namely, a partition of some A. Def. 2.6 T A set containing all addresses and the empty addr �,ess called set ofDef. 2.1 targets. W The set of words on addresses where no address repeats.W = Def. {� . . .� |� ∈ A,� ≠ � ∀�, �} 2.1&A.1 1 � � � � � A list of addresses. It usually denotes an element W orofW ⊗W. Def. 2.1 D A inite set, called set of data values. Def. 2.3 ≤� Q The set of data words of length at most � for some� ∈ Nś i.e.Q = D . Def. 2.3 � An element inQ. Def. 2.3 ∀S,H The Hilbert space constructed from any set S as speciied in Sect. F Sect. F H Hilbert space onT called target space. Def. 2.1 H Hilbert space onW called stored address space. Def. 2.1 H Hilbert space onQ called data space. Def. 2.3 H Input space. It is the tensor product ofH andH . Def. 2.4 � W Q H Output space. It is the tensor product ofH andH . Def. 2.4 � W Q H The sector space associated to�. It is the tensor product ofH ,H and Def. 2.4&2.6 T � H . � � � H The sector space associated to a gate� ⊂ A :H = H Def 2.6 �∈� H Circuit spaceH. = H Def. 2.7 �∈A |�⟩ A basis state ofH . Eq. 5 |�,�⟩ A basis state ofH . Ex. 2.9 |�,�⟩ A basis state ofH . Eq. 7 |�,�⟩ A basis state of the output space of sector �. Eq. 2 |�,� ⟩ A basis state ofH ⊗H . Eq. 5 W W W � � |�,� ⟩ A basis state ofH ⊗H . Eq. 5 Q Q Q � � |�⟩ A basis state of the i-th sector space. It can be decomposed either asDef. : 2.8 � � � � � ′ ′ � ′ ′ |�⟩ |�,�⟩ |� ,� ⟩ or as : |�⟩ |�,� ⟩ |�,� ⟩ O W Q T I T |�⟩ Where � ∈ {T,W,Q} is the corresponding space of the �-th sector. Def. 2.8 |32⟩ The state |3 2⟩ (ketśthreeśtwo), while being distinct from the state Ex. 2.2 |32⟩ (ketśthirtyśtwo), is always written as|32⟩ . This causes no confu- sion, as only address sets with fewer than ten addresses are used in this paper. � The scattering step. Def. 2.8 � The transport step. Def. 2.8 � � = ��, the global evolution operator. Def. 2.8 Table 1. Notations used in the paper ACM Trans. Quantum Comput.

Journal

ACM Transactions on Quantum Computing – Association for Computing Machinery

Published: Apr 24, 2023

Keywords: Models of distributed quantum computing

References

  • Adiabatic quantum computation
    [,
  • Computational advantage from quantum-controlled ordering of gates
    [,
  • On quantum superpositions of graphs
    [,
  • Quantum networks theory
    [,
  • Quantum causal graph dynamics
    [,
  • Theoretical framework for higher-order quantum theory
    [,
  • Coherent control and distinguishability of quantum channels via PBS-diagrams
    [,
  • Dynamics of quantum causal structures
    [,
  • Indefinite causal order enables perfect quantum communication with zero capacity channels
    [,
  • Quantum computations without definite causal structure
    [,
  • Quantum Shannon theory with superpositions of trajectories
    [,
  • PBS-calculus: A graphical language for coherent control of quantum computations
    [,
  • Information spreading in dynamic graphs
    [,
  • Quantum algorithms revisited
    [,
  • Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning
    [,
  • Anonymous networks: Randomization= 2-hop coloring
    [,
  • On the impact of identifiers on local decision
    [,
  • Node labels in local decision
    [,
  • Implementing quantum control for unknown subroutines
    [,
  • Communicating quantum processes
    [,
  • Indefinite causal order in a quantum switch
    [,
  • Exponential communication complexity advantage from quantum superposition of the direction of communication
    [,
  • Quantum random walks: An introductory overview
    [,
  • Causal and compositional structure of unitary transformations
    [,
  • Time-delocalized quantum subsystems and operations: On the existence of processes with indefinite causal structure in quantum mechanics
    [,
  • Quantum correlations with no causal order
    [,
  • Causal boxes: Quantum information-processing systems closed under composition
    [,
  • Experimental superposition of orders of quantum gates
    [,
  • The one-way quantum computer–a non-network model of quantum computation
    [,
  • Experimental verification of an indefinite causal order
    [,
  • Computational advantage from the quantum superposition of multiple temporal orders of photonic gates
    [,
  • Routed quantum circuits
    [,
  • Existence of processes violating causal inequalities on time-delocalised subsystems
    [,
  • Quantum circuits with classical versus quantum control of causal order
    [,
  • Experimental quantum switching for exponentially superior quantum communication complexity
    [,
  • A Diagrammatic Approach to Information Transmission in Generalised Switches
    [,