{'fraction_non_alphanumeric': 0.030482903604773386, 'fraction_numerical': 0.005750324615099239, 'mean_word_length': 4.325650312808693, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Influence of coin symmetry on infinite hitting times in quantum walks

Classical random walks on finite graphs have an underrated property: a walk from any vertex can reach every other vertex in finite time, provided they are connected. Discrete-time quantum walks on finite connected graphs however, can have infinite hitting times. This phenomenon is related to graph symmetry, as previously characterized by the group of direction-preserving graph automorphisms that trivially affect the coin Hilbert space. If a graph is symmetric enough (in a particular sense) then the associated quantum walk unitary will contain eigenvectors that do not overlap a set of target vertices, for any coin flip operator. These eigenvectors span the Infinite Hitting Time (IHT) subspace. Quantum states in the IHT subspace never reach the target vertices, leading to infinite hitting times. However, this is not the whole story: the graph of the 3D cube does not satisfy this symmetry constraint, yet quantum walks on this graph with certain symmetric coins can exhibit infinite hitting times. We study the effect of coin symmetry by analyzing the group of coin-permutation symmetries (CPS): graph automorphisms that act nontrivially on the coin Hilbert space but leave the coin operator invariant. Unitaries using highly symmetric coins with large CPS groups, such as the permutation-invariant Grover coin, are associated with higher probabilities of never arriving, as a result of their larger IHT subspaces.


I. INTRODUCTION
A classical random walk can be described by the movement of a particle on a graph, where the vertices represent possible locations and the edges connect neighboring sites. At each step, the next edge is chosen randomly [1]. Quantum walks are the unitary analogues of these classical random walks [2,3]. Similar to the classical case, there are discrete-time [4,5] and continuous-time [6,7] versions of quantum walks. In this paper, we only consider discrete-time quantum walks.
The unitary operatorÛ corresponding to one time step in the discrete-time quantum walk can be decomposed into two parts:Û =Ŝ(1 v ⊗Ĉ). The Hilbert space of U is H = H v ⊗ H c , where H v and H c are the Hilbert spaces of the position (vertices) and of the internal degree of freedom (coin), respectively. The shift operatorŜ propagates quantum states between the vertices of the graph. It is analogous to the adjacency matrix of the graph, but since the shift depends on the state of the coin it operates on the complete Hilbert space H. It takes the formŜ where {|v } are vertex basis states, {|c } are coin basis states, and |c(v) is the neighboring vertex to v along the edge labeled by coin state c.
The coin operatorĈ acts on the coin Hilbert space H c . Discrete-time quantum walks use these operators to mix the particle's internal basis states at each vertex. A vertex with d edges (degree d) allows the particle to have as many coin basis states. In irregular graphs, the degree is different for different vertices, which causes the dimension of the coin Hilbert space to occupy a range of values, and hence it becomes difficult to choose one coin to act on all the vertices. However there are a couple of solutions one can employ. Self-loops can be used to effect regularity. Another solution is for the coin operator to depend on the vertex. HenceĈ can be structured differently for different applications. In this paper we will only consider regular graphs.
The notion of vertex hitting time is a concept borrowed from classical random walks. Classically it is defined as the average number of time steps taken for a walk to reach a "final" vertex, v f , given an initial distribution. The formula for the hitting time τ h (v f ) is where p(v f , t) is the probability that the walk has reached vertex v f at time t for the first time.
Classical random walks will always have finite hitting times for all vertices in finite connected graphs. However, interference effects may prevent this in quantum walks. This leads to the uniquely quantum mechanical phenomenon of an infinite hitting time.
To define a quantum notion of hitting time we must define what it means to arrive at a vertex for the first time. In our approach, we treat the final vertex as an absorbing wall. After every time step of the walk, a measurement is performed on the final vertex to check if the walk has reached it or not. If it has, the walk is halted. The average time until the walk halts is the hitting time for the measured quantum walk. The projective measurements used areΠ f = |v f v f | ⊗ 1 c and 1 −Π f , where |v f is the state on the final vertex. For a detailed explanation, we refer the reader to [8].
Spectral analysis of the unitary evolution operator reveals that there may be some eigenvectors that have no overlap with the chosen final vertex v f . If a component of the initial state |ψ exists in the subspace spanned by these eigenvectors, that component never reaches the final vertex. This phenomenon may lead to infinite hit- ting time at the final vertex, so we label this the Infinite Hitting Time (IHT) subspace, denoted as V . The overlap between the initial state and the IHT subspace quantifies the probability that the final vertex is never reached: where {V i } is an orthonormal basis for V . A sufficient condition for infinite hitting times, established in [8][9][10], is for the evolution unitary to contain at least one k-dimensional eigenspace, where k > d. Within this eigenspace there will exist a subspace of dimension at least k − d that has no support on the final vertex. This subspace forms a part of the IHT subspace. If multiple eigenspaces contain IHT subspaces, the sum of these subspaces gives the IHT subspace of the entire unitary.
While the above condition is sufficient for a quantum walk unitary to have an IHT subspace, it is not a necessary condition. It is possible for eigenspaces with degeneracy ≤ d to contain vectors that have no overlap with the final vertex. Hence one must perform an analysis over all the eigenspaces when computing the size of the IHT subspace. The procedure is simple. Apply Gaussian elimination to each eigenspace and subsequently count the number of vectors that have no overlap with a chosen final vertex.
In general, degenerate eigenspaces of the unitary contribute to the existence of IHT subspaces. This degeneracy is primarily a consequence of symmetry, hence an analysis of the symmetries of the quantum walk may provide conditions predicting infinite hitting times.

II. SYMMETRIES OF A QUANTUM WALK
Previous work has focused on the influence of graph symmetry on infinite hitting time [9,10]. Here, the symmetry of the graph was represented by its group of direction-preserving automorphisms. The irreducible representations of this group give a sufficient condition for a quantum walk on this graph to have infinite hitting times. If the dimension of at least one of the irreducible representations is larger than the dimension of the coin, a corresponding eigenspace of the quantum walk unitary will have larger dimension than the coin, which is a sufficient condition for a graph to exhibit infinite hitting times. These papers considered Cayley graphs, where the automorphism group is simply related to the group used to define the graph. The first discovery of infinite hitting time [9] was observed on the n-dimensional hypercube with 2 n vertices, where n ≥ 3.
An automorphism of a graph is a reordering of the vertices that leaves the graph unchanged. Since this reordering is just a permutation of the vertices, we can use permutation matrices to define automorphisms. We consider two classes of permutations P 1 ⊆ P 2 ⊆ P where P is the set of all permutations on H. P 1 and P 2 contain permutations with a tensor product structure and are defined as: and whereP v andP c are permutations acting on H v and H c respectively. PermutationsP that give rise to graph automorphisms necessarily leave the shift operator invariant: Thus the group of direction-preserving automorphisms studied in [8][9][10], is generated from permutations in P 1 that leaveŜ invariant: Here, we consider automorphisms from the larger class of permutations P 2 : which forms the group of joint automorphisms. Clearly Infinite hitting times in quantum walks are a consequence of symmetry in the quantum walk unitary (Û ).
These symmetries can be represented by unitary opera-tionsŴ forming the group of quantum walk symmetries Hence for a graph automorphism to be a symmetry of the quantum walk, it must satisfyPÛP † =Û . This is readily satisfied by all the elements of A 1 . Hence the group of direction-preserving automorphisms actually contains symmetries of the quantum walk: For elements in A 2 ,PÛP † =Û is only satisfied when the coin permutation leaves the coin operator invariant: The joint automorphisms that satisfy this condition are symmetries of the quantum walk and are denoted as the group of coin-permutation symmetries: Evidently, coin symmetry plays a large role in determining the size of the group of coin-permutation symmetries. By choosing coins of varying symmetry, it may be possible to connect characteristics of the coin-permutation symmetry group to the existence of infinite hitting times. Automorphisms of the graph from W ∩ (A \ A 2 ) may still be symmetries of the quantum walk. We do not address symmetries of this type and leave it open to future research. Fig. 1 summarizes the relations between the different symmetry groups discussed above.

III. COINS
In the analysis of infinite hitting times in quantum walks, we use three coins. On one end, we have the Grover coin which is the most symmetric of the lot. On the other end, we consider a random unitary, which should lack any particular symmetry. As an intermediate between these two, we also consider the Discrete Fourier Transform (DFT) coin.
• Grover Coin: This is the most symmetric coin generally used in quantum walks, and we would expect to see this symmetry reflected in the eigenspace decomposition of a walk's unitary. The symmetry arises from the permutation invariance [11] of the coin which takes the form where we choose a = 2 d − 1 and b = 2 d and d is the dimension of the coin. Due to the permutation invariance property, all d! permutation matricesP c of size d × d satisfy the coin-permutation symmetry constraint:P cĜPc =Ĝ, implying this coin is associated with the largest possible coin-permutation symmetry group.
The symmetries of this coin fit into the symmetries of the hypercube very nicely. A quantum walk on an n-dimensional hypercube with this coin can be reduced to a quantum walk on a line, for the initial state |0 0| ⊗ |ψ ψ| where |ψ = 1 √ n n j=1 |j [12].
• DFT Coin: Another commonly used coin is the DFT coin,D. It is a generalization of the popular Hadamard coin,Ĵ, to arbitrary dimension: where ω = e i2π/d . This coin is not as symmetric as the Grover coin, and we see this reflected in our analysis of quantum walk unitaries. For a DFT coin of any dimension, there are only two permutation matrices that leave the coin invariant. The identity permutation gives rise to directionpreserving automorphisms, however the permutation (1, d, d − 1, . . . , 3, 2) can create joint automorphisms. The associated coin-permutation symmetry group is hence smaller than that with the Grover coin, however W 1 W 2 .
• Asymmetric coin: Our last coin is a random unitary. To create this unitary, we generate a matrix of random complex numbers, and subsequently orthogonalize it. Here we expect W 1 = W 2 .

IV. SPECTRAL ANALYSIS OF QUANTUM WALK UNITARIES
Using the coins from the previous section, we constructed quantum walk unitaries for multiple Cayley graphs. We consider Cayley graphs since their construction always yields d-regular graphs, and their automorphism groups are closely related to the groups used to construct them. In particular we look at Cayley graphs of the abelian Z d 2 group (hypercube of dimension d) and symmetric groups of different sizes.
Cayley graphs are defined using a group G and a generating set H ⊆ G. The elements g i ∈ G form the vertices of the Cayley graph, and edges exist between two vertices g i and g i if g i · g −1 i ∈ H. In other words, an element of H, say h j , defines an edge between g i and g i when h j · g i = g i . Thus each element of G will have |H| edges, making it an |H|-regular graph. H is called a generating set if and only if its elements produce a Cayley graph that is connected.
The shift operator,Ŝ, for Cayley graphs will thus bê where h j · g i is the group composition operation between two elements h j and g i .
where h(a) is the Hamming weight of string a and x ⊕ y is the bitwise XOR of the bit strings corresponding to vertices x and y. In the Cayley graph formalism, this implies the generating set H contains all weight-one bit strings. For any vertex x, there can only be d other bit strings which satisfy the above equation, hence each vertex of the hypercube has degree d. Thus, each vertex has d basis states and the dimension of the coin Hilbert space H c is also d. Thus the unitary describing the evolution of states in a hypercube will be of dimension |H c |·|H v | = d·2 d . The 3D cube is displayed as an example in Fig. 2.
The hypercube is an interesting case, because it does not satisfy the sufficient condition derived in [9] for a graph to exhibit quantum walks with infinite hitting times. Its automorphism group is Abelian, and all its irreducible representations have dimension 1. However, it was observed in [9] that walks on the hypercube can indeed exhibit infinite hitting times with some coins. This was presumed to be an effect of the coin symmetry. In this paper, we can now validate that intuition.
In the hypercube, the shift operatorŜ can be expressed asŜ where e j is the n-bit string corresponding to the number 2 j , and the notation |a, b ≡ |a ⊗ |b . Thus the shift operator transfers the state from vertex x along edge j to the vertex x ⊕ e j .    The results of spectral decomposition of the unitaries are displayed in Table I, Table II and Table III. For each of the proposed quantum walks in this paper, we ask whether the walk may potentially exhibit infinite hitting time or not. First, we note that infinite hitting times are possible in all the tested hypercubes for quantum walks that use the Grover or DFT coin. The lack of graph symmetry is outlined by the fact that there are no degenerate eigenspaces in any of the unitaries using the asymmetric coin. As illustrated in the tables, the                     dimension of the IHT subspace is generally larger for quantum walks that use the Grover coin than those that use the DFT coin. For quantum walks that use the DFT coin, eigenspaces of dimension < d may also contribute to the IHT subspace. Specifically in the 3D cube, none of the eigenspaces are of dimension greater than three, or even equal to three, yet infinite hitting times are possible. This points to the fact that there may be a more general condition that can predict infinite hitting times in these types of walks.

B. Cayley graphs of the symmetric group
We consider Cayley graphs of symmetric groups with different generating sets. For the groups S 3 and S 4 we consider elements (1,2,3) and (1,2,3,4) respectively as the final vertices. Cayley graph is a circle of the six elements of S 3 , as shown in Fig. 3. Quantum walks on the circle do not exhibit infinite hitting time except when the coin operator is the identity.
• S 3 with generating set H = {(2, 1, 3), (3, 2, 1), (1, 3, 2)}: When we add the permutation element (1,3,2) to the generating set, the graph becomes   Fig. 5, whereas H 2 generates a Cayley graph that requires no more than four edges to reach every other vertex. The Cayley graph corresponding to this generating set is displayed in Fig. 6. Both graphs exhibit infinite hitting times, as shown in Table V and Table VI. However, the dimension of the IHT subspace changes in each case, as shown in Table VII. Using the asymmetric coin, the unitary has eigenspaces of degeneracy three, which arise due to symmetries of the shift matrix, S.