Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.03681 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915651328671744 |
|---|---|
| author | Zschetzsche, Lilith Mansuroglu, Refik Molnár, András Schuch, Norbert |
| author_facet | Zschetzsche, Lilith Mansuroglu, Refik Molnár, András Schuch, Norbert |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_03681 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Direct Equivalence between Dynamics of Quantum Walks and Coupled Classical Oscillators Zschetzsche, Lilith Mansuroglu, Refik Molnár, András Schuch, Norbert Quantum Physics 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). |
| title | Direct Equivalence between Dynamics of Quantum Walks and Coupled Classical Oscillators |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2512.03681 |