**abstract:**
Mixing times provide a useful tool for analysis of algorithms based on random walks. The mixing time is a benchmarking quantity which reflects how efficiently algorithms can perform on a given graph. Understanding the details of the mixing processes of quantum walks is thus essential, and can give more insight to understanding the conditions when quantum speedup in algorithms is achievable, particularly when there is noise in the system.

In this talk, we explore mixing processes in quantum walks where the walker is coupled to a finite-size environment (called the bath), and the total evolution of the walker+environment system is unitary. Recent results in quantum thermodynamics show that when a small quantum system is coupled to a large bath, the smaller system thermalizes and evolves towards a stationary state, even under unitary dynamics. In the context of quantum walks, this thermalization behaviour can be understood as a mixing process. When the walker is coupled to a bath, the interactions with the bath drive the walker to the vicinity of the completely mixed state in position space.

The discrete-time model considered here consists of a walker on a circular 1d-lattice of size \(d_S\), and an environment with finite dimension \(d_B\). The unitary time evolution operator couples the walker with the environment, such that they become entangled during the walk. The dynamics of the reduced density matrix for position (denoted \(\rho_S\)) divides into two regimes: during the initial relaxation period, the system approaches the maximally mixed state with an exponential slope. This behaviour continues only until the distance between the maximally mixed state (denoted \(\omega\)) reaches a certain threshold value. In the second period, the position states are restricted to a certain set, such that the distance between \(\rho_S\) and \(\omega\) is almost a constant.

During the initial mixing period, the distance between \(\rho_S\) and \(\omega\) falls off exponentially: \(d(\rho_S,\omega) \propto e^{-t/\tau}\), where the constant \(\tau\) is defined as the mixing time. Numerical results show that the mixing time depends only on the dimensions \(d_S\) and \(d_B\), and not on the details of the coin or the environment. In the limit of large \(d_B\), the mixing time seems to converge to a number which is only dependent on \(d_S\).

In the stabilized regime of the time evolution, we investigate the behaviour of the average distance \(

The above results are for a model where the environment is in a certain sense non-local. We also compare these results to the case where the environment is local.

Fri 15 Nov, 10:00 - 10:30, Sala Stemmi

<< Go back