Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes

Abstract

We construct a hybrid quantum-classical Viterbi decoder for the classical error-correcting codes. Viterbi decoding is a trellis-based procedure for maximum likelihood decoding of classical error-correcting codes. In this article, we demonstrate that the quantum approximate optimization algorithm can find any path on the trellis with the minimum Hamming distance relative to the received erroneous vector. We construct a generalized method to map the Viterbi decoding problem into optimization of a parameterized quantum circuit for any classical linear block code. Also, we propose a uniform parameter optimization strategy to optimize the parameterized quantum circuit using a classical optimizer. We observe that the proposed method efficiently generates low-depth trainable parameterized quantum circuits. Our approach makes the hybrid decoder more efficient than previous attempts at making quantum Viterbi algorithm. We show that using uniform parameter optimization, we obtain parameters more efficiently for the parameterized quantum circuit than previously used methods such as random sampling and fixing the parameters.

32 pages, 18 figures, pre-print

References in corpus (18)

• Quantum Computing in the NISQ era and beyond
• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• Noisy intermediate-scale quantum (NISQ) algorithms
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Training variational quantum algorithms is NP-hard
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
• Variational Quantum Eigensolver with Reduced Circuit Complexity
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Quantum Computing Techniques for Multi-Knapsack Problems
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization