2022/09/26 by Javad Doliskani, Doliskani, Javad
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata #Quantum and electron transport phenomena
paper · pdf · doi:10.48550/arxiv.2209.13028
We introduce ε-projectors, using which we can sample from limiting distributions of continuous-time quantum walks. The standard algorithm for sampling from a distribution that is close to the limiting distribution of a given quantum walk is to run the quantum walk for a time chosen uniformly at random from a large interval, and measure the resulting quantum state. This approach usually results in an exponential running time. We show that, using ε-projectors, we can sample exactly from the limiting distribution. In the black-box setting, where we only have query access to the adjacency matrix of the graph, our sampling algorithm runs in time proportional to Δ-1, where Δ is the minimum spacing between the distinct eigenvalues of the graph. In the non-black-box setting, we give examples of graphs for which our algorithm runs exponentially faster than the standard sampling algorithm.