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]
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.)
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.]
[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.
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.
Show that it is possible to exactly simulate \(\mathrm{COIN}_{3/8}\) if your program has access to \(\mathrm{COIN}_{1/2}\) operations.
Show that it is impossible to exactly simulate \(\mathrm{COIN}_{1/7}\) if your program only has access to \(\mathrm{COIN}_{1/2}\) operations.
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.\][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
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.]
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.
Explicitly work out the entries of \(Q\) when \(\vert\psi\rangle = \vert1\rangle\) and \(\vert\phi\rangle = \vert-\rangle\).
Consider the matrix \(P = \vert\psi\rangle\langle \psi\vert\). Describe geometrically the transformation \(P\).
Describe geometrically the transformation \(I-2P\), where \(I\) is the \(d \times d\) identity matrix, and show that \(I-2P\) is unitary.
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.
Watch this video on the Many Worlds Interpretation (MWI) of quantum mechanics.