6533b861fe1ef96bd12c58f8

RESEARCH PRODUCT

Correcting for Potential Barriers in Quantum Walk Search

Thomas G. WongAndris Ambainis

subject

Nuclear and High Energy PhysicsQuantum PhysicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESComplete graphGeneral Physics and AstronomyFOS: Physical sciencesTheoryofComputation_GENERALStatistical and Nonlinear PhysicsOracleTheoretical Computer ScienceVertex (geometry)CombinatoricsAmplitudeComputational Theory and MathematicsAmplitude amplificationTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYGrover's algorithmQuantum algorithmQuantum walkQuantum Physics (quant-ph)Mathematical PhysicsMathematicsMathematicsofComputing_DISCRETEMATHEMATICS

description

A randomly walking quantum particle searches in Grover's $\Theta(\sqrt{N})$ iterations for a marked vertex on the complete graph of $N$ vertices by repeatedly querying an oracle that flips the amplitude at the marked vertex, scattering by a "coin" flip, and hopping. Physically, however, potential energy barriers can hinder the hop and cause the search to fail, even when the amplitude of not hopping decreases with $N$. We correct for these errors by interpreting the quantum walk search as an amplitude amplification algorithm and modifying the phases applied by the coin flip and oracle such that the amplification recovers the $\Theta(\sqrt{N})$ runtime.

yearjournalcountryeditionlanguage
2015-05-08
http://arxiv.org/abs/1505.02035