Notation xiii

N set of natural numbers, i.e., {0, 1, 2,... }

Z set of integers

R set of real numbers

C set of complex numbers

B classical bit (set {0, 1})

B quantum bit (qubit, space

C2

— p. 53)

Fq finite field of q elements

Z/nZ ring of residues modulo n

Zn additive group of the ring Z/nZ

(Z/nZ)∗

multiplicative group of invertible elements of

Z/nZ

Sp2(n) symplectic group of order n over the field F2

(p. 165)

ESp2(n) extended symplectic group of order n over the

field F2 (p. 164)

L(N ) space of linear operators on M

L(N , M) space of linear operators from N to M

U(M) group of unitary operators in the space M

SU (M) special unitary group in the

space M

SO (M) special orthogonal group in the

Euclidean space M

Notation for matrices:

H =

1

√

2

1 1

1 −1

, K =

1 0

0 i

,

Pauli matrices: σx =

0 1

1 0

, σy =

0 −i

i 0

, σz =

1 0

0 −1

Notation for complexity classes:

NC (p. 23) NP (p. 28) BQP (p. 91)

P (p. 14) MA (p. 138) BQNP (p. 139)

BPP (p. 36) Πk (p. 46) PSPACE (p. 15)

PP (p. 91) Σk (p. 46) EXPTIME (p. 22)

P/poly (p. 20)