スピントロニクス量子操作研究会「量子コンピュータの基礎」 第5回

3/24/2005

Fault tolerancez Assumptions used so far:

Fault tolerant quantum
computationz No errors when storing qubits
z No errors when processing qubits

z In reality:
z Logic operations may be faulty (encoding,syndrome measurement, etc)

Quantum error correcting code:
The 7-qubit (Steane) codez Errors might propagate during logic operationsz What we need:z Syndrome measurement; andz a universal set of quantum gates on encoded qubits

without unacceptable error propagationz A code that can correct more than one error in thecode block2

Useful identities

Propagation of errors
z Bit flip error

1.

2.

4.

HH

H

H

X

=ZX

==H X H

X=z Phase flip error

XZ

=

3.

=
H

H

ZZ
Z
3

Syndrome measurementz BadzErrors propagate andaccumulate!

Preparing ancillary qubits

z Goodz4z Shor stateNo error propagation

Shor =1∑w

8 even w

z Four qubits: equal weighted superposition

state of all even stringsz Reveal error syndrome onlyz 24 ancillary qubits (in 6 Shor states) and 24|0i|0i
|0i
|0i

|0i

CNOT gates
Bit flip error detection
dataToo much informationis copiedz Measurement destroys
encoded qubits
z|cati

Fumiko Yamaguchi <yamaguchi@stanford.edu>

H|cati

HShor state

HORH||1( 0000 + 1111 )2

5

Phase flip error detection
datadata|cati

H61

スピントロニクス量子操作研究会「量子コンピュータの基礎」 第5回

Preparing ancillary qubits II

3/24/2005

Verification of ancillary qubits
z Preparation of Shorz Steane statez Verification

State (not fault-tolerant)z 7 qubits: equal weighted superposition stateof all Hamming codewords(11
Steane =∑w = 2 0 +14 w∈Hamming)

|0i

H

H

|0i

H|Steanei

|0i

H|0i

HH

H

H
Hdata|Steanei

HH

H

|0i

If the ancillary qubit is1: One or more bit fliperrors (before H)
occurredÆ Discardz Measurement may befaulty
Æ Repeatzz Procedures:z Ancillary qubits mayz CNOT gate between corresponding data qubits

have errors!

and ancillary qubits
z Apply check matrix to the ancillary qubitsz

Phase flip errors
propagates to the dataqubits.
z Bit flip errors do notdamage the data qubits

z 14 ancillary qubits (in 2 Steane states) and14 CNOT gates
7Error propagation in Shor state

Fault-tolerant quantum gatesz Bit flip errorsz Logic gates on encoded qubits

z Bit flip on qubit #1 (no error)
H

H

X

|0i

H|0i

H|0i

H

= bitwise application
X

H

|0i

X

H

|0i

X

H

|0i

X

H

H

|0i
|0i

zZ
Z =Z1Z2Z3Z4Z5Z6Z7

H|0i

H

|0i

X

H

|0i

H|0i

X

H|0i

H|0i

X

H|0i

H
X

z Bit flip on qubit #3z Bit flip on qubit #4

z X =X1X2X3X4X5X6X7

1( 0000 + 1111 )2z Bit flip on qubit #2|0iz Hadamard gate HHHz Phase gate Sz Bitwise application of ZS
1( 0111 + 1000 )2

1( 0011 + 1100 )2
1( 0001 + 1110 )2

Fault-tolerant preparation of ancilla ΘHT

⎛1 0⎞
⎟⎟
S = ⎜⎜⎝0 i ⎠z CNOT gate
z Bitwise application of CNOT
910

Fault-tolerant preparation of ancilla Θ⎛1 0 ⎞iπ⎛π ⎞T = ⎜⎜= e 8 Rz ⎜ ⎟iπ ⎟4⎟⎝4⎠⎝0 e ⎠Θ=T |ψ iSXinterchanges Z and X:
XH =H1H2H3H4H5H6H7

Fault-tolerant π/8 gate

|0 i

80 + e iπ 4 1z Ancilla state Θz |0i: Eigenstate of Zz |Θi: Eigenstate of THZHT† = e-iπ/4SX

2Eigenvalue +1|ψ iz Fault-tolerant measurement of e-iπ/4SX[]1
Θ (a 0 + b 1 ) ⎯⎯⎯→0 (a 0 + b 1 ) + e iπ 4 1 (a 1 + b 0 )2
1=a 0 + e iπ 4 b 1 0 + b 0 + e iπ 4 a 1 12CNOT[()() ]z If measurement result = +1

⎛1 0⎞
⎟⎟
S = ⎜⎜⎝0 i ⎠z Ancilla state Θ is preparedz If measurement result = –1
If measurement result is 1, apply SX→ T|ψi (up to global phase)z Discard and repeat; ORz Apply fault-tolerant Z
11Fumiko Yamaguchi <yamaguchi@stanford.edu>

122スピントロニクス量子操作研究会「量子コンピュータの基礎」 第5回

Fault-tolerant Toffoli gate (1)3/24/2005

Fault-tolerant Toffoli gate (2)z Swap |xyzi with known state |000i

z Use commutation rules to move Toffoli

gate to the left
|0i|0i|0iHXHX
Z|xi|yi|zi

Fault-tolerant preparation of ancilla|xi|yi|z⊕xyi|0i|0i|0i

Not fault-tolerant

HXZHZ|xi|yi|ziHX|xi|yi|z⊕xyi

H

13

Measurement of operators(not fault-tolerant)

14

Fault-tolerant measurement ofoperators

z Circuit to measure a single qubit

PrepareVerifyControlled-M

Decodeoperator M with eigenvalue m = ±1|0i

H
1( 0 + 1 )ψ0 ψ ⎯⎯→2H

H|0i H|0i|0iC- M⎯⎯⎯→ 12 ( 0 + m 1 )ψ

⎧0 ψH
⎯⎯→⎨
⎩0 ψMz Operator M on encoded qubitsm = +1m = −1

H|0i

Encodedqubits|0i

H

Encodedqubitsz M: Bitwise application of M’
HM’M’M’M’
M’

MM’

15

16

Quantum error code to correct manyerrors
z Quantum error correcting code [[n, k,Accuracy threshold

2t+1]]z Uncorrectable if t+1 independent errors(each with probability ε) occur before error
correctionz Probability εt+1 ¿ ε; butz Longer codes require longer steps insyndrome measurementz Uncorrectable errors accumulate before

they can be corrected!
Æ Concatenated code
18

Fumiko Yamaguchi <yamaguchi@stanford.edu>

3スピントロニクス量子操作研究会「量子コンピュータの基礎」 第5回

Concatenated code

3/24/2005

Estimation of accuracy thresholdz Probability of failure:z The 7-qubit (Steane) codez Probability of failure ε2z At each level of concatenation, a block of 7 qubits

fails if two or more sub-blocks contain errors:⎛7⎞ 2
2
pL +1 ≈ ⎜⎜ ⎟⎟ pL + L = 21 pL + L⎝ 2⎠
z Threshold value: p0 =1/21

z Concatenated once: 72 blocks
z Probability of failure in the sub-block: ε2
z Total probability of failure: (ε2)2z Relate gate errors (εgate) and storage errorz L levels of concatenation: 7L blocks(εstorage) to p0

z Total probabilityz Assuming error correction after every CNOT gateof failure: (ε2)LÆ Threshold error rates

19εgate∼ 6·10-4
εstorage∼ 6·10-4

20

Shor’s algorithm?
z Factorize a 130-digit (432-bit) numberz A few months by a classical computerz Shor’s algorithmz Requirements

5×432 qubits
38×(432)3∼ 3×109 Toffoli gatesz Gate error < 10-9 per Toffoli gatez Storage error < 10-12 per gate operation timezzz Can be achieved byzz

3 levels of concatenation of 7-qubit Steane code
Individual error rates εgate∼εstorage∼ 10-6z Total number of qubits ∼ 106z

including additional ancillary qubits to implement gatesfault-tolerantly

21

Fumiko Yamaguchi <yamaguchi@stanford.edu>

4