@article { tarrataca13, abstract = {Graph search represents a cornerstone in computer science and is em- ployed when the best algorithmic solution to a problem consists in performing an analysis of a search space representing computational possibilities. Typically, in such problems it is crucial to determine the sequence of transitions performed that led to certain states. In this work we discuss how to adapt generic quantum search procedures, namely quantum random walks and Grover’s algorithm, in order to obtain computational paths. We then compare these approaches in the context of tree graphs. In addition we demonstrate that in a best-case scenario both approaches differ, performance-wise, by a constant factor speedup of two, whilst still providing a quadratic speedup relatively to their classical equivalents. We discuss the different scenarios that are better suited for each approach.}, journal = {Quantum Information Processing}, keywords = {Quantum computational paths; Quantum random walks; Quantum search; 68Q05; 68Q12; 81P40;Miscellaneous;}, number = {2}, pages = {1365-1378}, title = {Intricacies of quantum computational paths}, volume = {12}, year = {2013}, author = {Luis Tarrataca and Andreas Wichert} }

hide this content