q5-harder

Question 5 (Harder): Quantum Algorithms (State Initialization with Clifford Gates)

Source: Chapter 03, slides 3, 7-12, 28, 30-34, 38-39, 43-44

These problems go beyond the base Question 5 set: graph states built from many overlapping $CZ$ gates, longer phase-bookkeeping chains on more qubits, and circuits constrained to nearest-neighbor connectivity, forcing a genuine swap network instead of a direct controlled-NOT.

---

Problem 1: the 3-qubit triangle graph state (every pair connected by $CZ$)

Target: apply $H$ to all three qubits, then a $CZ$ between every pair $(0,1)$, $(1,2)$, $(0,2)$ — a complete graph on 3 vertices.

Circuit:

q0: |0> --H--*-----*-----
             |     |
q1: |0> --H--Z--*--|-----
                |  |
q2: |0> --H-----Z--Z-----

Step 1, why term-by-term tracing does not scale here. With three overlapping $CZ$ gates touching all $2^3=8$ basis terms, listing each term’s fate one $CZ$ at a time (as in Question 6) is slow and error-prone. Instead use the standard graph-state shortcut: after $H^{\otimes 3}$ the state is an equal-weight sum over all bit strings, and each $CZ(i,j)$ multiplies the amplitude of a term by $-1$ exactly when both bits $x_i,x_j$ are $1$ — so its net effect is just to add $x_i{x}_j$ to a running exponent.

Step 2, after $H^{\otimes 3}$.

$$\frac{1}{2\sqrt{2}}\sum _{x_1,x_2,x_3\in \{0,1\}}|x_1{x}_2{x}_3⟩.$$

Step 3, accumulate the phase exponent from all three $CZ$ gates. $CZ(0,1)$ contributes $x_1{x}_2$, $CZ(1,2)$ contributes $x_2{x}_3$, $CZ(0,2)$ contributes $x_1{x}_3$ (using 1-indexed bit labels matching the qubit order $q0,q1,q2\to x_1,x_2,x_3$):

$$|\psi ⟩=\frac{1}{2\sqrt{2}}\sum _{x_1,x_2,x_3}(-1{)}^{x_1{x}_2+x_2{x}_3+x_1{x}_3}|x_1{x}_2{x}_3⟩.$$

Step 4, evaluate the sign on each of the 8 terms.

$$\begin{array}{ccc}{x}_1{x}_2{x}_3& x_1{x}_2+x_2{x}_3+x_1{x}_3& \text{sign}\\ 000& 0& +\\ 001& 0& +\\ 010& 0& +\\ 100& 0& +\\ 011& 0+1+0=1& -\\ 101& 0+0+1=1& -\\ 110& 1+0+0=1& -\\ 111& 1+1+1=3& -\end{array}$$

Final state.

$$\frac{1}{2\sqrt{2}}\left(|000⟩+|001⟩+|010⟩+|100⟩-|011⟩-|101⟩-|110⟩-|111⟩\right).$$

Why this is harder than any base-file problem. Every one of the 8 basis terms is now populated with an independently determined sign fixed by three overlapping two-qubit gates acting on the same three wires, rather than a single controlled-NOT chain that only ever touches two terms at a time.

---

Problem 2: a 5-qubit GHZ state with a combined non-trivial global phase, $\frac{|00000⟩-i|11111⟩}{\sqrt{2}}$

Circuit:

q0: |0> --H--*--*--*--*----------
             |  |  |  |
q1: |0> -----X--|--|--|--Z-------
                |  |  |
q2: |0> --------X--|--|----------
                   |  |
q3: |0> -----------X--|----------
                      |
q4: |0> --------------X--S-------

Step 1 (start). $|00000⟩$.

Step 2 (after $H$ on q0). $\frac{1}{\sqrt{2}}\left(|00000⟩+|10000⟩\right)$.

Step 3 (after controlled-NOT from q0 to each of q1, q2, q3, q4 in turn). Every one of the four controlled-NOTs has control q0, which is still $|1⟩$ on the second term at the moment each fires, so each flips its target in turn:

$$\frac{1}{\sqrt{2}}\left(|00000⟩+|11111⟩\right),$$

the 5-qubit GHZ state.

Step 4 (after $S$ on q4). $S=\mathrm{diag}(1,i)$ multiplies the amplitude by $i$ whenever q4 is $|1⟩$; the $|11111⟩$ term has q4$=1$ and picks up $i$, while $|00000⟩$ is untouched.

$$\frac{1}{\sqrt{2}}\left(|00000⟩+i|11111⟩\right).$$

Step 5 (after $Z$ on q1). $Z$ multiplies the amplitude by $-1$ whenever q1 is $|1⟩$; the $|11111⟩$ term (carrying coefficient $i/\sqrt{2}$) has q1$=1$, so its coefficient becomes $i\cdot (-1)=-i$, while $|00000⟩$ is untouched.

$$\frac{1}{\sqrt{2}}\left(|00000⟩-i|11111⟩\right),$$

the target state.

Why this is harder. Reaching a target relative phase of $-i$ requires combining two different single-qubit Clifford phase corrections ($S$ contributing $i$, $Z$ contributing $-1$) applied on two different qubits, both of which only act on the shared $|11111⟩$ branch. Careless bookkeeping (applying them in the wrong place, or on the $|00000⟩$ branch by mistake) silently produces the wrong global phase, whereas every base-file GHZ problem only ever needed a single phase correction.

---

Problem 3: nearest-neighbor connectivity, Bell pair on non-adjacent qubits q0 and q3 via a swap network

Hardware constraint: 2-qubit gates are only physically available between adjacent wires, $(q0,q1)$, $(q1,q2)$, $(q2,q3)$. Target: $\frac{|0000⟩+|1001⟩}{\sqrt{2}}$, i.e. q0 and q3 entangled as a Bell pair, q1 and q2 left at $|0⟩$.

Circuit:

q0: |0> --H--*--------------
             |
q1: |0> -----X--x-----------
                |
q2: |0> --------x--x--------
                   |
q3: |0> --------------x-----

(the x--x columns denote swap; the second swap is between q2 and q3)

Step 1, why controlled-NOT(q0,q3) directly is not available. The problem restricts 2-qubit gates to adjacent pairs, so entanglement must first be created locally, then physically moved along the register using swap gates, exactly the technique used for connectivity-limited hardware.

Step 2 (after $H$ on q0). $\frac{1}{\sqrt{2}}\left(|0000⟩+|1000⟩\right)$.

Step 3 (after controlled-NOT, control q0, target q1). $\frac{1}{\sqrt{2}}\left(|0000⟩+|1100⟩\right)$, an ordinary adjacent Bell pair on q0,q1.

Step 4 (after swap between q1 and q2). Swap exchanges the values sitting on wires $q1,q2$ in every term: $|0000⟩$ is unaffected ($0,0\to 0,0$); $|1100⟩$ becomes $|1010⟩$ ($q1=1,q2=0\to q1=0,q2=1$).

$$\frac{1}{\sqrt{2}}\left(|0000⟩+|1010⟩\right).$$

Step 5 (after swap between q2 and q3). $|0000⟩$ unaffected; $|1010⟩$ becomes $|1001⟩$ ($q2=1,q3=0\to q2=0,q3=1$).

$$\frac{1}{\sqrt{2}}\left(|0000⟩+|1001⟩\right),$$

the target state: q0 and q3 hold the Bell correlation, q1 and q2 are back to $|0⟩$, disentangled.

Why this is harder. Every base-file problem allowed any wire to interact with any other wire directly; here the connectivity constraint forces two extra swap gates purely to relocate an entangled partner across the register, a genuinely different (and more error-prone) kind of circuit design than picking the right gate sequence on a fully-connected register.

---

Problem 4: merging two independent Bell pairs into one 4-term entangled cluster with a single connecting $CZ$

Target: starting from two ordinary Bell pairs, $(q0,q1)$ and $(q2,q3)$, apply one $CZ$ between $q1$ and $q2$ to link them.

Circuit:

q0: |0> --H--*-----------
             |
q1: |0> -----X--*--------
                |
q2: |0> --H-----Z--------
                   
q3: |0> -----------*-----
                    |
(continued)  q2 --Z--(already shown above), q3 unused by CZ, paired via its own CNOT below

To keep the diagram unambiguous, draw it as two clearly separated stages:

Stage A (build the two Bell pairs):
q0: |0> --H--*--------
             |
q1: |0> -----X--------
q2: |0> --H--------*--
                    |
q3: |0> ------------X--

Stage B (connect them):
q1: ----*--
        |
q2: ----Z--

Step 1 (after Stage A). Each pair independently becomes a Bell state, by Problem 1 of the base Question 5 file:

$$\frac{1}{2}{\left(|00⟩+|11⟩\right)}_{01}\otimes {\left(|00⟩+|11⟩\right)}_{23}=\frac{1}{2}(|0000⟩+|0011⟩+|1100⟩+|1111⟩).$$

Step 2, apply $CZ$ between q1 and q2 to every one of the 4 terms. $CZ$ multiplies a term’s amplitude by $-1$ exactly when both q1 and q2 are $1$ in that term; read off $(x_1,x_2)$ for each term:

$$\begin{array}{ccc}\text{term}& (x_1,x_2)& \text{sign}\\ |0000⟩& (0,0)& +\\ |0011⟩& (0,1)& +\\ |1100⟩& (1,0)& +\\ |1111⟩& (1,1)& -\end{array}$$

Final state.

$$\frac{1}{2}\left(|0000⟩+|0011⟩+|1100⟩-|1111⟩\right).$$

Why this is harder. This is a genuine 4-term entangled state on 4 qubits (not reducible to a tensor product of two 2-term Bell pairs any more, since the connecting $CZ$ correlates all four qubits together), yet it is built by composing two small, independently-verifiable circuits (Stage A, checked against Problem 5 of the base file) with one extra linking gate — the harder skill is tracking how a single additional gate changes all four amplitudes of an already-entangled multi-qubit state at once, rather than building the state gate-by-gate from scratch.