Natural Language Processing Meets Quantum Physics: A Survey and Categorization (2021)

Abstract: Recent research has investigated quantum NLP, designing algorithms that process natural language in quantum computers, and also quantum-inspired algorithms that improve NLP performance on classical computers. In this survey, we review representative methods at the intersection of NLP and quantum physics in the past ten years, categorizing them according to the use of quantum theory, the linguistic targets that are modeled, and the downstream application. The literature review ends with a discussion on the key factors to the success that has been achieved by existing work, as well as challenges ahead, with the goal of better understanding the promises and further directions.

## introduction quantum computing has received much interest in recent years. the basic idea is to make use the power of quantum mechanics for solving computational problems @xcite . while particular quantum algorithms can be substantially faster alternatives to classical counterparts @xcite , the mathematical framework of quantum physics has also been exploited for cognition @xcite , optimization @xcite and other disciplines. in the field of natural language processing (nlp), quantum mechanics has seen a surge of recent research interests, addressing problems ranging from lexical semantic ambiguities @xcite to semantic composition @xcite , and from information retrieval @xcite ) to text classification @xcite , where different characteristics of quantum physics have inspired novel algorithms. despite its growing research literature, no survey has reviewed and categorized the quantum nlp field. the most relevant surveys are on quantuminspired information retrieval @xcite . however, they did not include many important findings in the quantum nlp field. @xcite and @xcite generally reviewed the field of quantum machine learning. they also briefly mentioned several quantum algorithms for nlp, but they did not discuss them comprehensively or in detail. the goal of our paper is to, for the first time, propose a categorization of quantum nlp in the past ten years, aiming to provide the latest knowledge of developments and achievements in this field. we categorize existing work on quantum nlp based on the following three dimensions: although quantum nlp is still an emerging field, existing work shows exciting promise-not only better performance but also more efficient calculations are possible. in addition, noisy intermediatescale quantum (nisq) computers already exist and seem to have potential use in nlp tasks @xcite . it has been shown that quantum nlp can take effect in addressing the inherent ambiguities of words, representing lexical semantic correlations, and calculating semantic composition, which is useful for a set of language modeling and information retrieval tasks. on the other hand, success has been achieved only on small scales, and the key reason for achieving competitive performance still needs further understanding. the theoretical evidence provided in the literature cannot yet lead to a conclusion that quantum physics can gain substantial computational advantages in wider nlp tasks. ## quantum physics preliminaries the simplest quantum mechanical system is a qubit, which has two possible states: |0 and |1 , where '|• ' is called the dirac notation, and a ket |ψ denotes a unit column vector. similarly, the row vector ψ † is expressed as a bra ψ|, where the dagger ( †) corresponds to the conjugate transpose. a qubit can be represented by the linear combination of states, often called superposition: entanglement is another elementary and unique resource of quantum mechanics which plays a key role in many interesting applications of quantum computing. consider the following two-qubit entangled bell state @xcite : as discussed earlier, when we measure the first qubit, we obtain two possible results: 0 with probability 1/2 and 1 with probability 1/2. according to eq.2, a measurement of the second qubit always gives the same outcome as the measurement of the first qubit, because the measurement results of these two entangled qubits are correlated. @xcite proposed that if words are encoded into quantum states, then the grammatical structure is to entangle these states. because grammar is what correlates meanings between words. we will explain this in section 4.2.2. projective measurements are the most general form of measurement in quantum mechanics, where the measurement operators are projectors p that satisfy p 2 = p . if the state is |ψ before projective measurement then the probability that result m occurs is given by p(m) = ψ| p m |ψ . the state after measurement is: projective measurement can be applied to calculate cosine similarity in nlp, which measures the similarities between two vectors. suppose |a and |b represent word a and b, respectively. then, the cosine similarity of these two word vectors is in addition to state vectors, quantum mechanics can also be formulated using density matrix, which is mathematically equivalent. suppose that a quantum system is in one of the states |ψ i , where i is an index, with probability p i . the definition of the density matrix is: more information about quantum computing can be found in @xcite . ## the types of algorithms algorithms at the intersection of nlp and quantum physics can be implemented either on quantum computers or classical computers. the former ones are usually called quantum algorithms and the latter ones are usually named quantum-inspired or quantum-like models which are classical algorithms. we refer to both design of classical nlp algorithms inspired by quantum physics and quantum algorithms to process nlp tasks as quantum nlp. we organize the main surveyed work in ## the modeling target both quantum-inspired algorithms and quantum algorithms can model different features in the language. we divide them into word representation (section 4.1) and composition (section 4.2). ## applications quantum nlp shows comparable or better performance compared with strong baselines for some tasks. we summarize the results of these algorithms in ## conclusion thus far, articles have demonstrated early success in representing and processing text using quantum computers. their design is scalable and when hardware becomes more powerful they can scale up the size of the meaning spaces and complexity of the tasks. the key to whether or not quantum computers will be used to deal with nlp in the future lies in whether quantum algorithms can show quantum advantage. meanwhile, quantum-inspired models have shown strong performance on classical computers for certain tasks, and have better interpretability. the main difficulty in this direction is that neural networks have already achieved high accuracy on many nlp tasks. nevertheless, it is still worthwhile to explore the mathematical framework of quantum mechanics where a strong expressive ability and a corresponding physical explanation are expected. finally, it can also be possible that if neither of the above two directions has major breakthroughs, then this quantum nlp field may temporarily lose research attention during a period of time.