Solutions for Quantum computation and Quantum Information

This is an unofficial solution manual for for “Quantum Computation and Quantum Information: 10th Anniversary Edition (ISBN-13: 978-1107002173) by Nielsen and Chuang. This is available as a pdf also.

There is no guarantee that these solutions are correct. If you have any corrections or suggestions, please contact me or add a pull request.

Chapter 1

Exercise 1.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 a constant or a balanced function (atleast not with probability of error $\epsilon < 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 $\epsilon < 1/2$. Therefore, the best classical algorithm (probabilistic) will require 2 evaluations, irrespective of size of the input.

Exercise 1.2

If a device, upon input of one of two non-orthogonal quantum states correctly identified the state, without collapsing. 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.