QUANTUM ALGORITHMS
For a subgroup define
= 0 for all ,
where a · g is the dot product modulo 2 of g and g (regarded as Z2-vectors).
1. Let and . Define and .
(i) Prove that A = A0 ∪ A1 and ∅ = A0 ∩ A1.
(ii) Suppose that a ∈ A1. Prove that a + A0 = A1 and a + A1 = A0. Explain why this implies |A0| = |A1| if A1 6= ∅.
(iii) Prove that
(
X a·g |A| if a · g = 0 for all a ∈ A,
(−1) =
0 otherwise.
a∈A
2. Using the previous question, prove the assertion on page 119 that
if and only if a = b ∈ D⊥ (the book uses E∗).
3. We say that a subgroup is maximal if
and
then .
Similarly, is minimal if
• {0} 6= A and
• if {0} ≤ X ≤ A then {0} = X or X = A.
Prove that A is maximal if and only if A⊥ is minimal (use this in your solution to 13.1).
4. In Simon’s algorithm, what would happen if instead of measuring the first block of qubits, we measured the second block of qubits? Calculate the density matrix and describe what distribution it represents.
