Two new papers in Phys Rev E address quantum (computing) chaos for very different purposes. I haven't yet had time to digest them thoroughly, but thought others might be interested.
The first one (PRE 74, 035203) analyzes Shor's algorithm and is heavy on the math and jargon, but if I understand it right, implies that the states necessary for Shor demonstrate chaos, i.e. are sensitive to small perturbations. This would, I think, be bad news for Shor. They simplify the algorithm to the point that they treat the modular exponentiation as a single step, and the QFT as a single step, which of course is not very representative of the way the algorithm will really be run (I believe), but that doesn't mean that their analysis is necessarily off base. I've discussed this issue of real-world perturbations and Shor's alogithm with a number of people in the last couple of years, and I'm not completely satisfied with the answer yet. Probably I'm just being dense, or my intuition is off somewhere, but in my opinion, there is still work to do here, and this paper comes at the problem from a different angle.
The second paper (PRE 74, 026208) analyzes the all-silicon NMR quantum computer being developed by the Yamamoto group at Stanford and the Itoh group at Keio (see PRL 89, 017901 and a whole string of papers both earlier and later). The paper appears to be good news, saying that the strong magnetic fields help suppress chaos. (Disclaimer: I work with the Keio and Stanford people.)
I don't see why the first paper should be any obstacle to Shor's algorithm. There are lots of reasons for this, but one of the most obvious is that the statement of Shor's iterate being quantum chaotic is a statement about what happens upon repeated application of the unitary (the idea is that the classical limit, whatever the heck that is for Shor's iterate, the resulting classical system is chaotic.) Note that sensitivity to initial conditions cannot be used as a signature for quantum chaos due to the linearity of quantum theory. Instead what people look at is typically senstivity to changing the dynamics. But again, even if a small perturbation of this dynamics grows uncountrallably, we're not applying Shor's interate multiple times.
ReplyDeleteI also suspect that defining the classical limit of the Shor iterate is full of all sorts of trouble (there are definitely multiple path contributing to the interference and I don't see how to get a sensible classical limit here.)
Also note that the classical limit (should it exist) is exactly where we don't really care about the algorithm.
ReplyDelete