Download PDF
ads:
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ads:
1
2
k ε
P
µ
L
a b
2
k k ≥ 3
Y
1
, Y
2
, ..., Y
k
∀i, j P(Y
i
= y
i
, Y
j
= y
j
) = P(Y
i
= y
i
)P(Y
j
= y
j
) ,
P
n a
1
, . . . , a
n
2
n
− 1 Y
i
Y
i
i i ∈ {0, 1}
n
/{0}
n
Y
i
=
n
m=1
a
m
i
m
(mod 2) .
Y
i
Y
j
m i
m
= j
m
a
Y
i
Y
j
G = (V, E) x D(x)
c
c =
(x,y)∈E
P(D(x) = D(y)).
|V |
c |V |
log
2
(|V |)
2
log
2
|V |
≤ 2|V |
|V |/2
n
n
n
ε n
Ω
2
n
log(1/ε)
log log 2
n
2
n
1
f = Ω(g) f g
f = O(g) f g f = Θ(g) f
g
ρ
ρ
ρ → ρ
= UρU
†
.
ρ
ρ ρ
µ(U)
µ(U) H
H(U) = H(V U) = H(UV ) V
ρ → ρ
=
dH(U) UρU
†
,
V ρ
V
†
= ρ
V ρ
= I/2
H
µ
b
1
b
2
σ
b
1
x
σ
b
2
z
µ
b
1
,b
2
ρ
=
1
4
2
i=1
2
j=1
σ
j
x
σ
i
z
ρσ
i
z
σ
j
x
= I/2 .
1
4
2
i=1
2
j=1
σ
j
x
σ
i
z
|00|σ
i
z
σ
j
x
=
1
2
2
j=1
σ
j
x
|00|σ
j
x
= I/2 .
1
k
1
1 1 ρ
k k ρ
2
µ
µ = H µ
k k
2
2
2
U |ψ
E
|ψ
F
|ψ
(U, E) = F (U |ψψ|U
†
, E(|ψ ψ|)) = ψ|U
†
E(|ψψ|) U |ψ.
F (U, E) =
ψ|U
†
E(|ψψ|) U |ψdψ.
H
|0
F (U, E) =
0|V
†
U
†
E(V |00|V
†
) UV |0dH(V ).
F
E(V |00|V
†
)
U
†
|0
|0
p = 0|V
†
U
†
E(V |00|V
†
) UV |0 .
r O(
1
√
r
)
E
p (2, 2)
(V, V
†
) V
2
2 µ
U
†
MUNU
†
OUdµ(U) =
U
†
MUNU
†
OU dH(U) ,
H
V 1
k
k
F (U, E)
U
†
U
†
U
†
U
E
E {E
m
} (E
m
E
†
m
) =
2
n
δ
mm
(E
m
) = 2
n
δ
m0
E(ρ) =
mm
χ
mm
E
m
ρE
†
m
.
χ
mm
n
χ
mm
χ
mm
E
m
E m E
†
m
F
m
(E
m
, I) =
ψ|E
†
m
E(|ψψ|) E
m
|ψdψ =
2
n
χ
mm
+ 1
2
n
+ 1
.
ψ|O
1
|ψψ|O
2
|ψdψ =
T r[O
1
]T r[O
2
] + T r[O
1
O
2
]
2
n
(2
n
+ 1)
.
E
E
E n
2
S(ρ
A
) = −T r(ρ
A
ln ρ
A
) ,
ρ
A
n S
ln n
A
n
A
n
n
2
S(ρ
A
) ≥ log
2
T r(ρ
2
A
).
tr(ρ
2
A
) ρ
2
S
T r(ρ
2
A
)
|ψψ|
|ψψ| =
P ∈{0,X,Y,Z}
n
σ
p
ξ(p)
T r(ρ
2
A
)
=
(T r
B
(|ψψ|))dH
=2
n−n
A
p : ∀j /∈A,p
j
=0
ξ
2
(p)
,
ξ(p)
2n
n n
|ψ
2n n
n
|ψ
U |ψ
U U |ψ
U
†
|ψ
U
n
U
U
2 n
2
k k
k
n k k µ(ψ)
k µ
U
µ(U)
k
n k
k O(n/ log n)
1 2
k k µ
k
µ k
n 2
(i, j) Γ
2 W
ij
µ
Γ
d
Γ
n
Γ
Γ
µ
n
Γ
n(n − 1)
n
n O(n
3
)
n
2
2
ε
2
2 O(n(n+log ε
−1
))
2
2 2
O(n log(n/ε))
k k
U(4)
µ W
ij
µ W
ij
U
i
V
j
2
W
ij
U(4)
µ
C
C C
2
O(n)
2 O(log n)
O(n log(1/ε))
2
µ
2
n
k
n H
n
O
n
H
n
O
n
2
2n
O
n
(ˆ)
ˆ
C
X
(A) ≡ XAX
†
X A
• |A A
|ψψ| |ψ
|ψ
• A| (A
†
· )
• A|B
A · B = (A
†
B)
A|B = B|A
∗
.
A B
|ψ
ψ|ψ =
|ψψ| |ψψ|
= 1
• |AB|
(B
†
· )
A
|AB| |X = |AB|X
A |A
O
n
|σ
p
≡ |σ
p
1
⊗ . . . ⊗ |σ
p
n
p ≡ (p
1
. . . p
n
) p
j
∈
{0, X, Y, Z}
σ
p
j
σ
p
|σ
q
= 2
n
δ
p,q
,
p
|σ
p
σ
p
|= 2
n
ˆ
I .
|ρ
|ρ = 2
−n/2
p
ξ(p) |σ
p
,
ξ(p)
ξ(p) = 2
−n/2
σ
p
|ρ.
|σ
0
ξ
0
= 2
−n/2
σ
0
|ρ = 2
−n/2
(ρ) = 2
−n/2
.
p
ξ
2
(p) = 2
−n
p
ρ|σ
p
σ
p
|ρ = ρ|ρ = ρ
2
|ρ |ψ ξ
2
(p)
{0, X, Y, Z}
n
4
n
ξ
2
(p)
p |0 . . . 0
1
2
(I + Z)
⊗n
2
−n
p p
i
∈ {0, Z}, ∀i
m
ˆ
G
(1)
µ
(·) ≡
W · W
†
dµ(W ).
W m µ(W)
ˆ
G
(1)
µ
m
H
m
O
m
µ H
1
k m
ˆ
G
(k)
µ
(·) ≡
W
⊗k
· W
†⊗k
dµ(W ) .
k
m O
⊗k
m
k m
k
µ k k
ˆ
G
(k)
µ
k
ˆ
G
(k)
H
H
W
⊗k
· W
†⊗k
dµ(W ) =
W
⊗k
· W
†⊗k
dH(W ) .
µ
k
|A ∈ O
⊗k
n
ˆ
G
(k)
µ
|A
µ(W ) = µ(W
†
) W ∈ O
n
ˆ
G
(k)
µ
k
ˆ
C
(k)
W
≡ W
⊗k
· W
†⊗k
ˆ
C
(k) †
W
=
ˆ
C
(k)
W
†
ˆ
G
(k) †
µ
=
ˆ
C
(k) †
W
dµ(W ) =
ˆ
C
(k)
W
†
dµ(W ) =
ˆ
C
(k)
W
dµ(W
†
).
µ(W ) = µ(W
†
)
ˆ
G
(k)
µ
ˆ
G
(k)
µ
|Π ∈ O
⊗k
n
k
H
n
µ |Π Π|
k
ˆ
G
(k)
µ
λ = 1
ˆ
G
(k)
µ
|Π = |Π;
Π|
ˆ
G
(k)
µ
= Π|
Π, W
⊗k
= 0
ˆ
G
(k)
µ
ˆ
G
(k)
µ
|A ∈ O
⊗k
n
Π|
ˆ
G
(k)
µ
|A =
ΠW
⊗k
AW
†⊗k
dµ(W ) =
W
⊗k
ΠAW
†⊗k
dµ(W )
=
[ΠA] dµ(W ) = [ΠA] = Π|A
Π W
⊗k
µ H
k
ˆ
G
(k)
H
|Π k!
S
k
S
k,n
= {|Π} ⊂ O
⊗k
n
ˆ
G
(k)
µ
S
k,n
= S
k,n
µ
ˆ
G
(k)
H
S
k,n
ˆ
G
(k)
H
|V = 0 |V S
k,n
k = 2
ˆ
G
(2)
H
|Π
k = 2 |I = |σ
0
|S
d S
d
S =
1
d
d
2
−1
p=0
α
p
⊗ α
p
{α
p
} α
p
|α
p
= d
n d = 2
n
α
p
= σ
p
|I |S
I|S = (S) {|γ
i
} S
2,n
¯
S ≡ 2
n
S − I =
p=
0
σ
p
⊗ σ
p
≡
p=
0
σ
p,p
I|
¯
S
= 0
{|γ
i
} ≡
1
2
n
I,
1
2
n
√
2
2n
− 1
¯
S
ˆ
G
(2)
H
=
i
|γ
i
γ
i
| .
ˆ
G
(k)
H
1 × 1 |σ
0
(4
n
− 1) × (4
n
− 1)
1
4
n
−1
k ε
k n
k
k
k
k
ˆ
G
ˆ
G
= sup
d
aux
sup
ρ
T r
ˆ
G ⊗ I
d
aux
(ρ)
,
d
aux
ˆ
G
1
ˆ
G
2
ρ
ˆ
G
1
−
ˆ
G
2
k ε k
ε
µ k ε k
ˆ
G
(k)
µ
ˆ
G
(k)
µ
−
ˆ
G
(k)
H
≤ ε .
2
µ(U)
2 ε
max
Λ
U(Λ(U
†
ρU))U
†
dµ(U) −
V (Λ(V
†
ρV ))V
†
dH(V )
≤
ε
d
2
,
Λ d
2
n
n
µ 2 ε
2
ε
Ω
x ∈ Ω
y ∈ Ω P (x, y)
|Ω| × |Ω|
Ω
ν
(t+1)
(y) =
x∈Ω
ν
(t)
(x) P (x, y) ,
ν
(t+1)
= ν
(t)
P .
ν
(t)
(x)
X
(0)
= x t
z ∈ Ω
ν
t
= ν
0
P
t
π P π = πP
P π
ν νP
t
→ π
π P
P p, q ∈ Ω
p q
∃t P
t
(p, q) = 0
p
P (p, p) = 0
Ω
ν, π
Ω
ν − π
T V
≡ max
A⊂Ω
|ν(A) − π(A)| =
1
2
x∈Ω
|ν(x) − π(x)| .
a ∈ Ω
ν π 1/2
A a ∈ A ν π
A (1 + ν − π
T V
)/2
t
ν
t
= ν
0
P
t
P
ν
0
π P
d(t) ≡ sup
ν
0
ν
t
− π
T V
,
d(t)
P
t
mixP
≡ min{t : d(t) ≤ 1/4}
d = 1/4
< 1/2
t
mixP
(ε) ≡ min{t : d(t) ≤ ε} ≤ log
2
(ε
−1
) · t
mixP
.
P
P 1 > λ > −1 ∆
1 −1
∆ = min
λ
i
<1
{1 − |λ
i
|} .
e
−t ∆
t
rel
= 1/∆
t
2−mix
(ε) ≤
1
∆
ln
1
ε
,
t
2−mix
(ε) = min{t : max
µ
µP
t
− π
2
≤ ε}
2
ν − π
2
≡
x
(ν(x) − π(x))
2
.
t
mix
(ε) ≤
1
∆
ln
1
ε π
min
,
π
min
Ω
∆
1 − ∆
≥
log(1/2ε)
t
mix
(ε)
.
n |Ω| ∼ ( )
n
π
min
≤ ( )
−n
n
µ W
ij
µ = H U(4)
2
µ
µ
L
µ
W
ij
µ
L
W
ij
= (U
i
⊗ V
j
)C
ij
(U
i
⊗ V
j
) ⊗ I
k=i,j
.
C
ij
µ
U
i
V
j
U
i
V
j
k
µ (U
i
⊗V
j
)µ(U
i
⊗V
j
) = µ
1 U
i
V
j
U
i
V
j
C µ(C) = δ(C −C
0
)
µ
C
µ
L
µ
H
k
ˆ
G
(k)
µ
L
ij
(·) =
W
⊗k
ij
· W
†⊗k
ij
dU
i
dU
i
dV
j
dV
j
dµ(C) .
O
(i
1
j
1
)
2
⊗ O
(i
2
j
2
)
2
⊗ . . . ⊗ O
(i
k
j
k
)
2
W
ij
U
i
, V
j
, U
i
, V
j
ˆ
G
(k)
µ
L
ij
=
=
ˆ
G
(k)
H
i
1
i
2
...i
k
⊗
ˆ
G
(k)
H
j
1
j
2
...j
k
ˆ
C
i
1
j
1
⊗
ˆ
C
i
2
j
2
⊗ . . . ⊗
ˆ
C
i
k
j
k
dµ(C)
ˆ
G
(k)
H
i
1
i
2
...i
k
⊗
ˆ
G
(k)
H
j
1
j
2
...j
k
.
ˆ
G
(k)
H
a
1
a
2
...a
k
k k
ˆ
C
ˆ
C
C
C
ˆ
G
(k)
H
ˆ
C
†
C
=
ˆ
C
C
†
ˆ
G
(k)
µ
L
ij
µ µ(C) = µ(C
†
)
ˆ
G
(k)
C
ij
C
ˆ
G
(k)
µ
L
ij
A = A
i
⊗ A
j
B = B
i
⊗ B
j
µ
L
µ
L
(BW
ij
A) = µ
L
(W
ij
) ;
µ, ν
µ(C) = Bν(C)A)
µ
L
(W
ij
) = ν
L
(W
ij
) .
C, C
= BCA
µ
BCA
(W
ij
) = µ
C
(W
ij
) .
W
ij
C
ij
U
i
V
j
W
ij
t i, j
t + k t + l
U
i
V
j
U
i
V
j
t
U
i
, V
j
U
i
, V
j
C
2
Passo 1 Passo 2 Passo 3
U
1
C
1
· · ·
U
i
U
3
C
3
· · ·
U
ii
V
1
C
1
_ _ _ _ _ _
_ _ _ _ _ _
U
2
C
2
V
3
C
3
_ _ _ _ _ _
_ _ _ _ _ _
· · ·
U
iii
V
2
C
2
_ _ _ _ _ _
_ _ _ _ _ _
· · ·
U
iv
n
|ψ
0
W
ij
|ψ
t+1
= W
ij
|ψ
t
.
|ψ
t
ξ
t+1
(q) = 2
−n
p
σ
q
|
ˆ
C
W
ij
|σ
p
ξ
t
(p) .
W
ij
(i, j)
µ
µ
ξ
t+1
(q)
ξ
t+1
(q)
µ
≡
1
n(n − 1)
i=j
ξ
t+1
(q)dµ(W
ij
)
=
2
−n
n(n − 1)
i=j
p
σ
q
|
ˆ
G
(1)
µ
ij
|σ
p
ξ
t
(p)
µ
,
ˆ
G
(1)
µ
ij
i, j
t ξ
t
(q)
µ
ρ
t
ˆ
G
(1)
µ
ij
i, j
ξ
t+1
(q)
µ
=
2
−2
n(n − 1)
i=j
p
δ
p
/ij
,q
/ij
σ
q
i
q
j
ˆ
G
(1)
µ
ij
σ
p
i
p
j
ξ
t
(p)
µ
.
p
/ij
, q
/ij
i, j p q
ˆ
G
(1)
µ
t + 1
ξ
t+1
(q)ξ
t+1
(q
)
µ
=
2
−2n
n(n − 1)
i=j
p,p
σ
q,q
|
ˆ
G
(2)
µ
ij
|σ
p,p
ξ
t
(p)ξ
t
(p
)
µ
=
2
−4
n(n − 1)
i=j
p,p
δ
p
/ij
p
/ij
q
/ij
, q
/ij
σ
q
i
q
j
q
i
q
j
ˆ
G
(2)
µ
ij
σ
p
i
p
j
p
i
p
j
ξ
t
(p)ξ
t
(p
)
µ
|σ
p,q
≡|σ
p
⊗|σ
q
ˆ
G
(2)
µ
ij
(·) ≡
W
⊗2
ij
· W
†⊗2
ij
dµ(W
ij
)
2 i, j
4
4
× 4
4
ˆ
G
(2)
µ
k
k
k
ˆ
G
(k)
µ
µ
L µ
µ H U(4)
C = CNOT
µ
ξ
t+1
(q)ξ
t+1
(q
)
µ
= δ
q,q
p
ξ
2
t
(p)
µ
P
µ
(p, q) ,
P
µ
(p, q) ≡
2
−2n
n(n − 1)
i=j
σ
q,q
|
ˆ
G
(2)
µ
ij
|σ
p,p
q
P
µ
(p, q) =
p
P
µ
(p, q) = 1 .
q = q
ξ
2
(p)
P
µ
P
µ
µ P
µ
(p, q)
p = p
P
µ
(p, q)
n(n − 1)
P
µ
ij
(p, q) ≡ 2
−2n
σ
q,q
|
ˆ
G
(2)
µ
ij
|σ
p,p
= 2
−4
δ
p
/ij
q
/ij
σ
q
i
q
j
,q
i
q
j
ˆ
G
(2)
µ
ij
σ
p
i
p
j
,p
i
p
j
P
µ
(p, q)
q
P
µ
ij
(p, q) = 2
−2n
q
σ
q,q
|
ˆ
G
(2)
µ
ij
|σ
p,p
= 2
−2n
S|
ˆ
G
(2)
µ
ij
|σ
p,p
= 2
−2n
S|σ
p,p
= 1.
|S =
q
|σ
q,q
n
p
P
µ
ij
(p, q) = 2
−2n
σ
q,q
|
ˆ
G
(2)
µ
ij
|S = 2
−2n
σ
q,q
|S = 1
P
µ
ij
(p, q)
σ
q,q
|
ˆ
G
(2)
µ
ij
|σ
p,p
=
2
σ
q
W
ij
σ
p
W
†
ij
dµ(W
ij
); .
∗
A = A
†
∗
σ
q
W
ij
σ
p
W
†
ij
=
σ
q
W
ij
σ
p
W
†
ij
†
=
W
ij
σ
p
W
†
ij
σ
q
=
σ
q
W
ij
σ
p
W
†
ij
.
P
µ
ij
P
µ
µ
q = q
µ
ˆ
G
(2)
µ
ij
P
µ
ˆ
G
(2)
H
ij
(P
H
ˆ
G
(2)
C
ij
(P
C
)
µ = H
ˆ
G
(2)
H
ij
=
1
16
|σ
00,00
σ
00,00
|+
1
240
(kl),(k
l
)=00
|σ
kl,kl
σ
k
l
,k
l
|
⊗
ˆ
I
= i, j
(i
1
j
1
, i
2
j
2
)
µ
k
ˆ
G
(2)
µ
ij
=
ˆ
G
(2)
H
i
1
i
2
⊗
ˆ
G
(2)
H
j
1
j
2
ˆ
C
i
1
j
1
⊗
ˆ
C
i
2
j
2
dµ(C)
ˆ
G
(2)
H
i
1
i
2
⊗
ˆ
G
(2)
H
j
1
j
2
.
ˆ
G
(2)
H
i
1
i
2
⊗
ˆ
G
(2)
H
j
1
j
2
O
(i
1
j
1
)
2
⊗ O
(i
2
j
2
)
2
|I
i
1
i
2
|I
j
1
j
2
; |I
i
1
i
2
¯
S
j
1
j
2
;
¯
S
i
1
i
2
|I
j
1
j
2
;
¯
S
i
1
i
2
¯
S
j
1
j
2

.
ˆ
G
(2)
µ
ij
ˆ
C
i
1
j
1
⊗
ˆ
C
i
2
j
2
dµ(C)
µ
ˆ
G
(2)
µ
ij
q = q
p = p
σ
q,q
|
ˆ
G
(2)
µ
ij
|σ
p,p
= δ
q,q
δ
p,p
σ
q,q
|
ˆ
G
(2)
µ
ij
|σ
p,p
.
µ = H
ˆ
G
(2)
H
ij
|σ
p,p
= 0
p = p
σ
q,q
|
ˆ
G
(2)
H
ij
= 0 q = q
σ
i
1
j
1
00
σ
i
2
j
2
00
;
k=0
σ
i
1
j
1
0k
σ
i
2
j
2
0k
;
k=0
σ
i
1
j
1
k0
σ
i
2
j
2
k0
;
k,l=0
σ
i
1
j
1
kl
σ
i
2
j
2
kl
.
σ
ab
i
1
j
1
i
2
j
2
ˆ
G
(2)
H
i
1
i
2
⊗
ˆ
G
(2)
H
j
1
j
2
|σ
p,p
= 0
p = p
ˆ
G
(2)
µ
ij
|σ
p,p
= 0 p = p
σ
q,q
|
ˆ
G
(2)
µ
ij
= 0 q = q
µ = H
µ
L
H µ
L
n = 2 n = 1
µ = H
σ
q
ij
,q
ij
ˆ
G
(2)
H
ij
σ
p
ij
,p
ij
,
H
µ
σ
q
ij
,q
ij
ˆ
G
(2)
µ
ij
σ
p
ij
,p
ij
=
=
r
ij
,r
ij
s
ij
,s
ij
α
q
ij
,q
ij
,s
ij
s
ij
σ
s
ij
,s
ij
ˆ
C
i
1
j
1
⊗
ˆ
C
i
2
j
2
dµ(C)
σ
r
ij
,r
ij
α
r
ij
r
ij
,p
ij
,p
ij
,
ˆ
I = N
r
ij
r
ij
σ
r
ij
,r
ij

σ
r
ij
,r
ij
α
r
ij
r
ij
,p
ij
,p
ij
≡ N
σ
r
ij
,r
ij
ˆ
G
(2)
H
i
1
i
2
⊗
ˆ
G
(2)
H
j
1
j
2
σ
p
ij
,p
ij
= N
σ
r
i
,r
i
ˆ
G
(2)
H
i
1
i
2
σ
p
i
,p
i
σ
r
j
,r
j
ˆ
G
(2)
H
j
1
j
2
σ
p
j
,p
j
µ
µ
L
µ
L
µ
L
(U
i
, V
j
) (U
i
, V
j
)
W
ij
ˆ
G
(2)
H
i
1
i
2
⊗
ˆ
G
(2)
H
j
1
j
2
p, q
p
, q
C
ˆ
C
ˆ
C
Clifford
|σ
ab
= ±|σ
cd
, ∀σ
ab
.
µ
C
ˆ
C
i
1
j
1
⊗
ˆ
C
i
2
j
2
σ
i
1
j
1
ab
σ
i
2
j
2
ab
σ
ab
i
1
i
2
j
1
j
2
(U
i
, V
j
) W
ij
p
= q
σ
p
,q
|
ˆ
G
(2)
C
= 0
µ
C
C
(U
i
, V
j
)
(U
i
, V
j
) W
ij
µ
C
C = CNOT (U
i
, V
j
)
µ
µ
µ
µ
H
µ
H
C
C ν
C
P
µ
P
µ
P
µ
P
µ
(p, p
)
P
µ
(p, p
)
µ
W
ij
P
µ
(p, p
) = 0
p, p
n I = 2
−n
σ
0
ξ
2
(p) = 2
−2n
δ
p
0
P
µ
(p, p
)
I ξ
2
(p) = δ
p
0
P
µ
P
µ
π = (1 . . . 1) πP = π
δ
p
0
P
µ
ξ
2
t
(p)
ξ
2
t+1
(p)
= ξ
2
t
(p)P
µ
ξ
2
t
(p)
ξ
2
t+1
(p)
≺ ξ
2
t
(p)
S = −
i
x
i
ln x
i
S(
ξ
2
t+1
(p
)) ≥ S(ξ
2
t
(p))
δ
p
0
(i, j) Γ
W
ij
P (p, q)
Λ p, q
P (q
1
, . . . , q
n
; p
1
, . . . , p
n
) = P (q
Λ(1)
, . . . , q
Λ(n)
; p
Λ(1)
, . . . , p
Λ(n)
)
Λ (1 . . . n)
µ = H µ = µ
C
x, y, z
A
i
, A
j
, B
i
, B
j
X, Y, Z
P
µ
ij
(q, p) P
µ
(q, p)
p
i
q
j
X, Y Z
P
µ
(q, p)
p
i
, q
j
P
µ
{0, X, Y, Z}
n
P
µ
(p, q)
p q
µ = H
ˆ
G
(2)
H
ij
1×1 00, 00 15×15
1
m
F
m
F
m
m × m
1 P
µ
p
p
i
, p
j
p
p
i
= p
j
= 0
(p
i
, p
j
) = (0, 0)
{0, X, Y, Z}
2
/(0, 0)
C = CNOT
a b
µ
P
µ
p q
p
i
, p
j
p
Γ k = i, j
q
k
= p
k
q
i
, q
j
p
i
= p
j
= 0 q
i
= q
j
= 0
p
i
= 0, p
j
= 0
a, q
i
= r, q
j
= 0
b, q
i
= r, q
j
= s
1 − a − b, q
i
= 0, q
j
= r
r, s {X, Y, Z}
a =
3
32
σ
X0,X0
|
ˆ
G
(2)
µ
|σ
0X,0X
+ σ
0X,0X
|
ˆ
G
(2)
µ
|σ
X0,X0
b =
9
32
σ
XX,XX
|
ˆ
G
(2)
µ
|σ
0X,0X
+ σ
XX,XX
|
ˆ
G
(2)
µ
|σ
X0,X0
p
i
= 0, p
j
= 0 i ↔ j
p
i
, p
j
= 0
b/3, q
i
= r, q
j
= 0
b/3, q
i
= 0, q
j
= r
1 − 2b/3, q
i
= r, q
j
= s
r, s {X, Y, Z}
ˆ
G
(2)
µ
ij
P
µ
(p, q) =
2
−2n
n(n − 1)
(i,j)∈Γ
1
2
σ
q,q
|
ˆ
G
(2)
µ
ij
+
ˆ
G
(2)
µ
ji
|σ
p,p
P
µ
¯
P
µ
ij
=
1
2
P
µ
ij
+ P
µ
ji
P
µ
ij
(i, j)
¯
P
µ
ij
i, j p
p
i
p
j
→ q
i
q
j
¯
P
µ
ij
P(p
i
p
j
→ q
i
q
j
) = 2
−4
σ
q
i
q
j
,q
i
q
j
1
2
ˆ
G
(2)
µ
ij
+
ˆ
G
(2)
µ
ji
σ
p
i
p
j
,p
i
p
j
=
1
32
σ
q
i
q
j
,q
i
q
j
ˆ
G
(2)
µ
ij
σ
p
i
p
j
,p
i
p
j
+
σ
q
j
q
i
,q
j
q
i
ˆ
G
(2)
µ
ij
σ
p
j
p
i
,p
j
p
i
r s 0X → X0 0X → XX
¯
P
µ
ij
µ |σ
00,00
ˆ
G
(2)
µ
ij
σ
q
i
q
j
,q
i
q
j
ˆ
G
(2)
µ
ij
+
ˆ
G
(2)
µ
ji
|σ
00,00
q
i
= q
j
= 0
σ
00,00
|
ˆ
G
(2)
µ
ij
σ
p
i
p
j
,p
i
p
j
= 0 p
i
= p
j
= 0
q
i
= q
j
= 0
p
i
, p
j
, q
i
q
j
= 0
X, Y Z
p
i
= 0, p
j
= X q
i
= X, q
j
= 0
p
i
= 0, p
j
= Y q
i
= Z, q
j
= 0
a b
1 − a − b = 3 · P(0X → 0X) =
3
32
σ
0X,0X
|
ˆ
G
(2)
µ
|σ
0X,0X
+ σ
X0,X0
|
ˆ
G
(2)
µ
|σ
X0,X0
¯
P
µ
ij
¯
P
µ
ij
i, j
XX → X0
XX → 0X
c ≡
1
32
σ
X0,X0
|
ˆ
G
(2)
µ
|σ
XX,XX
+ σ
0X,0X
|
ˆ
G
(2)
µ
|σ
XX,XX
P(XX → X0) =
b
9
=
1
32
σ
XX,XX
|
ˆ
G
(2)
µ
|σ
0X,0X
+ σ
XX,XX
|
ˆ
G
(2)
µ
|σ
X0,X0
ˆ
G
(2)
µ
C
ˆ
G
(2)
µ
P
µ
ij
¯
P
µ
ij
0X
1 =
p
i
p
j
¯
P
µ
ij
(0X, p
i
p
j
) =
1
32
p
i
p
j
σ
0X,0X
|
ˆ
G
(2)
µ
ij
+
ˆ
G
(2)
C
ji
σ
p
i
p
j
,p
i
p
j
=
1
32
p
i
p
j
σ
0X,0X
|
ˆ
G
(2)
µ
ij
σ
p
i
p
j
,p
i
p
j
+ σ
X0,X0
|
ˆ
G
(2)
µ
ij
σ
p
j
p
i
,p
j
p
i
=
3
32
σ
0X,0X
|
ˆ
G
(2)
µ
ij
|σ
X0,X0
+ σ
X0,X0
|
ˆ
G
(2)
µ
ij
|σ
0X,0X
+
3
32
σ
0X,0X
|
ˆ
G
(2)
µ
ij
|σ
0X,0X
+ σ
X0,X0
|
ˆ
G
(2)
µ
ij
|σ
X0,X0
+
9
32
σ
0X,0X
|
ˆ
G
(2)
µ
ij
|σ
XX,XX
+ σ
X0,X0
|
ˆ
G
(2)
µ
ij
|σ
XX,XX
= a + (1 − a − b) + 9 c
c = b/9
ˆ
G
(2)
H
i
1
i
2
⊗
ˆ
G
(2)
H
j
1
j
2
a =
1
96
j,k∈{X,Y,Z}
2
σ
0j
Cσ
k0
C
†
+
2
σ
j0
Cσ
0k
C
†
dµ(C)
b =
1
96
i,j,k∈{X,Y,Z}
2
σ
ij
Cσ
k0
C
†
+
2
σ
ij
Cσ
0k
C
†
dµ(C)
a b
a = 1/5 b = 3/5
µ
C
a b
C
C(α
X
, α
Y
, α
Z
) = exp (i [α
X
σ
XX
+ α
Y
σ
Y Y
+ α
Z
σ
ZZ
]) ,
α
X
α
Y
α
Z
a b
α
X
, α
Y
, α
Z
[C(α
X
, α
Y
, α
Z
), σ
0X
± σ
X0
] = 2(α
Y
∓ α
Z
)(σ
ZY
± σ
Y Z
)
[C(α
X
, α
Y
, α
Z
), σ
ZY
± σ
Y Z
] = −2(α
Y
∓ α
Z
)(σ
X0
± σ
0X
)
X, Y, Z
a =
1
6
i=j
sen
2
(2α
i
) sen
2
(2α
j
)
b =
1
3
i=j
sen
2
(2α
i
) cos
2
(2α
j
)
α
X,Y,Z
π/4 ≥ α
X
≥ α
Y
≥ |α
Z
| ≥ 0
a b
a b
a + b ≤ 1
µ
C
b ≤ 2/3
C
Cσ
A0
C
†
=
ij
x
A
ij
σ
ij
; A = X, Y, Z γ
A
=
i,j=0
(x
A
ij
)
2
C γ
A
≤ 1
b
1
6
A
γ
A
Cσ
Y 0
C
†
= i
ij
x
X
ij
σ
ij
kl
x
Z
kl
σ
kl
= i
ij,kl
x
X
ij
x
Z
kl
σ
i
σ
k
⊗ σ
j
.σ
l
.
σ
i
, σ
j
, σ
k
, σ
l
= σ
0
σ
i
σ
k
σ
j
σ
l
σ
0
γ
X
γ
Z
γ
Y
γ
Y
≤ 1 −
i=j
k=l
x
X
ij
x
Z
kl
2
= 1 − γ
X
γ
Z
,
γ
X
+ γ
Y
+ γ
Z
≤ 1 + γ
X
+ γ
Z
− γ
X
γ
Z
≤ 2 ,
b
b
C
α
X,Y,Z
b = 0 C
α
i
≡ 0 α
i
≡ π/4
i = X, Y, Z
00 ↔ 00 0X ↔ 0X Y Z ↔ XY
X0 ↔ XX 0Y ↔ ZY XZ ↔ Y Y
Y 0 ↔ Y X 0Z ↔ ZZ ZX ↔ ZX
Z0 ↔ Z0
00 ↔ 00 0X ↔ Y Z XX ↔ XX
X0 ↔ ZY 0Y ↔ XZ Y Y ↔ Y Y
Y 0 ↔ ZX ZZ ↔ ZZ
Z0 ↔ 0Z XY ↔ Y X
C
n
P
µ
p = 0 b = 0
p q
b = 0
C
Cσ
ij
C
†
= ±σ
kl
k, l.
α
i
σ
XY
XY =
1
−i
−i
1
a, b
±
C
2
= ±I
a b
σ
0k
σ
j0
j, k = 0
n
1
n
2
C
σ
0k
σ
k0
σ
ij
i, j = 0 n
3
n
4
a b
a =
1
6
(n
1
+ n
2
); b =
1
6
(n
3
+ n
4
)
CNOT CZ : a = 0, b =
2
3
; XY DCNOT : a =
1
3
, b =
2
3
b a = 1, b = 0
b 0 2/3
b = 2/3
n
3
n
4
n
3
, n
4
≤ 2
n
3
≥ 1 n
3
= 3
Cσ
X0
C
†
= ±σ
kl
; k, l = 0 Cσ
Y 0
C
†
= ±σ
mn
; m = 0 n = 0.
C
C
Cσ
Z0
C
†
= ±iσ
k
⊗ σ
l
σ
n
± iσ
k
σ
m
⊗ σ
l
l = n l = n
n
3
= 1
n
4
= 1 b 0, 1/3
2/3 n
3
= n
4
n
1
= 2 Cσ
X0
C
†
= ±σ
0k
Cσ
Y 0
C
†
= ±σ
0l
Cσ
Z0
C
†
= ±σ
0m
n
5
σ
0k
, k = 0
n
5
= 2
n
3
= 0 n
4
= 2
n
3
= 0 n
4
= 2 n
1
+ n
3
+ n
5
= 3 n
1
n
5
= 2
n
1
= 3, n
5
= 0 n
1
= 3
C
σ
A0
→ ±σ
0A
, ∀A ∈ X, Y, Z σ
0X
→ ±σ
j0
; σ
0Y
→ ±σ
kl
j, k, l = 0
Cσ
Y Y
C
†
= ±σ
k
⊗ σ
Y
σ
l
Cσ
ZY
C
†
= ±σ
k
⊗ σ
Z
σ
l
l = Y l = Z
n
3
= 0 ⇒ n
4
= 0
n
4
= 0 ⇒ n
3
= 0 b = 1/3
C = exp(iα
Z
σ
ZZ
)
Ising : a = 0; b =
2
3
sen
2
(2α
Z
)
b α = 0 C
α = π/4 C CZ CNOT
B α
X
= π / 4, α
Y
=
π/8, α
Z
= 0
CN OT
B
B
B : a =
1
6
; b =
2
3
µ
a b a(C) b (C)
µ
C
a =
a(C)dµ(C) b =
b(C)dµ (C)
b ≤ 2/3
µ b = 0
em
dµ(C) = 0
0 < b ≤ 2/3
b
b = 2/3
π(x)P (x, y) = π(y)P (y, x), πP = π .
P
µ
µ
ˆ
G
(2)
µ
ν
{0, X, Y, Z}
(n)
P
µ
π
{0, X, Y, Z}
(n)
/ {0}
(n)
{0}
(n)
P
µ
P
µ
{0, X, Y, Z}
(n)
/{0}
(n)
P
µ
{0, X, Y, Z}
(n)
/ {0}
(n)
P
µ
P
µ
π(p) = 1/(4
n
− 1) P
µ
π
P
µ
P
µ
P (q, q) > 0, ∀q ∈ Ω
Q
t q p P
t
(q, p) > 0
q p B
0
= {i ∈ [1, n]|q
i
= p
i
}
p q
j ∈ B
0
p
q
(1)
p j
p q
Γ Γ
Γ
P
µ
µ P P
µ
Ω Ω
a
, Ω
b
, . . . ⊂ Ω
P(Ω
a
, Ω
b
) =
x∈Ω
a
y∈Ω
b
P (x, y)
p(x, y)
Ω
µ
Ω
ν
Ω
µ
P (p
1
, p
2
)
p
1
p
2
P i p 0 X, Y, Z
Ω q ∈ {0, 1}
n
= Ω
Q
Ω
q
Ω q
q 1
Ω
q
i j
Ω
q
Q P Ω
Q
= {0, 1}
n
/{0}
n
Q
(i,j)
Q
(i,j)
q
i
q
j
q
i
q
j
Q(q, q
) =
p∈Ωq
p
∈Ωq
P (p, p
) .
P Q
Q =
1
n(n−1)
i=j
Q
(i,j)
q,
q
∈ Ω
Q
i j Q
(i,j)
Q
(i, j)
Q
(i,j)
= aT
(i,j)
+ (1 − a)M
(i,j)
.
T
(i,j)
i j M
(i,j)
Q =
i,j
Q
(i,j)
a
Q = aT + (1 − a)M
T ≡
1
n(n−1)
(i,j)∈Γ
T
(i,j)
M ≡
1
n(n−1)
(i,j)∈Γ
M
(i,j)
q
M
(i,j)
1 − a − b
1 − a
b
1 − a
1 − a − b
1 − a
b
1 − a
b/3
1 − a
b/3
1 − a
1 − a − 2b/3
1 − a
M
(i,j)
q
i
q
j
q
i
q
j
L =
M + I
2
.
L M
L
L
M
Q
L
Γ
Γ
L
L
(i)
p Γ L
Γ
d
L
L =
1
n
i
L
(i)
,
L
(i)
2 × 2 p
i
L
(i)
0→1
=
b
1 − a
H
n − 1
, L
(i)
1→0
=
b
3(1 − a)
H −1
n − 1
, e L
(i)
0→0
= 1 −L
(i)
0→1
; L
(i)
1→1
= 1 −L
(i)
1→0
,
H p p
i
M
(i,j)
i j M L
p q
P
p
k
= 0 q
k
= 1
(i, j) M
(i,j)
k
1 (i, j)
2H
n(n−1)
b/2(1 −a)
P =
1
2
2H
n(n−1)
b
1−a
P L
(i)
0→1
1
n
i
p
k
= 1 q
k
= 0
L H
p
[L, T ] = 0
[M, T ] = 0
π L
T Q L π
q
0
Q L
π(q) =
1
4
n
− 1
3
H(q)
; .
π =
0 Q
P
π
T
M L
π
0
{0, 1}
n
/
0 L
Q Q
a 1 − a
M
Q
M a (1 − a) M
T
Q
Q M
L
L q
q
Q
Z
Ω
ζ
= {1, 2, . . . , n} Z(n, m)
n m
(q
i
, q
j
) = (0, 0) (1, 1)
H ±1
Z
Z(H, H + 1) = b H (n − H)
n
2
−1
,
Z(H, H − 1) =
b
3
H (H − 1)
n
2
−1
,
Z(H, H) = 1 − Z(H, H − 1) − Z(H, H + 1) = 1 −
2bH(3n − 2H − 1)
3n(n − 1)
,
H ∈ Ω
ζ
b
p H
H
(p
i
, p
j
) = (0, 1) (p
i
, p
j
) = (1, 0)
H(n −H)
n
2
−1
Q b
Z H
p Z
Q
Z Q
Z
Q
n
H
Q
π
ζ
(H) =
3
H
n
H
4
n
− 1
.
Z
Q
Z Q
t
mixZ
= Θ(n log n) ∆
Z
= Ω(1/n) b = 3/5
b = 3/5
b ≤ 2/3
1−b
b
b = 2/3 b
t
mix
= Θ(n log n)
b ∈ (0, 2/3]
Z
b a Z
b
a Z
CNOT XY
H
b
b Z
b = 3/5
b = 2/3
2
n
2
P
2
Q
L L
Q
2 P
2
n
n
C = CNOT
Q
O(n
3
)
U(4)
2 ε
O(n(n + log ε
−1
))
2 O(n log(n/ε))
O(n log(n/ε))
P
Z
Z
H
H
Z H
H
H ∈ [1, n
δ
] 0 < δ < 1/2 H ∈ [n
δ
/2, θn]
H ∈ [θn/2, n]
Z O(n log n)
P
Z P
ε O(n ln n/ε)
Z
n
2
n
n
n
n
2
n
2
n
1 − ε
n
n(ln n + c) < e
−c
t
mix
(ε) < n ln(n/ε)
P
p
i
p
P p
i
, p
j
p
i
(p
i
, p
j
) = (0, 0)
Z
O(n ln n) n
H = 3n/4
(p
i
, p
j
)
∈ {0, X, Y, Z}
2
P
= (000)
∆ = O(1/n)
∆ = O(1/n)
t
mix
= O(n(n + log
2
(1/ε)))
2
P
2
P
U(4)
XY CN OT ∆ = Θ(1/n)
ε O(n(n + log ε
−1
))
2
O(n log(n/ε))
2
O(n log ε
−1
) 2 2
ε O(n log(nε
−1
))
O(n(n + log ε
−1
)) 2
P
O(n log(n/ε))
Z
Z
Q
O(n log n)
Q
Z
P Q
L
L
L
Q
L M M Q L
M
L M
L
L
2
M
M −2/3 − 1/3(n − 1)
M
1
6
(1 −
1
n−1
) + δ
i
δ
i
≥ 0 ∀i
M =
1
6
(1 −
1
n−1
) + δ
1
···
1
6
(1 −
1
n−1
) + δ
2
···
p M
M
M
(i,j)
(0, 0) (1, 1) (1/2)(1 − 1/(n − 1))
1 − 2b/3(1 − a)
a + b ≤ 1 1 −2b/3(1 −a) ≥ 1/3
p M
M(p, p) α ≡ (1/6)(1 − 1/(n − 1))
M
1 − α α
M = αI + (1 − α)B, B ≡ (M − αI)/(1 − α) .
B −1 1
1 M
≥ α + (1 − α)(−1) = −1 + (2/6)(1 − 1/(n − 1))
n M
M
1 n
Ω(n)
M ∆ = O(1/n)
[−1, −2/3 −1/3(n −1)] M
(0, 0) (1, 1) H
[H(H −1) + (n − H)(n − H − 1)]/[n(n − 1)] (1/2)(1 − 1/(n − 1))
Q
L t
mixQ
≤
1
2(1−a)
t
mixL
L =
1
2
I +
1
2
M
M
t
mixL
= 2t
mixM
Q = aT + (1 − a)M T, M Q
t
mixQ
≤
1
(1−a)
t
mixM
O(n log n)
L Ω A
Ω × Ω A Ω
L A
L
t ν
(t)
(x, y) Ω × Ω
ν
(t)
1
(x) =
y∈Ω
ν
(t)
(x, y) ν
(t)
2
(y) =
x∈Ω
ν
(t)
(x, y)
ν
(t+1)
= ν
(t)
A; ν
(t+1)
1
= ν
(t)
1
L; ν
(t+1)
2
= ν
(t)
2
L
A = L ⊗ L
ν(x, y) = ν
1
(x)ν
2
(y)
X
t
Y
t
X
t
Y
t
X
s
= Y
s
⇒ X
t
= Y
t
, t ≥ s
τ (x, y)
X
0
= x Y
0
= y
L
d(t)
d(t) ≤ max
x,y∈Ω
P(τ (x, y) ≥ t) .
A
t
L τ
P
(
τ
> a
)
≤
τ
a
.
L
L
i
A
p
(1)
p
(2)
H
1
H
2
D
i p
(1)
i
= p
(2)
i
p
(1)
i
= p
(2)
i
L p
(1)
i
= p
(2)
i
P
1
(0 → 1) = P
1
(0 → 1|00) =
P(00 → 11) + P(00 → 10) = min{L
(1)
01
, L
(2)
01
} + max{0, L
(1)
01
− L
(2)
01
} = L
(1)
01
P(00 → 00) ≡ 1 − max{L
(1)
01
, L
(2)
01
} P(11 → 00) ≡ min{L
(1)
10
, L
(2)
10
}
P(00 → 11) ≡ min{L
(1)
01
, L
(2)
01
} P(11 → 11) ≡ 1 − max{L
(1)
10
, L
(2)
10
}
P(00 → 10) ≡ max{0, L
(1)
01
− L
(2)
01
} P(11 → 10) ≡ max{0, L
(1)
10
− L
(2)
10
}
P(00 → 01) ≡ max{0, L
(2)
01
− L
(1)
01
} P(11 → 01) ≡ max{0, L
(2)
10
− L
(1)
10
}
O(n log n)
P(D → D+1) ≡ P
+
D
p
(1)
i
= p
(2)
i
(n − D)/n γ
1
b
≡ b/(1 − a)
P
+
P
+
=
n − D
n
γ
b
3
|H
1
− H
2
|
n − 1
+ (1 − γ)b
|H
1
− H
2
|
n − 1
=
n − D
n
b
|H
1
− H
2
|
n − 1
1 −
2γ
3
.
D (p
(1)
i
, p
(2)
i
) = (0, 1) (1, 0)
L
i
D/n (0
,
1) D
P
−
=
D
n
b
H
2
n − 1
1 − b
H
1
− 1
3(n − 1)
+
1 −
b
H
2
n − 1
b
H
1
− 1
3(n − 1)
=
D
n
b
3(n − 1)
3H
2
+ H
1
− 1 −
2b
(n − 1)
(H
2
(H
1
− 1))
=
D
n
b
3(n − 1)
3H
2
+ (H
1
− 1)
1 − 2b
H
2
n − 1

.
(1, 0) H
1
→ H
2
H
2
→ H
1
H
12
H
1
H
2
P
−
=
D
n
b
3(n − 1)
3H
12
+ (H
21
− 1)
1 − 2b
H
12
n − 1

.
E(D → D − 1) ≡ E
−
±1
E
−
= P
−
(1) + P
+
(1 + E(D + 1 → D) + E
−
) + (1 − P
−
− P
+
)(1 + E
−
)
≤ P
−
(1) + P
+
(1 + 2E
−
) + (1 − P
−
− P
+
)(1 + E
−
)
= E
−
− E
−
(P
−
− P
+
) + 1 .
E(D + 1 → D) ≤ E(D → D − 1)
D D
E
−
≤ 1/(P
−
− P
+
) .
P
−
− P
+
=
D
n
b
3(n − 1)
3H
12
+ (H
21
− 1)
1 − 2b
H
12
n − 1

−
n − D
n
b
|H
1
− H
2
|
n − 1
1 −
2γ
3
.
Z
O(n log n)
O(n log n)
γ ≥ 3/4 − α H
12
/n ≥
3/4−α
α n α = 1/10
3n/4 Θ(
√
n) t
1 − te
−O(α
2
n
2
)
− ε
ε
b
≤ 1 |H
1
− H
2
| ≤ D
P
−
− P
+
≤
b
D
3n
(3(3/4 − α) + (3/4 − α)(1 − 2(3/4 − α)) − 3 + 2(3/4 − α))
= b
D Ω(1/n) ,
E
−
=
1
b
D
O(n).
D
max
x,y∈Ω
τ ≤
0
D=n
E
−
(D),
|
n
D=0
1/D − log n| ≤ 1
E(τ ) =
1
b
O(n log n) .
Z E(τ ) =
1
b
O(n log n)
L
L O(n log n)
P (t > 4E(τ )) ≤
1
4
,
t
mixL
≤
1
b
O(n log n) + t
mixZ
.
Z
Z O(n log n)
L
Q Θ(n log n)
t
mixQ
= O(n log n)
t
mixQ
= Ω(n log n) Q
n log n
n
2
(ln n − c) c
n log n Q
1
Q
n log n
a b
µ
b 0
P
µ a b
P a b
2
Q L
L Q
L b
b b = 2/3
b
t
mix(L|b≤2/3,a)
=
2
3b
t
mix(L|b=2/3,a)
.
b ≤ 2/3
1−b
b
b = 2/3
b
b 0
b = 0
L a
1/(1 − a)
t
mix(L|b≤2/3,a≤1−b)
=
2(1 − a)
3b
t
mix(L|b=2/3,a=0)
,
L a
Q
t
mix(Q|b≤2/3,a≤1−b)
=
1
3b
t
mix(L|b=2/3,a=0)
,
a
a = 0 t L
t
1−a
L (1 − a)
T
b = 2/3 b
b = 3/5
t
mixQ
a a T
Q T T
Q b b
T
d(t)
a b
a
b
b a a
b = 3/5 a = 1/5
XY DCNOT b = 2/3 0.67
a = 1/3
a Q
|ψ = |0 . . . 0
a
L
G {g
i
} ·
γ(g) g ∈ G
G g
h · g γ(h)
G
G(g, h) = γ(h · g
−1
)
γ G
2
(g, s) =
h
γ(s · h
−1
)γ(h · g
−1
) ≡ γ
∗2
(g, s)
• π(g) ≡ |G|
−1
• G {g|γ(g) > 0} G
• G
γ ν
t
= ν
0
G
t
G
f(g)
G
ˆ
f(ρ) ≡
g∈G
f(g)ρ(g).
ρ G f
G ρ
G Z
n
t
γ
∗t
− π
2
T V
≤
1
4
irreps=I
d
ρ
T r
ˆγ
t
(ρ)ˆγ
t
(ρ)
†
.
ρ G d
ρ
ρ
γ
∗t
− π
2
T V
≤
1
4
irreps=I
g∈Z
γ(g)ρ(g)
2t
.
˜
L L
˜
L
L
L
(i)
0→1
/L
(i)
1→0
= 3H / (H −1)
H 1
n 1 p
L
H 1
L
˜
L
L
˜
L
i
˜
L
(i)
0→1
= 1;
˜
L
(i)
1→0
= 1/3;
˜
L
(i)
0→0
= 0;
˜
L
(i)
1→1
= 2/3
L
˜
L
˜
L
∆ = Ω(1/3n)
∆ = Ω(1/3n(n − 1)) Q
O(n
3
) t
mixQ
˜
L L
L
O(n
2
)
O(n log n)
˜
L
1
1 2 3 G Z
n
4
= {0, 1, 2, 3}
n
i 0 1, 2 3
1/3 1, 2 3 0 1/3
2/3 1 0
G P
C = CNOT
a = 0 Q = M ∼ L
G Z
n
4
γ(g)
γ g
3n
1 2 3
1/3n
γ(g) =
1/3n j g
i
= 0∀i = j g
j
= 0 ,
0 .
{g|γ(g) >
0} Z
n
4
γ
Z
n
4
1
i e
i
g
g =
n
i=1
(e
i
)
g
i
.
Z
n
4
ρ
ρ(g) =
n
i=1
(ρ(e
i
))
g
i
ρ(e
i
) ∀i
(e
i
)
4
= id ρ
4
(e
i
) = ρ(I) = 1 ρ(e
i
)
ρ(e
i
) i −i n 4
n
Z
n
4
ˆγ(ρ) =
g∈Z
n
4
γ(g)ρ(g)
=
1
3n
n
i=1
(ρ(e
i
) + ρ
2
(e
i
) + ρ
3
(e
i
)) ,
ρ(e
i
) = 1
|ρ| ρ(e
i
) = 1 ρ
ˆγ(ρ) = 1 −
4|ρ|
3n
.
t =
3n
8
(ln(3n) + 2θ) θ > 0
t G
d(t) =
γ
∗t
− π
T V
≤
e
−θ
√
2
.
G ε
t
mixG
(ε) = O(n ln(n/ε))
γ
∗t
− π
2
T V
≤
1
4
irreps=I
1 −
4|ρ|
3n
2t
=
1
4
n
|ρ|=1
n
|ρ|
3
|ρ|
1 −
4|ρ|
3n
2t
,
n
|ρ|
≤
n
|ρ|
|ρ|!
1 − x ≤ e
−x
γ
∗t
− π
2
T V
≤
1
4
n
|ρ|=1
n
|ρ|
|ρ|!
3
|ρ|
e
−8t|ρ|/3n
=
1
4
n
|ρ|=1
[exp(ln(3n) − 8t/3n)]
|ρ|
|ρ|!
≤
1
4
{exp[exp(ln(3n) − 8t/3n)] − 1} .
t =
3n
8
(ln(3n) + 2θ) exp(e
−2θ
) − 1
e
x
−1 ≤ 2x 0 ≤ x ≤ 1
ε = e
−θ
/
√
2 d(t) ≤ ε
t
mixG
(ε) θ
t
t = O
n ln
n/ε
2

= O(n ln (n/ε)) .
Q
Z
˜
L G
Z
G
Z
G
(H, H + 1) =
n − H
n
,
Z
G
(H, H − 1) =
1
3
H
n
,
Z
G
(H, H) =
2
3
H
n
.
Z
G
t
mix
= O(n log n)
G Z
G
L
˜
L
L
˜
L L
N N
A
N
A
N
N
A
(x, y) = N(x, y)/(1 − N(x, x)) x = y N
A
(x, x) = 0
Z Z
G
Z
A
(H, H + 1) =
3(n − H)
3n − 2H − 1
Z
A
(H, H − 1) =
H − 1
3n − 2H − 1
Z
A
(H, H) = 0 ,
Z
A
G
(H, H + 1) =
3(n − H)
3n − 2H
Z
A
G
(H, H − 1) =
H
3n − 2H
Z
A
G
(H, H) = 0 .
Z
A
G
Z
A
H = O(1)
τ
Z
A
G
Z
A
H 3n/4
N
A
(x, x) = α α
Z Z
G
max τ
Z
≤ max ≤ τ
Z
G
≤ t
mixZ
G
= O(n log n)
t
mixZ
≤ max τ
Z
max τ
esperaZ
τ
esperaZ
O(n log n)
Z O(n log n)
Z O(n log n)
1 0
n
lim
n→∞
t
(n)
mix
(ε)
t
(n)
mix
(1 − ε)
= 1.
n
ε ∈ (0, 1)
t
(n)
mix
n
lim
n→∞
d
n
(c t
(n)
mix
) =
0 c < 1
1 c > 1
.
{ω
n
} = o(t
(n)
mix
)
c
ε
n
t
(n)
mix
(ε) − t
(n)
mix
(1 − ε) ≤ c
ε
ω
n
.
t
(n)
mix
O(f(n)) n log n
t
(n)
mix
= Θ(n log n)
lim
n→∞
t
(n)
mix
. ∆
(n)
→ ∞ .
Ω
BD
= Z
n
BD
(n)
O
t
(n)
mix
/∆
(n)
n
P
Z
Z
t
mixZ
= Θ(n log n) ∆
Z
= Ω(1/n)
G Z
G
Z
G
BD
t
mixZ
G
= O(n log n)
Ω(1/n)
G
P (g
1
, g
2
) ∈ Ω Ω → Ω
f(g
1
) = g
2
P (g
3
, g
4
) = P (f(g
3
), f(g
4
)) ∀g
3
, g
4
∈ Ω .
f(g) = gg
−1
1
g
2
G
G
Z
G
G
O(n
√
log n)
G P
Z
L
2
P
2
P
µ t 2
d(t)
2 ε d(t) ≤ ε
L
2
t P d
2
(t)
µ t 2 2
2n
d(t)
2 ε d
2
(t) ≤ ε/2
2n
t = O(n log(n/ε))
2 ε
Q L
2
L
2
d
2
d(t)
t
2−mix
k
kn log ( n/ε) ≥
1 − ∆
∆
ln(1/2ε) ,
ε → 0
kn ≥
1 − ∆
∆
,
∆ = Ω(1/n)
t
2−mixQ
(ε
) = O(n log(1/ε
)) ,
2 ε d
2
≤
(ε/2
2n
)
t
2−mixQ
(ε/2
2
n) = O(n log(2
2
n/ε)) = O( n(n + log ε
−1
)) ,
t = O( n(n+log ε
−1
))
2 ε
O(n)
2 O(log n) 2 O(n)
CZ
n ≤ 10
O(n)
n
O(n log n) O (n
2
)
n = 50
i j
0.2
0.25
0.3
0.35
0.4
0.45
1 10 100 1000 10000 100000 1e+006
"densidade.txt"
n → ∞
h
i
(t) i
t h(t)
h(t + 1) = h(t) +
1
n
1
n(n − 1)
i,j
(|h
i
(t) − h
j
(t)| + 2)
= h(t) +
1
n
2 +
1
n(n − 1)
i,j
|h
i
(t) − h
j
(t)|
,

w
i
(t) ≡ h
i
(t) −h(t) i
w(t) =
1
n
i
|w
i
|
1
n(n − 1)
i,j
|h
i
(t) − h
j
(t)| =
1
n(n − 1)
i,j
|h
i
(t) − h(t) − (h
j
(t) − h(t))|
≤
1
n
i
|w
i
| +
j
|w
j
|
= 2w(t)
h(t + 1) − h(t) ≤
2
n
(1 + w(t))
w
0
h(t) ≤
2t
n
(1 + w
0
)).
n w
0
h(t) + w
0
h
i
w
i
i
j j i i
j i (h
j
− h
i
+ 1)
h
i
(t + 1) − h
i
(t) = F(h
i
)
F(h
i
)
F(h
i
) > F(h
j
) h
j
> h
i
.
w
i
(t + 1) − w
i
(t) = F(h
i
) + h(t + 1) − h(t) = G(w
i
).
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
0 5 10 15 20 25 30 35 40 45 50
"WidthAbs5a5.txt"
"WidthAbs1a5.txt"
"WidthAbs1a4.txt"
"WidthAbs1a3.txt"
"WidthAbs1a2.txt"
n
w
i
(t) = 0 G(w
i
) G(w
i
)
w
i
= w
(G=0)
w
i
w
(G=0)
G(w
i
)
w
i
w(t)
n
n
w
i
n
w
i
w
i
w
i
(0) = 0
w
i
k
k = 2 P
∆
n
t
mix
Z O(n log(n/ε))
P n
O(n(n + log(ε
−1
))
ε O(n(n + log(ε
−1
))
T V
O(n log(n/ε))
•
•
Z P
•
O(n log(n/ε)) P
L
•
b > 0
a b
•
Z
•
n
O(log(n/ε))
ε O(n + log(1/ε)) ε
L
H
σ n 1
−1
v ±1
P(±1) =
1
2
(1 ∓ tanh βS(σ))
β
S(σ, v) =
w∼v
σ
w
σ v
v L
L
Γ
S
L S = 2H − n
β 1/n tanh(x) ∼ x 1
0 1
Θ(n log n) β 1/n
P(1) ∼ e
−βS
1
n
β = 1/n
L
H
L
H
Z
O(n log n)
L
L
k k ≥ 3
k
k ≥ 3 k
k = 2 k
k
ˆ
G
(k)
µ
k = 3
k = 2
σ
q,q
,q

|
ˆ
G
(3)
µ
ij
|σ
p,p
,p

µ
H
ˆ
G
(3)
H
ij
S
3,2
S
3
=
{I, (12), (13), (23), (123), (132)}
¯
S
(12)
≡ 2
n
S
(12)
− I =
p=
0
σ
p,p,
0
,
¯
S
(13)
≡ 2
n
S
(13)
− I =
p=
0
σ
p,
0,p
,
¯
S
(23)
≡ 2
n
S
(23)
− I =
p=
0
σ
0,p,p
.
(123) = (13)(12)
S
(123)
= S
(13)
S
(12)
=
1
2
2n
p,q
σ
p
σ
q
⊗ σ
q
⊗ σ
p
.
p, q = 0; p = 0, q = 0; p = 0, q = 0; p = q = 0
S
(123)
=
1
2
2n
I +
¯
S
(12)
+
¯
S
(13)
+
¯
S
(23)
+
p=q
p,q=
0
σ
p
σ
q
⊗ σ
q
⊗ σ
p
.
¯
S
(123)
≡ S
(123)
−
1
2
2n
I +
¯
S
(12)
+
¯
S
(13)
+
¯
S
(23)
=
p=q
p,q=
0
σ
p
σ
q
⊗ σ
q
⊗ σ
p
I,
¯
S
(12)
,
¯
S
(13)
,
¯
S
(23)
¯
S
(123)
|
¯
S
(123)
=
p=q
p,q=
0
[σ
q
σ
p
σ
p
σ
q
⊗ I ⊗ I] = 2
3n
2
2n
− 1
2
2n
− 2
.
(132) = (12)(13)
S
(132)
=
1
2
2n
I +
¯
S
(12)
+
¯
S
(13)
+
¯
S
(23)
+
p=q
p,q=
0
σ
q
σ
p
⊗ σ
q
⊗ σ
p
; .
¯
S
(132)
≡ S
(132)
−
1
2
2n
I +
¯
S
(12)
+
¯
S
(13)
+
¯
S
(23)
=
p=q
p,q=
0
σ
q
σ
p
⊗ σ
q
⊗ σ
p
,
¯
S
(123)
¯
S
(+)
≡
¯
S
(132)
+
¯
S
(123)
=
p=q
p,q=
0
{σ
q
, σ
p
} ⊗ σ
q
⊗ σ
p
,
¯
S
(−)
≡
¯
S
(132)
−
¯
S
(123)
=
p=q
p,q=
0
[σ
q
, σ
p
] ⊗ σ
q
⊗ σ
p
.
n = 1 σ
p
= σ
q
= σ
0
σ
p
σ
q
= −σ
q
σ
p
= i
rpq
σ
r
rpq
¯
S
(+)
¯
S
(−)
= 2
¯
S
(132)
= 2i
p=q
p,q=0
rpq
σ
r,p,q
.
ˆ
G
(3)
H
ij
1
m
F
m
F
m
m × m
ˆ
G
(2)
H
ij
k = 2
i=j
ˆ
G
(3)
H
ij
k
k = 2
ξ
2
t
(p)
k = 3
ξ
t
(p)ξ
t
(p
)ξ
t
(p)

k = 2
k
P
L
P P
L
=
I+P
2
C
δ ≤ 1
C =
1 − δ δ
δ 1 − δ
π =
1
2
(1 , 1) ↔ β
0
= 1 ,
π
1
=
1
2
(1 , −1) ↔ β
1
= 1 − 2δ .
C C
L
β
L
1
= 1 − δ
µ(t) t µ(t) = µ(o)P
t
=
π + c
1
π
1
β
t
1
|c
1
| ≤ 1 c
1
= 1
d(t) =
1
2
|β
t
1
|
t
mixC
=
ln(1/2)
ln(β
1
)
t
mixC
L
=
ln(1/2)
ln(β
L
1
)
.
0
0.5
1
1.5
2
2.5
3
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
t
mixC
L
/t
mixC
δ
δ → 0 2
δ → 1
∆ → 0 β
1
< 0
δ = 1
P P
L
2t
mixP
P
L
µ t
T V
d(t) =
µ(P
L
)
t
− π
T V
=
µ
t
i=0
t
i
(1/2)
t
I
t−i
P
i
− π
T V
≤
i
t
i
(1/2)
t
µP
i
− π
T V
i = t/2 σ = O(
√
t)
d
1
(t), d
2
(t) i < t/2−δ i ≥ t/2−δ δ < t/2
T V M
d
2
i = t/2 − δ
Γ
t/2−δ
d
2
≤
i≥t/2−δ
t
i
(1/2)
t
µM
i
− π
T V
≤
µM
t/2−δ
− π
T V
≤ 1
d
1
T V
≤ 1
d
1
≤
i<t/2−δ
t
i
(1/2)
t
.
d
1
≤ exp(−2δ
2
)
d(t) ≤ exp(−2δ
2
) +
µM
t/2−δ
− π
T V
.
t
µM
t/2−δ
− π
T V
≤ 1/4−e
−2δ
2
t
mixP
L
(ε) ≤ 2t
mixP
ε − e
−2δ
2
+ 2δ ,
δ =
log(1/ε)
t
mixP
L
(ε) ≤ 2t
mixP
ε − ε
2
+ 2
l og(1/ε) .
ε ε (1 − ε)
log(1/ε) t
mixP
A
B P =
A+B
2
t
mixP
≤ 2t
mixA
,
t
mixP
≤ 2t
mixB
,
A B
P = aA + (1 − a)B a ∈ [0, 1]
t
mixP
≤
1
a
t
mixA
,
t
mixP
≤
1
1 − a
t
mixB
.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo