# Quantum Natural Language Processing: Challenges and Opportunities
## 4 Theoretical Quantum Approaches  
Since its release, DisCoCat model offers several advantages on a theoretical level; in particular, it has provided a syntax-aware algorithm able to compute the meaning of sentences and phrases using tensor product composition. Although it is originally inspired by some properties and protocols of quantum mechanics [75], its implementation was limited by the high computational cost it required. Addressing this issue, the work of [26] proposes a way to implement distributional compositional models, such as DisCoCat using quantum computers. The starting assumption is that quantum computation innately fits for managing high dimensional tensor product spaces. Computational problems related to tensor-product-based compositional semantics are addressed by the scalability of quantum systems. In addition, the work proposes an efficient sentence similarity algorithm. These kinds of algorithms are good candidates to have a real implementation on a quantum hardware, since noisy results can be tolerated. The proposed algorithm exploits the abstract connection between NLP and quantum information modeling density matrices using mixed states of quantum systems. Concerning performance, the quadratic speedup has been demonstrated in sentence similarity task. However, this performance improvement has only been demonstrated on a theoretical level, since it is based on the assumption that it is possible to use QRAM, which is currently unavailable [21]. An alternative approach born to compensate for this lack has been proposed by [49]. This work theorizes a full-stack pipeline for NLP on a NISQ device exploiting the classical ansatz parameters instead of the never realized QRAM of the original algorithm. Starting from the tensor structure already proposed in the non-NISQ friendly algorithm [26], every step of the theorized NLP pipeline is described in detail, specifying the tools and methods that would be possible to apply to be compliant with a quantum hardware. In particular, ansatze are used as lexical categories to map DisCoCat models to variational quantum circuits. These categories are connected following the grammar in order to build circuits for arbitrary syntactic units. Two methods have been proposed for optimizing the resulting circuits, aiming at the implementation on NISQ devices. Moreover, the work explores alternative quantum computing models, i.e., continuous- variable, adiabatic and measurement-based. Although this is an essentially theoretical work that leaves many open issues (for instance, the limitations of CFG to approximate some linguistic phenomena), this method has been followed by an actual implementation on a NISQ device [63]. Even the implementation has been intended as a proof of concept experiment, and if it is tested on a very small scale, it can be considered the first QNLP experiment running on quantum hardware. The research line proposed by these preliminary works has been continued and expanded in [31]. The vast majority of issues addressed by this study will be subsequently explored in further theoretical and practical work. First, it provides mathematical foundations for QNLP, exploiting diagrammatic theories provided by DisCoCat and CQM. Using these diagrammatic systems of representation, language can be interpreted in terms of quantum processes. Moreover, the resulting quantum representation of natural language can be embedded in quantum circuit form using the ZX-calculus [76]. The ZX-calculus acts as a translator from linguistic diagrams to quantum circuit. This step is crucial to allow a real implementation on quantum hardware. This approach relies on the advocated intrinsic quantum-native nature of QNLP, allowing the possibility to merge meaning and structure of language in a single unified quantum model able to represent both syntactic and semantic levels. Another interesting cue triggered by the work of [31] is the potential meaning-awareness of the QNLP, an aspect that puts it in contrast with the vast majority of state-of-the-art machine learning approaches.