{'fraction_non_alphanumeric': 0.015559633027522935, 'fraction_numerical': 0.00910091743119266, 'mean_word_length': 4.684605757196495, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, '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}}
An analytic solution for one-dimensional quantum walks

The first general analytic solutions for the one-dimensional walk in position and momentum space are derived. These solutions reveal, among other things, new symmetry features of quantum walk probability densities and further insight into the behaviour of their moments. The analytic expressions for the quantum walk probability distributions provide a means of modelling quantum phenomena that is analogous to that provided by random walks in the classical domain.


Background
There is a growing body of evidence that quantum walks have a similar role in the modelling of quantum phenomena and the development of algorithms for quantum computation as that of random walks in the classical domain [1][2][3][4][5]. This evidence has been accumulated in part through numerical, moment and limit analysis of the discrete one-dimensional quantum walk.
The existence of a general analytic solution for the discrete quantum walk has been an open question thus far. In this paper, such a solution for the position and momentum space wavefunctions of the discrete one-dimensional quantum walk is derived. In contrast to previous analyses of quantum walks that have also utilised the momentum space our analysis provides elementary closed form solutions for both the momentum and position space. These solutions are powerful tools for analysing the properties of quantum walks as well as providing a capability for modelling quantum phenomena.
Quantum walk models have an interesting and important application with regard to whether human decision and reaction time data manifest quantum effects [6,7]. In this context the linearity of the quantum walk probability distributions, derived in this paper, with respect to their symmetry parameters should enable them to be estimated from experimental data via simple techniques, while the isolation of the temporal evolution parameter enables its estimation via a one-dimensional search.
Previous work that has been motivated by the development of algorithms for quantum computing has sought insight for this by choosing paradigmatic examples of quantum walks, such as the Hadamard walk, and argued that these are typical of quantum walks as a whole [1,3]. The work of this paper in developing simple explicit analytic forms of the general wave functions and hence probability distributions, that are closely connected to the underlying parameters, contrasts to this paradigmatic approach. The results obtained raise questions about how typical the Hadamard walk is of the spectrum of discrete quantum walks.
Hence while it was not the main motivation in seeking these general solutions it is possible that they will provide a better basis for developing quantum algorithms than the approaches used thus far. For example the isolation of the temporal evolution parameter in the walk from the other two symmetry parameters may assist in developing optimisation strategies for lattice searches to locate particular values of a parameter [9] or to determine a satisfactory plan [10].

Structure
In the next section the quantum walk dynamic equations in position space are stated and used to obtain those for the momentum space. Then in section 3 a generalised de Moivre principal is used to derive the momentum-space time-evolution operator in terms of type II Chebyshev polynomials.
Analytic expressions for the momentum space ( ) The key result of section 5 is that the quantum walk probability distributions have the special form of a sum of even and odd functions. These odd functions are multiplied by the two quantum walk parameters, previously referred to as symmetry parameters.
An explicit analytic representation of the position space wave functions is presented in section 6. This makes use of a new type of one-dimensional function whose properties are partially analysed to support the subsequent quantum walk analysis. In section 7 these functions are used to derive analytic expressions for the moments of the walks. In section 8 the results of the moment analysis are used to analyse the walks and provide linkages to other results in the literature. The paper finishes with a summary and the mention of an open area of research.

Quantum Walk Dynamic Equations
For a given we consider the evolution of a quantum state [10,11] The dynamics of the state evolve according to the difference equations , and R k ∈ 0 ψ and 1 ψ are the components of the spinor ψ .
We note that these difference equations define a linear system and hence follow Nayak and Vishwanath in exploiting the spatial homogeneity of the quantum walks by applying the Fourier transform [1] (2) ( We note that with a choice of units so that 1 = and an appropriate normalisation procedure such as requiring periodic boundary conditions then the spinor can be interpreted as a momentum space wave-function for the quantum walk with ] , ( π π − ∈ p [12].
Using this wave function equation 3 can be rewritten as the matrix equation be ae p * * is a unimodular matrix.
By applying the Fourier transform to the initial condition ( ) 0 , x ψ we can obtain the equivalent initial condition in the momentum space We can obtain the momentum space wavefunction at an arbitrary time with this initial condition by iterating equation 5 to give This equation permits the interpretation of as the evolution operator in the momentum space. This 2 by 2 matrix polynomial provides a simpler analytic base than its equivalent the infinite dimensional constant matrix in the position space.

The Evolution Operator
Other authors have analysed the momentum space wave functions using an eigenvalue decomposition of this evolution operator [1,3]. We use an alternate approach that has the advantage of giving the general evolution operator in a simple analytic form and hence general elementary closed forms for the momentum and position space wavefunctions.
The unimodular matrix can be written in an exponential form as where θ and c are real functions of p and the matrix vector σ has Pauli matrix components [13,14] , and This exponential form allows us to can write the powers of ( ) The trigonometric expressions in this equation can be written in terms of the Chebyshev polynomials T and U as [15] n n Substituting these expressions into equation 12 gives This equation can be written in terms of the type II Chebyshev polynomials alone by using the relation where we have used the even property of the cosine function and the odd property of the sine function.
By comparing the expression within the square brackets with equation 10 we see it is equivalent to an exponentiation of the inverse of the one step time evolution matrix and thus write By substituting this expression into equation 9 we obtain the time evolution operator as We can determine the function in terms of the components of S by defining the inner product on the vector space of two by two unitary matrices and hence obtain an inner product space with { } , , , as an ortho-normal basis.
We note that the coefficient of I on the right had side of equation 10 is ( ) ( p ) θ cos and the coefficient of I on the left hand side is where a is the absolute value of a and d its argument, that is Thus using the equality of coefficients and equation 20 we can write the time evolution operator in equation 18 as

Momentum Space
The momentum space wave functions are now easily obtained from equations 8, 9 and 22 as We can write this more explicitly in terms of the spinor components as where the latter terms are derived from the expansion of equation 24 as

Position Space
The inverse Fourier transform of equation 26 gives the position space wave functions as the inverse Fourier transform of the augmented Type II Chebyshev polynomials.
We will show in section 6 that the functions ( ) can be expressed in a simple closed form. At present we note that they are real even functions as they are the inverse Fourier transform of real even functions.
An inspection of equations 29 and 30 leads us to define the function ( ) ( ) ( ) 1 : : : and hence write the position space wavefunctions as (33b) The expressions in equations 29, 30 and 33 show clearly that the detailed temporal dynamics of the quantum walk depend dominantly on the single real parameter a via the functions ( )

Probability Densities
The quantum walk probability densities for each of the spinor components can be written by using equation 33 as Thus it can be seen explicitly that the one dimensional quantum walk is an interferometric system with only three effective real parameters that can be chosen as a , 0 c andδ . We note that By expanding the functions f t 2 and f t we are able to write the quantum walk probability distributions as the sum of an even  , , We note that the sum of even and odd functions is a special form for an asymmetric function. Examples of the even and odd components are plotted in figures 1 and 2.
Thus these are sufficient conditions for a quantum walk to be even.

Moments 1
Since the quantum walk probability densities can be decomposed exactly into the sum of an even and odd component then the even moments of the quantum walk Thus we can write the odd moments as (46)

Calculations
The even probability distribution equation 36a can be simplified to The odd component of the probability distribution for α = 0 is where equation 43 was used.
This is plotted for the Hadamard walk at t = 100 and ν = 1/2 in Figure 2.

Foundation Functions
An analysis of the foundation functions ( ) x a t : u helps develop tools to analyse quantum walks such as algebraic expressions for the moments in terms of the quantum walk parameters. It also helps develop insight into the temporal behaviour of quantum walks.
We start by considering the foundation functions role in building up the various distributions associated with the quantum walks.

Polynomial Expressions for the Foundation Functions
We now proceed to develop polynomial expression for these foundation functions by noting that Type II Chebyshev Polynomials can be as expressed as the power series [15] We note the following properties of the polynomials: They obey the recursion This is derived in appendix A.
The even symmetry of ( x and for the summation in equation (49) truncates at The formulas in equations 60 to 62 give us the polynomials up to 3 = t .
and zero otherwise.
This expression is useful for checking the general expressions for the polynomials and quantities derived from them such as the moments of the quantum walk probability distribution functions.

Moments 2
Analytic expressions for the moments of one-dimensional quantum walks are calculated in the following section by using the foundation polynomials. This allows direct comparison with the moments of experimental data and also connects with the literature on quantum walks that is moment based [1 and 2].

Even Moments
In this subsection expressions for the normalisation and second moment of the quantum walk are calculated using equation 41.

Normalisation
The normalisation requirement is

Second Moment
The equation In concluding this section we note with foresight that the oscillation in time between zero and one of the second moment at 0 = a is consistent with an oscillation of the first moment at this point.

Odd Moments
By substituting from equation 55 into the expression for the odd moments given in equation 46 we obtain an expression for the odd moments in terms of the foundation polynomials

First Moment
Hence the first moment is We can check the expressions obtained from these formulas by using the special case 1 = a and α =0 for which  For small a we note that these walks can be considered to oscillate with time between 0 and -1. The veracity of this statement is born witness to by the small value of the variance for small a see figure 6. These oscillations become more damped with time as a is increased up to a value of about 0.2. For large a the walks increase linearly with time. The intermediate region is characterised by the largest variances as seen in figure 6.

Variance
The variance (Var) of the quantum walk can be evaluated from the expression [16] ( ) The normalised variances

Conclusion
A general analysis of one dimensional quantum walks has been provided that gives new insights into their behaviour and tools for the modelling of experimental data.
In particular it has been shown that it is possible to express the general one dimensional quantum walk, in both the position and momentum space, in terms of simple analytic expressions. These expressions directly show that quantum walks depend on three effective real parameters, two that determine the symmetry of the walks and the third that controls the temporal evolution. The two that affect symmetry appear linearly in the expressions for the probability density of these walks making them easy to estimate from experimental data.
A new type of function was presented and partially analysed in terms of recursions and power series. This function was used to obtain the moments of the quantum walk as algebraic expressions of the walk parameters. These analytic expressions permitted an analysis of the walks that showed that the general second moments converge rapidly with time to a limiting form. They were then used to discuss the limited sense in which the Hadamard walk can be considered to be typical of the general onedimensional quantum walk.
In the light of the strong current interest in quantum computing this analysis raises the open question of what insights for quantum algorithm development can be gleaned from general analytic models.  . (A4)