Practical advantage beyond the quadratic speedup limit with fully-quantum walks

• URL: http://arxiv.org/abs/2607.22818v1
• Date: Fri, 24 Jul 2026 18:00:06 GMT
• Title: Practical advantage beyond the quadratic speedup limit with fully-quantum walks
• Abstract summary: 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.
• Score: 0.12891210250935145
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a new class of fully-quantum Metropolis walks in which both the proposal and acceptance steps are intrinsically quantum. Unlike standard quantum walks obtained by quantizing classically efficient Markov chains, our algorithm employs Hamiltonian simulation as a quantum-native proposal mechanism, enlarging the class of quantum walks beyond classical counterparts. We target the problem of sampling from the low-temperature Gibbs distribution of classical dense Ising models, within a fixed error in total variation distance. This approach achieves about a cubic polynomial asymptotic advantage over previous quantum-walks, resulting in a total sixth-degree polynomial queries speedup compared to the best classical walk. This shows that speedups beyond the widely assumed quadratic limit are possible within the quantum walk formalism. We perform a complete fault-tolerant compilation of all algorithmic primitives and benchmark against CPU, GPU, and FPGA implementations of the best classical Markov chain. Under identical hardware assumptions, the resulting advantage runtime crossover is reduced from approximately $10^3$ years for conventional quantum walks to less than one day. These results identify fully-quantum Markov chains as a promising route toward practical quantum advantage.

Related papers

• Faster Computation with the Generalized Laplacian Quantum Walk [0.0]
  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.
  arXiv  Detail & Related papers  (2026-09-09T16:41:48Z)
• Latent-Conditioned Parameterized Quantum Circuits as Universal Approximators for Distributions over Quantum States [0.0]
  We introduce latent-conditioned parameterized quantum circuits (LPQCs)<n>We prove that LPQCs are universal approximators for probability measures over density operators in the $1$-Wasserstein distance.<n> Numerical experiments validate the framework on a synthetic multi-cluster ensemble of mixed quantum states and on a QM9-derived ensemble of 3-D molecular structures.
  arXiv  Detail & Related papers  (2026-05-27T16:19:10Z)
• Automatic De-Quantization of Quantum Programs Using Constant Propagation [42.89658025409898]
  Every quantum operation is costly, making it crucial to minimize quantum resource usage in near-term algorithms.<n>In this work, we focus on de-quantizing quantum operations to classical computation whenever possible.<n>We formalize a hybrid state model for quantum-classical constant propagation, implement our optimizations in the open-source MQT Core tool, and evaluate them on benchmark circuits.
  arXiv  Detail & Related papers  (2026-05-21T19:21:11Z)
• 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)
• Correcting and extending Trotterized quantum many-body dynamics [0.0]
  We develop a hybrid ansatz that combines the strengths of quantum and classical methods.<n>We show how this hybrid ansatz can avoid SWAP gates in the quantum circuit.<n>We also show how it can extend the system size while keeping the number of qubits on the quantum device constant.
  arXiv  Detail & Related papers  (2025-02-19T14:50:12Z)
• 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)
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics [42.29248343585333]
  We benchmark quantum hardware and error mitigation techniques on up to 133 qubits. We show reliable control up to a two-qubit gate depth of 28, featuring a maximum of 1396 two-qubit gates. Results are transferable to applications such as Hamiltonian simulation, variational algorithms, optimization, or quantum machine learning.
  arXiv  Detail & Related papers  (2024-04-11T18:00:05Z)
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity [50.387179833629254]
  We introduce a collaborative classical-quantum architecture called co-TenQu. Co-TenQu enhances a classical deep neural network by up to 41.72% in a fair setting. It outperforms other quantum-based methods by up to 1.9 times and achieves similar accuracy while utilizing 70.59% fewer qubits.
  arXiv  Detail & Related papers  (2024-02-23T14:09:41Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Quantum-classical distance as a tool to design optimal chiral quantum walk [0.0]
  Continuous-time quantum walks (CTQWs) provide a valuable model for quantum transport, universal quantum computation and quantum spatial search. We argue that the quantum-classical distance, a figure of merit introduced to capture the difference in dynamics between a CTQW and its classical counterpart, guides the optimization of parameters of the Hamiltonian.
  arXiv  Detail & Related papers  (2021-06-22T11:38:58Z)
• Preparing random states and benchmarking with many-body quantum chaos [48.044162981804526]
  We show how to predict and experimentally observe the emergence of random state ensembles naturally under time-independent Hamiltonian dynamics. The observed random ensembles emerge from projective measurements and are intimately linked to universal correlations built up between subsystems of a larger quantum system. Our work has implications for understanding randomness in quantum dynamics, and enables applications of this concept in a wider context.
  arXiv  Detail & Related papers  (2021-03-05T08:32:43Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

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.