Chapter 12: Complexity );! 361
12.8.1 QUANTUM COMPUTERS
We know that a bit (a 0 or a 1) is the fundamental concept of classical
computation and information. Also a classical computer is built from an
electronic circuit containing wires and logical gates. Let us study quantum bits
and quantum circuits which are analogous to bits and (classical) circuits.
A quantum bit, or simply qubit can be described mathematically as
Ilf/) = alO; + 1310)
The qubit can be explained as follows. A classical bit has two states, a °and
a 1. Two possible states for a qubit are the states 10; and 11). (The notation
I-l is due to Dirac.) Unlike a classical bit, a qubit can be in infinite number
of states other than 10) and 11). It can be in a state IVJ> = alO) + 1310), where
a and 13 are complex numbers such that lal
2 + 1131
2 = 1. The 0 and 1are called
the computational basis states and IVJ> is called a superposition. We can call
Ilf/) = alO) + 1310) a quantum state.
In the classical case, we can observe it as a 0 or a 1. But it is not possible
to determine the quantum state on observation. When we measure/observe a
qubit we get either the state 10; with probability lal
2 or the state 11) with
probability 1131 2 .
This is difficult to visualize. using our 'classical thinking' but this is the
source of power of the quantum computation.
Multiple qubits can be defined in a similar way. For example. a two-qubit
system has four computational basis states, 100), 1°1), 110; and Ill) and
quantum states Ilf/) = O' {)oIOO) + aodOl) + aiOlI0) + a11I11) with 10' {)o12 + lo:od
2
+ la101
2 + lal11
2 = l.
Now we define the qubit gates. The classical NOT gate interchanges 0
and 1. In the case of the qubit the NOT gate, a 10) + 1311), is changed to
al1) + 1310;.
The action of the qubit NOT gate is linear on two-dimensional complex
vector spaces. So the qubit NOT gate can be described by
lal~[O 1]la]=[13]
L13 J 1 °l 13 a
The matrix [~ ~] is a unitary matrix. (A matrix A is unitary if A adjA = I.)
We have seen earlier that {NOR} is functionally complete (refer to
Exercises of Chapter 1). The qubit gate conesponding to NOR is the
cLntrolled-NOT or CNOT gate. It can be described by
IA. B) -7 IA. B EB A)
12.8.1 QUANTUM COMPUTERS
We know that a bit (a 0 or a 1) is the fundamental concept of classical
computation and information. Also a classical computer is built from an
electronic circuit containing wires and logical gates. Let us study quantum bits
and quantum circuits which are analogous to bits and (classical) circuits.
A quantum bit, or simply qubit can be described mathematically as
Ilf/) = alO; + 1310)
The qubit can be explained as follows. A classical bit has two states, a °and
a 1. Two possible states for a qubit are the states 10; and 11). (The notation
I-l is due to Dirac.) Unlike a classical bit, a qubit can be in infinite number
of states other than 10) and 11). It can be in a state IVJ> = alO) + 1310), where
a and 13 are complex numbers such that lal
2 + 1131
2 = 1. The 0 and 1are called
the computational basis states and IVJ> is called a superposition. We can call
Ilf/) = alO) + 1310) a quantum state.
In the classical case, we can observe it as a 0 or a 1. But it is not possible
to determine the quantum state on observation. When we measure/observe a
qubit we get either the state 10; with probability lal
2 or the state 11) with
probability 1131 2 .
This is difficult to visualize. using our 'classical thinking' but this is the
source of power of the quantum computation.
Multiple qubits can be defined in a similar way. For example. a two-qubit
system has four computational basis states, 100), 1°1), 110; and Ill) and
quantum states Ilf/) = O' {)oIOO) + aodOl) + aiOlI0) + a11I11) with 10' {)o12 + lo:od
2
+ la101
2 + lal11
2 = l.
Now we define the qubit gates. The classical NOT gate interchanges 0
and 1. In the case of the qubit the NOT gate, a 10) + 1311), is changed to
al1) + 1310;.
The action of the qubit NOT gate is linear on two-dimensional complex
vector spaces. So the qubit NOT gate can be described by
lal~[O 1]la]=[13]
L13 J 1 °l 13 a
The matrix [~ ~] is a unitary matrix. (A matrix A is unitary if A adjA = I.)
We have seen earlier that {NOR} is functionally complete (refer to
Exercises of Chapter 1). The qubit gate conesponding to NOR is the
cLntrolled-NOT or CNOT gate. It can be described by
IA. B) -7 IA. B EB A)