# CSE 599Q: Homework #1 (Review)

## Review

Due: Wed, Oct 12 @ 11:59pm

## 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.