Quantum Viterbi Algorithm

• URL: http://arxiv.org/abs/2605.18912v1
• Date: Sun, 17 May 2026 20:09:26 GMT
• Title: Quantum Viterbi Algorithm
• Abstract summary: We introduce a quantum Viterbi decoding algorithm for hidden quantum Markov models (HQMMs)<n>We prove a strict quantum advantage: coherent hidden trajectories can achieve decoding scores that strictly exceed any classical strategy.<n>Results position quantum Viterbi decoding as a concrete quantum algorithmic primitive for sequential decision-making.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a quantum Viterbi decoding algorithm for hidden quantum Markov models (HQMMs) motivated by quantum information processing and quantum algorithms. Given a finite sequence of measurement outcomes, the algorithm identifies hidden quantum trajectories that maximize a joint decoding functional, serving as a genuine quantum analogue of the classical Viterbi score. Unlike classical hidden Markov models, where decoding optimizes over a finite discrete state space, our method performs optimization over a continuous manifold of pure quantum effects, thereby exploiting coherent superpositions in the hidden memory. We prove a strict quantum advantage: coherent hidden trajectories can achieve decoding scores that strictly exceed any classical strategy constrained to diagonal (commuting) effects, even when both models share the same observed statistics. These results position quantum Viterbi decoding as a concrete quantum algorithmic primitive for sequential decision-making, with direct applications to quantum memories, quantum communication with memory, and near-term quantum machine learning on NISQ devices.

Related papers

• Quantum-Channel Matrix Optimization for Holevo Bound Enhancement [87.57725685513088]
  We propose a unified projected gradient ascent algorithm to optimize the quantum channel given a fixed input ensemble.<n> Simulation results demonstrate that the proposed quantum channel optimization yields higher Holevo bounds than input ensemble optimization.
  arXiv  Detail & Related papers  (2026-02-19T04:15:03Z)
• Quantum Approximate Walk Algorithm [0.6306978246081341]
  We present a classical data-traceable quantum oracle characterized by a circuit depth that increases linearly with the number of qubits.<n>By establishing an inferable mapping between the classical input and quantum circuit outcomes, we obtained experimental results on the state-of-the-art IBM hardware.
  arXiv  Detail & Related papers  (2025-11-10T22:43:12Z)
• Provably Robust Training of Quantum Circuit Classifiers Against Parameter Noise [49.97673761305336]
  Noise remains a major obstacle to achieving reliable quantum algorithms.<n>We present a provably noise-resilient training theory and algorithm to enhance the robustness of parameterized quantum circuit classifiers.
  arXiv  Detail & Related papers  (2025-05-24T02:51:34Z)
• Runtime Quantum Advantage with Digital Quantum Optimization [36.136619420474766]
  bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm on IBM's 156-qubit devices.<n>We suitably select problem instances that are challenging for classical methods, running in fractions of minutes even with multicore processors.<n>Our results indicate that available digital quantum processors, when combined with specific-purpose quantum algorithms, exhibit a runtime quantum advantage even in the absence of quantum error correction.
  arXiv  Detail & Related papers  (2025-05-13T15:24:17Z)
• The curse of random quantum data [62.24825255497622]
  We quantify the performances of quantum machine learning in the landscape of quantum data. We find that the training efficiency and generalization capabilities in quantum machine learning will be exponentially suppressed with the increase in qubits. Our findings apply to both the quantum kernel method and the large-width limit of quantum neural networks.
  arXiv  Detail & Related papers  (2024-08-19T12:18:07Z)
• Benchmarking Variational Quantum Eigensolvers for Entanglement Detection in Many-Body Hamiltonian Ground States [37.69303106863453]
  Variational quantum algorithms (VQAs) have emerged in recent years as a promise to obtain quantum advantage. We use a specific class of VQA named variational quantum eigensolvers (VQEs) to benchmark them at entanglement witnessing and entangled ground state detection. Quantum circuits whose structure is inspired by the Hamiltonian interactions presented better results on cost function estimation than problem-agnostic circuits.
  arXiv  Detail & Related papers  (2024-07-05T12:06:40Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Power Characterization of Noisy Quantum Kernels [52.47151453259434]
  We show that noise may make quantum kernel methods to only have poor prediction capability, even when the generalization error is small. We provide a crucial warning to employ noisy quantum kernel methods for quantum computation.
  arXiv  Detail & Related papers  (2024-01-31T01:02:16Z)
• Enhancing Quantum Annealing in Digital-Analog Quantum Computing [0.0]
  Digital-analog quantum computing (DAQC) offers a promising approach to addressing the challenges of building a practical quantum computer. We propose an algorithm designed to enhance the performance of quantum annealing. This study provides an example of how processing quantum data using a quantum circuit can outperform classical data processing, which discards quantum information.
  arXiv  Detail & Related papers  (2023-06-03T09:16:15Z)
• Quantum-Enhanced Greedy Combinatorial Optimization Solver [12.454028945013924]
  We introduce an iterative quantum optimization algorithm to solve optimization problems. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement.
  arXiv  Detail & Related papers  (2023-03-09T18:59:37Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum variational learning for entanglement witnessing [0.0]
  This work focuses on the potential implementation of quantum algorithms allowing to properly classify quantum states defined over a single register of $n$ qubits. We exploit the notion of "entanglement witness", i.e., an operator whose expectation values allow to identify certain specific states as entangled. We made use of Quantum Neural Networks (QNNs) in order to successfully learn how to reproduce the action of an entanglement witness.
  arXiv  Detail & Related papers  (2022-05-20T20:14:28Z)
• Optimizing High-Efficiency Quantum Memory with Quantum Machine Learning for Near-Term Quantum Devices [0.0]
  We define a novel quantum memory called high-retrieval-efficiency (HRE) quantum memory for near-term quantum devices. An HRE quantum memory unit integrates local unitary operations on its hardware level for the optimization of the readout procedure. We show that the readout procedure of an HRE quantum memory is realized in a completely blind manner without any information about the input quantum system or about the unknown quantum operation of the quantum register.
  arXiv  Detail & Related papers  (2020-03-11T12:01:03Z)

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.