Description
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).
- Let and. Define and .
- Prove that A = A0 ∪ A1 and ∅ = A0 ∩ A1.
- Suppose that a ∈ A1. Prove that a + A0 = A1 and a + A1 = A0. Explain why this implies |A0| = |A1| if A1 6= ∅.
- Prove that
(
X a·g |A| if a · g = 0 for all a ∈ A,
(−1) =
0 otherwise.
a∈A
- Using the previous question, prove the assertion on page 119 that
if and only if a = b ∈ D⊥ (the book uses E∗).
- 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).
- 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.
1
