1 Introduction and Overview
Exercise 1
It is already shown that a deterministic classical computer would require \(2^n/2+1\) queries.
Instead, if we use a probabilistic classical computer i.e, \(f(x)\) is evaluated for randomly chosen \(x\), with just one execution we cannot determine whether \(f(x)\) is constant or balanced function (atleast not with probability of error ε < 1/2). If the second evaluation gives a different result than first, we can say with certainity that \(f(x)\) is a balanced function. In the other case, the probaility that we get same result twice in a row if the function was balanced would be 1/2 for the first evaluation times \(\frac{2^n/2-1}{2^n-1}\) for the second which is less than 1/2 if:
\begin{equation}
\begin{split}
\frac{1}{2} \times \frac{2^n/2-1}{2^n-1} & < \frac{1}{2}\\\
2^n-2 & < 2(2^n-1)\\\
2^n & < 2^{n+1} \\\
n & < n+1
\end{split}
\end{equation}
which is always true for all positive integer \(n\) . So if we get same evaluation twice, we can say that \(f(x)\) is a constant function with a probability of error ε < 1/2. Therefore, the best classical algorithm (probabilistic) will require 2 evaluations, irrespective of size of the input.
Exercise 2
If a device, upon input of one of two non-orthogonal quantum states correctly identified the state without collapsing, then we can perform certain unitary transformation on an extra quantum state to create either of the quantum states, since we know its coefficients. Thus creating a clone of the input quantum state.
Conversely, if we have a device for cloning, we can in principle, generate multiple copies of the unknown quantum states and perform ensemble measurement to find it’s coefficients (hidden information - not accessible in single measurement) with enough precision to identify/distinguish them.
Problem 1
As suggested, I will attempt this once I finish rest of the book. An example: https://www.douban.com/group/topic/22546986.
Problem 2
As suggested, I will attempt this once I finish rest of the book.
2 Introduction to quantum mechanics
Exercise 1
To prove that a set of vectors are linearly dependent, it is enough to show that there exists a set of complex numbers \((a_1,…,a_n)\), not all zero, such that \(\newcommand{\ket}[1]{\lvert #1 \rangle}\) \[a_1\ket{v_1}+a_2\ket{v_1}+…+a_n\ket{v_n} = 0.\] Here,
\begin{equation}
\begin{split}
a_1
\begin{bmatrix}
1 \\\
-1
\end{bmatrix}
+a_2
\begin{bmatrix}
1 \\\
2
\end{bmatrix}
+a_3
\begin{bmatrix}
2 \\\
1
\end{bmatrix}
\begin{bmatrix}
0 \\\
0
\end{bmatrix}
\\\
\\\
\Rightarrow
a_1 + a_2 + 2 a_3 = 0,\\\
-a_1 + 2 a_2 +a_3 = 0.\\\
\end{split}
\end{equation}
This is a set of 2 simultaneous equations in 3 variables, so there exists \(\infty\) number of solutions like \(a_1=1, a_2=1,a_3=-1\) and any multiples of them.
Exercise 2
The matrix representation of an operator depends on the choise of basis for the underlying vector space (both input and output).
In this case, if we use \(\ket{0}\) and \(\ket{1}\) as the basis for V,
\begin{equation*}
\begin{split}
A\ket{v_1} &= A\ket{0} = A_{11}\ket{w_1}+A_{21}\ket{w_2} = A_{11}\ket{0}+A_{21}\ket{1}=\ket{1}
\Rightarrow A_{11} &= 0, A_{21} = 1\\\
A\ket{1} &= A_{12}\ket{0}+A_{22}\ket{1} = \ket{0} \Rightarrow A_{12} = 1,A_{22}=0\\\
\therefore A &=
\begin{bmatrix}
0 & 1 \\\
1 & 0
\end{bmatrix}
\end{split}
\end{equation*}
Instead, if we use \(\frac{\ket{0}+\ket{1}}{2}\) and \(\frac{\ket{0}-\ket{1}}{2}\) as the basis for V,
\begin{equation*}
\begin{split}
A\left(\frac{\ket{0}+\ket{1}}{2}\right) &= A_{11}\frac{\ket{0}+\ket{1}}{2}+A_{21}\frac{\ket{0}-\ket{1}}{2}= \frac{\ket{1}+\ket{0}}{2} \Rightarrow A_{11} = 1, A_{21} = 0\\\
A\left(\frac{\ket{0}-\ket{1}}{2}\right) &= A_{12}\frac{\ket{0}+\ket{1}}{2}+A_{22}\frac{\ket{0}-\ket{1}}{2}= \frac{\ket{1}-\ket{0}}{2} \Rightarrow A_{12} = 0, A_{22} = -1\\\
\therefore A &=
\begin{bmatrix}
1 & 0 \\\
0 & -1
\end{bmatrix}
\end{split}
\end{equation*}