See discussions, stats, and author profiles for this publication at: [Link]

net/publication/318207402

Low-Overhead Code Concatenation Approaches for Universal Quantum

Computation

Article in Quantum Information Processing · January 2023

DOI: 10.1007/s11128-023-03829-1

CITATIONS READS
0 134

3 authors, including:

Eesa Nikahd Morteza Saheb Zamani

Shahid Rajaee University Amirkabir University of Technology
10 PUBLICATIONS 69 CITATIONS 130 PUBLICATIONS 1,096 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Eesa Nikahd on 13 July 2017.

The user has requested enhancement of the downloaded file.

 Low-Overhead Code Concatenation Approaches for Universal Quantum Computation

Eesa Nikahd,∗ Morteza Saheb Zamani,† and Mehdi Sedighi‡

Quantum Design Automation Lab
Amirkabir University of Technology, Tehran, Iran
(Dated: July 5, 2017)
As there is no quantum error correction code with universal set of transversal gates, several
approaches have been proposed which, in combination of transversal gates, make universal fault-
tolerant quantum computation possible. Magic state distillation, code switching, code concatenation
and pieceable fault-tolerance are well-known examples of such approaches. However, the overhead
of these approaches is one of the main bottlenecks for large-scale quantum computation. In this
paper, two approaches for universal fault-tolerant quantum computation, mainly based on code
concatenation, are proposed. The proposed approaches outperform code concatenation in terms of
both number of qubits and code distance and has also significantly less resource overhead than code
switching, magic state distillation and pieceable fault-tolerance at the cost of reducing the effective
arXiv:1707.00981v1 [quant-ph] 1 Jul 2017

distance of the concatenated code for implementing non-transversal gates.

I. INTRODUCTION A quantum code can be concatenated recursively to

enhance its capability to correct errors even further. Us-
Quantum computers have the potential to efficiently ing concatenated quantum codes and fault-tolerant pro-
solve certain problems such as integer factorization cedure, as long as the physical gate error is below a
[1] and simulation of quantum systems [2] which are threshold value, it is possible to accomplish almost re-
prohibitively time-consuming using classical comput- liable quantum computation using noisy physical devices
ers. This computational advantage of quantum systems with poly-logarithmic overhead [8].
comes from the unique quantum mechanical properties Transversal implementation of logical gates is widely
such as superposition and entanglement, which have no considered as a simple and efficient method for fault-
classical analogue [3]. tolerant quantum computation (FTQC) [9][10], where
Quantum bits or qubits are the fundamental units a transversal gate refers to a gate which does not cou-
of information in quantum computing. Unfortunately, ple qubits inside a codeword. Unfortunately, there is no
qubits are fragile and tend to lose their information due quantum code with a universal set of transversal gates
to the environmental noise resulting in decoherence [3][4]. [11]. Several approaches have been proposed which, in
Furthermore, the physical implementations of quantum combination with transversal gates, make FTQC possi-
operations in any technology are imperfect [4][5]. Quan- ble. Magic state distillation [12], gauge fixing [13][14],
tum noise, due to decoherency of quantum states and pieceable fault-tolerance [15], code switching [10][16][17]
imperfect quantum operations, is the most important and code concatenation [18][19] are well-known examples
challenge in constructing large-scale quantum computers of such approaches.
[3][6][7]. Magic state distillation (MSD) is a procedure which
The most common approach to cope with this chal- uses only Clifford operations to increase the fidelity of
lenge is the use of quantum error correction codes and non-stabilizer states that can be used to realize non-
fault-tolerant operations to perform quantum computa- Clifford gates. This procedure is orders of magnitude
tion. In this approach, a logical qubit is encoded into more costly than transversal gates and can incur a sig-
multiple physical qubits using a suitable error correction nificant resource overhead for the implementation of a
code. Logical operations are applied directly on the en- quantum computer [18][20].
coded qubits in such a manner that decoding is not re- Gauge fixing is an alternative approach for universal
quired. After that, if a qubit becomes erroneous, that quantum computation without the need for a special an-
qubit can be corrected using repeated application of the cillary state prepared by MSD, using only one quantum
quantum error correction procedure. The logical oper- code. The method proposed by Paetznick and Reichardt
ations can potentially spread errors due to the interac- [13] is a known example of this approach. This method
tions among qubits. Therefore, to preserve the veracity has been described based on the [[15, 7, 3]] quantum
of computation, these operations must be implemented Hamming code as an example. In this code, by consid-
fault-tolerantly in such a way that they do not propa- ering the first logical qubit as data qubit and fixing the
gate errors from a corrupted qubit to multiple qubits in other six logical qubits into the encoded |0⊗6 i state as
a codeword. gauge qubits, CCZ gate will be transversal. Applying
the transversal H gate on all the 15 qubits of the code
performs a logical H to the first logical qubit. However,
∗ nikahd@[Link] as its application corrupts the state of the gauge qubits,
† szamani@[Link] additional error correction and transversal measurements
‡ msedighi@[Link] are needed in order to restore their state into |0⊗6 i after
 2

applying this gate.

Recently, Yoder et al. [15] have proposed a novel
approach to overcome the limits of non-transversality,
namely pieceable fault-tolerance (PFT). In this ap-
proach, a non-transversal circuit is broken into fault-
tolerant pieces with rounds of intermediate error correc-
tion in between to correct errors before they propagate qt
to a set of non-correctable errors. As an example, fault- (a)
tolerant implementation of CCZ was developed for the
7-qubit Steane code. This considerably reduces the re-
source overhead in comparison with MSD. However, this
approach is unable to find a fault-tolerant construction d
LC SC SC† LC†
for non-transversal single-qubit gates, such as T , with-
qt
out additional ancillae. This problem may impose addi-
tional cost when a quantum algorithm such as QFT is
synthesized to a fault-tolerant gate set not containing a
non-Clifford single-qubit gate. k+1 d
LC SC SC† LC†
The code switching method achieves a universal set
of transversal gates by switching between two different qt
quantum codes C1 and C2 where the non-transversal
gates on C1 /C2 have transversal implementations on
C2 /C1 . To this end, a fault-tolerant switching network is
required to convert C1 into C2 and vice versa. A general
d
approach to convert between the codes uses teleporta- LC SC SC† LC†
tion [17][21]. Alternatively, a method has been proposed qt
Z(θ)
by Anderson et al. for direct fault-tolerant conversion
between codes of Reed-Muller code family [10]. More- (b)
over, a method has been recently published in [15] using
pieceably fault-tolerant gates. FIG. 1. Non-transversal application of logical C k Z(θ) gate for
The uniform code concatenation method [18] uses two a stabilizer code [[n, 1, d]] by involving only d qubits of each
different quantum codes, namely C1 and C2 in concate- code block and only one physical C k Z(θ), where d is the code
nation to achieve universal fault tolerance. In this ap- distance [19]. SC is an abbreviation for staircase of CN OT s
proach, a logical qubit is encoded into the code of C1 and and LC is a circuit containing only local Clifford gates. Note
then each qubit of C1 is in turn encoded to the code of that only the active qubits are shown [19].
C2 , where for each non-transversal gate U on C1 , there is
an equivalent transversal implementation on C2 . In our
previous work [19], a method called non-uniform code
concatenation has been proposed which outperforms the
the only possible non-Clifford gate C k Z(θ), which is of-
uniform one. The main idea behind this approach is that
ten the main challenge for fault-tolerant implementation
the non-transversal implementation of gate U does not
of the circuit. In the code concatenation approaches,
necessary involve all of the C1 qubits and it is shown that
both C k Z(θ) and Clifford gates appeared in the circuit
we only need to encode the involved qubits in the second
must be transversal on C2 . Here, two related important
level of concatenation. Although these approaches elimi-
questions are arisen: ”Instead of using two codes C1 and
nate the need for magic state distillation, the number of
C2 with a complementary set of transversal gates, is it
necessary physical qubits to code the logical information
possible to use a more efficient code C20 than C2 in the sec-
is large. Moreover, for the non-transversal gates on C1
ond level of concatenation with possibly non-transversal
as well as the non-transversal gates on C2 , the overall
implementation for C k Z(θ) and exploit other methods
distance of the concatenated code is sacrificed.
to complete the fault-tolerant gate set on C20 ?” or ”Is
The main motivation of the proposed approaches in
it possible to encode only the target qubit of C k Z(θ)
this paper has been arisen from the following. In [19] it
of each codeword, e.g. qt , using a code with transver-
is shown that:
sal C k Z(θ) and encode the rest of active qubits using
Theorem 1. For a stabilizer code [[n, 1, d]], a logical a more efficient code with possibly non-transversal im-
C k Z(θ) gate can be implemented non-transversally us- plementation for C k Z(θ)?”. Fortunately the answer to
ing a circuit that involves only d qubits, called active both questions is yes and this leads to two approaches
qubits, of each code block as shown in Fig. 1, where namely hybrid code concatenation (HCC) and extended
Z(θ) = diag(1, expiθ ) and k ∈ {0, 1, 2, ...}. non-uniform code concatenation (ENUCC), respectively.
Describing how these approaches are accomplished is the
Magnifying this circuit draws our attention towards main focus of this paper.
 3

II. HCC: HYBRID CODE CONCATENATION causes only a single physical error in each of them which
are themselves encoded blocks of C2 . Consequently, this
In this section, a hybrid approach is proposed which error can be corrected using error correction procedure
combines the code concatenation approach with code on C2 .
switching, PFT or MSD, to provide a low-overhead uni- This approach can lead to a low-overhead fault-tolerant
versal fault-tolerant scheme. The proposed method en- implementation of the non-transversal gate U if the num-
codes the information using C1 in the first level of con- ber of non-transversal gates gnt (i.e. |S1 |) is relatively
catenation and then the qubits of C1 are in turn encoded small for the selected code C1 . Fortunately, as stated in
into the code of C2 , either uniformly or non-uniformly. Theorem 1 for a stabilizer code [[n, 1, d]], a logical C k Z(θ)
As there is no quantum code with a universal set of gate can be implemented using some local Clifford gates
transversal gates, there is at least one non-transversal (LC) and 2(d − 1) CNOT gates on each codeword and
gate U on C1 . Suppose that the non-transversal imple- only one physical C k Z(θ) gate. Therefore, for a non-
mentation of U on C1 is constructed using some gates transversal C k Z(θ) on both C1 and C2 , we have |S1 | = 1
G = {g1 , g2 , ..., gm }. In the proposed approach, there where C2 is a CSS code i.e., it has transversal imple-
may exist some gates gnt ∈ G with non-transversal im- mentation for CNOT gate. It is worth noting that the
plementation on C2 . This is in contrast to the code con- LC gates will not be a challenge even if they are non-
catenation approaches where all of the G gates must be transversal on C2 . This is because one can simply re-
transversal on C2 . Indeed, the proposed method uses a place the C1 code with C10 , where a C10 code is generated
more efficient code than code concatenation approaches by applying these gates on C1 . While C10 has the same
in the second level of concatenation but with the over- properties as C1 , the logical C k Z(θ) can be applied on
head of using more costly approaches such as code switch- C10 as shown in the dotted box of Fig. 1, without the
ing, MSD or PFT to complete the fault-tolerant gate set need for applying the LC gates.
on C2 . The idea behind this method is that the num- Let us now describe the HCC method in details by
ber of non-transversal gates gnt on C2 may be relatively some examples using the 5-qubit perfect code, 7-qubit
small. Steane code and 15-qubit Reed-Muller code (RM). Al-
Based on the implementation of the non-transversal though the following examples are described based on
gate U , the qubits of C1 can be partitioned into two sep- the combination of code concatenation and code switch-
arate sets, namely active and non-active qubits. Active ing in two levels of concatenation, one can easily replace
qubits are the coupled qubits and the remaining qubits the code switching with MSD or PFT with no consider-
belong to non-active qubits set. In the proposed ap- able modification and also generalize it for higher levels
proach, the active qubits should be encoded using C2 in of concatenation. It is reminded that PFT is unable to
the second level of concatenation whereas the non-active apply single-qubit gates such as T , fault-tolerantly.
qubits can be left unencoded, encoded using C1 or en-
coded using C2 . We refer to these three cases in dealing
with the non-active qubits as Case 1, Case 2 and Case 3, A. HCC-based code examples using the Steane
respectively. The ways in which the gates are applied in code as C1
the proposed approach are as follows.
The shared transversal gates on both C1 and C2 are The Steane code is considered as C1 in this section.
globally transversal on the concatenated code and are The Clifford set {H, S = C 0 Z( π2 ), CZ = C 1 Z(π)} along
therefore, fault-tolerant. For the transversal gates on C1 with a non-Clifford gate such as T = C 0 Z( π4 ) construct
with non-transversal implementation on C2 , although a a universal set. Clifford gates are transversal on Steane
single physical error may corrupt a C2 logical qubit, it while T is not. The non-transversal implementation of
can be corrected using error correction procedure on C1 , T on a Steane code block consists of one T and four
similar to the code concatenation approaches. CNOT gates as shown in Fig. 2. Thus, active qubits are
The main challenge is fault-tolerant application of the {q1 , q2 , q7 } and non-active qubits are {q3 , q4 , q5 , q6 } and
non-transversal gates on C1 referred to as U . As men- by choosing the Steane code as C2 , we have S1 = {g3 }
tioned above, the implementation of U on C1 uses some and S2 = {g1 , g2 , g4 , g5 }. The active qubits are encoded
gates G = {g1 , g2 , ..., gm }. These gates can be parti- using the Steane code and based on whether the non-
tioned into two non-overlapping sets, namely S1 and S2 . active qubits are left unencoded or are encoded using
A gate gi belongs to S2 if it has a transversal implemen- Steane, a 25- or 49-qubit code is produced, respectively.
tation on C2 and belongs to S1 , otherwise. The gates Clifford gates are transversal in both levels of coding
of S2 are transversal and therefore, fault-tolerant in the and are thus, fault-tolerant for the proposed concate-
second level of concatenation. However, the proposed nated codes. For fault-tolerant implementation of the
method exploits other existing approaches such as code logical T gate, the gates of S2 are applied transversally
switching, MSD or PFT for fault-tolerant application of on Steane (C2 ) and the T gate (g3 ) can be applied by
the S1 gates as they are non-transversal on C2 . There- switching q7 from Steane into RM and converting it back
fore, each gate gi ∈ G is applied fault-tolerantly in the to Steane after transversal application of T on RM . Fig.
second level and a single error on one of the active qubits 2 shows this procedure for the 49-qubit code. CC is
 4

Steane q1 g1 g4 g8 g9
Steane
g1 g5
q2
q1 K K†
q2
Steane q3 g2 g10
g2 g4 q3
Steane q4 Y Y
Steane q5 q4
g3 g5 g7 g11
K†
Steane q6 q5
g3 K
Steane RM Steane
CC T CC’ q7 g6
g1 g4 g8 g9
q1 K K†
FIG. 2. Fault-tolerant implementation of T based on the HCC
approach for the 49-qubit code. q2
g2 g10
q3 Y Y
q4
an abbreviation for Code Converter which can be imple- g3 g5 g7 g11
mented based on direct fault-tolerant conversion method
q5 K K†
between Reed-Muller codes [10], efficiently. CC and CC’
convert the Steane code into the RM code and vice versa, g6
g1 g4 g8 g9
respectively. q1 K K†
q2
g2 g10
q3 Y Z(θ) Y
q4
B. HCC-based code examples using the 5-qubit g3 g5 g7 g11
code as C1 q5 K K†

FIG. 3. Non-transversal implementation of C k Z(θ) for the

In this section, the 5-qubit code is selected as C1
5-qubit code.
and a logical qubit is encoded into the 5-qubit code in
the first level of concatenation. Let M={T = C 0 Z( π4 ),
S = C 0 Z( π2 ), CZ = C 1 Z(π)}. The gates in M along III. ENUCC: EXTENDED NON-UNIFORM
with K form a universal set for quantum computation, CODE CONCATENATION
where K = SH. The K gate is transversal on the 5-
qubit code but the gates of M are not. The gates of
M belong to the class of C k Z(θ) gates and thus, as de- In this approach, a logical qubit is encoded into the
scribed before, a CSS code such as Steane can be se- code of C1 where for the chosen gate library, each non-
lected as C2 with |S1 | = 1. Based on Fig. 3, which transversal gate on C1 must have the form of U =
shows the non-transversal implementation of M gates C k Z(θ). Remember that Fig. 1 shows the circuit for
on the 5-qubit code, we have active qubits={q1 , q3 , q5 } applying the non-transversal implementation of such a
and non-active qubits={q2 , q4 } and also S1 = {g6 } and U on C1 . In the non-uniform code concatenation ap-
S2 = {g1 , g2 , g3 , g4 , g5 , g7 , g8 , g9 , g10 , g11 } only for the T proach [19], only one quantum code, namely C2 , is used
gate (note that S and CZ are transversal on Steane). to encode the active qubits of C1 in the second level of
The active qubits are encoded using Steane and the non- concatenation, where C2 has the ability to perform all
active qubits can be either left unencoded or encoded of the gates in this circuit transversally. However, in
using the 5-qubit code or Steane which leads to a 23-, this section we extend the non-uniformity of the code by
31- or 35-qubit code, respectively. allowing to use two codes C2 and C3 for encoding the
active qubits. Indeed, qt is encoded into C3 and C2 is
The K gate can be applied transversally for all of the used to encode the remaining active qubits. The non-
23-, 31- and 35-qubit codes, as it is transversal on both active qubits can be left unencoded or encoded using ei-
the 5-qubit and Steane codes. The S and CZ gates are ther C1 or C2 and similar to the previous section, we
transversal on Steane. Consequently, these gates can be refer to them as Case 1, Case 2 and Case 3, respectively.
applied fault-tolerantly on the concatenated code with- C k Z(θ) must be transversal on C3 and as stated in Sec-
out need to exploit code switching. However, for fault- tion II, it is only needed for C2 to be a CSS code. Now, a
tolerant implementation of T , the proposed method dy- main challenge remained: How a CNOT gate can be ap-
namically alternates between Steane and RM for q3 when plied fault-tolerantly between the codewords of different
T (g6 ) should be applied. quantum codes, e.g., C2 and C3 ? In the following, this
 5

q1 q1
q2 q2

7-qubit Steane code

SZSteane
q7 q3

q4
q1 q5
q2
q6
q3
q7
q4

SXRM
q5
q1
q6
q2
q7
q3

q4
FIG. 4. Round-robin implementation of a logical CNOT gate
from a Steane code block to an RM code block which is piece- q5

15-qubit Reed-Muller code

ably fault-tolerant with four pieces. q6

q7

q8
question will be answered.
q9
Theorem 2. For any two non-degenerate stabilizer q10
codes, each of which either (a) possesses a complete set
q11
of fault-tolerant logical local Cliffords or (b) is CSS with
q12
a logical local Clifford gate, there exists a logical CNOT
gate between them in both directions [15]. q13

q14
For two codes C2 = [[n2 , 1, d2 ]] and C3 = [[n3 , 1, d3 ]]
which satisfy Theorem 2, a logical CNOT gate can be q15

applied as follows: Let SX2 /SZ2 and SX3 /SZ3 be the

supports of the logical operator X/Z for C2 and C3 , re- FIG. 5. Proposed implementation of a logical CNOT gate
spectively, on which the corresponding logical operator from a Steane code block to an RM code block which is piece-
only has X/Z and I. Connecting physical CNOT gates ably fault-tolerant with two pieces.
from SZ2 to SX3 in a round-robin fashion (take every
combination) applies a logical CNOT gate between C2

Non-Active Qubits
(as control) and C3 (as target). This implementation
is non-transversal. To make it fault-tolerant, the PFT
method can be used. Based on this method, the circuit
is broken into some min(d2 , d3 ) − 1 pieces and the inter-
C1 code block

mediate error corrections are inserted between them to C2

detect X errors in the middle and notify possible loca-

Active Qubits
C2
tions of Z errors to the final error correction.
As an example, Fig. 4 shows a round-robin circuit LC LC†
C2
which applies a logical CNOT gate from Steane to RM .
This circuit consists of 21 CNOTs in four pieces and thus, C3 qt
Z(θ)
three intermediate error corrections and a final error cor-
rection are required. However, we find a more efficient
circuit consisting of only 17 CNOTs with two pieces. Fig. FIG. 6. Fault-tolerant implementation of a logical Z(θ) gate
5 shows this circuit. This implementation can be simply based on the ENUCC approach. Note that, the CNOT gates
extended for applying a logical CNOT between two suc- surrounded by dotted boxes are applied on codewords of dif-
cessive Reed-Muller codes RM(n) and RM(n+1). ferent quantum codes and the PFT method is used to apply
them fault-tolerantly.
A general schematic of the proposed approach for ap-
plying a Z(θ) gate is shown in Fig. 6. The CNOT gates
surrounded by dotted boxes should be applied based on
PFT method as they are applied on codewords of differ- one. However, as all of the gates in the second level
ent codes, e.g., C2 and C3 . of concatenation are implemented fault-tolerantly, this
Up to here, fault-tolerant implementation of non- error propagates to at most one physical qubit in each
transversal gates on C1 are described. Note that these code block which can be corrected using error correction
gates are not fully transversal and a single physical er- procedure in the second level of coding hierarchy. The
ror on one of the active qubits can spread to another ways in which the other gates are applied in EN U CC
 6

Steane Steane
q1 K K†
Steane
q2 Steane

q3
RM
Y Z(θ) Y
q4
Steane
q5
Steane
q6 K K†
RM q7
T
FIG. 8. Fault-tolerant implementation of Z(θ) based on
FIG. 7. Fault-tolerant implementation of T based on the the ENUCC approach for the 43-qubit code. The CNOT
ENUCC approach for the 33-qubit code. The CNOT gates gates surrounded by dotted boxes are applied based on PFT
surrounded by dotted boxes are applied based on PFT method.
method.

codes in this section, a logical qubit is encoded into the

approach are similar to the method proposed in the pre- 5-qubit code in the first level of concatenation. While the
vious section, e.g., HCC. gates of M are not transversal on the 5-qubit code, they
Similar to the previous section, let us now describe the belong to the class of C k Z(θ) gates and also are transver-
ENUCC method by some examples using the 5-qubit, sal on RM . Therefore, Steane and RM can be selected
Steane and RM codes. as C2 and C3 , respectively. In the proposed codes, q3 (qt )
is encoded using RM and q1 and q5 are encoded into the
code of Steane. The non-active qubits, q2 and q4 , can
A. ENUCC-based code examples using the Steane be left unencoded or encoded using the 5-qubit code or
code as C1 Steane leading to a 31-, 39- or 43-qubit code, respectively.
The gates of M can be applied fault-tolerantly, as
In this section, the Steane code is considered as C1 with shown in Fig. 8, where the CNOT gates surrounded by
{H, S = C 0 Z( π2 ), CZ = C 1 Z(π), T = C 0 Z( π4 )} as the the dotted boxes are applied using the circuit depicted
universal gate set. As mentioned before, the Steane code in Fig. 5. The K gate is non-transversal on RM . How-
is a CSS code with only non-transversal implementation ever, an erroneous RM code block during application of
for T and T is transversal on RM . Therefore, Steane and this gate can be corrected using error correction on the
RM can be selected as C2 and C3 , respectively. Based on 5-qubit code.
this selection, q7 (qt ) is encoded into RM , the remaining
active qubits (q1 and q2 ) are encoded using Steane and
the non-active qubits (q3 to q6 ) can be encoded using IV. CODE ANALYSIS
Steane or left unencoded. Based on whether the non-
active qubits are left unencoded or encoded using Steane, Straight concatenation of the two codes [[n1 ,1,d1 ]] and
a 33- or 57-qubit code is produced, respectively. [[n2 ,1,d2 ]] leads to a code [[n1 n2 ,1,d1 d2 ]] [22]. However,
S and CNOT gates are transversal on both Steane and this distance (d1 d2 ) may be sacrificed because of error
RM and are thus, fault-tolerant for the proposed con- propagation during application of the non-transversal
catenated codes. The logical T gate can be applied fault- gates. We refer to d1 d2 as the overall distance of the
tolerantly as shown in Fig. 7 where the circuit depicted code and use effective distance to represent the sacrificed
in Fig. 5 is used to apply the CNOT gates surrounded by distance. In this section, we analyze the proposed codes
the dotted boxes. While H is transversal on Steane, it is in terms of overall and effective distance.
not transversal on RM . However, albeit a single physi- For the concatenated codes with fully encoded qubits
cal error on an RM code block causes a logical error on in both levels of concatenation (Cases 2 and 3), e.g., the
that code block, this error can be corrected using error 31-, 35-, 49-qubit HCC-based codes and 39-, 43- and 57-
correction on C1 . qubit ENUCC-based codes, the overall distance is 9. On
the other hand, for the codes with unencoded non-active
qubits (Case 1), e.g., the 23- and 25-qubit HCC-based
B. ENUCC-based code examples using the 5-qubit codes and 31- and 33-qubit ENUCC-based codes, the
code as C1 overall distance is 5 as deduced in [23] for the 49-qubit
non-uniform concatenated code [19].
In this section, similar to Section II B, the set M={T = The effective distance of the proposed codes varies for
C 0 Z( π4 ), S = C 0 Z( π2 ), CZ = C 1 Z(π)} along with K is different gates. Table I compares the effective distance of
considered as the universal gate set. In the proposed the proposed codes for the gates of the selected universal
 7

TABLE I. Comparison of the proposed concatenated codes q1

in terms of the number of qubits and effective distance for
different gates. q2

5-qubit code
Worst
Method C1 Case # qubits H K T S CZ CCZ
case
1 25 5 5 3 5 5 3 3
q3
Steane
2≡3 49 9 9 3 9 9 3 3
HCC 1 23 - 5 3 3 3 3 3 q4
5-qubit 2 31 - 9 3 3 3 3 3
3 35 9 9 3 9 3 3 3 q5
1 33 3 3 3 5 5 3 3
Steane
2≡3 57 7 7 3 9 9 3 3
ENUCC 1 31 - 3 3 3 3 3 3
5-qubit 2 39 - 7 3 3 3 3 3 FIG. 9. Transversal implementation of H on the 5-qubit code
3 43 7 7 3 7 3 3 3 with permutation. Note that q3 is not permuted.

most one physical error on each active qubit and these

gate sets. errors can be corrected using error correction procedure
For the shared transversal gates in both levels of con- on C2 code blocks. {S, CZ, T , CCZ} and {T , CCZ}
catenation, no error is propagated in the code blocks and are such gate set for the proposed codes based on the 5-
thus, the effective distance of the concatenated codes will qubit and Steane codes, respectively. It should be noted
be equal to its overall distance. The gates with the effec- that CCZ = C 2 Z(π) can be applied fault-tolerantly for
tive distance of 5 and 9 in Table I are examples of such the proposed codes as its implementation on the Steane
gates. and 5-qubit codes has the same structure as T and it is
The H and K gates are non-transversal on RM . Con- transversal on RM .
sequently, for these gates, the effective distance of the The proposed code examples outperform the codes
ENUCC-based codes, which have a coded block of RM , based on code concatenation proposed in [18] and [19] as
is reduced from 5 to 3 or from 9 to 7. For example, for they need fewer qubits and less resource to protect the
the 57-qubit code, the worst case is when two errors on a computation from arbitrary single physical error. For
Steane code block and one error on the RM code block example, the counterparts of the proposed 25- and 57-
occur that none of them possibly can be corrected us- qubit codes have 49 [19] and 105 qubits [18], respectively.
ing error correction in the second level. In this case, the Furthermore, for H and K, the effective distance of the
code block that is complementary to these two errors is proposed codes is higher than their concatenated coun-
identified when the Steane (C1 ) stabilizers are measured. terparts. This result becomes more valuable by the fact
However, since no error had been identified on that code that the threshold of the 49- and 105-qubit concatenated
block in the second level, the complementary errors can codes are limited by the application of logical H gate
be clearly identified. Although, adding one additional [24][23]. The only overhead of the proposed HCC-based
physical error on another Steane code block, make it am- codes in comparison with the concatenated codes is us-
biguous to correctly identify the erroneous qubits. ing code switching, MSD or PFT for application of S1
Note that the H gate is applicable for the 35- and gates (e.g., T or CCZ). In the case of ENUCC-based
43-qubit codes with the effective distance of 9 and 7, re- codes, two CNOT gates should be applied based on PFT
spectively. This is because H is transversal on the 5-qubit method with the overhead of additional intermediate er-
code by permutation as shown in Fig. 9 [15]. This permu- ror corrections.
tation is applicable for these two codes, as the permuted In comparison with the code switching, MSD and PFT
qubits during application of H, e.g. q1 , q2 , q4 and q5 , are approaches, the proposed methods significantly reduce
encoded blocks of the same code, e.g., Steane. However, the implementation overhead of non-transversal gates in
applying H with permutation for other proposed codes two-level concatenated codes. The main disadvantage
based on the 5-qubit code destroys the code structures of our method is that the overall distance of the con-
as it permutes code blocks that are encoded using differ- catenated code is sacrificed for non-transversal gates in
ent codes in the second level of concatenation. Generally, comparison with those approaches.
a transversal gate with permutation on C1 is not appli-
cable for non-uniform concatenated codes [19] unless it
permutes only the encoded blocks of the same code. It V. CONCLUSION
is worth noting that for the S gate, the effective distance
of 35- and 43-qubit codes are 9 and 7, respectively. This In this article, we proposed two low-overhead ap-
is because S can be applied as KH. proaches for universal FTQC, namely HCC and ENUCC.
For the non-transversal gates on C1 , the effective dis- The HCC method combines code concatenation with
tance of the proposed code examples is 3. In this case, code switching, MSD or PFT schemes. On the other
a single physical error on a qubit of C1 propagates to at hand, ENUCC uses two codes, C2 and C3 , for encoding
 8

active qubits by allowing to apply fault-tolerant CNOT and higher effective distance for H and K in comparison
gates between codewords of different codes C2 and C3 . with ENUCC-based codes. However, it uses more costly
code switching, MSD or PFT approaches for applying
The proposed approaches was described based on the
T and CCZ gates while the ENUCC-based codes only
5-qubit and Steane codes in two levels of concatenation as
need to use more efficient two PFT-based CNOT gates
examples which lead to the 25-, 49-, 23-, 31- and 35-qubit
between Steane and RM codes (Fig. 5) to perform such
HCC-based and 33-, 57-, 31-, 39- and 43-qubit ENUCC-
gates. Making accurate estimation of the error threshold
based codes. The proposed codes have significantly fewer
and resource overhead of the proposed codes and explor-
number of qubits in comparison with the codes based on
ing the method for other codes are considered as future
code concatenation approaches. In addition, the effective
works.
distance of the proposed codes is higher for H and K
gates. Furthermore, this approach significantly reduces
the resource overhead in comparison with code switch- ACKNOWLEDGEMENT
ing, MSD and PFT at the cost of reducing the effective
distance of the concatenated code for implementing non-
The authors acknowledge the financial support by the
transversal gates.
Iranian National Science Foundation (INSF). The first
The HCC-based codes have fewer number of qubits author is grateful to Ryuji Takagi for helpful discussions.

[1] P. W. Shor, in Foundations of Computer Science, 1994 [13] A. Paetznick and B. W. Reichardt, Physical review let-
Proceedings., 35th Annual Symposium on (IEEE, 1994) ters 111, 090505 (2013).
pp. 124–134. [14] H. Bombı́n, New Journal of Physics 17, 083002 (2015).
[2] C. Zalka, Fortschritte der Physik 46, 877 (1998). [15] T. J. Yoder, R. Takagi, and I. L. Chuang, Physical Re-
[3] M. A. Nielsen and I. L. Chuang, Quantum computation view X 6, 031039 (2016).
and quantum information (Cambridge university press, [16] A. M. Stephens, Z. W. E. Evans, S. J. Devitt, and
2010). L. C. L. Hollenberg, Physical Review A 77, 062335
[4] W. G. Unruh, Phys. Rev. A 51, 992 (1995). (2008).
[5] L. Mazzola, J. Piilo, and S. Maniscalco, Physical review [17] B.-S. Choi, Quantum Information Processing 14, 2775
letters 104, 200401 (2010). (2015).
[6] T. S. Metodi and F. T. Chong, Synthesis Lectures in [18] T. Jochym-OConnor and R. Laflamme, Physical review
Computer Architecture 1, 1 (2006). letters 112, 010505 (2014).
[7] M. Ahsan, Architecture framework for trapped-ion quan- [19] E. Nikahd, M. Sedighi, and M. S. Zamani, arXiv preprint
tum computer based on performance simulation tool, arXiv:1605.07007 (2016).
Ph.D. thesis, Duke University (2015). [20] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N.
[8] E. Knill, R. Laflamme, and W. H. Zurek, in Proceedings Cleland, Physical Review A 86, 032324 (2012).
of the Royal Society of London A: Mathematical, Physical [21] M. Oskin, F. T. Chong, and I. L. Chuang, Computer
and Engineering Sciences, Vol. 454 (The Royal Society, 35, 79 (2002).
1998) pp. 365–384. [22] D. Gottesman, arXiv preprint quant-ph/9705052 (1997).
[9] P. W. Shor, in Foundations of Computer Science, 1996. [23] C. Chamberland, T. Jochym-O’Connor, and
Proceedings., 37th Annual Symposium on (IEEE, 1996) R. Laflamme, arXiv preprint arXiv:1609.07497 (2016).
pp. 56–65. [24] C. Chamberland, T. Jochym-O’Connor, and
[10] J. T. Anderson, G. Duclos-Cianci, and D. Poulin, Phys- R. Laflamme, Physical review letters 117, 010501
ical review letters 113, 080501 (2014). (2016).
[11] B. Eastin and E. Knill, Physical review letters 102,
110502 (2009).
[12] S. Bravyi and A. Kitaev, Physical Review A 71, 022316
(2005).

View publication stats