Algorithms · Generalized Grover / amplitude amplification
Viterbi decoding of classical convolutional codes
The Viterbi algorithm finds the most likely sequence of hidden states a hidden Markov model passed through, given a sequence of emissions. Applied to decoding, the hidden states are the encoder states of a classical convolutional code and the emissions are the received symbols, so the most likely path is the decoded message.
Attested & literatureUpdated
A small worked example, computed in your browser. It is not a result from this record's papers.
Grover's algorithm finds |101⟩
3 qubits, searching for |101⟩ among 8 states, with 2 Grover iterations.
Step 1 of 5 · Hadamard layer(3)
Probability of each outcome after this step
- 00013%
- 00113%
- 01013%
- 01113%
- 10013%
- 10113%
- 11013%
- 11113%
Spreads the state into an equal superposition of all 8 three-qubit strings. Every answer is equally likely, including the right one.
Probability spreads from 1 outcome to 8. All 8 are equally likely.
The oracle marks |101⟩ by flipping its sign, and leaves the other seven states exactly as they were. Measuring now would be no better than guessing — the mark is a phase, and a phase is not an outcome.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
The diffuser reflects every amplitude about their average. The marked state sits below the average because its sign was flipped, so reflecting pushes it up and pulls the other seven down. This is where the phase becomes probability.
Probability moves between the same 8 outcomes. Up: 101 12.5% → 78.1%. Down: 111 12.5% → 3.1%, 011 12.5% → 3.1%.
The same oracle again, flipping the sign of |101⟩ — now the largest amplitude rather than one of eight equal ones.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
And the same reflection again. Two iterations is close to the optimal number for 8 states: a third would overshoot and start pushing the answer back down.
Probability moves between the same 8 outcomes. Up: 101 78.1% → 94.5%. Down: 100 3.1% → 0.8%, 010 3.1% → 0.8%.
Readout Measuring gives 101, the marked state, with high probability.
Open in Studio- Record typeLiterature reference
- Speedup class (secondary source)Varies
- Primary source on the speedupStated by the primary source: "We present a quantum Viterbi algorithm (QVA) with better than classical performance under certain conditions. … 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."
- Reported costA single iteration has gate complexity O(N |Q| F (log F)²) and time complexity O(N log F) if |Q| quantum systems can be manipulated simultaneously, where N is the frame length, Q the state set and F the fanout. The number of iterations can be up to O(√L) as in Grover's algorithm, with L = N F log F, giving O(√(F^N) N log F) overall when the maximal amount of parallelism is used.
- Papers1
The Viterbi algorithm finds the most likely sequence of hidden states a hidden Markov model passed through, given a sequence of emissions. Applied to decoding, the hidden states are the encoder states of a classical convolutional code and the emissions are the received symbols, so the most likely path is the decoded message. Grice and Meyer exploit the observation that the decoding trellis has the shape of the butterfly diagram of the fast Fourier transform, which has a fast quantum counterpart. The algorithm builds a superposition over all admissible paths through the decoding lattice, then marks each path with a phase that depends on its probability, then applies a specialized amplitude amplification procedure — analogous to Grover's algorithm — one or more times, so that the most probable path has a high probability of being measured. The paper works the construction through explicitly for a rate-1/2, memory-2 binary convolutional code, and tabulates the best phase parameter numerically for frame lengths from three to ten.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Grice and Meyer exploit the observation that the decoding trellis has the shape of the butterfly diagram of the fast Fourier transform, which has a fast quantum counterpart. The algorithm builds a superposition over all admissible paths through the decoding lattice, then marks each path with a phase that depends on its probability, then applies a specialized amplitude amplification procedure — analogous to Grover's algorithm — one or more times, so that the most probable path has a high probability of being measured. The paper works the construction through explicitly for a rate-1/2, memory-2 binary convolutional code, and tabulates the best phase parameter numerically for frame lengths from three to ten. This record's speedup class, "Varies", is a secondary source's classification of the algebraic and number theoretic algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "We present a quantum Viterbi algorithm (QVA) with better than classical performance under certain conditions. … 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.". Reported cost: A single iteration has gate complexity O(N |Q| F (log F)²) and time complexity O(N log F) if |Q| quantum systems can be manipulated simultaneously, where N is the frame length, Q the state set and F the fanout. The number of iterations can be up to O(√L) as in Grover's algorithm, with L = N F log F, giving O(√(F^N) N log F) overall when the maximal amount of parallelism is used..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Varies
- Primary source on the speedup
- Stated by the primary source: "We present a quantum Viterbi algorithm (QVA) with better than classical performance under certain conditions. … 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."
- Reported cost
- A single iteration has gate complexity O(N |Q| F (log F)²) and time complexity O(N log F) if |Q| quantum systems can be manipulated simultaneously, where N is the frame length, Q the state set and F the fanout. The number of iterations can be up to O(√L) as in Grover's algorithm, with L = N F log F, giving O(√(F^N) N log F) overall when the maximal amount of parallelism is used.
- Speedup class
- Varies (checked against the record's own primary paper, which states it)
- Complexity basis
- section 1 of arXiv:1405.7479: "A single iteration of the QVA will be shown to have gate complexity O(N |Q|F(log F)²) and time complexity O(N log F), if |Q| quantum systems can be manipulated simultaneously."; same section: "The number of iterations in general can be up to O(√L) as in Grover's algorithm [1], where here L = N F log F."; and "If using the maximal amount of parallelism, the QVA decodes the convolutional code in time O(√(F^N) N log F)."
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Generalized Grover / amplitude amplification with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Viterbi decoding of classical convolutional codes
PROBLEM: The Viterbi algorithm finds the most likely sequence of hidden states a hidden Markov model passed through, given a sequence of emissions. Applied to decoding, the hidden states are the encoder states of a classical convolutional code and the emissions are the received symbols, so the most likely path is the decoded message.
IDEA: Grice and Meyer exploit the observation that the decoding trellis has the shape of the butterfly diagram of the fast Fourier transform, which has a fast quantum counterpart. The algorithm builds a superposition over all admissible paths through the decoding lattice, then marks each path with a phase that depends on its probability, then applies a specialized amplitude amplification procedure — analogous to Grover's algorithm — one or more times, so that the most probable path has a high probability of being measured. The paper works the construction through explicitly for a rate-1/2, memory-2 binary convolutional code, and tabulates the best phase parameter numerically for frame lengths from three to ten.
REPORTED COST: A single iteration has gate complexity O(N |Q| F (log F)²) and time complexity O(N log F) if |Q| quantum systems can be manipulated simultaneously, where N is the frame length, Q the state set and F the fanout. The number of iterations can be up to O(√L) as in Grover's algorithm, with L = N F log F, giving O(√(F^N) N log F) overall when the maximal amount of parallelism is used.
BASIS: section 1 of arXiv:1405.7479: "A single iteration of the QVA will be shown to have gate complexity O(N |Q|F(log F)²) and time complexity O(N log F), if |Q| quantum systems can be manipulated simultaneously."; same section: "The number of iterations in general can be up to O(√L) as in Grover's algorithm [1], where here L = N F log F."; and "If using the maximal amount of parallelism, the QVA decodes the convolutional code in time O(√(F^N) N log F)."
PRIMARY SOURCE: Jon R. Grice, David A. Meyer (2014), A quantum algorithm for Viterbi decoding of classical convolutional codes — https://arxiv.org/abs/1405.7479
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
- Grover unstructured search
Algorithms
- Amplitude amplification
Algorithms
- Quantum Fourier Transform
Algorithms
References
- A quantum algorithm for Viterbi decoding of classical convolutional codes
Jon R. Grice, David A. Meyer · 2014
Primary source, and the source of this record's cost claim. Consult it for the simultaneous-manipulation assumption that the time complexity is conditioned on, for the fanout-versus-state-set relationship that the whole advantage argument rests on, and for section 3, where the phase parameter is chosen numerically because the general analysis is difficult.