Distributed Quantum Error Correction
Rodney Van MeterEnvironment and Information Studies, Keio University, and National Institute of Informatics, Japan ∗Jacob M. Taylor
Department of Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA

Liang Jiang
Department of Physics, Harvard University, Cambridge, MA 02138, USA(Dated: September 30, 2007)
The recent discovery of the use of operator subspaces as a generalization of stabilizers for quantum
error correction (QEC) has provided a more flexible framework for the implementation of QEC.
We have analyzed implementation of one such code, the Bacon-Shor code, in a two-dimensional
memory layout where operations on one axis are substantially more expensive and error-prone thaton the other, such as node-local versus inter-node operations in a distributed system. By favoringstabilizers that use local operations, rather than long-distance operations, we solve a key problem
in the implementation of a quantum multicomputer with code words spanning multiple nodes. We
also show efficient distributed creation of the cat states necessary for syndrome calculation. This
work improves the prospects for the use of very small nodes, holding only a few physical qubits each.
PACS numbers:

Hardware systems that can cleanly scale the numberof physical qubits in a single system are hard to build [1].
Thus, we have been investigating quantum multicomputerarchitectures, in which a set of quantum computers areconnected via quantum channels into a system that cansolve problems that are beyond the reach of any individual quantum computer [2].
In prior work on fault tolerance in multicomputerarchitectures, Van Meter et al. showed that Steane’s
method of measuring syndromes, which uses logical zerostates, is not well suited to quantum error correction on
distributed code words, and argued that individual multicomputer nodes therefore should contain complete logical qubits [3]. Logical gates are performed by teleporting complete logical qubits, then performing the gates
locally. Jiang et al. explored minimum-size nodes, using purification to insure the quality of distributed Bellpairs; each node effectively holds a single data qubit and afew ancillae [4]. The inter-node interconnect is treated as
the first-level qubit-to-qubit interconnect, for purposes ofcalculating an error threshold and planning logical operations. The system proposed by Oi et al. falls in between,holding a single, first-level logical qubit in each node [5].
The logical qubits do not move, and distributed zeros
built on ancillae are used to execute two-qubit gates.
Operator subspaces relax some of the constraints on
quantum error correction codes by recognizing that manyerrors that can occur do not impact our ability to continue to use a particular state for quantum computation [6, 7]. Aliferis and Cross have shown that a qubit
encoded in the Shor nine-bit code can be protected using∗ Electronic address: rdv@sfc.wide.ad.jp

only nearest-neighbor interactions on a 2D lattice andgauge bits along the edges of the lattice [8].
However, when using a multicomputer architecture,
the qubit-to-qubit interconnect is not fully symmetric:
interactions within a node are generally direct qubit-toqubit actions, governed by the node’s internal topology
and technology, but interactions between nodes are very
difficult, typically mediated by Bell pairs and teleportation operations. Our question then becomes how to lay
out the qubits to minimize the number of high-fidelity
Bell pairs that must be created using the inter-node interconnect.
We find that the standard stabilizer set for a generalized Bacon-Shor code, of the form [[n2 , 1, n]], works wellin a multicomputer, when cat states and Shor’s fault
tolerance method are used instead of logical zeros andSteane’s method. A particularly elegant approach becomes apparent for n multicomputer nodes holding a single logical qubit. Then, only O(n) distributed Bell pairs
are necessary for fault tolerant syndrome extraction anderror correction.
Writing stabilizers as a matrix with the jth column
corresponding to qubits in the jth node of the multicomputer, we usex
Sij= Xi,j Xi+1,j Sjz =nYZi,j Zi,j+1

(1)

i=1

That is, paired pauli X operators within a given node,and two columns of Z operators between adjacent nodes,x
as illustrated in Fig. 1a. Measurement of Sijis trivial
with good internal node operations. Our task is thenreduced to efficient measurement of the n − 1 pairedcolumn stabilizers, Sjz .
For this Pauli operator on 2n qubits, we will use
Shor-type syndrome extraction. This operation requires

2(a)Sx2,3=(b) AI
II
I
..

I
I
I
I
..

IX
X
I..

II
I
I
..

..
..
..
..
..

Sz2=I
I
I
I
..

Z
Z
Z
Z
..

Z
Z
Z
Z
..

..
..
..
..
..

I
I
I
I
..

A1
1A2

PBM

≡ |φ+ 〉ZZ

PBM
A2(c)|0000〉+|1111〉

PBM
PBM|00000000〉+|11111111〉
or|0000〉+|1111〉

PBM
PBM|00001111〉+|11110000〉

FIG. 1: (a) Stabilizers for a [[n2 , 1, n]] Bacon-Shor code, distributed between different multicomputer nodes (separation
indicated by the dashed lines). (b) A partial Bell measurement (PBM) circuit using one entangled Bell pair, with result±1 given by the product of the Z measurement results. (c)Fault tolerant “patching” of two 4-qubit cat states. The result
is kept only when both PBM measurements give the same result. For PBM results of 1,1, we get the top GHZ state, while-1,-1, gives the bottom.

preparing a 2n GHZ state of an ancillary system, followedby pairwise controlled-not operation and measurement ofthe ancillae. In a given node, we need n qubits for thecode word, n qubits for the cat state, and one additional
qubit for verification and entanglement generation.
Fault tolerance is achieved if this procedure does notamplify errors: no single bit error, occurring with probability p, can produce a two-bit errors on the code-word
qubits. We choose a recursive approach to proving fault
tolerance, using ancilla-mediated partial Bell measurements to verify the cat state against errors. In essence,
we can fault tolerantly “patch” two n cat states together
to a single cat state of size 2n. This operation requires
two partial Bell measurements (sequential or simultaneous), necessitating two Bell pairs be consumed for each
2n cat state needed.
Let us define the partial Bell measurement (PBM),
which will account for the entangling operations necessary to “patch” two cat states together. The idea of[1] Rodney Van Meter and Mark Oskin. Architectural implications of quantum computing technologies. ACM Journal

PBM is to projectively measure two qubits (one in eachsmaller cat) in two orthogonal subspaces: one subspace√is spanned by the Bell states |Φ± i = (|00i ± |11i) / 2,and the other√ is spanned by the Bell states |Ψ± i =(|01i ± |10i) / 2.

We can achieve PBM by entanglement generation andlocal operations. For distributed nodes (registers), we
implement PBM via the following procedure (shown inFig. 1b): (1) Prepare a high fidelity EPR pair sharedby the communication qubits from the two nodes, say|Φ+ iC1 ,C2 . (2) Then apply local CNOT gate. (3) The twostorage qubits (S1 and S2 ) are projected to the subspace√spanned by the Bell states |Φ± i = (|00i ± |11i) / 2 if
the measurement outcomes are the same, or they are
projected to the subspacespanned by the Bell states√|Ψ± i = (|01i ± |10i) / 2 if the measurement outcomesare different. (4) (Optional) For the latter case, we may
further flip one of the storage qubits, so that they are
projected to the subspace spanned by |Φ± i.

More specifically, we assume we have fault tolerantly
prepared two cat states of size n/2, spanned by |0̄i ≡|000 · · · i and |1̄i ≡ |111 · · · i. Suppose we start with twosuch blocks, prepared in |0̄i1 + |1̄i1 and |0̄i2 + |1̄i2 states,respectively (i.e., two small GHZ/cat states). Each blockis associated with a communication qubit for entanglement generation. We want to prepare a large GHZ state|0̄i1 |0̄i2 + |1̄i1 |1̄i2 fault tolerantly. We may achieve thistask by applying PBM twices as shown in Fig. 1c. The
fault-tolerance comes from the second (redundant) PBM.
Each PBM will indicate whether the upper qubits havethe same value as the lower ones. The indications fromtwo PBMs should be the same; otherwise there must be
something wrong. There are several sources that can leadto the inconsistency: (1) There is a bit error in one of thephysical qubits connect to the PBM. (2) The EPR pair
|Φ+ iC1 ,C2 for one PBM has a bit-flip error. (3) The measurement of the communication qubit within the PBM
has a mistake. If one of the above error occurs, it will
be detected by our double-PBM operation (Fig. 1c) [9].
The possibility for these errors to induce correlated errors in the large GHZ state is suppressed to the second
order by the circuit.

This specific example illustrates our approach for minimizing the number of Bell pairs necessary between separated nodes in a quantum multicomputer. Generalizations of this approach to non-degenerate quantum codesand concatenated codes remains an outstanding problem.
Acknowledgments. The authors thank MEXT for partial support for this research, and Kae Nemoto, Bill
Munro, Thaddeus D. Ladd, and Austin Fowler for technical guidance. Funding for JMT is provided by the Pappalardo Fellowship at MIT.

of Emerging Technologies in Computing Systems, 2(1):31–363, January 2006.
[2] Rodney Van Meter, W. J. Munro, Kae Nemoto, and Kohei M. Itoh. Arithmetic on a distributed-memory quantum multicomputer. ACM Journal of Emerging Technologies in Computing Systems, 2007. to appear; available asarXiv:quant-ph/0607160v2.
[3] Rodney Van Meter, Kae Nemoto, and W. J. Munro. Communication links for distributed quantum computation.
IEEE Transactions on Computers, 2007. to appear; available as http://arxiv.org/quant-ph/0701043.
[4] L. Jiang, J. M. Taylor, A. S. Sorensen, and M. D. Lukin.
Scalable quantum networks based on few-qubit registers.
quant-ph/0703029, 2007.
[5] Daniel K. L. Oi, Simon J. Devitt, and Lloyd C. L. Hollenberg. Scalable error correction in distributed ion trapcomputers. Physical Review A, 74:052313, 2006.
[6] D. Bacon. Operator quantum error-correcting subsystems
for self-correcting quantum memories. Physical Review A,73(1):12340, 2006.
[7] Dave Bacon and Andrea Casaccino. Quantum error correcting subsystem codes from two classical linear codes.
quant-ph/0610088, October 2006.
[8] Panos Aliferis and Andrew W. Cross. Subsystem fault
tolerance with the Bacon-Shor code. Physical Review
Letters, 98(22):220502, May 2007. arXiv version quantph/0610063 includes extensive, helpful appendix.
[9] We apply the double-PBM operation on different physical qubits, rather than repeating the PBM twice with thesame physical qubits. This helps to suppress the type (1)error to the second order.