Search results for "Quantum walk"
showing 10 items of 70 documents
Quantum Walk Search with Time-Reversal Symmetry Breaking
2015
We formulate Grover's unstructured search algorithm as a chiral quantum walk, where transitioning in one direction has a phase conjugate to transitioning in the opposite direction. For small phases, this breaking of time-reversal symmetry is too small to significantly affect the evolution: the system still approximately evolves in its ground and first excited states, rotating to the marked vertex in time $\pi \sqrt{N} / 2$. Increasing the phase does not change the runtime, but rather changes the support for the 2D subspace, so the system evolves in its first and second excited states, or its second and third excited states, and so forth. Apart from the critical phases corresponding to these…
Grover Search with Lackadaisical Quantum Walks
2015
The lazy random walk, where the walker has some probability of staying put, is a useful tool in classical algorithms. We propose a quantum analogue, the lackadaisical quantum walk, where each vertex is given $l$ self-loops, and we investigate its effects on Grover's algorithm when formulated as search for a marked vertex on the complete graph of $N$ vertices. For the discrete-time quantum walk using the phase flip coin, adding a self-loop to each vertex boosts the success probability from 1/2 to 1. Additional self-loops, however, decrease the success probability. Using instead the Ambainis, Kempe, and Rivosh (2005) coin, adding self-loops simply slows down the search. These coins also diffe…
Doubling the success of quantum walk search using internal-state measurements
2015
In typical discrete-time quantum walk algorithms, one measures the position of the walker while ignoring its internal spin/coin state. Rather than neglecting the information in this internal state, we show that additionally measuring it doubles the success probability of many quantum spatial search algorithms. For example, this allows Grover's unstructured search problem to be solved with certainty, rather than with probability 1/2 if only the walker's position is measured, so the additional measurement yields a search algorithm that is twice as fast as without it, on average. Thus the internal state of discrete-time quantum walks holds valuable information that can be utilized to improve a…
Quantum Walk Search through Potential Barriers
2015
An ideal quantum walk transitions from one vertex to another with perfect fidelity, but in physical systems, the particle may be hindered by potential energy barriers. Then the particle has some amplitude of tunneling through the barriers, and some amplitude of staying put. We investigate the algorithmic consequence of such barriers for the quantum walk formulation of Grover's algorithm. We prove that the failure amplitude must scale as $O(1/\sqrt{N})$ for search to retain its quantum $O(\sqrt{N})$ runtime; otherwise, it searches in classical $O(N)$ time. Thus searching larger "databases" requires increasingly reliable hop operations or error correction. This condition holds for both discre…
Quantum Walk Search on Johnson Graphs
2016
The Johnson graph $J(n,k)$ is defined by $n$ symbols, where vertices are $k$-element subsets of the symbols, and vertices are adjacent if they differ in exactly one symbol. In particular, $J(n,1)$ is the complete graph $K_n$, and $J(n,2)$ is the strongly regular triangular graph $T_n$, both of which are known to support fast spatial search by continuous-time quantum walk. In this paper, we prove that $J(n,3)$, which is the $n$-tetrahedral graph, also supports fast search. In the process, we show that a change of basis is needed for degenerate perturbation theory to accurately describe the dynamics. This method can also be applied to general Johnson graphs $J(n,k)$ with fixed $k$.
Quantum simulation of quantum relativistic diffusion via quantum walks
2019
Two models are first presented, of one-dimensional discrete-time quantum walk (DTQW) with temporal noise on the internal degree of freedom (i.e., the coin): (i) a model with both a coin-flip and a phase-flip channel, and (ii) a model with random coin unitaries. It is then shown that both these models admit a common limit in the spacetime continuum, namely, a Lindblad equation with Dirac-fermion Hamiltonian part and, as Lindblad jumps, a chirality flip and a chirality-dependent phase flip, which are two of the three standard error channels for a two-level quantum system. This, as one may call it, Dirac Lindblad equation, provides a model of quantum relativistic spatial diffusion, which is ev…
Trapping of Continuous-Time Quantum walks on Erdos-Renyi graphs
2011
We consider the coherent exciton transport, modeled by continuous-time quantum walks, on Erd\"{o}s-R\'{e}ny graphs in the presence of a random distribution of traps. The role of trap concentration and of the substrate dilution is deepened showing that, at long times and for intermediate degree of dilution, the survival probability typically decays exponentially with a (average) decay rate which depends non monotonically on the graph connectivity; when the degree of dilution is either very low or very high, stationary states, not affected by traps, get more likely giving rise to a survival probability decaying to a finite value. Both these features constitute a qualitative difference with re…
A study of Wigner functions for discrete-time quantum walks
2013
We perform a systematic study of the discrete time Quantum Walk on one dimension using Wigner functions, which are generalized to include the chirality (or coin) degree of freedom. In particular, we analyze the evolution of the negative volume in phase space, as a function of time, for different initial states. This negativity can be used to quantify the degree of departure of the system from a classical state. We also relate this quantity to the entanglement between the coin and walker subspaces.
Experimental Engineering of Arbitrary Qudit States with Discrete-Time Quantum Walks
2019
The capability to generate and manipulate quantum states in high-dimensional Hilbert spaces is a crucial step for the development of quantum technologies, from quantum communication to quantum computation. One-dimensional quantum walk dynamics represents a valid tool in the task of engineering arbitrary quantum states. Here we affirm such potential in a linear-optics platform that realizes discrete-time quantum walks in the orbital angular momentum degree of freedom of photons. Different classes of relevant qudit states in a six-dimensional space are prepared and measured, confirming the feasibility of the protocol. Our results represent a further investigation of quantum walk dynamics in p…
Quantum walks: background geometry and gauge invariance
2019
Ciertos tipos de problemas no pueden resolverse usando los actuales ordenadores clásicos. Una forma de encontrar una solución, es mediante el uso de ordenadores cuánticos. Sin embargo, construir un ordenador cuántico es realmente complicado actualmente, debido a las limitaciones tecnológicas. Mientras tanto, los simuladores cuánticos han sido capaces de resolver algunos de estos problemas, ya que los simuladores cuánticos son más accesibles experimentalmente. Las llamadas caminatas cuánticas, en su versión discreta, son una herramienta muy útil para simular ciertos sistemas físicos. En el límite al continuo, se puede obtener una serie de ecuaciones diferenciales, particularmente, la ecuació…