⚛️ quantum physics

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

This paper proposes a hybrid quantum-classical Viterbi decoder that utilizes the Quantum Approximate Optimization Algorithm (QAOA) with a uniform parameter optimization strategy to efficiently map and solve the maximum likelihood decoding problem for classical linear block codes using low-depth parameterized quantum circuits.

Original authors: Mainak Bhattacharyya, Ankur Raina

Published 2026-02-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mainak Bhattacharyya, Ankur Raina

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Quantum Detective in a Maze

Imagine you are trying to send a secret message across a noisy radio channel. The static (noise) might flip some of your letters. When the message arrives, it's garbled. Your job is to figure out what the original message was.

In the classical world, we use a method called Viterbi Decoding. Think of this as a detective trying to solve a maze.

The Maze: The maze represents all the possible paths your message could have taken.
The Goal: The detective wants to find the shortest path through the maze that matches the garbled message they received.
The Problem: As the message gets longer, the maze gets exponentially bigger. A classical computer has to check every single path one by one, which takes a very long time (like trying to find a needle in a haystack by looking at every piece of hay).

This paper proposes a new way to solve this maze using a Quantum Computer, but not just any quantum computer. They are using a "hybrid" team: a quantum computer doing the heavy lifting and a classical computer acting as the coach.

The Cast of Characters

The Viterbi Decoder (The Detective): The algorithm that finds the best path through the maze.
QAOA (The Quantum Strategy): This stands for Quantum Approximate Optimization Algorithm. Imagine QAOA as a "super-intuitive" hiker. Instead of walking every path, it can "feel" the terrain and guess which way leads to the bottom of the valley (the solution) much faster.
The Hybrid Team:
- The Quantum Part: Explores many paths at once (superposition).
- The Classical Part: The "Coach." It looks at the results from the Quantum part, says, "That wasn't quite right, try adjusting your steps," and sends new instructions back.

The Core Innovation: The "Uniform" Strategy

The biggest hurdle in using Quantum Computers right now (which are currently small and noisy, known as NISQ devices) is that they are hard to train.

The Problem: The "Flat Desert" (Barren Plateaus)
Imagine you are trying to find the lowest point in a landscape.

Old Method (Random/Fixed): You pick a spot and start walking. But the landscape is so flat (a "barren plateau") that you can't tell which way is down. You just wander aimlessly. If you try to teach the quantum computer by changing every step differently, it gets confused and the signal gets lost.
The Paper's Solution (Uniform Parameter Optimization - UPO): Instead of giving the quantum computer a different instruction for every single step, the authors say: "Let's all move in sync."

The Analogy:
Imagine a marching band trying to find the best route through a city.

Old Way: Every musician gets a different, random instruction on how to turn. The band falls apart, and no one knows where to go.
New Way (UPO): The conductor tells everyone to turn left at the same time, then everyone to turn right at the same time. By keeping the instructions uniform (the same for everyone), the band stays together, moves efficiently, and finds the destination much faster.

The paper shows that by forcing the quantum computer to use the same "settings" for every layer of its calculation, it avoids getting lost in the flat desert and finds the solution much more reliably.

How It Works (Step-by-Step)

Setting the Stage: They take a specific type of error-correcting code (like a [6,3,3] code, which is a small, manageable maze).
Creating the Superposition: They use a quantum circuit to create a state where all possible valid messages exist at the same time. It's like having a ghost version of every possible path in the maze simultaneously.
The "Cost" Check: They apply a "Cost Hamiltonian." Think of this as a scale that weighs how "wrong" a path is. If a path has many errors (flipped bits), it weighs heavy. If it's close to the received message, it's light.
The "Mixer" Dance: They apply a "Mixer Hamiltonian." This is like a dance move that shuffles the probabilities. It makes the "heavy" (wrong) paths less likely and the "light" (correct) paths more likely.
The Training Loop:
- The Quantum computer runs the dance.
- The Classical Coach measures the result.
- The Coach says, "The correct path isn't loud enough yet. Let's tweak the volume knobs (parameters)."
- Crucial Step: Instead of tweaking every knob randomly, they use the Uniform Strategy: they turn all the knobs by the same amount.
The Result: The correct path becomes the loudest signal. When they measure the quantum computer, it almost always spits out the correct original message.

Why This Matters

Efficiency: Previous attempts to use quantum computers for this were slow or required too much memory. This method uses "low-depth" circuits, meaning it doesn't need a massive, perfect quantum computer to work. It can work on the smaller, noisier machines we have today.
Accuracy: The paper proves that this "Uniform" training method finds the solution much more often than random guessing or other complex training methods.
Versatility: They showed it works on different types of codes, not just one specific puzzle.

The Conclusion

The authors have built a Quantum-Classical Hybrid Viterbi Decoder.

Think of it as a new type of GPS for data transmission. Instead of a classical computer getting stuck in traffic trying to check every route, this hybrid system uses a quantum "shortcut" guided by a smart, synchronized strategy (UPO) to find the fastest, most accurate path through the noise.

While we aren't replacing all our internet routers with quantum computers tomorrow, this paper proves that we can use today's imperfect quantum hardware to solve very hard decoding problems efficiently, paving the way for faster and more reliable communication in the future.

1. Problem Statement

Classical error-correcting codes (such as linear block codes and convolution codes) are essential for reliable data transmission. However, decoding these codes to find the most likely transmitted codeword from a noisy received vector is a computationally hard problem.

Complexity: Maximum Likelihood (ML) decoding is generally NP-hard, with a time complexity of $O(2^n)$ for a codeword of length $n$ .
Viterbi Decoding: While Viterbi decoding offers a trellis-based approach to find the path with the minimum Hamming distance (ML solution), it remains classically exhaustive for general linear block codes.
Quantum Limitations: Previous quantum attempts, such as Grover-based search or Iterative Amplitude Amplification (IAA), often suffer from high circuit depth or vulnerability to noise in Noisy Intermediate-Scale Quantum (NISQ) devices.
Optimization Challenge: Variational Quantum Algorithms (VQAs) like the Quantum Approximate Optimization Algorithm (QAOA) are promising for NISQ devices but face the "barren plateau" problem, where random parameter initialization leads to vanishing gradients, making optimization difficult.

2. Methodology

The authors propose a Hybrid Quantum-Classical Viterbi Decoder that maps the trellis-based decoding problem into a QAOA framework.

A. Problem Mapping to QAOA

Cost Function ( $f(c)$ ): The decoding goal is to minimize the Hamming distance between a candidate codeword $c$ and the received erroneous vector $y$ . This is formulated as a pseudo-Boolean function:
$f(c) = \sum_{i=1}^{n} (c_i \oplus y_i)$
Cost Hamiltonian ( $H_f$ ): The cost function is mapped to a diagonal Hamiltonian using Pauli-Z operators. The system uses two registers:
- Register $x$ : Represents the codeword bits.
- Register $r$ : Represents the received vector (ancilla qubits initialized to $|y\rangle$ ).
  $H_f = \sum_{i=1}^{n} \left( \frac{1}{2}I - \frac{1}{2}Z_{x_i}Z_{r_i} \right)$
Mixer Hamiltonian ( $H_m$ ): A critical contribution is the construction of a mixer that preserves the codespace $C$ $C$ (ensuring the system only evolves through valid codewords).
- Theorem 1: The authors prove that for a linear block code with minimum Hamming distance $d$ , the mixer Hamiltonian is the sum of $d$ -local Pauli-X operators. These operators map the null state (all-zero codeword) to other valid codewords at Hamming distance $d$ .
- This ensures the search space is restricted to valid codewords, preventing the algorithm from exploring invalid states.

B. Uniform Parameter Optimization (UPO) Strategy

To address the barren plateau problem and the difficulty of finding optimal parameters ( $\gamma, \beta$ ) in the Parameterized Quantum Circuit (PQC):

Standard Approach: Typically involves random initialization or Fixed Parameter Optimization (FPO), where parameters are optimized layer-by-layer.
Proposed UPO: The authors enforce a uniformity constraint where all mixer parameters are equal ( $\beta_1 = \beta_2 = \dots = \beta_p = \beta_0$ ) and all cost parameters are equal ( $\gamma_1 = \gamma_2 = \dots = \gamma_p = \gamma_0$ ).
Rationale: This reduces the dimensionality of the optimization landscape, avoiding flat regions (barren plateaus) and making the circuit more trainable on shallow depths.

C. Algorithm Workflow

Initialization: Create a uniform superposition of all valid codewords in the codespace using a generator unitary $U_g$ .
Encoding: Initialize ancilla qubits to represent the received vector $y$ .
Variational Loop: Apply $p$ layers of Cost Unitary ( $U_f(\gamma_0)$ ) and Mixer Unitary ( $U_m(\beta_0)$ ).
Optimization: Use a classical optimizer to minimize the expectation value $\langle H_f \rangle$ by adjusting $\gamma_0$ and $\beta_0$ via the UPO strategy.
Measurement: Measure the codeword register to obtain the decoded path with the highest probability.

3. Key Contributions

Generalized Mapping: A method to map the Viterbi decoding problem for any classical linear block code into a QAOA framework by defining a cost function based on Hamming distance.
Theorem 1 (Mixer Construction): A formal proof and construction of a mixer Hamiltonian that depends on the code's minimum Hamming distance ( $d$ ), ensuring the quantum evolution remains strictly within the valid codespace.
Uniform Parameter Optimization (UPO): A novel heuristic strategy that significantly outperforms random initialization and layer-wise fixed parameter optimization (FPO) in finding good parameters for shallow-depth circuits.
Low-Depth Efficiency: Demonstration that the hybrid decoder works effectively with low circuit depths, making it suitable for current NISQ hardware.

4. Results

The authors simulated the algorithm using IBM's Qiskit and QASM simulator on several codes:

[6, 3, 3] Code:
- Received vector: $y = 111011$ .
- Outcome: The UPO strategy successfully amplified the correct codeword $|011011\rangle$ (Hamming distance 1) with high probability.
- Comparison: UPO showed a regular, high-probability amplification of the solution. In contrast, FPO and random initialization showed random, inconsistent results and often failed to find the optimal parameters.
[9, 4, 4] Code: Successfully decoded with unit path metric using 3 unitary layers.
[3, 2, 1] Code: Successfully identified two paths with equal minimum metrics, correctly reflecting the theoretical ambiguity of the code.
Benchmarking: The hybrid decoder was benchmarked against a classical Min-Sum Belief Propagation decoder on repetition codes. The results showed comparable Word Error Rates (WER), validating the hybrid approach as a viable active decoder.
Landscape Analysis: Visualizations of the cost function landscape confirmed that UPO creates a non-flat landscape with distinct gradients, whereas FPO often results in flat regions (barren plateaus) where gradients vanish.

5. Significance and Future Outlook

NISQ Viability: This work provides a concrete pathway for implementing quantum decoding on current hardware by utilizing low-depth circuits and robust parameter optimization strategies.
Hybrid Efficiency: It demonstrates that a quantum-classical hybrid approach can solve NP-hard decoding problems more efficiently than previous specialized quantum algorithms (like IAA) which suffer from high overhead.
Scalability: While the current work focuses on small codes due to simulator limitations, the UPO strategy is theoretically expected to scale better than random or fixed methods for larger codes where the parameter space is vast.
Future Work: The authors suggest extending this to larger codes, integrating quantum error correction for NISQ implementation, and applying the variational approach to other inference problems beyond error correction.

In summary, the paper successfully bridges classical coding theory and quantum computing by transforming Viterbi decoding into a QAOA problem, solving the parameter optimization bottleneck via UPO, and demonstrating high-fidelity decoding on simulated NISQ devices.