Simulating depth-2 circuits

Question

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.

Answer 1

You say you understand the first step where two-qubit unitaries just convert the single-qubit states into lots of sets of two-qubit states. Good.

Now, you should also work backwards, from the end of the circuit. The rest of the circuit is another layer of two-qubit unitaries followed by single-qubit measurements. Well, you can change that by incorporating the two together. (For example, Hadamard followed by Z-measurement is the same as X-measurement.) So, those change into two-qubit measurements because, by the same argument as the forward reasoning, the single-qubit states that are projected on are converted into sets of two-qubit states.

The only issue is how to combine the two-qubit states we've produced with two-qubit measurements. Of course, if any two-qubit states and two-qubit measurements match up perfectly, we can take those out straight away and calculate the probabilities of the different outcomes. So, now imagine what happens if you've got two-qubit states on pairs of qubits $(1,2)$ and $(3,4)$, but we want to do a measurement on qubits $(2,3)$. Well, we write down the 4-qubit state across $(1,2,3,4)$ and apply the measurement. Whatever the outcome (of which there are 4, you you can calculate their probabilities), just pick one, and the output state is a pair of qubits $(1,4)$. Now repeat. For example, you might have another entangled state on qubits $(5,6)$, and want to perform a measurement on $(4,5)$. So, this is exactly the same scenario, which we just repeat the same calculation. Eventually, we've done all the calculations.

While it's not exactly the same, you may also be interested to read the section "Linearly assembled quantum states can be efficiently simulated on a classical computer" in this paper, which is where I learned about similar ideas.

In terms of what happens if you add something to the depth of the circuit, well think about trying to take into account two layers of unitaries on the initial state. The first layer makes two-qubit states as before. The second layer might then combine them together. It could combine all of them together (consider, for example, a set of qubits arranged along a line, each in the $|+\rangle$ state. You first perform controlled-phase gates between pairs $(2n-1,2n)$. Then you perform controlled-phase gates between pairs $(2n,2n+1)$ in the second layer. This state is completely entangled; there is no separability. So the described strategy cannot work (although that doesn't rule out other simulation strategies).

Answer 2

DaftWullie's answer outlines the idea pretty well, so I wanted to provide some more specifics on the fundamental gadget he describes and lay it out a bit more methodically.

Once the first step is performed, there exists a quantum state that is distributed over a set of qubits where qubits are at most pairwise entangled. If we now consider simulating the application of an arbitrary set of two and one qubit measurements to this state, then there are six different cases:

1. A single-qubit measurement on a single non-entangled qubit.
2. A single-qubit measurement on one qubit of a two-qubit entangled state.
3. A two-qubit measurement on two disentangled qubits, both of which are non-entangled qubits.
4. A two-qubit measurement on an entangled pair of qubits.
5. A two-qubit measurement on two disentangled qubits, where only one is part of two-qubit entangled state.
6. A two-qubit measurement on two disentangled qubits, where both are part of two separate two-qubit entangled states.

For 1, it is easy to see that this is classically simulable, since there are only two probabilities to calculate. Once these are calculated, the target qubit is no longer relevant and may be ignored by the simulation.

For 2, there are similarly only two probabilities to calculate, except this time, the measurement leaves a single qubit, which may be part of another measurement that can be part of a future instance of cases 1, 3, or 5.

For 3 and 4, since only four states are needed to span a two-qubit measurement basis, there are only four possible probabilities to calculate, regardless of whether the state is entangled or not. Similarly to 1, once these probabilities are calculated, both qubits may be ignored.

For 5, again, only four probabilities need be calculated, but this time, after the measurement, a single qubit remains, which similarly can be part of a future instance of cases 1, 3, or 5.

For 6, we also have four probabilities that need calculating, except now we have the case that the state which exists on the two remaining qubits which are not part of the measurement. This phenomena is known as "entanglement swapping". Hence, in the simulation, we apply the measurement and create a two-qubit entangled state that can then be part of a future instance of cases 2, 4, or 6.

So the algorithm goes as follows:

1. Apply the first stage, creating a state with at most pairwise entanglement.
2. For each two- or single-qubit measurement in the second stage, extract the desired measurement outcome probabilities and sample any output state accordingly. Because you never create a state which cannot be later simulated efficiently, this process can be repeated until you have performed all measurements.
3. Any unmeasured qubits are simply discarded.

Adding a third layer breaks this because now it is possible to create a state which is more than pair-wise entangled on which universal quantum computation can be performed. To see this, observe that such a protocol is equivalent to three stages of pairwise entanglement followed by a round of single-qubit measurements. It can then be seen that three such entangling stages are sufficient to produce the trivalent hexagonal cluster state lattice, a state which is universal for measurement-based quantum computation [1] (along with single-qubit measurements and classical communications). Once we have such a state, the final stage could then be used to perform a universal measurement-based quantum computation. Hence, if it were possible to simulate such states efficiently, we would be able to simulate quantum computers efficiently as well, which we do not expect to be true.

[1] Van den Nest, Maarten, et al. "Universal resources for measurement-based quantum computation." Physical review letters 97.15 (2006): 150504. Link here.