Appendix C — Exercise Solutions

This appendix contains solutions to all exercises in the book.

C.1 Chapter 1: Quantum Mechanics Basics

C.1.1 Solution 1.1: Normalization

Given the unnormalized state \(|\psi\rangle = 2|0\rangle + 2i|1\rangle\):

(a) Calculate \(\langle\psi|\psi\rangle\):

\[ \langle\psi|\psi\rangle = |2|^2 + |2i|^2 = 4 + 4 = 8 \]

(b) Normalize the state:

\[ |\psi_{\text{norm}}\rangle = \frac{|\psi\rangle}{\sqrt{\langle\psi|\psi\rangle}} = \frac{2|0\rangle + 2i|1\rangle}{\sqrt{8}} = \frac{2|0\rangle + 2i|1\rangle}{2\sqrt{2}} = \frac{1}{\sqrt{2}}|0\rangle + \frac{i}{\sqrt{2}}|1\rangle \]

(c) Verify normalization:

\[ \langle\psi_{\text{norm}}|\psi_{\text{norm}}\rangle = \left|\frac{1}{\sqrt{2}}\right|^2 + \left|\frac{i}{\sqrt{2}}\right|^2 = \frac{1}{2} + \frac{1}{2} = 1 \quad \checkmark \]

← Back to Exercise 1.1

---

C.1.2 Solution 1.2: Measurement Probabilities

Given \(|\psi\rangle = \frac{1}{2}|0\rangle + \frac{\sqrt{3}}{2}|1\rangle\):

(a) Measurement probabilities in Z-basis:

\[ P(0) = \left|\frac{1}{2}\right|^2 = \frac{1}{4} \]

\[ P(1) = \left|\frac{\sqrt{3}}{2}\right|^2 = \frac{3}{4} \]

(b) Verification:

\[ P(0) + P(1) = \frac{1}{4} + \frac{3}{4} = 1 \quad \checkmark \]

(c) Post-measurement state after obtaining outcome 1:

\[ |\psi_{\text{post}}\rangle = |1\rangle \]

The state collapses to the measured basis state.

← Back to Exercise 1.2

---

C.1.3 Solution 1.3: Basis Transformation

Express \(|1\rangle\) in the X-basis.

Using the inverse relation from the hint:

\[ |1\rangle = \frac{1}{\sqrt{2}}(|+\rangle - |-\rangle) \]

Verification: Substituting the definitions of \(|+\rangle\) and \(|-\rangle\):

\[ \frac{1}{\sqrt{2}}(|+\rangle - |-\rangle) = \frac{1}{\sqrt{2}}\left[\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) - \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\right] \]

\[ = \frac{1}{2}[(|0\rangle + |1\rangle) - (|0\rangle - |1\rangle)] = \frac{1}{2}(2|1\rangle) = |1\rangle \quad \checkmark \]

← Back to Exercise 1.3

---

C.1.4 Solution 1.4: Cross-Basis Measurement

Given \(|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\):

(a) Z-basis measurement probabilities:

\[ P(0) = \left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}, \quad P(1) = \left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2} \]

(b) X-basis measurement probabilities:

Since \(|+\rangle\) is itself a basis state of the X-basis:

\[ P(+) = 1, \quad P(-) = 0 \]

(c) Explanation:

The state \(|+\rangle\) is a superposition in the Z-basis, so measurements yield random outcomes (50/50). However, \(|+\rangle\) is an eigenstate of the X-basis, so X-measurements always yield the same result with certainty.

This illustrates basis-dependent measurement: the same quantum state appears “definite” in one basis but “random” in another. The choice of measurement basis determines whether we see quantum randomness or deterministic outcomes.

← Back to Exercise 1.4

---

C.1.5 Solution 1.5: Global Phase

Show that \(|\psi\rangle = |0\rangle\) and \(|\psi'\rangle = -|0\rangle = e^{i\pi}|0\rangle\) are physically equivalent.

Z-basis measurements:

For \(|\psi\rangle = |0\rangle\): \[ P(0) = |1|^2 = 1, \quad P(1) = |0|^2 = 0 \]

For \(|\psi'\rangle = -|0\rangle\): \[ P(0) = |-1|^2 = 1, \quad P(1) = |0|^2 = 0 \]

Identical probabilities. \(\checkmark\)

X-basis measurements:

Express both states in X-basis using \(|0\rangle = \frac{1}{\sqrt{2}}(|+\rangle + |-\rangle)\):

For \(|\psi\rangle = |0\rangle = \frac{1}{\sqrt{2}}|+\rangle + \frac{1}{\sqrt{2}}|-\rangle\): \[ P(+) = \frac{1}{2}, \quad P(-) = \frac{1}{2} \]

For \(|\psi'\rangle = -|0\rangle = -\frac{1}{\sqrt{2}}|+\rangle - \frac{1}{\sqrt{2}}|-\rangle\): \[ P(+) = \left|-\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}, \quad P(-) = \left|-\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2} \]

Identical probabilities. \(\checkmark\)

Since both states yield identical measurement probabilities in every basis, they are physically indistinguishable. The global phase factor \(e^{i\pi} = -1\) has no observable effect.

← Back to Exercise 1.5

---

C.1.6 Solution 1.6: Bloch Sphere Coordinates

Given \(|\psi\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{e^{i\pi/4}}{\sqrt{2}}|1\rangle\)

The general Bloch sphere parameterization is:

\[ |\psi\rangle = \cos\frac{\theta}{2}|0\rangle + e^{i\phi}\sin\frac{\theta}{2}|1\rangle \]

Comparing coefficients:

For the \(|0\rangle\) coefficient: \[ \cos\frac{\theta}{2} = \frac{1}{\sqrt{2}} \implies \frac{\theta}{2} = \frac{\pi}{4} \implies \theta = \frac{\pi}{2} \]

For the \(|1\rangle\) coefficient: \[ e^{i\phi}\sin\frac{\theta}{2} = \frac{e^{i\pi/4}}{\sqrt{2}} \]

Since \(\sin\frac{\pi}{4} = \frac{1}{\sqrt{2}}\): \[ e^{i\phi} \cdot \frac{1}{\sqrt{2}} = \frac{e^{i\pi/4}}{\sqrt{2}} \implies e^{i\phi} = e^{i\pi/4} \implies \phi = \frac{\pi}{4} \]

Answer: \(\theta = \frac{\pi}{2}\) (on the equator), \(\phi = \frac{\pi}{4}\) (45° from the \(|+\rangle\) state toward \(|{+i}\rangle\))

← Back to Exercise 1.6

---

C.2 Chapter 2: Entanglement

C.2.1 Solution 2.1: Identifying Entanglement

(a) \(|\psi\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |01\rangle)\)

Factor out the first qubit: \[ |\psi\rangle = \frac{1}{\sqrt{2}}|0\rangle_A \otimes (|0\rangle + |1\rangle)_B = |0\rangle_A \otimes |+\rangle_B \]

Separable - this is a product state.

(b) \(|\psi\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle)\)

Factor out the second qubit: \[ |\psi\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)_A \otimes |0\rangle_B = |+\rangle_A \otimes |0\rangle_B \]

Separable - this is a product state.

(c) \(|\psi\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)\)

Factor: \[ |\psi\rangle = \frac{1}{2}(|0\rangle + |1\rangle)_A \otimes (|0\rangle + |1\rangle)_B = |+\rangle_A \otimes |+\rangle_B \]

Separable - this is a product state.

Conclusion: None of these states are entangled. All three can be factored into tensor products of single-qubit states.

← Back to Exercise 2.1

---

C.2.2 Solution 2.2: Schmidt Decomposition

Given: \(|\psi\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)\)

From Exercise 2.1(c), we showed this factors as: \[ |\psi\rangle = |+\rangle_A \otimes |+\rangle_B \]

Schmidt decomposition: \[ |\psi\rangle = 1 \cdot |+\rangle_A \otimes |+\rangle_B \]

Schmidt rank: \(r = 1\)

Entanglement entropy:

Since there’s only one Schmidt coefficient (\(\lambda_1 = 1\)): \[ S = -1^2 \log_2(1^2) = -1 \cdot 0 = 0 \]

Result: \(S = 0\) bits, confirming the state is separable (not entangled).

← Back to Exercise 2.2

---

C.2.3 Solution 2.3: Entanglement Entropy

Given: \(|\psi\rangle = \frac{2}{\sqrt{5}}|00\rangle + \frac{1}{\sqrt{5}}|11\rangle\)

This is already in Schmidt form with: \[ \lambda_1 = \frac{2}{\sqrt{5}}, \quad \lambda_2 = \frac{1}{\sqrt{5}} \]

Verification of normalization: \[ \lambda_1^2 + \lambda_2^2 = \frac{4}{5} + \frac{1}{5} = 1 \quad \checkmark \]

Entanglement entropy: \[ S = -\lambda_1^2 \log_2(\lambda_1^2) - \lambda_2^2 \log_2(\lambda_2^2) \]

\[ S = -\frac{4}{5}\log_2\left(\frac{4}{5}\right) - \frac{1}{5}\log_2\left(\frac{1}{5}\right) \]

\[ S = -0.8 \log_2(0.8) - 0.2 \log_2(0.2) \]

\[ S = -0.8 \times (-0.322) - 0.2 \times (-2.322) \]

\[ S = 0.258 + 0.464 = 0.722 \text{ bits} \]

Is it maximally entangled?

No. For 2 qubits, maximal entanglement gives \(S = 1\) bit (achieved by Bell states with equal Schmidt coefficients \(\lambda_1 = \lambda_2 = \frac{1}{\sqrt{2}}\)).

This state has \(S \approx 0.722\) bits, so it is partially entangled.

← Back to Exercise 2.3

---

C.2.4 Solution 2.4: Bell State Transformations

Starting with \(|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)\):

To get \(|\Phi^-\rangle\): Apply \(Z\) to qubit B

\[ (I \otimes Z)|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|0\rangle Z|0\rangle + |1\rangle Z|1\rangle) \]

\[ = \frac{1}{\sqrt{2}}(|0\rangle|0\rangle + |1\rangle(-|1\rangle)) = \frac{1}{\sqrt{2}}(|00\rangle - |11\rangle) = |\Phi^-\rangle \quad \checkmark \]

To get \(|\Psi^+\rangle\): Apply \(X\) to qubit B

\[ (I \otimes X)|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|0\rangle X|0\rangle + |1\rangle X|1\rangle) \]

\[ = \frac{1}{\sqrt{2}}(|0\rangle|1\rangle + |1\rangle|0\rangle) = \frac{1}{\sqrt{2}}(|01\rangle + |10\rangle) = |\Psi^+\rangle \quad \checkmark \]

To get \(|\Psi^-\rangle\): Apply \(Z\) then \(X\) to qubit B (or \(X\) then \(Z\))

\[ (I \otimes Z)|\Psi^+\rangle = \frac{1}{\sqrt{2}}(|0\rangle Z|1\rangle + |1\rangle Z|0\rangle) \]

\[ = \frac{1}{\sqrt{2}}(|0\rangle(-|1\rangle) + |1\rangle|0\rangle) = \frac{1}{\sqrt{2}}(-|01\rangle + |10\rangle) \]

\[ = -\frac{1}{\sqrt{2}}(|01\rangle - |10\rangle) = -|\Psi^-\rangle \]

The global phase \(-1\) is physically irrelevant, so this equals \(|\Psi^-\rangle\). \(\checkmark\)

Summary:

Target State	Gate on B
\(\|\Phi^+\rangle\)	\(I\) (identity)
\(\|\Phi^-\rangle\)	\(Z\)
\(\|\Psi^+\rangle\)	\(X\)
\(\|\Psi^-\rangle\)	\(XZ\) (or \(ZX\))

← Back to Exercise 2.4

---

C.2.5 Solution 2.5: Partial Measurement

Given: \(|\Psi^+\rangle = \frac{1}{\sqrt{2}}(|01\rangle + |10\rangle)\)

(a) Measure qubit A in Z-basis, outcome 0:

The state has two terms: - \(|01\rangle\): qubit A is in \(|0\rangle\) ✓ (matches outcome) - \(|10\rangle\): qubit A is in \(|1\rangle\) ✗ (doesn’t match)

Only the \(|01\rangle\) term survives. The post-measurement state is:

\[ |\psi_{\text{post}}\rangle = |01\rangle = |0\rangle_A \otimes |1\rangle_B \]

(b) Probability of measuring qubit B as 1:

After the measurement in part (a), qubit B is in state \(|1\rangle\) with certainty.

\[ P(B = 1) = 1 \]

This demonstrates the perfect anti-correlation in \(|\Psi^+\rangle\): if A is measured as 0, B must be 1, and vice versa.

← Back to Exercise 2.5

---

C.2.6 Solution 2.6: Creating Bell States

Initial state: \(|00\rangle\)

Step 1: Apply Hadamard gate \(H\) to qubit A

\[ H|0\rangle_A \otimes |0\rangle_B = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)_A \otimes |0\rangle_B \]

\[ = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle) \]

Step 2: Apply CNOT gate (A = control, B = target)

The CNOT gate flips qubit B if qubit A is \(|1\rangle\): - \(\text{CNOT}|00\rangle = |00\rangle\) (A=0, B unchanged) - \(\text{CNOT}|10\rangle = |11\rangle\) (A=1, B flipped)

Applying to our state: \[ \text{CNOT}\left[\frac{1}{\sqrt{2}}(|00\rangle + |10\rangle)\right] = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) = |\Phi^+\rangle \quad \checkmark \]

Circuit diagram:

|0⟩ ─────[H]─────●─────
                 │
|0⟩ ─────────────⊕─────

This is the standard Bell state preparation circuit, producing \(|\Phi^+\rangle\).

← Back to Exercise 2.6

---

C.3 Chapter 3: n-Qubit Systems

C.3.1 Solution 3.1: GHZ State Verification

For \(|\text{GHZ}_4\rangle = \frac{1}{\sqrt{2}}(|0000\rangle + |1111\rangle)\):

(a) Probability of measuring outcome \(|0101\rangle\):

The GHZ state only contains the basis states \(|0000\rangle\) and \(|1111\rangle\). The state \(|0101\rangle\) has zero amplitude:

\[ P(0101) = |\langle 0101 | \text{GHZ}_4 \rangle|^2 = 0 \]

This is a key feature of GHZ states: only “all-zeros” or “all-ones” outcomes are possible.

(b) Measuring qubits 1 and 2 with outcomes 0 and 1:

Check which terms in the GHZ state match this outcome: - \(|0000\rangle\): qubit 1 = 0 ✓, qubit 2 = 0 ✗ - \(|1111\rangle\): qubit 1 = 1 ✗, qubit 2 = 1 ✓

Neither term matches! This measurement outcome is impossible for a GHZ state.

\[ P(\text{qubit 1} = 0, \text{qubit 2} = 1) = 0 \]

This demonstrates the perfect correlation in GHZ states: all qubits must have the same value.

← Back to Exercise 3.1

---

C.3.2 Solution 3.2: W State Properties

For \(|W_4\rangle = \frac{1}{2}(|1000\rangle + |0100\rangle + |0010\rangle + |0001\rangle)\):

(a) Probability of measuring \(|1000\rangle\):

\[ P(1000) = \left|\frac{1}{2}\right|^2 = \frac{1}{4} \]

By symmetry, each of the four basis states has probability \(\frac{1}{4}\).

(b) After measuring qubit 1 and getting 0:

Terms with qubit 1 = 0: \(|0100\rangle\), \(|0010\rangle\), \(|0001\rangle\)

Probability of outcome 0: \[ P(\text{qubit 1} = 0) = 3 \times \left|\frac{1}{2}\right|^2 = \frac{3}{4} \]

Unnormalized post-measurement state: \[ \frac{1}{2}(|0100\rangle + |0010\rangle + |0001\rangle) \]

Normalizing (divide by \(\sqrt{P(0)} = \sqrt{3/4} = \frac{\sqrt{3}}{2}\)):

\[ |\psi_{\text{post}}\rangle = \frac{1}{\sqrt{3}}(|0100\rangle + |0010\rangle + |0001\rangle) \]

\[ = |0\rangle_1 \otimes \frac{1}{\sqrt{3}}(|100\rangle + |010\rangle + |001\rangle)_{234} \]

\[ = |0\rangle_1 \otimes |W_3\rangle_{234} \quad \checkmark \]

This demonstrates the robustness of W states: losing one qubit (with outcome 0) preserves W-type entanglement in the remaining qubits.

← Back to Exercise 3.2

---

C.3.3 Solution 3.3: Entanglement Entropy Calculation

For \(|W_3\rangle = \frac{1}{\sqrt{3}}(|100\rangle + |010\rangle + |001\rangle)\) with partition \(12|3\):

Step 1: Rewrite in terms of the bipartition

Group by qubit 3’s value: \[ |W_3\rangle = \frac{1}{\sqrt{3}}|10\rangle_{12}|0\rangle_3 + \frac{1}{\sqrt{3}}|01\rangle_{12}|0\rangle_3 + \frac{1}{\sqrt{3}}|00\rangle_{12}|1\rangle_3 \]

\[ = \frac{1}{\sqrt{3}}(|10\rangle + |01\rangle)_{12} \otimes |0\rangle_3 + \frac{1}{\sqrt{3}}|00\rangle_{12} \otimes |1\rangle_3 \]

Step 2: Find Schmidt decomposition

Normalize the first term’s coefficient on system 12: \[ |W_3\rangle = \sqrt{\frac{2}{3}} \cdot \frac{1}{\sqrt{2}}(|10\rangle + |01\rangle)_{12} \otimes |0\rangle_3 + \frac{1}{\sqrt{3}}|00\rangle_{12} \otimes |1\rangle_3 \]

Schmidt coefficients: \[ \lambda_1 = \sqrt{\frac{2}{3}}, \quad \lambda_2 = \frac{1}{\sqrt{3}} = \sqrt{\frac{1}{3}} \]

Step 3: Calculate entropy

\[ \lambda_1^2 = \frac{2}{3}, \quad \lambda_2^2 = \frac{1}{3} \]

\[ S = -\frac{2}{3}\log_2\left(\frac{2}{3}\right) - \frac{1}{3}\log_2\left(\frac{1}{3}\right) \]

\[ S = -\frac{2}{3}(\log_2 2 - \log_2 3) - \frac{1}{3}(-\log_2 3) \]

\[ S = -\frac{2}{3}(1 - 1.585) + \frac{1}{3}(1.585) \]

\[ S = -\frac{2}{3}(-0.585) + 0.528 = 0.390 + 0.528 \approx 0.918 \text{ bits} \]

Result: \(S \approx 0.918\) bits, which is less than 1 bit (not maximally entangled).

← Back to Exercise 3.3

---

C.3.4 Solution 3.4: LOCC Impossibility

Why can’t we convert \(|\text{GHZ}_3\rangle\) to \(|W_3\rangle\) using LOCC?

Key insight: LOCC operations can only decrease (or preserve) entanglement measures, never increase them.

Argument 1: Different bipartite entanglement structure

• GHZ has \(S = 1\) bit for all bipartitions (1|23, 2|13, 3|12)
• W has \(S \approx 0.918\) bits for all bipartitions

If we could convert GHZ → W via LOCC, we would be decreasing entropy, which is allowed. But we also cannot convert W → GHZ, because that would require increasing entropy.

Argument 2: Robustness under qubit loss

• GHZ: Losing any qubit leaves the other two in a product state (zero entanglement)
• W: Losing any qubit (with outcome 0) leaves the other two in a Bell state (maximal 2-qubit entanglement)

LOCC cannot change this fundamental behavior. If GHZ could become W, then losing a qubit from the “converted” state should behave like W, but it doesn’t.

Argument 3: Genuine vs distributed entanglement

GHZ has “all-or-nothing” correlations: measuring any qubit determines all others. W has “distributed” correlations: information is spread across all qubits. These are fundamentally incompatible structures that LOCC cannot interconvert.

Conclusion: GHZ and W represent different entanglement classes that are LOCC-inequivalent.

← Back to Exercise 3.4

---

C.3.5 Solution 3.5: Multipartite Correlation

For \(|\psi\rangle = \frac{1}{2}(|000\rangle + |011\rangle + |101\rangle + |110\rangle)\):

(a) Check all bipartitions for entanglement:

Partition 1|23: \[ |\psi\rangle = \frac{1}{2}|0\rangle(|00\rangle + |11\rangle) + \frac{1}{2}|1\rangle(|01\rangle + |10\rangle) \]

\[ = \frac{1}{\sqrt{2}}|0\rangle \cdot \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) + \frac{1}{\sqrt{2}}|1\rangle \cdot \frac{1}{\sqrt{2}}(|01\rangle + |10\rangle) \]

\[ = \frac{1}{\sqrt{2}}|0\rangle|\Phi^+\rangle + \frac{1}{\sqrt{2}}|1\rangle|\Psi^+\rangle \]

Schmidt rank = 2 → Entangled ✓

Partition 2|13:

Grouping by qubit 2: - Qubit 2 = 0: \(|000\rangle, |101\rangle\) → qubits 1,3 in \((|00\rangle + |11\rangle)\) - Qubit 2 = 1: \(|011\rangle, |110\rangle\) → qubits 1,3 in \((|01\rangle + |10\rangle)\)

\[ |\psi\rangle = \frac{1}{\sqrt{2}}|0\rangle_2|\Phi^+\rangle_{13} + \frac{1}{\sqrt{2}}|1\rangle_2|\Psi^+\rangle_{13} \]

Schmidt rank = 2 → Entangled ✓

Partition 3|12:

Grouping by qubit 3: - Qubit 3 = 0: \(|000\rangle, |110\rangle\) → qubits 1,2 in \((|00\rangle + |11\rangle)\) - Qubit 3 = 1: \(|011\rangle, |101\rangle\) → qubits 1,2 in \((|01\rangle + |10\rangle)\)

\[ |\psi\rangle = \frac{1}{\sqrt{2}}|0\rangle_3|\Phi^+\rangle_{12} + \frac{1}{\sqrt{2}}|1\rangle_3|\Psi^+\rangle_{12} \]

Schmidt rank = 2 → Entangled ✓

Conclusion: Yes, \(|\psi\rangle\) is genuinely tripartite entangled (entangled across all bipartitions).

(b) Entanglement entropy for partition 1|23:

From part (a), the Schmidt coefficients are \(\lambda_1 = \lambda_2 = \frac{1}{\sqrt{2}}\).

\[ S = -\frac{1}{2}\log_2\frac{1}{2} - \frac{1}{2}\log_2\frac{1}{2} = 1 \text{ bit} \]

This state has maximal bipartite entanglement for partition 1|23.

← Back to Exercise 3.5

---

C.3.6 Solution 3.6: Fragility vs Robustness

Experimental Design: Comparing GHZ and W State Robustness

Setup: 1. Prepare many copies of \(|\text{GHZ}_3\rangle = \frac{1}{\sqrt{2}}(|000\rangle + |111\rangle)\) 2. Prepare many copies of \(|W_3\rangle = \frac{1}{\sqrt{3}}(|100\rangle + |010\rangle + |001\rangle)\) 3. Distribute qubits to three parties: Alice (qubit 1), Bob (qubit 2), Charlie (qubit 3)

Experiment: Simulate qubit loss by measuring qubit 1

Alice measures her qubit in the Z-basis, then Bob and Charlie test whether their qubits are still entangled.

For GHZ states: - Alice measures 0 → Bob and Charlie have \(|00\rangle\) (product state) - Alice measures 1 → Bob and Charlie have \(|11\rangle\) (product state) - Result: Bob and Charlie share NO entanglement, regardless of Alice’s outcome

For W states: - Alice measures 1 (prob. 1/3) → Bob and Charlie have \(|00\rangle\) (product state) - Alice measures 0 (prob. 2/3) → Bob and Charlie have \(\frac{1}{\sqrt{2}}(|10\rangle + |01\rangle) = |\Psi^+\rangle\) (Bell state!) - Result: With probability 2/3, Bob and Charlie still share maximal entanglement

Verification:

Bob and Charlie perform Bell inequality tests (CHSH) on their remaining qubits: - GHZ remnants: Always satisfy classical bounds (no entanglement) - W remnants: Violate Bell inequality 2/3 of the time (quantum entanglement preserved)

Conclusion: This experiment directly demonstrates that W states are robust to qubit loss while GHZ states are fragile.

← Back to Exercise 3.6

---

C.3.7 Solution 3.7: n-Qubit Generalization

General W state formula:

\[ |W_n\rangle = \frac{1}{\sqrt{n}}\sum_{i=1}^{n} |0\cdots 0 \underbrace{1}_{i\text{-th position}} 0 \cdots 0\rangle \]

This is an equal superposition of all \(n\) basis states with exactly one qubit in \(|1\rangle\).

Claim: Measuring \(k\) qubits and getting all outcomes 0 leaves the remaining \(n-k\) qubits in state \(|W_{n-k}\rangle\).

Proof:

Let qubits \(1, 2, \ldots, k\) be measured, and qubits \(k+1, \ldots, n\) remain.

The \(|W_n\rangle\) state has \(n\) terms. Each term has exactly one qubit in state \(|1\rangle\): - Terms where the \(|1\rangle\) is in positions \(1, 2, \ldots, k\): These have at least one measured qubit = 1, so they don’t survive the “all zeros” measurement. - Terms where the \(|1\rangle\) is in positions \(k+1, \ldots, n\): These have all measured qubits = 0, so they survive.

Number of surviving terms: \(n - k\)

Unnormalized post-measurement state: \[ \frac{1}{\sqrt{n}} \sum_{i=k+1}^{n} |0\rangle^{\otimes k} \otimes |0\cdots 1_i \cdots 0\rangle \]

Probability of all-zeros outcome: \[ P(0^k) = \frac{n-k}{n} \]

Normalized post-measurement state: \[ |\psi_{\text{post}}\rangle = \frac{1}{\sqrt{n-k}} \sum_{i=k+1}^{n} |0\cdots 1_i \cdots 0\rangle = |W_{n-k}\rangle \quad \square \]

Physical interpretation: The W state “stores” one unit of excitation distributed across \(n\) qubits. Measuring \(k\) qubits and finding them all in \(|0\rangle\) confirms the excitation is among the remaining \(n-k\) qubits, which are now in \(|W_{n-k}\rangle\).

Corollary: This process can continue until only 2 qubits remain, yielding: \[ |W_2\rangle = \frac{1}{\sqrt{2}}(|10\rangle + |01\rangle) = |\Psi^+\rangle \]

A Bell state! This is why W states are robust: entanglement persists down to the last pair.

← Back to Exercise 3.7

---

C.4 Chapter 4: MBQC Foundations

C.4.1 Solution 4.1: Cluster State Preparation

For a 2-qubit cluster state on graph \(1 — 2\):

(a) Initial state \(|+\rangle^{\otimes 2}\):

\[ |+\rangle^{\otimes 2} = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \]

\[ = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle) \]

(b) Apply \(CZ_{12}\):

The controlled-Z gate acts as: \(CZ|ab\rangle = (-1)^{a \cdot b}|ab\rangle\)

• \(CZ|00\rangle = (-1)^0|00\rangle = |00\rangle\)
• \(CZ|01\rangle = (-1)^0|01\rangle = |01\rangle\)
• \(CZ|10\rangle = (-1)^0|10\rangle = |10\rangle\)
• \(CZ|11\rangle = (-1)^1|11\rangle = -|11\rangle\)

Resulting cluster state: \[ |\text{Cluster}\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle) \]

(c) Verify entanglement by attempting to factor:

Assume \(|\text{Cluster}\rangle = (\alpha|0\rangle + \beta|1\rangle) \otimes (\gamma|0\rangle + \delta|1\rangle)\)

Expanding: \(\alpha\gamma|00\rangle + \alpha\delta|01\rangle + \beta\gamma|10\rangle + \beta\delta|11\rangle\)

Comparing coefficients with \(\frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle)\):

\[ \alpha\gamma = \frac{1}{2}, \quad \alpha\delta = \frac{1}{2}, \quad \beta\gamma = \frac{1}{2}, \quad \beta\delta = -\frac{1}{2} \]

From the first three equations: \(\alpha\gamma = \alpha\delta\) implies \(\gamma = \delta\), and \(\alpha\gamma = \beta\gamma\) implies \(\alpha = \beta\).

But if \(\alpha = \beta\) and \(\gamma = \delta\), then: \[ \beta\delta = \alpha\gamma = \frac{1}{2} \neq -\frac{1}{2} \quad \text{⚡ Contradiction!} \]

Therefore, the state cannot be factored and is entangled. \(\square\)

← Back to Exercise 4.1

---

C.4.2 Solution 4.2: Measurement Outcomes

For the 3-qubit chain cluster state, we first derive its explicit form.

Cluster state preparation:

Starting with \(|+\rangle^{\otimes 3}\) and applying \(CZ_{12}\) then \(CZ_{23}\):

The coefficient of \(|abc\rangle\) becomes \(\frac{1}{2\sqrt{2}}(-1)^{ab + bc}\)

Computing each term:

\(\|abc\rangle\)	\(ab + bc\)	\((-1)^{ab+bc}\)
\(\|000\rangle\)	0	+1
\(\|001\rangle\)	0	+1
\(\|010\rangle\)	0	+1
\(\|011\rangle\)	1	-1
\(\|100\rangle\)	0	+1
\(\|101\rangle\)	0	+1
\(\|110\rangle\)	1	-1
\(\|111\rangle\)	2	+1

\[ |\text{Cluster}\rangle = \frac{1}{2\sqrt{2}}(|000\rangle + |001\rangle + |010\rangle - |011\rangle + |100\rangle + |101\rangle - |110\rangle + |111\rangle) \]

Grouping by qubit 1:

\[ |\text{Cluster}\rangle = \frac{1}{2\sqrt{2}}\left[|0\rangle(|00\rangle + |01\rangle + |10\rangle - |11\rangle) + |1\rangle(|00\rangle + |01\rangle - |10\rangle + |11\rangle)\right] \]

Measuring qubit 1 in X-basis, outcome 0 (i.e., \(|+\rangle\)):

Project onto \(|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\):

\[ \langle +|_1 |\text{Cluster}\rangle \propto (|00\rangle + |01\rangle + |10\rangle - |11\rangle) + (|00\rangle + |01\rangle - |10\rangle + |11\rangle) \]

\[ = 2|00\rangle + 2|01\rangle = 2(|00\rangle + |01\rangle) \]

Normalizing: \[ |\psi\rangle_{23} = \frac{1}{\sqrt{2}}(|00\rangle + |01\rangle) = |0\rangle_2 \otimes \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)_3 = |0\rangle_2 |+\rangle_3 \]

Answer: After measuring qubit 1 in X-basis with outcome 0, qubits 2-3 are in state \(|0\rangle|+\rangle\).

← Back to Exercise 4.2

---

C.4.3 Solution 4.3: Gate Teleportation

Standard teleportation:

1. Alice has state \(|\psi\rangle\) on qubit 1
2. Bell pair \(|\Phi^+\rangle\) shared on qubits 2 (Alice) and 3 (Bob)
3. Alice performs Bell measurement on qubits 1-2, getting outcome \((a, b)\)
4. Bob applies \(X^a Z^b\) to qubit 3
5. Result: \(|\psi\rangle\) appears on qubit 3

How Hadamard-basis measurement applies H:

The key insight is that a Bell measurement can be decomposed as: - Apply \(CNOT_{12}\) (qubit 1 controls qubit 2) - Apply \(H\) to qubit 1 - Measure both qubits in computational (Z) basis

If Alice instead measures qubit 1 in the Hadamard basis (while still doing the CNOT), the sequence becomes:

1. \(CNOT_{12}\)
2. Measure qubit 1 in X-basis (equivalent to: \(H\), then measure in Z-basis)
3. Measure qubit 2 in Z-basis

The change in measurement basis propagates through the teleportation protocol. Since \(H^2 = I\), measuring in the \(H\)-rotated basis effectively “inserts” an \(H\) gate into the teleported state.

Mathematical explanation:

In standard teleportation, the combined state before measurement is: \[ |\psi\rangle_1 |\Phi^+\rangle_{23} = |\psi\rangle_1 \cdot \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)_{23} \]

After CNOT and measuring qubit 1 in X-basis instead of Z-basis, the effective operation on Bob’s qubit includes an additional Hadamard:

\[ |\psi\rangle \xrightarrow{\text{teleport with H-basis}} H|\psi\rangle \text{ (up to Pauli corrections)} \]

Physical intuition: The measurement basis choice determines which “frame” we observe the quantum information in. Rotating the measurement basis by \(H\) rotates the output by \(H\).

← Back to Exercise 4.3

---

C.4.4 Solution 4.4: Pattern Design

Goal: Implement Hadamard gate \(H\) on a 3-qubit chain cluster state.

Pattern specification:

Graph: Linear chain \(1 — 2 — 3\)

Protocol:

1. Prepare 3-qubit cluster state with input encoded on qubit 1

2. Measure qubit 1 in X-basis (\(\theta_1 = 0\)):

   • Outcome: \(s_1 \in \{0, 1\}\)

3. Measure qubit 2 in X-basis (\(\theta_2 = 0\)):

   • No adaptation needed for Hadamard
   • Outcome: \(s_2 \in \{0, 1\}\)

4. Apply corrections to qubit 3: \[ X^{s_2} Z^{s_1} \]

Result: Qubit 3 contains \(H|\psi_{\text{in}}\rangle\)

Explanation:

For a 3-qubit chain with both measurements in X-basis: - The first measurement “teleports” the input through the cluster - The second measurement applies the Hadamard transformation - The byproduct operators \(X\) and \(Z\) depend on measurement outcomes

Alternative (2-qubit pattern):

Hadamard can also be implemented on just 2 qubits:

1. Prepare 2-qubit cluster \(|+\rangle|+\rangle\) with \(CZ\)
2. Encode input on qubit 1
3. Measure qubit 1 in Y-basis (\(\theta = \pi/2\)), outcome \(s\)
4. Apply \(Z^s\) to qubit 2

Result: \(H|\psi\rangle\) on qubit 2

← Back to Exercise 4.4

---

C.4.5 Solution 4.5: Resource Scaling

Given: - Circuit with depth \(d\) and width \(n\) requires approximately \(d \cdot n\) qubits in MBQC - Grover’s algorithm on \(n\) qubits with \(O(\sqrt{2^n})\) gates

Analysis:

Grover’s algorithm parameters: - Width: \(n\) qubits (the search space has \(2^n\) elements) - Total gates: \(O(\sqrt{2^n}) = O(2^{n/2})\)

To estimate depth, we need to consider parallelization: - Each Grover iteration applies an oracle and a diffusion operator - Number of iterations: \(O(\sqrt{2^n})\) - Gates per iteration: \(O(n)\) (oracle and diffusion each use \(O(n)\) gates) - But wait, the problem states total gates is \(O(\sqrt{2^n})\), which suggests: - Either very few iterations, or - The oracle is very simple (constant-depth)

Case 1: If depth \(\approx\) total gates (sequential)

Cluster size \(\approx n \cdot O(2^{n/2}) = O(n \cdot 2^{n/2})\)

Case 2: If maximally parallelized

With \(n\) qubits and \(O(2^{n/2})\) gates, minimum depth is: \[ d \geq \frac{O(2^{n/2})}{n} \]

Cluster size \(\approx n \cdot \frac{2^{n/2}}{n} = O(2^{n/2}) = O(\sqrt{2^n})\)

Practical estimate:

For typical Grover implementations: - \(O(\sqrt{2^n})\) iterations - Each iteration has \(O(\log n)\) to \(O(n)\) depth

Answer: The cluster state size is approximately: \[ \boxed{O(n \cdot 2^{n/2})} \text{ to } \boxed{O(n^2 \cdot 2^{n/2})} \]

depending on the oracle complexity. For a simple oracle, the lower bound \(O(2^{n/2})\) qubits may suffice.

← Back to Exercise 4.5

---

C.4.6 Solution 4.6: Advantage Analysis

Three scenarios where MBQC has advantages:

1. Photonic quantum computing
   • Photons are easy to entangle (beam splitters, parametric down-conversion)
   • Direct photon-photon gates are extremely difficult
   • MBQC only requires single-photon measurements, which are routine
   • Companies like PsiQuantum and Xanadu use MBQC for this reason
2. Fault-tolerant quantum computing with surface codes
   • Surface codes are naturally implemented as MBQC on a 2D cluster
   • Syndrome extraction maps to measurements on the cluster
   • Topological protection emerges from the cluster state structure
   • This is the leading approach for large-scale fault-tolerant QC
3. Blind quantum computing
   • Client can delegate computation to a server without revealing the algorithm
   • Client only needs to prepare single qubits and specify measurement angles
   • Server prepares cluster state and measures, but learns nothing about the computation
   • MBQC naturally separates “resource preparation” from “computation specification”

Three scenarios where the circuit model is preferable:

1. Superconducting and trapped-ion hardware
   • These platforms have excellent two-qubit gates (99%+ fidelity)
   • Preparing large cluster states requires many gates anyway
   • Circuit model avoids the qubit overhead of MBQC (~5x more qubits)
   • Most current quantum computers (IBM, Google, IonQ) use circuit model
2. Near-term (NISQ) algorithms
   • Variational algorithms (VQE, QAOA) need parameter updates
   • Circuit model allows direct gate parameter optimization
   • MBQC would require recomputing measurement patterns each iteration
   • Classical-quantum hybrid loops are simpler in circuit model
3. Algorithm development and simulation
   • Circuit model has mature software ecosystem (Qiskit, Cirq, etc.)
   • Quantum algorithms are typically designed in gate language
   • Classical simulation of circuits is well-understood
   • Educational resources predominantly use circuit model

← Back to Exercise 4.6

---

C.5 Chapter 5: Cluster States

C.5.1 Solution 5.1: Stabilizer Verification

Verify that \(K_2 = Z_1 X_2\) stabilizes \(|G\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle)\).

Step 1: Apply \(X_2\) first

\(X_2\) flips the second qubit: - \(X_2|00\rangle = |01\rangle\) - \(X_2|01\rangle = |00\rangle\) - \(X_2|10\rangle = |11\rangle\) - \(X_2|11\rangle = |10\rangle\)

\[ X_2|G\rangle = \frac{1}{2}(|01\rangle + |00\rangle + |11\rangle - |10\rangle) \]

Step 2: Apply \(Z_1\)

\(Z_1\) applies phase \(-1\) when qubit 1 is \(|1\rangle\): - \(Z_1|00\rangle = |00\rangle\) - \(Z_1|01\rangle = |01\rangle\) - \(Z_1|10\rangle = -|10\rangle\) - \(Z_1|11\rangle = -|11\rangle\)

\[ Z_1 X_2|G\rangle = \frac{1}{2}(|01\rangle + |00\rangle - |11\rangle + |10\rangle) \]

Step 3: Reorder terms

\[ K_2|G\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle) = |G\rangle \quad \checkmark \]

← Back to Exercise 5.1

---

C.5.2 Solution 5.2: 4-Qubit Chain Stabilizers

For the 4-qubit linear cluster state \(1 — 2 — 3 — 4\):

Neighbors: - \(N(1) = \{2\}\) - \(N(2) = \{1, 3\}\) - \(N(3) = \{2, 4\}\) - \(N(4) = \{3\}\)

Stabilizer generators using the formula \(K_i = X_i \prod_{j \in N(i)} Z_j\):

\[ \begin{align*} K_1 &= X_1 Z_2 \\ K_2 &= Z_1 X_2 Z_3 \\ K_3 &= Z_2 X_3 Z_4 \\ K_4 &= Z_3 X_4 \end{align*} \]

Verification: These four operators: - Are all Hermitian (equal to their conjugate transpose) - Square to identity: \(K_i^2 = I\) - Mutually commute: \(K_i K_j = K_j K_i\) for all \(i, j\) - Uniquely determine the 4-qubit cluster state

← Back to Exercise 5.2

---

C.5.3 Solution 5.3: Stabilizer Commutation

Prove that \(K_1 = X_1 Z_2\) and \(K_2 = Z_1 X_2 Z_3\) commute.

Method: Count anticommuting pairs

Two Pauli operators commute if they share an even number of positions where they anticommute.

Writing out the operators on each qubit:

Qubit	\(K_1\)	\(K_2\)	Commute?
1	\(X\)	\(Z\)	No (anticommute)
2	\(Z\)	\(X\)	No (anticommute)
3	\(I\)	\(Z\)	Yes (commute)

Number of anticommuting positions: 2 (even)

Therefore: \(K_1\) and \(K_2\) commute: \(K_1 K_2 = K_2 K_1\) \(\checkmark\)

Alternative verification via direct calculation:

\[ K_1 K_2 = (X_1 Z_2)(Z_1 X_2 Z_3) = (X_1 Z_1)(Z_2 X_2)(Z_3) \]

Using \(XZ = -ZX\) (anticommutation): - \(X_1 Z_1 = iY_1\) - \(Z_2 X_2 = -iY_2\)

\[ K_1 K_2 = (iY_1)(-iY_2)(Z_3) = Y_1 Y_2 Z_3 \]

\[ K_2 K_1 = (Z_1 X_2 Z_3)(X_1 Z_2) = (Z_1 X_1)(X_2 Z_2)(Z_3) \]

• \(Z_1 X_1 = -iY_1\)
• \(X_2 Z_2 = iY_2\)

\[ K_2 K_1 = (-iY_1)(iY_2)(Z_3) = Y_1 Y_2 Z_3 \]

Result: \(K_1 K_2 = K_2 K_1 = Y_1 Y_2 Z_3\) \(\checkmark\)

← Back to Exercise 5.3

---

C.5.4 Solution 5.4: Local Complementation

Starting with path graph \(1 — 2 — 3 — 4\), apply Hadamard to qubit 3.

Step 1: Identify neighbors of qubit 3

\[ N(3) = \{2, 4\} \]

Step 2: Find induced subgraph on \(N(3)\)

The induced subgraph on vertices \(\{2, 4\}\) contains only those two vertices. In the original graph, there is no edge between 2 and 4.

Step 3: Complement the induced subgraph

Complement rule: toggle each edge (add if absent, remove if present).

Since \((2, 4)\) is absent → add edge \((2, 4)\)

Step 4: Resulting graph

1 — 2 — 3 — 4
    |       |
    +———————+

Or equivalently:

1 — 2 ——— 3 — 4
     \   /
      \ /
       ×

The new graph has edges: \((1,2), (2,3), (3,4), (2,4)\)

State transformation: \(H_3|G\rangle = |G'\rangle\) where \(G'\) is the new graph.

← Back to Exercise 5.4

---

C.5.5 Solution 5.5: Measurement Update

For 3-qubit chain \(1 — 2 — 3\) with stabilizers: \[ K_1 = X_1 Z_2, \quad K_2 = Z_1 X_2 Z_3, \quad K_3 = Z_2 X_3 \]

Measure qubit 1 in X-basis with outcome 0.

Step 1: Understand the measurement

X-basis measurement with outcome 0 means qubit 1 is projected to \(|+\rangle\).

This implies \(X_1 = +1\) (eigenvalue of \(|+\rangle\)).

Step 2: Update stabilizers

From \(K_1 = X_1 Z_2\) with \(X_1 \to +1\): - New stabilizer: \(Z_2\)

From \(K_3 = Z_2 X_3\) (doesn’t involve qubit 1): - Remains: \(Z_2 X_3\)

Step 3: Handle \(K_2 = Z_1 X_2 Z_3\)

Since qubit 1 is measured in X-basis, \(Z_1\) becomes indeterminate. We multiply \(K_2\) by \(K_1\) to eliminate qubit 1:

\[ K_2 \cdot K_1 = (Z_1 X_2 Z_3)(X_1 Z_2) = Z_1 X_1 \cdot X_2 Z_2 \cdot Z_3 \]

After measuring with \(X_1 = +1\), the qubit-1 part contributes only a phase. The remaining stabilizer on qubits 2-3 is:

\[ X_2 Z_3 \quad \text{(up to sign depending on outcome)} \]

Final stabilizers for qubits 2-3:

\[ K'_2 = X_2 Z_3, \quad K'_3 = Z_2 X_3 \]

These are exactly the stabilizers of a 2-qubit cluster state \(2 — 3\), which makes sense: measuring out qubit 1 in X-basis leaves the remaining qubits in a 2-qubit cluster state.

← Back to Exercise 5.5

---

C.5.6 Solution 5.6: Graph State Entanglement

For a star graph with central qubit 0 connected to \(n\) outer qubits \(\{1, 2, \ldots, n\}\).

Step 1: Derive the star graph state

\[ |\text{star}\rangle = CZ_{01} CZ_{02} \cdots CZ_{0n} |+\rangle^{\otimes (n+1)} \]

The central qubit starts in \(|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\).

When the center is \(|0\rangle\): all CZ gates act as identity on outer qubits → outer qubits stay \(|+\rangle^{\otimes n}\)

When the center is \(|1\rangle\): each CZ applies \(Z\) to the corresponding outer qubit → \(|+\rangle \xrightarrow{Z} |-\rangle\)

Result: \[ |\text{star}\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle |+\rangle^{\otimes n} + |1\rangle |-\rangle^{\otimes n}\right) \]

Step 2: Find Schmidt decomposition

This is already in Schmidt form with partition (central qubit) | (outer qubits):

\[ |\text{star}\rangle = \frac{1}{\sqrt{2}}|0\rangle|\phi_0\rangle + \frac{1}{\sqrt{2}}|1\rangle|\phi_1\rangle \]

where \(|\phi_0\rangle = |+\rangle^{\otimes n}\) and \(|\phi_1\rangle = |-\rangle^{\otimes n}\) are orthogonal.

Schmidt coefficients: \(\lambda_1 = \lambda_2 = \frac{1}{\sqrt{2}}\)

Step 3: Calculate entanglement entropy

\[ S = -\sum_i \lambda_i^2 \log_2 \lambda_i^2 = -\frac{1}{2}\log_2\frac{1}{2} - \frac{1}{2}\log_2\frac{1}{2} = 1 \text{ bit} \]

Answer: The entanglement entropy between the central qubit and all outer qubits is 1 bit, regardless of \(n\).

Physical interpretation: The star graph state is essentially a GHZ-like state where the central qubit is maximally entangled with the collective state of all outer qubits.

← Back to Exercise 5.6

---

C.5.7 Solution 5.7: Resource Comparison

For a 2D cluster state simulating a circuit of depth \(d\) on \(n\) qubits, the cluster size is approximately \(O(d \times n)\).

(a) Grover’s algorithm on 10 qubits

Parameters: - Search space: \(2^{10} = 1024\) elements - Number of Grover iterations: \(O(\sqrt{2^{10}}) = O(32)\) - Gates per iteration: \(O(n) = O(10)\) (oracle + diffusion) - Total depth: \(d \approx 32 \times 10 = 320\) - Width: \(n = 10\) qubits

2D cluster size: \[ \text{Cluster qubits} \approx d \times n = 320 \times 10 = 3{,}200 \text{ qubits} \]

(b) Quantum Fourier Transform on 20 qubits

Parameters: - Width: \(n = 20\) qubits - Sequential depth: \(O(n^2) = O(400)\) (naive implementation) - Parallelized depth: \(O(n) = O(20)\) (with sufficient ancillas)

2D cluster size (sequential): \[ \text{Cluster qubits} \approx 400 \times 20 = 8{,}000 \text{ qubits} \]

2D cluster size (parallelized): \[ \text{Cluster qubits} \approx 20 \times 20 = 400 \text{ qubits} \]

Summary:

Algorithm	Qubits	Depth	Cluster Size
Grover (10 qubits)	10	~320	~3,200
QFT (20 qubits, sequential)	20	~400	~8,000
QFT (20 qubits, parallel)	20	~20	~400

Note: These are rough estimates. Actual implementations may have constant-factor overhead for error correction, gate decomposition, and MBQC-specific requirements.

← Back to Exercise 5.7

---

C.6 Chapter 6: Measurement Patterns

C.6.1 Solution 6.1: Hadamard Compilation

Complete measurement pattern for the Hadamard gate:

Cluster preparation:

N_1        # Create qubit 1 in state |+⟩ (this will hold input)
N_2        # Create qubit 2 in state |+⟩ (this will be output)
E_12       # Entangle qubits 1 and 2 with CZ

Measurement:

M_1^0 → s  # Measure qubit 1 in X-basis (θ = 0), outcome s ∈ {0,1}

Correction:

Z_2^s      # Apply Z to qubit 2 if s = 1

Summary:

Step	Command	Description
1	\(N_1, N_2\)	Create two qubits in \(\|+\rangle\)
2	\(E_{12}\)	Apply \(CZ\) to create cluster
3	\(M_1^0 \to s\)	Measure qubit 1 in X-basis
4	\(Z_2^s\)	Apply \(Z\) correction if \(s=1\)

Result: Qubit 2 contains \(H|\psi\rangle\) where \(|\psi\rangle\) was encoded in qubit 1.

Verification: This works because measuring in the X-basis (\(|+\rangle, |-\rangle\)) on a cluster state effectively applies a Hadamard transformation to the information as it “flows” through the cluster.

← Back to Exercise 6.1

---

C.6.2 Solution 6.2: Rotation Angle

Question: For rotation \(R_Z(\theta)\) implemented by measuring in basis \(|\pm_\alpha\rangle\), what is the relationship between \(\theta\) and \(\alpha\)?

Answer: The measurement angle equals the rotation angle:

\[ \boxed{\alpha = \theta} \]

Explanation:

The measurement basis states are: \[ |\pm_\alpha\rangle = \frac{1}{\sqrt{2}}(|0\rangle \pm e^{i\alpha}|1\rangle) \]

When measuring in this basis on a cluster state, the gate applied is: \[ R_Z(\alpha) = e^{-i\alpha Z/2} = \begin{pmatrix} e^{-i\alpha/2} & 0 \\ 0 & e^{i\alpha/2} \end{pmatrix} \]

Key insight: The phase factor \(e^{i\alpha}\) in the measurement basis directly translates to the rotation angle in the implemented gate.

Special cases: - \(\alpha = 0\): X-basis measurement → \(R_Z(0) = I\) (identity, but with Hadamard effect from cluster) - \(\alpha = \pi/2\): Y-basis measurement → \(R_Z(\pi/2) = S\) (phase gate) - \(\alpha = \pi\): \(-X\)-basis measurement → \(R_Z(\pi) = Z\)

← Back to Exercise 6.2

---

C.6.3 Solution 6.3: CNOT Pattern

Circuit:

|ψ⟩ ——●——— (output)
      |
|0⟩ ——⊕—[H]— (output)

This is CNOT followed by Hadamard on the target qubit.

Cluster graph:

1 ——— 2 ——— 3        (control path)
      |
      4 ——— 5        (target path with H)

Where: - Qubit 1: Control input (encoded with \(|\psi\rangle\)) - Qubit 4: Target input (initialized to \(|+\rangle\), represents \(|0\rangle\) in computational basis) - Qubit 2: CNOT interaction ancilla - Qubit 3: Control output - Qubit 5: Target output (after CNOT and H)

Measurement pattern:

Qubit	Measurement Basis	Outcome
1	X-basis (\(\theta = 0\))	\(s_1\)
2	X-basis (\(\theta = 0\))	\(s_2\)
4	X-basis (\(\theta = 0\))	\(s_4\)

Corrections: - On qubit 3 (control output): \(Z^{s_1}\) - On qubit 5 (target output): \(X^{s_2} Z^{s_4}\)

Pattern commands:

N_1  N_2  N_3  N_4  N_5    # Create 5 qubits
E_12  E_23  E_24  E_45     # Create cluster structure
M_1^0 → s_1                # Measure control input
M_2^0 → s_2                # Measure CNOT ancilla
M_4^0 → s_4                # Measure target input (also implements H)
Z_3^{s_1}                  # Correct control output
X_5^{s_2} Z_5^{s_4}        # Correct target output

Note: The H gate on the target is “absorbed” into the measurement of qubit 4 - measuring in X-basis naturally applies H to the information flow.

← Back to Exercise 6.3

---

C.6.4 Solution 6.4: Adaptive Measurement

Circuit: \(H\) followed by \(R_Z(\theta)\)

Question: If the first measurement (for \(H\)) gives outcome \(s_1 = 1\), should the second measurement angle be \(\theta\) or \(\theta + \pi\)?

Answer: The second measurement angle should be \(\theta + \pi\).

\[ \boxed{\theta' = \theta + \pi \cdot s_1 = \theta + \pi} \]

Justification:

When the first measurement gives outcome \(s_1 = 1\), there is a byproduct operator that propagates through the computation. Specifically:

1. After first measurement (\(s_1 = 1\)): The state acquires an \(X\) byproduct operator.

2. Commutation relation: When \(X\) commutes past \(R_Z(\theta)\): \[ X \cdot R_Z(\theta) = R_Z(-\theta) \cdot X \] This is because \(X Z X = -Z\), so the rotation direction flips.

3. Compensation: To get the correct \(R_Z(\theta)\) instead of \(R_Z(-\theta)\), we need to change our measurement angle. Since: \[ R_Z(\theta + \pi) = -R_Z(\theta) \cdot Z \] and the sign and \(Z\) can be absorbed into later corrections, measuring at \(\theta + \pi\) effectively compensates for the sign flip.

4. Adaptation rule: \[ \theta_{\text{actual}} = \theta + \pi \cdot s_1 \]

• If \(s_1 = 0\): measure at \(\theta\) (no adaptation needed)
• If \(s_1 = 1\): measure at \(\theta + \pi\) (flip the angle)

This is the essence of feed-forward in MBQC: measurement outcomes from earlier qubits determine the measurement bases for later qubits.

← Back to Exercise 6.4

---

C.6.5 Solution 6.5: Pattern Optimization

Problem: A depth-10 circuit on 5 qubits naively compiles to a \(5 \times 11 = 55\) qubit cluster. Describe two techniques to reduce this.

Technique 1: Gate Cancellation

Simplify the circuit before compiling to MBQC:

• Adjacent inverse gates: \(H \cdot H = I\), \(CNOT \cdot CNOT = I\), \(S \cdot S^\dagger = I\)
• Commutation: Reorder gates that commute to enable more cancellations
• Gate synthesis: Replace sequences with equivalent shorter sequences

Example: If the circuit contains \(H \cdot H\) on some qubit, removing these saves 2 layers → cluster reduced by \(5 \times 2 = 10\) qubits.

Technique 2: Using Native CZ Gates

Replace \(CNOT\) with \(CZ\) where possible:

• \(CNOT = (I \otimes H) \cdot CZ \cdot (I \otimes H)\)
• But if there are adjacent \(H\) gates, they may cancel
• \(CZ\) is native to cluster states (no ancilla needed for the entangling operation itself)

Savings: Each \(CNOT\) replaced by \(CZ\) can save 1-2 ancilla qubits.

Additional techniques:

3. Parallel measurement: Gates on different qubits can share cluster layers
4. Signal shifting: Track Pauli corrections classically rather than implementing physically
5. Lazy correction: Defer corrections to the end, absorbing them into the final measurement interpretation

Estimated savings: With aggressive optimization, a 55-qubit naive cluster can often be reduced to 25-35 qubits for typical circuits.

← Back to Exercise 6.5

---

C.6.6 Solution 6.6: Deterministic Gates

Claim: The Pauli \(X\) gate can be implemented deterministically in MBQC.

Proof:

In MBQC, Pauli gates (\(X\), \(Y\), \(Z\)) are special because they are byproduct operators - they arise naturally from measurement outcomes and are tracked classically rather than implemented physically.

Method 1: Classical tracking

The \(X\) gate doesn’t require any measurement to implement. Instead:

1. When compiling, note that \(X\) should be applied
2. Track this as a “pending \(X\) correction” on that qubit
3. At the end of computation, either:
   • Apply the physical \(X\) gate, or
   • Flip the interpretation of the final measurement outcome

This is deterministic because no probabilistic measurement is involved.

Method 2: Measurement-based implementation

If we insist on using measurements:

1. Prepare: 2-qubit cluster with input \(|\psi\rangle\) on qubit 1
2. Measure: Qubit 1 in the \(Z\)-basis
3. Result:
   • Outcome 0: Qubit 2 is in state \(H|\psi\rangle \cdot |+\rangle\) projection
   • Outcome 1: Qubit 2 is in state \(H X|\psi\rangle \cdot |-\rangle\) projection

The key insight: although the outcome is random, the correction needed is always the same up to the known measurement result. We can predict exactly what correction is needed.

Why this is “deterministic”:

The term “deterministic” here means: - The correction formula is fixed (not dependent on the outcome in a complicated way) - The final state after correction is always \(X|\psi\rangle\) - There’s no adaptation or feed-forward uncertainty

\[ \text{Final state} = X|\psi\rangle \quad \text{(always, regardless of measurement outcome)} \]

← Back to Exercise 6.6

---

C.6.7 Solution 6.7: Circuit to Pattern

Circuit:

|ψ⟩ —[H]—●—[S]— (output 1)
         |
|0⟩ ————⊕———— (output 2)

where \(S = R_Z(\pi/2)\) is the phase gate.

Step 1: Identify gates - \(H\) on qubit 1 - \(CNOT\) with qubit 1 as control, qubit 2 as target - \(S = R_Z(\pi/2)\) on qubit 1

Step 2: Cluster graph

1 — 2 — 3 — 4     (qubit 1: input → H → CNOT_ctrl → S → output)
        |
5 ————— 6         (qubit 2: input → CNOT_tgt → output)

Vertex roles: - 1: Input qubit 1 (holds \(|\psi\rangle\)) - 2: Ancilla for \(H\) gate - 3: CNOT interaction vertex (connects control and target paths) - 4: Output qubit 1 (also implements \(S\) via measurement of vertex 3) - 5: Input qubit 2 (initialized in cluster as \(|+\rangle\)) - 6: Output qubit 2

Step 3: Measurement pattern

Qubit	Role	Measurement Basis	Outcome
1	H gate	X-basis (\(\theta = 0\))	\(s_1\)
2	Flow	X-basis (\(\theta = 0\)), adapted	\(s_2\)
3	CNOT + S	\(\theta = \pi/4\) (for \(S\)), adapted	\(s_3\)
5	CNOT target	X-basis (\(\theta = 0\))	\(s_5\)

Adaptive angles: - \(\theta_2' = 0 + \pi \cdot s_1\) - \(\theta_3' = \pi/4 + \pi \cdot s_2\)

Step 4: Corrections

On output qubit 4: \[ X^{s_2} Z^{s_1 \oplus s_3} \]

On output qubit 6: \[ X^{s_3} Z^{s_5} \]

Complete pattern:

# Preparation
N_1  N_2  N_3  N_4  N_5  N_6      # Create 6 qubits in |+⟩
E_12  E_23  E_34  E_35  E_56      # Create cluster edges

# Measurements (in order)
M_1^0 → s_1                       # H gate
M_5^0 → s_5                       # CNOT target input
[M_2^0]^{s_1} → s_2               # Adapted by s_1
[M_3^{π/4}]^{s_2} → s_3           # S gate, adapted by s_2

# Corrections
X_4^{s_2} Z_4^{s_1 ⊕ s_3}         # Output qubit 1
X_6^{s_3} Z_6^{s_5}               # Output qubit 2

Output: Qubits 4 and 6 contain the circuit output state.

← Back to Exercise 6.7