1. Universal gates for classical circuits [12 points]

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 NAND gates. (You may allow NAND 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.]

2. Simulating a biased coin [15 points]

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 impossible to exactly simulate $\mathrm{COIN}_{1/5}$ if your program only has access to $\mathrm{COIN}_{1/2}$ operations.

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

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

3. 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}] &= 4/5 \\ \Pr[G(\epsilon)=1 \mid G(\epsilon) \neq \mathrm{FAIL}] &= 1/5. \end{align*}$$

3. Unitary matrices [8 points]

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]

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 = \vert0\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.