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.
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
A complex matrix is unitary if it is (complex-conjugated) orthogonal and the complex norm of each column(row) is 1, or
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
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.
(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.
