Do multi-qubit measurements make a difference in quantum circuits?

Question

Consider the unitary circuit model of quantum computation. If we need to generate entanglement between the input qubits with the circuit, it must have multi-qubit gates such as CNOT, as entanglement cannot increase under local operations and classical communication. Consequently, we can say that quantum computing with multi-qubit gates is inherently different from quantum computing with just local gates. But what about measurements?

Does including simultaneous measurements of multiple qubits make a difference in quantum computing or can we perhaps emulate this with local measurements with some overhead? EDIT: by "emulate with local measurements", I mean have the same effect with local measurements + any unitary gates.

Please notice that I am not merely asking how measuring one qubit changes the others, which has already been asked and answered, or if such measurements are possible. I am interested to know whether including such measurements could bring something new to the table.

Answer 1

Entangling measurements are powerful. In fact, they are so powerful that universal quantum computation can be performed by sequences of entangling measurements only (i.e., without extra need for unitary gates or special input state preparations):

1. Nielsen showed that universal quantum computation is possible given a quantum memory and the ability to perform projective measurements on up to 4-qubits [quant-ph/0310189].

2. The above result was extended to 3-qubit measurements by Fenner and Zhang [quant-ph/0111077].

3. Later on, Leung gave an improved method that requires only 2-qubit measurements, which are also both sufficient and necessary [quant-ph/0111122].

The idea there is to combine sequences of measurements to drive the computation. This is quite similar to Raussendorf-Briegel's model of measurement based quantum computation (MBQC) (aka the one way quantum computer), but in standard MBQC you also restrict your measurements to be non-entangling (i.e., they must act on single qubits) and you start with an entangled resource state as input (canonically, a cluster state [Phys. Rev. Lett. 86, 5188, quant-ph/0301052]). In the afore-mentioned protocols by Nielsen, Fenner-Zhang, Leung you are allowed to do entangling measurements but you do not rely on any other additional resource (i.e., no gates, no special inputs such as cluster states).

In short, the difference between entangling and local measurements is analogous to the difference between entangling and local gates.

---

PS: As discussed in other answers you can simulate entangling measurements with entangling gates (such as CNOTS and local measurements). Viceversa, the above results show you can trade entangling gates for entangling measurements. If your all of your resources are local you cannot use them to simulate entangling ones though. In particular, you cannot simulate entangling measurements with local gates and inputs.

Answer 2

While multi-qubit measurements can be incredibly powerful, as already described elsewhere, they do not give you anything new compared to unitary operations and local measurements. Think of a projective measurement for example, with projectors $P_m$. If you write down the observable $O=\sum_m P_m$, then there will be a unitary $U$ that diagonalises $O$. So, measuring $O$ is equivalent to implementing the unitary $U$ with a normal quantum circuit (including multi-qubit gates), and then performing local measurements in the standard basis.

Alternatively, this gives you some insight about multi-qubit measurements. Any unitary circuit followed by projective measurements could be wrapped up as a single multi-qubit measurement by inverting the above process.

A similar construction can be applied to more general measurements, but you have to extend the unitary operation to include some ancilla qubits. This is sometimes referred to as “the church of the larger Hilbert space”. There's a proof that unitaries + projective measurements are equivalent to generalised measurements in section 2.2.8 of Nielsen & Chuang.