Chirality from quantum walks without quantum coin
Giacomo Mauro D'Ariano Marco Erba Paolo Perinotti




dariano@unipv.it

marco.erba@unipv.it

paolo.perinotti@unipv.it
Università degli Studi di Pavia, Dipartimento di Fisica, QUIT Group, and INFN Gruppo IV, Sezione di Pavia, via Bassi 6, 27100 Pavia, Italy

Quantum walks (QWs) describe the evolution of quantum systems on graphs. An intrinsic degree of freedom—called the coin and represented by a finite-dimensional Hilbert space—is associated to each node.


Scalar quantum walks are QWs with a one-dimensional coin. 

We propose a general strategy allowing one to construct scalar QWs on a broad variety of graphs, which admit embedding in Eulidean spaces, thus having a direct geometric interpretation. After reviewing the technique that allows one to regroup cells of nodes into new nodes, transforming finite spatial blocks into internal degrees of freedom, we prove that no 

QW with a two-dimensional coin can be derived from an isotropic scalar QW in this way. Finally we show that the Weyl and Dirac QWs can be derived from scalar QWs in spaces of dimension up to three, via our construction.


02.10.Ox, 02.10.Yn, 02.20.-a, 03.65.Ta, 03.65.Pm, 03.67.-a, 03.67.Ac

Chirality from quantum walks without quantum coin
    Paolo Perinotti
    December 30, 2023
=================================================






§ INTRODUCTION

Quantum walks (QWs) on graphs <cit.> describe the evolution of quantum systems in a discrete arena. Their applications range from quantum information and computation <cit.>—where they have been applied to design search algorithms <cit.>—to discrete approaches for the foundations of relativistic Quantum Field Theory (QFT) <cit.>—where QWs are particularly suitable for a reformulation of free QFTs in a discrete scenario <cit.>.
In particular, foundational investigations have been carried out focusing on how a continuous space-time, fermionic dynamics and Lorentz symmetry can be reconstructed by a discrete and purely quantum theory <cit.>. In Ref. <cit.> it has been proved that, under the physical assumption of homogeneity of the physical evolution [This assumptions require not only that the QW evolution rule is the same at each node, but also that the nodes are not distinguishable on the basis of the evolution, i.e. that the if a labeled path is closed starting from a given node, then it is closed starting from any other node.], the graph of the QW must be in fact a Cayley graph, namely the graphical representation of a group. This allows one to exploit the group-theoretical machinery, which is of aid in order to construct the QWs, analyze them and connect the graph to the emergent continuous geometry <cit.>.

Historically <cit.>, QWs have been introduced in the broader context of Quantum Cellular Automata (QCAs) <cit.>, which provide a general model for the local unitary evolution of quantum systems on arbitrary graphs. In the case where the evolution law is linear in the fields, a QCA reduces to a QW, representing the quantum counterpart of the classical random walk model. 


So far, the case of a Euclidean emergent space has been particularly studied, as a simplifying restriction of the theory. It is worth mentioning here that, in fact, non-Euclidean cases have been hardly treated in the context of QWs, while the literature focuses on QWs on lattices. The main reason to focus on the Euclidean case is that lattices have a convenient embedding in the usual space ℝ^d. Furthermore, this has the advantage of allowing one to easily define the Fourier transform on the lattice and analyze the QWs dynamics in the wave-vector space, and this in turn provides a straightforward procedure for taking the continuum limit. Restricting to Cayley graphs which have a Euclidean emergent space ℝ^d is equivalent to consider groups containing finitely many copies of ℤ^d <cit.>: these groups are called virtually Abelian <cit.>.

A QW is, loosely speaking, a unitary evolution for a wave-function on a graph. Each vertex of the graph is structured as a local quantum system, and thus associated with a finite-dimensional Hilbert space, usually referred to as the coin system of the walk at a given vertex. If the QW is homogeneous, every vertex is equivalent, and thus all the coin systems are isomorphic to a prototype Hilbert space called the coin system of the QW. One can now constructively analyze all the conceivable QWs on a given graph. This analysis can be carried out in a twofold way: on the one hand, one can fix the simplest allowed group, i.e. ℤ^d itself, and investigate the admissible QWs defined on its Cayley graphs, varying the coin dimension s; on the other hand, one can fix s and construct all the admissible groups and graphs complying to the Euclidean restriction. The first path has been carried out in Refs. <cit.>.

In this manuscript, we explore the second way, starting with the minimal coin dimension s=1, and performing a systematic analysis of the Euclidean scenario. QWs with a one-dimensional coin are often referred to as scalar or coinless <cit.>. Despite the algorithmic simplicity of the model, finding all scalar QWs for an arbitrary graph is not a straightforward task. Indeed, the resolution of the unitarity constraints involves a quadratic system of complex equations, and it turns out that it is simpler to address the problem as a matrical one. In Ref. <cit.>, scalar QWs on Cayley graphs of arbitrary Abelian groups have been classified, finding that they give rise to trivial dynamics: this result extends the classical no-go theorem by Meyer <cit.>. Therefore, the present approach is to undertake a systematic investigation of QWs on Cayley graphs of virtually Abelian groups, relaxing the Abelianity assumption. This allows to have nontrivial dynamics.

The present manuscript benefits from the work carried out in Refs. <cit.>, and represents their completion. Here we construct the first examples of infinite scalar QWs with more than one space-dimension; moreover, we avoid partitions of the underlying graph or of the QW itself, as opposed to the literature where the partition is used <cit.> to circumvent the no-go theorem <cit.>, leading to an inhomogeneous evolution. Furthermore, the scalar QWs constructed here are both non-Abelian and infinite, unlike those explored in Ref. <cit.>, where only finite graphs have been considered.

The manuscript is organized as follows. In Sec. <ref> we review the general model of discrete-time QWs on graphs; we then specialize our treatment to the Euclidean case, establishing a connection between algebraic and geometrical properties of groups. In Sec. <ref> we study the group extension problem in generality, proving some structure results and reviewing a coarse-graining technique for QWs on Cayley graphs; we then apply the aforementioned results and technique to the Euclidean case. In Sec. <ref> we investigate the Euclidean scalar QWs, proving a no-go theorem in the isotropic case, and then paving the way for the study of a particular class of QWs in space-dimension d=1,2,3. In Sec. <ref> we apply the group extension technique to particularly analyze the case of scalar QWs whose coarse-grainings are QWs with a two-dimensional coin on the simple square and on the BCC lattices; finally we derive the Dirac QW in two and three space-dimensions as the coarse-graining of a scalar QW on the Cayley graph of a non-Abelian group. In Sec. <ref> we conclude the manuscript discussing some (open) aspects of the theory and drawing our conclusions.





§ DISCRETE-TIME QUANTUM WALKS ON GRAPHS





















For the convenience of the reader, we start recalling the basic notion of a directed graph.



	A directed graph or digraph is an ordered pair Γ = (V,E), where V and E are set such that E collects arbitrary ordered pairs (x_1,x_2) of elements x_1,x_2∈ V. The elements in V are called the vertices and those in E the edges of the graph.

The vertices are graphically represented as dots and are also called the sites or nodes. The set E of edges defines the connectivity between the vertices of the graph: an edge (x_1,x_2) is graphically represented by an arrow having direction from x_1 to x_2. In the following we define the neighbourhood schemes for the sites of a graph.

	Let Γ = (V,E) be a graph. We define the first-neighbourhood of each site x∈ V as the set
	
    N_x { y∈ V . | . (x,y)∈ E },

	namely all the vertices reached by arrows from x. The elements contained in N_x are called first-neighbors of x. The complement of the first-neighborhood of each site x∈ V is the set defined as
	
    N_x^-1{ y∈ V . | . (y,x)∈ E } .


We are now ready to give the definition of a discrete-time QW on a graph.

	
	Let Γ = (V,E) be a graph and let a finite-dimensional Hilbert space ℋ_x be associated to each node x∈ V. A QW on Γ in ℋ⊕_x∈ Vℋ_x is a unitary operator W providing a time-homogeneous evolution defined as follows:
	
    W : ℋ    ⟶ ℋ
    |ψ(t)⟩    ⟼ |ψ(t+1)⟩

	
	
	
	for all times t, such that, defining Π_x as the projection on ℋ_x, one has
	
    Π_xW:
    		⊕_y∈ N_x^-1|ψ_y(t)⟩    ⟼ |ψ_x(t+1)⟩  ∀ x∈ V.


This defines a discrete-time evolution on a graph Γ according to its neighbourhood schemes. By linearity of the operator W, 

one can block-decompose the evolution as:
	
    Π_xW⊕_y∈ N_x^-1|ψ_y(t)⟩ = ∑_y∈ N_x^-1A_yx|ψ_y(t)⟩,

	where the A_xy are dimℋ_x ×dimℋ_y matrices, called the transition matrices of the QW.
Definition <ref> represents the general definition of a QW, as originally given in Ref. <cit.>, namely every QW model admits a form (<ref>). We now wish to represent the QW evolution on the total Hilbert space

    ℋ_tot⊕_x∈ V|x⟩⊗ℂ^s_x≅ℋ.

One can verify that the action of the QW evolution is represented on ℋ_tot by the following operator:

    A = ∑_x∈ V∑_y∈ N_xΔ_xy⊗ A_xy∑_x∈ V∑_y∈ N_xyx⊗ A_xy.












We notice that the evolution can be rewritten in terms of the first-neighborhoods, while in expression (<ref>) the sum is on their complements. Thus the walk operator can be finally written in terms of the  edges of the graph as:

    A = 
    	
    	∑_x∈ V∑_f∈ D_xΔ_xx_f⊗ A_xx_f,

where the set D_x collects the edges f connecting x to its first-neighbors x_f and the Δ_xx_f are the shift operators, mapping |x⟩ to |x_f⟩. Eq. (<ref>) represents the most general form of a QW evolution operator. The graph structure is inferred from the neighborhood schemes N_x and the evolution may also be inhomogeneous in the sites. In the following, as already discussed, we will restrict to homogeneous QWs, namely such that one has: (i) D D_x=D_x', (ii) |N_x|=|N_x'|,|N_x^-1|=|N_x'^-1|, and (iii) A_xx_f=A_x'x'_f for all x,x'∈ V and f∈ D. Accordingly, we consider regular directed graphs. Moreover, the edges are equipped with the same set of associated transition matrices. Thus, the dimension of the coin system is taken to be the same at any vertex—say s.

Accordingly, ℋ_tot= ℓ^2(V)⊗ℂ^s, and one has the following form for the evolution operator:

    A = ∑_f∈ DΔ_f⊗ A_f ∑_f∈ D(∑_x∈ Vx_fx) ⊗ A_f,

where D collects the set of edges, x_f represents the first-neighbor of x connected by the edge labeled as f, and the A_f are s× s complex matrices.

Equations (<ref>) and (<ref>) are equivalent expressions providing the evolution of a QW in terms of the transition matrices. In the literature, it is quite common to present QWs in terms of a decomposition into a product of (generally unitary) operators, namely in the following form:

    |Ψ(t+1)⟩   = ∑_x∈ Vxψ_x(t+1) = A|Ψ(t)⟩ = 
       =∑_x∈ VO_1O_2⋯ O_n xψ_x(t).

In general, these operators take the form

    O_l = ∑_i,j=1^s c_ij^l S_ij^l ⊗ij,

where c_ij^l∈ℂ, {|i⟩}_i=1^s is the canonical basis of ℂ^s, and the S_ij^l act as shift operators, namely

    S_ij^l|x⟩ = |π_ij^l(x)⟩

for some permutation π_ij^l (including the identical one) of the vertices of an underlying graph. Examples of decomposition (<ref>) can be found in Refs. <cit.>. It is common to associate a geometrical meaning to the shift operators appearing in the definition of the operators O_l, namely to infer the graph structure from these. Yet this interpretation is in some sense misleading, since, for a fixed QW, the decomposition in the form (<ref>) may not be unique. Consequently, the same QW might be decomposed into “virtual” steps, as in (<ref>), in several ways. On the other hand, all such different decompositions correspond to a unique expression of the form (<ref>). Moreover, the “virtual” steps in (<ref>) are not elementary steps of the walk evolution: the elementary steps are in any case given by each application of the total walk operator A=O_1O_2⋯ O_n. In the context of homogeneous QWs, a paradigmatic example of this fact is given by the three-dimensional Dirac QW. In Ref. <cit.> one can find the Dirac QW expressed as a product of three unitaries, each involving a translation on one Cartesian axis, corresponding to a decomposition on a simple cubic lattice. The same QW can be expressed in the form (<ref>) on the BCC lattice. In two recent works <cit.> one can find the two-dimensional Dirac QWs decomposed into local operators in several ways, each one with a different “virtual” graph. Nevertheless, each of them is indeed a different decomposition of the same QW, namely the two-dimensional Dirac QW on the simple square lattice <cit.>. On the other hand, in Ref. <cit.> a theorem has been proven stating that, for isotropic QWs on lattices (graphs embeddable in ℝ^d) with a two-dimensional coin, expression (<ref>) identifies indeed a unique graph for d≤ 3 (namely the integer lattice in d=1, the simple square in d=2, and the BCC lattice in d=3). We point out that, however, the different equivalent decompositions (<ref>) have in fact a relevance with regard to the concrete implementation and simulation of the same QW.






 §.§ Quantum walks on Cayley graphs

In the present subsection we shall treat QWs on Cayley graphs in full generality. In Subsec. <ref> and from Subsec. <ref> onwards, we shall restrict our attention to Cayley graphs of virtually Abelian groups (i.e. the Euclidean case). 

Throughout this paper, we will write G_1 ≤ G_2 if G_1 is a subgroup of G_2, and G_1⊴ G_2 if G_1 is normal in G_2. Finally, Z(G) will denote the center of G.

Consider a finitely generated group

    G = S_+|R,

where S_+ is a (finite) generating set for G, and R a set of relators. We will denote the set of inverses of the elements in S_+ by S_-. A generating set S_+ is called symmetric if S_+=S_- and we define the set of generators S S_+∪ S_- of G, which is clearly symmetric. Every group element g∈ G is a word defined on the alphabet S. On the other hand, R is a set of closed paths generating all the cycles in the group by concatenation or conjugation with arbitrary words. The closed paths correspond to words of S which amount to the identity element e∈ G. 

Expression (<ref>) is called a presentation of G. In the following, we will restrict our attention to finitely presented groups, namely such that also |R|<∞ holds. Every group can be presented, in principle, in infinitely many ways, the presentations being in one-to-one correspondence with Cayley graphs, as it is clear from the following definition.


The Cayley graph Γ(G,S_+) of a group G with respect to the generating set S_+ is the edge-coloured directed graph constructed as follows: (i) G is the vertex set of Γ; (ii) for all g∈ G, a coloured edge directed from g to gh is assigned to each h∈ S_+.


Edges corresponding to some h∈ S_+ are represented as undirected if and only if h^2 = e. In general we allow e∈ S_+, whose corresponding edges can be denoted by loops on the Cayley graph.

We shall consider the right-regular representation T of a group G on ℓ^2(G), given as follows. We will denote
by {|g⟩}_g∈ G the canonical basis for ℓ^2(G) and we define

    T_g'|g⟩|gg'^-1⟩,

from which it follows that T_gT_g'=T_gg' for all g,g'∈ G. By construction, the right-regular representation is unitary. For finite G one has ℓ^2(G) ≡^|G|.

	Let G be a finitely presented group. A quantum walk on the Cayley graph Γ(G,S_+) with an s-dimensional coin is the quadruple

    W={G,S,s,{A_h}_h∈ S},

such that:


  * s∈^+;

  * for all h∈ S, the transition matrices A_h∈M_s();

  * the operator

    A = ∑_h∈ ST_h⊗ A_h

defined on ℓ^2(G)⊗^s is unitary.



The walk operator (<ref>) is unitary if and only if all the following system of equations holds:

    ∑_h,h'∈ S
    hh'^-1=gA_hA_h'^† = ∑_h,h'∈ S
    h^-1h'=gA_h^† A_h' =δ_g,eI_s, 
    ∀ g∈{ g'∈ G .|. ∃ h_1,h_2∈ S  g'=h_1h_2^-1} .

Eq. (<ref>) can be checked just plugging expression (<ref>) into the unitarity conditions:

    A^†A = AA^† = T_e ⊗ I_s.

Given a Cayley graph Γ, the unitarity conditions (<ref>) represent nontrivial constraints to solve in order to define a QW on Γ.

The following definition is useful to introduce the generalized notion of isotropy for QWs <cit.>. This feature is relevant to model the physical law in a theory aiming to reconstruct relativistic QFTs. Given a group G, the order of an element g∈ G is defined as the natural number

    r_gmin{ r∈^+  g^r = e } .

If r_g does not exist, the order of g is said to be infinite. We are now ready to define an isotropic QW.


	
A QW on the Cayley graph Γ(G,S_+) with a s-dimensional coin is called isotropic if there exists a faithful unitary representation {U_l}_l∈ L on ^s of a graph automorphism group L, called the isotropy group, satisfying the following:


  * L is transitive on the classes of elements of S_+ having the same order [In the original definition <cit.>, where just free Abelian groups were considered, this requirement has been stated without mentioning the possibility of different element-orders.];

  * the following invariance condition holds:

    ∑_h∈ ST_l(h)⊗ U_l A_h U_l^†=∑_h∈ ST_h⊗ A_h,  ∀ l∈ L;



In the case of a free QFT derived as a QW theory, the following additional requirement has been demanded:


    [U_l , A_h] ≠ 0  ∀ h∈ S,l∈ L l(h)≠ h.

Condition (<ref>) is never satisfied in the scalar case, since both the representation {U_l}_l∈ L and the transition matrices are one-dimensional. However, as long as the Cayley graph structure is not derived by the requirement of homogeneity of the evolution—but rather assumed as in the present context—condition (<ref>) is dropped. In Subsec. <ref> we will prove a no-go result for isotropic scalar QWs without assuming condition (<ref>).
This shows that in the Euclidean case, no QW with a two-dimensional coin can be derived from an isotropic scalar QW, even using the weak Definition <ref> of isotropy.

In Ref. <cit.> it has been proven that, in the case of QWs on lattices (namely Cayley graphs of ℤ^d), isotropy entails that all the generators can be represented with the same length in ℝ^d. In particular, this implies that one has the following unitarity constraints:

    A_hA_-h^† = A_h^† A_-h = 0,  ∀ h∈ S.

Eq. (<ref>) implies that the transition matrices assume the following form <cit.>:

    A_± h = α_± h V_h |η_± h⟩⟨η_± h|,

where, for all h∈ S, α_± h>0, V_h is unitary, and {|η_h⟩, |η_-h⟩} is an orthonormal basis in the coin space for every h. Finally, in Ref. <cit.> it is shown that in the case of Abelian G one 
has ∑_h∈ S A_h =U for some unitary U commuting with the isotropy group representation { U_l }_l∈ L. The same happens for arbitrary group G, by a straightforward generalisation.  Therefore, for the purpose of classification one can first solve the unitarity and isotropy constraints by posing

    ∑_h∈ S A_h = I_s,

and then obtain the other solutions upon multiplying all the matrices A_h by an arbitrary unitary U in the commutant of { U_l }_l∈ L. We shall make use of Eqs. (<ref>), (<ref>), and (<ref>) in the proof of our main results in Secs. <ref> and <ref>.

We conclude this section recalling a necessary condition for the existence of a scalar (or coinless) QW on a given Cayley graph.

	Given a Cayley graph Γ(G,S_+), a necessary condition for the existence of a scalar QW
	
    A = ∑_h∈ S z_hT_h

	is that, for all the ordered pairs (h_1,h_2) ∈ S× S such that h_1 ≠ h_2, there exists at least a different pair (h_3,h_4) such that h_1h_2^-1=h_3h_4^-1. This is called quadrangularity condition.


Proposition <ref> holds for homogeneous coinless QWs, according to the definition of the present work and related literature (see e.g. <cit.>); yet, a similar result must hold, for any two connected nodes, also for inhomogeneous QWs. Elsewhere, the homogeneity requirement has been in general dropped (see e.g. Refs. <cit.> for the model of the so called Staggered QW with Hamiltonians, or SQWH). It is interesting to notice that—imposing homogeneity to the transition scalars in the 1D example of SQWH presented in Ref. <cit.>—by direct inspection of the first-neighborhood scheme one easily realizes that this QW is contained in the family of QWs on the infinite dihedral group found in <cit.>. Again, from the point of view of a decomposition in the form (<ref>), the “virtual” graph can be regarded as the integer lattice, while expressing the QW in the form (<ref>) (which is unique), one realizes that the actual graph is indeed a Cayley graph of the infinite dihedral group. Remarkably, it is possible that the present model is actually contained in the SQWH model. However, both constructions have been devised in order to overcome the issue of constructing coinless QWs. A no-go theorem proven in Ref. <cit.>, and generalizing a result by Meyer <cit.>, states that coinless QWs on Abelian graphs exhibit trivial dynamics. In the present work we show how to overcome this issue considering more general graphs, while keeping a homogeneous evolution rule. We point out that generally inhomogeneous models (like the Staggered QW one) find their relevance on the side of the experimental implementation, or also to mimic a curved space-time <cit.>.




 §.§ The continuum limit

Let G be isomorphic to ℤ^d, for an arbitrary integer d≥1. Let then Γ(G,S_+) be a Cayley graph of G. This case encompasses the usual lattices, including most of the cases treated in the literature where QWs are exploited to simulate wave equations or to devise algorithms. In particular, in this case the shift operators commutes. Accordingly, throughout the present subsection we will use Abelian notation, denoting the group composition law with the additive notation and the elements x̌∈ G as boldfaced d-dimensional real vectors. In particular, we will consider G as a space-vector.

Now, let the unitary operator

    A =  ∑_∈ S( ∑_y̌∈ Gy̌-y̌) ⊗ A_ =  ∑_∈ S T_⊗ A_

represent a QW on the Cayley graph Γ. The unitary irreducible representations of ℤ^d are one-dimensional. We now constructively show how to decompose the right-regular representation, which is unitary by definition, into the one-dimensional unitary irreducible representations of G. The latter are classified by the joint eigenvectors given by the relation

    T_y̌|⟩ = e^i·y̌|⟩,  y̌∈ G,

where

 is an element of the dual G^*. Taking the following expansion for the eigenvectors

    |⟩ = ∑_∈ G c(,) |⟩,

and substituting it into Eq. (<ref>), one obtains

    T_y̌|⟩   = ∑_∈ G c(,) |-y̌⟩= 
       = ∑_∈ G c(+y̌,) |⟩ = ∑_∈ G e^i·y̌c(,) |⟩.

Accordingly, the relation e^-i·y̌ c(+y̌,)=c(,) leads to e^i·c(0,)=c(,).
Substituting the latter into Eq. (<ref>) and imposing the normalization for the |⟩, we obtain:

    |⟩   = 1/(2π)^d/2∑_∈ G e^i·|⟩,
    |⟩   = 1/(2π)^d/2∫_B d  e^-i·|⟩,

where B is the first Brillouin zone, which we determine in the following. In general, the generators in S_+ are not linearly independent, then we define all the sets

    D_n{_n_1,…,_n_d}⊆ S_+,

collecting linearly independent elements, where n labels the specific subset. For every n, we can then define the dual set

    D̃_n{_n_1,…,_n_d},  _n_l·_n_m=δ_lm.

We now can expand each ∈ G and ∈ G^* as

    = ∑_j = 1^d x_n_j_n_j,   = ∑_j=1^d k_n_j_n_j,

for some n, where x_n_j∈ℕ for every j and ∈ B. 
Two eigenstates |⟩,|'⟩ are equivalent if there exists θ∈ [0,2π] such that

    |⟩ = e^iθ|'⟩.

Thus, from Eq. (<ref>), one can derive

    e^-i(-')· = e^iθ = e^-i(-')·y̌,  ∀,y̌∈ G,

which is equivalent to the condition

    ∃ľ∈ℕ^d : k_n_j - k'_n_j = 2π l_j,   j=1,…,d.

Since the choice of D_n,D̃_n is arbitrary, defining D̃:=⋃_nD̃_n, the Brillouin zone B⊆ℝ^d is the polytope defined as:

    B=⋂_∈D̃{∈ℝ^d|-π||^2≤·≤π||^2}.

The evolution operator A can be thus diagonalized as follows:

    A=∫_Bd ⊗ A_,

where the the matrix

    A_∑_∈ Se^i·A_

must be unitary for every . Being A_
polynomial in e^i·, imposing unitarity straightforwardly amounts to find the same general set of constraints of Eqs. (<ref>).

Clearly, in general A_∈𝕌(s) and its eigenvalues are of the form	e^iω_l(), for some integer 1≤ l ≤ s. The functions in the set

    {ω_1(),… , ω_s() },   ∈ B

are called the dispersion relations of the QW. As one can realize from the unitarity constraints in Eqs. (<ref>), the operator A is defined up to a global phase factor, and then in particular one can always choose A_∈𝕊𝕌(s) without loss of generality. This fact, in the case s=2, implies that the dispersion relation of a QW with a two-dimensional coin system is of the form ±ω(). In particular, this are interpretable as the particle and antiparticle branches of the dispersion relation.


The Fourier representation allows one to define differential equations for the evolution of the eigenstates, and also study the continuum limit. Let us introduce the interpolating Hamiltonian H_I() defined by the relation:

    exp(-iH_I())  A_ .

H_I() generates a discrete-time unitary evolution interpolating through a continuous time t as

    exp(-iH_I()t)|ψ(,0)⟩ = |ψ(,t)⟩.

Then we can write a Schrödinger-like differential equation

    i∂_t |ψ(,t)⟩ = H_I()|ψ(,t)⟩

and expand to the first order in , obtaining

    i∂_t |ψ(,t)⟩ =   [ H_I(0̌)+ .∇_' H_I(')|_'=0̌·] |ψ(,t)⟩ + 
       + O(||^2) |ψ(,t)⟩ .

Now, identifying  with the momentum of the system, one can interpret Eq. (<ref>) as a wave equation in the wave vector representation. Let us consider narrowband states |ψ(,t)⟩, where small wave vectors || ≪ 1 correspond to small momenta for the system. Then, identifying the lattice step with an elementary invariant length (e.g. a hypothetical Planck scale), the limit of small momenta is equivalent to the relativistic limit for the QW's evolution.

In the case s=2, let |u^±()⟩ be the positive and negative frequency eigenstates of H_I(), namely such that: H_I()|u^±()⟩ = ±ω() |u^±()⟩.
Then a so-called (anti)particle state is defined as

    |ψ^±(t)⟩ = ∫_B d/(2π)^d g(,t) u^±()u^±().

Taking the normalized distribution g(,t) smoothly peaked around a given _0∈ B,  the evolution given by Eq. (<ref>) leads to a dispersive  Schrödinger dfferential equation for the QW:

    i∂_t g̃(x̌,t)=±[ v̌·∇ + 1/2Ď·∇∇] g̃(x̌,t),

where g̃(,t) is the Fourier transform of e^-i _0· + iω(_0)tg(,t). Eq. (<ref>) is a Fokker–Planck equation, with drift vector and diffusion matrix given respectively by

    v̌ = .∇_ω()|_=_0,  Ď = .∇_∇_ω()|_=_0.

This method is general for the case of Cayley graphs of ℤ^d, and in particular it has been exploited—e.g. in Ref. <cit.>—to study the Weyl and Dirac QWs dynamics.

In Subsec. <ref>, via a unitary coarse-graining technique, we will prove that the Euclidean QWs are strictly contained in the QWs on ℤ^d. Accordingly, one can apply the Fourier method and take the continuous limit for all Euclidean QWs, even in some particular non-Abelian cases, as showed in the following. This will allow us to reconstruct the Weyl and Dirac QWs from scalar QWs on non-Abelian groups.

To best of our knowledge, a technique allowing one to extend a similar Fourier method to the non-Euclidean case is still unknown. This would be relevant since it would allow one to study the continuum limit of QWs on graphs with a nonvanishing curvature, e.g. on Fuchsian groups (which admit an embedding in the Poincaré disk). On the other hand, so far in the literature curvature has been implemented on classical gauge fields encoded in the transition matrices (see e.g. Refs. <cit.>).




 §.§ Embedding Cayley graphs into smooth manifolds

In this section we review some results from Geometric Group Theory <cit.> connecting algebraic properties of groups to geometric ones. The starting point is recognizing that endowing Cayley graphs with the notion of a distance allows us to study them as metric spaces.

Let G = S_+|R be a finitely generated group. The word length is the norm defined, for all g∈ G, as

    l_S(g) min{ n∈ | g=h_1⋯ h_n, h_i∈ S } .

The norm l_S induces the word metric, defined as

    d_G^(S) (g,g')  l_S(g^-1g')  ∀ g,g'∈ G.


We are interested in Cayley graphs suitably embeddable in a Euclidean space ℝ^d, with a notion of embedding resorting to the following concept of quasi-isometry <cit.>.

Let (G,d_G) and (M,d_M) be two metric spaces. A quasi-isometry is a function ℰ:G→ M satisfying, for some fixed a≥ 1 and b,c ≥ 0, and ∀ g,g'∈ G, the two following conditions:

    1/ad_G(g,g')-b ≤ d_M(ℰ(g),ℰ(g')) ≤ ad_G(g,g')+b, 
       ∀ m∈ M ∃ g∈ G  d_M(m,ℰ(g)) ≤ c.


The previous definition intuitively states that the two metrics are equivalent modulo fixed bounds. Quasi-isometry is an equivalence relation <cit.> and two metric spaces G,M are called quasi-isometric if there exists a quasi-isometry between them.


Let P be a group property. A group G is called virtually P if there exists H ≤ G satisfying P and such that the cardinality of the coset space |G/H| (called the index of H in G) is finite.


In the following  the property of a group of  “being isomorphic to G” will be denoted by the same symbol G.  For example “the group K is virtually ℤ” means 
that there exists a subgroup H of K isomorphic to ℤ with finite index in K.
The next definition further refines the notion of virtually P group and shall be useful to the characterization of the groups whose Cayley graphs are quasi-isometric to ℝ^d.


Let N and Q be two group properties. A group G is called Q-by-N if there exists N ⊴ G satisfying N and such that the quotient group G/N satisfies Q. 

We now provide some useful results to the purpose of establishing a quasi-isometric equivalence between ℝ^d and virtually ℤ^d groups.


Every finitely generated Abelian group is isomorphic to a direct product of finitely many cyclic groups.




Let G be a group containing a proper subgroup H of finite index l. Then the normal core of H in G, namely N_H ⋂_g∈ GgHg^-1, is a normal subgroup and of finite index l' in G, where l' is a multiple of l and a divisor of l!.




Let G be a group and P a group property inherited by subgroups of finite index. Then G is finite-by-P if and only if it is virtually P.

(⇒) It follows by definition.

(⇐) Let H be of finite index in G and satisfying P. Let us define

    N_H ⋂_g∈ GgHg^-1,

namely the normal core of H in G. Clearly, N_H ⊴ H. Furthermore, by a result due to Poincarè <cit.>, |G/N_H| < +∞ holds, and then also |H/N_H| < +∞ holds. By hypothesis, N_H satisfies P, and then the thesis follows.



A group is finite-by-ℤ^d if and only if it is virtually ℤ^d.

We have to check that the property of “being isomorphic to ℤ^d” is inherited by subgroups of finite index. By the Fundamental theorem of finitely generated Abelian groups (Theorem <ref>), every subgroup M of N ≅ℤ^d must be isomorphic to ℤ^d' with d' ≤ d, thus | N / M | = +∞ unless d=d'.


It is easy to see that further properties inherited by subgroups of finite index are: cyclicity, Abelianity, freeness.



Two groups G,G' are called virtually isomorphic if there exists a group Q such that both G and G' are virtually Q-by-finite.



Let G,G' two virtually isomorphic finitely generated groups: then they are quasi-isometric. <cit.>


Let G be a virtually G' group, then both G and G' are virtually G'-by-finite: in particular, they are virtually isomorphic.


A group G is said quasi-isometrically rigid if every group G' being quasi-isometric to G is also virtually isomorphic to G.




If a finitely generated group G is quasi-isometric to ℤ^d, then it has a finite index subgroup isomorphic to ℤ^d.


Let G be a finitely generated group. Then G is quasi-isometric to ℝ^d if and only if G is finite-by-ℤ^d.


This straightforwardly follows from the fact that quasi-isometry is an equivalence relation and ℝ^d is quasi-isometric to ℤ^d.


We shall restrict our investigation to groups quasi-isometric to ^d. Since quasi-isometry is an equivalence relation and ℤ^d is quasi-isometric to ℝ^d, Theorem <ref> implies that if a finitely generated group G is quasi-isometric to ℝ^d, then G is virtually ℤ^d. In Corollary <ref> we have proved that virtually ℤ^d is equivalent to finite-by-ℤ^d, whence restricting to groups quasi-isometric to ℝ^d is equivalent to restricting to finite-by-ℤ^d groups.

In the light of Corollary <ref>, our aim is to provide structure results for finite-by-ℤ^d groups, along with their presentations, in order to derive admissible (Euclidean) scalar QWs on them. The problem of characterizing the class of groups G with fixed N ⊴ G and quotient Q=G/N is called group extension problem: G is indeed said an extension of Q by N. In Subsec. <ref> the extension problem will be discussed, while in Subsec. <ref> we shall specialize the analysis to the case N≅ℤ^d and |Q|<∞. Our aim is to provide necessary and sufficient conditions in order to explicitly construct every possible extension of Q by N.





§ THE GROUP EXTENSION PROBLEM





 §.§ Constructing group extensions

Let N,Q be two arbitrary groups, and G be a Q-by-N group. The cardinality |Q| is called order of the group Q, and it is precisely the index of N in G. The group G can be then partitioned as follows

    G = { Nc_q_1,Nc_q_2,… , Nc_q_|Q|},

where the c_q_i are called the coset representatives. The identity of Q will be denoted by ẽ. One has c_ẽ c_q_1∈ N and c_q_i∉N for all i≠ 1.  The elements q ∈ Q are in a one-to-one correspondence with the cosets representatives c_q, which, by normality of N, follow the same composition rule of the elements q up to multiplication by elements of N. One has:

    c_q_1c_q_2c_q_1q_2^-1∈ N,  ∀ q_1,q_2 ∈ Q .


By definition, every element g∈ G can be written as g=nc_q, with n∈ N and c_q the representative of the coset corresponding to q∈ Q. Then the group multiplication can be obtained as follows

    n_1c_q_1n_2c_q_2   = n_1c_q_1n_2c^-1_q_1c_q_1c_q_2
       
    n_1φ_q_1(n_2)f(q_1,q_2)c_q_1q_2,

where

    φ_q(n) c_qnc_q^-1,   f(q_1,q_2) c_q_1c_q_2c_q_1q_2^-1,

and clearly φ_q∈Aut(N). Therefore, a piece of information we need in order to identify the extension G is the assignment of a composition rule for the coset representatives: this observation motivates the following definition.


	
Let G be an extension of Q by N and { c_q}_q∈ Q a set of representatives of the cosets of N in G. The function f : Q× Q → N defined as

    f(q_1,q_2)  c_q_1c_q_2c_q_1q_2^-1,  ∀ q_1,q_2 ∈ Q

is called a 2-cocycle.








Moreover, from associativity, if a function f : Q× Q → N is a 2-cocycle then it satisfies the following two properties ∀ q,q_1,q_2,q_3∈ Q:

    f(q,ẽ)   =f(ẽ,q) = e, 
    
    f(q_1,q_2)f(q_1q_2,q_3)    = φ_q_1(f(q_2,q_3))f(q_1,q_2q_3).

We will prove in Lemma <ref> that the two above properties are also sufficient for f to be a 2-cocycle.

From relation (<ref>) one has

    φ_q_1∘φ_q_2∘φ_q_1q_2^-1∈Inn(N).





Defining

    ϕ_m(·):=m· m^-1,  ∀ m∈ N,

one indeed obtains

    φ_q_1∘φ_q_2( ·)    = (c_q_1c_q_2) · (c_q_1c_q_2)^-1 = 
       = ϕ_f(q_1,q_2)∘φ_q_1q_2(·),  ∀ q_1,q_2∈ Q.

Accordingly, the family {φ_q }_q ∈ Q can be identified, in general, as a family of automorphisms which are in correspondence with elements of the outer automorphism group of N[We remind to the reader that an outer automorphism is an automorphism which is not inner, namely it does not have a realization as the conjugation by some element of the group. However, the group Out(N) Aut(N)/Inn(N) is called the outer automorphism group, despite the fact that, in general, it does not collect the outer automorphisms of N, since it is not generally a subgroup of Aut(N).]. Since Inn(N) ⊴Aut(N) and Out(N) Aut(N)/Inn(N), Eq. (<ref>) induces a homomorphism φ̃ which associates an element of Out(N) to each q ∈ Q. We define:





    φ Q    ⟶Aut(N) 
    
    q    ⟼φ_q(·) = c_q· c_q^-1,

and

    πAut(N)    ⟶Out(N) 
    ν∘ξ_ω   ⟼ω,


such that ν∈Inn(N), ξ_ω∈Aut(N) are some coset representative of the cosets of Inn(N) in Aut(N), and the composition φ̃:=π∘φ is a group homomorphism.


Therefore, in order to identify a group extension G of Q by N (i.e. in order to give the complete composition rule for the elements of G) one needs to choose a family of automorphisms of N and a 2-cocycle, i.e. a pair (φ,f) such that f satisfies Definition <ref> and φ is defined as in (<ref>) and satisfies Eq. (<ref>). We call such a pair (φ,f) data for the extension G of Q by N. We are now ready to classify the group extensions in the following Lemma.

	Let Q and N be two groups, and φ,f two maps such that φ:Q→Aut(N), and f : Q× Q → N. Then, there exists an extension G of Q by N with data (φ,f) if and only if the following relations are satisfied ∀ q_1,q_2,q_3∈ Q:
	
    φ_q_1∘φ_q_2   = ϕ_f(q_1,q_2)∘φ_q_1q_2	,
    
    
    	f(q_1,q_2)f(q_1q_2,q_3)    = φ_q_1(f(q_2,q_3))f(q_1,q_2q_3).



==========================COMMENTATA
 Given two groups N and Q, there exists an extension G of Q by N if and only if there exists a map φ:Q→Aut(N) such that Eq. (<ref>) holds, with f satisfying the following two relations ∀ q,q_1,q_2,q_3∈ Q:

    f(q,ẽ)   =f(ẽ,q) = e, 
    
    f(q_1,q_2)f(q_1q_2,q_3)    = φ_q_1(f(q_2,q_3))f(q_1,q_2q_3).



(⇒) Let G be an extension of Q by N with data (φ,f). Property (<ref>) has been already shown to hold. It is easy to check property (<ref>) for a 2-cocycle by imposing the associativity for the product of coset representatives, namely by the following computation. On the one hand, one has

    (c_q_1c_q_2)c_q_3   = f(q_1,q_2)c_q_1q_2c_q_3 =
       = f(q_1,q_2)f(q_1q_2,q_3) c_q_1q_2q_3

On the other hand, also

    c_q_1(c_q_2c_q_3)   = c_q_1f(q_2,q_3)c_q_2q_3=
       =φ_q_1(f(q_2,q_3))f(q_1,q_2q_3)c_q_1q_2q_3

holds, proving the first implication.

(⇐) We now explicitly construct the extension G of Q by N having (φ,f) as data.

Let G' be the set of ordered pairs N × Q, and denote its generic element by g = (n,q). Let us also equip G' with the following composition rule:

    (n_1,q_1)(n_2,q_2):=(n_1φ_q_1(n_2)f(q_1,q_2),q_1q_2).

Moreover, let the inverse of g∈ G' be given by

    (n,q)^-1 (φ_q^-1(n^-1f(q,ẽ)^-1)f(q^-1,q)^-1,q^-1),

and the identity element of G' by e (f(ẽ,ẽ)^-1,ẽ). 
We now show that G' is isomorphic to an extension of Q by N with data (φ,f). 
First, we need to show that G' is actually a group. Associativity of the composition can be proved using the properties (<ref>) and (<ref>). Now, we can prove that e∈ G' actually behaves as an the identity as follows.
By property (<ref>) we have

    φ_ẽ = ϕ_f(ẽ,ẽ).

Moreover, by choosing q_1=q_2=ẽ, and using Eq. (<ref>), relation (<ref>) reads

    f(ẽ,ẽ) = f(ẽ,q),  ∀ q∈ Q.

Relation (<ref>) with the choice q_2=q_3=ẽ reads

    φ_q(f(ẽ,ẽ)) = f(q,ẽ),  ∀ q∈ Q.

Using Eqs. (<ref>), (<ref>) and (<ref>), it is now easy to check that e(n,q)=(n,q)e=(n,q). Eqs. (<ref>) and (<ref>) with the choice q_1=q_3,q_2=q_1^-1 read:

    φ_q = ϕ_f(q,q^-1)∘φ_ẽ∘φ_q^-1^-1,
       φ_q(f(q^-1,q)^-1)f(q,q^-1) = f(q,ẽ)f(ẽ,q)^-1.

To prove that the inverse of (n,q) is well defined by relation (<ref>), one has to use (<ref>) and (<ref>) for the right-multiplication, and relations (<ref>) and (<ref>) for the left-multiplication. We can now show that the group G' is Q-by-N. Let us define r_n (nf(ẽ,ẽ)^-1,ẽ). The subset N'{ r_n .|. n∈ N } forms a subgroup of G', thus r_mr_nr_m^-1∈ N'. Let now define c_q (e_N,q). One has:

    c_qr_nc_q^-1= (φ_q(n)f(ẽ,ẽ)^-1,ẽ) ≡ r_φ_q(n),

where we used Eqs. (<ref>), (<ref>) and (<ref>). Thus, since the general element (n,q)∈ G' can be expressed as r_nc_q, Eq. (<ref>) shows that the subgroup N' is normal in G'. Moreover, we have that

    c_q_1c_q_2 = (f(q_1,q_2)f(ẽ,ẽ)^-1,ẽ)c_q_1q_2≡ r_f(q_1,q_2)c_q_1q_2.



















Moreover, one verifies that N' is indeed isomorphic to N:

    r_n_1r_n_2   = (n_1f(ẽ,ẽ)^-1,ẽ)(n_2f(ẽ,ẽ)^-1,ẽ) =
       = (n_1n_2f(ẽ,ẽ)^-1,ẽ) = r_n_1n_2.

On the other hand, the quotient G'/N' is clearly isomorphic to Q. We have then proven that G' is Q-by-N. Finally, we can now define an isomorphism ζ:G'→ G by setting ζ(r_n)=n and ζ(c_q)=c_q, where N is now a normal subgroup of G with quotient G/N≅ Q. Thus, G is an extension of Q by N. Moreover, since relation (<ref>) holds, and by Eqs. (<ref>) and (<ref>) one has 

    ζ(c_qr_n c_q^-1)=c_q n c_q^-1=ζ(r_φ_q(n))=φ_q(n),
       ζ(c_q_1c_q_2) =c_q_1c_q_2=ζ(r_f(q_1,q_2)c_q_1q_2)=f(q_1,q_2)c_q_1q_2,

then the group G has data (φ, f).










































































(⇒) The existence of  φ and f satisfying condition (<ref>) has been already shown. As to condition (<ref>), 
since one can choose c_ẽ=e, the proof is straightforward. Finally, it is easy to check property (<ref>) for a 2-cocycle by imposing the associativity for the product of coset representatives, namely by the following computation 

    f(q_1,q_2)f(q_1q_2,q_3) c_q_1q_2q_3=
    f(q_1,q_2)c_q_1q_2c_q_3=
    =     (c_q_1c_q_2)c_q_3
    =     c_q_1(c_q_2c_q_3) 
    =    c_q_1f(q_2,q_3)c_q_2q_3
    
    =    φ_q_1(f(q_2,q_3))f(q_1,q_2q_3)c_q_1q_2q_3.


(⇐) Denote by g:=(n,q)∈ G the ordered pairs of N × Q, equipped with the composition rule

    (n_1,q_1)(n_2,q_2):=(n_1φ_q_1(n_2)f(q_1,q_2),q_1q_2),

where f satisfies properties (<ref>) and (<ref>), and the map φ satisfies relation (<ref>). We want to show that G is an extension of Q by N. From the above product and using the properties of φ and f, one can verify that G is a group with e=(e_N,ẽ) and inverse given by

    (n,q)^-1=(φ_q^-1(n^-1f(q,q^-1)^-1),q^-1).


============================
One can also check that the pairs (n,ẽ) form a normal subgroup isomorphic to N. For consistency we finally need to check that 

    φ_q(n)=c_q nc_q^-1∈ G.

Indeed, upon denoting c_q=(n_q,q) and using Eq. (<ref>), Eq. (<ref>) reads

    (φ_q(n),ẽ)=(n_q,q)(n,ẽ)(φ_q^-1(n_q^-1f(q,q^-1)^-1),q^-1),

obtaining

    (φ_q(n),ẽ)=(n_qφ_q(n)n_q^-1,ẽ).

Then one can just choose n_q∈ Z(N) ∀ q∈ Q to obtain the desired extension corresponding to fixed φ and f.





Lemma <ref> extends the result proven in Ref. <cit.> for the case where N is Abelian. By Lemma <ref>, in order to construct and classify the extensions of Q by N one has to choose: (i) a map φ defined as in (<ref>), and (ii) a map f : Q× Q → N, such that properties (<ref>) and (<ref>) are satisfied. In particular, in the case where N is Abelian, by Eq. (<ref>) one has that the map φ:Q→Aut(N) is a group homomorphism, since in this case Inn(N) is trivial.

Yet, in general two extensions with different choices of data (φ,f) may still be isomorphic. We shall now prove a sufficient conditions implying that two extensions having different data are indeed isomorphic.

Let G,G' be two extensions of Q by N and of of Q' by N', respectively. G and G' are called pseudo-congruent extensions if there exist: (i) an isomorphism ψ : G '→ G, (ii) two isomorphisms α : N' → N and β: Q' → Q, and (iii) a family { n_q.|. q∈ Q' ,n_q∈ N' }, such that

    ψ(n)=α(n),  ψ(c'_q)=α(n_q)c_β(q),  ∀ n ∈ N',∀ q∈ Q'.




Let N,N',Q,Q' be groups such that N≅ N',Q≅ Q', and G' an extension of Q' by N' with data (φ',f'). Then, there exists an extension G of Q by N with data (φ,f) and pseudo-congruent to G', if and only if there exist two isomorphisms α : N' → N and β: Q' → Q, and a family { n_q.|. q∈ Q' ,n_q∈ N' }, such that

    φ_β(q_1) = ϕ_α(n_q_1^-1)∘α∘φ'_q_1∘α^-1,
    
       f(β(q_1),β(q_2))=
       =φ_β(q_1)∘α(n_q_2^-1)α(n_q_1^-1f'(q_1,q_2)n_q_1q_2),  ∀ q_1,q_2∈ Q.


(⇒) Let N,N',Q,Q' be groups such that N≅ N' and Q≅ Q'. Let then G',G be two extensions of Q' by N' and of Q by N with data (φ',f') and (φ,f), respectively. By hypothesis, there exists an isomorphism ψ : G' → G, two isomorphisms α : N' → N and β: Q' → Q, and a family { n_q.|. q∈ Q',n_q∈ N' }, satisfying the following:

    ψ(n)=α(n),  ψ(c'_q)=α(n_q)c_β(q),  ∀ n ∈ N',∀ q∈ Q'.

For all n∈ N' and q_1,q_2∈ Q', one has c_q_1'nc_q_2' = φ'_q_1(n)f'(q_1,q_2)c_q_1q_2'. Then, letting ψ act on both sides of the latter relation, it follows, ∀ n∈ N', ∀ q∈ Q', that

    α(n_q_1)c_β(q_1)α(nn_q_2)c_β(q_2) = 
       = α(n_q_1)φ_β(q_1)∘α (nn_q_2)f(β(q_1),β(q_2))c_β(q_1q_2) = 
       =α∘φ'_q_1 (n )α (f'(q_1,q_2)n_q_1q_2)c_β(q_1q_2).

Choosing n=e in Eq. (<ref>), one obtains:

    f(β(q_1),β(q_2))=
       =φ_β(q_1)∘α(n_q_2^-1)α(n_q_1^-1)α(f'(q_1,q_2)n_q_1q_2).

Using condition (<ref>), Eq. (<ref>) finally gives relation (<ref>).

(⇐) By hypothesis, G' is an extension of Q' by N' with data (φ',f'). Moreover, there exist two groups N,Q, a map φ Q →Aut(N), two isomorphisms α : N' → N and β: Q' → Q, and a family { n_q.|. q∈ Q ,n_q∈ N }, satisfying Eqs. (<ref>), (<ref>). Then, using relations (<ref>) and  (<ref>) for the data (φ',f'), we have

    ϕ_f'(q_1,q_2)∘φ'_q_1q_2=
    φ'_q_1∘φ'_q_2=
       =ϕ_n_q_1∘α^-1∘φ_β(q_1)∘α∘ϕ_n_q_2∘α^-1∘φ_β(q_2)∘α=
       =
    α^-1∘ϕ_α(n_q_1)∘φ_β(q_1)∘ϕ_α(n_q_2)∘φ_β(q_2)∘α=
       =
    α^-1∘ϕ_α(n_q_1)φ_β(q_1)∘α(n_q_2)∘φ_β(q_1)∘φ_β(q_2)∘α,
       ∀ q_1,q_2∈ Q

that reads:

    φ_β(q_1)∘φ_β(q_2)=
    
       = ϕ_φ_β(q_1)∘α(n_q_2^-1)α(n_q_1^-1)∘α∘ϕ_f'(q_1,q_2)∘φ'_q_1q_2∘α^-1 =
    
       = ϕ_φ_β(q_1)∘α(n_q_2^-1)α(n_q_1^-1)α(f'(q_1,q_2))∘α∘φ'_q_1q_2∘α^-1 =
       =
    ϕ_φ_β(q_1)∘α(n_q_2^-1)α(n_q_1^-1f'(q_1,q_2)n_q_1q_2)∘φ_β(q_1q_2)=
       =
    ϕ_f(β(q_1),β(q_2))∘φ_β(q_1q_2),  ∀ q_1,q_2∈ Q.








Therefore, by Eq. (<ref>), the maps φ,f satisfy property (<ref>). Moreover, expressing f' in terms of φ',f by Eqs. (<ref>),(<ref>) and writing property (<ref>), it is straightforward to verify, using Eq. (<ref>), that property (<ref>) also holds for φ,f. Thus, Lemma (<ref>) guarantees the existence of an extension G of Q by N with data (φ,f). Let ψ : G' → G be map defined by: ψ(nc_q')=α(n)α(n_q)c_β(q) ∀ n ∈ N',∀ q∈ Q'. On the one hand, one has:

    ψ( n_1c'_q_1n_2c'_q_2)=
       = 
    ψ( n_1φ_q_1(n_2)f'(q_1,q_2)c'_q_1q_2) =
       = α(n_1)α∘φ'_q_1(n_2)α(f'(q_1,q_2)n_q_1q_2)c_β(q_1q_2).

On the other hand, also

    ψ( n_1c'_q_1)ψ( n_2c'_q_2) = α(n_1n_q_1)c_β(q_1)α(n_2n_q_2)c_β(q_2) =
       = α(n_1n_q_1)φ_β(q_1)∘α(n_2n_q_2)f(β(q_1),β(q_2))c_β(q_1q_2)

holds. Using relation (<ref>) and Eq. (<ref>), one finally concludes that ψ( n_1c'_q_1n_2c'_q_2)=ψ( n_1c'_q_1)ψ( n_2c'_q_2) ∀ n_1,n_2∈ N', q_1,q_2∈ Q'. Consequently, ψ is an isomorphism and then the two extensions G' and G are pseudo-congruent.













































































One can always choose

    c_ẽ=f(ẽ,ẽ)=f(ẽ,q)=f(q,ẽ)=e,  ∀ q∈ Q

up to pseudo-congruence.

We have already proven that f'(ẽ,ẽ)=f'(ẽ,q) ∀ q∈ Q (see Eq. (<ref>)). Then, by choosing α,β to be the identical maps, n_ẽ=f'(ẽ,ẽ), q_1=ẽ, q_2=q, and using Eq. (<ref>), relation (<ref>) reads: f(ẽ,ẽ)=f(ẽ,q)=e ∀ q∈ Q. Moreover, by Eq. (<ref>), one has e=φ_q(f(ẽ,ẽ)) = f(q,ẽ) ∀ q∈ Q.
Lemma <ref> and Lemma <ref>, along with Corollary <ref>, imply the following result.

Let N and Q be two groups, and π the projection map in (<ref>).
The following procedure allows one to explicitly construct all the extensions of Q by N up to pseudo-congruence:


  * Classify all the homomorphisms φ̃:Q→Out(N) up to the equivalence relation defined as follows:

    φ̃^(1)∼φ̃^(2)⇔
         ∃ α∈Aut(N), β∈Aut(Q),  φ:Q→Aut(N) 
       φ̃^(1)_q = π∘α^-1∘φ_β(q)∘α,  φ̃^(2)_q = π∘φ_q,  ∀ q∈ Q.

For each chosen homomorphism φ̃^* (modulo the equivalence defined above), choose a map φ^* such that φ̃^*=π∘φ^*. 

  * Classify all the maps f:Q× Q→ N satisfying properties (<ref>) and (<ref>) with φ=φ^*, and (<ref>) up to the following equivalence relation:

    f^(1)∼ f^(2) ⇔ ∃{ n_q.|. q∈ Q ,n_q∈ N },
         ∃ α∈Aut(N), β∈Aut(Q), ϑ:Q→Aut(N) 
       f^(1)(β(q_1),β(q_2))=
       =ϑ_β(q_1)∘α(n_q_2^-1)α(n_q_1^-1f^(2)(q_1,q_2)n_q_1q_2), ∀ q_1,q_2∈ Q.

Choose a map f^* (modulo the equivalence defined above). 

Each pair of maps φ^*,f^* obtained in this way provides, up to pseudo-congruence, a different extension G of Q by N, whose data are (φ^*,f^*).

Although a general criterion allowing to classify and construct extensions up to an arbitrary isomorphism is not known, the structure of the particular groups N,Q under study can possibly help to recognize whether or not two extensions are isomorphic, while being not pseudo-congruent. Such a structure can also help to explicitly construct the equivalence classes defined in relations (<ref>), (<ref>) of Proposition <ref>, and we give an example of this in the next subsection.



 §.§ Finite-by-ℤ^d extensions

Our aim is to study the Euclidean scalar QWs, namely walks on Cayley graphs quasi-isometric to ℝ^d. By Corollary <ref>, this can be accomplished without loss of generality constructing the extensions of some finite group Q by N≅ℤ^d. Notice that, in the case where the group N is Abelian, then one has Inn(N)={id}, namely Aut(N) ≅Out(N). Consequently, being the projection map π trivial, we shall set φ̃≡φ.

The group of automorphisms of ℤ^d is isomorphic to 𝔾𝕃(d,ℤ).

By relation (<ref>) in Proposition <ref> combined with Theorem <ref>, for each fixed finite group Q, one can consider the equivalence classes of maps φ:Q→𝔾𝕃(d,ℤ) up to pre-composition with  arbitrary β∈Aut(Q) and to conjugation by arbitrary α∈𝔾𝕃(d,ℤ).








	Every element q of a finite group Q has a finite order r_q.





Lemma <ref>, using property (<ref>) along with the fact that Inn(N) is trivial, implies that

    ∀ q ∈ Q ∃ r_q∈ℕ φ_q^r_q (n) = n,  ∀ n∈ N.
 
Such an automorphism φ_q is called r_q-involutory. Since φ is a group homomorphism, we need the conjugacy classes of finite subgroups of 𝔾𝕃(d,ℤ), whose elements will be r_q-involutory matrices. This fact will also help in finding the equivalence classes defined in Eq. (<ref>) in Proposition <ref>.








In the following, we shall focus our attention in particular on the extensions by ℤ^d with index |Q| = 2, since it allows to reconstruct QWs with a two-dimensional coin. In this case, by Corollary <ref>, the problem reduces to choose the only nontrivial value of the 2-cocycle f, namely f(q̃,q̃) = c_q̃^2  c^2, which by property (<ref>) is invariant under the automorphism φ_q̃. Accordingly, one can calculate the invariant space of φ_q̃ and then use Eq. (<ref>) to find all the inequivalent 2-cocycles. We notice that Eq. (<ref>) and Corollary <ref> imply n_ẽ=e. Furthermore, for Q ≅ℤ_2, Aut(Q)={id}. Therefore in this case, for a chosen c^2, by Eq. (<ref>) one looks for solutions n,c'^2∈ N≅ℤ^d to the following equation:

    c^2 = n + φ_q̃(n) + c'^2

(where we used the Abelian additive notation). We will neglect the trivial homomorphism φ (from Q ≅ℤ_2 to I_d), since it gives rise to Abelian extensions, implying a trivial scalar QW dynamics <cit.>. The explicit construction of all the extensions for the cases d=1,2,3 and Q≅ℤ_2 will be performed in Sec. <ref>, along with two extensions with Q≅ℤ_2×ℤ_2.



 §.§ Coarse-graining of QWs on Cayley graphs



Let G be a finitely generated group and N a subgroup of G. One can define a unitary mapping between ℋ=ℓ^2(G) and 𝒦=ℓ^2(N)⊗ℓ^2(G/N) in the following way:

    U_N ℋ    ⟶ 𝒦,
    |nc_q⟩    ⟼ nq,


We notice that N has not to be necessarily normal in G. For all n∈ N, h∈ G and q∈ G/N, there exist n'∈ N and q'∈ G/N such that nc_q h^-1 = n'c_q'(h,q). In particular, n'=n (c_q'(h,q)hc_q^-1)^-1, and c_q'(h,q)hc_q^-1∈ N for all q∈ G/N. One can then provide a representation for G in terms of the right-regular representation of N:

    T̃_h     = U_N T_h U_N^† =
    
    ∑_q∈ G/N T_c_q'(h,q)hc_q^-1⊗|q'(h,q)⟩⟨q|.



The abovementioned change of representation has been used in Ref. <cit.> to define the so-called coarse-graining of QWs. Suppose to have a finitely generated group G with a finite-index subgroup N. In the following lemma, we prove that a QW on the Cayley graph Γ(G,S_+) with a s-dimensional coin can be represented as a QW on the Cayley graph of N having the following set of generators 

    S_N{ c_q'(h,q)hc_q^-1}_h∈ S^q∈ G/N,

and with an enlarged coin of dimension s· |G/N|.

Let G be a group, S a set of generators for G and N a subgroup of G. Let the coset representatives of N in G be denoted by { c_q}_q∈ G/N with c_q_1∈ N. Then 
S_N is a set of generators for N.


Let S̃_N be a set of generators for N≤ G. For all h̃∈S̃_N, by hypothesis there exist h_1,h_2,… ,h_n∈ S such that

    h̃ = h_1h_2⋯ h_n.

Using elements in the set S_N, we can now recursively construct all the elements of the form:

    c_q'(h_1,q'(q'(...))h̃c_q_1^-1
       
    c_q'(h_1,q'(q'(...))h_1⋯  h_n-1c_q'(h_n,1)^-1 c_q'(h_n,1)h_nc_q_1^-1,

which are in N by construction (since c_q'(h,q)hc_q^-1∈ N for all h∈ G and q∈ G/N). Then it must be c_q'(h_1,q'(q'(...))∈ N, meaning that q'(h_1,q'(q'(...)) = q_1. We thus constructed c_q_1h̃ c_q_1^-1 for all generators h̃ of N. Hence the thesis follows noticing that the set { c_q_1h̃c_q_1^-1∈ N .|. h̃∈S̃_N} generates the whole N.

In Lemma <ref> we have proven that the coarse-graining of QWs on Cayley graphs preserves the whole subgroup N≤ G, namely the coarse-grained walk is rigorously defined on a Cayley graph of N. Moreover, being a unitary mapping, this coarse-graining does not erase  information of the original walk: some degrees of freedom are just encoded in the new enlarged coin. This circumstance was verified for particular cases in Ref. <cit.>. Notice that the coarse-graining is well defined with no need to assume the normality of N in G.

Now suppose to fix a given presentation of N, i.e. to choose some generators g_l for N. Problem: does the generators of G reaching the given presentation of N with a change of representation depends on the choice of the coset representatives?

In the index-2 abelian case, the answer is no.
We pose h_i = n_ic_q(i) and the generic coset representative x_qc_q, for x_q ∈ N. Then one has to impose

    g_l(i) = x_1c_ẽh_i(x_q(i)c_q(i))^-1 =  x_1n_ix_q(i)^-1

(l injective), implying that every n_i is defined as x_1^-1g_l(i)x_q(i). In the index-2 Abelian case, n_i  x_1^-1x_q(i)g_l(i), therefore it is defined up to a fixed overall translation which does not change the resulting graph.


Let now G be an extension of Q by N. For an arbitrary h = x_hc_q_h∈ G, expression (<ref>) reads

    T̃_h    = U_N T_h U_N^† = 
       = ∑_q_1,q_2∈ Q∑_n,n'∈ N|n⟩⟨n'|⊗|q_1⟩⟨q_2|δ_nc_q_1,n'c_q_2c_q_h^-1x_h^-1.

Accordingly, one obtains 

    q_2 = q_1q_h,   n= n'c_q_1q_hc_q_h^-1c_q_1^-1φ_q_1(x_h^-1),

and the following holds:

    T̃_h =
    
    ∑_q'∈ Q T_φ_q'(x_h) T_f(q',q_h)⊗|q'⟩⟨q'| T_q_h.

One can thus give the following representation of the scalar QW evolution operator (<ref>) on Γ(G,S_+) in terms of the right-regular representations of N and Q:

    Ã = ∑_h∈ S∑_q'∈ Q  T_φ_q'(x_h) T_f(q',q_h)⊗ z_h|q'⟩⟨q'| T_q_h,

where z_h∈ and h = x_hc_q_h∈ G. Finally, the transition matrices corresponding to the coarse-grained generators h̃∈ S_N are given by (see Ref. <cit.>):

    (A_h̃)_ij = ∑_h∈ Sδ_h̃,c_q_i hc_q_j^-1δ_q_i,q_jq_h^-1 z_h.

Notice that each transition scalar is associated to one and only one coarse-grained matrix element. Finally, via the above construction we have proven the following.

Let P be a group property. The set of QWs on Cayley graphs of virtually P groups is contained in the set of QWs on Cayley graphs of groups satisfying the property P.


The Euclidean QWs are contained in the set of QWs on ℤ^d. The Euclidean coinless QWs are contained in the set of QWs on ℤ^d with a s-dimensional coin, for s≥ 2.


On the one hand, this change of representation is relevant in order to characterize scalar QWs on an extension G manifestly in terms of N (and Q) and its elements (allowing to study a Cayley sub-graph of N of the Cayley graph of G); on the other hand, it allows to investigate the isotropy group L (which results when representing the walk on ℓ^2(N)⊗ℓ^2(Q)) in terms of the action of the quotient Q on the normal subgroup N.






§ EUCLIDEAN SCALAR QUANTUM WALKS


In the following, when we consider the elements of N≅ℤ^d as vectors embedded in ℝ^d, we use the boldfaced notation, indicating by ň the vector corresponding to the element n∈ N≅ℤ^d. Depending on the context and without loss of clarity, in the index-2 case where Q = {ẽ, q̃}≅ℤ_2, we  adopt the identification φ_q̃≡φ.





 §.§ Isotropic scalar QWs

In the present subsection, we treat the isotropic case. We start by proving some useful results.


Let N≅ℤ^d be an index-2 subgroup of a non-Abelian group G={ N,Nc}. Then N is characteristic in G, namely N is invariant under the action of every automorphism l∈Aut(G). In particular, N⊴ G.


By contradiction, suppose that

    ∃ l∈Aut(G),∃ n∈ N  l(n)=n'c.

Accordingly,

    l(n^2) = n'φ(n')c^2∈ Z(G)

but n∉Z(G), since every automorphism l maps Z(G) to itself and l(n)=n'c∉Z(G). On the other hand, for all r∈ℕ^+ and g∈ N, one has that

    g^r∈ Z(G) ⟹ φ(g)^rg^-r=e,

implying g∈ Z(G), since N is free Abelian. However, by Eq. (<ref>), it must be n^2∈ Z(G) and then also n∈ Z(G), which is absurd. Then N is characteristic in G.

Using Proposition <ref> we can now construct the automorphism group of a ℤ_2-by-ℤ^d group.

Let G be a ℤ_2-by-ℤ^d group. Then Aut(G) ≅ℤ^d ⋊𝔾𝕃(d,ℤ).


Let us pose G={ N,Nc } and N≅ℤ^d. By Proposition <ref>, any automorphism of G acts separately on the two cosets. Let L_N,L_c be the proper subgroups of Aut(G) such that, for all l_N∈ L_N,l_c∈ L_c, n∈ N, then

    l_N(n)    ∈ N,   l_N(c) = c 
    
    l_c(n)    = n,   l_c(c)   = n_c c,   n_c∈ N.

Then, for all l∈Aut(G) and for all n∈ N, one can define the two automorphisms l_N∈ L_N,l_c∈ L_c by

    l_N(n)   l(n),   l_c(c)  l(c),

so that l  =l_N∘ l_c.
Furthermore, L_c∩ L_N = { e } clearly holds. Moreover, for all l_N∈ L_N,l_c∈ L_c, n∈ N, the following hold:

    ł_N∘ł_c∘ l_N^-1(n)     = n, 
    ł_N∘ł_c∘ l_N^-1(nc)    = nl_N(l_c(c)) = nl_N(n_c)c  l_c'(nc),

where l_c'∈ L_c. This means that L_c⊴Aut(G). We conclude that Aut(G)≅ L_c⋊ L_N. Finally, L_N≅Aut(N)≅𝔾𝕃(d,ℤ) (by Theorem <ref>), while L_c≅ℤ^d: it is easy to verify that L_c is free Abelian and the cardinality of a minimal set of generators is d (the elements of L_c are the d-dimensional translations).

In Ref. <cit.> it is proven that the isotropy group L (Definition <ref>) of a QW must be indeed a finite subgroup of Aut(G). Moreover, a technique for constructing Cayley graphs starting from L is presented. For an isotropic QW, the generating set coincides with the orbit of an element h under the isotropy group L, denoted by 𝒪_L(h). Our aim is now to characterize the isotropic presentations of ℤ_2-by-ℤ^d groups G, in order to investigate  the admissible isotropic scalar QWs on them.

By Proposition <ref>, we know that the isotropy groups of a ℤ_2-by-ℤ^d group are isomorphic to the finite subgroups of L_N≅𝔾𝕃(d,ℤ), since L_c≅ℤ^d has no nontrivial finite subgroups. The finite groups L≤𝔾𝕃(d,ℤ) are reported in Ref. <cit.>. In particular, as long as the (isotropic) Cayley graphs of ℤ^d are embedded in ℝ^d, the elements in the orbit 𝒪_L(h) can be represented having all the same length <cit.>. We shall use the above results to prove the following no-go result.


In dimensions d≥ 2, there exists no isotropic scalar QW on a ℤ_2-by-ℤ^d non-Abelian group G. In other words, for d≥ 2 no QW on ℤ^d with a two-dimensional coin can be derived from an isotropic scalar QW by coarse-graining. For d=1, there exists a family of QWs on the infinite dihedral group D_∞=ℤ⋊_φℤ_2, with φ(n)=-n, containing the 1D Weyl and Dirac QWs.


Let us suppose that S = { (g_lc)^± 1.|. 2≤ l < ∞} is a set of generators for the non-Abelian group G={ N,Nc }, with N≅ℤ^d and d∈ℕ^+. Take g_l_1,g_l_2 such that the length-2 path g_l_1c (g_l_2c)^-1 = g_l_1g_l_2^-1, for g_l_1c,g_l_2c∈ S, is of maximal length in N among all paths of the form g_lg_l'^-1. Following the argument of the proof of Proposition 1 in Ref. <cit.>, the pair (g_l_1,g_l_2) is unique in N. Accordingly, by the quadrangularity condition (Proposition <ref>), we have to include g_ic,g_jc∈ Nc in S such that

    g_l_1g_l_2^-1 = g_i g_j^-1

and with g_i = g_l_2^-1 and g_j = g_l_1^-1. This implies that g_l_1^± 1c∈ S. Imposing isotropy, and using Proposition <ref> and <ref> along with aforementioned characterization of the isotropic presentations of Ref. <cit.>, we see that all the g_l are all equal in length. Accordingly, g_l_1c(g_l_1^-1c)^-1 = g_l_1^2 has maximal length in N, and there cannot exist a different pair (g_i'c,g_j'c) such that g_i'c(g_j'c)^-1 = g_l_1^2. Then, by quadrangularity (see Proposition <ref>), the set of generators for the group G must have the form S = { g_n^± 1 , (g_mc)^± 1.|. n∈ I, m∈ J, |I|≥ 1,|J| ≥ 1 }, with ‖ǧ_n_1‖ = ‖ǧ_n_2‖ and ‖ǧ_m_1‖ = ‖ǧ_m_2‖ for all n_1,n_2∈ I and m_1,m_2∈ J. Moreover, by isotropy, the g_mc cannot have infinite order, implying that they must have order 2. Take now, for n_1∈ I, g_n_1(g_n_1^-1)^-1 = g_n_1^2: there must exist two different g_m_1c,g_m_2c∈ S such that g_m_1g_m_2^-1 = g_n_1^2. Then |J|≥ 2. Now, by the same above argument of the maximal length, there exists g_m'∈ N such that g_m'^± 1c∈ S. This implies that g_m'∈ S and finally, by isotropy, also


    S ={𝒪_L(g_m'^± 1), 𝒪_L(g_m'^± 1)c } .

Therefore one has:

    e = (g_m'^± 1c)^2 = g_m'^± 1φ (g_m'^± 1)c^2=(g_m'φ (g_m'))^± 1c^2,

implying c^2 = e and φ (g_m”) = g_m”^-1 for all g_m”∈𝒪_L(g_m'). By Eq. (<ref>), {𝒪_L(g_m'^± 1), 𝒪_L(φ (g_m')^± 1) } is a set of generators for N, and then G must be then isomorphic to ℤ^d ⋊_φℤ_2, with φ(n)=-n. By isotropy, denote now by z_± and z_c the transition scalars associated to the elements in 𝒪_L(g_m'^± 1) and in {𝒪_L(g_m')c,𝒪_L(g_m'^-1)c}, respectively. Computing the transition matrices of the coarse-grained QW on Γ (N,S_N) using Eq. (<ref>), these are equal to

    A_± h = [ z_± z_c; z_c z_∓ ]  ∀± h∈ S_N.





For d≥ 2, it is easy to see that |𝒪_L(g_m')|≥ 2. Accordingly, in this case, in Eq. (<ref>) one has at least one term with h,h'∈ S_N and h≠± h'. Let us take the path h-h' with maximal length, which is unique: this fact,

using Eq. (<ref>) with Eq. (<ref>), implies the condition

    |z_+|^2 + |z_c|^2 + |z_-|^2 + |z_c|^2 = 0,

which is clearly impossible to satisfy. This proves the impossibility for all dimensions d≥ 2. In the case d=1, namely N≅ℤ, the only possible extension is isomorphic to D_∞ = ℤ⋊_φℤ_2. The most general family of scalar QWs on D_∞ has been studied in Ref. <cit.>. Imposing isotropy to these QWs, one straightforwardly finds that the resulting QWs contain the Weyl and Dirac QWs in one dimension.

We conclude this investigation on the isotropic scalar QWs with the following theorem, which can be of aid in the attempt of generalizing the construction performed above.

Let G be a finitely generated group. Then every finite index subgroup H in G contains a subgroup N which is finite
index and characteristic in G.


	Accordingly, a finite-by-ℤ^d group has, in general, the following structure:

    G = { N,Nc_2,… , Nc_i },

with the subgroup N≅ℤ^d characteristic and of finite index i in G. This, in particular, means that classifying finite-by-ℤ^d groups up to pseudo-congruence (see Proposition <ref>) is equivalent to classifying virtually Abelian groups up to general isomorphisms. Moreover, Proposition <ref> can be easily generalized to groups G finite-by-ℤ^d: in this case, Aut(G) ≅ L_Q ⋊𝔾𝕃(d,ℤ), where L_Q is the group acting on the coset representative as a pseudo-congruence. This fact, albeit not leading to a straightforward generalization of Proposition <ref>, can help to construct the Euclidean isotropic scalar QWs with index greater than 2.





 §.§ Spinorial walks from scalar QWs

In Subsec. <ref>, we imposed isotropy to those scalar QWs which reconstruct the QWs with a two-dimensional coin on lattices, finding that they exist in dimension d=1 only. In the present subsection we address the problem to provide necessary and suffient conditions in order to reconstruct a class of known spinorial QWs. In particular, we aim to derive, without imposing isotropy, QWs with a two-dimensional coin on the simple square lattice and on the BCC lattice. In fact, as already well understood in the Abelian case, unitarity alone in general does not allow to perform a tight a priori selection on the admissible Cayley graphs. For this reason, in the following we restrict to the case of coarse-grained presentations exhibiting generators all with the same length in ℝ^d (a necessary, but still not sufficient, condition for isotropy, as already pointed out). However, the one-dimensional case has been broadly studied in Ref. <cit.>. Accordingly, as already mentioned, the cases which will be studied in generality shall be the simple square lattice and the BCC lattice.

Suppose that, for d∈ℕ^+ and N≅ℤ^d, a QW on Γ (N,S_+), with a two-dimensional coin and having generators which can be embedded in ℝ^d having all the same length, is the coarse-graining of a scalar QW on Γ (G,S_+'), with G a ℤ_2-by-N non-Abelian group. Then G≅ℤ^d⋊ℤ_2. 


Let us fix a set of generators g_i∈ S_N for N≅ℤ^d, with ‖ǧ_i_1‖ =‖ǧ_i_2‖ for all i_1,i_2. Denoting again G={ N,Nc } and using Eq. (<ref>), one can easily see that the following statements hold:

    h_i ∈ S_G∩ N ⇒ h_i ,φ(h_i)∈ S_N, 
       h_i= g_ic ∈ S_G∩ Nc ⇒ g_i,φ(g_i)+c^2 ∈ S_N.

We can then follow the same argument in the first part of the proof of Proposition <ref>, since the same hypotheses hold. Therefore, we have that ∃ g_i'∈ N  g_i'^± 1c,g_i'∈ S_G, and then also

    (g_i'^± 1c)^-1 = φ (g_i'^± 1)c^-2c ∈ S_G.

Then from Eq. (<ref>), φ (g_i'^± 1)c^-2∈ S_N. Using also Eq. (<ref>), we obtain ‖φ (ǧ_̌ǐ'̌) - č^̌2̌‖ = ‖ -φ (ǧ_̌ǐ'̌) - č^̌2̌‖ = ‖φ (ǧ_̌ǐ'̌) ‖, implying č^̌2̌ = 0 (i.e. c^2 = e). Then G is a semidirect product.

We will consider two lattices for Γ (N,S_+): the simple square and the BCC. The simple square lattice is generated by

    ȟ_̌1̌ = [ 1; 0 ], ȟ_̌2̌ = [ 0; 1 ],

while the BCC lattice is generated by

    ȟ_̌1̌ = [ 1; 1; 1 ], ȟ_̌2̌ = [ -1; -1;  1 ], ȟ_̌3̌= [ -1;  1; -1 ], ȟ_̌4̌= [  1; -1; -1 ].

Following the same arguments of the proofs of Proposition <ref> and Lemma <ref> (in particular, using Eqs. (<ref>) and (<ref>)), by direct inspection it is easy to see that the only set of generators for G satisfying the quadrangularity condition (see Proposition <ref>) is of the form: 
    S' = { g, gc }_g∈ S,

S being the set of generators corresponding to the simple square or the BCC lattices.














Our strategy is the following. On  one hand, in Appendix <ref> we derive the most general QWs with a two-dimensional coin on the simple square and BCC lattices. These are shown in Eqs. (<ref>) and (<ref>). On the other hand, in Subsecs. <ref> and <ref> we construct the admissible groups (according to Lemma <ref>) supporting the scalar QWs whose coarse-graining is a spinorial one on the two chosen lattices. Clearly, their coarse-graining is contained in the spinorial QWs derived there.

Let 𝒲_1(Γ) be the family of the scalar QWs on a given Cayley graph Γ(G,S_+) of a group G, and 𝒲_p(Γ_p) the family of QWs on the Cayley graph Γ_i(H,S̃_+) of a subgroup H≤ G of index i, given by a fixed regular tiling of Γ with respect to H. The QWs on Γ_p have coin system of dimension p. Let us now identify the QWs up to local unitary transformations (i.e. on the coin system) and changes of representation (coarse-grainings). These operations are all unitary, namely represents just changes of basis and the identification is well-posed. Since for all W∈𝒲_1(Γ) there exists a unique W'∈𝒲_p(Γ_p) such that W' is a coarse-graining of W up to a local change of basis, then clearly 𝒲_1(Γ) ⊆𝒲_p(Γ_p) holds. Moreover, if for all W∈𝒲_p(Γ_p) there exists a unique “refinement” mapping W to an element W'∈𝒲_1(Γ), then also 𝒲_p(Γ_p) ⊆𝒲_1(Γ) holds. Thus, provided that one checks that up to a local change of basis the transition matrices for every walk in 𝒲_p(Γ_p) can be written in the form of those of the coarse-graining of a walk in 𝒲_1(Γ), then also 𝒲_1(Γ)=𝒲_p(Γ_p) holds.































We will derive the form of the coarse-grained QWs and impose that form to the spinorial QWs (<ref>) and (<ref>) modulo unitary equivalence. This will allow us to find the most general family of scalar QWs on the extensions of ℤ_2 by ℤ^d (d=2,3), whose coarse-grainings are QWs with a two-dimensional coin on the simple square and BCC lattices.








§ RELATIVISTIC WAVE EQUATIONS FROM COINLESS QWS





 §.§ One-dimensional case

For completeness, we here briefly treat the one-dimensional case, namely N≅ℤ. The only nontrivial finite subgroup of Aut(N)≅𝔾𝕃(1,ℤ) is isomorphic to ℤ_2 itself. Accordingly, the only non-Abelian index-2 extension by ℤ is isomorphic to the infinite dihedral group D_∞. The most general family of admissible scalar QWs on D_∞ has been studied in Ref. <cit.>. This contains the one-dimensional Weyl and Dirac QWs.

We here outline a generalization of these results for higher indices.

Let G be a finite group and G'≤ G. Then |G'| divides |G|.
This means that if we choose |Q| to be odd, then the order r_q of each element of q∈ Q will be odd. If we look for a nontrivial homomorphism φ Q →{ 1,-1 }, with |Q| odd, then for some q we will have

    1 = φ_q^r_q = (-1)^r_q = -1,

which is impossible. As a consequence, all the extensions of some group Q of odd order by ℤ must satisfy

    φ_q =1,  ∀ q∈ Q.

[ℤ_3-by-ℤ groups]
Let us pose Q = {ẽ, q̃, q̃^2 }≅ℤ_3. Chosen a 2-cocycle f, one has

    f(q̃,q̃)c_q̃^2   = c_q̃^2 =  (c_q̃)c_q̃^2(c_q̃)^-1 = 
       = φ_q̃( f(q̃,q̃) ) c_q̃c_q̃^2c_q̃^-1 = f(q̃,q̃) c_q̃c_q̃^2c_q̃^-1,

where we used Eq. (<ref>). This implies

    c_q̃^2c_q̃ = c_q̃c_q̃^2.

However, by Eq. (<ref>), one also has 

    c_q̃n=nc_q̃,  ∀ n ∈ N,∀q̃∈ Q,

whence it follows that an extension G of ℤ_3 by ℤ must be Abelian. Namely, G is isomorphic to either ℤ or ℤ×ℤ_3 (by the Fundamental theorem of finitely generated Abelian groups, see Theorem <ref>).





 §.§ Two-dimensional case

In Ref. <cit.> one can find a complete classification of the finite subgroups of 𝔾𝕃(2,ℤ) up to conjugation. The subgroups of order 2 are three, clearly isomorphic to ℤ_2 = {ẽ,q̃}. These are, respectively, generated by:

    -I_2, σ_x =
    [ 0 1; 1 0 ], σ_z =
    [  1  0;  0 -1 ].

The simple square lattice is generated by the canonical basis for ℝ^2, i.e. the set of vectors (<ref>). Regardless of the homomorphism φ  chosen, one has that c_q̃^2∈ N≅ℤ^2 will be invariant under φ_q̃. For each automorphism, then, one has to fix the only nontrivial 2-cocycle value f(q̃,q̃) = c_q̃^2 among the invariant vectors of the chosen automorphism. In the following, we provide an application of the group-extension technique developed in Sec. <ref>. We construct all the index-2 non-Abelian extensions of N≅ℤ^2 below.


  * Case φ_q̃ = -I_2. The only invariant element is the zero vector. Then the only possibility is J_1 ≅ℤ^2 ⋊_-I_2ℤ_2.

  * Case φ_q̃ = σ_x. The invariant space in ℤ^2 is r_x (ȟ_̌1̌+ȟ_̌2̌), with r_x∈ℤ. Let us choose r_x=0: using Eq. (<ref>), we have

    (I_2 + σ_x)(n_q̃,0ȟ_̌1̌ + n_q̃,1ȟ_̌2̌)+r'_x (ȟ_̌1̌+ȟ_̌2̌)    = 
     
     (n_q̃,0 + n_q̃,1 + r'_x)(ȟ_̌1̌+ȟ_̌2̌) = 0,

namely ∀ r'_x ∃ n_q̃,0,n_q̃,1∈ℤ such that the extension with c'_q̃^2 = r'_x (ȟ_̌1̌+ȟ_̌2̌) differs from that with c_q̃^2 = 0 for a change of coset representative. Then the only possibility is again J_2 ≅ℤ^2 ⋊_σ_xℤ_2.

  * Case φ_q̃ = σ_z. The invariant space is r_z ȟ_̌1̌, with r_z∈ℤ. Choosing r_z=0, again from Eq. (<ref>) we have

    (I_2 + σ_z)(n_q̃,0ȟ_̌1̌ + n_q̃,1ȟ_̌2̌)+r'_z ȟ_̌1̌ = 
     = (2n_q̃,0 + r'_z)ȟ_̌1̌ = 0,

namely, ∀ r'_z even, ∃ n_q̃,0,n_q̃,1∈ℤ such that the extension with c'_q̃^2 = r'_z ȟ_̌1̌ differs from that with c_q̃^2 = 0 for a change of coset representative. Then J_3 ≅ℤ^2 ⋊_σ_zℤ_2. Choosing r_z=1, one has

    (2n_q̃,0 + r'_z)ȟ_̌1̌ = ȟ_̌1̌

and ∀ r'_z odd ∃ n_q̃,0,n_q̃,1∈ℤ such that the extension with c'_q̃^2 = r'_z ȟ_̌1̌ differs from that with c_q̃^2 =ȟ_1 for a change of coset representative. In this last case, the extension J_4 is not a semidirect product.

We list some possible presentations of all the non-Abelian extensions of ℤ_2 by ℤ^2:

    J_1    =  h_1,h_2,c .|. h_1h_2h_1^-1h_2^-1, c^2, ch_1c^-1h_1, ch_2c^-1h_2 , 
    
    J_2    =  h_1,h_2,c .|. h_1h_2h_1^-1h_2^-1, c^2, ch_1c^-1h_2^-1, ch_2c^-1h_1^-1, 
    
    J_3    =  h_1,h_2,c .|. h_1h_2h_1^-1h_2^-1, c^2, ch_1c^-1h_1^-1, ch_2c^-1h_2 , 
    
    J_4    =  h_2,c .|. c^2h_2c^-2h_2^-1, ch_2c^-1h_2 .

We now construct the admitted scalar QWs on the derived extensions. Lemma <ref> excludes J_4, since it is not a semidirect product. The admissible presentations are of the form (<ref>), S ={ h_1,-h_1,h_2,-h_2} being the set of generator associated to the simple square lattice. We write the coarse-grained transition matrices, derived using Eq. (<ref>), for the three cases:

	
  * Case of J_1, for x∈{h_1,h_2}:
	
    A_+x=
    	[     z_x    z_xc; z_x^-1c  z_x^-1 ], 
    	A_-x=
    		[  z_x^-1 z_x^-1c;    z_xc     z_x ].

	
  * Case of J_2, for x,y∈{h_1,h_2} : x≠ y:
		
    A_+x=
    	[  z_x z_xc; z_yc  z_y ], 
    	A_-x=
    	[  z_x^-1 z_x^-1c; z_y^-1c  z_y^-1 ].

	
  * Case of J_3:
	
    A_± h_1=
    	[  z_h_1^± 1 z_h_1^± 1c; z_h_1^± 1c  z_h_1^± 1 ], 
    	A_± h_2=
    	[  z_h_2^± 1 z_h_2^± 1c; z_h_2^∓ 1c  z_h_2^∓ 1 ].


One can check the  conditions under which the above coarse-grained matrices are unitarily equivalent to those of (<ref>).

	
  * Every QW obtained as the two-dimensional Weyl QW <cit.>, multiplied on the left by an arbitrary unitary commuting with σ_y can be viewed as a coarse-graining of  a scalar QW on the Cayley graph corresponding to presentation  J_1. 
	
  * Every isotropic 2D QW with a two-dimensional coin <cit.> can be viewed as a coarse-graining of a scalar QW on the Cayley graph corresponding to presentation  J_2.
	
  * No QW with a two-dimensional coin the simple square lattice can be viewed as  a coarse-graining of a scalar  QW on the Cayley graph corresponding to presentation J_3.

Both families of coinless QWs on J_1 and on J_2 stricly contain the Weyl QW in two-space dimensions <cit.>. The presentations corresponding to the QWs on the Cayley graphs of J_2 and its coarse-graining, along with, respectively, the associated transition scalar and matrices, are reported in Fig. <ref>.






 §.§ Three-dimensional case

In Ref. <cit.> one can find a complete classification of the finite subgroups of 𝔾𝕃(3,ℤ) up to conjugation. One can exploit the same methods provided in the two-dimensional case (Subsec. <ref>) in order to construct all the extension of ℤ_2 by ℤ^3. 

The subgroups of order 2 are five, clearly isomorphic to ℤ_2, and are respectively generated by:

    -I_3, Σ_±±[  1  0  0;  0 -1  0;  0  0 -1 ], Λ_±±[ -1  0  0;  0  0  1;  0  1  0 ].

Lemma <ref> excludes the extensions which are not semidirect products. Accordingly, all the admissible non-Abelian extensions of ℤ_2 by ℤ^3 are derived as follows:


  * K_1 ≅ℤ^3 ⋊_-I_3ℤ_2,

  * K_2 ≅ℤ^3 ⋊_Σ_+ℤ_2,

  * K_3 ≅ℤ^3 ⋊_Σ_-ℤ_2,

  * K_4 ≅ℤ^3 ⋊_Λ_+ℤ_2,

  * K_5 ≅ℤ^3 ⋊_Λ_-ℤ_2.

The BCC lattice is generated by the set of vectors (<ref>). The presentation of the groups K_i admitting a scalar QW is given by (<ref>), with S collecting the generators (<ref>) and the element c realizing the automorphisms (<ref>) by conjugation. Adopting the same arguments used in Subsec. <ref>, one finds that K_4 and K_5 do not support a scalar QW whose coarse-graining is a QW with a two-dimensional coin on the BCC lattice. On the other hand, K_1, K_2 and K_3 admit scalar QWs, which can be found directly checking unitary equivalence. In particular, the transition matrices in the case of K_2 are:

    A_± h_1=
    	[  z_h_1^± 1 z_h_1^± 1c; z_h_4^± 1c  z_h_4^± 1 ], 
    	A_± h_2=
    	[  z_h_2^± 1 z_h_2^± 1c; z_h_3^± 1c  z_h_3^± 1 ], 
    
    			A_± h_3=
    	[  z_h_3^± 1 z_h_3^± 1c; z_h_2^± 1c  z_h_2^± 1 ], 
    	A_± h_4=
    	[  z_h_4^± 1 z_h_4^± 1c; z_h_1^± 1c  z_h_1^± 1 ].

Accordingly, there exists a unitary W such that WA_± h_1W^† = A_± h_4 and WA_± h_2W^† = A_± h_3, and the family of scalar QWs on K_2 strictly contains the Weyl QW in three space-dimensions <cit.>.







 §.§ The 2D and 3D Dirac QWs from coinless walks

For one space-dimension, we already saw in Proposition <ref> that the 1D Weyl and Dirac QWs are the coarse-graining of isotropic scalar walks on D_∞ (see the analysis carried out in Ref. <cit.>).

We conclude the present work constructing two extensions of ℤ_2×ℤ_2 by ℤ^d for d=2,3. This is needed to implement the coinless Dirac QWs <cit.>. Clearly, the coin dimension of the coarse-grained QWs must be of dimension 4, and this is the reason why we take an index-4 extension by ℤ^d.

Let G_d be an extension of Q≅ D_2 = ℤ_2×ℤ_2 by N^d≅ℤ^d, with

    G_d = { N,Nc_1,Nc_2,Nc_1c_2 }

and

    c_1^2 = c_2^2 = e,   c_1c_2=c_2c_1.

Accordingly, G_d ≅ℤ^d⋊_φ D_2. The associated automorphisms realizing the semidirect product are denoted by φ_1, φ_2 and φ_12 = φ_1 ∘φ_2 = φ_2 ∘φ_1.

We choose the following presentation for G_d:

    S'_d = { h, hc_1, c_2 .|. h∈ S_d  },

where S_d is the set of generators corresponding to the simple square lattice for d=2, and to the BCC lattice for d=3 (see Eqs. (<ref>) and (<ref>)). Let {φ_1,φ_2 } be represented in dimension d=2 by

    {σ_z, -σ_z },  σ_z = [  1  0;  0 -1 ],

while in dimension d=3 by

    {Σ_+, Σ_+' },  Σ_+ = [    1    0;    0 -I_2 ],  Σ_+' = [ -I_2    0;    0    1 ].

It is immediate to check that the associated Cayley graphs satisfy the quadrangularity condition (Proposition <ref>). Accordingly, via Eq. (<ref>), the coarse-grained transition matrices are given by:

    A^D_h    = 
    [ nA_h    0;    0 nB_h ],   A^D_e = 
    [        0 z_c_2I_d; z_c_2I_d        0 ], 
     A_h    = 
    1/n[         z_h      z_hc_1; z_φ_1(h)c_1    z_φ_1(h) ],
     B_h    =
    1/n[     z_φ_2(h)  z_φ_2(h)c_1; z_φ_12(h)c_1    z_φ_12(h) ],

where n∈ (0,1] and A_e^D is associated to the identity element (i.e. the mass term). Since the form of the matrices (<ref>) is the same of those of the Dirac QWs <cit.>, we can  choose the A_h to be the transition matrices of Subsecs. <ref> and <ref> for the two- and three-dimensional Weyl scalar QWs, with B_h = A_h^† and z_c_2 = im, with m≥ 0 and n^2+m^2=1. We notice that one can perform a change of basis only on the diagonal blocks, attaining the desired form. These choices guarantee unitarity and select the d-dimensional Dirac scalar QWs for d=2,3.



§ DISCUSSION AND CONCLUSIONS

In this work we addressed the problem of providing a constructive procedure to obtain all the possible QWs on Cayley graphs quasi-isometric to Euclidean spaces—i.e. of virtually Abelian groups. The latter are exhausted by groups that are extensions of finite groups by free Abelian groups. The problem has then been tackled starting from a thorough characterization of all extensions of finite groups by arbitrary groups, providing (partial) criteria for checking isomorphism of a priori different extensions. The piece of theory thus constructed is then applied in the special case of interest, i.e. where the extension is by a free Abelian group.

We then constructed all the extensions of ℤ_2 by ℤ and ℤ^2. As to the case of ℤ_2 by ℤ^3, the analysis has been restricted to semidirect products, even though there exist also different extensions. However, extensions of the latter kind would lead to embeddings in ℝ^3 where the nearest neighbours of a given node need to have different distances from the node. We then neglected extensions that are not semidirect products, since the subsequent analysis focused on the simple square and the BCC, where all the nearest neighbours of a given node have the same distance from the node.

We then proved that there are no isotropic scalar QWs on (non-Abelian) extensions of ℤ_2 by free Abelian groups of dimension larger than 1. Our main results consist in providing criteria to find the families of QWs with s=2 on the simple square and BCC lattices that can be obtained by coarse-graining a QW on ℤ_2-by-ℤ^d with d=2,3. Among those, interestingly, there are the Weyl QWs in 2 and 3 dimensions. Finally, in a very special case of the extension (ℤ_2×ℤ_2)-by-ℤ^d with d=2,3, we show that the Dirac QWs in d=2,3 can be obtained by coarse-graining.

This line of research has a relevance within our approach to QFTs, where that all the non-trivial structures can be derived from very simple evolution algorithms. In particular, internal degrees of freedom like spin or chirality can be viewed as obtained by coarse-graining of QWs with trivial coin, i.e. originally describing the dynamics of particles with trivial internal structure. A big problem that remains open in this respect is the origin of symmetries like isotropy in this scenario. One of the possible developments might consist in studying how isotropy of coarse-grained QWs can follow from other requirements for the coinless underlying QWs, e.g. those considered in Ref. <cit.>. Along these lines, one can imagine a relaxation of isotropy where the symmetry involves only a family of subgraphs.

We characterized Euclidean QWs in d dimensions, proving that these are exhausted by the QWs on ℤ^d via a unitary coarse-graining procedure. One possible future line of research is the investigation of the properties of the Euclidean QWs which are not coarse-graining of any (scalar) QW, e.g. a subfamily of those derived in the Appendix of the present work. In particular, the dynamics and space-time symmetries of these can be in principle different from the ones exhibited by the Weyl and Dirac QWs. Moreover, one could ask whether or not there exist Euclidean scalar QWs on Cayley graphs of (non-Abelian) groups with no cyclic element (i.e. without torsion) under the hypothesis of coarse-grained generators having all the same length. Finally, the next step is a characterization and study of QWs on Cayley graphs which are not embeddable in Euclidean spaces, i.e. carrying a non-trivial curvature.





§ ACKNOWLEDGMENTS

The authors wish to thank Benson S. Farb, Cornelia Druţu, Roberto Frigerio, Romain Tessera, and Francesco Genovese for useful discussions and precious insights. The section presenting original results on group extension benefited from the material of Ref. <cit.>. This publication was made possible through the support of a grant from the John Templeton Foundation, ID # 60609 “Quantum Causal Structures”. The opinions expressed in this publication are those of the authors and do not necessarily reflect the views of the John Templeton Foundation.










§ DERIVATION OF THE QWS

In Appendices <ref> and <ref> we derive the most general families of QWs with a two-dimensional coin on the simple square and BCC lattices.



 §.§ Simple square lattice

The presentation of ℤ^2 corresponding to the simple square lattice is given by: h_1,h_2 | h_1h_2h_1^-1h_2^-1. The unitarity conditions (<ref>) are given by:

    A_+iA_-i^† = A_-i^†A_+i = 0, 
    
    A_+iA_∓ j^† + A_± jA_-i^† = 0, 
    
    A_-i^†A_± j + A_∓ j^†A_+i = 0 ,

for i,j∈{ h_1,h_2 } and i ≠ j. Let us introduce the polar decomposition for the transition matrices: ∀ A ∈𝔾𝕃(n,ℂ) there exists V unitary and P positive semidefinite such that A=VP. The first of Eqs. (<ref>) implies

    A_± i = α_± i V_i |± i⟩⟨± i|,

where {|-i⟩, |+i⟩} are orthonormal basis and α_± i >0 ∀ i and we posed V_+i = V_-i V_i: It is easy to verify it in view of the non-uniqueness of the polar decomposition when the matrix is not full-rank (we refer the reader to Ref. <cit.>).

The second and third of Eqs. (<ref>) imply

    A_+iA_± j^†A_+i = A_-iA_± j^†A_-i = 0,

reading

    ⟨+i|∓ j⟩⟨∓ j|V_j^†V_i|+i⟩ = ⟨-i|± j⟩⟨± j|V_j^†V_i|-i⟩ = 0 .

It's easy to see that at least one among ⟨∓ j|V_j^†V_i|+i⟩ and ⟨± j|V_j^†V_i|-i⟩ must be vanishing. The cases are just two:


  *  ⟨± j|V_j^†V_i|± i⟩ = 0 ⇒|± i⟩ = |± j⟩|0⟩,|1⟩,

  *  ⟨∓ j|V_j^†V_i|± i⟩ = 0 ⇒|± i⟩ = |∓ j⟩|0⟩,|1⟩

(up to a phase factor which is not relevant in defining the transition matrices). Then V_j^†V_i is anti-diagonal in the basis {|0⟩,|1⟩}, say V_1  W = V [ 0 μ; ν 0 ], where V  V_2. Using the second and third of Eqs. (<ref>) and Eqs. (<ref>) for g=e (i.e. the normalization condition), one gets in both cases μ = -ν^*, α_+1 = α_-1α and α_+2 = α_-2 = √(1-α^2). Substituting and changing basis to set ν = 1, one gets

    A_+1   = α V |1⟩⟨0|, A_-1 = -α V |0⟩⟨1|, 
     A_+2   = √(1-α^2) V |0⟩⟨0|, A_-2 = √(1-α^2) V |1⟩⟨1|,

for the first case, while the second case is recovered just swapping +2 ↔ -2.

Now, one can check that the unitarity conditions

    A_hA_e^† + A_eA_-h^† = 0, 
    
    A_e^† A_h + A_-h^† A_e = 0

cannot be satisfied for all h∈ S_+.

Finally, can impose the condition (<ref>), finding V = [ √(1-α^2)        α;       -α √(1-α^2) ]. Plugging this into the transition matrices (<ref>) one obtains:

    A_+1 = [       α^2         0; α√(1-α^2)         0 ], A_-1 = [          0 -α√(1-α^2);          0        α^2 ], 
     A_+2 = [      1-α^2          0; -α√(1-α^2)          0 ], A_-2 = [         0 α√(1-α^2);         0     1-α^2 ],

with α∈ (0,1), and up to a left-multiplication by an arbitrary unitary commuting with the symmetry group giving the invariance condition (<ref>).




 §.§ BCC lattice

The presentation of ℤ^3 corresponding to the BCC lattice is given by: h_1,h_2,h_3,h_4| h_ih_jh_i^-1h_j^-1, h_1h_2h_3h_4. There are three kinds of different paths of length 2 giving rise to the unitarity conditions:

    ± 2h_i, 
       ± h_i ∓ h_j, 
       ± (h_i+h_j),

for h_i,h_j ∈ S_+. Similarly to the two-dimensional case, from the first family of paths (<ref>) we obtain the following general expression for the transition matrices:

    A_± i = α_± i V_i |± i⟩⟨± i|,

with {|-i⟩,|+i⟩} an orthonormal basis and α_± i > 0 ∀ i. On the other hand, the condition associated to (<ref>) amounts to

    A_+iA_+j^† + A_-jA_-i^† = 0, 
    
    A_+i^†A_+j + A_-j^†A_-i = 0 .

Exploiting the form (<ref>) and using Eqs. (<ref>), we get:

    A_+iA_+j^†A_+i = 0 ⇒ A_+iA_+j^† = 0 ∨ A_+j^†A_+i = 0 .

Accordingly, one of the two following cases hold:

    A_± i = α_± i V_i |± i⟩⟨± i|,
    
    A_± j = α_± j V_j |∓ i⟩⟨∓ i|;
    
    A_± i^† = α_± i V_i^†V_i |± i⟩⟨± i|V_i^†,
    
    A_± j^† = α_± j V_j^† V_i|∓ i⟩⟨∓ i| V_i^†.

In case (<ref>), A_+jA_+i^† = A_+lA_+i^† = 0 implies A_+jA_+l^†≠ 0, while in case (<ref>) A_+i^†A_+j = A_+i^†A_+l = 0 implies A_+j^†A_+l≠ 0: since there are four elements in S_+, it is easy to see that, for a fixed +i, conditions in (<ref>) can be satisfied at most for two different values of +j. The possible couples are six, then either the first or the second condition must be satisfied for at least two couples with a fixed +i. Thus one has (modulo relabeling the h_l) three set of conditions:

    A_+1A_+2^† = A_+1A_+3^† = A_+2A_+4^†  = 0, 
    
    A_+2^†A_+3 = A_+1^†A_+4 = A_+3^†A_+4 = 0 ,

or

    A_+1A_+2^† = A_+1A_+3^† = A_+2A_+4^† = A_+3A_+4^†  = 0, 
    
    A_+2^†A_+3 = A_+1^†A_+4 = 0 ,

or the previous one modulo the exchange of A_+i and A_+i^†, i.e. equivalently modulo the PT transformation A_ǩ↦ A_ǩ^†. It is then sufficient to solve the first two sets of equations.

Imposing the conditions which are common to Eqs. (<ref>) and (<ref>), we obtain:

    A_+1   = α_+1V_1 M,    A_-1   = α_-1V_1 (1-M), 
    
    A_+2   = α_+2V_2 (1-M),    A_-2   = α_-2V_2 M, 
    
    A_+3   = α_+3V_3 (1-M),    A_-3   = α_-3V_3 M, 
    
    A_+4   = α_+4V_4 M,    A_-4   = α_-4V_4 (1-M),

where M |0⟩⟨0|, 1-M |1⟩⟨1| are arbitrary one-dimensional projectors, and V_1^†V_4,V_2^†V_3 have vanishing diagonal elements. This form of the solutions is equivalent to the set of constraints (<ref>). Imposing (<ref>) we find

    α_+1α_+4 V_1 M V_4^† + α_-1α_-4 V_4 (1-M) V_1^† = 0, 
    α_+2α_+3 V_2 (1-M) V_3^† + α_-2α_-3 V_3 M V_2^† = 0,

implying that

    α_+1α_+4 = α_-1α_-4, 
    α_+2α_+3 = α_-2α_-3, 
    
    V_1^†V_4, V_2^†V_3 ∈𝕊𝕌(2).

Also, we have

    α_+1α_+2 MV_1^†V_2 (1-M) + α_-1α_-2 MV_2^†V_1 (1-M)  = 0, 
    α_+1α_+3 MV_1^†V_3 (1-M) + α_-1α_-3 MV_3^†V_1 (1-M)  = 0, 
    α_+2α_+4 (1-M) V_2^†V_4 M + α_-2α_-4 (1-M)V_4^†V_2 M  = 0, 
    α_+3α_+4 (1-M) V_3^†V_4 M + α_-3α_-4 (1-M)V_4^†V_3 M  = 0,

implying (V_i^†V_j)_01 = - (V_i^†V_j)_10^* for the pairs (i,j) = (1,2),(1,3),(2,4),(3,4). Then we can pose

    V_i^†V_j    [          ρ_ije^iθ_ij   √(1-ρ_ij^2)e^iφ_ij; -√(1-ρ_ij^2)e^-iφ_ij        ρ_ije^-iθ'_ij ],
    ρ_14   = ρ_23 = 0.

Notice that, from Eqs. (<ref>), ρ_ij≠ 1 and this implies:

    θ_ij=θ'_ij, α_+iα_+j = α_-iα_-j, ∀ (h_i,h_j)∈ S_+× S_+.

Using the equality V_i^†V_l = V_i^†V_jV_j^†V_l, it is easy to show that

    ρ_12 = √(1-ρ_13^2) = √(1-ρ_24^2) = ρ_34,

and, recalling Eqs. (<ref>),(<ref>) and considering the determinants, one also realizes that

    V_i^† V_j ∈𝕊𝕌(2)  ∀(i,j)∈ S_+× S_+.

In paricular, this holds ∀ρ_ij∈ [0,1] and one has θ_ij = θ'_ij in Eq. (<ref>).

Accordingly, the only three possible cases are:

    ρ_12≠ 0,1;
    ρ_12 = 1;
    ρ_12 = 0.

From paths of the form (<ref>) the following conditions follow:

    α_+1α_-2V_1 M V_2^† + α_-1α_+2V_2 (1-M) V_1^† + 
     + α_-3α_+4V_3 M V_4^† + α_+3α_-4V_4 (1-M) V_3^† = 0,


    α_+1α_-2M V_1^† V_2 M + α_-1α_+2(1-M)V_2^† V_1(1-M) + 
     + α_-3α_+4M V_3^†V_4 M + α_+3α_-4 (1-M) V_4^†V_3 (1-M) = 0,


    α_-1α_+3V_3 (1-M) V_1^† + α_+1α_-3V_1 M V_3^† + 
     + α_+2α_-4V_4 (1-M) V_2^† + α_-2α_+4V_2 M V_4^† = 0,


    α_-1α_+3(1-M)V_3^† V_1 (1-M) + α_+1α_-3MV_1^† V_3M + 
     + α_+2α_-4 (1-M) V_4^† V_2 (1-M) + α_-2α_+4 M V_2^† V_4 M = 0,


    α_-1α_+4 MV_4^†V_1 (1-M) + α_+1α_-4 MV_1^† V_4 (1-M) + 
     + α_+2α_-3 MV_3^† V_2 (1-M) + α_-2α_+3 M V_2^† V_3 (1-M) = 0.

We shall use the previous equations in order to show that cases (<ref>) and (<ref>) lead to nontrivial solutions connected via a swap 2 ↔ 3, while case (<ref>) does not satisfy unitarity.

Case (<ref>). Recalling that in this case ρ_ij≠ 1 ∀ (i,j), then from Eqs. (<ref>), (<ref>) it is easy to derive that α_+i = α_-iα_i ∀ h_i∈ S_+. We can use this condition in Eq. (<ref>), along with ρ_12 = ρ_34, obtaining α_1α_2 = α_3α_4. Similarly, since ρ_13 = ρ_24, from Eq. (<ref>) also α_1α_3 = α_2α_4 follows. One thus straightforwardly has: α_1 = α_4 and α_2 = α_3. Then again from Eqs. (<ref>) and (<ref>) it follows that e^iθ_12 = -e^iθ_34,e^iθ_13 = -e^iθ_24. Finally, multiplying Eq. (<ref>) by V_1^† to the left and by V_2 to the right and using the two identities on the phases just found, the first matrix element reads:

    1-(1-ρ_12^2)-ρ_13^2 + e^i(θ_14-θ_23) = 0
       ⟹   2ρ_12^2 -1 = -e^i(θ_14-θ_23),

meaning that either ρ_12=1 or ρ_12=0, which is absurd.


Case (<ref>). Recalling Eq. (<ref>), from Eq. (<ref>) one obtains α_± 1α_∓ 2 = α_∓ 3α_± 4 and V_1^† V_2 = -V_3^† V_4, while from (<ref>) one gets

    α_± 1α_∓ 2   = α_± 3α_∓ 4,
    
    V_1^† V_4    = -V_2^† V_3.

Plugging the latter equation into Eq. (<ref>), one gets α_+1α_-4 + α_+2α_-3 = α_-1α_+4 + α_-2α_+3. The latter equation found, using conditions (<ref>), reads

    α_+1α_-4/α_+1α_-2 + α_+2α_-3/α_+4α_-3 = α_-1α_+4/α_-1α_+2 + α_-2α_+3/α_-4α_+3,

which in turn implies:

    α_+4α_-4 + α_+2α_-2/α_-2α_+4 = α_+4α_-4 + α_+2α_-2/α_+2α_-4,

namely α_-2α_+4 = α_+2α_-4. Combining this condition with those already found, we just end up with: α_+i = α_-iα_i and α_1α_2 = α_3α_4.

Posing now θθ_21, φφ_31,V V_1, we notice that V^† V_4 = -V_2^† V_3 = -V_2^† V V^† V_3 (where we used Eq. (<ref>)) and that it can be set e^iφ=1 via a change of basis. We finally find the transition matrices:

    A_+1   = α_1 V |0⟩⟨0|,     A_-1   = α_1 V |1⟩⟨1|, 
     A_+2   = α_2 e^iθV |1⟩⟨1|,    A_-2   = α_2e^-iθ V |0⟩⟨0|, 
    
    A_+3   = -α_3 V |0⟩⟨1|,    A_-3   = α_3 V |1⟩⟨0|, 
    
    A_+4   = -α_4 e^-iθV |1⟩⟨0|,    A_-4   = α_4e^iθ V |0⟩⟨1|,

along with the condition α_1α_2 = α_3α_4 and being V an arbitrary unitary.

Case (<ref>). Similarly to the previous derivation, from Eq. (<ref>) we get V_1^† V_3 = -V_2^† V_4, while from Eq. (<ref>) we have V_1^† V_4 = V_2^† V_3. Then, from the form of V_1^† V_3 and V_1^† V_4, the identity V_1^† V_2 = V_1^† V_3V_3^† V_2 = V_1^† V_3V_4^† V_1 = V_4^† V_1V_3^† V_1 holds. Moreover, using Eqs. (<ref>), (<ref>) and (<ref>), one likewise can derive the conditions α_+i = α_-iα_i and α_1α_3 = α_2α_4. At this point one easily realizes that this solution is connected to the previous one via a swap 2 ↔ 3.

We can now check that the unitarity conditions

    A_hA_e^† + A_eA_-h^† = 0, 
    
    A_e^† A_h + A_-h^† A_e = 0

cannot be satisfied for all h∈ S_+.

Finally, we can impose condition (<ref>), finding

    V = [   α_1+α_2e^iθ   α_3-α_4e^iθ; -α_3+α_4e^-iθ  α_1+α_2e^-iθ ][    β    γ; -γ^*  β^* ].

Plugging this into the transition matrices (<ref>), one obtains:

    A_+1   = α_1[    β    0; -γ^*    0 ], 
    A_-1 = α_1[   0   γ;   0 β^* ],
    
    A_+2   = α_2e^iθ[   0   γ;   0 β^* ], 
    A_-2 = α_2e^-iθ[    β    0; -γ^*    0 ],
    
    A_+3   = -α_3[    0    β;    0 -γ^* ], 
    A_-3 = α_3[   γ   0; β^*   0 ],
    
    A_+4   = -α_4e^-iθ[   γ   0; β^*   0 ], 
    A_-4 = α_4e^iθ[    0    β;    0 -γ^* ],

with α_i>0, α_1α_2 = α_3α_4, ∑_i=1^4α^2_i=1, β and γ defined as in Eq. (<ref>), and up to a left-multiplication by an arbitrary unitary commuting with the symmetry group giving the invariance condition (<ref>).






