Faster Computation with the Generalized Laplacian Quantum Walk

• URL: http://arxiv.org/abs/2609.10429v1
• Date: Wed, 09 Sep 2026 16:41:48 GMT
• Title: Faster Computation with the Generalized Laplacian Quantum Walk
• Abstract summary: We prove that a continuous-time quantum walk effected by a generalized Laplacian can solve a computational problem more quickly than typical quantum walks governed by the standard Laplacian or adjacency matrix.<n>This raises the potential for the generalized Laplacian quantum walk to be a useful method for developing additional faster quantum algorithms.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Practical advantage beyond the quadratic speedup limit with fully-quantum walks [0.12891210250935145]
  We introduce a new class of fully-quantum walks in which both the proposal and acceptance steps are intrinsically quantum.<n>Under identical hardware assumptions, the resulting advantage runtime crossover is reduced from approximately $103$ years for conventional quantum walks to less than one day.
  arXiv  Detail & Related papers  (2026-07-24T18:00:06Z)
• Quantum Algorithms for Computing Maximal Quantum $f$-divergence and Kubo-Ando means [0.0]
  We present quantum algorithms for computing the maximal quantum $f$-divergences and the operator-theoretic matrix Kubo--Ando means.
  arXiv  Detail & Related papers  (2025-11-13T18:43:00Z)
• Quantum Circuits for the Metropolis-Hastings Algorithm [0.0]
  Quantum computers are expected to provide a speedup of Metropolis-Hastings (MH) simulations.<n>We present a quantum walk construction which follows the classical proposal-acceptance logic.<n>We expect the end-to-end quadratic speedup to hold for MH Markov Chain Monte-Carlo simulations.
  arXiv  Detail & Related papers  (2025-06-13T08:31:33Z)
• Exponential quantum speedups in quantum chemistry with linear depth [0.0]
  We prove a connection to particle number conserving matchgate circuits with fermionic magic state inputs.<n>We apply this result to quantum multi-reference methods designed for near-term hardware.<n>We discuss the implications for achieving exponential quantum advantage in quantum chemistry on near-term hardware.
  arXiv  Detail & Related papers  (2025-03-26T23:15:32Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem.<n>We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions.<n>We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Parallel Quantum Computing Simulations via Quantum Accelerator Platform Virtualization [44.99833362998488]
  We present a model for parallelizing simulation of quantum circuit executions. The model can take advantage of its backend-agnostic features, enabling parallel quantum circuit execution over any target backend.
  arXiv  Detail & Related papers  (2024-06-05T17:16:07Z)
• 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)
• Unitary Coined Discrete-Time Quantum Walks on Directed Multigraphs [1.2183405753834557]
  Unitary Coined Discrete-Time Quantum Walks (UC-DTQW) constitute a universal model of quantum computation. Current quantum computers work based on the quantum circuit model of computation.
  arXiv  Detail & Related papers  (2023-04-04T07:19:55Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• Quantum estimation bound of Gaussian matrix permanent [1.7404865362620803]
  Exact calculation and even multiplicative error estimation of matrix permanent are challenging for both classical and quantum computers. Our newly developed formula for matrix permanents and its corresponding quantum expression have enabled better estimation of the average additive error.
  arXiv  Detail & Related papers  (2022-05-03T06:34:04Z)
• Escaping from the Barren Plateau via Gaussian Initializations in Deep Variational Quantum Circuits [63.83649593474856]
  Variational quantum circuits have been widely employed in quantum simulation and quantum machine learning in recent years.<n>However, quantum circuits with random structures have poor trainability due to the exponentially vanishing gradient with respect to the circuit depth and the qubit number.<n>This result leads to a general standpoint that deep quantum circuits would not be feasible for practical tasks.
  arXiv  Detail & Related papers  (2022-03-17T15:06:40Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)

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.