A Quantum Search Decoder for Natural Language Processing

Abstract

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. for infinite beam width) with high constant success probability. When the input to the decoder is distributed as a power-law with exponent $k>0$, our algorithm has runtime $R^{nf(R,k)}$, where $R$ is the alphabet size, $n$ the input length; here $f<1/2$, and $f\to 0$ exponentially fast with increasing $k$, hence making our algorithm always more than quadratically faster than its classical counterpart. We further modify our procedure to recover a finite beam width variant, which enables an even stronger empirical speedup while still retaining higher accuracy than possible classically. Finally, we apply this quantum beam search decoder to Mozilla's implementation of Baidu's DeepSpeech neural net, which we show to exhibit such a power law word rank frequency.

arXiv comment39 pages, 16 figures, 2 algorithms

References in corpus (14)

• Deep Learning in Neural Networks: An Overview
• Quantum algorithm for solving linear systems of equations
• The theory of variational hybrid quantum-classical algorithms
• Quantum algorithms: an overview
• Halving the cost of quantum addition
• Accelerated Variational Quantum Eigensolver
• A quantum-inspired classical algorithm for recommendation systems
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Nearly optimal lattice simulation by product formulas
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Quantum speedup of branch-and-bound algorithms
• Time and Space Bounds for Reversible Simulation
• Classifying Data with Local Hamiltonians

Cited by in corpus (2)

• Grammar-aware sentence classification on quantum computers
• Quantum Natural Language Processing