量子計算基礎 - quest.is.uec.ac.jp

1 {}{}0101nmf{}01n{}01m{}{}:0,10,1nmf {}0,1n{}0,1m Turing Branching Programt {} {}:0,10,1nmf ()()() : ()()()12341 243 12,,,fxx xxx xxx xx= AND, OR, NOT AND:{}{}20101 OR:{}{}20101 NOT:{}{}0101 {}{}0,10,1 {}{}0,10,1 {}{}0,10,1 xyxyxxy xy x 0000000110001010101110010111011111 n {}1,,0,1nxx L 1 0 1 ()00000f=()f()00011f=()()00101f=M()11110 f= ()11,,nnfxx xx= LL ()11,,nnfxx xx.

2 XOR XOR mod 2 xyxy 000101101011110()()xyxyxy = xy xy xy()fxx xx ()11,,nnfxx xx= LL()()xxx x= LL()()121nnxxx x = , ()()1234xx xx , ()()()()()()12341234xxxx xxxx= AND,OR,NOT ,, , ()()On ()()()()0:limsnsn OtnCC > < ()sn()tn()()()()()0:limnsn OtnCCtn = > < ()()()22420084241snn nsnOn=+ + = ()()()5 log3 log loglog logsnn n nnsn Onn=+ =() ()()()5 log3 log loglog logsnn n nnsn Onn+ ()() On= Shannon ()2nOShannon ()12.

3 ,nfxxx()()()()10xfx xxf x x ()()()()121 21, ,..,0, ,..,nnxfx xxf x x= ()sn n ()()()214,11snsns +=()sn n ()()2nsn O= or 01 + 0 1 0 1 q-bit q 01 +2 001 +221() += C2 11(,) += C 2 10 01 2 0,0 = 11 = 1 0,10 2 10 01 2 0,0 = 11 = ()101110101 +=+ ()01222 ()101()012 01 =+{}01,MMM= []01100010,000M == = 000 []1000110 1101M == = []101 2 00Pr "0"0 0MM === ( ) 2 ( ) 2 11Pr "1"1 1MM === ( )

4 01 {}MMM 01 =+0011MM=={}01,MMM= 0100,11MM==1 2 02 0 = =, ,1110 110000 000000 = = = = 0 n 2n 010101 111000 0<01<1010100 = = 000000 = = 0 0 0 0 01010101 = = 00011110 = = 2<231010 1101 2<3< {}00,11M= 000 000 , 001 001 ,, 1 11 1 11nnM = 6474864748 LLLLLLL14444444444244444444443 2n Pauli 01X = 0iY = 10Z 10X= 0Yi= 01Z= XYZXYZ 01 XNOT == 10 01 1 0 X100 = 01 1 0110 0 1 == X01 +10 + Hadamard 111H = 112H= HH Hadamard 11 1111 ()101110110122H == ()1012=+()10()1012+H Hadamard 11 01111H ()

5 101111111122H == ()012= ()11()1012 H NOT CNOT 110 CNOT= 011100xxxx{},0,1xy yxy NOT CNOT0x=y CNOT1x=y xxxx{},0,1xy yxy NOT CNOT0x=y CNOT1x=y 0000{}0,1y y0yy = NOT CNOT0x=y CNOT1x=y 1111{}0,1y y1yy = 0000 102+00 112+00220H000 112+H02 AND,OR,NOT n ()2nO CNOT n ()24nO n ()24nOn Bloch Bloch Bloch (), z0 (), y y x1()()cos2 0sin2 1ie =+Bloch z110122+10122i+0()2,0 ==()2,2 ==yyx1()()cos2 0sin2 1ie =+ ()()cossin22exp2cossin22xiRiXIiX = = = 22sincos22i ()()cossin22exp2cossin22yRiYIiY = = = 22sincos22 ()()220exp2cossin220izieRiZIiZe = = = 0zR 2xR yy101i x022()2,3 2 ==cossin111144001iiR === 00102222sincos44xRii === ()() cossin22nxyzRIinX nYnZ = ++()()22nxyz()3 ,,nnnn= (),,xyznnnn U U ,,n ()

6 InUeR =()Z-Y ZY U ,,, ()()()izyzUeR R R = ()()()zyz i ie ()(),yzRR ( X-Y )zRxR 1. n-qbit U CNOT+ 1qbit 2. CNOT 1-qbit +CNOT2. CNOT 1qbit +CNOT3. 1-qbit 1-qbit +CNOT 1-qbit CNOT q CNOT CNOT 1x1xnxnxy()1nxxy Lnn() CNOT CNOT 1x1x2x2x3x3xy()123xxx y ()()123,,0,0,1xx x= y 1-qbit 1qbit cc cU U10 ()1001CU = 0()CU= U0 Toffoli CCNOT 108 6447448 CCNOT=10001O 01010 1x1x {}12,,0,1xx y 2x2xy()12xxy y12,xxToffoli CCNOT oo CCNO CCNOT=T T TSHHTT T T 100Si = 4100iTe = 111112H = 0i 0e vs.

7 (Shor, 1994) RSA RSA (G1996) (Grover, 1996) vs 2logNN ()()()()()()()132313exp1lnln ln,64 9 OCo N N C+= Sh 1994 Shor 1994 ()()()22logON2lognN= ()()()()()131323exp 64 9lnln lnCNNN=2()()22logQNN=()()() ,210 NCNQN 10 PFLOPS, 1 161025210 RSA n = 1024 n = 2048 (Shor, 1994) RSA RSA (G1996) (Grover, 1996)