Quantum Viterbi Algorithm

2026

Read Quantum Viterbi Algorithm (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18912.txt.

Introduction

Luigi Accardi and four colleagues present a quantum version of Viterbi decoding for hidden quantum Markov models. Given results, the method finds hidden quantum paths that top a joint decoding score, the quantum twin of the classical Viterbi score. Unlike classical decoding over a finite state space, it searches a continuous manifold of pure quantum effects, using superpositions in hidden memory. The authors prove a strict quantum advantage: coherent paths can beat any classical strategy restricted to diagonal effects, even with identical data.

Catalog record

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80446
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.18912

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Viterbi Algorithm 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. Keywords: Quantum hidden Markov models, quantum Viterbi algorithm, Statistical Model, quantum dynamic programming, quantum advantage, sequential decoding. Luigi Accardi Centro Vito Volterra, Università di Roma ”Tor Vergata” Roma I-00133, Italy [email protected] Abdessatar Souissi Department of Management Information Systems, College of Business and Economics, Qassim University, Buraydah 51452, Saudi Arabia [email protected] El Gheteb Soueidi Department of Mathematics and Informatics, Faculty of Sciences and Technologies, University of Nouakchott, Mauritania [email protected] Farrukh Mukhamedov Department of Mathematical Sciences, College of Science, United Arab Emirates University, P.O. Box 15551, Al Ain, Abu Dhabi, UAE [email protected] Mohamed Rhaima Department of Statistics and Operations Research, College of Sciences, King Saud University, P. O Box 2455, Riyadh 11451, Saudi Arabia [email protected] 1 Introduction For over five decades, the Hidden Markov Model (HMM) has stood as a quiet workhorse of artificial intelligence—a testament to the power of modeling the world through what we cannot see. From the earliest speech recognition systems that learned to parse the cacophony of human speech into discrete phonetic units, to modern computational biology where these models trace the intricate architecture of genes within vast strands of DNA, the HMM has provided a unifying framework for understanding sequential data [ 65 , 27 , 52 ] . Its enduring appeal is not merely its ability to capture the subtle dance between observed phenomena and their hidden causes, but the sheer elegance of its computational solution. At its heart lies a daunting challenge: the number of possible hidden state sequences grows as d^{n+1} for d states and length n , a combinatorial explosion that would rapidly become intractable. Yet, the Viterbi algorithm, a masterpiece of dynamic programming, tames this complexity, reducing what seems like an exponentially scaling problem to a disciplined O(d^{2}n) computation [ 77 , 32 , 48 ] . This efficiency—the ability to extract the single most probable explanation from a sea of possibilities—is what transformed HMMs from a theoretical curiosity into a practical cornerstone of modern machine learning and signal processing [ 4 , 78 , 50 ] . However, as we stand on the cusp of the quantum computing era, this very notion of scaling is being re‑evaluated. The emergence of quantum convolutional coding and its maximum‑likelihood decoding strategies, inspired by Viterbi‑type recursions in the quantum regime [ 58 , 59 , 60 ] , together with explicitly quantum algorithms for Viterbi decoding of classical convolutional codes [ 61 ] , signals a profound shift: dynamic programming on trellises is no longer confined to classical computation. These developments, synthesized and systematized in the modern theory of quantum convolutional codes [ 62 ] , challenge us to ask whether the algorithmic guarantees that have underpinned the classical Viterbi algorithm for generations can be not only matched but fundamentally re‑engineered in a quantum setting. Can a quantum formulation of Viterbi decoding reshape the scaling landscape for inference over hidden processes, moving beyond the limits of classical dynamic programming to approach, or even attain, genuine quantum advantage in sequential data analysis? Quantum Markov chains (QMCs) provide a principled non‑commutative generalization of classical Markov chains, replacing stochastic kernels by completely positive, identity‑preserving transition expectations on operator algebras [ 3 , 2 , 40 ] . Their Hilbert–Schmidt duals are quantum channels, yielding the usual Schrödinger‑picture formulation familiar in quantum information theory [ 29 , 24 , 40 ] . In finite dimensions, a QMC is determined by a transition expectation \mathcal{E}:\mathcal{B}(\mathcal{H})\otimes\mathcal{B}(\mathcal{H})\to\mathcal{B}(\mathcal{H}) that is completely positive, unital, and defines a consistent family of local states on the quasi‑local algebra \mathcal{B}(\mathcal{H})^{\otimes\mathbb{N}} , thereby encoding a genuinely quantum Markov property [ 2 ] . When \mathcal{E} preserves a diagonal subalgebra, the construction collapses to a classical Markov chain on a finite alphabet, but in general the presence of off‑diagonal coherence leads to dynamics that have no classical counterpart [ 47 , 2 , 40 ] . Hidden quantum Markov models (HQMMs) enrich this picture by coupling a hidden quantum chain to an observable system via quantum instruments, yielding a quantum analogue of classical HMMs [ 1 , 51 ] . In the HQMP formulation, one specifies hidden and observable tensor‑product algebras, a family of hidden transition expectations \mathcal{E}_{H;n} , and emission maps \mathcal{E}_{H,O;n} that implement the measurement–back‑action mechanism on the hidden algebra, with a joint state \varphi_{H,O} enforcing consistency of the process [ 1 ] . Classical HMMs are recovered when these maps preserve diagonal subalgebras, while the fully quantum case allows coherent hidden evolution and nontrivial back‑action, producing temporal correlations beyond any classical HMM of the same hidden dimension [ 1 , 51 ] . Moreover, HQMMs connect naturally to entangled hidden Markov models and matrix product state descriptions of quantum processes, where output statistics are encoded by MPS generated from suitable Kraus operators [ 54 , 70 , 31 ] . This embeds HQMMs into the tensor‑network toolkit of quantum many‑body physics and clarifies their capacity to model finite‑memory quantum stochastic processes [ 51 , 70 , 31 ] . Taken together, these constructions provide a robust mathematical framework within which one can formulate and analyze rigorous quantum analogues of classical decoding algorithms—most notably Viterbi‑type and Bellman‑recursive schemes for quantum and hidden quantum Markov models—thereby offering a natural setting to pursue the quantum decoding questions raised above [ 2 , 1 , 51 , 70 ] . 1.1 Contribution We develop a Viterbi-type decoding scheme for hidden quantum Markov models (HQMMs) in an operator-algebraic setting, placing quantum decoding within the non-commutative Markov and HQMP framework introduced above [ 2 , 1 , 51 ] . Given a finite observation sequence (q_{0},\dots,q_{n}) with q_{m}\in\mathcal{P}_{1}(\mathcal{K}) (rank-one projections on \mathcal{K} ), the quantum Viterbi problem is to select a hidden trajectory (p_{0},\dots,p_{n}) of pure effects p_{m}\in\mathcal{P}_{1}(\mathcal{H})\subset\mathsf{Eff}(\mathcal{H}) that maximizes the joint score functional \psi_{n}(p_{0},\dots,p_{n}):=\varphi_{H,O}\!\left(\bigotimes_{m=0}^{n}(p_{m}\otimes q_{m})\right), where \mathsf{Eff}(\mathcal{H})=\{e\in\mathcal{B}(\mathcal{H})\mid 0\leq e\leq\mathbb{I}\} is ordered by A\leq B\Leftrightarrow B-A\geq 0 , and \mathcal{P}_{1}(\mathcal{H}) plays the role of an “atomic” hidden state space, generalizing the finite state set S of a classical HMM [ 2 , 1 ] . The basic optimization task is to compute \psi_{\mathrm{quantum}}^{*}:=\sup_{(p_{0},\dots,p_{n})\in\mathcal{P}_{1}(\mathcal{H})^{n+1}}\psi_{n}(p_{0},\dots,p_{n}) and to identify an optimal or approximately optimal trajectory (p_{0}^{*},\dots,p_{n}^{*}) . In the classical case, with hidden states i_{m}\in S , this supremum reduces to a finite maximum \psi_{\mathrm{classical}}^{*}=\max_{(i_{0},\dots,i_{n})\in S^{n+1}}\psi_{n}\bigl(|i_{0}\rangle\!\langle i_{0}|,\dots,|i_{n}\rangle\!\langle i_{n}|\bigr), and the Markov property yields a scalar factorization into transition and emission

Read the complete text