From Robin Houston, University of Manchester
I enjoyed your cover story about “quantum knots” and its enthusiastic engagement with an interesting and often difficult subject (24 January, p 30). It is a shame that some of the central facts were garbled.
Paul Parsons asserts that a quantum computer could be used to perform NP-hard computations quickly. That is wrong. The situation here is complicated by the fact that we don’t even know whether conventional computers can perform NP-hard computations quickly – this is the famous “P = NP” problem – but there is no good evidence that a quantum computer would fare any better than a classical one in this regard.
Parsons also seems to believe that finding the factors of large numbers is an NP-hard problem. That is not true either – or rather, it isn’t known to be true and is widely suspected not to be. The problem of calculating the Jones polynomial of a knot is NP-hard; in fact it is “#P-hard”, which is even worse – but even a topological quantum computer cannot calculate the exact value of the Jones polynomial, so it doesn’t follow that such a computer could solve NP-hard problems.
Manchester, UK
