References

## Quantum Mechanics

### 1. Superposition

Quantum state is a (complex) superposition of classical states.

Here, the coefficients are complex numbers called amplitudes.

The states

are the basis of the N-dimensional Hilbert space.

For example, the state can be spin state, angular momentum, etc.

### 2. Measurement

The (superposed) state is not observable, but the we will see only one of the classical state by "measurement". The probability of measurement to a state, |j>, is the square of the amplitude.

$P(j) = |\alpha_j|^2$

The measurement is non-unitary, i.e., irreversible.

### 3. Unitary Evolution

Operator: change a state to another state

Quantum mechanical operators are linear. For a finite Hilbert space, linear operators can be represented by complex matrices.

Quantum mechanical time-evolution is unitary.

Unitarity is the complex version of orthonormality.

A real matrix is orthonormal if it is orthogonal and the norm of each column(row) is 1, or

$O^{-1} = O^T$

A complex matrix is unitary if it is (complex-conjugated) orthogonal and the complex norm of each column(row) is 1, or

$U^{-1} = U^{\dagger} = U^{*T}$

## Qubits and Quantum Memory

### 1. Qubits

A bit, which can be 0 or 1, is the unit of information in classical computation.

A "qubit" (quantum bit) is a (complex) superposition of 0 and 1.

which lives in 2-dim complex space.

n-bits can represent 2^n state.

n-qubit represents a vector in 2^n dimensional complex space.

The basis of this space can be written in many ways. For example, in 2-qubit case,

is called Cartesian product. Or, briefly, we can write as

$\left.|00\right>, \left.|01\right>, \left.|10\right>, \left.|11\right> or \left.|0\right>, \left.|1\right>, \left.|2\right>, \left.|3\right>$

### 2. Entanglement

If we measure the first qubit, we can find the state of the second qubit without measuring it.

In general, a bipartite state is called entangled if it cannot be written as a tensor product of two states.

Entanglement is analogous to statistical independence of two probability distributions.

### 3. Elementary gates

In analogy to classical logic gates like AND, OR and NOT, a unitary operation on qubits is called a gate.

Ex.0) The Paulit matrices I, X, Y, Z are 1-qubit gates

Ex.1) Phase Gate

which corresponds to the unitary matrix

Ex.2) Hadamard transform

or

Ex.3) CNOT (controlled-not gate) : 2-qubit gate which negates the second qubit

The first qubit is called the "control" qubit, the second the "target" qubit. Its matrix form is

### 4. Quantum Teleportation

1, Alice wants to send a qubit state to Bob

Alice also shares an EPR-pair

with Bob and the second state belongs to Bob. The joint state is

2. The first two qubits belong to Alice and she performs a CNOT on her two qubits and a Hadamard transform on her first qubit. The joint state is now written as

3. Now, Alice measures her two qubits and sends the result (ab) to Bob over a classical channel.

4. Bob wants to regain the qubit

First, if b = 1, he applies a bitflip(X-gate) on his qubit.

Second, if a = 1, he applies a phaseflip (Z-gate).

For instance, if ab = 11, then Bob knows that his qubit is

so he needs to do a bitflip and a phaseflip.

5. Now, Alice's qubit is destroyed. So, teleporting moves a qubit from Alice to Bob, rather than copying it.

## The Circuit Model and Deutscha-Jozsa

### 1. Quantum Computation

There are two models for quantum computation: the quantum Turing machine and the quantum circuit model. They are equivalent in the sense that they can simulate each other in polynomial time.

#### Classical Circuits

a Boolean circuit is a finite DAG with AND, OR and NOT gates.

#### Quantum Circuits

A quantum gate is a unitary transformation on a small number of qubits

Ex) 1-qubit gate: bitflip(X), phaseflip(Z), Hadamard gate(H)

Ex) 2-qubit gate: controlled-NOT(CNOT)

Ex) 3-qubit gate: Toffoli gate (or CCNOT). Any classical reversible computation can be implemented by a circuit of Toffoli gates.

A quantum circuit can be constructed by applying the above gates parallelly and sequentially.

For example,

The resulting state is an entangled state.

### 2. Universality of various sets of elementary gates

(1) The set of all 1-qubit operations together with the 2-qubit CNOT gate is universal, meaning that any other unitary transformation can be built from these gates.

(2) The set consisting of CNOT, Hadamard and the pahse-gate T is universal in the sense of approximation, where T represents 45-degrees phase rotation.

$T = R_{\pi/4}$

(3) The set of Hadamard and Toffoli(CCNOT) is universal for all real unitary(orthonormal) transformations in the sense of approximation.

### 3. Quantum Parallelism

A quantum gate is a linear operation, so it operates parallelly on a superposed state.

### 4. The Early Algorithms

The two main successes of quantum algorithms so far are Shor's factoring algorithm(1994) and Grover's search algorithm(1996), explained in later chapters.

#### Query (black-box, oracle)

We consider N-bit input with N=2^n so that we can address each bit using n-bit index i.

We want a unitary query operation with n+1 qubits.

Sometimes "phase-oracle" is more convenient.

#### Deutsch-Jozsa

1 Start from n-qubit zero state.

2. Apply a Hadamard on each qubit.

3. Apply a query (phase-oracle)

4. Apply another Hadamard to each qubit

The amplitude of the n-qubit zero state in the final state is

Hence the final observation is n-qubit zero state if x is constant and will yield some other state if x is balanced.

In classical deterministic algorithm, we need at least N/2 + 1 queries.

However, if some error is allowed, we can query x at only two positions and say "constant" if they same and "balanced" if they are different. Therefore, the quantum-classical separation of this problem only holds if we consider algorithms without error probability.

#### Bernsteion-Vazirani

Solved using the same algorithm as the Deutsch_jozsa's. Note that, after applied the first Hadamard and phase-oracle, the zero state becomes

Since the Hadamard transform is the inverse of itself, application of the last Hadamard transform yields the classical state |a>.

Classical algorithm needs n queries for information-theoretic reasons. A recursive version of Bernstein and Vazirani algorithm can be solved in poly(n) steps while classical randomized algorithm rees n^log(n) steps.