= Solution
Use <GHZ preparation with Hadamard and controlled-Z gates> for $n\geq2$. Apply a <Hadamard gate> to the first <qubit>, then a <controlled-NOT gate> from that <qubit> to each of the other $n-1$ <qubits>. Every controlled-NOT can be written in the allowed gate set as
$$
\operatorname{CNOT}_{1\to j}=H_j\,CZ_{1j}\,H_j.
$$
Indeed conjugating the target $Z$ by $H$ makes the controlled phase into a controlled $X$. The rightmost gate acts first. Consequently the <Clifford circuit> uses $1+3(n-1)$ allowed gates and gives
$$
\boxed{|\psi\rangle=\frac{|0\rangle^{\otimes n}+|1\rangle^{\otimes n}}{\sqrt2}.}
$$
For every chosen <qubit> $j$, tracing out the other <qubits> yields $\rho_j=\tfrac12(|0\rangle\langle0|+|1\rangle\langle1|)=I/2$. Equivalently, across that <qubit> versus the rest, the displayed state is a <Schmidt decomposition> with two nonzero coefficients $1/\sqrt2$. It is therefore <entangled> across every such bipartition.
\b[<Entanglement> does not prevent the polynomial single-output simulation from part (iii).] The simulation follows the measured observable rather than claiming that the intermediate states remain <product states>. When $n=1$, there is no remaining subsystem and the requested <entanglement> is impossible; the construction and claim require $n\geq2$.
Back to article page
