Dresden 2026 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
QI: Fachverband Quanteninformation
QI 1: Quantum Computing and Algorithms I
QI 1.2: Talk
Monday, March 9, 2026, 09:45–10:00, BEY/0137
Equivalence of Quantum Walk and Coupled Classical Oscillator Simulation — •Lilith Zschetzsche1, Refik Mansuroglu1, András Molnár1,2, and Norbert Schuch1,2 — 1University of Vienna, Faculty of Physics, Boltzmanngasse 5, 1090 Wien, Austria — 2University of Vienna, Faculty of Mathematics, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria
We present direct and physically well-motivated reductions between the simulation of quantum walk Hamiltonians and the simulation of exponentially many coupled classical oscillators, problems that are known to be BQP-complete. Mapping the complex amplitudes of the quantum walk to the displacements and conjugate momenta of the classical oscillators allows us to identify the equations of motions of the quantum walk with those of the harmonic oscillators. That is, we construct a classical Hamiltonian of harmonic oscillators from a quantum walk Hamiltonian (and vice versa), such that energy terms for oscillators and vertex populations of the quantum walk are identified as measurement outcomes on the time-evolved state. Given the BQP-completeness of one of those problems, our reduction can be seen as an alternative proof for BQP-hardness of the other, although the reduction reaches beyond BQP-complete versions of the problem.
Keywords: Quantum Simulation; Complexity Theory; Coupled Classical Oscillators; Quantum Walk; Quantum Computation