Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts. / Mathematics

O passeio aleatório quântico foi totalmente entendido por [3] e desde então muitos esforços foram feitos para compreender casos mais gerais como no passeio aleatório tradicional. Nós introduzimos o caso periódico e discutimos a heurística sendo considerada como uma partícula quântica difundindo em um cristal atômico linear. Assim, estendemos o teorema de Grimmett-Janson- Scudo [3] para este caso que é um método para obter a densidade de probabilidade limite do operador posição dependendo da diagonalização da matriz de evolução unitária e mostramos que o caso periódico é de fato balístico, [9]. Como um exemplo, édiscutida a densidade probabilidade limite de período dois. / The homogeneous quantum random walk was completely understood by [3] and since then many efforts were made to compreehend more general cases like in the tradicional random walk. We introduce the periodic case and discuss a heuristic to be considered as a quantum particle diffusion in a atomic linear crystal. Thus, we extend the theorem of Grimmett-Janson-Scudo [3] to this case which is a method to obtain the limit of the probability density of the position operator depending on the diagonalization of the unitary evolution matrix and show that the periodic case is in fact ballistic, [9]. As an example, it is shown the limit probability density of the period two.

O passeio aleatório quântico foi totalmente entendido por [3] e desde então muitos esforços foram feitos para compreender casos mais gerais como no passeio aleatório tradicional. Nós introduzimos o caso periódico e discutimos a heurística sendo considerada como uma partícula quântica difundindo em um cristal atômico linear. Assim, estendemos o teorema de Grimmett-Janson- Scudo [3] para este caso que é um método para obter a densidade de probabilidade limite do operador posição dependendo da diagonalização da matriz de evolução unitária e mostramos que o caso periódico é de fato balístico, [9]. Como um exemplo, édiscutida a densidade probabilidade limite de período dois. / The homogeneous quantum random walk was completely understood by [3] and since then many efforts were made to compreehend more general cases like in the tradicional random walk. We introduce the periodic case and discuss a heuristic to be considered as a quantum particle diffusion in a atomic linear crystal. Thus, we extend the theorem of Grimmett-Janson-Scudo [3] to this case which is a method to obtain the limit of the probability density of the position operator depending on the diagonalization of the unitary evolution matrix and show that the periodic case is in fact ballistic, [9]. As an example, it is shown the limit probability density of the period two.

O passeio aleatório quântico foi totalmente entendido por [3] e desde então muitos esforços foram feitos para compreender casos mais gerais como no passeio aleatório tradicional. Nós introduzimos o caso periódico e discutimos a heurística sendo considerada como uma partícula quântica difundindo em um cristal atômico linear. Assim, estendemos o teorema de Grimmett-Janson- Scudo [3] para este caso que é um método para obter a densidade de probabilidade limite do operador posição dependendo da diagonalização da matriz de evolução unitária e mostramos que o caso periódico é de fato balístico, [9]. Como um exemplo, édiscutida a densidade probabilidade limite de período dois. / The homogeneous quantum random walk was completely understood by [3] and since then many efforts were made to compreehend more general cases like in the tradicional random walk. We introduce the periodic case and discuss a heuristic to be considered as a quantum particle diffusion in a atomic linear crystal. Thus, we extend the theorem of Grimmett-Janson-Scudo [3] to this case which is a method to obtain the limit of the probability density of the position operator depending on the diagonalization of the unitary evolution matrix and show that the periodic case is in fact ballistic, [9]. As an example, it is shown the limit probability density of the period two.

Random walks describe diffusion processes, where movement at every time step is restricted only to neighbouring locations. Classical random walks are constructed using the non-relativistic Laplacian evolution operator and a coin toss instruction. In quantum theory, an alternative is to use the relativistic Dirac operator. That necessarily introduces an internal degree of freedom (chirality), which may be identified with the coin. The resultant walk spreads quadratically faster than the classical one, and can be applied to a variety of graph theoretical problems. We study in detail the problem of spatial search, i.e. finding a marked site on a hypercubic lattice in d-dimensions. For d=1, the scaling behaviour of classical and quantum spatial search is the same due to the restriction on movement. On the other hand, the restriction on movement hardly matters for d ≥ 3, and scaling behaviour close to Grover’s optimal algorithm(which has no restriction on movement) can be achieved. d=2 is the borderline critical dimension, where infrared divergence in propagation leads to logarithmic slow down that can be minimised using clever chirality flips. In support of these analytic expectations, we present numerical simulation results for d=2 to d=9, using a lattice implementation of the Dirac operator inspired by staggered fermions. We optimise the parameters of the algorithm, and the simulation results demonstrate that the number of binary oracle calls required for d= 2 and d ≥ 3 spatial search problems are O(√NlogN) and O(√N) respectively. Moreover, with increasing d, the results approach the optimal behaviour of Grover’s algorithm(corresponding to mean field theory or d → ∞ limit). In particular, the d = 3 scaling behaviour is only about 25% higher than the optimal value.

No description available.

Ce manuscrit de thèse s’intéresse à l’étude théorique et à l’observation d’effets quantiques résultantde la manipulation de photons en fréquence. Ainsi nous rapportons une expérience d’interférenceà deux photons, pour laquelle l’intrication et la manipulation des photons survient dans le domainedes fréquences. Nous montrons que cette figure d’interférence est sensible à la dispersion des deuxphotons jumeaux et que ce phénomène peut être compensé de manière non-locale. D’un autre coté,nous étudions la réalisation d’une marche aléatoire quantique établie par la modulation de phase.Nous mettons en évidence un comportement intéressant de ces marches et suggérons un schémaexpérimental. / This manuscript deals with a theoretical and experimental study of quantum effects taking place inthe frequency domain. On one side, we report a two photons interference experiment, where both theentanglement of the photons and their manipulation take place in the frequency domain. We showthat this interference pattern is sensitive to the dispersion of both photons and allows us to perform anonlocal dispersion cancellation. On the other side we study the implementation of a quantum walkbased on the phase modulation. We predict an interesting behavior of these quantum walks andsuggest a physical implementation.