Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi.

In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have countably many quantum Turing machine.

Is this choice of angle arbitrary?

  • 7
    N.B. $53.15^\circ \approx \arcsin (4/5) $. Restricting to rational amplitudes with a denominator of 5 is an old convention from the early days of quantum computing, dating back at least to Bernstein and Vazirani, for those who are looking for a special case to make comparisons between quantum complexity and counting complexity. – Niel de Beaudrap Sep 15 '16 at 7:09
  • I will check their paper. – Omar Shehab Sep 15 '16 at 7:47
  • 4
    @Niel: I am fairly sure that Bernstein and Vazirani were the first ones to use arcsin(4/5). And if it's not already clear from Niel's comment, $4/5$ is chosen because $3^2 + 4^2 = 5^2$. – Peter Shor Nov 19 '16 at 22:37

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.