Quantum Dynamics Based on Discrete Time Quantum Walks II

Albert T. Schmitz, William A. Schwalm

Yutaka Shikano

One-dimensional discrete-time quantum walks (DTQWs) can simulate various quantum and classical dynamics and have already been implemented in several physical systems. This implementation needs a well-controlled quantum dynamical system, which is the same requirement for implementing quantum information processing tasks. Here, we consider how to realize DTQWs by Dirac particles toward a solid-state implementation of DTQWs.

Ivan Bardet

Gianpaolo Torre

Mathieu Roget

Quantum computing is a new field of computer science that leverage the quan-tum properties of atomic and subatomic particles for solving computational tasks.However, quantum computing provides very little intuition on how it works. Thismakes the identification of computational tasks with a potential quantum speedupand the elaboration of quantum algorithms for said tasks very difficult. In this context,this thesis focuses on a quantum dynamical system called Discrete Time QuantumWalk (DTQW). DTQWs are dynamical systems with discrete time and space whichare inspired from random walks. This thesis focuses on the problem of searchingan element in an unstructured database. It is known in the literature that searchingpan element with a DTQW on a grid has a quasi-square-root (i.e. O( n poly-log n))complexity in the dataset size n. This provides a significant quantum speedup overthe linear complexity of classical brute-force or random walk based algorithms. A firstcontribution of this thesis shows that, when two elements are searched, the worst casecomplexity becomes quasi-linear while the average case complexity remains quasi-square-root. Moving on from grids to arbitrary topologies, a second contributionintroduces a new model of DTQW onto the edges of an arbitrary graph. This modelunique features are: (i) the position which is on the edges; (ii) a polarity on each edgethat generalizes the notion of right and left we have on a line. A third contributionintroduces a model of quantum distributed computing and shows how this model onan arbitrary graph can reproduce the dynamic of a DTQW on the same graph.

Yutaka Shikano

The discrete time quantum walk defined as a quantum-mechanical analogue of the discrete time random walk have recently been attracted from various and interdisciplinary fields. In this review, the weak limit theorem, that is, the asymptotic behavior, of the one-dimensional discrete time quantum walk is analytically shown. From the limit distribution of the discrete time quantum walk, the discrete time quantum walk can be taken as the quantum dynamical simulator of some physical systems.