Name
Abstract | ||
|---|---|---|
We present an efficient general method for realizing a quantum walk operator corre-sponding to an arbitrary sparse classical random walk. Our approach is based on Groverand Rudolph's method for preparing coherent versions of efficiently integrable probabil-ity distributions [1]. This method is intended for use in quantum walk algorithms withpolynomial speedups, whose complexity is usually measured in terms of how many timeswe have to apply a step of a quantum walk [2], compared to the number of necessary clas-sical Markov chain steps. We consider a finer notion of complexity including the numberof elementary gates it takes to implement each step of the quantum walk with somedesired accuracy. The difference in complexity for various implementation approaches isthat our method scales linearly in the sparsity parameter and poly-logarithmically withthe inverse of the desired precision. The best previously known general methods eitherscale quadratically in the sparsity parameter, or polynomially in the inverse precision.Our approach is especially relevant for implementing quantum walks corresponding toclassical random walks like those used in the classical algorithms for approximating per-manents [3, 4] and sampling from binary contingency tables [5]. In those algorithms,the sparsity parameter grows with the problem size, while maintaining high precision isrequired. |
Year | Venue | Keywords |
|---|---|---|
2010 | Quantum Information & Computation | efficient circuit,quantum walk operator,sparse classical random walk,quantum walk,inverse precision,efficient general method,corresponding toclassical random walk,sparsity parameter,high precision,method scales linearly,general method,markov chain,random walk,probability distribution,quantum physics,circuit,markov chains,quantum walks,contingency table |
Field | DocType | Volume |
Quantum complexity theory,Discrete mathematics,Quantum mechanics,Quantum sort,Quantum walk,Quantum algorithm,Quantum operation,Quantum capacity,Quantum error correction,Mathematics,Heterogeneous random walk in one dimension | Journal | 10 |
Issue | ISSN | Citations |
5 | Quantum Information and Computation, Vol.10, No.5&6, pp0420-0434
(2010) | 8 |
PageRank | References | Authors |
0.62 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chen-Fu Chiang | 1 | 13 | 2.28 |
| Daniel Nagaj | 2 | 57 | 5.84 |
| Pawel Wocjan | 3 | 136 | 22.21 |