Quantum depth-2 circuits can be efficiently simulated classically, as shown in Proposition 2 of this paper. The following is a quote of the proof.

After the first time step the quantum state of the circuit consists of a set of 2-qubit entangled states and possibly some 1-qubit states and thus the amplitudes of this state can be efficiently represented classically. We may consider the second computing step and the final measurement step as one single step in which a set of final measurements are performed in arbitrary 2-qubit bases. We pick a first measurement. It is simple to calculate the probabilities for the various outcomes since they depend on the state of no more than four qubits. We flip coins according to the outcome probabilities and fix the outcome. We replace the 4-qubit state by the post-measurement projected state consisting now of 2 qubits. We pick the next measurement and proceed similarly etc. If only a subset of these measured bits are required as output, the rest are simply discarded.

I don't understand the proof. I get how the first time step can be efficiently simulated as it only consists of disjoint one/two qubit gates.

But what about the second time-step? Why do the measurement outcomes depend on no more than four qubits? Why is it efficient to classically simulate measurement by an arbitrary two qubit basis? I'm not sure how we can simulate the conditional probabilities by putting in the projectors.

The authors also remark that adding another layer will break this simulation protocol. I’m not sure why that is the case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.