Direct Equivalence between Dynamics of Quantum Walks and Coupled Classical Oscillators
Authors
Lilith Zschetzsche, Refik Mansuroglu, András Molnár, Norbert Schuch
Categories
Abstract
Continuous time quantum walks on exponentially large, sparse graphs form a powerful paradigm for quantum computing: On the one hand, they can be efficiently simulated on a quantum computer. On the other hand, they are themselves BQP-complete, providing an alternative framework for thinking about quantum computing -- a perspective which has indeed led to a number of novel algorithms and oracle problems. Recently, simulating the dynamics of a system of harmonic oscillators (that is, masses and springs) was set forth as another BQP-complete problem defined on exponentially large, sparse graphs. In this work, we establish a direct and transparent mapping between these two classes of problems. As compared to linking the two classes of problems via their BQP-completeness, our mapping has several desirable features: It is transparent, in that it respects the structure of the problem, including the geometry of the underlying graph, initialization, read-out, and efficient oracle access, resulting in low overhead in terms of both space and time; it allows to map also between restricted subsets of instances of both problems which are not BQP-complete; it provides a recipe to directly translate any quantum algorithm designed in the quantum walk paradigm to harmonic oscillators (and vice versa); and finally, it provides an alternative, transparent way to prove BQP-completeness of the harmonic oscillator problem by mapping it to BQP-completeness construction for the quantum walk problem (or vice versa).
Direct Equivalence between Dynamics of Quantum Walks and Coupled Classical Oscillators
Categories
Abstract
Continuous time quantum walks on exponentially large, sparse graphs form a powerful paradigm for quantum computing: On the one hand, they can be efficiently simulated on a quantum computer. On the other hand, they are themselves BQP-complete, providing an alternative framework for thinking about quantum computing -- a perspective which has indeed led to a number of novel algorithms and oracle problems. Recently, simulating the dynamics of a system of harmonic oscillators (that is, masses and springs) was set forth as another BQP-complete problem defined on exponentially large, sparse graphs. In this work, we establish a direct and transparent mapping between these two classes of problems. As compared to linking the two classes of problems via their BQP-completeness, our mapping has several desirable features: It is transparent, in that it respects the structure of the problem, including the geometry of the underlying graph, initialization, read-out, and efficient oracle access, resulting in low overhead in terms of both space and time; it allows to map also between restricted subsets of instances of both problems which are not BQP-complete; it provides a recipe to directly translate any quantum algorithm designed in the quantum walk paradigm to harmonic oscillators (and vice versa); and finally, it provides an alternative, transparent way to prove BQP-completeness of the harmonic oscillator problem by mapping it to BQP-completeness construction for the quantum walk problem (or vice versa).
Authors
Lilith Zschetzsche, Refik Mansuroglu, András Molnár et al. (+1 more)
Click to preview the PDF directly in your browser