Quantum Pascal's Triangle and Sierpinski's carpet
Tom Bannink Harry Buhrman

On the stratifications of 2-qubits X-state space
    Arsen Khvedelidze1,2,3,4akhved@jinr.ru Astghik Torosyan4astghik@jinr.ru 

    December 30, 2023
=============================================================================


In this paper we consider a quantum version of Pascal's triangle. Pascal's triangle is a well-known triangular array of numbers and when these numbers are plotted modulo 2, a fractal known as the Sierpinski triangle appears. We first prove the appearance of more general fractals when Pascal's triangle is considered modulo prime powers. The numbers in Pascal's triangle can be obtained by scaling the probabilities of the simple symmetric random walk on the line. In this paper we consider a quantum version of Pascal's triangle by replacing the random walk by the quantum walk known as the Hadamard walk. We show that when the amplitudes of the Hadamard walk are scaled to become integers and plotted modulo three, a fractal known as the Sierpinski carpet emerges and we provide a proof of this using Lucas's theorem. We furthermore give a general class of quantum walks for which this phenomenon occurs.




§ INTRODUCTION

Pascals's triangle, shown in Figure <ref>, exhibits many interesting properties one of which is the appearance of a fractal when the numbers are considered modulo a prime p <cit.>. This is shown in Figure <ref>, and for p=2 the fractal is known as the Sierpinski triangle or Sierpinski gasket. One way of obtaining the numbers in Pascal's triangle is through a random walk on a line as will be explained in Section <ref>. This paper explores the results of considering a similar triangle of numbers that is obtained when the 1-dimensional random walk is replaced by a 1-dimensional quantum walk. This also yields the Sierpinski triangle when the probabilities associated to the quantum walk are considered modulo 2, but more interestingly one can find another fractal known as the Sierpinski carpet hidden in the amplitudes modulo 3 which is not present in Pascal's triangle. When these quantum walk numbers are plotted modulo p, more general fractals appear.



This paper starts with Pascal's triangle and shows how it is related to the Sierpinski triangle when the numbers are taken modulo a prime. We then provide a proof of the appearance of a more general version of the Sierpinski triangle when instead we take prime powers. Then, quantum walks are introduced with an emphasis on a walk that is commonly known as the Hadamard walk. We derive an expression for the probabilities of these walks and then the appearance of both the Sierpinski triangle and Sierpinski carpet is shown as well as some other properties.
Table <ref> provides a summarising overview of the different fractals that are obtained from these different sources.



§ PASCAL'S TRIANGLE
 
Pascal's triangle is a set of integers arranged in a triangle, where the k'th value in the n'th row (both n and k start at zero) is given by the binomial coefficient nk. It is shown in Figure <ref>, and can also be constructed by using nk=n-1k-1+n-1k, i.e. every number is the sum of its two neighbours in the row above. Alternatively it can be thought of as `scaled' probabilities of a random walk on ℤ, in the following way. Assume the random walk starts in the origin, and goes left or right with probability 1/2. The probability of being at location l∈ℤ after n steps, with -n≤ l ≤ n is given by 1/2^nn(n+l)/2 if n+l is even and 0 if n+l is odd. When considering only the n+1 non-zero probabilities after n steps, the k'th non-zero value corresponds to position l=-n+2k of the line, where 0≤ k≤ n. The k'th non-zero probability is given by 1/2^nnk. Removing the factor 1/2^n yields the integer numbers in Pascal's triangle.











 §.§ Pascal's triangle modulo two

Pascal's triangle has many interesting properties and one interesting feature comes from considering all numbers modulo two <cit.>. This `binary' triangle is shown in Figure <ref> where black and white pixels are used to represent the values modulo two. The figure that appears looks very much like the Sierpinski triangle (also known as the Sierpinski gasket). Indeed, in the limit of an infinite number of rows, Pascal's triangle modulo two is the Sierpinski gasket.


To prove that Pascal's triangle modulo two converges to the Sierpinski triangle, a definition of the Sierpinski triangle is needed. There are different ways to construct it, and one of them is by shrinking and duplication <cit.>. This process is shown in Figure <ref>. Start with any shape (a closed bounded region) in the plane, like shown in the first image. Shrink the shape to half its size (both height and width) and make three copies of it. Place these copies in the corners of an equilateral triangle such that the shapes touch as shown in the second image. Repeat this with the new shape. The rightmost image shows the result after four iterations, and after an infinite number of iterations one obtains the fractal.


To show that Pascal's triangle modulo two converges to the fractal, one can show that for all n, the shape given by the first 2^n+1  rows contains exactly three copies of the first 2^n rows, and nothing more than those copies, i.e. with `white' in-between, see Figure <ref>. If we index Pascal's triangle by row r and column c, with r≥ 0 and 0≤ c ≤ r then we need to show that for 0≤ r < 2^n and 0≤ c ≤ r,

    rc≡r+2^nc≡r+2^nc+2^n 2.

Here r+2^nc corresponds to a `pixel' in the copy at the bottom left, and r+2^nc+2^n corresponds to the copy at the bottom right, as shown in Figure <ref>.
Furthermore, we need to show that there is nothing more than these copies, i.e. the triangular area in-between the copies is empty. This means that the values in the corresponding region are even, and it is sufficient to show that the top row of the region is even with odd endpoints. The top row of this region is at r=2^n, and the endpoints of the row, c=0 and c=2^n are odd since r0=rr=1. When the remainder of this row is even, i.e. for 1≤ c ≤ 2^n - 1,

    2^nc   ≡ 0  2,

then the complete region will be even. This is because a value in Pascal's triangle is the sum of its two neighbours in the row above. Adding two even numbers results in an even number, so the next row (r=2^n+1) will also have even values except near the boundary where an even number is added to an odd number. In particular, at every row the size of the `even part' in the middle decreases by one, resulting in an empty up-side-down triangle ending at r=2^n + 2^n - 1 where the two endpoints have joined. By proving that the top row is even it follows that all entries in the up-side-down triangle are even. We conclude that it is sufficient to prove (<ref>) and (<ref>). For this, one can use Lucas's theorem.

It is convenient to introduce notation for representing a number by it's base-p digits for a prime p. We will write

    n = [n_m n_m-1⋯ n_0]_p = ∑_j=0^m n_j   p^j     with  0 ≤ n_i < p  for each  i,

where the n_i are the base-p digits of n


Let p be prime and n,k non-negative integers. Let n=[n_m n_m-1⋯ n_0]_p and k=[k_m k_m-1⋯ k_0]_p. Then

    nk≡n_mk_mn_m-1k_m-1⋯n_0k_0 p,

where we define nk=0 if k>n.


There are many extensions and generalisations of Lucas's theorem <cit.>, that include versions for prime powers or similar congruences for generalised binomial coefficients, but they are not needed here.

 
For any prime p,

    nk≡ 0  p     ∃ i   :   k_i > n_i



If there is an i such that k_i > n_i then n_ik_i=0 and by Lucas's theorem, nk≡ 0  p. Conversely, if k_i ≤ n_i for all i then n_ik_i=n_i!/k_i!(n_i-k_i)!. Since n_i <p and p is prime, we have that p is not a factor of n_i! and also not a factor of n_i!/k_i!(n_i-k_i)!. Since p is not a divisor of n_ik_i and p is prime, it also does not divide the product ∏_i n_ik_i which concludes the proof.

The following corollary considers adding extra digits to n and k and is also known as Anton's Lemma:
 
If n,k < p^m and then for all l,q≥ 0,

    l· p^m + nq· p^m + k≡lqnk p.



When n,k<p^m then n_i=k_i=0 for i≥ m, so that l· p^m + n = [l_M l_M-1⋯ l_0 n_m-1 n_m-2⋯ n_0]_p and q· p^m + k = [q_M q_M-1⋯ q_0 k_m-1 k_m-2⋯ k_0]_p. Therefore, by Lucas's theorem

    l· p^m+nq· p^m + k   ≡l_Mq_Ml_M-1q_M-1⋯l_0q_0n_m-1k_m-1⋯n_0k_0 p
       ≡lqnk p.


Note that vice versa, Corollary <ref> implies Lucas's theorem by induction on the number of digits.

We can now prove (<ref>) and (<ref>). By Corollary <ref> for p=2 we have

    r+2^nc≡10rc 2,
    r+2^nc+2^n≡11rc 2,

so (<ref>) follows from 10=11=1. To show (<ref>), note that since 1≤ c ≤ 2^n -1 there is a digit c_i that is nonzero for i<n, whereas all digits of r=2^n are zero except for the r_n, so (<ref>) follows form Corollary <ref>.



 §.§ Pascals triangle modulo general n


In a similar fashion one can consider Pascal's triangle modulo general n. Figure <ref> shows this for n∈{2,3,4,5,6,7}. We can distinguish cases for primes, prime powers and other numbers.



  §.§.§ Pascals triangle modulo a prime


When n is a prime (2,3,5,7 in the figure), one obtains a generalisation of Sierpinski's triangle. This generalisation for primes p can also be constructed using the shrinking and duplication method. When using the shrinking and duplication construction, one can start with an arbitrary shape, shrink it and create p(p+1)/2 copies. These copies have to be arranged into a larger triangle where all the copies are touching. The proof is a generalisation of the one given in the previous section. One has to show that

    rc≡r+l· p^nc+q· p^n p,

where 0≤ l < p and 0≤ q ≤ l. Each value of (l,q) corresponds to one of the p(p+1)/2 copies. This equivalence follows from Corollary <ref> and lq≢0  p. The empty up-side-down triangles correspond to r+l· p^mc+q· p^m but where the range of c is now r<c<p^m as opposed to 0≤ c ≤ r. This case is also included in Corollary <ref>, and as rc=0 for r<c this finishes the proof.



  §.§.§ Pascals triangle modulo a composite number


When n is composite (mod 6 in the figure) then the resulting shape is the union of the shapes obtained of its factors (prime powers) albeit with different colours. For example, at n=6, shown in Figure <ref> one can see the union of the shapes of p=2 and p=3. This is simply because when n=p_1^k_1⋯ p_m^k_m then x≡ 0  n if and only if for all i : x ≡ 0  p_i^k_i.



  §.§.§ Pascals triangle modulo a prime power


When n is a prime power then the pattern becomes slightly more complicated. One can see in Figure <ref> that for n=4, the image is the same as for n=2 but with extra triangles in the places that used to be empty. When one would consider n=8, this idea is repeated and the holes in the n=4 shape are filled with additional triangles.

Figure <ref> shows what happens when the triangle is plotted modulo powers of 3. From the Figure we can conjecture the general pattern: Start with the `mod p triangle' and in every empty region, add p(p-1)/2 copies of the `mod p triangle'. This yields the pattern for the `mod p^2 triangle'. To go to the `mod p^3 triangle', again add p(p-1)/2 copies of the `mod p triangle' to the empty regions of the `mod p^2 triangle'.

This process can be iterated to find the shape corresponding to p^k for any k. To make this statement more concrete, we need the following definition.

    The p-adic valuation ν_p(n) of a number n is the largest power of p that divides n.



The statements that we want to prove are most easily explained with a picture, shown in Figure <ref>. We will show that at each recursion level of the triangle, the p-adic valuation of the numbers r'c' in a copy (meaning r'=l p^n + r and c' = q p^n + c) is the same as that of the corresponding number rc in the original region. Furthermore, we show that the regions that were empty in the `mod p triangle' have particular p-adic valuations that are 1 or 2 or k higher than the original, as depicten in Figure <ref>. Every time you fill a previously-empty region with triangles, the p-adic valuation increases by one.

We will now prove this by using Kummer's theorem.

 
 


Let p be prime and n,k non-negative integers, n≥ k. Then the p-adic valuation ν_p(nk) of nk is equal to the number of “carries” when k and n-k are added in base-p arithmetic.

One way to find the number of carries that occur when k is added to n-k in base-p is by considering the base-p digits of n and k, defining c^n,k_-1=0 and

    c^n,k_i =  1     n_i < k_i
     0     n_i > k_i
     c^n,k_i-1    n_i = k_i .

The number of carries is then equal to ∑_i≥ 0 c^n,k_i. Kummer's theorem can therefore be written as ν_p(nk) = ∑_i≥ 0 c^n,k_i.

The following claim shows what happens to ν_p(nk) when a digit l is added to n and a digit q is added to k:

    Let p be prime and n,k,q,l,m non-negative integers with 0≤ k ≤ n < p^m and 0 ≤ q ≤ l < p. Then
    
    ν_p(l· p^m + nq· p^m + k) = ν_p(nk)



    Define n'=l· p^m +n and k'=q· p^m + k.
    Note that n,k have at most m-1 digits when expressed in base p and l,q are the m-th digits of n' and k'. Note that we have c^n,k_i=c^n',k'_i for i<m since the first m-1 digits are the same. For the m-th digits we have
    
    c^n',k'_m= 1     l < q
     0     l > q
     c^n,k_m-1    l = q  .

    By Kummer's theorem the difference between ν_p(n'k') and ν_p(nk) is equal to c^n',k'_m, so it remains to show that c^n',k'_m=0. By assumption we know q≤ l and if q<l we have c^n',k'_m = 0 by definition. Consider the case l=q where we have c^n',k'_m = c^n,k_m-1. If n=k then all the c^n,k_i are zero so we are done. If n ≠ k then the consider the most significant digit where n and k differ, i.e. take the highest i for which n_i ≠ k_i and call it i^*. Since k<n by assumption, it must be true that k_i^* < n_i^* and therefore c^n,k_i^* = 0. For all i>i_* we have n_i=k_i so c^n,k_i=c^n,k_i-1. So c^n',k'_m = c^n,k_i_* = 0.


    If ν_p(n) = ν_p(m) then for any k 
    n≡ 0  p^k  m≡ 0  p^k.



    It follows from the fact that n≡ 0  p^k if and only if ν_p(n) ≥ k.


Consider Figure <ref>.
The size of the recursion levels in the `mod p^k triangle' is the same as in the mod p triangle, meaning powers of p and not powers of p^k. Repeating what we did before for the mod p triangle, we can see that at recursion level n, the “copies” and “empty regions” correspond to the following binomial coefficients of Pascal's triangle:

    l· p^n+rq· p^n + c      [                           “copies”→ 0 ≤ q ≤ l < p   ,   0 ≤ c ≤ r < p^n;                            “empty”→ 0 ≤ q < l < p   ,   0 ≤ r < c < p^n ]
        .

Here n is the recursion level and (l,q) index the different copies or empty regions whereas r and c index points within those regions. By claim <ref>, the p-adic valuation of a number r'c' in the copy is the same as that of the corresponding original number rc. By Claim <ref>, we have now shown that for any k, the copies in the `mod p^k triangle' are indeed all the same.

What is left to show is how the empty regions of the `mod p triangle' are filled. We will first consider k=2. The new triangles in the mod p^2 shape can be indexed as follows:

    l· p^n + s· p^n-1 + rq· p^n + t · p^n-1 + c    with [  0 ≤ q < l < p   ,;  0 ≤ s < t < p   ,; 0 ≤ c ≤ r < p^n-1. ]

These lie within the empty regions of the mod p triangle. Similar to the proof of Claim <ref> we can let the carries c^r',c'_i be defined as before, for the numbers r'=[l s r_n-2r_n-3...r_0]_p and c'=[q t c_n-2...c_0]_p. We have q<l hence c^r',c'_n=0 and s<t so c^r',c'_n-1=1. This means there is exactly one extra carry compared to r and c and hence by Kummer's theorem

    ν_p(l· p^n + s· p^n-1 + rq· p^n + t · p^n-1 + c) = ν_p(rc) + 1

for these values of l,q,s,t,r,c.
This is what we need, because it implies

    l· p^n + s· p^n-1 + rq· p^n + t · p^n-1 + c≡ 0  p^k+1rc≡ 0  p^k

i.e. in the mod p^k+1 shape there is a copy of the (smaller) mod p^k shape. This proves what was drawn as a size-p^n triangle in Figure <ref>.
If we continue to the triangles that are newly added in the `mod 3^3 triangle', we find that they correspond to

    r'_n· p^n + r'_n-1· p^n-1 + r'_n-2· p^n-2 + rc'_n· p^n + c'_n-1· p^n-1 + c'_n-2· p^n-2 + c
                with [     0 ≤ c'_n < r'_n < p   ,;  0 ≤ r'_n-1≤ c'_n-1 < p   ,; 0 ≤ r'_n-2 < c'_n-2 < p   ,;          0 ≤ c ≤ r < p^n-2. ]

Define r'=[r'_n r'_n-1 r'_n-2 r_n-3⋯ r_0]_p and c'=[c'_n c'_n-1 c'_n-2 c_n-3⋯ c_0]_p. Then by the same reasoning as before we can apply Kummer's theorem to obtain ν_p(r'c') = ν_p(rc)+ c^r',c'_n-2 + c^r',c'_n-1 + c^r',c'_n. Looking at the constraints for digits n-2 up to n we see that c^r',c'_n = 0, and c^r',c'_n-1 is 1 or equal to c^r',c'_n-2 which is always 1. We conclude: ν_3(r'c') = ν_3(rc)+2. We can continue the pattern, and we find that in the `mod p^k+1 triangle', the newly added triangles correspond to the following constraints on the digits of r',c' with the following carries:

    0 ≤ c'_n          <    r'_n < p              c^r',c'_n = 0 
    
        0 ≤ r'_n-1   ≤ c'_n-1 < p       c^r',c'_n-1 = 1  or  c^r',c'_n-1 = c^r',c'_n-2
       ⋮
    
        0 ≤ r'_n-k+1   ≤ c'_n-k+1 < p     c^r',c'_n-k+1 = 1  or  c^r',c'_n-k+1 = c^r',c'_n-k
    
        0 ≤ r'_n-k   <    c'_n-k < p          c^r',c'_n-k = 1 
    
        0 ≤ c             ≤ r < p^n-k   ν_3rc .

We see that ν_3r'c' = ν_3rc + k as required.
We still have to show that the empty regions in the `mod p^k+1 triangle' are empty. They correspond to the same indices as above except for 0≤ r'_n-k≤ c'_n-k < p and 0 ≤ r < c < p^n-k. We can apply the same idea as in the proof of Claim <ref> by noting that the first digit where r and c differ will satisfy r_i^* < c_i^* and hence all the carries c^r',c'_i are 1 for i ≥ i^*. This gives ν_3 r'c'≥ k+1, meaning that r'c'≡ 0  p^k+1 so the region is indeed empty.

 

Since the numbers in Pascal's triangle can be thought of as scaled probabilities of a random walk, one could imagine writing down probabilities of a quantum walk, scaled to become integer, and show them modulo two. The next section will introduce a specific quantum walk and apply this idea with p=2 and p=3.




§ HADAMARD WALK

Quantum walks are simple models for a quantum particle moving through some system. This paper is only concerned with the probability distribution that emerges from one particular quantum walk, and therefore the physical aspects of it are left out. Here we only provide a short overview of the relevant concepts, and we refer the reader to <cit.> for a complete introduction to the field of quantum information. For the purposes of this paper we only need to know that the state of a particle is described by a unit vector in a complex Hilbert space, and quantum mechanics dictates that time evolution is limited to applying unitary operators to this vector. We will denote such state vectors using the commonly used `bra-ket' notation, writing |ψ⟩ for a vector as opposed to ψ⃗. We can write the vector as a linear combination of orthonormal basis states, |ψ⟩=∑_i α_i |x_i⟩ where α_i∈ℂ and ∑_i |α_i|^2 = 1. The |x_i⟩ are the standard basis vectors of the Hilbert space and the coefficients α_i are known as amplitudes. Inner products are denoted by ⟨ϕ|ψ⟩ for two vectors |ϕ⟩ and |ψ⟩. One of the axioms of quantum mechanics states that one can observe (measure) the system |ψ⟩ in a chosen basis and the result can be any of the basis states, where state |x_i⟩ has probability |α_i|^2 of appearing.

A simple example of a quantum walk on a one-dimensional line is the so-called Hadamard walk <cit.>. It can be thought of as a quantum particle moving on ℤ, the discrete line. The particle has an internal degree of freedom other than its position (a spin-1/2 degree of freedom, for physicists). The internal state is sometimes referred to as the coin state of the particle with associated Hilbert space ℋ_coin=ℂ^2 and basis states  and . The Hilbert space associated with the complete quantum system is ℋ=ℋ_pos⊗ℋ_coin where ℋ_pos=span{|n⟩ |  n∈ℤ}. So the most general state of the particle is

    |ψ⟩ = ∑_n∈ℤ(α_n,↑|n,↑⟩+α_n,↓|n,↓⟩) ,

with normalization ∑_n∈ℤ(|α_n,↑|^2+|α_n,↓|^2) = 1 and where we used the notation |a,b⟩≡|a⟩⊗|b⟩. The dynamics of the particle are given by repeated application of a unitary operator U that consists of two steps. The first step is a unitary only applied to the internal state and is sometimes considered the quantum analogue of `flipping a coin'. The second step updates the position of the particle conditioned on the outcome of the coin. In the specific case of the Hadamard walk, the unitary in the first step is the Hadamard operator H, defined as

    H = 1/√(2)[  1  1;  1 -1 ],  where  = [ 1; 0 ] and  = [ 0; 1 ].

The time evolution operator U is then given by

    U = S·(Id_pos⊗ H),

where Id_pos is the identity on ℋ_pos and S is called the shift, given by

    S|n,↑⟩ = |n+1,↑⟩,     S|n,↓⟩=|n-1,↓⟩.

It can be thought of as updating the position of the particle conditioned on the outcome of the coin flip. A full step U of the Hadamard walk, acting on the basis state |n,↓⟩ for example, is given by

    U|n,↓⟩coin= S (1/√(2)|n,↑⟩ - 1/√(2)|n,↓⟩) shift=1/√(2)|n+1,↑⟩ - 1/√(2)|n-1,↓⟩ .

If we now were to measure the system, the result would be either |n+1,↑⟩ or |n-1,↓⟩, both with probability |±1/√(2)|^2=1/2.

Figure <ref> shows a schematic representation of one step U of the Hadamard walk.

With these definitions, one can now consider the following process. Select a starting state, say |ψ_s⟩=|0,↑⟩, evolve it with U for t steps and then measure the position. For example, starting in |0,↑⟩, the state of the system after three steps is given by

    U^3 |0,↑⟩ = 1/(√(2))^3(
          |-3,↓⟩
        - |-1,↑⟩
        + 2 |1,↑⟩ + |1,↓⟩
        + |3,↑⟩).

Now measuring the system will result in finding some position X with probabilities ℙ[X=-3]=1/8, ℙ[X=-1]=1/8, ℙ[X=1]=5/8 and ℙ[X=3]=1/8. The amplitudes of the first five steps are also displayed in Figure <ref>.



 §.§ Hadamard triangle

The numbers in Pascal's triangle can be thought of as scaled probabilities of a random walk, and carrying this idea over to the Hadamard walk, one could consider the amplitudes or probabilities of the Hadamard walk, but scaled by a factor of √(2^n) so that all numbers involved become integer. Another way to view this is instead of applying H, use √(2)H, a matrix with only integer coefficients. Note that we could either use the amplitudes or the probabilities which are simply their squares. However, since we are primarily interested in whether or not they are divisible by some prime p, squaring the amplitudes does not make a difference. We therefore continue with the (unsquared) amplitudes. Figure <ref> shows the start of the Hadamard triangle.





























We will now derive expressions for these amplitudes when starting in |0,↑⟩.



 §.§ Expressions for amplitudes

Meyer <cit.> gave explicit expressions for the amplitudes encountered in the Hadamard walk. Let ψ_↑(n,t) be the amplitude at |n,↑⟩ after t steps when starting in |0,↑⟩, i.e. ψ_↑(n,t):=⟨ n,↑|U^t|0,↑⟩. Similarly, let ψ_↓(n,t):=⟨ n,↓|U^t|0,↑⟩. Then we have
 When t+n is odd or when |n|>t we have ψ_↑(n,t)=ψ_↓(n,t)=0. Otherwise the amplitudes are given by

    ψ_↑  (n,t)    =
        1/√(2^t)    n = t
    1/√(2^t)∑_k≥ 1(t-n)/2-1k-1(t+n)/2k(-1)^(t-n)/2-k    n < t
        
    ψ_↓(n,t)    = 1/√(2^t)∑_k≥ 0(t-n)/2-1k(t+n)/2k(-1)^(t-n)/2-k-1


We will give an alternative and slightly shorter proof of this for a general coin operator. This proof also allows us to make another observation stated in the following claim. Let C be any unitary 2x2 matrix. Any such matrix can be written as follows

    C = [ c_r c_u; c_d c_l ]
        = [           √(p)  e^i α          √(1-p)  e^iβ;       - √(1-p)  e^i γ √(p)  e^i (γ + β - α) ]   ,   with  0 ≤ p ≤ 1.

 
    Let ψ_↑(n,t) and ψ_↓(n,t) be the up and down amplitudes at position n at time t but for the general coin operator C.
    When t+n is odd or when |n|>t we have ψ_↑(n,t)=ψ_↓(n,t)=0. Otherwise the amplitudes are given by
    
    ψ_↑  (n,t)    =
            
                e^iα n√(p^t)    n = t
    
                e^i(α n + (γ+β)(t-n)/2)√(p^t)∑_k≥ 1(t+n)/2k(t-n)/2-1k-1(-1-p/p)^k     n < t
            
    ψ_↓(n,t)    = -e^i(α n +(γ+β)(t-n)/2 -β)
               ×  √((1-p)p^t-1)∑_k≥ 0(t+n)/2k(t-n)/2-1k(-1-p/p)^k

    The probabilities |ψ_↑(n,t)|^2 and |ψ_↓(n,t)|^2 associated to these amplitudes are independent of the complex phases α,β,γ of the coin operator.

Note that the lemma follows directly from the claim by setting p=1/2, α=β=0 and γ=π to obtain the Hadamard coin matrix. Furthermore note that for a more general starting state, not equal to |0,↑⟩, the probabilities do depend on the complex phases present in the coin operator.


We want to have an expression for both the up and down component at position n after t steps, i.e. we want to know ⟨ n,↑|U^t|0,↑⟩ and ⟨ n,↓|U^t|0,↑⟩. These two cases will be handled separately. We will use the path counting technique, where one counts all possible paths starting at |0,↑⟩ and end at the desired state. Every path gets a certain (possibly negative) amplitude and these have to be added.


  §.§.§ Up component

We want to find all possible paths from |0,↑⟩ to |n,↑⟩ using t steps. If n=t there is exactly one path. Otherwise, we have -t< n < t. Figure <ref> shows the directed graph on which we consider possible paths. Consider a single path and let r,l,u,d be the number of times the path uses the right, left, up and down arrows respectively. To end at |n,↑⟩ we then have

    r+l+u+d   =t    total number of steps
    
        r-l    =n       ending column
    
        u      =d       start up and end up

Let k=u=d, then we have r=t+n/2 - k and l=t-n/2 - k. We have k≥ 1 (we need to go down and up at least once) and k≤t-n/2,t+n/2.


For a specific set of values (r,l,u,d) the path will arrive with an amplitude (c_r)^r(c_l)^l(c_u)^u(c_d)^d. So we sum over all possible values for (r,l,u,d) and count how many paths there are for a specific set of values (r,l,u,d). We can construct such paths as follows. Construct a sequence of choices to make if the walker is in the top layer and another sequence of choices to make if the walker is in the bottom layer.
The walker is in the  state (top layer) k+r=t+n/2 times, out of which r times it goes right and k times it goes down. There are (t+n)/2k possible ways to do this. Likewise, the particle is in  (bottom layer) l+k=t-n/2 times and has to choose between left and up. The last of these choices should always be up, so this gives (t-n)/2-1k-1 possibilities. To construct the full path, start with the top-layer choices, and whenever the choice is `down', continue with the bottom-layer choices and so on.
Therefore

    ⟨n,↑|U^t|0,↑⟩   =  (c_r)^t     n = t
    ∑_k≥ 1(t+n)/2k(t-n)/2-1k-1 c_r^(t+n)/2-k c_l^(t-n)/2-k c_u^k c_d^k     n < t .

Now rewrite the last sum for n<t and group the factors that do not depend on k:

    c_r^(t+n)/2 c_l^(t-n)/2∑_k≥ 1(t+n)/2k(t-n)/2-1k-1(c_u c_d/c_r c_l)^k

Note that c_u c_d/c_r c_l = -1-p/p so this fraction is always a real (negative) number, regardless of the complex phases present in the entries of the coin matrix. The sum above in terms of p and α,β,γ is equal to

    e^i(α n + (γ+β)(t-n)/2)√(p^t)∑_k≥ 1(t+n)/2k(t-n)/2-1k-1(-1-p/p)^k ,

as claimed.
The probability |ψ_↑(n,t)|^2 of being at |n,↑⟩ after t steps when starting in |0,↑⟩ is independent of α,β,γ since the only dependence on these variables is in the prefactor e^i(α n + (γ+β)(t-n)/2) which always has norm 1.



  §.§.§ Down component

For the down component, the equations are similar:

    r+l+u+d   =t      total number of steps
    
        r-l       =n+1    ending column (tilted)
    
        u+1       =d      start up and end down

Let u=k, then the equations give r=(t+n)/2-k and l=(t-n)/2-k-1. The argument is the same as before, but now the last choice in the top layer has to be `down' with no restrictions on the last choice in the bottom layer.
We are in  r+d=(t+n)/2+1 times. The last choice has to be down, so this gives (t+n)/2k.
We are in  l+u=(t-n)/2-1 times which gives (t-n)/2-1k. The expression is therefore given by

    ψ_↓(n,t)    = ∑_k≥ 0(t+n)/2k(t-n)/2-1k c_u^k c_d^k+1 c_l^(t-n)/2-k-1 c_r^(t+n)/2-k .

Rewriting this in terms of p,α,β,γ gives the expression given in the claim. Again the only dependency on the complex phases is in the prefactor which has norm 1 so the probability |ψ_↓(n,t)|^2 only depends on p.



 §.§ Hadamard walk modulo 2 - Sierpinski triangle
 
When the amplitudes of the Hadamard walk are plotted modulo two, the Sierpinski triangle appears in a similar fashion to Pascal's triangle. To see why this is the case, we note that to find the amplitudes at some time t modulo two it is enough to consider a process where every single time-step is done modulo two. The scaled Hadamard operator becomes

    √(2)H ≡[ 1 1; 1 1 ] 2,

and we can immediately see that the amplitude sent to the right is the same as the amplitude sent to the left. More precisely, after any time-step the amplitude at |n-1,↓⟩ is the same as the amplitude at |n+1,↑⟩ modulo two, for all n. 

This idea is shown in Figure <ref> which is similar to Figure <ref> but modulo two. An ellipse is drawn around the pairs of amplitudes of states |n-1,↓⟩ and |n+1,↑⟩. The figure shows that the two values in each ellipse are equal, and are the sum of the values in the two neighbouring ellipses above it. This is the same rule with which Pascal's triangle can be constructed. Indeed, taking one value out of every ellipse, the Sierpinski triangle can be obtained. These are the either the red or the blue values shown in Figure <ref>.



 §.§ Hadamard walk modulo 3 - Sierpinski carpet
 

We will now show that the  components of the scaled walk, modulo three, give rise to the Sierpinski carpet. In particular, we colour a square white if the amplitude is divisible by 3, and give it a different colour otherwise. Figure <ref> shows the start of the resulting carpet. The top of the carpet is at t=1 and n=-1 indicated by the blue values in Figure <ref>. Considering only these values, indexed by a row R and column C we are interested in amplitudes at t=R+1 and n=2C-R-1. Define H_blue(R,C):=ψ_↓(2C-R-1,R+1), then

    H_blue(R,C)    = (-1)^R-C∑_k=0^min(C,R-C)CkR-Ck (-1)^k.

For the structure of the Sierpinski carpet, however, it is more convenient to consider coordinates x,y that are aligned with the square structure of the carpet. The choice of these directions is indicated in Figure <ref>, and we have R=x+y and C=x. As a function of these coordinates we define Φ(x,y) = H_blue(x+y,x), so

    Φ(x,y) = (-1)^y ∑_k=0^min(x,y)xkyk (-1)^k.

A pixel at coordinates x,y is now coloured white if Φ(x,y)≡ 0  3 and a different colour otherwise. To show that the resulting figure is the Sierpinski carpet we have to show that for all n≥ 1 and 0≤ l,q ≤ 2 with (l,q)≠(1,1),

    Φ(x,y) ≡±Φ(l·3^n + x,q·3^n + y)  3     for all  0≤ x,y ≤ 3^n - 1

where this means that for every x,y,l,q the equivalence should hold with either a plus or minus sign. For (l,q)=(1,1) we require

    Φ(3^n+x,3^n+y) ≡ 0  3     for all  0≤ x,y ≤ 3^n - 1

Figure <ref> shows this graphically. The values (l,q)=(1,1) corresponds to the empty square in the middle, and all other values of (l,q) should be copies of the square at (l,q)=(0,0), up to exchanging the non-white colours.

To show this we prove something slightly more general.
 
For any m∈ℤ define f_m:ℕ×ℕ→ℤ as

    f_m(x,y) = ∑_k=0^min(x,y)xkyk (-m)^k


The reason for the minus sign in (-m)^k is that all valid quantum walks will have m≥ 0 this way, as will become clear later.
As a side note, this function is a special case of the so-called hypergeometric function _2F_1(a,b;c;z), namely f_m(x,y) = _2F_1(-x,-y,1,-m).
The following claim could be seen as something similar to Corollary <ref> but for f_m:
 
    Let p be a prime and let 0≤ l,q ≤ p-1. Then we have for all m∈ℤ and for all 0≤ x,y≤ p^n - 1
    
    f_m(l· p^n + x  ,  q· p^n + y) ≡ f_m(l,q)· f_m(x,y)  p .



    Note that any sum can be split in the following way:
    
    ∑_k=0^p^n+1-1 g(k) = ∑_s=0^p-1∑_k=0^p^n - 1 g(s· p^n + k) ,

    where s takes the role of the most significant digit and k takes the role of the other digits. We apply this idea to the sum in f_m(x,y) where we note that min(lp^n + x, qp^n + y) ≤ p^n+1 -1 but we can let the sum range all the way to p^n+1-1 because the summand is zero in this extra range. Therefore we have
    
    f_m(l· p^n + x  ,  q· p^n + y)     = ∑_k=0^p^n+1-1l· p^n+xkq· p^n+yk (-m)^k 
       = ∑_s=0^p-1∑_k=0^p^n-1l· p^n+xs· p^n + kq· p^n+ys· p^n + k (-m)^s· p^n + k

    Note that by Fermat's little theorem we have m^p ≡ m  p so m^s· p^n≡ m^s  p. Now we apply Corollary <ref> to the binomial coefficients to obtain
    
    f_m(l· p^n + x  ,  q· p^n + y)     ≡∑_s=0^p-1∑_k=0^p^n-1lsqsxkyk (-m)^s + k
       ≡( ∑_s=0^p-1lsqs (-m)^s ) f_m(x,y) 
       ≡ f_m(l,q)· f_m(x,y)  p,

    as required.

Note that l,q take the role of the most significant digits and x,y are the other digits. Just as Corollary <ref> implies Lucas's theorem, we can apply this claim inductively on the number of digits to arrive at a result very similar to Lucas's theorem but now for the function f_m:
[Lucas'-like theorem for f_m] 
    Let p be prime and x,y non-negative integers. Let x=[x_n x_n-1⋯ x_0]_p and y=[y_n y_n-1⋯ y_0]_p. Then for all m∈ℤ we have
    
    f_m(x,y) ≡ f_m(x_n,y_n)  f_m(x_n-1,y_n-1)⋯ f_m(x_0,y_0)  p.



We can now prove (<ref>) and (<ref>) by noting that Φ(x,y) = (-1)^y f_1(x,y) so by Claim <ref> we have

    Φ(l· 3^n + x, q· 3^n + y) ≡ (-1)^q· 3^n f_1(l,q) Φ(x,y) ≡Φ(l,q)Φ(x,y)  3.

where we used that (-1)^q· 3^n = (-1)^q. Note that Φ(1,1) = 0 which proves (<ref>) and Φ(l,q) ≡± 1  3 for the other values of l,q which proves (<ref>).
























 §.§ Results for a more general quantum walk

We can generalize the results of the previous section. First of all, we can consider the same numbers modulo any prime p. But more generally, the Hadamard operator H could be replaced by any matrix C∈ U(2). As stated before, we can write any unitary 2× 2 matrix as

    C = [ c_r c_u; c_d c_l ]
        = [           √(p)  e^i α          √(1-p)  e^iβ;        -√(1-p)  e^i γ √(p)  e^i (γ + β - α) ]   ,   with  0 ≤ p ≤ 1.

The expression for the amplitudes with general coin operator is given by ψ_↓(n,t) as given in Claim <ref>, and we can do the same substitutions as before to go to the x,y coordinates:

    Φ_C(x,y)    = c_d c_r^x c_l^y ∑_k≥ 0xkyk(-1-p/p)^k 
       = c_d c_r^x c_l^y   f_m(x,y) .

where m=(1-p)/p and we extend the definition of f_m for non-integer m. Note that (1-p)/p≥ 0 for any valid coin which was the reason for defining f_m with a minus sign.
In the previous sections we considered the amplitudes of the quantum walk as opposed to the probabilities (which are equal to the norm squared of the amplitudes). For the purpose of the Sierpinski carpet, this distinction was not important because all entries of the Hadamard matrix are real and we were only interested in whether or not an integer was zero modulo a prime. Since x≡ 0  p  x^2≡ 0  p, squaring did not matter. For a general coin, however, there could be complex amplitudes and so we consider the corresponding probabilities to make sure all numbers involved are real. Note that since f_m is real, the imaginary component of Φ_C(x,y) comes only from c_d c_r^x c_l^y. We therefore consider the probabilities:

    |Φ_C(x,y)|^2 = |c_d c_r^x c_l^y |^2 ( f_m(x,y) )^2 .

In the previous sections we rescaled the Hadamard matrix by a factor of √(2) so that all numbers involved became integer. For a general coin matrix, in order to consider the probabilities modulo a prime, we assume that the coin matrix is such that m=(1-p)/p is integer. Note that this can not be achieved by scaling the entire matrix because m is invariant under such scalings. In fact, we have p=1/1+m and m≥ 0 has to be integer. Furthermore, as stated in Claim <ref>, the complex phases α,β,γ do not influence |Φ_C(x,y)|^2. Therefore the most general form of the matrix we can consider to obtain integer probabilities is the unitary matrix

    C_m =
        [  √(1/(1+m))  √(m/(1+m));  √(m/(1+m)) -√(1/(1+m)) ]  for  m∈ℤ ,  m ≥ 0 ,

where have set α=β=0 and γ=π such that C_1=H, but any other setting of phases would be equally valid.
If we want to scale the matrix by a factor λ such that |c_d c_r^x c_l^y|^2 is integer then this requires λ = √(n(1+m)) for any integer n≥ 1. This gives a scaled matrix 

    √(n(1+m))C_m = √(n)[    1 √(m); √(m)   -1 ] ,

and for this scaled matrix, |c_d c_r^x c_l^y|^2 = m n^x+y+1.
By Claim <ref> we have for this scaled coin matrix that

    |Φ_C(l· p^n+x,q· p^n+y)|^2    ≡n^(l+q)(p^n-1)-1/m  |Φ_C(l,q)|^2   |Φ_C(x,y)|^2  p 
       ≡1/mn  |Φ_C(l,q)|^2   |Φ_C(x,y)|^2  p ,

where we used Fermat's little theorem in the second step.
For m=1 and n=1 we recover the exact same rules as for the Hadamard matrix. This class also includes the commonly used coin

    1/√(2)[ 1 i; i 1 ].

To find out what kind of fractals are generated by these quantum walks, it is useful to note that we are only interested in distinguishing |Φ(x,y)|^2 ≡ 0  p from |Φ(x,y)|^2≢0  p. Since we have |Φ(x,y)|^2 = mn^x+y+1(f_m(x,y))^2 we can see that if m≡ 0  p or n≡ 0  p then all values |Φ(x,y)|^2 are zero modulo p and there is no fractal since all pixels are white. Therefore, assume that both m and n are not zero modulo p. In that case we have |Φ(x,y)|^2 ≡ 0 p if and only if f_m(x,y)≡ 0  p. Now we can apply the quantum version of Lucas' theorem. By Lemma <ref>, f_m(x,y)≡ 0  p if and only if there is an i such that f_m(x_i,y_i)≡ 0  p, where x_i,y_i are the base-p digits of x,y. 

In general, to find the fractal generated by a quantum walk with the general coin from Equation (<ref>) for some n,m that are non-zero modulo p, we simply have to compute f_m(x,y)  p for only 0≤ x,y < p to find what we call the base image. Figure <ref> shows these base images for several values of m and p.  From this the fractal can be constructed in a simple recursive way, shown in Figure <ref>, resulting in the fractals shown in Figure <ref>.
This recursive method is valid because each recursion step corresponds to adding another digit to x and y, and as mentioned above, a pixel will be white if and only if there are digits (i.e. a recursion step) in which the region corresponding to those digits is white. In case of the example construction (Figure <ref>), the third picture corresponds to x,y values in the range 0≤ x,y < 2^3 which can be described by three digits modulo 2. Let x=[x_2 x_1 x_0]_2 and y=[y_2 y_1 y_0]_2, then x_2,y_2 specify which of the four biggest quadrants the pixel is in. Likewise, x_1,y_1 specify which of the four subquadrants of that first quadrant it is in, and x_0,y_0 specify the final position within that subquadrant. By the construction in Figure <ref>, the pixel will be white if and only if one of those chosen quadrants was bottom-right. This is equivalent to saying that the pixel is white if and only if there is an i such that f_m(x_i,y_i)≡ 0 p.







 §.§ Other properties of the Hadamard triangle

One can add the probabilities in each row of the triangle and by unitarity this sum will always be equal to one. Instead one can also consider summing all the amplitudes in a row. Define the column vector Ψ(t) = (Ψ_↑(t)   Ψ_↓(t))^T where Ψ_↑(t) is the sum of the up amplitudes at time t, i.e.

    Ψ_↑(t) = ∑_n=-t^tψ_↑(n,t) ,

and similar for Ψ_↓(t). Alternatively, consider the linear map

    Σ = ∑_n∈ℤ⟨n|,

so that Ψ(t) = Σ  U^t |0,↑⟩.
Note that to go from time t to t+1, one application of a coin and shift is performed (U=S(Id⊗ H)), but the sums of all up or down amplitudes are invariant under the shift operation. In other words Σ S = Σ. Furthermore we have Σ (Id⊗ H) = H Σ, so we have

    Σ U^t = Σ (S(Id⊗ H))^t = H^t Σ.

This can also be seen by simply looking at Figure <ref>, and noting that Ψ_↑(t+1)=1/√(2)(Ψ_↑(t)+Ψ_↓(t)) and Ψ_↓(t+1)=1/√(2)(Ψ_↑(t)-Ψ_↓(t)), or simply

    Ψ(t+1) = H Ψ(t).

The sum over all amplitudes, up and down, is therefore

    Ψ_↑(t) + Ψ_↓(t) =
        Ψ_↑(0) + Ψ_↓(0)     t  even
    √(2)Ψ_↑(0)     t  odd

Note that when the process is scaled so that all numbers become integer (i.e. H'=√(2)H), as was done for the fractals, and the starting state is |0,↑⟩ then the above gives

    Ψ'_↑(t) + Ψ'_↓(t) =
        
            2^t/2    t  even,
    
            2^(t+1)/2    t  odd,

so the sum of all amplitudes in a row is always a power of two.

 

Pascal's triangle has the property that summing over the so-called shallow diagonals yields the Fibonacci sequence. The n'th shallow diagonal d_n (n≥ 0) corresponds to the sum

    d_n = ∑_c = 0^⌊ n/2 ⌋n-cc,

over the numbers in Pascal's triangle and is equal to the Fibonacci number F_n+1, where F_1=F_2=1 and F_n+1=F_n + F_n-1. By the property nk=n-1k-1+n-1k it follows that

    d_n    = ∑_c≥ 1(n-1)-cc-1 + ∑_c ≥ 0(n-1)-cc
       = ∑_c≥ 0(n-2)-cc + ∑_c ≥ 0(n-1)-cc = d_n-2 + d_n-1.

We can consider the same diagonals but now in the triangle of amplitudes of the Hadamard walk. In particular we will consider the same numbers that gave rise to the Sierpinski triangle, namely the red and blue numbers of Figure <ref>. The blue numbers (down components) are given by H_blue as in Equation (<ref>). Similarly, the red numbers (up components) are given by

    H_red(R,C) = ∑_k≥ 1C+1kR-C-1k-1 (-1)^R-C-k    C < R
     1     C=R

Unlike the case of Pascal's triangle, it now matters in which direction the diagonal is considered because the triangle is no longer symmetric. We therefore consider four options, corresponding to the two triangles (red and blue) and the two possible directions for the diagonals ╱ and . We denote the ╱ diagonals by A_red and A_blue and the  diagonals by B_red and B_blue. They are defined as

    [               A_blue,n =     ∑_c≥ 0 H_blue(n-c,c)                                        B_blue,n =  ∑_c≥ 0 H_blue(n-c,n-2c);               A_red ,n =     ∑_c ≥ 0 H_red(n-c,c)                                        B_red ,n = ∑_c≥ 0 H_red(n-c,n-2c) . ]

Using the same property of binomial coefficients as before, we have

    A_blue,n   =∑_c≥ 0∑_k≥ 0ckn-2ck (-1)^n-k
       =∑_c≥ 0∑_k≥ 0ckn-2c-1k-1 (-1)^n-k
        + ∑_c≥ 0∑_k≥ 0ckn-2c-1k (-1)^n-k
       = A_red,n-2 - A_blue,n-1

Similarly we find

    A_red,n = A_red,n-2 + A_blue,n-1,

and combining these two equations yields the same recurrence relation for both the red and blue diagonals:

    A_n   = - A_n-1 + A_n-2 + 2 A_n-3,

but with different initial conditions for the red and blue sequences.
For the diagonal in the other direction () we find

    B_blue,n   = B_red,n-1 - B_blue,n-2, 
    
        B_red ,n   = B_red,n-1 + B_blue,n-2,

which can be combined to form another recurrence relation

    B_n = B_n-1 - B_n-2 + 2 B_n-3,

that holds for both the blue and red sequence but with different initial conditions.



§ ACKNOWLEDGEMENTS

The authors would like to thank Florian Speelman and Jeroen Zuiddam for useful discussions and Frank den Hollander for feedback.
The work in this paper is supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.



