[go: up one dir, main page]

0% found this document useful (0 votes)
92 views14 pages

Single Quantum Deletion Error-Correcting Codes: Ayumu Nakayama Manabu HAGIWARA

This paper discusses a construction method for quantum deletion error-correcting codes. It defines deletion errors for quantum states, an encoder that maps quantum messages to encoded states, and a decoder. It provides two combinatorial conditions for sets A and B that make the encoded states correctable against single deletion errors. Specifically, the conditions require that the deletion sets of A and B are disjoint and have a certain ratio relationship. Sets satisfying these conditions can be used to construct quantum deletion error-correcting codes.

Uploaded by

udslv
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
92 views14 pages

Single Quantum Deletion Error-Correcting Codes: Ayumu Nakayama Manabu HAGIWARA

This paper discusses a construction method for quantum deletion error-correcting codes. It defines deletion errors for quantum states, an encoder that maps quantum messages to encoded states, and a decoder. It provides two combinatorial conditions for sets A and B that make the encoded states correctable against single deletion errors. Specifically, the conditions require that the deletion sets of A and B are disjoint and have a certain ratio relationship. Sets satisfying these conditions can be used to construct quantum deletion error-correcting codes.

Uploaded by

udslv
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

arXiv:2004.

00814v1 [quant-ph] 2 Apr 2020


Single Quantum Deletion Error-Correcting
Codes
∗ †
Ayumu NAKAYAMA Manabu HAGIWARA

Abstract
In this paper, we discuss a construction method of quantum dele-
tion error-correcting codes. First of all, we define deletion errors for
quantum states, an encoder, a decoder, and two conditions which is
expressed by only the combinatorial language. Then, we prove that
quantum deletion error-correcting codes can be constructed by two
sets that satisfy the conditions. In other words, problems that cor-
rect the deletion errors for quantum states are reduced to problems
that find the sets satisfying the condition by this paper. Also, we
performed experiment of the codes over IBM Quantum Experience.

1 Introduction
In the classical coding theory, deletion error-correcting codes have been stud-
ied for synchronization error-correction of communication since the pioneer
work of Levenshtein in 1966 [9]. These codes have interesting applications
such as error-correction for DNA storages [2], error-correction for racetrack
memories [4], etc.
In the quantum coding theory, there are some well-known codes such as
CSS codes [3], stabilizer codes [6], surface codes [5], etc. However, these
codes cannot correct deletion errors. Therefore, in this paper, we discuss
the construction of quantum deletion error-correcting codes. Here deletion
errors for quantum states are errors corresponding to the case where a part
of photons which a sender transmitted do not reach to a receiver or where
quantum states disappear by the energy decays.

Department of Mathematics and Informatics, Graduate School of Science and En-
gineering, Chiba University 1-33 Yayoi-cho, Inage-ku, Chiba City, Chiba Pref., JAPAN,
263-0022

Department of Mathematics and Informatics, Graduate School of Science, Chiba Uni-
versity 1-33 Yayoi-cho, Inage-ku, Chiba City, Chiba Pref., JAPAN, 263-0022

1
Recently a few papers about quantum deletion error-correcting codes have
been published. In the paper [8], quantum insertion-deletion channels are
introduced and in the papers [11] and [7], two types of quantum deletion
codes are constructed.
In this paper, we define an encoder and a decoder for given sets A, B ⊂
{0, 1}n and provide two combinatorial conditions for A and B that make the
image of the encoder single quantum deletion error-correctable. The codes
in the paper [11] and [7] are the specific instances.
This paper is organized as follows. In section 2, some notations and
definitions are introduced, and in section 3, the deletion error for a quantum
state is defined. In section 4, an encoder, a decoder, and two conditions
(C1) and (C2) for sets A, B ⊂ {0, 1}n are defined. In section 5, the sets A, B
satisfying the conditions (C1) and (C2) are introduced. In section 6, a circuit
of an encoder and a decoder are created over IBM Quantum Experience [1]
that is indicated in [7] and experiments were performed. Finally this paper
is summarized in section 7.
Partial results have been presented at Japanese domestic workshop in
Japanese [10].

2 Preliminaries
Let n be an integer greater than or equal to 2 and [n] := {1, 2, . . . , n}. For
a square matrix A over a complex field C, Tr(A) denotes the sum of the
diagonal elements of A. Set |0i , |1i ∈ C2 as |0i := (1, 0)T , |1i := (0, 1)T , and
|xi as |xi := |x1 i⊗|x2 i⊗· · ·⊗|xn i for a bit sequence x = x1 x2 · · · xn ∈ {0, 1}n .
Here ⊗ is the tensor product operation and T is the transpose operation.
We denote by S(C2⊗n ) the set of all density matrices of order 2n . A density
matrix is employed to represent a quantum state. In a particular case n = 1,
we call σ ∈ S(C2 ) a quantum message.
Definition 1 (partial trace Tri ). Let i ∈ [n] be an integer. Define a function
Tri : S(C2⊗n ) → S(C2⊗n−1 ) as
X
Tri (A) := ax,y · Tr(|xi i hyi |) |x1 i hy1 | ⊗
x,y∈{0,1}n

· · · ⊗ |xi−1 i hyi−1 | ⊗ |xi+1 i hyi+1 | ⊗


· · · ⊗ |xn i hyn | ,

where X
A= ax,y |x1 i hy1 | ⊗ · · · ⊗ |xn i hyn | .
x,y∈{0,1}n

2
The map Tri is called the partial trace.

Definition 2 (projection measurement P). A set P := {P1 , . . . Pm } of com-


plex matrices P1 , . . . Pm of order 2n is called a projection measurement if and
only if every Pi is a projection matrix and
m
X
Pi = I,
i=1

where I is the identity matrix of order 2n . If we perform the projection


measurement P under a quantum state ρ ∈ S(Cn ), the probability to obtain
an outcome k ∈ [m] is Tr(Pk ρ), and the state associated with k after the
measurement ρ0 is
Pk ρPk
ρ0 := .
Tr(Pk ρ)

3 Single Deletion Errors


In this section, we define a single deletion error for a quantum state. Remark
that in the classical coding theory, a single deletion error is defined as a map
from a bit sequence x1 . . . xi−1 xi xi+1 . . . xn ∈ {0, 1}n to a shorter sequence
x1 . . . xi−1 xi+1 . . . xn ∈ {0, 1}n−1 for some i.

Definition 3 (deletion error Di ). Let i ∈ [n] be an integer. Define a function


Di : S(C2⊗n ) → S(C2⊗n−1 ) as

Di (ρ) := Tri (ρ),

where ρ ∈ S(C2⊗n ) is a quantum state. We call the map Di a deletion error.

4 Construction of Quantum Deletion Error-


Correcting Codes
In this section, we define an encoder and a decoder and propose two condi-
tions for two sets of bit sequences. Afterwards, we discuss the construction
of the quantum deletion error-correcting codes.

Definition 4 (encoder EncA,B ). Let A, B ⊂ {0, 1}n be sets which satisfy the
following conditions A 6= ∅, B 6= ∅, A ∩ B = ∅. Define an encoder EncA,B :
S(C2 ) → S(C2⊗n ) as
EncA,B (σ) := |Ψi hΨ| ,

3
where σ := |ψi hψ| ∈ S(C2 ) is a quantum message with a unit vector |ψi :=
α |0i + β |1i ∈ C2 and
α X β X
|Ψi := p |ai + p |bi .
|A| a∈A |B| b∈B

Definition 5 (∆i,b ). Let i ∈ [n] and b ∈ {0, 1} be integers. Define a set


∆i,b (A) ⊂ {0, 1}n−1 as

∆i,b (A) := {(a1 , . . . , ai−1 , ai+1 , . . . , an ) ∈ {0, 1}n−1 |


(a1 , . . . , ai−1 , b, ai+1 , . . . , an ) ∈ A},

where A ⊂ {0, 1}n is a non-empty set. We call the set ∆i,b (A) an (i, b)
deletion set of A.
Definition 6 (conditions (C1) and (C2)). For non-empty sets A, B ⊂ {0, 1}n ,
define two conditions (C1) and (C2) as follows.
(C1 distance condition):
For any i1 , i2 ∈ [n] and any b1 , b2 ∈ {0, 1},

|∆i1 ,b1 (A) ∩ ∆i2 ,b2 (B)| = 0.

(C2 ratio condition):


For any i1 , i2 ∈ [n] and any b ∈ {0, 1},

|A||∆i1 ,b (B) ∩ ∆i2 ,b (B)| = |B||∆i1 ,b (A) ∩ ∆i2 ,b (A)|.

Lemma 7. Let A, B ∈ {0, 1}n be non-empty sets satisfying the conditions


|A| |B|
(C1) and (C2). Define (a0 , b0 ) := ( gcd(|A|,|B|) , gcd(|A|,|B|) ). Then the output P
of Algorithm 1 is a projection measurement. Here gcd(|A|, |B|) is the greatest
common divisor of |A| and |B|.
Proof. By the condition (C2), ∆i1 ,b (B) ∩ ∆i2 ,b (B) 6= ∅ holds as ∆i1 ,b (A) ∩
∆i2 ,b (A) 6= ∅ does. Then we obtain a ratio |A| : |B| = |∆i1 ,b (A) ∩ ∆i2 ,b (A)| :
|∆i1 ,b (B) ∩ ∆i2 ,b (B)| = a0 : b0 . Therefore we are able to take a0 + b0 distinct
elements
x1 , x2 , . . . , xa0 ∈ ∆i1 ,b (A) ∩ ∆i2 ,b (A)
y1 , y2 , . . . , yb0 ∈ ∆i1 ,b (B) ∩ ∆i2 ,b (B)
if the step at 2: in Algorithm 1 holds. Similarly, we can take a0 + b0 distinct
elements
x1 , x2 , . . . , xa0 ∈ ∆i,b (A), y1 , y2 , . . . , yb0 ∈ ∆i,b (B)

4
if the step at 5: in Algorithm 1 holds. Note that hxt |ys i = 0 follows from
the condition (C1).
Hence, by the definitions of P1 , . . . , Pp−1 , it is clear that these
P matrices
are projection matrices, where p := |P|. It is also trivial that P ∈P P = I
holds due to the definition of Pp . Let
a0
X b0
X
P := |xt i hxt | + |ys i hys | ,
t=1 s=1

a0
X b0
X
P̃ := |x̃t0 i hx̃t0 | + |ỹs0 i hỹs0 | .
t0 =1 s0 =1
Then X X
Pp† = I† − P† = I − P = Pp
P P
holds, and

X X
Pp2 = I − 2 P+ P P̃
P P,P̃
X X
=I−2 P+ δP,P̃ P
P P,P̃
X X
=I−2 P+ P = Pp
P P

holds. Therefore P is a projection measurement.


Definition 8 (error-correcting operator Uk ). For non-empty sets A, B ⊂
{0, 1}n satisfying the conditions (C1) and (C2) and a projection measurement
P that is constructed by Algorithm 1, we can choose a unitary matrix Uk which
satisfies the followings for 1 ≤ k ≤ |P|:
P
x∈∆(A) Pk |xi
Uk P = |0 · · · 00i ,
|| x∈∆(A) Pk |xi ||
P
y∈∆(B) Pk |yi
Uk P = |0 · · · 01i ,
|| y∈∆(B) Pk |yi ||
where [ [
∆(A) := ∆i,b (A), ∆(B) := ∆i,b (B).
i∈[n] i∈[n]
b∈{0,1} b∈{0,1}

We call the matrix Uk an error-correcting operator.

5
Definition 9 (decoding algorithm DecA,B ). Let A, B ⊂ {0, 1}n be non-empty
sets satisfying the conditions (C1) and (C2) and P a projection measurement
which is constructed by Algorithm 1. Define a function DecA,B : S(C2⊗n−1 ) →
S(C2 ) as a map which assigns ρ0 ∈ S(C2⊗n−1 ) to σ 0 ∈ S(C2 ) which is con-
structed by the following procedure.

1. Perform the projection measurement P under the state ρ0 . Assume that


the outcome is 1 ≤ k ≤ |P| and that the state after measurement is ρ0k .

2. Let ρ̃ := Uk ρ0k Uk† . Here Uk is the error-correcting operator.

3. At last, return σ 0 := Tr1 ◦ · · · ◦ Tr1 (ρ̃).


| {z }
n−2 times

Theorem 10. Let A, B ⊂ {0, 1}n be non-empty sets satisfying the conditions
(C1) and (C2). Then for any quantum message σ ∈ S(C2 ) and any deletion
position i ∈ [n],
DecA,B ◦ Di ◦ EncA,B (σ) = σ.
Here the symbol ◦ represents the composition of functions. In other words,
EncA,B (S(C2 )) is a single quantum deletion error-correcting code with the
decoder DecA,B .

Proof. For a quantum message σ := |ψi hψ| with a unit vector |ψi = α |0i +
β |1i ∈ C2 , set ρ as
ρ := EncA,B (σ). (1)
Then for any i ∈ [n], Di (ρ) is rewritten as

X |α|2 X
Di (ρ) = |xi hx̃|
|A|
b∈{0,1} x∈∆i,b (A)
x̃∈∆i,b (A)

αβ X
+ p |xi hy|
|A||B| x∈∆ (A)
i,b
y∈∆i,b (B)

αβ X
+ p |yi hx|
|A||B| y∈∆ (B)
i,b
x∈∆i,b (A)
!
|β|2 X
+ |yi hỹ| .
|B|
y∈∆i,b (B)
ỹ∈∆i,b (B)

6
Let P = {P1 , P2 , . . . , Pp } be the projection measurement constructed by
Algorithm 1. By the definition of Pp ,

Pp Di (ρ) = O

for any i ∈ [n], where O is the zero matrix. In addition, for any i ∈ [n] and
any k ∈ [p − 1], the following equation holds. Here Pk is denoted as
a0
X b0
X
(k) (k)
Pk = |xt i hxt | + |ys(k) i hys(k) | .
t=1 s=1

Pk Di (ρ) =
a0
X |α|2 X X (k) (k)
hxt |xi |xt i hx̃|
|A| t=1 x∈∆i,b (A)
b∈{0,1}
x̃∈∆i,b (A)
a0
αβ X X (k) (k)
+p hxt |xi |xt i hy|
|A||B| t=1 x∈∆i,b (A)
y∈∆i,b (B)
b0
αβ X X
+p hys(k) |yi |ys(k) i hx|
|A||B| s=1 y∈∆i,b (B)
x∈∆i,b (A)
b0
!
|β|2 X X
+ hys(k) |yi |ys(k) i hỹ| .
|B| s=1
y∈∆i,b (B)
ỹ∈∆i,b (B)

Therefore in the case where k = p,

Tr(Pk Di (ρ)) = 0

holds for any i ∈ [n] and in the case where k ∈ [p − 1], there exists b ∈ {0, 1}
such that
a0
|α|2 X X (k)
Tr(Pk Di (ρ)) = | hxt |xi |2
|A| t=1
x∈∆i,b (A)
b0
|β|2 X X
+ | hys(k) |yi |2
|B| s=1
y∈∆i,b (B)

7
holds for any i ∈ [n]. Hence for k ∈ [p − 1] such that Tr(Pk Di (ρ)) 6= 0,

a0 |α|2 b0 |β|2 1
Tr(Pk Di (ρ)) = + =
|A| |B| λ

and the state after the measurement is


a0 Xa0
|α|2 X (k) (k)
λPk Di (ρ)Pk = |x i hxt0 |
a0 t=1 t0 =1 t
a0 Xb0
αβ X (k)
+ √ |xt i hys(k) |
a0 b0 t=1 s=1
b0 Xa0
αβ X (k)
+ √ |ys(k) i hxt |
a0 b0 s=1 t=1
b0 Xb0
|β|2 X (k)
+ |ys(k) i hys0 |
b0 s=1 s0 =1
= |Φk i hΦk | ,

where λ := gcd(|A|, |B|) and


a0 b0
α X (k) β X
|Φk i := √ |x i + √ |ys(k) i .
a0 t=1 t b0 s=1

Note that |Φk i can be rewritten as


P P
x∈∆(A) Pk |xi y∈∆(B) Pk |yi
|Φk i = α P +β P .
|| x∈∆(A) Pk |xi || || y∈∆(B) Pk |yi ||

From the discussion above, for any quantum message σ ∈ S(C2 ) and any
deletion position i ∈ [n],

DecA,B ◦ Di ◦ EncA,B (σ)


= DecA,B ◦ Di (ρ) (∵ (1))
= Tr1 ◦ · · · ◦Tr1 (Uk |Φk i hΦk | Uk† ) (∵ Def. 9)
= Tr1 ◦ · · · ◦ Tr1 (|0i h0| ⊗ · · · ⊗ |0i h0| ⊗ σ) (∵ Def. 8)
=σ (∵ Def. 3)

holds.

8
5 Examples of Quantum Deletion Error-Correcting
Codes
In this section, we introduce two instances of sets A, B ⊂ {0, 1}n that satisfy
the conditions (C1) and (C2).

5.1 Example 1 (4 qubits code [7])


Let n := 4,
A := {0000, 1111},
and
B := {0011, 0101, 1001, 0110, 1010, 1100}.
Then for any i ∈ [4],

∆i,0 (A) = {000}, ∆i,1 (A) = {111},

∆i,0 (B) = {011, 101, 110}, ∆i,1 (B) = {001, 010, 100}.
Therefore for any i1 , i2 ∈ [4] and any b1 , b2 ∈ {0, 1},

|∆i1 ,b1 (A) ∩ ∆i2 ,b2 (B)| = 0,

thus A and B satisfy the condition (C1). Moreover for any i1 , i2 ∈ [4] and
b ∈ {0, 1},
|A||∆i1 ,b (B) ∩ ∆i2 ,b (B)| = 2 × 3 = 6,
|B||∆i1 ,b (A) ∩ ∆i2 ,b (A)| = 6 × 1 = 6.
Consequently A and B satisfy the condition (C2).
This code has two interesting properties. One is that the cardinalities of
A and B are different. Thereby the code can be expressed by neither any
CSS codes [3] nor any stabilizer codes [6]. The other is that the length of the
code is 4. In the paper [7], it is proved that the minimum length of the code
capable of correcting any single deletion errors is 4.

5.2 Example 2 (8 qubits code [11])


Let n := 8,

A := {00001001, 01101111}, B := {00001111, 01101001}.

The tables 1 and 2 show ∆i,b (A) and ∆i,b (B) for all i ∈ [8] and b ∈ {0, 1}.
By these tables, it is easy to see that A and B satisfy the conditions (C1)
and (C2).

9
The interesting point of this code is that the states after single dele-
tion errors may be different depending on the deletion positions. Further-
more the different states are not even orthogonal (e.g., D1 (EncA,B (σ)) and
D2 (EncA,B (σ)) are not orthogonal). However, this code is also a quantum
deletion error-correcting code.

Figure 1: encoder and decoder circuit

6 Experiment by IBM Quantum Experience


6.1 About IBM Quantum Experience
IBM Quantum Experience (IBM Q) [1] is a service to implement circuits
which users create, does experiments on the quantum computer IBM pos-
sesses, and outputs the results to the users.

6.2 Implementation over IBM Quantum Experience


In the paper [7], circuits of an encoder and two decoders are constructed. We
implemented the encoder and the decoder on IBM Q and did experiments to
see if the quantum deletion error-correcting codes work on the real quantum
computer. The figure 1 shows the circuit on IBM Q. The circuit before the
symbol ? in the figure represents the encoder circuit, the circuit after is the
decoding circuit, and we express the deletion error D1 by not using the first
qubit right after encoding.

6.3 Experimental Results


The table 3 shows the percentages that the outcomes 0 and 1 obtained on
the simulation and the quantum computer for three types of states |0i, |1i,
and √12 (|0i + |1i). By the simulation results, it is proved that the circuit

10
we created on IBM Q works correctly. However, the results by the quantum
computer indicates that error-correcting fails with 30 ∼ 35%.
Qubits in the quantum computer on IBM Q are arranged in a two-
dimensional form and it is not possible to operate two nonadjacent qubits
simultaneously. Therefore operations of two nonadjacent qubits are trans-
formed into combinations of operations of two adjacent qubits. It causes the
increase of the number of total quantum gates. It is known that the more the
gates increase, the more errors occur. Hence the future work is to redesign
the circuit to reduce the number of gates.

7 Summary
In this paper, we discussed the quantum deletion error-correcting codes. First
of all, we defined the deletion errors for quantum states by using the partial
trace operations. Since taking partial trace for a density matrix corresponds
to expressing the state of its subsystem, it is natural that a deletion error is
defined by using the partial trace.
In section 4, we defined the encoder, decoder, and the conditions (C1)
and (C2) for sets A, B ⊂ {0, 1}n , and proved that quantum error-correcting
codes for single deletion errors can be constructed by employing the sets
A, B ⊂ {0, 1}n which satisfy the conditions (C1) and (C2). In addition, we
introduced two kinds of examples satisfying the conditions (C1) and (C2) in
section 5.
In section 6, we created the encoder and decoder circuit on IBM Q which
is shown in the paper [7]. As the experimental results, we found that there
are 30 ∼ 35% miscorrections on the quantum computer. This is due to the
increase of quantum gates so that redesigning the circuit is the future work.

Acknowledgments
This paper is partially supported by KAKENHI 18H01435.

References
[1] https://quantum-computing.ibm.com.

[2] Tilo Buschmann and Leonid V Bystrykh. Levenshtein error-correcting


barcodes for multiplexed dna sequencing. BMC bioinformatics,
14(1):272, 2013.

11
[3] A Robert Calderbank and Peter W Shor. Good quantum error-
correcting codes exist. Physical Review A, 54(2):1098–1105, 1996.

[4] Yeow Meng Chee, Han Mao Kiah, Alexander Vardy, Eitan Yaakobi,
et al. Coding for racetrack memories. IEEE Transactions on Information
Theory, 64(11):7094–7112, 2018.

[5] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N


Cleland. Surface codes: Towards practical large-scale quantum compu-
tation. Physical Review A, 86(3):032324, 2012.

[6] Daniel Eric Gottesman. Stabilizer Codes and Quantum Error Correc-
tion. PhD thesis, California Institute of Technology, 1997.

[7] Manabu Hagiwara and Ayumu Nakayama. A four-qubits code that is a


quantum deletion error-correcting code with the optimal length. arXiv
preprint arXiv:2001.08405, 2020.

[8] Janet Leahy, Dave Touchette, and Penghui Yao. Quantum insertion-
deletion channels. ArXiv, abs/1901.00984, 2019.

[9] Vladimir I Levenshtein. Binary codes capable of correcting deletions,


insertions, and reversals. In Soviet physics doklady, volume 10, pages
707–710, 1966.

[10] Ayumu Nakayama and Manabu Hagiwara. Construction of quantum


error correcting codes for single deletion errors (in japanese with english
summary). IEICE Technical Report, 119(376, IT2019-68):185–189, 2020.

[11] Ayumu Nakayama and Manabu Hagiwara. The first quantum error-
correcting code for single deletion errors. IEICE Communications Ex-
press, page 2019XBL0154, 2020.

12
Algorithm 1
1: Input: A, B ⊂ {0, 1}n . Output: P = {P1 , . . . , Pj }.
2: j := 1, P := ∅.
3: while there exist i1 ∈ [n], i2 ∈ [n]\{i1 }, b ∈ {0, 1}
such that ∆i1 ,b (A) ∩ ∆i2 ,b (A) 6= ∅ do
4: take a0 + b0 distinct elements
x1 , x2 , . . . , xa0 ∈ ∆i1 ,b (A) ∩ ∆i2 ,b (A),
y1 , y2 , . . . , yb0 ∈ ∆i1 ,b (B) ∩ ∆i2 ,b (B),
and define
Pa0 the followings:
Pj := t=1 |xt i hxt | + bs=1
P0
|ys i hys |,
P := P ∪ {Pj },
j := j + 1,
for all i ∈ [n],
∆i,b (A) := ∆i,b (A)\{x1 , . . . , xa0 },
∆i,b (B) := ∆i,b (B)\{y1 , . . . , yb0 }.
5: end while
6: while there exist i ∈ [n], b ∈ {0, 1}
such that ∆i,b (A) 6= ∅ do
7: take a0 + b0 distinct elements
x1 , x2 , . . . , xa0 ∈ ∆i,b (A),
y1 , y2 , . . . , yb0 ∈ ∆i,b (B),
and define
Pa0 the followings:
Pj := t=1 |xt i hxt | + bs=1
P0
|ys i hys |,
P := P ∪ {Pj },
j := j + 1,
∆i,b (A) := ∆i,b (A)\{x1 , . . . , xa0 },
∆i,b (B) := ∆i,b (B)\{y1 , . . . , yb0 }.
8: end while
P
9: Pj := I − P ∈P P .
10: P := P ∪ {Pj }.
11: return P

13
A = {00001001, 01101111}
∆i,b (A)
b=0 b=1
i=1 {0001001, 1101111} ∅
i=2 {0001001} {0101111}
i=3 {0001001} {0101111}
i=4 {0001001, 0111111} ∅
i=5 ∅ {0000001, 0110111}
i=6 {0000101} {0110111}
i=7 {0000101} {0110111}
i=8 ∅ {0000100, 0110111}

Table 1: ∆i,b (A) for i ∈ [8], b ∈ {0, 1}


B = {00001111, 01101001}
∆i,b (B)
b=0 b=1
i=1 {0001111, 1101001} ∅
i=2 {0001111} {0101001}
i=3 {0001111} {0101001}
i=4 {0001111, 0111001} ∅
i=5 ∅ {0000111, 0110001}
i=6 {0110101} {0000111}
i=7 {0110101} {0000111}
i=8 ∅ {0000111, 0110100}

Table 2: ∆i,b (A) for i ∈ [8], b ∈ {0, 1}


Simulator Quantum computer
Initial state Outcome:0 Outcome:1 Outcome:0 Outcome:1
|0i 100% 0% 69.922% 30.078%
|1i 0% 100% 35.669% 64.331%
1
√ (|0i + |1i)
2
50.562% 49.438% 54.565% 45.435%

Table 3: Theoretical values and experimental values for three types of initial
states

14

You might also like