[SOLVED] Quantum computing (cs5100) : problem set 2

1. Construct a CNOT gate from two Hadamard gates and one controlled-Z gate. Recall,
the controlled-Z gate maps |11⟩ → −|11⟩ and acts like the identity on the other basis
states. (10 marks)
2. A SWAP-gate interchanges two qubits, i.e., it maps basis state |a, b⟩ to |b, a⟩. Implement a SWAP-gate using only CNOT gates. When using a CNOT, you’re allowed to
use either of the 2 bits as the control, but be explicit about this. (10 marks)
3. Let U be a 1-qubit unitary that we would like to implement in a controlled way, i.e.,
we want to implement the map |c⟩|b⟩ 7→ |c⟩U
c
|b⟩ for all c, b ∈ {0, 1} (here U
0 = I and
U
1 = U). Suppose there exist 1-qubit unitaries A, B, and C, such that ABC = I and
AXBXC = U, where X is the NOT-gate. Give a circuit that acts on two qubits and
implements a controlled-U gate, using CNOTs and (uncontrolled) A, B, and C gates.
(10 marks)
4. Let C be a given quantum circuit consisting of T many gates, which may be CNOTs
and single-qubit gates. Show that we can implement C in a controlled way using O(T)
Toffoli gates, CNOTs and single-qubit gates, and no auxiliary qubits other than the
controlling qubit. (10 marks)
5. Recall we can apply a standard query Ox to bitstring x ∈ {0, 1}
N
in the usual form:
Ox : |i, b⟩ 7→ |i, b ⊕ xi⟩.
1
Give a circuit, involving one application of Ox and some other gates, to implement the
following controlled-phase-query:
Cx : |c, i, 0⟩ 7→ (−1)cxi
|c, i, 0⟩.
The idea here is that we implement a phase-query to x, but only in case the controlqubit (c ∈ {0, 1}) is set to 1. (10 marks)
6. Show that a standard query Ox can be implemented using one controlled-phase-query
to x (which maps |c, i⟩ 7→ (−1)cxi
|c, i⟩, so the phase is added only if the control bit is
c = 1), and possibly some auxiliary qubits and other gates. (10 marks)
7. Give a circuit that maps |0
n
, b⟩ 7→ |0
n
, 1⊕b⟩ for b ∈ {0, 1}, and that maps |i, b⟩ 7→ |i, b⟩
whenever i ∈ {0, 1}
n
{0
n}. You are allowed to use elementary gates, including Toffoli
gates, as well as auxiliary qubits that are initially |0⟩ and that should be put back to
|0⟩ at the end of the computation. (10 marks)
8. Suppose we can make queries of the type |i, b⟩ 7→ |i, b ⊕ xi⟩ to input x ∈ {0, 1}
N
,
with N = 2n
. Let x
′ be the input x with its first bit flipped (e.g., if x = 0110 then
x
′ = 1110). Give a circuit that implements a query to x
′
. Your circuit may use one
query to x. (10 marks)
9. Suppose our N-bit input x satisfies the following promise: either (1) the first N/2 bits
of x are all 0 and the second N/2 bits are all 1; or (2) the number of 1s in the first half
of x plus the number of 0s in the second half, equals N/2. Modify the Deutsch-Jozsa
algorithm to efficiently distinguish these two cases (1) and (2). (10 marks)
10. Consider the following generalization of Simon’s problem: the input is x = (x0, . . . , xN−1),
with N = 2n and xi ∈ {0, 1}
n with the property that there is some unknown subspace
V ⊆ {0, 1}
n
(where {0, 1}
n
is the vector space of n-bit strings with entrywise addition modulo 2) such that xi = xj
iff there exists a v ∈ V such that i = j ⊕ v. The
usual definition of Simon’s problem corresponds to the case of 1-dimensional subspace
V = {0, s}.
Show that one run of Simon’s algorithm now produces a j ∈ {0, 1}
n
that is orthogonal
to the whole subspace (i.e., j · v = 0 mod 2 for every v ∈ V ). (10 marks)
2