IEEE Spectrum August, 2014 - 39

SpeedinG up SeArch
In a classIcal search algorIthm, hunting for a particular string in
an unstructured database involves looking at every entry in succession until
a match is found. On average, you'd have to run through half, or N/2, of the
queries before the correct entry is located. Grover's algorithm, a quantum
search algorithm named for computer scientist Lov Grover, could speed
up that work by simultaneously querying all entries. The process still isn't
queries.
instantaneous: Finding the correct one would take, on average,
But it could make a difference for large databases. To search a trillion entries,
the scheme would require 0.0002 percent of the number of queries needed
in the classical approach. Here's how it works.

1

The input, a quantum version
of the search string, is set up.
It contains N different states, one
of which is the index of the string
you're looking for. All N states exist in
superposition with one another, much
like Schrödinger's cat, which can be
both dead and alive at the same time.
At this point, if the input is observed,
it will collapse into any one of its N
component states with a probability
of 1/N (the square of the quantum
state amplitude shown in the y-axis
of the diagram).

but we can't see it. The probability of
observing the correct state is still the
same as that of all the others.

2

4

1

Initial state

Index

2

Query database....
Mean
Index

3

To get around this observation
problem, a quantum computer
can be made to perform a simple
operation that would invert all of the
amplitudes of the states about their
overall mean. Now, when the input
is measured, it will be more likely to
collapse into the correct answer. But
if N is large, this probability will still be
quite small.
To increase the probability of
observing the correct entry,
Grover's algorithm repeats steps
2 and 3 many times. Each time, the
correct state will receive a boost.
cycles, the probability of
After
observing that state will be very
close to 1 (or 100 percent).

that behaves according to the laws of quantum physics and can be
placed in a superposition of states could be used to make a qubit.
Since quantum behavior is typically most evident at small
scales, most natural qubits are tiny objects such as electrons,
single atomic nuclei, or photons. Any property that could take
on two values, such as the polarization of light or the presence
or absence of an electron in a certain spot, could be used to en-
code quantum information. One of the more practical options
is spin. Spin is a rather abstruse property: It reflects a particle's
angular momentum-even though no physical rotation is occur-
ring-and it also reflects the direction of an object's intrinsic mag-
netism. In both electrons and atomic nuclei, spin can be made
to point up or down so as to represent a 1 or a 0, or it can exist
in a superposition of both states.
It's also possible to make macroscopic qubits out of artificial
structures-if they can be cooled to the point where quantum behav-
ior kicks in. One popular structure is the flux qubit, which is made
of a current-carrying loop of superconducting wire. These qubits,
which can measure in the micrometers, are quantum weirdness
writ large: When the state of a flux qubit is in superposition, the
current flows in both directions around the loop at the same time.
D-Wave uses qubits based on superconducting loops, although
these qubits are wired together to make a computer that operates
differently from a universal quantum computer. The company

RE PE AT

The input is fed into the
database, which has been
configured to invert the phase of
the correct entry. Here, phase is a
quantum attribute. It can't be directly
measured, but it affects how quantum
states interact with one another. The
correct entry is highlighted in one step,

Amplitude

Invert about the mean...

3

Mean
Index

after √-
n cycles...

4
Index

employs an approach called adiabatic quantum computing, in
which qubits are set up in an initial state that then "relaxes" into
an optimal configuration. Although the approach could poten-
tially be used to speedily solve certain optimization problems,
D-Wave's computers can't be used to implement an arbitrary al-
gorithm. And the quantum-computing community is still active-
ly debating the extent to which D-Wave's hardware behaves in a
quantum-mechanical fashion and whether it will be able to offer
any advantage over systems using the best classical algorithms.
Although large-scale universal quantum computers are still a
long way off, we are already getting a good sense of how we'd make
one. There are several approaches. The most straightforward one
employs a model of computation known as the gate model. It uses
a series of "universal gates" to wire up groups of qubits so that they
can be made to interact on demand. Unlike conventional chips with
hardwired logic circuitry, these gates can be used to configure and
reconfigure the relationships between qubits to create different
logic operations. Some, such as XOR and NOT, may be familiar,
but many won't be, since they're performed in a complex space
where a quantum state in superposition can take on any one of a
continuous range of values. But the basic flow of computation is
much the same: The logic gates control how information flows, and
the states of the qubits change as the program runs. The result is
then read out by observing the system.
SPECTRUM.IEEE.ORG

|

nORTh aMERICan

|

aUG 2014

|

39
http://SPECTRUM.IEEE.ORG
Table of Contents for the Digital Edition of IEEE Spectrum August, 2014
