Direct Equivalence between Dynamics of Quantum Walks and Coupled Classical Oscillators

• URL: http://arxiv.org/abs/2512.03681v1
• Date: Wed, 03 Dec 2025 11:20:52 GMT
• Title: Direct Equivalence between Dynamics of Quantum Walks and Coupled Classical Oscillators
• Authors: Lilith Zschetzsche, Refik Mansuroglu, András Molnár, Norbert Schuch,
• Abstract summary: Continuous time quantum walks on exponentially large, sparse graphs form a powerful paradigm for quantum computing.<n>In this work, we establish a direct and transparent mapping between these two classes of problems.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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).

Related papers

• QSearchNet: A Quantum Walk Search Framework for Link Prediction [0.0]
  Link prediction is one of the fundamental problems in graph theory.<n>Quantum computing offers a powerful alternative by leveraging superposition for simultaneous multi-path exploration.<n>QSearchNet simulates a topology-aware quantum evolution to propagate amplitudes across multiple nodes simultaneously.
  arXiv  Detail & Related papers  (2025-09-30T22:32:34Z)
• Ancilla-train quantum algorithm for simulating non-Markovian open quantum systems [0.0]
  We present a quantum algorithm for simulating open quantum systems coupled to Gaussian environments valid for any configuration and coupling strength.<n>We show that the algorithm can reproduce the true dynamics of such problems at arbitrary accuracy and, for a broad range of problems, only adds a minor resource cost relative to Trotterized time evolution.
  arXiv  Detail & Related papers  (2025-09-16T06:18:06Z)
• A hybrid quantum walk model unifying discrete and continuous quantum walks [1.8835490533310801]
  This work introduces a hybrid quantum walk model that integrates the coin mechanism of discrete walks with the Hamiltonian-driven time evolution of continuous walks.<n>The proposed framework demonstrates unifying capabilities by naturally encompassing existing quantum walk models as special cases.
  arXiv  Detail & Related papers  (2025-09-11T07:55:37Z)
• State-Averaged Orbital-Optimized VQE: A quantum algorithm for the democratic description of ground and excited electronic states [0.0]
  The SA-OO-VQE package aims to answer both problems with its hybrid quantum-classical conception based on a typical Variational Quantum Eigensolver approach. The SA-OO-VQE has the ability to treat degenerate (or quasi-degenerate) states on the same footing, thus avoiding known numerical optimization problems around avoided crossings or conical intersections.
  arXiv  Detail & Related papers  (2024-01-22T12:16:37Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
  The anticipated applications of quantum computers span across science and industry.<n>We present a survey of several potential application areas of quantum algorithms.<n>We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Demonstration of algorithmic quantum speedup [0.0]
  An experimental demonstration of a provable algorithmic quantum speedup has remained elusive. We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring. The speedup is observed on only one of the two QCs.
  arXiv  Detail & Related papers  (2022-07-15T17:59:47Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Long-Time Error-Mitigating Simulation of Open Quantum Systems on Near Term Quantum Computers [38.860468003121404]
  We study an open quantum system simulation on quantum hardware, which demonstrates robustness to hardware errors even with deep circuits containing up to two thousand entangling gates. We simulate two systems of electrons coupled to an infinite thermal bath: 1) a system of dissipative free electrons in a driving electric field; and 2) the thermalization of two interacting electrons in a single orbital in a magnetic field -- the Hubbard atom. Our results demonstrate that algorithms for simulating open quantum systems are able to far outperform similarly complex non-dissipative algorithms on noisy hardware.
  arXiv  Detail & Related papers  (2021-08-02T21:36:37Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Quantum Permutation Synchronization [88.4588059792167]
  We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
  arXiv  Detail & Related papers  (2021-01-19T17:51:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.