Introduction

In this chapter, two preliminary symbolic processing experiments inspired by quantum mechanics are presented. The underlying idea is to treat a symbolic computation (described by a function $\mathfrak L$ of discrete logic values -- $\mathbb{F}$ for false, and $\mathbb{T}$ for true) as a physical experiment that obeys the laws of quantum mechanics. The input symbols are prepared as an initial state (an input state) for a particular quantum mechanical experimental arrangement. We assume that the input state can be represented in terms of a complete basis of eigenstates corresponding to an observable operator $S$ that writes down the symbol of a state. It is helpful to think of $S$ as an analogy of coordinate (position) observable $X$, as in the case of solving a Schrödinger equation (Equation 3.19). Every time a position-measurement is performed, the system yields a precise and well-defined location of each particle. In our case, the analogy of position is a well-defined symbol. An $S$-measurement can then yield one and only one of the eigenstates and the measured value can be one and only one of the eigenvalues (corresponding to $\mathbb{T}$ or $\mathbb{F}$).

Once the system is prepared, it is allowed to evolve without any external disturbance. The way the system evolves depends solely on the arrangement (it is helpful to think of this arrangement as different ways of putting ``pegs'' or ``traps'' in an analogous quantum physical system -- some sort of quantum billiard table), with the total energy of the system constant. In this case, the system can be described by a (classical) Hamiltonian $H$ and a unitary operator $U(t)$ associated with $H$. After a specific duration, the system is measured again against $S$, which yields an eigenstate of $S$ ($\mathbb{T}$ or $\mathbb{F}$). The corresponding symbol is then said to be the result of the corresponding symbolic computation. Specifically, suppose an input $\vec x_{in}$ of symbols ( $\vec x_{in} \in \{\mathbb{T}, \mathbb{F}\}^n$, where $n$ is the dimension of the input symbolic vector) is prepared as an input state $\phi_0$, the computation is carried out by an underlying physical system, as shown in the following diagram:

$$\begin{CD} \phi_0 @>{U(t)}>> \phi_t\\ @V{S}VV @VV{S}V \\ \vec x_{in} @>{\mathfrak L}>> \vec x_{out} \end{CD}$$

The evolution of the system (described by a wave function) is deterministic and continuous, both in spatial and temporal terms. However, since $S$ is a quantum measurement involving an abrupt collapse of the wave function, the outcome of the computation is discrete and irreversible. Notice that this scheme is stochastic. In other words, we can only predict the aggregate behavior of the system according to the absolute square of the projection the end-state on each eigenstate (corresponding to either $\mathbb{T}$ or $\mathbb{F}$), or

$$\sigma : \phi_t \to {\left(p_{\mathbb{T}},p_{\mathbb{F}}\right)}^m,$$

where $p_{\mathbb{T},m}$ ( $p_{\mathbb{F},m}$) is the probability of finding the system in $\mathbb{T}$ ($\mathbb{F}$) eigenstate for $m$-th output eigenstates with

$$\sum\limits_{k\in \{ \mathbb{T}, \mathbb{F}\}^m } {p_k}=1.$$

(In the experiments presented in this chapter, there is only one output, namely $m=1$). In this chapter it will also be demonstrated that the quantum computational scheme ``extends'' the classical computation but has a much richer structure. In other words, classical computation can be regarded as a special case of its quantum computational counterpart.