1. Universal gates for classical circuits [12+4 points]

SOLUTION

1. Show that any Boolean function \(f : \{0,1\}^n \to \{0,1\}\) can be computed by a Boolean circuit using the following set of logic gates: \(2\)-bit AND, \(2\)-bit OR, and NOT.

   [Hint: Disjunctive normal form]

2. Show that any Boolean function can be computed by a Boolean circuit consisting only of NOR gates. (You may allow NOR gates with one of the inputs hard-coded to be 0 or 1.)

3. Show that there are infinitely many Boolean functions that cannot be computed by a Boolean circuit using only AND and OR gates.

   [Hint: A Boolean function \(f : \{0,1\}^n \to \{0,1\}\) is called monotone if flipping any input bit from 0 to 1 (and leaving the rest fixed) cannot change the value of the output from 1 to 0. Think about whether AND and OR gates are monotone, and what that means about any circuit composed of AND and OR gates.]

4. [BONUS] Show that there are infinitely many Boolean functions \(f : \{0,1\}^n \to \{0,1\}\) that cannot be computed by a Boolean circuit using only XOR and NOT gates.

2. Simulating a biased coin [12+4 points]

SOLUTION

Suppose that your favorite programming language can only access random numbers via an operation called \(\mathrm{COIN}_p\) that returns 1 with probability \(p\) and 0 with probability \(1-p\). Distinct calls to \(\mathrm{COIN}_p\) are independent random trials.

1. Show that it is possible to exactly simulate \(\mathrm{COIN}_{3/8}\) if your program has access to \(\mathrm{COIN}_{1/2}\) operations.

2. Show that it is impossible to exactly simulate \(\mathrm{COIN}_{1/7}\) if your program only has access to \(\mathrm{COIN}_{1/2}\) operations.

3. On the other hand, show that it is possible to use \(\mathrm{COIN}_{1/2}\) operations to approximately simulate \(\mathrm{COIN}_{1/7}\): Give pseudocode for a (randomized) function \(F(\epsilon)\) with outputs \(\{0,1\}\) and such that

   \[\frac{1}{7} - \epsilon \leq \Pr\left[F(\epsilon) = 1\right] \leq \frac{1}{7} + \epsilon.\]

4. [BONUS] Show that it’s possible to do something slightly stronger: Give pseudocode for a (randomzied) function \(G(\epsilon)\) with outputs \(\{0,1,\mathrm{FAIL}\}\) such that \(\Pr[G(\epsilon) = \mathrm{FAIL}] \leq \epsilon\) and

\[\begin{align*} \Pr[G(\epsilon)=0 \mid G(\epsilon) \neq \mathrm{FAIL}] &= 6/7 \\ \Pr[G(\epsilon)=1 \mid G(\epsilon) \neq \mathrm{FAIL}] &= 1/7. \end{align*}\]

3. Unitary matrices [8 points]

SOLUTION

Let \(A\) be a \(d \times d\) complex matrix with the property that \(\|Av\|_2 = \|v\|_2\) for all \(v \in \mathbb{C}^d.\) Prove that \(A\) is a unitary matrix, i.e., \(A^{*} A = I\), where \(A^*\) denotes the conjugate transpose of \(A\).

[Hint: Recall the singular value decomposition of a matrix.]

4. Bras and kets [8 points]

SOLUTION

Consider two unit vectors \(\vert\psi\rangle\) and \(\vert\phi\rangle\) in \(\mathbb{C}^d\). Then \(Q = \vert\phi\rangle \langle \psi\vert\) is a \(d \times d\) complex matrix.

1. Explicitly work out the entries of \(Q\) when \(\vert\psi\rangle = \vert1\rangle\) and \(\vert\phi\rangle = \vert-\rangle\).

2. Consider the matrix \(P = \vert\psi\rangle\langle \psi\vert\). Describe geometrically the transformation \(P\).

3. Describe geometrically the transformation \(I-2P\), where \(I\) is the \(d \times d\) identity matrix, and show that \(I-2P\) is unitary.

4. Suppose that \(\vert\psi_1\rangle, \ldots, \vert\psi_d\rangle\) and \(\vert\phi_1\rangle, \ldots, \vert\phi_d\rangle\) are orthonormal bases in \(\mathbb{C}^d\). Use the bra-ket notation to define a unitary matrix that transforms one bases into the other and justify your definition.

5. Many Worlds [4 points]

Watch this video on the Many Worlds Interpretation (MWI) of quantum mechanics.