I'm working on the following problem form Nielsen and Chuang (Ex. 4.40) regarding the universality of Hadamard, phase and $\pi/8$ gates for single qubit gates:

For arbitrary $\alpha$, $\beta$,

$E(R_{\vec{n}}(\alpha), R_{\vec{n}}(\alpha + \beta)) = |1 - exp(i\beta/2)|$, where $E(U, V) = max_{|\psi\rangle} || (U-V)|\psi\rangle||$

Show (using the previous equality) $\forall \epsilon >0$ , $\exists n$, such that $E(R(\alpha)_{\vec{n}}, {R(\theta)_{\vec{n}}}^n) < \frac{\epsilon}{3}$, where $\theta$ is an irrational multiple of $2\pi$.

My attempt:

Prior to the exercise, it discusses how for any arbitrary error $\epsilon > 0$, we can find some multiple $(mod$ $2\pi)$ of irrational $\theta$ (found using the Pigeonhole principle, which I think I understand, and I'm skipping and taking as given), call it $\theta_k \in (0, 2\pi]$, |$\theta_k| < \epsilon$ such that all multiples $(mod$ $2\pi)$ of $\theta_k$ differ by at most $\epsilon$. Thus $\forall \alpha \in [0, 2\pi)$, $\exists m$, such that $|\alpha - (m\theta_k) | =|\alpha - (mk\theta)| < \epsilon$. Let $n = mk$, then

$E(R(\alpha), {R_{\vec{n}}}(\theta)^n) = E(R_{\vec{n}}(\alpha), {R_{\vec{n}}}(n\theta)) = E(R_{\vec{n}}(\alpha), {R_{\vec{n}}}(\alpha + (n\theta -\alpha))) < E(R_{\vec{n}}(\alpha), {R_{\vec{n}}}(\alpha + \epsilon)) = |1 - exp(i\epsilon/2)| = \sqrt{((1 - cos(\epsilon/2))^2 + sin(\epsilon/2)^2} = \sqrt{2(1 - cos(\epsilon/2))} < 2$

(which is not correct).

I feel like I'm missing something very obvious in this whole exercise. A hint would be appreciated.

  • 1
    $\begingroup$ Remember to think of $\epsilon$ as small. With that, you can get a much better bound for that square root. This might put an extra upper bound on $\epsilon$ at first so you don't reach $\epsilon = 2 \pi$. But you can fix that next. $\endgroup$
    – AHusain
    Mar 23, 2020 at 20:33
  • $\begingroup$ @AHusain oh wow, small angle approximation. So with small angle approximation, it becomes : $\sqrt{2(1-cos(\epsilon/2))} \approx \sqrt{2(1-(1 - (\epsilon/2)^2/2))} = \epsilon/2$ This means $\epsilon$ is approximately less than $\frac{\pi}{4}$. It doesn't look like it can be made tighter. However, I get that $\epsilon$ can technically be made smaller than $\frac{\pi}{4}$. $\endgroup$
    – dylan7
    Mar 23, 2020 at 22:20

1 Answer 1


Firstly, I think there's a reason why the bit in the textbook before the question is using $\delta$ instead of $\epsilon$ for the results. So, replacing what you've written, it should really be $$ E<\sqrt{2(1-\cos(\delta/2))} $$

Now, start with a double-angle formula: $1-\cos(\delta/2)=2\sin^2(\delta/4)$. Thus, $$ E<2\sin(\delta/4) $$ Now if you apply the small $\epsilon$ approximation (which should be more obvious following that manipulation), you get $$ E<\delta/2. $$ Finally, if you want $E<\delta/2$, you simply have to select $\delta=2\epsilon/3$.

You might ask why you want the factor of $1/3$ in there at all? Why not just leave it as $1/2$? This point is that there's going to be a sequence of three of these rotations, and you want to bound the final error by $\epsilon$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.