Compact quantum circuits from one-way quantum computation

In this paper we address the problem of translating one-way quantum computation (1WQC) into the circuit model. We start by giving a straightforward circuit representation of any 1WQC, at the cost of introducing many ancilla wires. We then propose a set of simple circuit identities that explore the relationship between the entanglement resource and correction structure of a 1WQC, allowing one to obtain equivalent circuits acting on fewer qubits. We conclude with some examples and a discussion of open problems.

Figure 1

Examples of graphs satisfying the conditions of (a) flow [11] and (b) gflow [12]. Black vertices represent qubits to be measured, white vertices represent unmeasured (output) qubits, and input qubits appear in a box. Arrows point from each qubit to be measured $i$ to other vertices $j$, each of which corresponds to an operator $K_j=X_j{\prod }_{n\sim j}{Z}_n$ in the correcting set of $i$. The dashed arrow indicates a correcting stabilizer $K_j$, which is associated with a vertex $j$ not connected to $i$ in the graph.

Figure 2

Extended circuit representation of a measurement and the corrections it requires on other qubits for deterministic computation in the 1WQC model. Note that each correction arises from a particular stabilizer in the correcting set of $i$, raised to the power $s_i$, where $s_i$ is the outcome of measurement $i$. This subcircuit shows only the gates corresponding to the correcting set of qubit $i$.

Figure 3

Extended circuit for a simple one-way quantum computation protocol. This j-gate identity will be used repeatedly to simplify generic extended circuits, as discussed in Sec. 4. Note that the j-gate angles in (a) and (b) differ by a minus sign.

Figure 4

Circuit identities that aid in the process of removing ancillas in an extended circuit corresponding to a 1WQC procedure. These circuit identities are proven in the Appendix.

Figure 5

Removing undesired cz gates. (a) Undesired ${\text{cz}}_{ik}$ in time slice ${\mathcal{C}}_i$ with the corresponding initial entangling-round ${\text{cz}}_{jk}$ in time slice ${\mathcal{E}}_1$. (b) The ${\text{cz}}_{jk}$ gate was moved from ${\mathcal{E}}_1$ to ${\mathcal{C}}_i$, where the circuit identity in Fig. 4a can be applied, resulting in the circuit depicted in (c).

Figure 6

Generic structure of extended circuits obtained from graphs with flow or gflow. See the main text for information about the division into time slices.

Figure 7

Simplifying an extended circuit originated from the entanglement graph with gflow of Fig. 1b. For a step-by-step explanation, see Sec. 4b 1.

Figure 8

Graph with gflow, whose extended circuit we simplify step by step in Sec. 4b 2. Qubits 1, 3, and 5 are the computation's inputs and qubits 2, 4, and 6 are the outputs.

Figure 9

Simplifying the extended circuit originated from the graph in Fig. 8. For a step-by-step explanation, see Sec. 4b2.