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
    $\begingroup$ 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. $\endgroup$ Sep 15, 2016 at 7:09
  • $\begingroup$ I will check their paper. $\endgroup$ Sep 15, 2016 at 7:47
  • 4
    $\begingroup$ @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$. $\endgroup$ Nov 19, 2016 at 22:37


Your Answer

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