Faster Computation with the Generalized Laplacian Quantum Walk

Abstract

Quantum walks are the quantum analogues of classical random walks or Markov chains. They are universal models of quantum computing, and they underpin a variety of quantum algorithms. We prove that a continuous-time quantum walk effected by a generalized Laplacian, which can arise in spin chains, can solve a computational problem more quickly than typical quantum walks governed by the standard Laplacian or adjacency matrix. This generalized Laplacian consists of the standard Laplacian plus a real-valued multiple of the degree matrix, and we prove that as the magnitude of the multiple of the degree matrix is increased, its corresponding quantum walk can search the complete bipartite graph with multiple marked vertices in time that approaches the optimal. This raises the potential for the generalized Laplacian quantum walk to be a useful method for developing additional faster quantum algorithms.

Walk/Zeta correspondence for quantum walks on path graphs: a pre-geometric structure implied by a generalized reflection principle
Jiro Akahori, Riki Kitano, Norio Konno +1
arXiv4 Oct 2026PreprintarXiv licenceFull textMathematical physics ProbabilityarXiv
Near-Optimal Bounds on the Density of Low-Energy States of k-Local Hamiltonians and Faster Quantum Algorithms
Sevag Gharibian, François Le Gall, Ranitha Mataraarachchi +1
arXiv28 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Stronger Entanglement Dies Faster: Quantum Mpemba Effect in Dissipative Qubits
Zhilong Liu, Zehua Tian, Jieci Wang
arXiv29 Oct 2026PreprintarXiv licenceFull textGravitation & general relativity Quantum physics & quantum informationarXiv
Faster Quantum Monte Carlo Simulation by Random Compilation
John M. Martyn, Joshua Lin, Neill C. Warrington +2
arXiv9 Sep 2026PreprintarXiv licenceFull textCondensed matter High-energy & particle physicsarXiv
Wave-Particle Complementarity in Quantum Walk from a Quantum Mechanical Perspective
Norio Konno, Shigeki Matsutani, Etsuo Segawa +1
arXiv19 Oct 2026PreprintarXiv licenceFull textMathematical physics Quantum physics & quantum informationarXiv

Cite

BibTeX RIS

BibTeX

@misc{duda2026faster,
  title = {{Faster Computation with the Generalized Laplacian Quantum Walk}},
  author = {Jonas Duda and Thomas G. Wong},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.10429},
  eprint = {2609.10429},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.10429},
}

RIS

TY  - UNPB
TI  - Faster Computation with the Generalized Laplacian Quantum Walk
AU  - Jonas Duda
AU  - Thomas G. Wong
PY  - 2026
DA  - 2026/09/09
PB  - arXiv
DO  - 10.48550/arxiv.2609.10429
UR  - https://arxiv.org/abs/2609.10429
AB  - Quantum walks are the quantum analogues of classical random walks or Markov chains. They are universal models of quantum computing, and they underpin a variety of quantum algorithms. We prove that a continuous-time quantum walk effected by a generalized Laplacian, which can arise in spin chains, can solve a computational problem more quickly than typical quantum walks governed by the standard Laplacian or adjacency matrix. This generalized Laplacian consists of the standard Laplacian plus a real-valued multiple of the degree matrix, and we prove that as the magnitude of the multiple of the degree matrix is increased, its corresponding quantum walk can search the complete bipartite graph with multiple marked vertices in time that approaches the optimal. This raises the potential for the generalized Laplacian quantum walk to be a useful method for developing additional faster quantum algorithms.
ER  -

Abstract

Related

Cite