MACM 476:  Quantum Algorithms

Assignment 4

Due at 11:59pm on MARCH 30. All solutions must be in LATEX’ed PDF form.

Question 1 [7 points]: Coset states and Generalized Simon

Recall that the dot product on the vector space is defined as x · y = x1y1  ⊕ x2y2 ⊕ · · · ⊕ xnyn  where x = (x1, x2,..., xn) and y = (y1, y2,..., yn). For any subspace S of , define the orthogonal complement of S with respect to the dot product as

1. Let and show that

Hint: show that for any z ∈ , either z ∈ S丄 or z · s = 0 for exactly half the elements of S.

2.  Show that Simon’s algorithm works with no changes to the quantum part to solve the Boolean hidden subgroup problem. Explicitly, given a linear subspace S of Z2(n)  and f(x) = f(y) if and only if

x = y ⊕ s for some s ∈ S, find a basis for S.  You should sketch an algorithm in pseudo-code.

Question 2 [3 points]: Factoring, classically

In this question we will factor the number 21 classically.  You do not have to show your calculations and you may find it useful to use a calculator or program to calculate the GCD. If it were me, I would probably write a program to do it.

1.  Compute the period of f(x) = 5x   mod 21 — that is, find the smallest integer r such that 5r  ≡  1 mod 21.

2.  Compute GCD(5r/2 + 1, 21), GCD(5r/2 — 1, 21). What’s the problem?

3. Now repeat steps 1 and 2 with f(x) = 2x    mod 21 to factor 21 into its prime factors.

Question 3 [3 points]: QFT or QFT—1?

In lectures and in the notes we’ve been pretty cavalier about whether we use QFT or the QFTt  in period finding and phase estimation. In this question we’ll investigate why.

1.  Determine what transformation is applied by  — that is, compute QFT2n(QFT2n |x⟩) where x ∈ {0, 1}n.

2. Now suppose you accidentally applied QFT when you should have applied QFT-1  and measured the result to get a bit string y ∈ {0, 1}n.  How could you classically recover the “correct” bit string z ∈ {0, 1}n  that you would have measured if you had instead applied QFT-1 ?

Question 4 [8 points]: Qutrit quantum computing

Much of quantum computation can be generalized to higher-dimensional qudits.  Most gates we’ve seen have higher-dimensional generalizations, like the Pauli gates X, Y, Z and the Hadamard or Fourier gate

H. In this question we will explore this notion briefly.

Consider a qutrit, which is a 3-dimensional quantum particle and whose state is a unit vector in C3 .

As discussed in class, we denote the computational basis of C3  as {|0⟩, |1⟩, |2⟩}, or  |x⟩ where x ∈ Z3, the integers mod 3. Denote the primitive third root of unity as ω3  = e2πi/3 .  The Pauli X and Z operators on a qutrit can now be defined as

Likewise, the qutrit Hadamard gate can be defined as

1.  Show that X and Z have order 3 (i.e. X3 = Z3  = I)

2.  Show that XZ = ω3ZX . Use this to calculate k such that XiZj  = ωkZj Xi whenever i,j ∈ {0, 1, 2} .

3.  Show that Ht ZH = X .

4.  Compute the eigenvalues of X and give corresponding (unit) eigenvectors.  Hint:  recall the relation- ship between H and the eigenvectors of X in the qubit case.

5. Now show that Deutsch’s algorithm generalizes to qutrits. Explicitly, given a function f : Z3  → Z3 promised to either be constant or balanced where balanced in this case means for every y ∈ Z3 , there exists exactly one x ∈ Z3  such that f(x) = y, show that Deutsch’s algorithm with the qutrit version of the H gate works the same way.

Hint: you may want to use the fact that over qutrits, H = QFT3, and so

Question 5 [6 points]: A quantum algorithm for SAT?

Given a formula in propositional logic φ — that is, a logical formula over Boolean variables, constants, ∨ , ∧,  =⇒  , and ¬  — the SAT problem is to determine whether there exists a satisfying assignment to the variables in φ .  That is, when viewed as a function from the values of its n variables to {0, 1}, there exists some x1 , . . . , xn  ∈ {0, 1} such that φ(x1,..., xn) = 1.

In this question we’re going to investigate whether or not the type of interference we’ve seen so far suffices (at least, in an obvious way) to give an efficient quantum algorithm for SAT.

1.  Consider the superposition

Show that the amplitude of a computational basis state |x1x2... xn⟩ in the above is non-zero if and only if φ(x1x2... xn) = 1.

In general, given a Boolean function f  :  {0, 1}n  →  {0, 1}, the phase  (—1)yf(x)  acts like a filter, filtering out the unwanted values of x where f(x) = 1.  Part of my research involves the use and generalization of interference patterns like this to allow (classical) computers to symbolically reason about quantum programs.

2.  Can the transformation

be implemented using unitary operations?  Stated more simply, is the state on the right hand side a unit vector for every φ?

3. Now consider the transformation

This transformation is indeed unitary, but we no longer get useful interference as in part 1.  Explain why.

4. Is it likely that we’ll easily discover an efficient quantum algorithm for SAT knowing that an efficient algorithm for SAT would allow us to solve any problem in NP efficiently?