Is this generalized 2D cluster state still a universal resource?

Question

Let $G = (V,E)$ be a graph that defines the graph state $$ |G\rangle = \prod_{(i,j)\in E} CZ_{i,j}|+\rangle^{\otimes |V|}. $$ Alternatively, we can write $$ | G \rangle = \sum_{x \in \{0,1\}^{|V|}} f_G(x)|x\rangle, $$ for some function $f_G$ that can be determined by expanding the definition of $|G\rangle$.

In the case where $G$ is a 2d lattice graph, then $|G\rangle$ is a cluster state, and $|G\rangle$ is also a universal resource for measurement-based quantum computing. Thus, with post-selection, one can simulate any BQP circuit.

My question is the following. Let $G$ be a 2d lattice graph and consider the state $$ | G' \rangle = \sum_{x \in \{0,1\}^{|V|}} f_G(x)|x\rangle \otimes | x\rangle. $$ Is this universal for MBQC? What if I restrict to post-selecting on only the upper $|V|$ registers?

Answer 1

TLDR: Yes, it's universal. If you only measure on one of the two registers, No.

Longer answer...

Let's deal with the measuring just one register first. So we're doing nothing with the other register. So we should trace it out. Once you've traced it out, you're left with the maximally mixed state on the register you're going to measure. The outcomes of measurements on a maximally mixed state can be classically sampled, so as much as we believe the quantum computers can do something that classical computers cannot, we believe that the maximally mixed state is not a universal resource for MBQC. (After all, it's separable!)

As for whether the whole state is universal, think about describing how it's built:

1. prepare all qubits in the $|0\rangle$ state
2. take one register, and apply Hadamards on every qubit. Now we have $\sum_x|x\rangle|0\rangle$.
3. Apply controlled nots controlled off each qubit of the first register targeting the equivalent qubit in the second register. This produces $\sum_x|x\rangle|x\rangle$
4. Now apply the controlled-phase gates on the first register along the edges of the graph.

Now, let me rewrite step 3: Apply Hadamards on all the qubits of the second register, apply controlled-phases between the two registers (where the cNOTs were before), and apply Hadamards on all qubits of the second register.

So, if we neglect the very last round of Hadamards, we have a graph state which includes the universal 2D grid as a subgraph. So universal MBQC is certainly possible. The addition of Hadamards on some qubits just alters the measurement basis that you have to use.