Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond

Details Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond

2008-11-06

arxiv.org/abs/0811.0898v2

Quant. Inf. Comp. 10, 3-4 pp. pp0258-0271 (2010)

Physics

Quantum Physics

14 pages, shortened version, one additional result. To appear in Quant. Inf. Comp

Scientific paper

We study classical simulation of quantum computation, taking the Gottesman-Knill theorem as a starting point. We show how each Clifford circuit can be reduced to an equivalent, manifestly simulatable circuit (normal form). This provides a simple proof of the Gottesman-Knill theorem without resorting to stabilizer techniques. The normal form highlights why Clifford circuits have such limited computational power in spite of their high entangling power. At the same time, the normal form shows how the classical simulation of Clifford circuits fits into the standard way of embedding classical computation into the quantum circuit model. This leads to simple extensions of Clifford circuits which are classically simulatable. These circuits can be efficiently simulated by classical sampling ('weak simulation') even though the problem of exactly computing the outcomes of measurements for these circuits ('strong simulation') is proved to be #P-complete--thus showing that there is a separation between weak and strong classical simulation of quantum computation.

Affiliated with

Also associated with

No associations

Rating

Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-630443