Quantum Walks can Unitarily Represent Random Walks on Finite Graphs

• URL: http://arxiv.org/abs/2103.06463v2
• Date: Mon, 12 Jun 2023 09:36:00 GMT
• Title: Quantum Walks can Unitarily Represent Random Walks on Finite Graphs
• Authors: Matheus G. Andrade, Franklin de Lima Marquezino, Daniel R. Figueiredo
• Abstract summary: This paper describes a quantum walk that matches a random walk without measurements at all time steps. It covers both homogeneous and non-homogeneous random walks. Results shed light on the power of quantum walks to generate samples for arbitrary probability distributions.
• Score: 0.8164433158925593
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum and random walks have been shown to be equivalent in the following sense: a time-dependent random walk can be constructed such that its vertex distribution at all time instants is identical to the vertex distribution of any discrete-time coined quantum walk on a finite graph. This equivalence establishes a deep connection between the two processes, far stronger than simply considering quantum walks as quantum analogues of classical random walks. The present work strengthens this connection by providing a construction that establishes this equivalence in the reverse direction: a unitary time-dependent quantum walk can be constructed such that its vertex distribution is identical to the vertex distribution of any random walk on a finite graph at all time instants. The construction shown here describes a quantum walk that matches a random walk without measurements at all time steps (an otherwise trivial statement): measurement is performed in a quantum walk that evolved unitarily until a given time $t$ such that its vertex distribution is identical to the random walk at time $t$. The construction procedure is general, covering both homogeneous and non-homogeneous random walks. For homogeneous random walks, unitary evolution implies time dependency for the quantum walk, since homogeneous quantum walks do not converge under arbitrary initial conditions, while a broad class of random walks does. Thus, the absence of convergence demonstrated for quantum walks in its debut comes from both time-homogeneity and unitarity, rather than unitarity alone, and our results shed light on the power of quantum walks to generate samples for arbitrary probability distributions. Finally, the construction here proposed is used to simulate quantum walks that match uniform random walks on the cycle and the torus.

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)
• Quantum walks, the discrete wave equation and Chebyshev polynomials [1.0878040851638]
  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.
  arXiv  Detail & Related papers  (2024-02-12T17:15:19Z)
• Non-uniform Mixing of Quantum Walks on the Symmetric Group [0.0]
  We analyze the spectra of the Szegedy walk operators using the representation theory of the symmetric group. Our techniques are general, and we believe they can be applied to derive similar analytical results for other non-commutative groups.
  arXiv  Detail & Related papers  (2023-11-06T03:17:36Z)
• Normal quantum channels and Markovian correlated two-qubit quantum errors [77.34726150561087]
  We study general normally'' distributed random unitary transformations. On the one hand, a normal distribution induces a unital quantum channel. On the other hand, the diffusive random walk defines a unital quantum process.
  arXiv  Detail & Related papers  (2023-07-25T15:33:28Z)
• Measurement phase transitions in the no-click limit as quantum phase transitions of a non-hermitean vacuum [77.34726150561087]
  We study phase transitions occurring in the stationary state of the dynamics of integrable many-body non-Hermitian Hamiltonians. We observe that the entanglement phase transitions occurring in the stationary state have the same nature as that occurring in the vacuum of the non-hermitian Hamiltonian.
  arXiv  Detail & Related papers  (2023-01-18T09:26:02Z)
• Geometric phases along quantum trajectories [58.720142291102135]
  We study the distribution function of geometric phases in monitored quantum systems. For the single trajectory exhibiting no quantum jumps, a topological transition in the phase acquired after a cycle. For the same parameters, the density matrix does not show any interference.
  arXiv  Detail & Related papers  (2023-01-10T22:05:18Z)
• Time-inhomogeneous Quantum Walks with Decoherence on Discrete Infinite Spaces [0.2538209532048866]
  Recently, a unified time-inhomogeneous coin-turning random walk with rescaled limiting distributions, Bernoulli, uniform, arcsine and semicircle laws as parameter varies have been obtained. We obtained a representation theorem for time-inhomogeneous quantum walk on discrete infinite state space. The convergence of the distributions of the decoherent quantum walks are numerically estimated.
  arXiv  Detail & Related papers  (2021-04-19T07:50:52Z)
• 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)
• Analysis of Lackadaisical Quantum Walks [0.0]
  The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each. We analytically prove that lackadaisical quantum walks can find a unique marked. vertebrae on any regular locally arc-transitive graph with constant success probability. quadratically faster than the hitting time.
  arXiv  Detail & Related papers  (2020-02-26T00:40:25Z)
• 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)
• Projection evolution and quantum spacetime [68.8204255655161]
  We discuss the problem of time in quantum mechanics. An idea of construction of a quantum spacetime as a special set of the allowed states is presented. An example of a structureless quantum Minkowski-like spacetime is also considered.
  arXiv  Detail & Related papers  (2019-10-24T14:54:11Z)

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.