A Quantum Search Decoder for Natural Language Processing

Understand

Probabilistic language models, e.g.

• those based on an LSTM, often face the problem of finding a high probability prediction from a sequence of random variables over a set of tokens.
• This is commonly addressed using a form of greedy decoding such as beam search, where a limited number of highest-likelihood paths (the beam width) of the decoder are kept, and at the end the maximum-likelihood path is chosen.
• In this work, we construct a quantum algorithm to find the globally optimal parse (i.e.