2019/07/09 by Jeremy Cook, Cook, Jeremy
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1907.11368
arxiv created 2019/10/06 · arxiv updated 2019/10/08
Quantum walk algorithms can speed up search of physical regions of space in both the discrete-time [arXiv:quant-ph/0402107] and continuous-time setting [arXiv:quant-ph/0306054], where the physical region of space being searched is modeled as a connected graph. In such a model, Aaronson and Ambainis [arXiv:quant-ph/0303041] provide three different criteria for a unitary matrix to act locally with respect to a graph, called Z-local, C-local, and H-local unitaries, and left the open question of relating these three locality criteria. Using a correspondence between continuous- and discrete-time quantum walks by Childs [arXiv:0810.0312], we provide a way to approximate N× N H-local unitaries with error δ using O(1/√δ,√(N)) C-local unitaries, where the comma denotes the maximum of the two terms.