Quantum Viterbi Algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909054993956864 |
|---|---|
| author | Accardi, Luigi Souissi, Abdessatar Soueidi, El Gheteb Mukhamedov, Farrukh Rhaima, Mohamed |
| author_facet | Accardi, Luigi Souissi, Abdessatar Soueidi, El Gheteb Mukhamedov, Farrukh Rhaima, Mohamed |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_18912 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Quantum Viterbi Algorithm Accardi, Luigi Souissi, Abdessatar Soueidi, El Gheteb Mukhamedov, Farrukh Rhaima, Mohamed Quantum Physics Mathematical Physics Probability 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. |
| title | Quantum Viterbi Algorithm |
| topic | Quantum Physics Mathematical Physics Probability |
| url | https://arxiv.org/abs/2605.18912 |