Next: 3 The Satisfiability Problem Up: Solving Highly Constrained Search Previous: 1 Introduction

# 2 Quantum Computers

The state of a classical computer can be described by a string of bits, each of which is implemented by some two-state device. Quantum computers use physical devices whose full quantum state can be controlled. For example [19], an atom in its ground state could represent a bit set to 0, and an excited state for 1. The atom can be switched between these states and also be placed in a uniquely quantum mechanical superposition of these values, which can be denoted as a vector , with a component (called an amplitude) for each of the corresponding classical states for the system. These amplitudes are complex numbers. A superposition should not be confused with a probabilistic representation of ignorance about whether a classical bit is really 0 or 1. Nor is a superposition simply in between a 0 or 1, as could be the case with a 3 volt value for classical bits implemented as 0 and 5 volts. Instead, a superposition has no complete classical analog.

In contrast to a classical machine which, at any given step of its program, has a definite value for each bit, a quantum machine with n quantum bits exists in a general superposition of the classical states for n bits, described by the vector

The amplitudes have a physical interpretation: when the computer's state is measured, the superposition randomly changes to one of the classical states with being the probability to obtain the state s. Thus amplitudes satisfy the normalization condition . This measurement operation is used to obtain definite results from a quantum computation.

Using this rich set of states requires operations that can rapidly manipulate the amplitudes in a superposition. Because quantum mechanics is linear and the normalization condition must always be satisfied, these operations are limited to unitary linear operators [29]. That is, a state vector can only change to a new vector related to the original one by a unitary transformation, i.e., where U is a unitary matrix of dimension . In particular, this requires that the operations be reversible: each output is the result of a single input. In spite of the exponential size of the matrix, in many cases the operation can be performed in a time that grows only as a polynomial in n by quantum computers [7, 35]. Importantly, the quantum computer does not explicitly form, or store, the matrix U. Rather it performs a series of elementary operations whose net effect is to produce the new state vector . On the other hand, the components of the new vector are not directly accessible: rather they determine the probabilities of obtaining various results when the state is measured.

Important examples of such operations are reversible classical programs [3, 22]. Let P be such a program. Then for each classical state s, i.e., a string of bit values, it produces an output , and each output is produced by only a single input. A simple example is a program operating with two bits that replaces the first value with the exclusive-or of both bits and leaves the second value unchanged, i.e., P[00]=00, P[01]=11, P[10]=10 and P[11]=01. When used with a quantum superposition, such classical programs operate independently and simultaneously on each component to give a new superposition. That is, a program operating with n bits gives

where with . This quantum parallelism allows a machine with n bits to operate simultaneously with different classical states.

Unitary operations can also mix the amplitudes in a state vector. An example for n=1 is

This converts , which could correspond to an atom prepared in its ground state, to , i.e., an equal superposition of the two states. Since amplitudes are complex numbers, such mixing can combine amplitudes to leave no amplitude in some of the states. This capability for interference [4, 21] distinguishes quantum computers from probabilistic classical machines.

Next: 3 The Satisfiability Problem Up: Solving Highly Constrained Search Previous: 1 Introduction