# About 2D graph state and branching MERA

In my former post I asked if a 2D graph state on a 2D lattice can be represented by branching MERA. I got an answer that it seems this is true.

Then I have to following deductions

(1) 2D graph state on a 2D lattice is universal for measurement based quantum computation, so that all quantum computations can be achieved by a 2D graph state with local measurements.

(2) Branching MERA state can be classically simulated in the meaning that local observables on such a state can be computed efficiently.

(3) If (1)(2) are true, then the local measurement on the 2D graph state can be classically simulated.

(4) From (1)(2)(3), it seems that all quantum computations can be classically simulated.

This of course not true. What's wrong with my deduction?

• Could you please devise the simulation algorithm you mention in (3)? – Norbert Schuch Oct 29 '18 at 10:14
• A local measurement is a function on the local density matrix. To compute the local observables on a branching MERA state, we must at least have the capability to compute the local density matrix. So (2) means that local density matrix can be computed efficiently. If the local density matrix can be efficiently computed, then the local measurement can be classically computed. Something wrong here? – XXDD Oct 29 '18 at 10:19

## 1 Answer

While local measurements in MERA can be efficiently simulated, this is not true for sequences of measurements, such as required for measurement based quantum computation (where the outcome of the computation is in the correlation between the measurement results).

Thus, there is no contradiction.

• Maybe your are right. But if I measure a single qubit of the graph state, and I can simulate the result of this measurement classically, will this measurement affect the measurement on other qubits? I think the answer should be No. After the measurement on a single qubit, this qubit is not physically correlated/connected with the remaining qubits in the graph state any more. So all the measurements on every qubit should be computed classically. Then all the (sequential) measurements can be simulated. Something wrong here? – XXDD Oct 29 '18 at 12:24
• As far as I can understand, if a state can be classically simulated depends on the entanglement and complexity (not sure their relationship). For measurement based quantum computation, the only operation is the measurements on each qubit, and measurement will decrease both entanglement and complexity (right?). So with the MQC, the system will get more and more simpler. If the initial graph state can be classically simulated, why not the following simpler states? Maybe I have a misunderstanding again here, please correct me. – XXDD Oct 29 '18 at 12:42
• @XXDD Why don't you ask a new question on that? – Norbert Schuch Oct 29 '18 at 13:30
• Dear Norbert, for me what I explained above is part of my question. My point is that there seems to be a contradiction in the classical simulation of 2D graph states and the MQC. This is just a component of the deduction chain. Do you mean I should take the classical simulation of the serial measurements on 2D graph states as a new question? – XXDD Oct 29 '18 at 13:57
• will this measurement affect the measurement on other qubits? I think the answer should be No. -- This is wrong. Each measurement by itself is fully random. – Norbert Schuch Oct 29 '18 at 15:33