数理解析研究所講究録
1142 巻 2000 年 36-52

36Implementation of the
Algorithm to Solve the Deutsch’s Problem
on One-, Two-, and Three-Qubit NMR
Quantum Computers$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{S}- \mathrm{K}\mathrm{i}\mathrm{m}- \mathrm{H}_{\mathrm{o}\mathrm{l}\mathrm{t}_{\mathrm{o}\mathrm{n}}}$Ushio Sakaguchi, Hiroshi Ozawa,b Chikara Amano,
Toshio Fukumi, d William S. Pricee$\mathrm{a}$$\mathrm{c}$(坂口潮, 小澤宏, 天野力, 福見俊夫, William S. Price)a

Kumamoto Gakuen University, Kumamot.o 862-8680, JapanbInformation Technology Center, The University of Tokyo, Tokyo 113-8658, Japan
cDepartment of Chemistry, Kanagawa University, Hiratsuka 259-1293, Japand
Osaka National Research Institute, Ikeda 563-8577, Japane Water
Research Institute, Tsukuba 305-0047, Japan
AbstractThe
algorithm to solve the Deutsch’s problem is implemented
for the first time on one-, two-, and three-qubit nuclear magnetic resonance (NMR)
quantum computers. The one-qubit case is the simplest example of implementationof any nontrivial quantum algorithm. The three-qubit case is the first meaningful
test of quantum algorithms to solve the Deutsch’s problem in that entangled states
are involved. In the three-qubit case, a new approach which uses a field gradientpulse immediately before signal acquisition is adopted to implement the algorithm
which is otherwise almost impossible to perform by NMR.
$\mathrm{C}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{s}-\mathrm{K}\mathrm{i}\mathrm{m}-\mathrm{H}_{\mathrm{o}1}\mathrm{t}_{\mathrm{o}\mathrm{n}}$1Introduction

Quantum computation is an exciting and rapidly growing field of research [1-6].
Most previous studies centered on theoretical aspects, mainly because thepractical realization of quantum computers is difficult. A quantum computeruses a quantum system to store information, manipulates the system states
through unitary transformations, and extract useful information from the resulting state. To this end, a quantum system should be protected from the37effect of decoherence, which might destroy the information stored in the quantum system. Decoherence is now considered to be the biggest obstacle to realizing any quantum computer.
Recently several groups proposed the use of nuclear magnetic resonance (NMR)
quantum computers and demonstrated their usefulness [7-27]. Nuclear spin
systems are rather well isolated from the environment and have longer decoherence times. The first quantum algorithm that was implemented on any
quantum computer was the Deutsch-Jozsa algorithm to solve the Deutsch’s
problem [28] (see below) and these implementations employed NMR [15-17].
The algorithm for the two-qubit (quantum bit) case has been implemented by
Chuang et al. [15] and Jones and Mosca [16] and more recently implementationof the three-qubit case has been reported by Linden, Barjat, and Freeman [17].
The Deutsch-Jozsa algorithm has been refined recently by Collins, Kim, andHolton (CKH) [18]. The CKH algorithm allows the size of a quantum computer to be reduced by one qubit than the original algorithln. Thus, previous
implementations correspond to cases of one- and two-qubits in this modified
algorithm.

We here report the results of implementation of the CKH algorithm to solve
the Deutsch’s problem on one-, two-, and three-qubit NMR quantum computers. The one-qubit case is, of course, the simplest example of implementationof any nontrivial quantum algorithm and shows that even a quantum computer with only one qubit can be used to solve a problem. The three-qubit caseconstitutes the first meaningful test of the CKH algorithm. As CKH pointedout [18], any meaningful test of their algorithm (and the Deutsch-Jozsa algorithm) occurs if and only if the number of qubits of a quantum computeris greater than two. The three-qubit case involves entangled states whereas
previous implementations cited above did not exploit entangled states which
are considered to be responsible for the power of quantum computers.

The Deutsch’s problem [28] may be stated as follows: “Given an unknown
function $f(x)$ that maps $N$ bits to one bit. Determine whether the function isconstant or balanced using only one function call (function evaluation).” Here“balanced” means that the function gives an equal number of and 1 outputs.
$0$

On a classical deterministic computer, at least $2^{N-1}+1$ function calls are
required to tell with certainty that the function is really constant or not. For
example, in the simplest one-bit case where $f(x)$ is a function on only one bit,
we need to evaluate both $f(0)$ and $f(1)$ to determine whether it is balanced
or constant. Namely, two function calls are necessary classically. In quantum
algorithms (the Deutsch-Jozsa and the CKH algorithms), only one function
call suffices (see below).
The CKH algorithm which was implemented in this study works as follows.

38

Suppose that a quantum computer is made of $N$ qubits and prepared in the(or) refers to the spin up (or down) state of, wherestate
field. First we apply the Hadamard
magnetic
externalinana nuclear spintransformation $H$ which is defined by$|0\rangle$$|0\rangle$$\cdots|0\rangle$$|0\rangle$$|1\rangle$(1)$H= \frac{1}{\sqrt{2}}$upon each qubit, producing an equally weighted superposition$(|0 \rangle+|1\rangle)(|0\rangle+|1\rangle)\cdots(|0\rangle+|1\rangle)=2^{N}1\sum_{x=^{0}}^{-}|x\rangle$,(2)

where stands for a binary number $x=x_{1}x_{2}\cdots X_{N}$ . Also here and hencethat
forth we omit normalization constants. The unitary transformation
performs function evaluation is defined in the CKH algorithm by$x$$U_{f}$$U_{f}$:$arrow(-1)^{f()}x|_{X\rangle}$$|x\rangle$.

(3)

In the original Deutsch-Jozsa algorithm, function evaluation was defined by
the transformation$U_{f}$:$|X\rangle$$|y\rangle$$arrow|x\rangle$ $|y\oplus f(_{X)}\rangle$

$(4)$

,

and at least two qubits were necessary for any implementation. We then apply
defined in Eq. (3) to the above state in superposition, yielding the state$U_{f}$$\sum_{x}(-1)f(x)|_{X\rangle}$(5).

Finally we apply the Hadamard transformation $H$ again to obtain the final
state$\sum_{x}\sum_{y}(-1)f(x)(-1)x*y|y\rangle$(6),

where $x*y$ is the sum (mod 2) of the bitwise product of $x=x_{1}x_{2N}\ldots X$ and$y=y_{1}y_{2y:}\ldots N$$X*y=X1y_{1}\oplus x_{2y_{2^{\oplus}}\cdots\oplus}X_{N}y_{N}$

.

(7)

39

Now, if $f(x)$ is constant,$\sum_{x}\sum_{y}(-1)f(x)(-1)x*y|y\rangle=(-1)^{f()}0\sum(\sum(-1)x*y)|y\rangle yx$$=(-1)^{f}(0)_{\sum,y}\delta 0|yy\rangle$$=(-1)^{f(0)}|0\rangle$(8),

while if $f(x)$ is balanced, the amplitude of the state$\sum_{x}(-1)^{f}(x)=^{0}$$|0\rangle$

is given by(9),

because $f(x)$ contains an equal number of Os and . Thus, after the series
in theof operations $Harrow U_{f}arrow H$ , the amplitude of the state
final state of the quantum computer tells with certainty whether the function
is constant or balanced. Note in the above we made the function call only
once. Note also that the last amplitude measurement can not be implemented
directly on NMR, except in the simplest one-qubit case.
$1\mathrm{s}$$|0\rangle$

2

The One-and Two-Qubit Cases$vs$$|0\rangle$$\cdots|0\rangle$. the Three-Qubit CaseIn the one-qubit case, the algorithm becomes quite simple. Starting from the. There are four functions thatstate , we apply $H$ to yield the state
and $f_{11}(x)=1$ foraremap one bit to one bit. Constant functions
both $x=0$ and 1. Balanced functions are $f_{01}(x)=x$ and $f_{10}(x)=1-x$ . Upon
, we get the state) on the state )(orapplication ofof this state gives risetransformation
Hadamard. The second
as the final state. On the other hand, application of
to the state,) generates the state(orthe balanced function(orwhich, after the second Hadamard transformation, becomes the state. Thus, if we look at the final state, we can tell with certainty whether
the function is constant or balanced.
$|0\rangle$$|0\rangle$$+|1\rangle$$f\mathrm{o}\mathrm{o}(x)=0$$|0$$U_{f_{11}}$$U_{f_{00}}$$+|1\rangle$$|0\rangle$$+|1\rangle$$(\mathrm{o}\mathrm{r}-(|0\rangle+|1\rangle))$$|0\rangle$$(\mathrm{o}\mathrm{r}-|0\rangle)$$f_{01}$$|0\rangle$$fi\mathrm{o}$$-|1\rangle$$(\mathrm{o}\mathrm{r}-(|\mathrm{o}\rangle-|1\rangle)$$|1\rangle$$-|1\rangle)$

obtained by applying the
In the two qubit case, the state$H$ on the starting stateis transformed
first Hadamard transformation, yielding the statesby one of the eight$(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)$$|0\rangle$$|0\rangle$$U_{f}\mathrm{s}$$\pm(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)$for constant functions and

(10)

40

$\pm(|0\rangle-|1\rangle)(|0\rangle+|1\rangle)$$\pm(|0\rangle-|1\rangle)(|0\rangle-|1\rangle)$

or
or
(11)

$\pm(|0\rangle+|1\rangle)(|0\rangle-|1\rangle)$for six balanced functions. The final states are$\pm|0\rangle|0\rangle$$\pm|1\rangle|0\rangle$$\pm|1\rangle|1\rangle$$\pm|0\rangle|1\rangle$

for
for
for
for

$f_{000}\mathrm{o}$$f_{0011}$$f_{0110}$$f_{0101}$

and
and
and
and

$f_{1111}$$f_{1100}$,,$f_{1001}$,$f_{1010}$

.

and
(12)

We can discriminate not only constant from balanced functions but also theseread-pulse,
four groups. For example, if we apply a hard (non-selective)
and if we denote the first and second spins as
and , respectively, theresulting spectrum of the two (I and ) doublets should appear both upward
for constant functions but down-up or down-down or up-down doublets forbalanced functions. Alternatively, we may apply a soft (selective)
readpulse only to the spin , for example, in which case only one peak of the
doublet will appear upward and at a position corresponding to the partner
spin being in the state
for constant functions. For balanced, a downward singlet will be seen at the same position
functionsandwhile the other balanced functions will give rise to a single peak at a position
corresponding to $S_{z}=\beta(|1\rangle)$ . Alternatively again, we may use a selective
pulse along the, where the pulse notation refers to a-axis (of the rotating frame of reference) on spin . These three methodsof detection serve to a complete characterization of the final states and we
performed all the three.
$\pi/2$

$S$

$I$

$S$

$\pi/2$

$I$

$I$

$S$

$S_{z}=\alpha(|0\rangle)$$U_{f_{0011}}$$U_{f_{1100}}$$\pi/2$$(\pi/2)_{x}(S)\mathrm{p}\mathrm{u}1_{\mathrm{S}}\mathrm{e}$

$S$

$x$

state appears anywhere.
cases, noIn both of the one- andThis makes a sharp contrast to the three-qubit case. In the three-qubit case,there are 70 balanced functions, of which half can be seen to give the same
spectra as the remaining half. These 35 balanced functions and their correO rs are summarized in Table 1.
sponding.
$\mathrm{t}_{\mathrm{W}\mathrm{O}}- \mathrm{q}\mathrm{u}\mathrm{b}\dot{\mathrm{i}}\mathrm{t}$$\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{l}\mathrm{e}\mathrm{d}$,$U_{J^{\mathrm{O}}\mathrm{P}}.\mathrm{e}\mathrm{r}\mathrm{a}.\mathrm{t}$Final states are in general entangled. For example, the balanced function$f_{0}\mathrm{o}\mathrm{o}\mathrm{l}0111$$|11\rangle)|1\rangle$, which belongs to group I, gives the stateas the final state:$|0\rangle|0\rangle|0\rangle$$(|01\rangle+|10\rangle)|0\rangle+(|00\rangle$-$arrow H$$\sum_{x}|x\rangle$$arrow U_{f}$$arrow H$$(|00\rangle-|11\rangle)(|0\rangle+|1\rangle)+(|01\rangle+|10\rangle)(|0\rangle-|1\rangle)$$(|01\rangle+|10\rangle)|0\rangle+(|00\rangle-|11\rangle)|1\rangle$

.

(13)

In general it may be difficult, if not impossible, to examine the amplitude of41

Table 1
Balanced functions in the three-qubit case, grouped into nine categories.
total number*$\frac{\mathrm{g}\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}U_{f\mathrm{P}}}\mathrm{o}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}_{0\Gamma}}{\mathrm{A}f_{000011}11ei\pi I_{\mathcal{Z}}3}$

fo01111oo$\mathrm{B}$$f\mathrm{o}1101001$$\mathrm{C}$$f\mathrm{o}0101101$$\mathrm{D}$foloololl$f_{00}011110$$\mathrm{E}$$f10000111$$f\mathrm{o}0011011$$\mathrm{F}$$\mathrm{H}$I3$e^{i\pi(1}I_{\tilde{4}}+sz+I’z)$

1$eei \pi I_{\mathcal{Z}}i\frac{\pi}{2}(s_{z}-K_{z})e\pi is_{zz}K$3$e^{i\pi I_{z}i(-K)\pi}e \frac{\pi}{2}szze^{-is_{zz}}K$3$e^{i\pi}e \frac{\pi}{2}(Sz+I\mathfrak{i}_{z})e^{i}I_{z}i’\pi S_{z\mathcal{Z}}K$3$e^{i\pi I_{z}}e \frac{\pi}{2}(s_{z}+l\mathrm{i}_{z}’)ei-i\pi s_{zz}K$3$e^{i\frac{\pi}{2}(+}eI_{z}s_{z})i\pi \mathrm{A}’.zIze-i\pi KzS_{z}$3.
$eei \frac{\pi}{2}(I_{z}+S_{z})-i\pi K_{z}I_{z}e^{i\pi}KzSz$

3$f_{01001110}$$e.ezei \frac{\pi}{2}(I_{z^{-}}s_{z})i\pi K_{z}Ii.\pi K_{zz}s$3$f10001101$$e^{i\frac{\pi}{2}()i\pi K}I_{z}-S_{z}e-i\pi K_{z}I\mathcal{Z}e-\mathcal{Z}S_{z}$3$f10001110$$e^{i\frac{\pi}{2}(-s_{z}}- I_{z}.-l\mathrm{i}_{z}’)e-i2\pi I_{z}S_{zz}K$3$f_{00100111}$$\mathrm{G}$$e^{i\pi I_{z}}e^{i}\pi s_{z}$$f\mathrm{o}0010111$

.

)

1

$e^{i\frac{\pi}{2}(h_{z}’}eI_{z}+S_{z}+$ $-i2\pi I_{z}S_{zz}K$*Operators which will be obtained by cyclically permuting$I_{z},$$S_{z}$, and$I1_{\mathcal{Z}}^{r}$

are not

shown in the table. Only the total numbers are listed.

in such final states (in superposition of states) and to
the stateobtain a clear-cut analysis by NMR, because NMR performs a deterministic
measurement on a Avogadro’s number of identical molecules.
$|0\rangle$$|0\rangle$$\cdots|0\rangle$

However, we note here that the transverse relaxation causes the loss of thephase coherence of the transverse magnetization. The transverse relaxationis shorter than or equal to the longitudinal relaxation time
time
process is much faster than theand it is well known that usually theprocess [29]. This means that if we allow such a final spin state to decohere fora time of order , only the diagonal part of the density matrix remains (If weallow the spins to decohere for much longer times, the spin system will attainthe thermal equilibrium state and any remaining information will be lost due
to the longitudinal relaxation). For example, the density operator after
decoherence of the above entangled state is given, in the product operator
formalism [29], by$(T_{1})$$(T_{2})$$T_{2}$$T_{1}$$T_{2}$$T_{2}$$\rho=(1-8I_{z}S_{z}K_{z}\mathrm{I}/2,$

(14)

42

where refers to the first spin, to the second, and $K$ to the third, and weomitted proportionality constants. Equation (14) holds forof group ,as well as group I. We can see that the other balanced functions should yield
similarly$I$$S$$U_{f}\mathrm{s}$for group A ,$\rho=(1-2I_{z})(1-2S)z(1+2K_{z})/8$ for group,$\rho=(1-2I_{z})(1-2sz)(1-2K_{z}\mathrm{I}/8$
for group ,$\rho=(1-2I_{z})/2$
for groups and ,$\rho=(1-4I_{z}S_{z})/2$
for groups and ,and their cyclic permutations of, andexcept for group ,$\mathrm{H}$$p=(1-2I_{z})(1+2S_{z})(1+2K_{z})/8$$\mathrm{B}$$\mathrm{C}$$\mathrm{D}$$\mathrm{E}$$\mathrm{F}$$\mathrm{G}$$I_{z},$$S_{z}$$\mathrm{A}_{z}’$$\mathrm{C}$(15)

while constant functions should give$p=(1+2I_{z})(1+2S_{z})(1+2I\mathrm{f}_{z})/2$

.

(16)

These states are far simpler than otherwise and allow an easy and straightforward distinction to be made between constant and balanced functions.

Note further that the same effect can be obtained experimentally by application of the pulsed field gradient along the -axis, which is known [29]to annihilate only the transverse magnetization while preserving the longitudinal one, hence the name “purging pulse” or “purging gradient.” The state
which results as the final state for constant functions is unaffected by
the transverse decoherence ( relaxation) nor by . Thus, we may solve theDeutsch’s problem in the three-qubit case also by NMR if we insert this procedure immediately before measurement. We employed this procedure for thethree-qubit case. It is easy to see that this method can be used to spin systems
containing more spins, because constant functions always regenerate, as the
final state after decoherence, the starting state, but balanced functions should yield density operators definitely different from(containing no contribution from).
$z$$(G_{z})$$|000\rangle$$T_{2}$$G_{z}$$|0\cdots 0\rangle$$|0\cdots 0\rangle$$\langle \mathrm{o}\cdots 0|$$|0\cdots 0\rangle\langle 0\cdots 0|$

3

Thermal State as an Input

In the above, the statesandrepresent either pure states or effective
pure states. However, we note that to solve the Deutsch’s problem only, we do
not need to prepare (effective) pure states and thermal states suffices. This isbecause, as we will show below, we can discriminate constant from balanced
functions even if we started from thermal states. This is not the first time it$|0\rangle$$|1\rangle$

43
was realized that thermal input states are sufficient to implement a quantum
algorithm $[17,24]$ . Therefore, we started from the thermal state in one- andthree-qubit cases.
Only in the two-qubit case, we prepared actually the effective pure state
as an input from thermal state by the method of spatial labelling, in order toshow that a variety of methods for signal detection can be used to attain ourgoal (see above).
$|0\rangle$$|0\rangle$

Let us examine briefly the behaviour of the density operator when we startfrom thermal state. In the one-qubit case, the density operator describing
the state of an ensemble of one-spin molecules at thermal equilibrium in an
external magnetic field can be written, if we omit proportionality constants,
as$p_{\mathrm{e}q}=I_{z}$

.

(17)

It is easy to see that this starting state is eventually transformed into $p=I_{z}$for constant functions and $\rho=-I_{z}$ for balanced functions. An NMR peak after
read-pulse will appear upward for the former but downward
applying thefor the latter.
$\pi/2$In the three qubit case, if we use thermal state as an input, the density operatorof this starting state is written in the same way as before as$\rho_{eq}=I_{z}+S_{z}+K_{z}$

.

(18)

After application of the sequence $Harrow U_{f}arrow Harrow G_{z}$ , constant functions
regenerates the same state, $p=I_{z}+S_{z}+I\zeta_{z}$ , because of $H$ being self-inverse$(HH=1)$ , while balanced functions yieldfor group A ,$\rho=-I_{z}-S_{z}+K_{z}$for group ,$p=-I_{z}-S_{z}-K_{z}$for group ,$\rho=-I_{z}$for groups and ,, and I,for groups$\rho=0$
and their cyclic permutations of, and E.
for groups$\rho=-I_{z}+S_{z}+I\mathrm{f}_{z}$$\mathrm{B}$$\mathrm{C}$$\mathrm{E}$$\mathrm{D}$$\mathrm{F},$$\mathrm{A},$$\mathrm{B},$$\mathrm{G},$$\mathrm{H}$$I_{z},$$S_{z}$, and$\rho_{eq}=I_{z}+S_{z}+K_{z}$$arrow H$(19)$\mathrm{D}$For example, in the case of $f10001110$ , which belongs to group
operator is transformed as$p=I_{x}+S_{x}+I\zeta_{x}$$K_{z}$$\mathrm{H}$, the density

44$arrow U_{f}$$arrow H$$arrow c_{z}$$p=4I_{x}S_{z}K_{z}-4IzxSK_{z}-4I_{z}S_{z}K_{x}$$p=4I_{z}S_{x}I\zeta_{x}-4I_{x}s_{zx}K-4ISxxzI\zeta$$\rho=0$,(20)

which is easily seen if we use the relation$e^{-i2\pi I_{z}sK}I_{x}zze^{i}2\pi I_{z}S_{z}h_{z}’=4I_{y}S_{z}K_{z}$

.

(21)

read-pulse, constant functions will yield all three (I,If we apply a hard$K$
, and ) quartets pointing upward, whereas balanced functions will exhibit, and C), or either
three quartets pointing downward somewhere (groups
only one (I) quartet appearing downward (groups and E), or no quartet atall (groups
and I). Thus, we can determine whether the function isconstant or balanced in a single experiment.
$\pi/2$$S$$\mathrm{A},$$\mathrm{B}$$\mathrm{D}$$\mathrm{F},$$\mathrm{G},$$\mathrm{H}$

4 tImplementation

The first step of the CKH algorithm starts with the Hadamard transformation$H$ , which corresponds to the operator
and was simply imple$H$ that is used in the last$(-\pi/2)_{y}$transformationThe
pulse.
amented bypulse in order to assure thatstep of the algorithm was executed by a
$H$ is self-inverse.
$e^{-i\frac{\pi}{2}}e^{i\pi I_{x}}e-i \frac{\pi}{2}I_{y}$$(\pi/2)_{y}$nothwere simply
andIn the one-qubit case, transformations
apartcorrespond to the operator
anding.” Transformations
from an irrelevant overall phase-factor and were implemented by the pulse
sequence $(\pi)_{x}-(\pi)_{y}$ , where the pulse sequence should be read from left topulse.”
pulse followed by aright as “ a($U_{f_{00}}$$‘ \mathrm{d}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{g}$$U_{f_{11}}$$e^{i\pi I_{z}}$$U_{f_{10}}$$U_{f_{01}}$$(\pi)_{y}$$(\pi)_{x}$In the two-qubit case, there are six balanced and two constant functions. For
transformations are implemented as given in Table 2. All thethese the.
oror
operators for balanced functions are of the form
$U_{f}$$e^{-i\pi I_{z}}$$e^{i\pi S_{z}}$$e^{-i2\pi IS_{z}}z$

in one-, two-,As seen from Tables 1 and 2, the unitary transformation
,
form
of
the
and three-qubit cases all consist of terms
. The
, and
, and their cyclic permutations of, andwere implemented by the pulse sequences
and
terms
$(U_{f}\mathrm{s})$$e^{\pm i\frac{\pi}{2}I_{z}},$$e^{\pm i2\pi IS_{z}}z$$e^{\pm i\frac{\pi}{2}I_{z}}$$e^{\pm i2\pi IsK}zzz$$I_{z},$$e^{\pm i\pi I_{z}}$$e^{\pm i\pi I_{z}},$$S_{z}$$e^{\pm i\pi I_{z}s_{z}}$$I\mathrm{f}_{z}$$(- \frac{\pi}{2})y(I)-$$e^{is_{z}}( \pm\frac{\pi}{f_{z}})_{x}(\pi \mathrm{a}\mathrm{n}I)-(\mathrm{d}e\frac{\pi}{2,l})_{y,\pi}(I)2I_{z}S_{z}\mathrm{a}_{\mathrm{W}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{i}1\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{d}\mathrm{s}}\mathrm{n}\mathrm{d}(\pm \mathrm{m}\mathrm{p}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{a}\pi)_{x}(I)-(\pi)_{y}(I),\mathrm{r}\mathrm{e}\mathrm{s}_{\mathrm{P}^{\mathrm{e}\mathrm{C}}\mathrm{y}.\mathrm{e}\mathrm{u}}\mathrm{t}\mathrm{i}\mathrm{V}\mathrm{e}1\mathrm{T}\mathrm{h}\mathrm{n}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{S}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{e}\tau-(\pi)_{x}(I\mathrm{i}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{y}\mathrm{o}),$$(\pi \mathrm{p})_{x}(\mathrm{e}\mathrm{r}_{S}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{s})-$where is the free precession period of length $\tau=1/4]_{IS}$and $\tau=1/2J_{IS}$ , respectively. If we note the relation$\tau-(\pi)_{x}(I),$ $(\pi)_{x}(S)$$\tau$

45

Table 2The unitary operators$U_{f}$$U_{f\mathrm{o}00}0$$U_{f1111}$$U_{f_{0011}}$$U_{f_{1100}}$$U_{f\mathrm{o}11}0$$U_{f_{1001}}$$U_{f\mathrm{o}\mathrm{l}0}1$$U_{f1010}$$(U_{f}\mathrm{s})$in the two-qubit case.

operatorpulse sequence*1

doing nothing$e^{-i\pi I_{z}}$$(-\pi)_{x}(I)-(\pi)y(I)$$e^{-i2\pi IS_{z}}z$$\tau-(\pi)_{x}(I),$ $(\pi)_{x}(S)-\mathcal{T}-(\pi)x(I),$ $(\pi)_{x}(s)$$e^{i\pi S_{z}}$$(\pi)_{x}(s)-(\pi)_{y}(s)$$*\tau=1/2J_{IS}$$e^{-i2\pi IsK_{z}}zz=e-i \frac{\pi}{2}I_{x}e-i\pi IzKze^{-}\frac{\pi}{2}Iei-yi\pi Izszei\frac{\pi}{2}I_{y}iee\pi IzKzi\frac{\pi}{2}I_{x}$

(22)

,

will be seen to be implemented by a proper combinathe operator
tion of the above pulse sequences.
$e^{\pm i2\pi I_{z}s_{z}}K_{z}$5Experimental

operAll the experiments were done on a Bruker DMX 500 spectrometer) at room temperature (about 298 K). As the water
ating frequency 500(Showa Denko, nominal
sample for the one-spin case we used actuallypurity $>99$ %) as supplied to avoid the radiation damping. The residual
water signal gave a strong enough signal. For the two-spin experiment, wedissolved in
employed trans-cinnamic acidof 671 Hz and ashiftchemicala, whose olefinic protons havespin-spin coupling constant $J=16.0$ Hz. The selective pulses were Gaussianin form and centered on each doublet. We did not use any window function
prior to Fourier transformation of the free induction decay.
$(^{1}\mathrm{H}$$\mathrm{M}\mathrm{H}\mathrm{z}$$\mathrm{D}_{2}\mathrm{O}$$(\mathrm{C}_{6}\mathrm{H}_{5}- \mathrm{C}\mathrm{H}=\mathrm{c}\mathrm{H}(\mathrm{C}\mathrm{o}\mathrm{o}\mathrm{H}))$$\mathrm{C}\mathrm{D}\mathrm{C}1_{3}$$(\sim 0.65\mathrm{M}/1)$

6

Results and Discussion

Figure 1 shows the results of the one-qubit experiment. While a constantfunction yields an upward peak, a downward peak is obtained for a balanced
function, as expected. This experiment corresponds, in essence, to the twoqubit implementations of the Deutsch-Jozsa algorithm made by Chuang et al.
[15] and Jones and Mosca [16], but the present result demonstrates clearly

46

that even only one qubit can work as a quantum computer and can actually
solve a problem.
Figures 2 to 4 give the results of the two-qubit experiment. In the two-qubit
and the final statescase, we started by preparing the effective pure state
given in Eq. (12) allow a variety of measurements. One can read out the final
pulse and Fourier transforming thestates by applying a non-selective
resulting free induction decay. This result is given in Fig. 2.
$|00\rangle$$\pi/2$

read-pulse on spin (or ), yielding
Alternatively, one may use a selective
completely characterize the final
to
In
order
4).
the results of Fig. 3 (or Fig.
states, all these three are necessary. The three results are compared to theprediction (stick diagrams) in Figs. 2 to 4. In these figures, the agreement
between the observed and the expected signals seems rather good, confirming
basically that the CKH algorithm works properly in the first place and that
our implementation is correct.
$\pi/2$$I$$S$In Fig. 2, small anomalies are noted in the relative intensities in each doublet.
Also, in Figs. 3 and 4, residual peaks are noted which, in theory, should notappear at all. These imperfections, for which we did not ascertain the origins,seem to arise from imperfect selectivity of “selective pulses” or from the decoherence (In the cases of Figs. 3 and 4, a total of five selective pulses areneeded, apart from hard pulses and field-gradient pulses). The results of thethree-qubit experiment will be reported elsewhere.
In conclusion, the present experiment demonstrates, for the first time, that(i) the CKH algorithm is valid for solving the Deutsch-Jozsa’s problem, (ii)even one qubit can work as a quantum computer and solve an actual problem,and (iii) the CKH algorithm in the three-qubit case which involves entangledstates can be implemented by NMR.

47

constant functionsbalanced functions

Fig. 1. The results of one-qubit NMR computation,“water experiment.”

48

Fig. 2. The results of the two-qubit experiment. The computer molecule istrans-cinnamic acid dissolved in chloroform-d. Final states are read out by applying
pulse on both spins. The relevant peaks are the two outermosta non-selective
doublets. Ignore the two central peaks which are due to the phenyl group of thecomputer molecule and the residual solvent. The predicted spectra are given to theright as stick diagrams.
$\pi/2$

49

Fig. 3. The results of the two-qubit experiment, obtained by applying a selective
read-pulse on spin , which is to the left of the spectra. In the stick diagram,the dotted lines indicate peaks that are expected, in theory, to disappear. Other
remarks are the same as in Fig. 2.
$\pi/2$$I$50$f_{1001}f\mathrm{o}110$

Fig. 4. The results of the two-qubit experiment, obtained by applying a selective
read-pulse on spin , which is to the right of the spectra. Other remarks are
the same as in Figs. 2 and 3.
$\pi/2$$S$

51
References[1] A. Steane, “Quantum computing,” Rept. Prog. Phys. 61, 117-173 (1998).
[2] E. G. Rieffel and W. Polak, “An introduction to quantum computing for nonphysicists,” LANL -print quant-ph/9809016.
$\mathrm{e}$[3] D. Aharonov, “Quantum computation,” LANL -print quant-ph/9812037;
to appear in D. Stauffer, ed., Annual Reviews of Computational Physics, VI(World Scientific, 1998).
$\mathrm{e}$[4] V. Vedral and M. B. Plenio, “Basics of quantum computation,” LANL e-print
quant-ph/9802065; Prog. Quant. Electron. 22, 1-40 (1998).

,[5] R. Jozsa, “Entanglement and quantum computation,” in S. Huggett, et al.
1997).
Press,
University(Oxford
Sciencein the Foundations ofGeometric$\mathrm{e}\mathrm{d}\mathrm{s}.$$Issue\mathit{8}$[6] D. P.

$\mathrm{D}\mathrm{i}\mathrm{V}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{Z}\mathrm{o}$, “Quantum computation,” Science 270, 255-261 (1995).

[7] D. G. Cory, M. D. Price, and T. F. Havel, “Nuclear magnetic resonancespectroscopy: An experimentally accessible paradigm for quantum computing,”, 82-101 (1998).
Physica$\mathrm{D}120$[8] D. G. Cory, A. F. Fahmy, and T. F. Havel, “Ensemble quantum computing by
NMR spectroscopy,” Proc. Natl. Acad. Sci. USA 94, 1634-1639 (1997).
[9] E. Knill, I. Chuang, and R. Laflamme, “Effective pure states for bulk quantum
computation,” Phys. Rev. A 57, 3348-3363 (1998).

[10] N. A. Gershenfeld and I. L. Chuang, “Bulk spin resonance quantum
computation,” Science 275, 350-356 (1997).
[11] I. L. Chuang, N. Gershenfeld, M. G. Kubinec, and D. W. Leung, “Bulk quantum
computation with nuclear magnetic resonance: Theory and experiment,”
Proc. R. Soc. Lond. A 454, 447-467 (1998).
[12] W. S. Warren, “The usefulness of NMR quantum computing,” Science 277,
1688-1689 (1997).
[13] N. Gershenfeld and I. L. Chuang, “Quantum computing with molecules,”Sci. Am., June 1998, 50-55.
[14] N. Linden, H. Barjat, R. J. Carbajo, and R. Freeman, “Pulse sequences for
NMR quantum computers: How to manipulate nuclear spins while freezing the
motion of coupled neighbours,” LANL -print quant-ph/9811043.
$\mathrm{e}$[15] I. L. Chuang, L. M. K. Vandersypen, X. Zhou, D. W. Leung, and S. Lloyd,“Experimental realization of a quantum algorithm,” Nature 393, 143-146(1998).

[16] J. A. Jones and M. Mosca, “Implementation of a quantum algorithm tosolve Deutsch’s problem on a nuclear magnetic resonance quantum computer,”J. Chem. Phys. 109, 1648-1653 (1998).

52[17] N. Linden, H. Barjat, and R. Freeman, “An implementation of the DeutschJozsa algorithm on a three-qubit NMR quantum computer,” LANL e-print
quant-ph/9808039.
[18] D. Collins, K. W. Kim, and W. C. Holton, “Deutsch-Jozsa algorithm as a testof quantum computation,” Phys. Rev. A 58, R1633-R1636 (1998).
[19] I. L. Chuang, N. Gershenfeld, and M. Kubinec, “Experimental implementationof fast quantum searching,” Phys. Rev. Lett. 80, 3408-3411 (1998).
[20] J. A. Jones, M. Mosca, and R. H. Hansen, “Implementation of a quantum searchalgorithm on a nuclear magnetic resonance quantum computer,” Nature 393,
344-346 (1998).
[21] D. G. Cory, M. D. Price, W. Maas, E. Knill, R. Laflamme, W. H. Zurek,
T. F. Havel, and S. S. Somaroo, “Experimental quantum error correction,”
Phys. Rev. Lett. 81, 2152-2155 (1998).

[22] D. Leung, L. Vandersypen, X. Zhou, M. Sherwood, C. Yannoni, M. Kubinec,
and I. Chuang, “Experimental realization of a two bit phase damping quantum
code,” LANL -print quant-ph/9811068.
$\mathrm{e}$[23] R. Laflamme, E. Knill, W. H. Zurek, P. Catasti, and S. V. S. Mariappan, “NMR
-Zeilinger states,” Philos. Trans. R. Soc. Lond. A 356, 19411948 (1998).
$\mathrm{G}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{n}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{r}-\mathrm{H}_{0}\mathrm{r}\mathrm{n}\mathrm{e}$[24] S. Lloyd, “Microscopic analogs of the Greenberger-Horne-Zeilinger experiment,”
Phys. Rev. A 57, R1473-R1476 (1998).

[25] M. A. Nielsen, E. Knill, and R. Laflamme, “Complete quantum teleportation
using nuclear magnetic resonance,” Nature 396, 52-55 (1998).
[26] J. A. Jones and M. Mosca, “Approximate quantum counting on an NMR
ensemble quantum computer,” LANL -print quant-ph/9808056.
$\mathrm{e}$[27] J. A. Jones, R. H. Hansen, and M. Mosca, “Quantum logic gates andnuclear magnetic resonance pulse sequences,” LANL -print quant-ph/9805070;
J. Magn. Resonance 135, 353-360 (1998).
$\mathrm{e}$[28] D. Deutsch and R. Jozsa, “Rapid solution of problems by quantum
computation,” Proc. R. Soc. Lond. A 439, 553-558 (1992).

[29] R. R. Ernst, G. Bodenhausen, and A. Wokaun, Principles of Nuclear Magnetic
Resonance in One and Two Dimensions (Clarendon Press, Oxford, 1991).