Quantum walks, the discrete wave equation and Chebyshev polynomials
- URL: http://arxiv.org/abs/2402.07809v1
- Date: Mon, 12 Feb 2024 17:15:19 GMT
- Title: Quantum walks, the discrete wave equation and Chebyshev polynomials
- Authors: Simon Apers and Laurent Miclo
- Abstract summary: A quantum walk is the quantum analogue of a random walk.
We show that quantum walks can speed up the spreading or mixing rate of random walks on graphs.
- Score: 1.0878040851638
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A quantum walk is the quantum analogue of a random walk. While it is
relatively well understood how quantum walks can speed up random walk hitting
times, it is a long-standing open question to what extent quantum walks can
speed up the spreading or mixing rate of random walks on graphs. In this
expository paper, inspired by a blog post by Terence Tao, we describe a
particular perspective on this question that derives quantum walks from the
discrete wave equation on graphs. This yields a description of the quantum walk
dynamics as simply applying a Chebyshev polynomial to the random walk
transition matrix. This perspective decouples the problem from its quantum
origin, and highlights connections to earlier (non-quantum) work and the use of
Chebyshev polynomials in random walk theory as in the Varopoulos-Carne bound.
We illustrate the approach by proving a weak limit of the quantum walk dynamics
on the lattice. This gives a different proof of the quadratically improved
spreading behavior of quantum walks on lattices.
Related papers
- Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
In this paper, we give a short proof of the optimal linear hitting time for a welded tree problem by a discrete-time quantum walk.
The same technique can be applied to other 1-dimensional hierarchical graphs.
arXiv Detail & Related papers (2024-04-30T11:45:49Z) - Phase transition of a continuous-time quantum walk on the half line [0.0]
Quantum walks are referred to as quantum analogs to random walks in mathematics.
We study a continuous-time quantum walk on the half line and challenge to find a limit theorem for it in this paper.
arXiv Detail & Related papers (2024-03-20T13:21:29Z) - Polyander visualization of quantum walks [0.0]
We investigate quantum walks which play an important role in the modelling of many phenomena.
The detailed and thorough description is given to the discrete quantum walks on a line, where the total quantum state consists of quantum states of the walker and the coin.
arXiv Detail & Related papers (2023-11-01T10:01:08Z) - A family of quantum walks on a finite graph corresponding to the
generalized weighted zeta function [0.0]
The result enables us to obtain the characteristic of the transition matrix of the quantum walk.
We treat finite graphs allowing multi-edges and multi-loops.
arXiv Detail & Related papers (2022-11-02T06:08:41Z) - Quantum walks on random lattices: Diffusion, localization and the
absence of parametric quantum speed-up [0.0]
We study propagation of quantum walks on percolation-generated two-dimensional random lattices.
We show that even arbitrarily weak concentrations of randomly removed lattice sites give rise to a complete breakdown of the superdiffusive quantum speed-up.
The fragility of quantum speed-up implies dramatic limitations for quantum information applications of quantum walks on random geometries and graphs.
arXiv Detail & Related papers (2022-10-11T10:07:52Z) - Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware.
We present an algorithm that compresses the Trotter steps into a single block of quantum gates.
This results in a fixed depth time evolution for certain classes of Hamiltonians.
arXiv Detail & Related papers (2021-08-06T19:38:01Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems.
We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z) - The Time-Evolution of States in Quantum Mechanics [77.34726150561087]
It is argued that the Schr"odinger equation does not yield a correct description of the quantum-mechanical time evolution of states of isolated (open) systems featuring events.
A precise general law for the time evolution of states replacing the Schr"odinger equation is formulated within the so-called ETH-Approach to Quantum Mechanics.
arXiv Detail & Related papers (2021-01-04T16:09:10Z) - Quantum walk processes in quantum devices [55.41644538483948]
We study how to represent quantum walk on a graph as a quantum circuit.
Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
arXiv Detail & Related papers (2020-12-28T18:04:16Z) - Projection Theorem for Discrete-Time Quantum Walks [0.0]
We make and generalize the observation that summing of probability amplitudes of a discrete-time quantum walk over partitions of the walking graph consistent with the step operator results in a unitary evolution on the reduced graph which is also a quantum walk.
We show that this is is the case for a lazy quantum walk, a walk with large coherent jumps and a walk on a circle with a twisted boundary condition.
arXiv Detail & Related papers (2020-04-03T01:51:55Z) - Jumptime unraveling of Markovian open quantum systems [68.8204255655161]
We introduce jumptime unraveling as a distinct description of open quantum systems.
quantum jump trajectories emerge, physically, from continuous quantum measurements.
We demonstrate that quantum trajectories can also be ensemble-averaged at specific jump counts.
arXiv Detail & Related papers (2020-01-24T09:35:32Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.