home | literature reviews

"Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups", Maarten Van den Nest, 2012

Reviewed August 17, 2023

Citation: Nest, M. "Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups." arXiv preprint arXiv:1201.4867 (2012).

Web: https://arxiv.org/abs/1201.4867

Tags: Abelian-anyons, Computer-scientific, No-go

This paper introduces a generalization of the qudit formalism to general abelian groups. A generalization of the Gottesman-Knill theorem is demonstrated.

This paper demonstrates a lot of things about this general group-theoretical model, which seems to be very applicable to abelian anyons.

The author, clearly, does not have a very good idea about how this work fits into the wider literature yet. Namely, much of what he considers "new" in this work is already shown in the qudit case, which was settled at least a year earlier:

> De Beaudrap, Niel. "A linearized stabilizer formalism for systems of finite dimension." arXiv preprint arXiv:1102.3354 (2011).

The author is very confused about how a model which contains the quantum fourier transform can be efficiently classically simulated: "In particular the usual superficial arguments that the power of quantum factoring comes from entanglement, interference or other 'quantumness' measures, seem to apply equally well to normalizer circuits. Probably this indicates that such arguments have little merit and that much more delicate considerations are necessary"

I'd argue that those superficial arguments DO have merit. The implicit assumption of those arguments is that you have sufficient control over your quantum system. In normalizer circuits you have powerful quantum gates available, but you have frustratingly little control over individual qubits. In particular, over Zn it becomes easy to make big superpositions over all computational basis states, but it is hard to superpose over just two or three states. This lack of fine control makes it impossible to implement algorithms like factoring.

It seems like the author figured this out in later works.