Quantum Walk Search on the Complete Bipartite Graph
arXiv:1812.06079 · doi:10.1103/PhysRevA.99.032301
Abstract
The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of vertices for one of marked vertices with different initial states. We prove intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one timestep to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches 1/2, but if they are in different partite sets, it instead reaches . This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is 8/9. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schrödinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.
arXiv comment13 pages, 7 figures
References in corpus (16)
- A Quantum Random Walk Search Algorithm
- Spatial search by quantum walk
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- From quantum cellular automata to quantum lattice gases
- Realization of quantum walks with negligible decoherence in waveguide lattices
- Universal quantum computation using the discrete time quantum walk
- Quantum walk of a trapped ion in phase space
- Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
- On the absence of homogeneous scalar unitary cellular automata
- Grover Search with Lackadaisical Quantum Walks
- Global Symmetry is Unnecessary for Fast Quantum Search
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
- Quantum searches on highly symmetric graphs
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Coined Quantum Walks on Weighted Graphs
- Doubling the Success of Quantum Walk Search Using Internal-State Measurements
Cited by in corpus (14)
- On the optimality of spatial search by continuous-time quantum walk
- Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
- Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
- Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- Lackadaisical quantum walk in the hypercube to search for multiple marked vertices
- Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
- Multiple-scale integro-differential perturbation method for generic non-Markovian environments
- Search by Lackadaisical Quantum Walk with Symmetry Breaking
- Quantum walk-based protocol for secure communication between any two directly connected nodes on a network
- Quantum Algorithm for Testing Graph Completeness
- Quantum Search with the Signless Laplacian
- Generalized quantum teleportation of shared quantum secret with quantum walks
- Quantum spatial best-arm identification via quantum walks
- Key graph properties affecting transport efficiency of flip-flop Grover percolated quantum walks