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.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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.
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.
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..
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.
Compare Generalized Grover / amplitude amplification with the strongest classical method for the same instance, input budget, and output metric.
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
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.
arxiv.org/abs/1405.7479 ↗