A quantum algorithm for Viterbi decoding of classical convolutional codes

DOI10.1007/S11128-015-1003-3MaRDI QIDQ2516136zbMATH OpenOpenAlexFDO

Authors Jon R. Grice, David A. Meyer

Publication date 11 August 2015

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.7479

zbMATH Keywords

Viterbi algorithmhidden Markov modelconvolutional codeamplitude amplificationtensor product structurebutterfly diagramquantum function optimum finding

Mathematics Subject Classification ID

Quantum coding (general) (81P70)

Abstract: We present a quantum Viterbi algorithm (QVA) with better than classical performance under certain conditions. In this paper the proposed algorithm is applied to decoding classical convolutional codes, for instance; large constraint length $Q$ and short decode frames $N$. Other applications of the classical Viterbi algorithm where $Q$ is large (e.g. speech processing) could experience significant speedup with the QVA. The QVA exploits the fact that the decoding trellis is similar to the butterfly diagram of the fast Fourier transform, with its corresponding fast quantum algorithm. The tensor-product structure of the butterfly diagram corresponds to a quantum superposition that we show can be efficiently prepared. The quantum speedup is possible because the performance of the QVA depends on the fanout (number of possible transitions from any given state in the hidden Markov model) which is in general much less than $Q$. The QVA constructs a superposition of states which correspond to all legal paths through the decoding lattice, with phase a function of the probability of the path being taken given received data. A specialized amplitude amplification procedure is applied one or more times to recover a superposition where the most probable path has a high probability of being measured.

Recommendations

• scientific article; zbMATH DE number 5582982
• Convolutional and Tail-Biting Quantum Error-Correcting Codes
• scientific article; zbMATH DE number 6492463
• scientific article; zbMATH DE number 1504668
• Belief propagation decoding of quantum channels by passing quantum messages

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• Algebraic Codes for Data Transmission
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
• Perpectives in computation.
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Single-query learning from abelian and non-abelian Hamming distance oracles
• The algorithm design manual
• The quantum query complexity of learning multilinear polynomials

Cited in

(2)

• scientific article; zbMATH DE number 5582982 (Why is no real title available?)
• Quantum mean centering for block-encoding-based quantum algorithm

Describes a project that uses

Uses Software

• Stony Brook

This page was built for publication: A quantum algorithm for Viterbi decoding of classical convolutional codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2516136)