We introduce a family of models for quantum mechanical, one-dimensional random walks, called quantum multibaker maps (QMB). These are Weyl quantizations of the classical multibaker models previously considered by Gaspard, Tasaki, and others. Depending on the properties of the phase's parametrizing the quantization, we consider only two classes of the QMB maps: uniform and random. Uniform QMB maps are characterized by phases that are the same in every unit cell of the multibaker chain. Random QMB maps have phases that vary randomly from unit cell to unit cell. The eigenstates in the former case are extended while in the latter they are localized. In the uniform case and for large variant Planck's over 2pi, analytic solutions can be obtained for the time-dependent quantum states for periodic chains and for open chains with absorbing boundary conditions. Steady state solutions and the properties of the relaxation to a steady state for a uniform QMB chain in contact with "particle" reservoirs can also be described analytically. The analytical results are consistent with, and confirmed by, results obtained from numerical methods. We report here results for the deep quantum regime (large variant Planck's over 2pi ) of the uniform QMB, as well as some results for the random QMB. We leave the moderate and small variant Planck's over 2pi results as well as further consideration of the other versions of the QMB for further publications.
We introduce a family of models for quantum mechanical, one-dimensional random walks, called quantum multibaker maps (QMB). These are Weyl quantizations of the classical multibaker models previously considered by Gaspard, Tasaki, and others. Depending on the properties of the phase's parametrizing the quantization, we consider only two classes of the QMB maps: uniform and random. Uniform QMB maps are characterized by phases that are the same in every unit cell of the multibaker chain. Random QMB maps have phases that vary randomly from unit cell to unit cell. The eigenstates in the former case are extended while in the latter they are localized. In the uniform case and for large variant Planck's over 2pi, analytic solutions can be obtained for the time-dependent quantum states for periodic chains and for open chains with absorbing boundary conditions. Steady state solutions and the properties of the relaxation to a steady state for a uniform QMB chain in contact with "particle" reservoirs can also be described analytically. The analytical results are consistent with, and confirmed by, results obtained from numerical methods. We report here results for the deep quantum regime (large variant Planck's over 2pi ) of the uniform QMB, as well as some results for the random QMB. We leave the moderate and small variant Planck's over 2pi results as well as further consideration of the other versions of the QMB for further publications.
We define and analyze quantum computational variants of \nrandom walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random \nwalk, which we call the Hadamard walk. Several striking \ndifferences between the quantum and classical cases are ob- served. For example, when unrestricted in either direction, \nthe Hadamard walk has position that is nearly uniformly \ndistributed in the range [-t/√2, t/√2] after t steps, which \nis in sharp contrast to the classical random walk, which has \ndistance O(√t) from the origin with high probability. With \nan absorbing boundary immediately to the left of the starting position, the probability that the walk exits to the left is 2/π, and with an additional absorbing boundary at location n, the probability that the walk exits to the left actually increases, approaching 1/√2 in the limit. In the classical case both values are 1.
The quantum walk is a unitary analogue to the discrete random walk, and its properties have been increasingly studied since the turn of the millennium. In comparison with the classical random walk, the quantum walk exhibits linear spreading and initial condition dependent asymmetries. As noted early on in the conjecture and subsequent calculation of absorption probabilities in the one dimensional Hadamard walk, the interaction of the quantum walk with an absorbing boundary is fundamentally divergent from classical case. Here, we will survey absorption probabilities for a more general collection of one dimensional quantum walks and extend the method to consider d-dimensional walks in the presence of d-1 dimensional absorbing walls. However, these results are concerned only with local behavior at the boundary in the form of absorption probabilities. The main results of this thesis are concerned with the global behavior of finite quantum walks, which can be described by linear spreading in the short term, modal phenomena in the mid term, and stable distributions in the exceedingly long term. These theorems will be rigorously proved in the one-dimensional case and extrapolated to higher dimensional quantum walks. To this end we introduce QWSim, a new and robust computational engine for displaying finite two dimensional quantum walks.
We show that particle transport, as characterized by the equilibrium mean square displacement, in a uniform, quantum multibaker map, is generically ballistic in the long time limit, for any fixed value of Planck's constant. However, for fixed times, the semiclassical limit leads to diffusion. Random matrix theory provides explicit analytical predictions for the mean square displacement of a particle in the system. These results exhibit a crossover from diffusive to ballistic motion, with crossover time on the order of the inverse of Planck's constant. We expect that, for a large class of 1D quantum random walks similar to the quantum multibaker, a sufficient condition for diffusion in the semiclassical limit is classically chaotic dynamics in each cell. The systems described generalize known quantum random walks and may have applications for quantum computation.
A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.
The study of dissipation and decoherence in generic open quantum systems recently led to the investigation of spectral and steady-state properties of random Lindbladian dynamics. A natural question is then how realistic and universal those properties are. Here, we address these issues by considering a different description of dissipative quantum systems, namely, the discrete-time Kraus map representation of completely positive quantum dynamics. Through random matrix theory (RMT) techniques and numerical exact diagonalization, we study random Kraus maps, allowing for a varying dissipation strength, and their local circuit counterpart. We find the spectrum of the random Kraus map to be either an annulus or a disk inside the unit circle in the complex plane, with a transition between the two cases taking place at a critical value of dissipation strength. The eigenvalue distribution and the spectral transition are well described by a simplified RMT model that we can solve exactly in the thermodynamic limit, by means of non-Hermitian RMT and quaternionic free probability. The steady state, on the contrary, is not affected by the spectral transition. It has, however, a perturbative crossover regime at small dissipation, inside which the steady state is characterized by uncorrelated eigenvalues. At large dissipation (or for any dissipation for a large-enough system), the steady state is well described by a random Wishart matrix. The steady-state properties thus coincide with those already observed for random Lindbladian dynamics, indicating their universality. Quite remarkably, the statistical properties of the local Kraus circuit are qualitatively the same as those of the nonlocal Kraus map, indicating that the latter, which is more tractable, already captures the realistic and universal physical properties of generic open quantum systems.