Juan Bermejo-Vega, Maarten Van den Nest
Quantum normalizer circuits were recently introduced as generalizations of Clifford circuits. A normalizer circuit over a finite Abelian group G is composed of the quantum Fourier transform (QFT) over G together with gates which compute quadratic functions and automorphisms. In [arXiv:1201.4867] it was shown that every normalizer circuit can be simulated efficiently classically. This result provides a nontrivial example of a family of quantum circuits that cannot yield exponential speed-ups in spite of usage of the QFT---the latter being a central quantum algorithmic primitive. Here we extend the aforementioned result in several ways. Most importantly, we show that normalizer circuits supplemented with intermediate measurements can also be simulated efficiently classically, even when the computation proceeds adaptively. This yields a generalization of the Gottesman-Knill theorem, valid for qubits, to arbitrary G. Moreover our simulations are twofold, i.e., we show how to classically efficiently sample the measurement probability distributions as well as compute the amplitudes of the state vector. Finally we develop a generalization of the stabilizer formalism relative to arbitrary finite Abelian groups. For example we characterize how to update stabilizers under generalized Pauli measurements and provide a normal form of he amplitudes of generalized stabilizer states using quadratic functions and subgroup cosets.
View original:
http://arxiv.org/abs/1210.3637
No comments:
Post a Comment