12.10 Quantum Computing
225
at its output X. The circuit below shows a logical AND gate with inverted output,
which results in a not-and, or NAND-gate. The tables below the two circuits shows
the outputs X and Y that correspond to the input values A and B. More complex
logical operations, such as adding two binary digits in the half-adder, shown on
the right-hand side in Fig. 12.10, can be constructed with suitably connected NAND
gates. The table below the circuit illustrates how the inputs A and B are combined to
produce the sum S and a carry-bit C. All digital devices, including the processors that
drive modern computers, are composed of many such elementary building blocks.
We emphasize that a state must be in one of the logic states “0” and “1,” which
represents one bit.
Quantum computers [22], on the other hand, operate on qubits, which are
quantum-mechanical states that may be visualized as spins pointing up or down,
commonly represented as |0 and |1. In contrast to classical bits can qubits be in
superposition states α|0 + β|1 with α
2
+ β
2
= 1; Schrödinger’s cat is in such a
state. Instead of using Dirac’s notation, we can equally well write the qubits as
column vectors, such as
|0 =
1
0
, |1 =
0
1
, and α|0 + β|1 =
α
β
.
(12.37)
Quantum-mechanical operators take the role of the logic gates and the Pauli-matrix σ x
[23], shown on the left-hand side in (12.38), acts similar to an inverter; it exchanges
the “0” and “1” component of a qubit.
σ x =
0 1
1 0
,
H =
1
√
2
1 1
1 −1
,
R k =
1 0
0 e
2πi/2
k
(12.38)
The Hadamard operator H , shown in the second equation creates a superposition
of the “0” and “1” components with α = 1/
√
2 and β = ±1/
√
2. R k , shown on
the right-hand side in (12.38), adds a phase factor to one of the components. Note
that these operators transform one qubit at their input to one qubit at their output.
Moreover, all operators are represented as unitary matrices, because they describe
the transformation of one spin state to a different spin state, but they do not change
the magnitude of the spin.
In order to describe multi-input gates we introduce states that describe multiple
qubits q 1 and q 2 as the tensor product of the individual qubits: |q 1 q 2 = |q 1 ⊗ |q 2 .
Using this notation we introduce the controlled-not, or CNOT gate, which operates
on two qubits |q 1 q 2 and flips q 2 , but only if q 1 = 1. We can therefore describe it
through
CNOT = |0000| + |0101| + |1011| + |1110| ,
(12.39)
where q| denotes the transpose of |q. It is straightforward to understand the action
of CNOT on, for example, |11, because only the third term in (12.39) is non-zero
and leads to |10 at the output. Since the first qubit is “1,” the second qubit is flipped.
225
at its output X. The circuit below shows a logical AND gate with inverted output,
which results in a not-and, or NAND-gate. The tables below the two circuits shows
the outputs X and Y that correspond to the input values A and B. More complex
logical operations, such as adding two binary digits in the half-adder, shown on
the right-hand side in Fig. 12.10, can be constructed with suitably connected NAND
gates. The table below the circuit illustrates how the inputs A and B are combined to
produce the sum S and a carry-bit C. All digital devices, including the processors that
drive modern computers, are composed of many such elementary building blocks.
We emphasize that a state must be in one of the logic states “0” and “1,” which
represents one bit.
Quantum computers [22], on the other hand, operate on qubits, which are
quantum-mechanical states that may be visualized as spins pointing up or down,
commonly represented as |0 and |1. In contrast to classical bits can qubits be in
superposition states α|0 + β|1 with α
2
+ β
2
= 1; Schrödinger’s cat is in such a
state. Instead of using Dirac’s notation, we can equally well write the qubits as
column vectors, such as
|0 =
1
0
, |1 =
0
1
, and α|0 + β|1 =
α
β
.
(12.37)
Quantum-mechanical operators take the role of the logic gates and the Pauli-matrix σ x
[23], shown on the left-hand side in (12.38), acts similar to an inverter; it exchanges
the “0” and “1” component of a qubit.
σ x =
0 1
1 0
,
H =
1
√
2
1 1
1 −1
,
R k =
1 0
0 e
2πi/2
k
(12.38)
The Hadamard operator H , shown in the second equation creates a superposition
of the “0” and “1” components with α = 1/
√
2 and β = ±1/
√
2. R k , shown on
the right-hand side in (12.38), adds a phase factor to one of the components. Note
that these operators transform one qubit at their input to one qubit at their output.
Moreover, all operators are represented as unitary matrices, because they describe
the transformation of one spin state to a different spin state, but they do not change
the magnitude of the spin.
In order to describe multi-input gates we introduce states that describe multiple
qubits q 1 and q 2 as the tensor product of the individual qubits: |q 1 q 2 = |q 1 ⊗ |q 2 .
Using this notation we introduce the controlled-not, or CNOT gate, which operates
on two qubits |q 1 q 2 and flips q 2 , but only if q 1 = 1. We can therefore describe it
through
CNOT = |0000| + |0101| + |1011| + |1110| ,
(12.39)
where q| denotes the transpose of |q. It is straightforward to understand the action
of CNOT on, for example, |11, because only the third term in (12.39) is non-zero
and leads to |10 at the output. Since the first qubit is “1,” the second qubit is flipped.