# Quantum Natural Language Processing: Challenges and Opportunities
## 2 Theoretical Background
### Quantum Background
#### 2.1.1 Fundamental Notions  
* **Qubits** is the basic unit of information in quantum computing. Similar to its classical counterpart, the bit, it can assume two distinct values of 0 or a 1. The difference is that whereas a bit must be either 0 or 1, a qubit can be 0, 1 or a superposition of both. Conventionally, possible states of a qubit are represented using the Dirac notation: \(\ket{0}\) and \(\ket{1}\). * **Superposition** is a principle of quantum mechanics allowing separate elements to assume many configuration arrangements, such that the general state is a combination of all of these possibilities. For the purpose of this work, notice that each qubit could take a superposition of both \(\ket{0}\) and \(\ket{1}\), assuming a representation obtained from the linear combination of the two states: \(\ket{\psi}=a\ket{0}+b\ket{1}\), where \(\ket{\psi}\) is a state that lives in a 2-dimensional complex vector space (Hilbert space), \(a\) and \(b\) two arbitrary complex coefficients whose sum of squares is 1 and \(\ket{0}\) and \(\ket{1}\) are orthonormal basis vectors, related to the respective measures 0 and 1. In the context of NLP, the superposition gives the possibility to better manage some pervasive natural language phenomena, such as lexical ambiguity and polysemy [29; 30]. For instance, the term _bar_ can have different meanings. It can indicate a place where alcoholic drinks are served or a piece of metal. Using the Dirac notation, the word _bar_ can be represented as a superposition state: \(\ket{bar}=a\ket{place}+b\ket{rod}\). * **Entanglement** is a non-local property that distinguishes qubits from the classic bit. It allows multiple states simultaneously, differently from the classical bits that can have only one value at a time. For instance, considering two entangled qubits in the Bell state, Bell states are specific quantum states of two qubits representing the simplest and maximal examples of quantum entanglement \(\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})\). These two qubits are separated and assigned to two different elements, \(a\) and \(b\). The measurement of qubits assigned to \(a\) gives \(\ket{0}\) or \(\ket{1}\) as a result. Due to the entanglement property, \(b\) must now obtain exactly the same measurement as \(a\). In particular, if \(a\) measures a \(\ket{0}\), \(b\) must measure the same, as \(\ket{00}\) is the only state where \(a\) qubit is a \(\ket{0}\). With regard to NLP, the assumption is that words that the grammatical structure that connects with specific relations of multiple words, form and entangle between quantum states in which the words are encoded [31]. * **Hilbert space** is defined as a vector space equipped with an inner product, which allows defining a distance function so that it becomes a complete metric space. In quantum mechanics, the possible states of a system are represented by state vectors located in a complex separable Hilbert space [32]. * **Quantum measurement** is the act of observing a qubit in superposition and resulting in one of the possible states. The act of observing or measuring a qubit collapses the superposition state and the qubit takes on a classical binary state of either 1 or 0. Thus, when a qubit in a certain superposition state \(\ket{\psi}=a\ket{0}+b\ket{1}\) is measured with respect to the standard basis for quantum computation \(\ket{0}\),\(\ket{1}\), it is possible to get either the result 0 with probability \(a^{2}\), or the result 1 with probability \(b^{2}\). Once a qubit has been measured, it stays in that state forever. In other words, measurement alters the state of a qubit, collapsing it from its superposition of \(\ket{0}\) and \(\ket{1}\) to the specific state consistent with the result of the measurement, i.e., if \(\ket{\psi}\) is observed to be in state \(\ket{0}\) through measurement, then the post-measurement state of the qubit will be \(\ket{0}\), and any subsequent measurements (in the same basis) will yield 0 with probability 1.