11institutetext:  Department of Chemistry, University of York, YO10 5DD, York,
UK 22institutetext: Department of Computer Science, University of York, YO10
5DD, York, UK

# Boolean logic gate design principles in unconventional computers: an NMR
case study

Matthias Bechmann 11<EMAIL_ADDRESS>Angelika Sebald 11
<EMAIL_ADDRESS>Susan Stepney 22<EMAIL_ADDRESS>
###### Abstract

We present a general method for analysing novel computational substrates to
determine which of their parameters can be manipulated to exhibit the complete
set of 2-input boolean logical operations. We demonstrate this approach with
an NMR-based case study, showing which NMR parameters can be used to perform
boolean logic.

###### keywords:

NMR, boolean logic, canalising functions, universal gates, spin

##  1 Introduction

There is much work on _in materio_ computing: exploiting unconventional
material substrates and their dynamical properties to perform computation, and
examining their computational properties and abilities. One of the more
advanced is optical computing [33, 34]. Other, more exotic, substrates include
nuclear spins in NMR experiments [16, 17, 24, 6], liquid crystals [12, 13,
14], conductive media [21, 22], reaction-diffusion chemical systems [19, 23,
27, 32], DNA [3, 4], and even slime moulds [2, 31].

The aim is to allow the material to do what comes naturally, under control of
physical laws, and to exploit this natural dynamics as an efficient form of
computation [29, 30, 18]. The question arises: given some novel substrate, how
to analyse its properties to determine whether it is a suitable medium for
computation, and, if so, how it can be manipulated to perform computation in a
manner best suited to that substrate.

Here we tackle a part of that problem: analysing a novel substrate to
determine how it can be used to perform boolean logical operations. We present
the design principles through a case study of using bulk nuclear spins, in the
context of NMR (nuclear magnetic resonance) experiments.

##  2 Theory and Background

###  2.1 Boolean functions and logic gates

The NAND and NOR logic gates are both _universal_ , in that either can be used
to construct all the other boolean 2-input logic gates. However, to do so,
several such gates may be required. In an implementation, it is often more
important to minimise the circuitry (the number of actual gates) than to
minimise the number of types of gates.

Logic gates can be classified in terms of their symmetry properties [28, 11].
In terms of minimising circuitry, gates can be classified in terms of
equivalence classes on permutations (rewiring) of inputs, and on negation of
inputs and/or outputs (i.e. adding inverters, important in cases where they
are significantly _cheaper_ to implement than binary gates [9]). There are
four such equivalence classes for the 16 boolean 2-input logic gates (Tables 1
and 2).

class | members
---|---
0 | T, F
1 |  $A$, NOT $A$, $B$, NOT $B$
2 |  $A$ AND $B$; $A$ NAND $B$; NOT $A$ AND $B$, $A$ AND NOT $B$, …
3 |  $A$ XOR $B$, NOT ($A$ XOR $B$)
Table 1: The four equivalence classes of the 16 boolean 2-input logic gates. These correspond to equivalence classes under permutations of inputs and negation of the inputs and/or outputs [9], and to the different kinds of canalising functions [10].  $A$ | $B$ | T | $B$ |  $A$ NAND $B$ |  $A$ XOR $B$
---|---|---|---|---|---
0 | 0 | 1 | 0 | 1 | 0
0 | 1 | 1 | 1 | 1 | 1
1 | 0 | 1 | 0 | 1 | 1
1 | 1 | 1 | 1 | 0 | 0
Table 2: Truth tables of examples of the four classes of boolean logic gates,
for each possible input value of $A$ and $B$. Class 0 (example T) is
independent of either input value. Class 1 (example $B$) is independent of one
of the input values (here, $A$) for all possible inputs. Class 2 (example $A$
NAND $B$) is independent of one of the input values when the other has a
particular value (here, it it independent of the value of $B$ when $A$ has the
value $0$). Class 3 (example $A$ XOR $B$) depends on both input values for all
inputs.

The same classification is found by considering canalising functions [10].
These are functions where the output is independent of one (or more) of the
inputs, for one (or more) input values. Class 0 consists of the constant
functions: the output is completely independent of the inputs. Class 1
consists of the strongly canalising functions: the output is independent of
one of the inputs (for example, the function $B$ is independent of the value
of input $A$). Class 2 consists of the weakly canalising functions: the output
is independent of one of the inputs when the other input has a specific value
(for example, the function $A$ NAND $B$ is independent of the value of input
$B$ when the value of input $A$ is false). Class 3 consists of the non-
canalising functions: the output is determined by both inputs.

We use these symmetries/canalising properties of the gates (Figure 1) to look
for analogous properties exhibited by the substrate that indicates a natural
implementation route.

Figure 1: Logic-gates patterns and their different symmetries as visible from
the two-dimensional representations of the canalising functions gate classes
0, 1, 2 and 3.

###  2.2 Nuclear spin dynamics

The most common application of NMR spectroscopy is that as a tool for
structure elucidation of condensed matter in general, and of molecules in the
liquid state in particular. The quantised nature of nuclear spin can also be
assigned to the notion of a qubit in quantum computations [26]. Nuclear spins
have also been used as a substrate to implement classical computation
paradigms such as binary or continuous logic gates and circuits [24, 6].

A major reason for these computational applications to choose nuclear magnetic
spins as the implementation platform is the rigour by which nuclear spin
dynamics are described by quantum mechanics. In addition, the accuracy by
which the macroscopically measured signal in an NMR experiment can be related
to the underlying microscopic spin dynamics, using a density matrix approach,
is nearly unrivalled by any other spectroscopic technique. In order to develop
the formal relationship between the properties of logic gates and the quantum
mechanical expressions describing the spin dynamics in a NMR experiment, we
give a short summary of the necessary formalisms. For more details see
textbooks on NMR [20]. Here we consider only uncoupled spins $S=1/2$ in the
liquid state.

The time evolution of an initial spin state vector
$\Ket{\psi\left(t_{a}\right)}$ is described as

$\displaystyle\Ket{\psi\left(t\right)}$ $\displaystyle=$
$\displaystyle\mathcal{U}\left(t,t_{a}\right)\Ket{\psi\left(t_{a}\right)}$ (1)

where $\mathcal{U}\left(t,t_{a}\right)$ is the time propagator describing the
spin dynamics at every given point in time. The general orientation of the
spin vector $\Ket{\psi}$ is [20]

$\Ket{\psi}=\left(\begin{array}[]{c}\cos\frac{\theta_{\mathrm{s}}}{2}\mathrm{e}^{-\mathrm{i}\frac{1}{2}\phi_{\mathrm{s}}}\\\
\sin\frac{\theta_{\mathrm{s}}}{2}\mathrm{e}^{+\mathrm{i}\frac{1}{2}\phi_{\mathrm{s}}}\end{array}\right)$
(2)

where $\theta_{\mathrm{s}}$ and $\phi_{\mathrm{s}}$ are the polar and azimuth
angles. Its three-dimensional representation is given by

$\left(\begin{array}[]{c}\Braket{\psi}{I_{x}}{\psi}\\\
\Braket{\psi}{I_{y}}{\psi}\\\
\Braket{\psi}{I_{z}}{\psi}\end{array}\right)=\frac{1}{2}\left(\begin{array}[]{c}\sin\theta_{\mathrm{s}}\cos\phi_{\mathrm{s}}\\\
\sin\theta_{\mathrm{s}}\sin\phi_{\mathrm{s}}\\\
\cos\theta_{\mathrm{s}}\end{array}\right)$ (3)

describing a general Cartesian vector orientation (see Figure 2), where
$I_{x}$, $I_{y}$ and $I_{z}$ are basis spin operators [25].

Figure 2: Spin state vector orientation of $\Ket{\psi}$ in its Cartesian
representation

The time propagation of the macroscopic NMR signal is described by the density
matrix $\rho(t)=\overline{\Ket{\psi\left(t\right)}\Bra{\psi\left(t\right)}}$
as

$\displaystyle\rho(t)$ $\displaystyle=$
$\displaystyle\mathcal{U}\left(t,t_{a}\right)\rho(t_{a})\mathcal{U}^{\dagger}\left(t,t_{a}\right)$
(4)

where the bar signals the ensemble average. The thermal equilibrium density
matrix is [20]

$\rho_{z}^{\mathrm{eq}}=\frac{1}{2}\mathbbm{1}+\frac{1}{2}\lambda_{\mathrm{B}}I_{z}$
(5)

where $\lambda_{\mathrm{B}}=\hbar\gamma B_{0}/(k_{\mathrm{B}}T)$ defines a
Boltzmann factor, scaling the separation of spin energy levels, that can be
interpreted as a spin polarisation along the $z$-axis.

The NMR system Hamiltonian and generator of the time evolution propagators for
isolated, uncoupled spins is

$\mathcal{H}=\mathcal{H}_{\mathrm{CS}}+\mathcal{H}_{\mathrm{\mathrm{rf}}}$ (6)

where $\mathcal{H}_{\mathrm{CS}}$ and $\mathcal{H}_{\mathrm{rf}}$ are the
chemical shielding and radio frequency (r.f.) Hamiltonian, respectively. The
explicit representation of the r.f. Hamiltonian is particularly simple in the
rotating reference frame (RRF) as

$\displaystyle\mathcal{H}_{\mathrm{rf}}$ $\displaystyle=$
$\displaystyle\omega_{\mathrm{p}}I_{z}+\kappa_{\mathrm{p}}\left(I_{x}\cos\phi_{\mathrm{p}}+I_{y}\sin\phi_{\mathrm{p}}\right)$
(7)

where $\omega_{\mathrm{p}}$ is a frequency offset (relative to the frequency
of RRF), and $\kappa_{\mathrm{p}}$ and $\phi_{\mathrm{p}}$ are the amplitude
and phase of the pulse. Figure 3(a) summarises the behaviour of the
magnetisation vector $\boldsymbol{M}$ (Eqs. (1)–(43)) under the influence of a
r.f. pulse; Figure 3(b) depicts the relevant parameters.

Figure 3: NMR single-pulse experiment: (a) rotation of the magnetisation
vector $\boldsymbol{M}$ by a r.f. pulse
$R_{\phi_{\mathrm{p}}}\left(\beta\right)$ with
$\phi_{\mathrm{p}}=\frac{\pi}{2}$ and
$\beta=\kappa_{\mathrm{p}}\tau_{\mathrm{p}}=\frac{\pi}{2}$; (b) the relevant
parameters describing the single-pulse NMR experiment (pulse amplitude
$\kappa_{\mathrm{p}}$, pulse duration $\tau_{\mathrm{p}}$, pulse phase
$\phi_{\mathrm{p}}$, pulse frequency $\omega_{\mathrm{p}}$, free evolution
delay $\tau{}_{\mathrm{d}}$ and acquisition phase $\phi_{\mathrm{a}}$).

Pulses applied to spins resonating at the rotation frequency of the RRF are
described by the system Hamiltonian

$\displaystyle\mathcal{H}=\mathcal{H}_{\mathrm{rf}}$ $\displaystyle=$
$\displaystyle\kappa_{\mathrm{p}}\left(I_{x}\cos\phi_{\mathrm{p}}+I_{y}\sin\phi_{\mathrm{p}}\right)$
(8)

and the overall system Hamiltonian for uncoupled isolated spins $S=1/2$ is

$\displaystyle\mathcal{H}$ $\displaystyle=$
$\displaystyle\mathcal{H}_{\mathrm{CS}}+\mathcal{H}_{\mathrm{\mathrm{rf}}}:\mbox{during
pulse}$ $\displaystyle\mathcal{H}$ $\displaystyle=$
$\displaystyle\mathcal{H}_{\mathrm{CS}}\,:\mbox{during free evolution}$ (9)

including a chemical shielding offset $\mathcal{H}_{\mathrm{CS}}$ from the RRF
frequency.

The general form of the time evolution propagator in NMR is

$\displaystyle\mathcal{U}\left(t_{b},t_{a}\right)$ $\displaystyle=$
$\displaystyle\mathcal{T}\exp\left\\{-\mathrm{i}\int_{t_{a}}^{t_{b}}\mathcal{H}\left(t\right)\mathrm{d}t\right\\}$
(10)

where $\mathcal{T}$ is the Dyson time-ordering operator [25].

Dependent on the symmetry of the Hamiltonian, different (simpler) expressions
for the propagator can be formulated

$\displaystyle\mathcal{H}\left(t\right)=\mathcal{H}$
$\displaystyle\rightarrow$
$\displaystyle\mathcal{U}\left(t_{b},t_{a}\right)=\exp\left\\{-\mathrm{i}\mathcal{H}\left(t_{b}-t_{a}\right)\right\\}$
$\displaystyle\mathrm{time\ independent}$
$\displaystyle\left[\mathcal{H}\left(t^{\prime}\right),\mathcal{H}\left(t^{\prime\prime}\right)\right]=0$
$\displaystyle\rightarrow$
$\displaystyle\mathcal{U}\left(t_{b},t_{a}\right)=\exp\\{-\mathrm{i}{\textstyle\int}_{t_{a}}^{t_{b}}\mathrm{d}t^{\prime}\mathcal{H}\left(t^{\prime}\right)\\}$
$\displaystyle\mathrm{self-commuting}$
$\displaystyle\mathcal{H}\left(t_{a}+\tau\right)=-\mathcal{H}\left(t_{b}-\tau\right)$
$\displaystyle\rightarrow$
$\displaystyle\mathcal{U}\left(t_{b},t_{a}\right)=1\>\mbox{; anti-symmetric}$
(14) $\displaystyle\mathcal{U}\left(t_{b},t_{a}\right)=\pm 1\>\mbox{; cyclic}$

In the case of a hard pulse, a so-called $\delta$ pulse is usually a valid
description of the time propagator

$\displaystyle\mathcal{U}\left(t_{b},t_{a}\right)$ $\displaystyle=$
$\displaystyle\exp\left\\{-\mathrm{i}\mathcal{H}_{\mathrm{rf}}\tau_{\mathrm{p}}\right\\};\,\tau_{\mathrm{p}}=t_{b}-t_{a}$
(15) $\displaystyle=$
$\displaystyle\exp\left\\{-\mathrm{i}\kappa_{\mathrm{p}}\tau_{\mathrm{p}}\left(I_{x}\cos\phi_{\mathrm{p}}+I_{y}\sin\phi_{\mathrm{p}}\right)\right\\}$
$\displaystyle=$ $\displaystyle
R_{\phi_{\mathrm{p}}}\left(\beta\right);\,\beta=\kappa_{\mathrm{p}}\tau_{\mathrm{p}}$

which is equivalent to the rotation operation
$R_{\phi_{\mathrm{p}}}\left(\beta\right)$. It generates a rotation by an angle
$\beta$ about an axis in the $xy$-plane with azimuth angle
$\phi_{\mathrm{p}}$. For a sequence of $\delta$ pulses the propagator can be
factorised as

$\displaystyle\mathcal{U}\left(t_{c},t_{a}\right)$ $\displaystyle=$
$\displaystyle\mathcal{U}_{2}\left(t_{c},t_{b}\right)\mathcal{U}_{1}\left(t_{b},t_{a}\right);\,\tau_{\mathrm{p1}}=t_{b}-t_{a}\,\mbox{and
}\tau{}_{\mathrm{p2}}=t_{c}-t_{b}$ (16) $\displaystyle=$ $\displaystyle
R_{\phi{}_{\mathrm{p}2}}\left(\beta_{2}\right)R_{\phi_{\mathrm{p}1}}\left(\beta_{1}\right);\,\beta_{1}=\kappa_{\mathrm{p}1}\tau_{\mathrm{p}1};\,\beta_{2}=\kappa{}_{\mathrm{p}2}\tau{}_{\mathrm{p2}}$

The explicit form of these propagators is equivalent to rotation operators in
two dimensions and is [20]

$\displaystyle R_{x}\left(\beta\right)$ $\displaystyle=$
$\displaystyle\mathrm{e}^{-\mathrm{i}\beta
I_{x}}=\left(\begin{array}[]{cc}\cos\frac{\beta}{2}&-\mathrm{i}\sin\frac{\beta}{2}\\\
-\mathrm{i}\sin\frac{\beta}{2}&\cos\frac{\beta}{2}\end{array}\right)$ (19)
$\displaystyle R_{y}\left(\beta\right)$ $\displaystyle=$
$\displaystyle\mathrm{e}^{-\mathrm{i}\beta
I_{y}}=\left(\begin{array}[]{cc}\cos\frac{\beta}{2}&-\sin\frac{\beta}{2}\\\
\sin\frac{\beta}{2}&\cos\frac{\beta}{2}\end{array}\right)$ (22) $\displaystyle
R_{z}\left(\beta\right)$ $\displaystyle=$
$\displaystyle\mathrm{e}^{-\mathrm{i}\beta
I_{z}}=\left(\begin{array}[]{cc}\mathrm{e}^{-\mathrm{i}\frac{\beta}{2}}&0\\\
0&\mathrm{e}^{+\mathrm{i}\frac{\beta}{2}}\end{array}\right)$ (25)
$\displaystyle R_{\phi}\left(\beta\right)$ $\displaystyle=$
$\displaystyle\mathrm{e}^{-\mathrm{i}\beta\left(I_{x}\cos\phi+I_{y}\sin\phi\right)}=\left(\begin{array}[]{cc}\cos\frac{\beta}{2}&-\mathrm{i}\sin\frac{\beta}{2}\mathrm{e}^{-\mathrm{i}\phi}\\\
-\mathrm{i}\sin\frac{\beta}{2}\mathrm{e}^{+\mathrm{i}\phi}&\cos\frac{\beta}{2}\end{array}\right)$
(28) $\displaystyle=$ $\displaystyle
R_{z}\left(\phi\right)R_{x}\left(\beta\right)R_{z}\left(-\phi\right)$ (29)

After a pulse $R_{\phi_{\mathrm{p}}}\left(\beta\right)$ with phase
$\phi_{\mathrm{p}}=\frac{\pi}{2}$ and flip angle $\beta=\frac{\pi}{2}$ the
thermal equilibrium density matrix $\rho_{z}^{\mathrm{eq}}$ is transformed
according to

$\displaystyle
R_{\frac{\pi}{2}}\left(\frac{\pi}{2}\right)\rho_{z}^{\mathrm{eq}}R_{\frac{\pi}{2}}^{\dagger}\left(\frac{\pi}{2}\right)$
$\displaystyle=\frac{1}{2}\mathbbm{1}+\frac{\lambda_{\mathrm{B}}}{2}$
$\displaystyle\left(\begin{array}[]{cc}0&1\\\ 1&0\end{array}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\mathbbm{1}+\frac{1}{2}\lambda_{\mathrm{B}}I_{x}$
$\displaystyle=$ $\displaystyle\rho_{x}$ (33)

yielding spin polarisation along the $+x$ direction.

A r.f. pulse $R_{\phi_{\mathrm{p}}}\left(\beta\right)$ applied to an initial
state $\rho^{\left(i\right)}$ generates a spin density matrix that can be
expressed in terms of its final polar coordinates
$\rho\left(\phi_{\mathrm{s}},\theta_{s}\right)=\overline{\Ket{\psi}\Bra{\psi}}$
(Eq. (2)) or as a function of the pulse parameters rotating an initial state
$\rho^{\left(i\right)}\left(\phi_{\mathrm{p}},\beta\right)$. For example when
starting from $\rho^{\left(z\right)}=\rho_{z}^{\mathrm{eq}}$ the final state
is

$\displaystyle\rho^{\left(z\right)}\left(\phi_{\mathrm{p}},\beta\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\mathbbm{1}+\frac{\lambda_{\mathrm{B}}}{2}\left(\begin{array}[]{cc}\cos\beta&-\mathrm{i}\sin\beta\mathrm{e}^{-\mathrm{i}\phi_{\mathrm{p}}}\\\
-\mathrm{i}\sin\beta\mathrm{e}^{+\mathrm{i}\phi_{\mathrm{p}}}&-\cos\beta\end{array}\right)$
(36)

and the relation
$\rho\left(\phi_{\mathrm{s}},\theta_{s}\right)=\rho^{\left(z\right)}\left(\phi_{\mathrm{p}},\beta\right)$
holds for
$\left(\phi_{\mathrm{s}},\theta_{s}\right)=\left(\phi_{\mathrm{p}}-\frac{\pi}{2},\beta\right)$.

Equivalently to the calculation of the three-dimensional spin-vector
orientation in Eq. (3) from the two-dimensional spin state $\Ket{\psi}$ (Eq.
(2)), the three-dimensional magnetisation vector $\boldsymbol{M}$ can then be
calculated from any given two-dimensional density matrix $\rho$ as

$\displaystyle\boldsymbol{M}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{c}\overline{\Braket{I_{x}}}\\\
\overline{\Braket{I_{y}}}\\\
\overline{\Braket{I_{z}}}\end{array}\right)=\left(\begin{array}[]{c}\mbox{Tr}\left\\{\rho
I_{x}\right\\}\\\ \mbox{Tr}\left\\{\rho I_{y}\right\\}\\\
\mbox{Tr}\left\\{\rho I_{z}\right\\}\end{array}\right)$ (43)

In the case of single isolated spins this also implies the equivalence in
interpretation of the spin vector orientation in Figure 2 and the
magnetisation vector $\boldsymbol{M}$.

In general a NMR pulse sequence can consist of any number and parametrisation
of r.f. pulses and free evolution delays. This provides for numerous options
for the implementation of e.g. logic gates. The most useful parametrisation in
the following is the one describing the NMR signal as a function of the pulse
sequence, $\rho^{\left(i\right)}\left(\phi_{\mathrm{p}},\beta\right)$.

##  3 Logic Gates from NMR parameters

###  3.1 Classification of NMR parameters

The most common parameters describing a NMR experiment, open for use as
control parameters to implement logic operations, are
$\left\\{\kappa_{\mathrm{p}},\phi_{\mathrm{p}},\tau_{\mathrm{p}},\omega_{\mathrm{p}},\tau_{\mathrm{d}},\phi_{\mathrm{a}}\right\\}$:
pulse amplitude, pulse phase, pulse duration, pulse frequency, free evolution
delay, and receiver phase, respectively (see Figure 3).

A heuristic classification rule has been given elsewhere [24], separating
logic gates based on the relation between the experimental NMR parameters
chosen:

  1. 1.

if the effect of the first parameter cannot be compensated for by setting the
second parameter (canalising input value), then
$\mbox{AND},>,<\mbox{NOR},\mbox{OR},\leq,\geq,\mbox{NAND}$ gates can be
constructed (asymmetric gates);

  2. 2.

if the effect of the first parameter can be compensated by a setting of the
second parameter, then XOR and XNOR gates can be constructed (symmetric
gates).

This classification of logic gates seamlessly integrates in a generalised
description by using the concept of canalising functions [10] and equivalence
classes [9]. Fixing one of the inputs of a logic gate ($A$ or $B$) is a
_canalising input value_ if changing the other (unfixed) input does not alter
the gate output. The number of all possible canalising input values for a
given logic gate for all possible inputs states is used as a criterion to
assign logic gates to one of four classes (see Table 3):

class | canalising input values for fixed: | $A$ | $B$
---|---|---|---
0 | T | 2 | 2
1 | $B$ | 0 | 2
2 |  $A$ NAND $B$ | 1 | 1
3 |  $A$ XOR $B$ | 0 | 0
Table 3: Number of canalising input values for the four gate classes.
Demonstrated for one representative member of every class: T, $B$, $A$ NAND
$B$, $A$ XOR $B$. The respective truth tables for these four gates are shown
in Table 2.

class 0

two canalising input values for either of the two inputs $A$ and $B$

class 1

two canalising input values for exactly one of the inputs $A$ or $B$

class 2

one canalising input values for either of the two inputs $A$ and $B$

class 3

no canalising input values for either inputs $A$ and $B$

These four classes also show unique symmetry patterns in their two-dimensional
representations (see Figure 1). Rows and columns of equal coloured squares
signal the presence of a canalising input. These patterns can be used to map
functions $f(x1,x2)$ to corresponding canalising functions and, therefore, the
logic gate(s) they can naturally implement are readily identified.

According to our previous definitions [24] a strong parameter would generate a
canalising function for at least one of its states (class 0, 1 and 2), because
altering the other parameter causes no change in the NMR output. On the other
hand, for a weak parameter the output would always change (class 3).

In the following we demonstrate how the abstract concept of canalising
functions relates to the symmetries and commutation relations of the NMR
Hamiltonian, the time evolution propagator, and the experimental output of a
NMR experiment.

###  3.2 Canalising input values in NMR context

Here we consider a system Hamiltonian that consists only of the
$\mathcal{H}_{\mathrm{rf}}$ term. Hence, we are in the single spin, strong
pulse, on-resonant regime, and for simplicity we only consider the
experimental parameters
$\kappa_{\mathrm{p}},\phi_{\mathrm{p}},\tau_{\mathrm{p}}$ (r.f. pulse
amplitude, phase and duration) for logic gate generation.

The NMR r.f. pulse propagator
$R_{\phi_{\mathrm{p}}}\left(\beta\right)=R_{z}\left(\phi_{\mathrm{p}}\right)R_{x}\left(\beta\right)R_{z}\left(-\phi_{\mathrm{p}}\right)$
(Eq. (29)) is the general rotation operator about an axis in the traverse
$xy$-plane of the RRF. It therefore commutes with a particular spin state
($I_{\phi_{\mathrm{p}}}$) in the transverse plane for a given value
$\phi_{\mathrm{p}}$ (e.g. for $\phi_{\mathrm{p}}=0$;
$\left[R_{0}(\beta),I_{x}\right]=0$ independent of the value of $\beta$).
However, $R_{\phi_{\mathrm{p}}}\left(\beta\right)$ will never commute with the
thermal equilibrium state $\rho_{z}^{\mathrm{eq}}$ ($\sim I_{z}$) (Eq. (5)),
which is perpendicular to the $xy$-plane. For example, a
$R_{0}\left(\frac{\pi}{2}\right)$ pulse applied to $z$-magnetisation ($\sim
I_{z}$) will flip it to the $-y$ direction, and therefore change the spin
state and its orientation. A subsequent pulse applied using
$R_{-\frac{\pi}{2}}\left(\frac{\pi}{2}\right)$ will leave it unaltered, since
the system is in the $-I_{y}$ spin state, an eigenstate of
$R_{-\frac{\pi}{2}}\left(\frac{\pi}{2}\right)$ and, therefore, a canalising
input is generated in this second step. One can postulate now that a
_canalising input_ is generated by an r.f. pulse if:

  1. 1.

$R_{\phi_{\mathrm{p}}}\left(\beta\right)$ leaves the system state unaltered
(eigenstate;$\left[R_{\phi_{\mathrm{p}}}(\beta),\rho\right]=0$),

  2. 2.

$R_{\phi_{\mathrm{p}}}\left(\beta\right)=\mathbbm{1}$, the unity operator.

In the following this behaviour and the possibility of generating canalising
input values is analysed. First we consider single-pulse experiments assuming
different initial system-state preparations $\rho^{\left(i\right)}$. Second we
consider experiments composed of more than one pulse.

####  3.2.1 Single-pulse gates

The signal as detected during a NMR experiment is not the effect of the full
spin magnetisation vector $\boldsymbol{M}$ as given in Eq. (43) but only its
projection into the $xy$-plane [20]. Hence, the physically meaningful
quantities that can be measured by NMR are the magnetisation vector components
$M_{x}=\overline{\Braket{I_{x}}}$ and $M_{y}=\overline{\Braket{I_{y}}}$,
describing the orientational distribution of this projection, and the
magnitude $M_{xy}=\sqrt{\Braket{I_{x}}^{2}+\Braket{I_{y}}^{2}}$ describing the
total amount of magnetisation present in the $xy$-plane. The functional
structure of $M_{x}$, $M_{y}$ and $M_{xy}$ is determined by the r.f. pulse
$R_{\phi_{\mathrm{p}}}\left(\beta\right)$ and the initial spin state
$\rho^{\left(i\right)}$ to which the r.f. pulse is applied. $M_{x}$, $M_{y}$
and $M_{xy}$ are therefore functions of pulse phase $\phi_{\mathrm{p}}$, pulse
flip angle $\beta=\kappa_{\mathrm{p}}\tau_{\mathrm{p}}$ and the initial
direction of the spin magnetisation.

The spin magnetisation can assume every possible orientation, while the r.f.
pulse and therefore the rotation axis of the spin magnetisation is restricted
to the $xy$-plane. It is instructive to examine scenarios where the initial
spin state $\rho^{\left(i\right)}$ is either perpendicular to the $xy$-plane
and never commutes with the r.f. pulse operator
$R_{\phi_{\mathrm{p}}}\left(\beta\right)$, or where it is coplanar to it and
therefore can commute.

##### Starting from thermal equilibrium state

The most simple and natural initial spin state is the one the system assumes
at thermal equilibrium $\rho^{\left(i\right)}=\rho_{z}^{\mathrm{eq}}$ (Eq.
(5)). Here the spin polarisation is pointing along the $z$-axis, perpendicular
to the $xy$-plane and $R_{\phi_{\mathrm{p}}}(\beta)$ never commutes with it.
$\rho_{z}^{\mathrm{eq}}$ transforms under the influence of a pulse
$R_{\phi_{\mathrm{p}}}(\beta)$ as

$\displaystyle\rho^{\left(z\right)}\left(\phi_{\mathrm{p}},\beta\right)$
$\displaystyle=$ $\displaystyle
R_{\phi_{\mathrm{p}}}(\beta)\rho_{z}^{\mathrm{eq}},R_{\phi_{\mathrm{p}}}^{\dagger}(\beta)$
(44)

After this single pulse the spin magnetisation vector $\boldsymbol{M}$ (Eq.
(43)) is a function of pulse flip angle $\beta$ and pulse phase
$\phi_{\mathrm{p}}$

$\displaystyle\left(\begin{array}[]{c}M_{x}\\\ M_{y}\\\
M_{z}\end{array}\right)=\left(\begin{array}[]{c}\mathrm{Tr}\left\\{\rho^{\left(z\right)}(\phi_{\mathrm{p}},\beta)I_{x}\right\\}\\\
\mathrm{Tr}\left\\{\rho^{\left(z\right)}(\phi_{\mathrm{p}},\beta)I_{y}\right\\}\\\
\mathrm{Tr}\left\\{\rho^{\left(z\right)}(\phi_{\mathrm{p}},\beta)I_{z}\right\\}\end{array}\right)=\frac{\lambda_{\mathrm{B}}}{4}\left(\begin{array}[]{c}\sin\phi_{\mathrm{p}}\sin\beta\\\
-\cos\phi_{\mathrm{p}}\sin\beta\\\ \cos\beta\end{array}\right)$ (54)

and the NMR measurable quantities $M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)=\frac{\lambda_{\mathrm{B}}}{4}\left|\sin\beta\right|$
are readily determined. These quantities are functions of the two pulse
parameters $\phi_{\mathrm{p}}$ and $\beta$ just like the binary logic gates
are functions of the two inputs $A$ and $B$ (Table 2). An instructive way to
analyse $M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$, as to which logic gates can be
implemented by them, is by examining their representation as two-dimensional
contour plots. These are shown in Figure 4.

Figure 4: Contour plots of the NMR detectable quantities (a)
$M_{x}=\overline{\Braket{I_{x}}}$, (b)$M_{y}=\overline{\Braket{I_{y}}}$ and
(c)
$M_{xy}=\sqrt{\overline{\Braket{I_{x}}}^{2}+\overline{\Braket{I_{y}}}^{2}}$
(Eq. (54)) as a function of the pulse parameters $\phi_{\mathrm{p}}$ and
$\beta$. The initial spin polarisation has been along the $z$-axis
($\rho_{z}^{\mathrm{eq}}$) and $\lambda_{\mathrm{B}}=1$ has been assumed. The
ranges for $\phi_{\mathrm{p}}$ and $\beta$ have been chosen such that the only
symmetry operation necessary to generate a full, infinite plot are horizontal
and vertical translations.

A comparison with the two-dimensional sketches of 2-input logic gates in
Figure 1 immediately reveals agreements and disagreements in symmetries.

In principle the functions $M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ are continuous in
$\phi_{\mathrm{p}}$ and $\beta$ whereas logic gates are boolean functions of
$A$ and $B$ that can only assume the discrete values of
$\left\\{0,1\right\\}$. In order to map the continuous functions in Figure 4
to the four possible discrete sets ($A$,$B$) of a logic gate one has to find
four discrete pairs $\left(\phi_{\mathrm{p}},\beta\right)$ at which to
evaluate the continuous functions and where the symmetry pattern of the
desired logic gate results.

For example from Figure 4(a) depicting $M_{x}$, one can directly identify the
symmetry pattern corresponding to a class 3 gate in Figure 1. In order to
implement the class 3 (XOR) gate (Table 2) one needs to define four discrete
value sets
$\left(\phi_{\mathrm{p}}=\phi_{\mathrm{p}}^{A},\beta=\beta^{B}\right)$ (with
$A$,$B$ $\in\\{0,1\\}$). Inspection of Figure 4(a) immediately suggests the
positive and negative extrema as possible candidates: Selecting the pair
$\left(\phi_{\mathrm{p}}^{A=0},\beta^{B=0}\right)=\left(\frac{\pi}{2},-\frac{\pi}{2}\right)$
the detected output is
$M_{x}\left(\phi_{\mathrm{p}}^{A=0}=\frac{\pi}{2},\beta^{B=0}=-\frac{\pi}{2}\right)=-0.25$.
In the same fashion, $M_{x}\left(\frac{\pi}{2},\frac{\pi}{2}\right)=0.25$,
$M_{x}\left(\frac{3\pi}{2},-\frac{\pi}{2}\right)=0.25$ and
$M_{x}\left(\frac{3\pi}{2},\frac{\pi}{2}\right)=-0.25$ are calculated for the
remaining XOR gate input configurations. The values of
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ in Figure 4 are calculated
assuming $\lambda_{\mathrm{B}}=1$. Mapping these values to the final boolean
values $\left\\{0,1\right\\}$ is achieved by scaling them by a factor of 4.

class | $\phi_{\mathrm{p}}^{A}$ | $\beta^{B}$ | Output=$M_{x}\left(\phi_{p}^{A},\beta^{B}\right)$ | gate
---|---|---|---|---
0 | 1 | 0 | 1 | 00 | 01 | 10 | 11
0 | $\frac{\pi}{2}$ | $\frac{5\pi}{2}$ | $\frac{\pi}{2}$ | $\frac{5\pi}{2}$ | 0.25 | 0.25 | 0.25 | 0.25 | T
1 | $\frac{\pi}{2}$ | $\frac{5\pi}{2}$ | $-\frac{\pi}{2}$ | $\frac{\pi}{2}$ | -0.25 | 0.25 | -0.25 | 0.25 | $B$
2 | $\pi$ | $\frac{3\pi}{2}$ | $0$ | $\frac{\pi}{2}$ | 0 | 0 | 0 | -0.25 |  $A$ NAND $B$
3 | $\frac{\pi}{2}$ | $\frac{3\pi}{2}$ | $-\frac{\pi}{2}$ | $\frac{\pi}{2}$ | -0.25 | 0.25 | 0.25 | -0.25 |  $A$ XOR $B$
Table 4: Some selected values $\phi_{p}$ and $\beta$ to generate one
representative gate of every gate class using
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$ as shown in Figure 4(a).

A class 3 gate is characterised by the absence of any canalising input (Table
3). A change in $\phi_{\mathrm{p}}^{A}$ or $\beta^{B}$ will therefore always
change the value $M_{x}\left(\phi_{\mathrm{p}}^{A},\beta^{B}\right)$. In order
to change one of the parameters $\phi_{\mathrm{p}}^{A}$ or $\beta^{B}$ and
achieve the same result in $M_{x}\left(\phi_{\mathrm{p}}^{A},\beta^{B}\right)$
one can take advantage of the periodicity of the trigonometric functions in
Eq. (54) and in this way
$M_{x}\left(\frac{\pi}{2},-\frac{\pi}{2}\right)=M_{x}\left(\frac{5\pi}{2},-\frac{\pi}{2}\right)=-0.25$
and
$M_{x}\left(\frac{\pi}{2},\frac{\pi}{2}\right)=M_{x}\left(\frac{5\pi}{2},\frac{\pi}{2}\right)=0.25$
can be implemented. This gate is evaluating $\phi_{\mathrm{p}}^{A}$ at values
separated by $2\pi$ and the gate is therefore independent of a change in
$\phi_{\mathrm{p}}^{A}$ no matter which of its two permitted values
$\beta^{B}$ assumes. A change in $\beta^{B}$, however, will always change
$M_{x}\left(\phi_{\mathrm{p}}^{A},\beta^{B}\right)$. This behaviour
corresponds to a class 1 gate with two canalising input values for one
parameter. In order to implement class 2 gates a comparison of the logic gate
patterns and the contour plot for
$M_{x}\left(\phi_{\mathrm{p}}^{A},\beta^{B}\right)$ suggests a restriction of
the parameter range to smaller intervals. For example, one may choose the
interval $\phi_{\mathrm{p}}\in\left[\pi,\frac{3\pi}{2}\right]$ and
$\beta\in\left[0,\frac{\pi}{2}\right]$ to implement a NAND gate representing a
class 2 (NAND) gate (see Table 4). The implementation of a class 0 gate
requires two canalising input values for both $\phi_{\mathrm{p}}^{A}$ and
$\beta^{B}$. As in the class 1 ($B$) gate scenario the periodicity of
$M_{x}\left(\phi_{\mathrm{p}}^{A},\beta^{B}\right)$ can be used to achieve
canalising inputs. However, this time both parameters have to undergo the
$2\pi$ value changes. Alternatively one can use pulses corresponding to
rotation operators $R_{\phi_{\mathrm{p}}}\left(\beta\right)=\pm\mathbbm{1}$
for generating canalising inputs for any parameter configuration of
$\phi_{\mathrm{p}}^{A}$ or $\beta^{B}$.

Having demonstrated how to implement one member of every gate class it is now
a trivial task to generate implementations of all the members of a given gate
class. By using the symmetry operations of permuting the input assignment of
$A$ and $B$ to $\phi_{\mathrm{p}}$ and $\beta$, inverting the input or the
output, the remaining gates are obtained directly.

This shows that all 2-input logic gates can be implemented using the functions
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$.
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ are both products of two linear
trigonometric functions, differing only by a phase shift of $\frac{\pi}{2}$ in
the factor depending on $\phi_{\mathrm{p}}$
($\sin\left(\phi_{\mathrm{p}}+\frac{\pi}{2}\right)=\cos\phi_{\mathrm{p}}$).
This phase shift can be seen in Figure 4(a) and (b) as a horizontal shift by
$\frac{\pi}{2}$, otherwise both plots are identical. Their overall symmetry
pattern is that of a class 3 gate. Hence, everything said about
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$ implementations equally holds for
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$.

However the same can not be said about the magnetisation magnitude
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ (Figure 4(c)).
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)=M_{xy}\left(\beta\right)=\frac{\lambda_{\mathrm{B}}}{4}\left|\sin\beta\right|$
is only a function of the pulse flip angle $\beta$ and, therefore, displays a
contour plot with a symmetry corresponding to a class 1 gate.

The behaviour of the functions under permutation of the variables
$\phi_{\mathrm{p}}$ and $\beta$ and/or their inversion distinguishes
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ from each other.
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$ is invariant to permutation of the
variables while $M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ is not. In
contrast, $M_{x}\left(\phi_{\mathrm{p}},\beta\right)$ changes under inversion
of its variables $\phi_{\mathrm{p}}\rightarrow-\phi_{\mathrm{p}}$ or
$\beta\rightarrow-\beta$, while $M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$
is invariant to inversion of $\phi_{\mathrm{p}}\rightarrow-\phi_{\mathrm{p}}$.
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ shows the same behaviour as
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ under these transformations.
However, a simple shift in $\phi_{\mathrm{p}}=\frac{\pi}{2}$ gives
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)=M_{y}\left(\phi_{\mathrm{p}}+\frac{\pi}{2},\beta\right)$,
an operation which is not possible for
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ since it is independent of
$\phi_{\mathrm{p}}$. The differences in behaviour arise because for
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ both variables $\phi_{\mathrm{p}}$
and $\beta$ are arguments of products of trigonometric functions, which
generates function values in the range of $\left[-1,1\right]$, whereas
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ has trigonometric function values
in $\left[-1,1\right]$ only for the variable $\beta$.

In principle, the task of implementing all 2-input logic gates by NMR
spectroscopy is already accomplished by using only the simplest of all NMR
experiments: starting from thermal equilibrium and only using a single r.f.
pulse. This scenario can therefore serve as a Universal Logic Module (ULM)
[35]. There are, however, good reasons why one needs to explore other starting
conditions, and more complicated NMR pulse sequences. NMR is uniquely suitable
as a single testbed for the implementation of classical as well as quantum
computations. In common formulations of quantum algorithms the initial state
of the computation is not the thermal equilibrium state but a superposition
state [16]. For valid comparisons between classical and quantum algorithm NMR
implementations the same initial (superposition) state should be used.
Further, it may be desirable to construct more extended circuitry than just a
single logic gate [15]. Then gate implementations that can deal with initial
states other than $\rho_{z}^{\mathrm{eq}}$ are attractive as an efficient
means of taking advantage of the output of a logic gate without having to
restore the initial state $\rho_{z}^{\mathrm{eq}}$ before the next logic gate
in a circuit can be executed.

##### Starting from superposition state

A r.f. pulse $R_{\frac{\pi}{2}}(\frac{\pi}{2})$ applied to
$\rho_{z}^{\mathrm{eq}}$ generates the superposition state
$\rho_{x}=\frac{1}{2}\mathbbm{1}+\frac{1}{2}\mathbb{\lambda_{\mathrm{B}}}I_{x}$,
which corresponds to spin polarisation pointing along the $+x$-axis. Here we
take $\rho_{x}$ as the initial superposition state. The commutator between
$R_{\phi_{\mathrm{p}}}(\beta)$ and $\rho_{x}$ is

$\left[R_{\phi_{\mathrm{p}}}(\beta),\rho_{x}\right]=-\lambda_{\mathrm{B}}I_{z}\sin\phi_{\mathrm{p}}\sin\frac{\beta}{2}$
(55)

and is zero for values $\phi_{\mathrm{p}}=n\pi$. These angles correspond to
rotations around the positive and negative $x$-axis (the commutator is also
zero for $\beta=2n\pi$, but these angles represent trivial $2\pi$ rotations).
$\rho_{x}$ transforms under the influence of a r.f. pulse
$R_{\phi_{\mathrm{p}}}(\beta)$ as

$\displaystyle\rho^{\left(x\right)}\left(\phi_{\mathrm{p}},\beta\right)$
$\displaystyle=$ $\displaystyle
R_{\phi_{\mathrm{p}}}(\beta)\rho_{x}R_{\phi_{\mathrm{p}}}^{\dagger}(\beta)$
(56)

The r.f. pulse generates a magnetisation vector $\boldsymbol{M}$ (Eq. (43)) as
a function of pulse flip angle $\beta$ and pulse phase $\phi_{\mathrm{p}}$
according to

$\displaystyle\left(\begin{array}[]{c}M_{x}\\\ M_{y}\\\
M_{z}\end{array}\right)=\left(\begin{array}[]{c}\mathrm{Tr}\left\\{\rho^{\left(x\right)}(\phi_{\mathrm{p}},\beta)I_{x}\right\\}\\\
\mathrm{Tr}\left\\{\rho^{\left(x\right)}(\phi_{\mathrm{p}},\beta)I_{y}\right\\}\\\
\mathrm{Tr}\left\\{\rho^{\left(x\right)}(\phi_{\mathrm{p}},\beta)I_{z}\right\\}\end{array}\right)=\frac{\lambda_{\mathrm{B}}}{4}\left(\begin{array}[]{c}1-2\sin^{2}\phi_{\mathrm{p}}\sin^{2}\frac{\beta}{2}\\\
\sin 2\phi_{\mathrm{p}}\sin^{2}\frac{\beta}{2}\\\
-\sin\phi_{\mathrm{p}}\sin\beta\end{array}\right)$ (66)

All the quantities $M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)=\frac{\lambda_{\mathrm{B}}}{4}\sqrt{1-\sin^{2}\phi_{\mathrm{p}}\sin^{2}\beta}$
are functions of $\phi_{\mathrm{p}}$ and $\beta$. Contour plots of these three
functions are shown in Figure 5.

Figure 5: Contour plots of the NMR detectable quantities (a)
$M_{x}=\overline{\Braket{I_{x}}}$, (b)$M_{y}=\overline{\Braket{I_{y}}}$ and
(c)
$M_{xy}=\sqrt{\overline{\Braket{I_{x}}}^{2}+\overline{\Braket{I_{y}}}^{2}}$
(Eq. (66)) as a function of the pulse parameters $\phi_{\mathrm{p}}$ and
$\beta$. The initial spin polarisation has been along the $x$-axis
($\rho_{x}$) and $\lambda_{\mathrm{B}}=1$ has been assumed. The ranges for
$\phi_{\mathrm{p}}$ and $\beta$ have been chosen such that the only symmetry
operation necessary to generate a full, infinite plot are horizontal and
vertical translations.

Again, agreements and disagreements in symmetries are found by comparison with
Figure 1. Inspection of Figures 4 and 5 immediately reveals differences in the
transformation behaviour of $\rho_{x}$ and $\rho_{z}^{\mathrm{eq}}$.

As shown earlier it is possible to implement any logic gate from a NMR
measurable quantity that has the symmetry of a class 3 gate in Figure 1 (e.g.
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$ in Figure 4(a)). However, none of
the three contour plots in Figure 5 displays this symmetry and no class 3
gates can be implemented. The symmetries present belong to those of class 0, 1
and 2 gates and can be found in any of the three contour plots. Implementing
class 1 gates requires taking advantage of the periodicity of the functions
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ in order to generate canalising
inputs. Class 2 gates use a reduced parameter range for $\phi_{\mathrm{p}}$
and $\beta$.

Permutation of $\phi_{\mathrm{p}}$ and $\beta$ changes
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$, while
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ stays invariant under this
operation. $M_{x}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ are invariant under input
inversion $\phi_{\mathrm{p}}\rightarrow-\phi_{\mathrm{p}}$ or
$\beta\rightarrow-\beta$ while $M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ is
only invariant under $\beta\rightarrow-\beta$. All functions are now periodic
with $\pi$ in $\phi_{\mathrm{p}}$ because of their dependence on
$\sin^{2}\phi_{\mathrm{p}}$ or $\sin 2\phi_{\mathrm{p}}$.
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ have a $2\pi$ periodicity interval
in $\beta$ and $\pi$ periodicity for
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$. All the functions
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ are the products of two
trigonometric functions of which at least one is quadratic. The squaring
reduces the trigonometric function values to the interval $\left[0,1\right]$
and therefore, it is not possible to have a symmetry behaviour required for
class 3 gates.

The rotation operator $R_{\phi_{\mathrm{p}}}(\beta)$ _not commuting_ with the
initial density matrix $\rho_{z}^{\mathrm{eq}}$ leads to the functions
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ described by products of linear
trigonometric functions and the ability to implement _all_ logic gates. The
rotation operator $R_{\phi_{\mathrm{p}}}(\beta)$ _commuting_ with the initial
density matrix $\rho_{x}$, however, leads to the functions
$M_{x}\left(\phi_{\mathrm{p}},\beta\right)$,
$M_{y}\left(\phi_{\mathrm{p}},\beta\right)$ and
$M_{xy}\left(\phi_{\mathrm{p}},\beta\right)$ characterised by quadratic
trigonometric factors and _does not_ permit the implementation of all logic
gates. Achieving universality when starting from $\rho_{x}$ therefore requires
a different rotation operator that never commutes with $\rho_{x}$. This could
be achieved by choosing different pairs of parameters from the set of
parameters describing the single-pulse experiment (Figure 3) such that a non-
commuting rotation operator for $\rho_{x}$ results. Alternatively, one can
keep the pair of parameters $\phi_{\mathrm{p}}$ and $\beta$, and use more than
one r.f. pulse, with rotation operators such as
$R_{\phi_{\mathrm{p}2}}\left(\beta_{2}\right)R_{\phi_{\mathrm{p1}}}\left(\beta_{1}\right)$.
This latter option we consider next.

####  3.2.2 Two-pulse gates

The initial density matrix $\rho_{x}$ transforms under the influence of two
r.f. pulses
$R_{\phi_{\mathrm{p}2}}\left(\beta_{2}\right)R_{\phi_{\mathrm{p1}}}\left(\beta_{1}\right)$
as

$\displaystyle\rho^{\left(x\right)}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)=R_{\phi_{\mathrm{p}2}}\left(\beta_{2}\right)R_{\phi_{\mathrm{p1}}}\left(\beta_{1}\right)\rho_{x}R_{\phi_{\mathrm{p1}}}^{\dagger}\left(\beta_{1}\right)R_{\phi_{\mathrm{p}2}}^{\dagger}\left(\beta_{2}\right)$
(67)

Thus, the NMR detectable quantities
$M_{x}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)$,
$M_{y}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)$
and
$M_{xy}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)$
are functions of the four variables $\phi_{\mathrm{p2}}$, $\beta_{2}$,
$\phi_{\mathrm{p1}}$ and $\beta_{1}$. Any two of these variables can serve as
logic gate input parameters with the remaining two fixed. This offers a high
degree of flexibility in assigning parameters as variable (and to control the
logic gate), and as fixed.

A trivial example is based on the fact that all 2-input gates can be
implemented when starting from thermal equilibrium magnetisation by a single
pulse. Starting from $\rho_{x}$, a first r.f. pulse
$R_{\frac{\pi}{2}}\left(-\frac{\pi}{2}\right)$ generates
$\rho_{z}^{\mathrm{eq}}$ and yields $\phi_{\mathrm{p1}}=\frac{\pi}{2}$ and
$\beta_{1}=-\frac{\pi}{2}$. From there on any second r.f. pulse
$R_{\phi_{\mathrm{p2}}}\left(\beta_{2}\right)$ generates a functional
behaviour identical to that of the single-pulse scenario in Eq. (54),
generating universality.

Another strategy uses the commutation properties of the rotation operators. In
the single-pulse scenario, starting from $\rho_{z}^{\mathrm{eq}}$ all logic
gates can be implemented because the overall rotation operator never commutes
with the initial density matrix. In the two-pulse scenario,
$R_{\phi_{\mathrm{p}2}}\left(\beta_{2}\right)R_{\phi_{\mathrm{p1}}}\left(\beta_{1}\right)$
must not commute with $\rho_{x}$. This implies further that the first r.f.
pulse $R_{\phi_{\mathrm{p1}}}\left(\beta_{1}\right)$ must not commute with
$\rho_{x}$, otherwise Eq. (67) simplifies to
$\rho^{\left(x\right)}\left(\phi_{\mathrm{p2}},\beta_{2}\right)=R_{\phi_{\mathrm{p}2}}\left(\beta_{2}\right)\rho_{x}R_{\phi_{\mathrm{p}2}}^{\dagger}\left(\beta_{2}\right)$
(identical to Eq. (56)) which _can not_ implement all logic gates. To avoid
commutation, $\phi_{\mathrm{p1}}$ should never be fixed to values $n\pi$ (Eq.
(55)). The second r.f. pulse $R_{\phi_{\mathrm{p}2}}\left(\beta_{2}\right)$
must not commute with the spin basis operators $I_{x}$ or $I_{y}$ when
calculating
$M_{x}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)=\overline{\Braket{I_{x}}}$
or
$M_{y}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)=\overline{\Braket{I_{y}}}$
(Eq. (43)), otherwise
$R_{\phi_{\mathrm{p}2}}\left(\beta_{2}\right)R_{\phi_{\mathrm{p1}}}\left(\beta_{1}\right)\rho_{x}R_{\phi_{\mathrm{p1}}}^{\dagger}\left(\beta_{1}\right)I_{x}R_{\phi_{\mathrm{p}2}}^{\dagger}\left(\beta_{2}\right)$
is just a similarity transform of
$R_{\phi_{\mathrm{p1}}}\left(\beta_{1}\right)\rho_{x}R_{\phi_{\mathrm{p1}}}^{\dagger}\left(\beta_{1}\right)I_{x}$
under which the trace is invariant. A commutation
$\left[R_{\phi_{\mathrm{p}2}}\left(\beta_{2}\right),I_{x}\right]=0$ can be
avoided by setting $\phi_{\mathrm{p}2}\neq n\pi$. For
$M_{y}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)$
a commutator
$\left[R_{\phi_{\mathrm{p}2}}\left(\beta_{2}\right),I_{y}\right]=0$ is avoided
for $\phi_{\mathrm{p}}\neq\left(2n+1\right)\frac{\pi}{2}$ . These constraints
on the parameters of type phase $\phi_{\mathrm{p}}$ implement the functions
$M_{x}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)$
such as those shown in Table 5 and Figure 6: these examples were deliberately
chosen such that the two fixed variables are taken as having equal values of
$\frac{\pi}{2}$.

| $\phi_{\mathrm{p2}}$ | $\beta_{2}$ | $\phi_{\mathrm{p1}}$ | $\beta_{1}$ | $M_{x}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)$
---|---|---|---|---|---
(a) | $A$ | $\frac{\pi}{2}$ | $B$ | $\frac{\pi}{2}$ | $\frac{\lambda_{\mathrm{B}}}{4}\left(\cos\phi_{\mathrm{p2}}\cos\phi_{\mathrm{p1}}\cos\left(\phi_{\mathrm{p2}}-\phi_{\mathrm{p1}}\right)-\sin\phi_{\mathrm{p2}}\sin\phi_{\mathrm{p1}}\right)$
(b) | $A$ | $\frac{\pi}{2}$ | $\frac{\pi}{2}$ | $B$ | $\frac{\lambda_{\mathrm{B}}}{4}\left(\cos^{2}\phi_{\mathrm{p2}}\cos\beta_{1}-\sin\phi_{\mathrm{p2}}\sin\beta_{1}\right)$
(c) | $\frac{\pi}{2}$ | $A$ | $\frac{\pi}{2}$ | $B$ | $\frac{\lambda_{\mathrm{B}}}{4}\cos\left(\beta_{2}+\beta_{1}\right)$
(d) | $\frac{\pi}{2}$ | $A$ | $B$ | $\frac{\pi}{2}$ | $\frac{\lambda_{\mathrm{B}}}{4}\left(\cos^{2}\phi_{\mathrm{p1}}\cos\beta_{2}-\sin\phi_{\mathrm{p1}}\sin\beta_{2}\right)$
(e) | $A$ | $B$ | $\frac{\pi}{2}$ | $\frac{\pi}{2}$ | $-\frac{\lambda_{\mathrm{B}}}{4}\sin\phi_{\mathrm{p2}}\sin\beta_{2}$
(f) | $\frac{\pi}{2}$ | $\frac{\pi}{2}$ | $A$ | $B$ | $-\frac{\lambda_{\mathrm{B}}}{4}\sin\phi_{\mathrm{p1}}\sin\beta_{1}$
Table 5: Examples of logic gate implementations from
$M_{x}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)$
using any possible pair of variables as gate input $A$ and $B$, and fixing the
remaining two parameters to $\frac{\pi}{2}$. Apart from a change in sign,
examples (e) and (f) are identical to the case in Figure 4(a). Example (d) is
identical to (b). Figure 6: Contour plots of
$M_{x}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)$
corresponding to examples (a)–(c) in Table 5.

One can see that class 0, 1 and 3 gates can be implemented by all possible
permutations of fixed pairs of variables of identical value (here
$\frac{\pi}{2}$). The non-commutation constraint provides the non-canalising
behaviour of class 3 gates, while the inherent periodicity of the system is
sufficient to provide the canalising input configurations necessary for class
0 and 1 gates. However, periodicity does not suffice for a class 2 gate
implementation. Comparing the single-pulse scenario (Figure 4(a)) with the
contour plots in Figure 6 demonstrates that class 2 gate implementations
require horizontal and vertical traces of constant value zero. Such traces are
absent in the contour plots in Figure 6. In short, arbitrarily choosing pairs
of fixed parameters as equal valued (not just for $\frac{\pi}{2}$) leads to
the loss of universality.

Let us examine if universality is regained if the fixed parameters are no
longer taken as equal valued. For example, taking $\beta_{1}=\frac{\pi}{2}$
and $\beta_{2}=\pi$ gives
$M_{x}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)=\frac{\lambda_{\mathrm{B}}}{4}\cos\left(2\phi_{\mathrm{p2}}-\phi_{\mathrm{p1}}\right)\cos\left(\phi_{\mathrm{p1}}\right)$.
The corresponding contour plot is shown in Figure 7(a) highlighting the
presence of constant horizontal zero-valued traces. Allowing for unequal-
valued pairs of parameters $\beta_{1}$ and $\beta_{2}$ (or
$\phi_{\mathrm{p1}}$ and $\phi_{\mathrm{p2}}$ ) permits implementation of
class 0, 1 and 2 gates but not class 3.

Universality is regained if pairs of parameters of _different_ _types_ , e.g.
$\phi_{\mathrm{p1}}$ and $\beta_{2}$ are fixed and do _not_ assume equal
values. Figure 7(b) shows that $\phi_{\mathrm{p1}}=\frac{\pi}{2}$,
$\beta_{2}=\pi$ gives
$M_{x}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)=\frac{\lambda_{\mathrm{B}}}{4}\cos
2\phi_{\mathrm{p2}}\cos\beta_{1}$. Both horizontal and vertical zero-valued
traces are re-established in the corresponding contour plot (Figure 7(b)); all
2-input logic gates can be obtained.

Figure 7: Contour plot of
$M_{x}\left(\phi_{\mathrm{p2}},\beta_{2},\phi_{\mathrm{p1}},\beta_{1}\right)$
for (a) $\beta_{1}=\frac{\pi}{2}$, $\beta_{2}=\pi$ and for (b)
$\phi_{\mathrm{p1}}=\frac{\pi}{2}$, $\beta_{2}=\pi$.

The flexibility and the ease of implementation as seen from our illustrative
examples are good indicators for the richness of the natural computational
potential of this system. Computational operations more complicated than just
2-input boolean logics are therefore well within the grasp of this system.
This includes multi-input logic gates, continuous logic, and analogue
computing implementations. The ubiquitous occurrence of function values
$\left\\{-1,0,1\right\\}$, due to the trigonometric system functions,
especially holds promise for the implementation of a balanced ternary logic as
being natural to this particular system [7]. Note also, that we can reverse
the operation of a logic gate if we know the pulse(s) that originally
generated the output [20]. This does not match with the usual predictions
about a computation where e.g. NAND gates are not reversible [8]. Obviously
our raw output stores additional information that can be exploited for more
sophisticated computations.

##  4 Summary and Conclusions

We have provided a design approach to analysing novel substrates in order to
determine which of their parameters can be used to implement boolean logic
gates. We have illustrated this with a case study drawn from NMR-based
classical computation. The design process requires cataloguing the parameters
that are naturally used to describe and manipulate the target system,
analysing their behaviours in combinations, and then matching the resulting
patterns of behaviour with the corresponding behaviour patterns of the target
gate classes. Our case study here focusses on two particular parameters
($\beta=\kappa_{\mathrm{p}}\tau_{\mathrm{p}}$ and $\phi_{\mathrm{p}}$); a full
design study would assess other combinations of other parameters, since the
aim is not simply to find some solution, but to analyse the ‘natural’
computational capabilities of the substrate. For example, in our work on
continuous gates [6], we focussed on $\omega_{\mathrm{p}}$ and
$\tau_{\mathrm{p}}$.

The design approach is not restricted to 2-input gates; combining several
parameters can produce patterns corresponding to more complex gates. More
sophisticated experiments could directly exploit symmetry properties of the
Hamiltonian (Eq. (2.2)–(14)). Eventually, however, specific behaviours will be
more easily achieved by combining simpler gates in circuits than by directly
designing complex gates.

Circuit design requires additional analysis to determine how individual gates
can be combined in a circuit in a manner ‘natural’ for the substrate in
question. Circuit design requires determining techniques for: sequencing
parameter manipulations to implement the sequence of gate operations in a
circuit; combining manipulations to implement multiple gate operations in
parallel; routing and transforming the output of one gate to the appropriate
input of the next. We will address these circuit design issues in a companion
paper [5].

This work addresses only how to implement ‘classical’ boolean logic gates in
unconventional substrates, yet it is clear that the example system has further
information available, that is thrown away when viewing it as a boolean gate.
If this extra information is instead retained and exploited, more powerful
computation becomes available [1]. The real computational power of these novel
substrates will come from not viewing them as merely alternative ways of
implementing classical logic gates, but from exploiting them to implement non-
classical forms of computation: quantum, continuous (analogue), hybrid, and
more. The design approach described here forms a first step in a principled
approach for analysing substrates with a view to performing a specified form
of computation.

##  5 Acknowledgements

Support of this work by the Deutsche Forschungsgemeinschaft and Leverhulme
grant FM/00224/AM is gratefully acknowledged. We thank Alastair Abbott for
constructive comments.

## References

  * [1] Alastair A. Abbott, Matthias Bechmann, Christian S. Calude, and Angelika Sebald.  (May 2011).  A nuclear magnetic resonance implementation of a classical Deutsch-Jozsa algorithm.  submitted.
  * [2] Andrew Adamatzky.  (2007).  Physarum machines: encapsulating reaction-diffusion to compute spanning tree.  Naturwissenschaften, 94(12):975–980.
  * [3] Leonard M. Adleman.  (1994).  Molecular computation of solutions to combinatorial problems.  Science, 266(5187):1021–1024.
  * [4] Martyn Amos.  (2005).  Theoretical and Experimental DNA Computation.  Springer.
  * [5] Matthias Bechmann, Angelika Sebald, and Susan Stepney.  Direct wiring of multi-gate NMR logic circuits.  In preparation.
  * [6] Matthias Bechmann, Angelika Sebald, and Susan Stepney.  (2010).  From binary to continuous gates—and back again.  In ICES 2010, York, UK, September 2010, volume 6274 of LNCS, pages 335–347. Springer.
  * [7] Matthias Bechmann, Angelika Sebald, and Susan Stepney.  (2011).  Design of ternary logic gates: a nucler magnetic resonance case study.  In preparation.
  * [8] Charles H. Bennett.  (1982).  The thermodynamics of computation—a review.  Int. J. Theor. Phys., 21:905–940.
  * [9] Vinícius P. Correia, André I. Reis, Cep Porto, and Alegre Rs Brasil.  (2001).  Classifying n-input boolean functions.  In Proc. VII Workshop de Iberchip, IWS, Montevideo, page 58.
  * [10] Barbara Drossel.  (2009).  Random Boolean Networks, pages 69–110.  Wiley.
  * [11] Solomon Golomb.  (1959).  On the classification of boolean functions.  IRE Transactions on Information Theory, 5(5):176–186.
  * [12] Simon L. Harding and Julian F. Miller.  (2004).  A tone discriminator in liquid crystal.  In CEC 2004, pages 1800–1807. IEEE Press.
  * [13] Simon L. Harding and Julian F. Miller.  (2005).  Evolution in materio: A real-time robot controller in liquid crystal.  In Proc. NASA/DoD Conference on Evolvable Hardware, pages 229–238. IEEE Press.
  * [14] Simon L. Harding, Julian F. Miller, and Edward A Rietman.  (2008).  Evolution in materio: Exploiting the physics of materials for computation.  Int. J. Unconventional Computing, 4(2):155–194.
  * [15] Yorik Hardy and Willi H. Steeb.  (2001).  Classical and Quantum Computing.  Birkhäuser Verlag, Basel.
  * [16] Jonathan A. Jones.  (2001).  NMR quantum computation.  Prog. Nucl. Magn. Reson. Spectrosc., 38(4):325–360.
  * [17] Jonathan A. Jones.  (2011).  Quantum computing with nmr.  Progress in Nuclear Magnetic Resonance Spectroscopy, 59(2):91–120.
  * [18] Viv Kendon, Angelika Sebald, Susan Stepney, Matthias Bechmann, Peter Hines, and Robert C. Wagner.  (2011).  Heterotic computing.  In Unconventional Computation 2011, number 6714 in LNCS, pages 113–124. Springer.
  * [19] Lothar Kuhnert, Konstantin Agladze, and Valentin Krinsky.  (1989).  Image processing using light-sensitive chemical waves.  Nature, 337:244–247.
  * [20] Malcolm. H. Levitt.  (April 2008).  Spin Dynamics: Basics of nuclear magnetic resonance.  John Wiley & Sons, Ltd, Chichester, 2nd edition.
  * [21] Jonathan W. Mills.  (2008).  The nature of the extended analog computer.  Phys. D, 237(9):1235–1256.
  * [22] Jonathan W. Mills, Matt Parker, Bryce Himebaugh, Craig Shue, Brian Kopecky, and Chris Weilemann.  (2006).  “Empty Space” computes: The evolution of an unconventional supercomputer.  In Proc. of the 3rd conference on Computing frontiers, pages 115–126.
  * [23] Ikuko N. Motoike and Andrew Adamatzky.  (2005).  Three-valued logic gates in reaction-diffusion excitable media.  Chaos, Solitons & Fractals, 24(1):107–114.
  * [24] Marta Roselló-Merino, Matthias Bechmann, Angelika Sebald, and Susan Stepney.  (2010).  Classical computing in nuclear magnetic resonance.  Int. J. Unconventional Computing, 6(3–4):163–195.
  * [25] Jun J. Sakurai.  (1994).  Modern Quantum Mechanics.  Addison-Wesley Publishing Company, Reading, MA, Revised edition.
  * [26] Benjamin Schumacher.  (Apr 1995).  Quantum coding.  Phys. Rev. A, 51(4):2738–2747.
  * [27] Jakub Sielewiesiuk and Jerzy Gorecki.  (2001).  Logical functions of a cross-junction of excitable chemical media.  J. Phys. Chem. A, 105(35):8189–8195.
  * [28] David Slepian.  (1953).  On the number of symmetry types of boolean functions of $n$ variables.  Can. J. Math., 5(2):185–193.
  * [29] Susan Stepney.  (July 2008).  The neglected pillar of material computation.  Physica D, 237(9):1157–1164.
  * [30] Susan Stepney, Samson Abramsky, Andy Adamatzky, Colin Johnson, and Jon Timmis.  (2008).  Grand challenge 7: Journeys in non-classical computation.  In Visions of Computer Science, pages 407–421. BCS.
  * [31] Atsushi Tero, Seiji Takagi, Tetsu Saigusa, Kentaro Ito, Dan P. Bebber, Mark D. Fricker, Kenji Yumiki, Ryo Kobayashi, and Toshiyuki Nakagaki.  (2010).  Rules for biologically inspired adaptive network design.  Science, 327(5964):43–9–442.
  * [32] Ágota Tóth and Kenneth Showalter.  (1995).  Logic gates in excitable media.  J. Chem. Phys., 103:2058–2066.
  * [33] Damien Woods and Thomas J. Naughton.  (2008).  Parallel and sequential optical computing.  In Optical SuperComputing, volume 5172 of LNCS, pages 70–86. Springer.
  * [34] Damien Woods and Thomas J. Naughton.  (2009).  Optical computing.  Appl. Math. Comput., 215(4):1417–1430.
  * [35] Stephen S. Yau and Calvin K. Tang.  (feb. 1970).  Universal logic modules and their applications.  IEEE Transactions on Computers, C-19(2):141–149.