Duplicate
🎱

# Introduction to Quantum Computing

Created
2021/07/04 06:55
발표일자
2020/12/07
발표자
이동훈
Tags
Quantum
✅main
포스팅 종류
논문리뷰
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
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.