Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states

While the circuit model of quantum computation defines its logical depth or “computational time” in terms of temporal gate sequences, the measurement-based model could allow totally different temporal ordering and parallelization of logical gates. By developing techniques to analyze Pauli measurements on multiqubit hypergraph states generated by the controlled-controlled-Z (ccz) gates, we introduce a deterministic scheme of universal measurement-based computation. In contrast to the cluster-state scheme where the Clifford gates are parallelizable, our scheme enjoys massive parallelization of ccz and swap gates, so that the computational depth grows with the number of global applications of Hadamard gates, or, in other words, with the number of changing computational bases. A logarithmic-depth implementation of an $N$-times controlled-Z gate illustrates a trade-off between space and time complexity.

Figure 1

Any quantum computation can be described as alternative applications of logical ccz and Hadamard gates. Our MBQC scheme allows a parallelization of all logical ccz (namely, ${\text{ccz}}^{nn}$ and swap) gates and each Hadamard layer increments computational depth, as it requires adaptation of measurement bases to correct prior by-products.

Figure 2

(a) Denoting the four-qubit hypergraph state with hyperedges $E=\left\{\right\{1,2,4\},\{2,3,4\},\{1,3,4\left\}\right\}$ with the vertex and the box. (b) Pauli-$X$ measurements on vertices 1, 2, and 3 by Pauli-$X$ measurement on the box.

Figure 3

Pauli-$X$ measurements on the given hypergraph states result in graph states, with a Hadamard gate applied to its vertex 5. All dashed lines (depicting by-products) appear additionally if the product of measurement outcomes on vertices 1, 2, and 3 is $-1$. (a) Pauli-$Z$ by-product. (b) Pauli-$Z$ and cz by-products.

Figure 4

(a) The universal resource state composed of elements on Figs. 3 and 3. (b) Resource state obtained after measuring all boxes in Pauli-$X$ bases, except the ones attached to three qubits surrounded by a hyperedge. All dashed circles represent Pauli-$Z$ by-products.

Figure 5

A nearest-neighbor ccz gate is implemented up to $\{Z,\text{cz}\}$ by-products. See Appendix pp2 for details.

Figure 6

A deterministic graph state to implement swap and H gates, and correction steps. (a) Gets rid of hyperedges entirely and projects on the graph state with Pauli-$Z$ and cz by-products depicted by dashed lines in (b). The hexagonal lattice (d) is obtained deterministically after measuring colored vertices in suitable Pauli bases on (c).

Figure 7

The circuit identity to create a ${\text{c}}^6\text{z}$ gate using ${\text{ccz}}^{nn}$, swap, and Hadamard gates.

Figure 8

The circuit identity implementing the ${\text{c}}^{12}\text{z}$ gate. Here the middle ${\text{c}}^6\text{z}$ gate was created with the circuit in Fig. 7. The procedure can be iterated to the general ${\text{c}}^N\text{z}$ gate.

Figure 9

The five-qubit three-uniform hypergraph state [56] is the smallest hypergraph state with no usual graph edges which can project on a Bell state deterministically. It has hyperedges $E=\left\{\right\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{2,3,4\},\{2,3,5\left\}\right\}$. Qubits 1, 2, and 3 are measured in the $X$ basis and the postmeasurement state is a graph state with a Hadamard correction on vertex 4. The graph state is obtained with unit probability but up to a Pauli-$Z_4$ by-product. The probabilistic Pauli-$Z_4$ is denoted by the dotted circle and it appears with the probability $4/5$ when the product of Pauli-$X$ measurement outcomes is $-1$.

Figure 10

Implementing the ${\text{ccz}}^{nn}$ gate. All measurements are made simultaneously. We present them step by step to emphasize how cz by-products come into the computational scheme. Step 1: The Pauli-$Z$ measurement on the box removes the box and introduces Pauli-$Z$ by-products on vertices 1, 2, and 3. Step 2: Vertex 4 is measured in the $X$ basis projecting on the state at step 3. Step 3: We see the ${\text{cz}}_{23}$ by-product depending on the outcome of the measurement on vertex 4. Measuring vertex 1 in Pauli-$Z$ projects on the hypergraph at step 4. Step 4: Repeating the measurements for vertices 2, 3, 5, and 6 gives the state at step 5.

Figure 11

(a) Circuit for ${\text{c}}^6\text{z}$ gate using long-ranged ccz gates. (b) Implementation swap gate: uses nine cz gates (brown edges) and eight ancilla qubits.

Figure 12

(a) The 55-qubit graph state given in Ref. [26], which can implement three-qubit phase gates. Six gray vertices are for input-output, seven dark purple vertices are measured in the second round of measurement, and the rest are measured in the Pauli-$X$ basis in the first round and the vertices which are already removed are measured in the Pauli-$Z$ basis. (b) The seven-qubit graph state obtained after Pauli measurements in (a) capable of implementing a three-qubit phase gate [26, 57].