Fast Quantum Algorithm for Attention Computation
Yeqi Gao Zhao Song Xin Yang Ruizhe Zhang
Large language models (LLMs) have demonstrated exceptional performance across
a wide range of tasks. These models, powered by advanced deep learning
techniques, have revolutionized the field of natural language processing (NLP)
and have achieved remarkable results in various language-related tasks.
  LLMs have excelled in tasks such as machine translation, sentiment analysis,
question answering, text generation, text classification, language modeling,
and more. They have proven to be highly effective in capturing complex
linguistic patterns, understanding context, and generating coherent and
contextually relevant text. The attention scheme plays a crucial role in the
architecture of large language models (LLMs). It is a fundamental component
that enables the model to capture and utilize contextual information during
language processing tasks effectively. Making the attention scheme computation
faster is one of the central questions to speed up the LLMs computation. It is
well-known that quantum machine has certain computational advantages compared
to the classical machine. However, it is currently unknown whether quantum
computing can aid in LLM.
  In this work, we focus on utilizing Grover's Search algorithm to compute a
sparse attention computation matrix efficiently. We achieve a polynomial
quantum speed-up over the classical method. Moreover, the attention matrix
outputted by our quantum algorithm exhibits an extra low-rank structure that
will be useful in obtaining a faster training algorithm for LLMs. Additionally,
we present a detailed analysis of the algorithm's error analysis and time
complexity within the context of computing the attention matrix.