Exam Preparation Deck

Question 1

How can any qubit state be represented by two angles, \phi and \theta?

Answer 1

Question 2

How do you express matrix M into a linear sum of outer products?

How can you retrieve the (i,j)-th entry from matrix M?

Answer 2

Question 3

Define the tensor product of two matrices A and B.

Answer 3

Question 4

How do you change the basis of a vector from standard i to another orthonormal one, say u_i?

Answer 4

Question 5

Suppose U is the change of basis matrix from i to u_i.

Suppose matrix A is in basis i. How do you change its basis to u_i?

Answer 5

Question 6

How can you approximate any unitary operation?

Answer 6

Any unitary operation can be approximated to any required degree of accuracy using only gates from the set {CNOT, H, T}.

Question 7

What is a quantum black box?

Describe Deutsch’s algorithm.

Answer 7

Maps x, y to x, y + f(x).

Question 8

Describe BB84 protocol.

How can Alice generate a shared key with Bob securely?

Answer 8

Question 9

Define Bell State \beta_{z,x}

Answer 9

Question 10

How can you prepare a Bell State (z,x) from computational basis?

Answer 10

Question 11

Illustrate how superdense coding works.

How can you get two bits of information from one entangled qubit?

Answer 11

Question 12

Suppose Alice has a state \phi. How can she teleport the state to Bob, assuming that they share a EPR pair?

Answer 12

Question 13

Draw out the circuit diagram for Grover’s algorithm.

Clearly define the gates used.

Answer 13

V is known as the phase oracle, which only flips basis vector a.

So it has form I - 2|a>

Question 14

Describe a quantum routine that finds factors of number N.

Answer 14

Question 15

Find a concise way of describing the n-bit Quantum Fourier Transform.

Answer 15

Question 16

Describe a quantum method in finding the order of a function f.

Answer 16

1. Pass the uniform superposition sum_x(x, 0) to quantum black box. The result is sum_x(x, f(x)).
2. Measure the second register. Denote outcome by f_0. Then result is sum_k(x_0 + kr, f_0), where r is the order. First register contains a periodic structure.
3. Apply QFT to the first register.
4. Measure the first register. It is likely to get a y such that ry/2^n is an integer. So y is an integer of r/2^n. Can recover r by continued fraction expansion.

Question 17

Define the four complexity classes:

• P (Deterministic polynomial time)
• PP (Probabilistic polynomial time)
• BPP (Bounded-error probabilistic polynomial time)
• BQP (Bounded-error quantum polynomial time)

Answer 17

Question 18

Define the complexity classes:

• NP (Non-deterministic polynomial time)
• MA (Merlin-Arthur)
• QMA (Quantum Merlin-Arthur)

Answer 18

Arthur is a polynomial-time Turing machine. It can verify solutions in polynomial time…?