Assignment 1: Foundations of Quantum Computation

(a) Colliding Trajectories and Landauer’s Principle:

Evaluating \(\operatorname{Maj}(x_1, x_2, x_3)\) on all \(2^3 = 8\) input configurations:

• Configurations mapping to \(0\): \((0,0,0)\), \((0,0,1)\), \((0,1,0)\), \((1,0,0)\) (\(4\) configurations).
• Configurations mapping to \(1\): \((0,1,1)\), \((1,0,1)\), \((1,1,0)\), \((1,1,1)\) (\(4\) configurations).

The operation maps an 8-element configuration space to a 2-element space. Because 4 distinct input configurations collapse into each output configuration, the mapping is many-to-one (non-injective). Given only the output bit, the predecessor configuration cannot be uniquely reconstructed: 2 bits of configuration entropy are destroyed. By Landauer's principle, any physical process that merges logical trajectories reduces the information entropy of the computational degrees of freedom, transferring at least \(\Delta S = k_B \ln 4 = 2 k_B \ln 2\) of entropy to the thermal environment as heat dissipation \(Q \ge 2 k_B T \ln 2\).

(b) Polynomial over the Binary Field:

Over \(\mathbb{F}_2\), the disjunction \(a \lor b = a \oplus b \oplus ab\). For the majority function, no two products \(x_1 x_2\), \(x_2 x_3\), and \(x_3 x_1\) can simultaneously equal \(1\) unless at least two variables are \(1\). If exactly two inputs are \(1\), exactly one product is \(1\) and the others are \(0\), giving sum \(1\). If all three inputs are \(1\), all three products are \(1\), giving \(1 \oplus 1 \oplus 1 = 1\). If fewer than two inputs are \(1\), all products are \(0\), giving \(0\). Thus, over \(\mathbb{F}_2\):

\[\operatorname{Maj}(x_1, x_2, x_3) = x_1 x_2 \oplus x_2 x_3 \oplus x_3 x_1.\]

Verification across all eight configurations:
- On \(000\): \(0 \oplus 0 \oplus 0 = 0\).
- On \(001, 010, 100\): exactly one variable is \(1\), all pairwise products are \(0\), yielding \(0\).
- On \(011, 101, 110\): exactly one pair is \(1\), yielding \(1\).
- On \(111\): all three pairs are \(1\), yielding \(1 \oplus 1 \oplus 1 = 1\).
The algebraic normal form matches the truth table identically.

(c) Reversible Embedding and Toffoli Cascade:

The mapping \(\tau_{\text{rev}}: (x_1, x_2, x_3, y) \mapsto (x_1, x_2, x_3, y \oplus \operatorname{Maj}(x))\) is an involution: applying \(\tau_{\text{rev}}\) twice yields \((x_1, x_2, x_3, (y \oplus \operatorname{Maj}(x)) \oplus \operatorname{Maj}(x)) = (x_1, x_2, x_3, y)\), the identity mapping. Because \(\tau_{\text{rev}}^2 = I\), it is a bijection (a permutation of order 2) on the 16 configurations, ensuring no trajectories collide.

An elementary Toffoli gate \(\text{CCNOT}(a, b; c)\) maps \((a, b, c) \mapsto (a, b, c \oplus ab)\). Since \(\operatorname{Maj}(x) = x_1 x_2 \oplus x_2 x_3 \oplus x_3 x_1\), we apply three successive Toffoli gates all targeting the output wire \(y\):

1. \(\text{CCNOT}(x_1, x_2; y)\): updates target to \(y \oplus x_1 x_2\).
2. \(\text{CCNOT}(x_2, x_3; y)\): updates target to \(y \oplus x_1 x_2 \oplus x_2 x_3\).
3. \(\text{CCNOT}(x_3, x_1; y)\): updates target to \(y \oplus x_1 x_2 \oplus x_2 x_3 \oplus x_3 x_1 = y \oplus \operatorname{Maj}(x)\).

The control configurations \(x_1, x_2, x_3\) are strictly preserved, preventing any trajectory collision.

(d) Uncomputing Workspace Footprints:

Resetting the workspace wire \(w\) by an irreversible reset operation (\(w \mapsto 0\)) merges the trajectories \(w = 0\) and \(w = 1\), dissipating Landauer heat. In quantum computing, retaining garbage in \(w\) is even more consequential: the entangled workspace configuration \(\sum_x \ket{x}\ket{g(x)}_w\ket{f(x)}_y\) prevents destructive interference between different \(x\) computational paths.

Bennett’s compute–copy–uncompute protocol resolves this in three reversible stages:

1. Compute: Apply reversible circuit \(U\): \((x, 0_w, 0_t) \xrightarrow{U} (x, g(x)_w, f(x)_t)\), where \(w\) holds workspace garbage and \(t\) holds the answer.
2. Copy: Apply a CNOT gate from target wire \(t\) to a fresh output wire \(y\) initialized to \(0\): \((x, g(x)_w, f(x)_t, 0_y) \xrightarrow{\text{CNOT}} (x, g(x)_w, f(x)_t, f(x)_y)\).
3. Uncompute: Apply the inverse circuit \(U^{-1}\) to the input, workspace, and intermediate wires: \((x, g(x)_w, f(x)_t, f(x)_y) \xrightarrow{U^{-1}} (x, 0_w, 0_t, f(x)_y)\).

Because \(U^{-1}U = I\), the workspace configuration returns deterministically to \(0_w\) and intermediate wire to \(0_t\) without any information erasure or heat dissipation.

(a) Invariants and Variants of Euclid’s Algorithm:

(i) Invariance of \(\gcd(a, b)\): Suppose \(a > b\). Let \(g\) divide both \(a\) and \(b\) (\(g \mid a\) and \(g \mid b\)). Then \(a = k_1 g\) and \(b = k_2 g\), so \(a - b = (k_1 - k_2)g\), meaning \(g \mid (a - b)\). Thus any common divisor of \((a, b)\) also divides \((a - b, b)\). Conversely, let \(d\) divide both \((a - b)\) and \(b\). Then \(a = (a - b) + b\) is a multiple of \(d\), so \(d\) divides both \(a\) and \(b\). Because the set of common divisors of \((a, b)\) is identical to the set of common divisors of \((a - b, b)\), their greatest common divisors must be identical: \(\gcd(a - b, b) = \gcd(a, b)\). By symmetry, when \(b > a\), \(\gcd(a, b - a) = \gcd(a, b)\). Thus \(I(\tau(a, b)) = I(a, b)\) across every step.

(ii) Strict Variant: Define \(V(a, b) = a + b\). Since \(a, b \in \mathbb{N}^+\), \(V \ge 2\). When \(a > b\), \(\tau(a, b) = (a - b, b)\), giving \(V(\tau(a, b)) = (a - b) + b = a\). Since \(b \ge 1\), \(a \le a + b - 1 = V(a, b) - 1\). Symmetrically, if \(b > a\), \(V(\tau(a, b)) = b \le V(a, b) - 1\). Thus \(V\) strictly decreases by at least \(1\) on each step. Halting occurs when \(a = b \ge 1\), where \(V \ge 2\). Therefore, starting from \((a_0, b_0)\), the algorithm must halt within at most \(a_0 + b_0 - 2\) steps.

(b) Trajectory Topology and Reversible Cycles:

(i) Consider a deterministic sequence of \(S + 1\) configurations: \(c_0, c_1, \dots, c_S\). Since there are only \(S\) distinct configurations in \(\mathcal{C}\), by the pigeonhole principle there must exist indices \(0 \le j < k \le S\) such that \(c_j = c_k\). Thus the trajectory revisits an earlier configuration and enters a periodic loop.

(ii) In a reversible system, \(\tau\) is a bijection: every configuration has a unique successor and a unique predecessor. Suppose for contradiction that the trajectory forms a "lasso": a transient tail \(c_0, c_1, \dots, c_{j-1}\) that enters a cycle at \(c_j\) from outside, where \(c_k = c_j\) for some \(k > j > 0\). Then configuration \(c_j\) has two distinct predecessors: \(c_{j-1}\) (from the transient tail) and \(c_{k-1}\) (from inside the cycle). Since \(c_{j-1} \notin \{c_j, \dots, c_{k-1}\}\), \(c_{j-1} \ne c_{k-1}\). But this means \(\tau(c_{j-1}) = c_j = \tau(c_{k-1})\), which violates reversibility (injectivity). Therefore, no transient tail can exist: every repeating trajectory must return directly to \(c_0\) (\(j = 0\)). The entire configuration space of any finite reversible system partitions into disjoint, closed periodic cycles.

(c) Undecidability of Halting:

(i) Define machine \(D\) taking description \(\langle M \rangle\):
1. Run decider \(H\) on input \(\langle M, \langle M \rangle \rangle\).
2. If \(H\) accepts (meaning \(M\) halts on \(\langle M \rangle\)), \(D\) intentionally enters an infinite loop.
3. If \(H\) rejects (meaning \(M\) loops forever on \(\langle M \rangle\)), \(D\) halts immediately.

(ii) Now feed \(\langle D \rangle\) into \(D\):
- If \(D\) halts on \(\langle D \rangle\), then by construction \(H(\langle D, \langle D \rangle \rangle)\) must output \(1\), which triggers \(D\) to enter an infinite loop (a contradiction).
- If \(D\) loops forever on \(\langle D \rangle\), then \(H(\langle D, \langle D \rangle \rangle)\) outputs \(0\), which triggers \(D\) to halt immediately (a contradiction).
Since both possibilities lead to logical contradiction, the assumption that there exists a total deterministic decider for halting must be false.

(a) Stochastic Evolution and \(\ell_1\) Conservation:

(i) For \(\mathbf{p}' = M\mathbf{p}\) to be a valid distribution for all \(\mathbf{p}\):
- Each entry must be non-negative: \(M_{ij} \ge 0\) for all \(i, j\).
- The columns must sum to 1: \(\sum_{i=1}^N M_{ij} = 1\) for every column \(j\).

(ii) For any non-negative probability vector \(\mathbf{p}\) (where \(p_j \ge 0\)):

\[\|\mathbf{p}'\|_1 = \sum_{i=1}^N p'_i = \sum_{i=1}^N \sum_{j=1}^N M_{ij} p_j = \sum_{j=1}^N p_j \left( \sum_{i=1}^N M_{ij} \right) = \sum_{j=1}^N p_j (1) = \sum_{j=1}^N p_j = \|\mathbf{p}\|_1 = 1.\]

Thus stochastic matrices are isometries with respect to the \(\ell_1\) norm on the probability simplex.

(b) Impossibility of Destructive Cancellation in Stochastic Networks:

In a stochastic network, the total transition probability from \(j\) to \(i\) is a sum of products of non-negative real numbers: \(P(i \leftarrow j) = \sum_k M_{ik} M_{kj}\). Since every product \(M_{ik} M_{kj} \ge 0\), every term in the sum is non-negative. For any specific path through configuration \(k^*\):

\[P(i \leftarrow j) = M_{ik^*} M_{k^*j} + \sum_{k \ne k^*} M_{ik} M_{kj} \ge M_{ik^*} M_{k^*j}.\]

Adding alternative paths can only increase or keep constant the transition probability; alternative paths can never cancel out each other’s contributions. Destructive interference is mathematically impossible in any \(\ell_1\) stochastic model.

(c) Unitary Operators and \(\ell_2\) Norm Conservation:

(i) Using the definition of the Euclidean norm via the conjugate transpose inner product: \(\|U \ket{\psi}\|_2^2 = (U \ket{\psi})^\dagger (U \ket{\psi}) = \bra{\psi} U^\dagger U \ket{\psi}\). We require \(\|U \ket{\psi}\|_2^2 = \|\ket{\psi}\|_2^2 = \bra{\psi} I \ket{\psi}\) for all \(\ket{\psi} \in \mathbb{C}^N\). Thus:

\[\bra{\psi} (U^\dagger U - I) \ket{\psi} = 0 \quad \forall \ket{\psi}.\]

Let \(A = U^\dagger U - I\). The operator \(A\) is Hermitian (\(A^\dagger = A\)). For any Hermitian matrix \(A\), if \(\bra{\psi} A \ket{\psi} = 0\) for all \(\ket{\psi}\), all its eigenvalues must be zero, which implies \(A = 0\). Therefore, \(U^\dagger U = I\), meaning \(U\) is unitary. Conversely, if \(U^\dagger U = I\), \(\|U\ket{\psi}\|_2^2 = \bra{\psi}U^\dagger U \ket{\psi} = \bra{\psi}\ket{\psi} = \|\ket{\psi}\|_2^2\).

(ii) By the polarization identity for complex inner products, \(\braket{\phi}{\psi} = \frac{1}{4} \sum_{k=0}^3 i^{-k} \|\ket{\phi} + i^k \ket{\psi}\|_2^2\). Since \(U\) preserves the \(\ell_2\) norm of all vectors, it preserves each term in the sum, and therefore \(\braket{U\phi}{U\psi} = \braket{\phi}{\psi}\). Unitary operators are isometries that preserve all geometric lengths and angles.

(d) Invertibility of Evolution:

Because \(U^\dagger U = I\), the matrix \(U\) is always full rank and invertible with two-sided inverse \(U^{-1} = U^\dagger\). Furthermore, \((U^\dagger)^\dagger (U^\dagger) = U U^\dagger = I\), so \(U^\dagger\) is itself a valid unitary operator. Quantum evolution is always a reversible physical process.
In contrast, an arbitrary stochastic matrix \(M\) need not be invertible (e.g., the reset matrix with all rows equal to \((1, 0)\) has determinant \(0\)). Even when invertible, \(M^{-1}\) generally contains negative entries and is therefore not a valid stochastic matrix.

(a) The Path Sum:

Inserting the resolution of the identity \(I = \sum_z \ket{z}\bra{z}\) in the computational basis:

\[A(x \to y) = \bra{y} U_2 U_1 \ket{x} = \bra{y} U_2 \left( \sum_z \ket{z}\bra{z} \right) U_1 \ket{x} = \sum_z \bra{y} U_2 \ket{z} \bra{z} U_1 \ket{x}.\]

Each term \(A_z = \bra{y} U_2 \ket{z} \bra{z} U_1 \ket{x}\) is the complex amplitude along the specific computational path \(x \to z \to y\). The net transition probability is:

\[P(x \to y) = |A(x \to y)|^2 = \left| \sum_z A_z \right|^2 = \sum_z |A_z|^2 + \sum_{z \ne z'} A_z A_{z'}^*.\]

In contrast, classical probability theory prescribes \(P_{\text{class}}(x \to y) = \sum_z P(x \to z \to y) = \sum_z |A_z|^2\). The cross-terms \(\sum_{z \ne z'} 2 \operatorname{Re}(A_z A_{z'}^*)\) are the quantum interference terms.

(b) Constructing Destructive Interference:

We require the first row of \(U_2\), denoted \(\bra{u_0}\), to satisfy \(\braket{u_0}{\psi} = 0\), so that \(\bra{0} U_2 \ket{\psi} = 0\). Since \(\ket{\psi} = \frac{1}{\sqrt{3}}(\ket{0} + \ket{1} + \ket{2})\), the inner product with \(\bra{u_0} = (u_{00}^*, u_{01}^*, u_{02}^*)\) is \(\frac{1}{\sqrt{3}}(u_{00} + u_{01} + u_{02}) = 0\).
Choose the first row of \(U_2\) as \(\bra{u_0} = \frac{1}{\sqrt{2}}(0, 1, -1)\). Then \(\braket{u_0}{\psi} = \frac{1}{\sqrt{6}}(0 + 1 - 1) = 0\), yielding amplitude \(0\) and probability \(P(\ket{0}) = 0\).
To distribute the remaining probability equally, choose the second and third rows of \(U_2\) to form an orthonormal basis containing \(\bra{u_0}\). For instance, set:

\[\bra{u_1} = \left(\frac{2}{\sqrt{6}}, -\frac{1}{\sqrt{6}}, -\frac{1}{\sqrt{6}}\right), \quad \bra{u_2} = \left(\frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}}\right).\]

Then \(\bra{u_2} = \bra{\psi}\), so \(\bra{2}U_2\ket{\psi} = \braket{\psi}{\psi} = 1\), or rotating the \(\ket{1}\) and \(\ket{2}\) subspace by \(\frac{1}{\sqrt{2}}\begin{pmatrix}1 & 1 \\ 1 & -1\end{pmatrix}\), we obtain amplitudes \(\bra{1}U_2\ket{\psi} = 1/\sqrt{2}\) and \(\bra{2}U_2\ket{\psi} = 1/\sqrt{2}\). Thus \(P(\ket{1}) = 1/2\) and \(P(\ket{2}) = 1/2\). Destructive interference completely extinguishes the transition into configuration \(\ket{0}\).

(c) Which-Path Information and Erasure of Interference:

(i) Applying \(U_2 \otimes I\) gives \(\ket{\Psi_{\text{final}}} = \sum_z \sum_w \bra{z} U_1 \ket{x} \bra{w} U_2 \ket{z} \ket{w}_{\text{sys}} \otimes \ket{e_z}_{\text{anc}}\). The probability of finding the system in configuration \(\ket{y}\) is obtained by projecting onto \(\ket{y}\bra{y} \otimes I\):

\[P(x \to y) = \sum_z \sum_{z'} \bra{y} U_2 \ket{z} \bra{z} U_1 \ket{x} (\bra{y} U_2 \ket{z'})^* (\bra{z'} U_1 \ket{x})^* \braket{e_{z'}}{e_z}_{\text{anc}}.\]

Separating diagonal terms (\(z = z'\)) where \(\braket{e_z}{e_z} = 1\) from off-diagonal terms (\(z \ne z'\)) yields the stated equation.

(ii) When the ancilla states are orthogonal (\(\braket{e_{z'}}{e_z} = 0\) for \(z \ne z'\)), every cross-term vanishes: \(\sum_{z \ne z'} (\dots) \cdot 0 = 0\). Therefore:

\[P(x \to y) = \sum_z |\bra{y} U_2 \ket{z} \bra{z} U_1 \ket{x}|^2 = \sum_z P(x \to z \to y).\]

The quantum probability reduces exactly to the classical probability sum. Entangling the computational degrees of freedom with an ancillary environment destroys quantum interference without needing any active disturbance.

(a) Inner Products and Transition Amplitudes:

(i) By the measurement postulate (Section 4.2.2), when \(\ket{\psi} = \sum_j c_j \ket{b_j}\) is measured in the orthonormal basis \(\{\ket{b_j}\}\), the probability of outcome \(j\) is \(p(j) = |\braket{b_j}{\psi}|^2 = |c_j|^2\). If \(\ket{\phi}\) is one of the basis elements, say \(\ket{b_k}\), the probability of observing outcome \(\ket{\phi}\) is \(p(\phi) = |\braket{\phi}{\psi}|^2\).

(ii) If \(\braket{\phi}{\psi} = 0\), the detection probability is strictly zero. Geometrically, \(\ket{\psi}\) and \(\ket{\phi}\) are perpendicular in the Hilbert space. Physically, the two states represent mutually exclusive alternatives: a system prepared in \(\ket{\psi}\) will never trigger detector \(\phi\), allowing perfect, error-free discrimination.

(b) Real State Plane and Non-Orthogonal Discrimination:

(i) Using standard trigonometric angle-subtraction:
\[\braket{\psi(\theta_0)}{\psi(\theta_1)} = (\cos\theta_0\bra{0} + \sin\theta_0\bra{1})(\cos\theta_1\ket{0} + \sin\theta_1\ket{1}) = \cos\theta_0\cos\theta_1 + \sin\theta_0\sin\theta_1 = \cos(\theta_1 - \theta_0).\]

(ii) Let the measurement basis be \(\ket{b_0} = \cos\beta\ket{0} + \sin\beta\ket{1}\) and \(\ket{b_1} = -\sin\beta\ket{0} + \cos\beta\ket{1}\).
If state \(\ket{\psi_0} = \ket{0}\) was prepared, the probability of obtaining outcome \(b_1\) is \(|\braket{b_1}{\psi_0}|^2 = \sin^2\beta\). To ensure zero error on input \(\ket{\psi_0}\), we must set \(\sin^2\beta = 0\), forcing \(\beta = 0\) (so the basis is \(\{\ket{0}, \ket{1}\}\)).
Now evaluate this basis on state \(\ket{\psi_1} = \cos\delta\ket{0} + \sin\delta\ket{1}\): the probability of obtaining outcome \(0\) (which falsely identifies the state as \(\ket{\psi_0}\)) is \(|\braket{0}{\psi_1}|^2 = \cos^2\delta\). Since \(\delta \in (0, \pi/2)\), \(\cos^2\delta > 0\), so an error occurs with non-zero probability. Symmetrically, any basis that never misidentifies \(\ket{\psi_1}\) will misidentify \(\ket{\psi_0}\). Error-free discrimination is impossible unless \(\delta = \pi/2\) (\(\cos\delta = 0\), orthogonal states).

(c) Projective Measurement and Collapse:

The projector onto \(\ket{b_j}\) is \(P_j = \ketbra{b_j}{b_j}\). Acting on \(\ket{\psi} = \sum_k c_k \ket{b_k}\):
\[P_j\ket{\psi} = \ket{b_j}\braket{b_j}{\psi} = c_j \ket{b_j}.\]
Normalizing the non-zero result yields \(\frac{P_j\ket{\psi}}{\|P_j\ket{\psi}\|} = \frac{c_j}{|c_j|}\ket{b_j} = \ket{b_j}\) (up to an unobservable global phase). All components \(c_k \ket{b_k}\) for \(k \ne j\) are multiplied by \(\braket{b_j}{b_k} = 0\) and permanently erased. Because the projection operator has rank 1, it has a non-trivial null space and cannot be inverted.

(d) Sequential Incompatible Measurements:

(i) Starting in \(\ket{0}\), the \(X\)-basis measurement projects onto \(\ket{+}\) with probability \(|\braket{+}{0}|^2 = |1/\sqrt{2}|^2 = 1/2\) and \(\ket{-}\) with probability \(|\braket{-}{0}|^2 = |-1/\sqrt{2}|^2 = 1/2\).
If the outcome was \(\ket{+}\), the subsequent \(Z\)-measurement yields \(\ket{1}\) with probability \(|\braket{1}{+}|^2 = 1/2\).
If the outcome was \(\ket{-}\), the subsequent \(Z\)-measurement yields \(\ket{1}\) with probability \(|\braket{1}{-}|^2 = 1/2\).
By the law of total probability, the final probability of observing \(\ket{1}\) is \(\frac{1}{2}(1/2) + \frac{1}{2}(1/2) = 1/2\).

(ii) Without the intermediate \(X\)-measurement, measuring \(\ket{0}\) in the \(Z\)-basis would yield \(\ket{1}\) with probability \(0\). The intermediate measurement along the incompatible \(X\)-basis completely randomized the qubit, destroying all memory that it was initialized in \(\ket{0}\).

(a) Pauli Algebra:

(i) Multiplying matrices explicitly:
\[XZ = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}.\]
\[ZX = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} = -XZ.\]
Thus \(XZ = -ZX\): the operators anti-commute.

(ii) Evaluating the remaining products:
\[XY = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix} = \begin{pmatrix} i & 0 \\ 0 & -i \end{pmatrix} = i \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} = iZ.\]
Similarly, \(YZ = iX\) and \(ZX = iY\). Squaring each matrix: \(X^2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I\), \(Y^2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I\), and \(Z^2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I\).

(b) Pauli Basis Decomposition:

(i) Notice that \(I + Z = \begin{pmatrix} 2 & 0 \\ 0 & 0 \end{pmatrix}\), \(I - Z = \begin{pmatrix} 0 & 0 \\ 0 & 2 \end{pmatrix}\), \(X + iY = \begin{pmatrix} 0 & 2 \\ 0 & 0 \end{pmatrix}\), and \(X - iY = \begin{pmatrix} 0 & 0 \\ 2 & 0 \end{pmatrix}\). Every elementary matrix unit can therefore be expressed as a linear combination of \(\{I, X, Y, Z\}\). For an arbitrary matrix \(A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}\):

\[A = \frac{a+d}{2} I + \frac{b+c}{2} X + \frac{i(b-c)}{2} Y + \frac{a-d}{2} Z.\]

(ii) Notice that \(\operatorname{tr}(I) = 2\) while \(\operatorname{tr}(X) = \operatorname{tr}(Y) = \operatorname{tr}(Z) = 0\). Using the product identities from part (a): \(\operatorname{tr}(X^2) = \operatorname{tr}(I) = 2\), and \(\operatorname{tr}(XY) = \operatorname{tr}(iZ) = 0\), etc. For \(\sigma_j \in \{I, X, Y, Z\}\), \(\operatorname{tr}(\sigma_j \sigma_k) = 2\delta_{jk}\). Therefore, taking the trace of \(A \sigma_k\):

\[\operatorname{tr}(A \sigma_k) = \operatorname{tr}\left( \sum_{j=0}^3 c_j \sigma_j \sigma_k \right) = \sum_{j=0}^3 c_j \operatorname{tr}(\sigma_j \sigma_k) = \sum_{j=0}^3 c_j (2\delta_{jk}) = 2 c_k \implies c_k = \frac{1}{2}\operatorname{tr}(A \sigma_k).\]

(iii) For \(H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\):
\(c_0 = \frac{1}{2}\operatorname{tr}(H) = \frac{1}{2\sqrt{2}}(1 - 1) = 0\).
\(c_1 = \frac{1}{2}\operatorname{tr}(HX) = \frac{1}{2\sqrt{2}}\operatorname{tr}\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix} = \frac{1}{2\sqrt{2}}(2) = \frac{1}{\sqrt{2}}\).
\(c_2 = \frac{1}{2}\operatorname{tr}(HY) = \frac{1}{2\sqrt{2}}\operatorname{tr}\begin{pmatrix} i & -i \\ -i & -i \end{pmatrix} = 0\).
\(c_3 = \frac{1}{2}\operatorname{tr}(HZ) = \frac{1}{2\sqrt{2}}\operatorname{tr}\begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix} = \frac{1}{2\sqrt{2}}(2) = \frac{1}{\sqrt{2}}\).
Thus \(H = \frac{1}{\sqrt{2}}(X + Z)\).

(c) Relative Phase and Output Probabilities:

(i) Tracing the circuit step by step:
1. Initial state: \(\ket{0}\).
2. After \(H\): \(\ket{+} = \frac{1}{\sqrt{2}}(\ket{0} + \ket{1})\).
3. After \(P(\phi)\): \(\ket{\psi_\phi} = \frac{1}{\sqrt{2}}(\ket{0} + e^{i\phi}\ket{1})\).
4. After second \(H\):

\[\ket{\text{out}} = H\ket{\psi_\phi} = \frac{1}{2}(\ket{0} + \ket{1}) + \frac{e^{i\phi}}{2}(\ket{0} - \ket{1}) = \left(\frac{1+e^{i\phi}}{2}\right)\ket{0} + \left(\frac{1-e^{i\phi}}{2}\right)\ket{1}.\]

(ii) Factoring out \(e^{i\phi/2}\):
\(\frac{1+e^{i\phi}}{2} = e^{i\phi/2}\left(\frac{e^{-i\phi/2}+e^{i\phi/2}}{2}\right) = e^{i\phi/2}\cos(\phi/2)\).
\(\frac{1-e^{i\phi}}{2} = e^{i\phi/2}\left(\frac{e^{-i\phi/2}-e^{i\phi/2}}{2}\right) = -i e^{i\phi/2}\sin(\phi/2)\).
The probabilities are:
\(P(0) = |e^{i\phi/2}\cos(\phi/2)|^2 = \cos^2(\phi/2)\).
\(P(1) = |-i e^{i\phi/2}\sin(\phi/2)|^2 = \sin^2(\phi/2)\).

(iii) Before the second Hadamard gate, the probability of measuring \(\ket{0}\) or \(\ket{1}\) in the state \(\ket{\psi_\phi}\) is \(|1/\sqrt{2}|^2 = 1/2\) and \(|e^{i\phi}/\sqrt{2}|^2 = 1/2\), completely independent of \(\phi\). The second Hadamard gate brings the \(\ket{0}\) and \(\ket{1}\) paths together, causing them to interfere constructively and destructively, translating the phase angle \(\phi\) into a population difference.

(d) Global Phase Invariance:

Let \(\ket{\psi'} = e^{i\alpha}\ket{\psi}\). For any basis state \(\ket{b_j}\):
\[p'(j) = |\braket{b_j}{\psi'}|^2 = |\braket{b_j}{e^{i\alpha}\psi}|^2 = |e^{i\alpha}\braket{b_j}{\psi}|^2 = |e^{i\alpha}|^2 |\braket{b_j}{\psi}|^2 = (1) |\braket{b_j}{\psi}|^2 = p(j).\]
All measurement probabilities are identical, so two state vectors differing only by a global phase represent the exact same physical state.

(a) Local Operations Preserve Product Structure:

(i) By the definition of the tensor product of linear operators: \((U_A \otimes U_B)(\ket{\psi_A} \otimes \ket{\psi_B}) = (U_A \ket{\psi_A}) \otimes (U_B \ket{\psi_B})\). Let \(\ket{\phi_A} = U_A \ket{\psi_A} \in \mathcal{H}_A\) and \(\ket{\phi_B} = U_B \ket{\psi_B} \in \mathcal{H}_B\). Both \(\ket{\phi_A}\) and \(\ket{\phi_B}\) are normalized state vectors. Therefore, the resulting state is \(\ket{\phi_A} \otimes \ket{\phi_B}\), which is a product state by definition.

(ii) Since a product state has entanglement zero, and local operations map product states to product states, local operations alone cannot generate entanglement from an initially unentangled state.

(b) Bell State Synthesis and Non-Factorization:

(i) Tracing the circuit:
1. Initial state: \(\ket{00}\).
2. Applying \(H \otimes I\): \(\ket{00} \mapsto \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) \otimes \ket{0} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{10})\).
3. Applying \(\text{CNOT}_{1 \to 2}\): By linearity, \(\frac{1}{\sqrt{2}}(\text{CNOT}\ket{00} + \text{CNOT}\ket{10}) = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11}) = \ket{\Phi^+}\).

(ii) To prove \(\ket{\Phi^+}\) does not factor, suppose there exist complex numbers \(\alpha, \beta, \gamma, \delta\) such that:

\[(\alpha\ket{0} + \beta\ket{1}) \otimes (\gamma\ket{0} + \delta\ket{1}) = \alpha\gamma\ket{00} + \alpha\delta\ket{01} + \beta\gamma\ket{10} + \beta\delta\ket{11} = \frac{1}{\sqrt{2}}\ket{00} + \frac{1}{\sqrt{2}}\ket{11}.\]

Equating coefficients:
1. \(\alpha\gamma = 1/\sqrt{2}\) (\(\alpha \ne 0\), \(\gamma \ne 0\)).
2. \(\beta\delta = 1/\sqrt{2}\) (\(\beta \ne 0\), \(\delta \ne 0\)).
3. \(\alpha\delta = 0\). But since \(\alpha \ne 0\) and \(\delta \ne 0\), their product cannot be zero! Contradiction.
Therefore, \(\ket{\Phi^+}\) cannot be factored: its probability amplitudes cannot be localized to individual qubits.

(c) The Bell Basis:

(i) Computing inner products:
\(\braket{\Phi^+}{\Phi^-} = \frac{1}{2}(\bra{00}+\bra{11})(\ket{00}-\ket{11}) = \frac{1}{2}(1 - 1) = 0\).
\(\braket{\Phi^\pm}{\Psi^\pm} = 0\) identically because the \(\Phi\) states have support exclusively on \(\{\ket{00}, \ket{11}\}\) while the \(\Psi\) states have support exclusively on \(\{\ket{01}, \ket{10}\}\), and these two subspaces are orthogonal.
\(\braket{\Phi^+}{\Phi^+} = \frac{1}{2}(1 + 1) = 1\). Symmetrically for all four states. Hence they form an orthonormal basis.

(ii) The circuit consisting of \(H\) on qubit 1 followed by \(\text{CNOT}_{1 \to 2}\) maps:
- \(\ket{00} \xrightarrow{H \otimes I} \frac{\ket{00}+\ket{10}}{\sqrt{2}} \xrightarrow{\text{CNOT}} \ket{\Phi^+}\).
- \(\ket{01} \xrightarrow{H \otimes I} \frac{\ket{01}+\ket{11}}{\sqrt{2}} \xrightarrow{\text{CNOT}} \ket{\Psi^+}\).
- \(\ket{10} \xrightarrow{H \otimes I} \frac{\ket{00}-\ket{10}}{\sqrt{2}} \xrightarrow{\text{CNOT}} \ket{\Phi^-}\).
- \(\ket{11} \xrightarrow{H \otimes I} \frac{\ket{01}-\ket{11}}{\sqrt{2}} \xrightarrow{\text{CNOT}} \ket{\Psi^-}\).
The unitary circuit \(U_{\text{Bell}} = \text{CNOT}_{1 \to 2} (H \otimes I)\) maps the computational basis bijectively to the Bell basis.

(a) The Hypothetical Cloning Machine:

A universal cloning machine must execute the unitary mapping \(U(\ket{\psi}\ket{0}) = \ket{\psi}\ket{\psi}\) for any arbitrary state \(\ket{\psi} \in \mathcal{H}\).

(b) Proof by Inner Product Preservation:

(i) For input states \(\ket{\psi}\ket{0}\) and \(\ket{\phi}\ket{0}\):

\[\braket{\psi\otimes 0}{\phi\otimes 0} = (\braket{\psi}{\phi})(\braket{0}{0}) = \braket{\psi}{\phi}.\]

(ii) For the cloned output states \(\ket{\psi}\ket{\psi}\) and \(\ket{\phi}\ket{\phi}\):

\[\braket{\psi\otimes \psi}{\phi\otimes \phi} = (\braket{\psi}{\phi})(\braket{\psi}{\phi}) = (\braket{\psi}{\phi})^2.\]

(iii) Since \(U\) is unitary, it preserves all inner products: \(\braket{U(\psi\otimes 0)}{U(\phi\otimes 0)} = \braket{\psi\otimes 0}{\phi\otimes 0}\). Therefore:

\[\braket{\psi}{\phi} = (\braket{\psi}{\phi})^2.\]

(iv) The equation \(z = z^2\) has only two roots: \(z = 0\) or \(z = 1\). This means \(\braket{\psi}{\phi} = 0\) (the states are orthogonal) or \(|\braket{\psi}{\phi}| = 1\) (the states are identical up to a global phase). A cloning machine can only clone sets of mutually orthogonal states; it cannot clone a general unknown quantum state.

(c) Proof by Linearity:

(i) By linearity of unitary operator \(U\):

\[U(\ket{+}\ket{0}) = U\left( \frac{\ket{0} + \ket{1}}{\sqrt{2}} \otimes \ket{0} \right) = \frac{1}{\sqrt{2}} U(\ket{0}\ket{0}) + \frac{1}{\sqrt{2}} U(\ket{1}\ket{0}) = \frac{1}{\sqrt{2}}\ket{00} + \frac{1}{\sqrt{2}}\ket{11} = \ket{\Phi^+}.\]

(ii) The desired cloned state is:

\[\ket{+}\ket{+} = \left(\frac{\ket{0}+\ket{1}}{\sqrt{2}}\right) \otimes \left(\frac{\ket{0}+\ket{1}}{\sqrt{2}}\right) = \frac{1}{2}\ket{00} + \frac{1}{2}\ket{01} + \frac{1}{2}\ket{10} + \frac{1}{2}\ket{11}.\]

(iii) The actual evolved state is the entangled Bell state \(\ket{\Phi^+}\), which completely lacks the product terms \(\ket{01}\) and \(\ket{10}\). Since \(\ket{\Phi^+} \ne \ket{+}\ket{+}\), the cloning operation fails. Linearity dictates that the machine entangles the target with the source rather than copying the superposition.

(d) Classical vs. Quantum Copying:

The CNOT gate acts on the computational basis as \(\ket{00} \to \ket{00}\) and \(\ket{10} \to \ket{11}\). These two configurations are mutually orthogonal (\(\braket{0}{1} = 0\)). Since \(\braket{0}{1} = 0\) satisfies \(z = z^2\) (\(0 = 0^2\)), copying orthogonal basis states does not violate the no-cloning theorem. Classical computers only ever store and copy orthogonal bit states (\(0\) or \(1\)). Quantum cloning becomes impossible only when trying to clone an unknown state with non-trivial superposition amplitudes.

(a) Quantum Teleportation Decomposition:

(i) Expanding the joint state:

\[\ket{\Psi_{123}} = (\alpha\ket{0}_1 + \beta\ket{1}_1) \otimes \frac{1}{\sqrt{2}}(\ket{00}_{23} + \ket{11}_{23}) = \frac{1}{\sqrt{2}} \left[ \alpha\ket{000} + \alpha\ket{011} + \beta\ket{100} + \beta\ket{111} \right].\]

(ii) We invert the Bell basis definitions for qubits 1 and 2:
\(\ket{00} = \frac{1}{\sqrt{2}}(\ket{\Phi^+} + \ket{\Phi^-})\), \(\ket{11} = \frac{1}{\sqrt{2}}(\ket{\Phi^+} - \ket{\Phi^-})\),
\(\ket{01} = \frac{1}{\sqrt{2}}(\ket{\Psi^+} + \ket{\Psi^-})\), \(\ket{10} = \frac{1}{\sqrt{2}}(\ket{\Psi^+} - \ket{\Psi^-})\).
Substituting these into \(\ket{\Psi_{123}}\):

\[\ket{\Psi_{123}} = \frac{1}{2} \left[ \alpha(\ket{\Phi^+} + \ket{\Phi^-})\ket{0} + \alpha(\ket{\Psi^+} + \ket{\Psi^-})\ket{1} + \beta(\ket{\Psi^+} - \ket{\Psi^-})\ket{0} + \beta(\ket{\Phi^+} - \ket{\Phi^-})\ket{1} \right].\]

Regrouping by Alice’s Bell states:

\[\ket{\Psi_{123}} = \frac{1}{2} \left[ \ket{\Phi^+}_{12}(\alpha\ket{0} + \beta\ket{1}) + \ket{\Phi^-}_{12}(\alpha\ket{0} - \beta\ket{1}) + \ket{\Psi^+}_{12}(\beta\ket{0} + \alpha\ket{1}) + \ket{\Psi^-}_{12}(-\beta\ket{0} + \alpha\ket{1}) \right].\]

(iii) The required unitary correction operations on Bob’s qubit 3 are:
- If Alice measures \(\ket{\Phi^+}_{12}\): Bob has \(\ket{\psi}\), applies \(I\).
- If Alice measures \(\ket{\Phi^-}_{12}\): Bob has \(Z\ket{\psi}\), applies \(Z\).
- If Alice measures \(\ket{\Psi^+}_{12}\): Bob has \(X\ket{\psi}\), applies \(X\).
- If Alice measures \(\ket{\Psi^-}_{12}\): Bob has \(XZ\ket{\psi}\), applies \(ZX = -iY\) (or \(XZ\)).

(b) The No-Signaling Theorem:

(i) By the measurement postulate, Bob's probability of observing outcome \(b\) is the sum of joint probabilities \(p(a, b) = |c_{ab}|^2\) for all of Alice's outcomes \(a \in \{0, 1\}\):
\[p_B(b) = p(0, b) + p(1, b) = |c_{0b}|^2 + |c_{1b}|^2.\]
Since \(\ket{v_b} = c_{0b}\ket{0} + c_{1b}\ket{1}\), its squared Euclidean length is \(\|\ket{v_b}\|^2 = |c_{0b}|^2 + |c_{1b}|^2 = p_B(b)\).

(ii) Applying \(U_A \otimes I\) yields \(\ket{\Psi'} = (U_A\ket{v_0})\otimes\ket{0} + (U_A\ket{v_1})\otimes\ket{1}\). Bob's probability of observing \(b\) becomes \(p'_B(b) = \|U_A\ket{v_b}\|^2\). Because unitary operators are isometries that preserve Euclidean lengths (\(\|U_A\ket{v}\| = \|\ket{v}\|\)), we have \(\|U_A\ket{v_b}\|^2 = \|\ket{v_b}\|^2\). Thus \(p'_B(b) = p_B(b)\). Alice's local gate cannot transfer amplitude across Bob's orthogonal basis sectors.

(iii) If Alice measures outcome \(a\), the conditional probability for Bob to see \(b\) is \(p(b \mid a) = \frac{|c_{ab}|^2}{p_A(a)}\). Without Alice's message, Bob's observed probability is the statistical average across all branches:
\[\sum_a p_A(a) p(b \mid a) = \sum_a p_A(a) \frac{|c_{ab}|^2}{p_A(a)} = \sum_a |c_{ab}|^2 = p_B(b).\]
The branch probability \(p_A(a)\) exactly cancels the normalization denominator of the collapsed state!

(iv) Because neither local gates nor local measurements can alter Bob's outcome probabilities in any basis, Alice cannot transmit any signal to Bob through entanglement alone. In teleportation, Bob's qubit is left in an unconditioned random mixture until he receives Alice's classical measurement bits over an ordinary channel that respects the speed of light.

(a) The Oracle Gate:

(i) Applying \(U_f\) twice to any basis state:

\[U_f^2 \ket{x}\ket{y} = U_f \ket{x}\ket{y \oplus f(x)} = \ket{x}\ket{(y \oplus f(x)) \oplus f(x)} = \ket{x}\ket{y \oplus 0} = \ket{x}\ket{y}.\]

Since \(U_f^2 = I\), \(U_f^{-1} = U_f\). Because \(U_f\) is a permutation of the real standard basis, its matrix elements are real, so \(U_f^\dagger = U_f^T = U_f\). Thus \(U_f\) is both unitary and Hermitian.

(ii) Initial state: \(\ket{\psi_0} = \frac{1}{\sqrt{2^n}}\sum_{x} \ket{x}\ket{0}\). Applying \(U_f\) by linearity:

\[\ket{\psi_f} = U_f \left(\frac{1}{\sqrt{2^n}}\sum_x \ket{x}\ket{0}\right) = \frac{1}{\sqrt{2^n}}\sum_{x \in \{0,1\}^n} \ket{x}\ket{f(x)}.\]

(b) What a Complete Measurement Reveals:

(i) Each basis configuration \(\ket{x}\ket{f(x)}\) has amplitude \(1/\sqrt{2^n}\). By the measurement postulate, the probability of observing any specific pair \((x_0, f(x_0))\) is:

\[P(x_0, f(x_0)) = \left|\frac{1}{\sqrt{2^n}}\right|^2 = \frac{1}{2^n}.\]

(ii) The measurement projects the state onto the single observed configuration \(\ket{x_0}\ket{f(x_0)}\), irreversibly destroying the superposition of all other \(2^n - 1\) computational branches. We learn the function value for only one randomly chosen input \(x_0\). This provides no advantage over simply choosing \(x_0\) at random classically and evaluating \(f(x_0)\). Quantum parallelism alone does not yield a speedup without subsequent interference to extract global properties.

(c) Measuring Only the Target Qubit:

(i) We can split the state \(\ket{\psi_f}\) into two orthogonal sums based on the value of \(f(x)\):

\[\ket{\psi_f} = \frac{1}{\sqrt{2^n}}\left( \sum_{x: f(x)=0} \ket{x} \right)\ket{0} + \frac{1}{\sqrt{2^n}}\left( \sum_{x: f(x)=1} \ket{x} \right)\ket{1}.\]

The probability of observing \(0\) on the target is the sum of squared amplitudes for all configurations with target \(0\):

\[P(y = 0) = \sum_{x: f(x)=0} \left|\frac{1}{\sqrt{2^n}}\right|^2 = \frac{N_0}{2^n},\]

where \(N_0 = |\{x \mid f(x) = 0\}|\) is the number of preimages of \(0\). Similarly, \(P(y = 1) = \frac{N_1}{2^n}\) where \(N_1 = 2^n - N_0\).

(ii) When the target measurement yields \(0\), the projector \(I \otimes \ketbra{0}{0}\) selects the first sum. Normalizing the collapsed state yields:

\[\ket{\psi_{\text{in}}^{(0)}} = \frac{1}{\sqrt{N_0}} \sum_{x: f(x)=0} \ket{x}.\]

(iii) When the target measurement yields \(1\), the projector \(I \otimes \ketbra{1}{1}\) selects the second sum. Normalizing the collapsed state yields:

\[\ket{\psi_{\text{in}}^{(1)}} = \frac{1}{\sqrt{N_1}} \sum_{x: f(x)=1} \ket{x}.\]

(iv) Because the target bit is entangled with the input register, measuring only the target performs a partial measurement that projects the input register into an equal superposition over all preimages of the observed value. This prepares a clean superposition over a specific functional level set.