bit: Evolution of the quantum state is given by mapping x to Ux, where U is a unitary matrix, meaning that it always preserves length (mathematically, , where ).

Single qubits are interesting for physics experiments, but for computational purposes, we are more interested in what happens when we have n qubits. In this case, the state x is a unit vector in , with entries labeled by n-bit strings. Most n-qubit states are entangled, meaning that their amplitudes are in some way correlated across the n bits. Dynamics are now given by 2nx2n unitary matrices.

While this seems both abstract,
and potentially complicated (there
are a lot of 2nx2n unitary matrices!),
a similar formalism can be used to
describe classical deterministic and
randomized computations. An n-
bit string can be represented, albeit
somewhat wastefully, as a vector of
length two inches with a single entry
equal to one and the rest equal to zero.
Dynamics can be represented by map-
ping x to Mx where M is a 0/1 matrix
with a single 1 in each column. Ran-
domized computation is similar. This
time the state is a vector of nonnega-
tive real numbers summing to one,
and x Mx is a valid transition for
any M with nonnegative entrieswhose
columns each sum to one.

01 10

!

" #

$ % &

Geometrically, this is a rotation by π/2. However, only a quantum computer can perform the following “square root of NOT,” which corresponds to a rotation by π/4.

 

NOT = 1/ 2

1/ 2

"

#
$
$
!1/ 2
1/ 2

Figure 2. When light, or any other wave, is split into two beams and recombined, the relative phase of the two beams determines whether they interfere constructively or destructively. Since the phase of light depends on how far it’s traveled, this is a very sensitive way to measure distance. Similarly, quantum computers can split computations into multiple branches and recombine them to obtain either constructive or destructive interference.

If we start with the “0” state and apply NOT  , then we obtain the state

max Ai,j,k i,j,k

xiyjzk  
Were we to measure, the outcomes
zero or one would each occur with prob-
ability . 5. However, if we apply NOT   a
second time before measuring, then we
always obtain the outcome one. (To see
that this is indeed performing a NOT  
check the result of applying it twice to
e0.) This demonstrates a key difference
between quantum superpositions and
random mixtures; placing a state into
a superposition can be done without
any irreversible loss of information.

 

FAMOUS, CUT TING-EDGE QUANTUM ALGORITHMS When we have n qubits, superposition and interference enable us to achieve greater computational advantages. One famous example is Grover’s algorithm, which, given a binary function f on n bits, allows us to search for an input x 0, 1 { }n with f(x)= 1 using ≈ 2n/2 evaluations of f; a square-root advan-