# The classical simulation of 2D graph state and the measurement based quantum computation

In my former post on Physics SE I deduced a contradiction in the classical simulation of 2D graph state and the classical simulation of general measurement-based quantum computation.

In Norbert's answer, he mentioned that the serial measurements on the graph state cannot be classically simulated.

This might be the right answer if we admit that a general quantum computation cannot be efficiently simulated classically. Especially if the quantum computation is not measurement based but rather a normal quantum circuit based implementation, since even the initial state can be simulated classically, the evolution of the state may change the state and the entanglement pattern so that it does not fulfill a certain criterion for the classical simulation.

But for measurement based QC, the measurement is carried out on each individual qubit and the measurement on one qubit will not change the state of another qubit. So the sequential measurements on each qubit can all be classically simulated. Then the contradiction is still there.

I am sure there must be something wrong with my deduction. Please help me to find it.

the measurement is carried out on each individual qubit and the measurement on one qubit will not change the state of another qubit

This is an incorrect statement. If the state that you are measuring is entangled (which it very much is for the 2D cluster state), measuring the state of one qubit absolutely changes the state of another qubit. The trivial example of this is teleportation.

• In teleportation, the measurement on AB does not change the density matrix of C. I think only when we know the specific measurement result, the state of C is changed. But if we carry out a measurement on AB and another measurement on C, the sequence of which measurement is carried out first will not change the measurement results.
– XXDD
Oct 29 '18 at 16:01
• @XXDD Yes, but the measurement results have to be globally consistent. For example, if you measure the two qubits in $|01\rangle-|10\rangle$ in the same basis,, you must get opposite answers. Oct 29 '18 at 16:03
• so, the point is, that if you're doing a classical simulation, and performing measurement on one qubit, you need a record of the measurement outcome, and what the corresponding state is on other qubits. It's not enough to just forget what the measurement outcome is and give an average state on other qubits (the density matrix, which I agree is unchanged) Oct 29 '18 at 16:04
• Ah, yes, you are right. So the entanglement in the graph state is a kind of global pattern and the local simulation on observables can not fully explore the state structure. Right?
– XXDD
Oct 29 '18 at 16:06
• So from this point of view, the so called 'classical simulation of branching MERA state' or even the simulation of normal MERA states is not exactly strict since they can not explore the global correlation, right? Is this essentially due to the complex entanglement pattern in these states?
– XXDD
Oct 29 '18 at 16:10