Chapter 1

Introduction and Overview

Exercise

1.1

So long as the set of possible \(x\) is finite, only 2 times are needed to keep error probability less than 1/2.
Say \(x_0\neq x_1\in {0,…,2^{n}-1}\), $$ f(x_0)=f(x_1) \Rightarrow f\ \text{is constant,}\\ f(x_0)\ne f(x_1) \Rightarrow f\ \text{is balanced.} $$ For the second condition, no error will occur. For the first condition, error occurs when we pick two variable from the same subset with \(2^n-1\) members, so the error probabilty is $$ \epsilon=\dfrac{2^{n-1}-1}{2^n-1}=\dfrac{1}{2}-\dfrac{1}{2(2^n-1)}<\dfrac{1}{2}. $$

For a given threshold \(\epsilon\), we should require after \(k\) times evaluation, $$ 2\times\dfrac{\left( \begin{array}{c} 2^{n-1}\\ k\\ \end{array} \right)}{\left( \begin{array}{c} 2^n\\ k\\ \end{array} \right)}\le\epsilon $$ The coefficient 2 comes from that the first pick can be either value. Suppose \(n\) is very large and \(2k\ll 2^n\), we take logarithm and use Stirling’s approximation:

$$ 2^{n-1}\ln2^{n-1}-2^n\ln2^n+(2^n-k)\ln(2^n-k)-(2^{n-1}-k)\ln(2^{n-1}-k)<\ln\frac{\epsilon}{2}\\ \frac{k^2}{2^n}+k\ln2+\ln\frac{\epsilon}{2}\gtrsim0\\ k\gtrsim2^{n-1}\times(-\ln2+\sqrt{(\ln2)^2-2^{2-n}\ln\frac{\epsilon}{2}})\sim2^{n/2}\sqrt{\ln\epsilon} $$

1.2

If we have a device to distinguish \(|\psi\rangle\) and \(|\phi\rangle\) correctly, then given a state, we can use the device to figure out what the state is, and according to the result, we can (in principal) produce the same state as many as we want. Therefore, we build a cloning device for \(|\psi\rangle\) and \(|\phi\rangle\) in a identification-producing way.

If we have a clonig device, we just make as many copies as we need and measure these identical states in the basis {\(|\psi\rangle,\ |\psi^{\perp}\rangle\)}, then we can draw the conclusion because: $$ \lim_{n\rightarrow\infty}|\langle\psi|\phi\rangle|^n=0 $$ so long as they are different.

Updated: 2021-09-11