v e r s s e a r c h a l g o r i th m : a n o p ti c a l a p p r o a c h
P. G. KWIAT , J. R. MIT CHEL L , P. D. D. SCHWINDT
and A. G. WHIT E
Physics Division , P-23, MS -H803, L os Alamos National L aboratory ,
L os Alam os, NM 87545, USA
(
Received 7 A pril 1999
)
A b s tr a c t.
T he essential operations of a quantum computer can be accom -
plished using solely optical elements, with di erent polarization or spatial
modes representing the individual qubits. We present a simple all-optical
implementation of G rover s algorithm for e cient searching, in which a
database of four elements is searched with a single query. By `compiling the
actual set-up, we have reduced the required number of optical elements from 24
to only 12. We discuss the extension to large databases, and the limitations of
these techniques.
1.
In tr o d u c tio n
It is now well known that quantum computation, if implementable, could
enable tremendous improvements over traditional computing methods for certain
types of problems, such as factoring large numbers into primes
[
1
]
, and e ciently
searching a database
[
2
]
. T hus far, the implem entation of actual algorithms has
been limited to schemes employing bulk nuclear magnetic resonance
(
NMR
)
methods
[
3, 4
]
, althoug h basic gate operations have also been perform ed using
cooled ions
[
5
]
and also cavity quantum electrodynamics
(
QED
)
methods
[
6
]
. T o
date there have been a number of discussions on the implementation of basic
quantum operation s using purely optical methods
[
7± 11
]
. T he central idea is that
individ ual qubits can be represented by di erent polarization or spatial-mode
degrees of freedom. T he di erence from a genuine quantum computer with
distinct entangleable registers is that the optical implementation requires a number
of elements which grows exponentially with the number of qubits. Nevertheless, as
we shall see, it is possible to `compile the circuits, allowing one easily to realize
and test non-trivial algorith ms involvin g several bits. One conclusion of this
approach is that a quantum computer is essentially a
(
complicated
)
interferometer
[
12
]
.
As shown in
[
10
]
, with this representation all the basic circuit elements of
quantum computation can be accomplished using only linear passive optical
elements. T his includes the Controlled Not
(
CNOT
)
gate, which entangles
di erent
bits,
and
the
simpler
Walsh± Hadamard
(
WH
)
transform:
0
! 0 1 =
2
1=2
and 1
! 0
¡
1 =
2
1=2
. For the present work we shall only need
the latter, in addition to the ability to apply various phase shifts on the bits. If one
considers a qubit based on the polarization degree- of-freedom, where horizontal
J
ournal of Modern O ptics ISS N 0950± 0340 print/I SS N 1362± 3044 online # 2000 T aylor & Francis L td
http://www.tandf.co.uk/JNL S /mop.htm
http://www.taylorandfrancis.com/JNL S/mop.htm
JOURNAL OF MODERN OPTICS
, 2000,
VOL
. 47,
NO
. 2/3, 257 ± 266 (
H
)
and vertical
(
V
)
polarization represent 0 and 1, respectively, then the WH
transformation can be accomplished with a half waveplate
(
HWP
)
oriented at 22.5
8
to the horizontal. S imilarly, a simple 50± 50 beamsplitter
(
BS
)
performs the WH
transform on a right-propagatin g spatial mode
(
²
0
)
and an upward-propagatin g
spatial mode
(
²
1
)
, after two extra phase shifters are included.
{
We will now
describe how a non-trivial quantum circuitÐ Grover s algorith m for e ciently
searching a databaseÐ may be constructed using these elements.
2.
Gr o v e r s s e a r c h a l g o r i th m
2.1. G eneral description
Consider a database of N elements
(
e.g. a list of integers
)
exactly one of which
is `marked as satisfying some desirable characteristic
(
e.g. is a prime number
)
.
T ypically, one would expect to have to look at and test roughly half the database
(
making
¹
N
=
2 `queries on average
)
before locating this element. Grover s algor-
ithm uses the parallelis m a orded by quantum superposition to accomplish the
task with only
¹
N
1=2
queries. Since it is described in detail elsewhere
[
2, 4, 13
]
,
here we present without proof the necessary steps. Enough qubits are input to the
computer to encode the elements of the databaseÐ n qubits su ce for a 2
n
-element
database. T o initializ e the computer, a WH transform is performed on each qubit
individ ually, thereby preparing the overall state into an equal superposition of each
of the database elements, e.g. j
00
i j
01
i j
10
i j
11
i =
2. Next, an `Oracle
simultaneously examines all database elements, and marks one
(
or more
)
of
them with a
p
phase shift. In general, the Oracle might perform some computation
on each element
(
e.g. test whether it is prime
)
, and mark only that element which
yielded a certain result
(
e.g. `prime
)
. For our proof-of-principle demonstration,
the Oracle merely marks one element of the database
(
e.g. the state
j
01
i
if the
second element is the desired one
)
, while leaving the others unchanged. Viewed as
a computation, our Oracle accepts a user-speci® ed input
(
e.g. `2
)
, and marks
which database element matches that number.
Finally , a series of transform ations accomplish the `inversion about the mean
operation at the heart of the amplitude-enhancement technique introduced by
Grover
[
2
]
. T hese are:
(
1
)
apply a second WH transformation to each bit;
(
2
)
apply
a
p
phase shift to all but the ® rst element
(
j
00
i
)
of the database ; and
(
3
)
again apply
a ® nal WH transform to each bit. T he net result of these last three operation s is to
transfer some of the amplitude from the non-special elements to the marked one.
Remarkably , for N 4
(
i.e. a 2 bit database
)
, all of the amplitude is transferred to
the desired element in a single run of the quantum circuit. In general for larger N ,
running the circuit
¹
N
1=2
=
8 times will lead to a ® nal state in which the magnitud e
of the marked element s amplitude is greater than 1
=
2
1=2
Ð a measurement on the
system will then yield this element more than half the time
[
14
]
. For our experi-
ment we focused on the simplest case of a 2 bit, 4-element database. Below we
discuss the extension to more bits.
258
P. G . Kwiat et al.
{ T he BS transformations are well known: a
! a ib =2
1
=
2
, b
! ia b =2
1
=
2
. A
¡
p=2
phase shift in the b mode before and after the BS yields the WH transform
[
10
]
. 2.2. O ptical coding
Figure 1
(
a
)
shows the optical layout corresponding to a direct 1-to-1 imple-
mentation of Grover s algorith m, in which each operation is implemented in-
dependently. A HWP oriented at 22
:
5
8
performs the initial WH transformation on
the polarization bit, while the WH transformation on the spatial-mode bit is
performed by the ® rst 50± 50 BS and the
¡
p=
2 phase shifter in the re¯ ected path.
T he oval represents the Oracle. Below we will discuss a practical implementation
of this device ; for the moment consider simply inserting a waveplate in the spatial
path a or b, which depending on its orientation gives a
p
phase shift to either H or
V polarizationÐ the oracle can thus ¯ ip the sign of any one of the database
elements
j
aH
i
,
j
aV
i
,
j
bH
i
, or
j
bV
i
. For example, if the second element is the
marked one, the state of the system after the Oracle is given by j
aH
i
¡ j
aV
i j
bH
i j
bV
i =
2
² j
00
i
¡ j
01
i j
10
i j
11
i =
2. Note that this is
an entangled state of the two qubitsÐ it cannot be factorized into a product of a
term involvin g only the polarization and a term involvin g only the spatial path.
G rov er s search algorith m
259
Figure 1.
Grover s technique for e ciently seaching a database.
(
a
)
A one-to-one
optical implementation of the circuit, for the case of n 2 bits
(
one represented by
polarization and the other by spatial mode.
)
All half waveplates
(
HWPs
)
are oriented
at 22:58.
(
b
)
A `compiled version of the algorithm, where many of the components
have been consolidated. T he ® rst and second HWPs are at 22:58 and 458,
respectively. T he ® rst WH transformation of the `inversion-about-the-mean subroutine on
the polarization bit is again accomplished by HWPs, and on the spatial mode by
combining paths a and b on a second 50± 50 BS
(
with associated
¡
p=
2 phase
shifters
)
. T he minus sign on all but the
j
00
i ²
j
a
0
H
i element is obtained by a
p
phase shift thickness of non-birefringent glass in path b
0
(
or by simply lengthening
path b
0
by
¶=
2
)
, and a half waveplate in path a
0
, oriented with its fast axis
horizontal
(
and labelled `
p
V
in ® gure 1
(
a
))
. T he ® nal WH transformations are
again produced with HWPs and a 50± 50 BS . We examine each of the outputs with
a polarizin g beamsplitter
(
PBS
)
in the H± V basis.
2.3. `Compiling
T his basic optical circuit for Grover s algorithm may be simpli® ed consider-
ably by consolidati ng some of the optical transformations. For example, because
we are free to choose the order in which the WH transforms are applied to the
polarization and spatial modes
(
i.e. these operation s on di erent qubits commute
)
,
we may move the HWPs in paths a and b after the second BS, and combine them
with elements in the second interferometerÐ the HWP±
p
V
± HWP combination in
path a
0
is equivale nt to a single HWP oriented along 45
8
, and the HWP± H WP
combination in path b
0
yields the identity transformation, i.e. no element at all.
After a few other consolidations of various phase shifts, the optical circuit of ® gure
1
(
a
)
may be simpli® ed to that in ® gure 1
(
b
)
.
T o understand the device performance, we calculate, for example, the prob-
ability that a photon will exit to detector 1, by summing the amplitudes of the four
possible paths, and taking the absolute square:
P 1
1
2
1=2
1
2
1=2
A
aV
1
2
1=2