សៀគ្វីអ៊ីនធឺណិត

ក្នុង ទ្រឹស្តីកង់តូព ដែលជា សៀគ្វីកង់ទិច ជា គំរូ សម្រាប់ កុំព្យូទ័រ នៅក្នុងការដែលកុំព្យូទ័រមួយគឺលំដាប់នៃ ច្រកទ្វារកង់ទិច ដែលមាន

ការផ្លាស់ប្តូរញ្ច្រាស់នៅលើ មេកានិចកង់ទិច អាណាឡូក នៃ n - បន្តិច ចុះឈ្មោះ ។ រចនាសម្ព័ន្ធស្រដៀងគ្នានេះត្រូវបានសំដៅដល់ថាជាការ ចុះឈ្មោះ n - qubit ។

មាតិកា

 

• 1ច្រកទ្វារតក្កវិជ្ជាត្រលប់មកវិញ
• 2ច្រកទ្វារតក្កវិទ្យា
• 3សៀគ្វីតក្កវិស័យ
• 4គណនា Quantum
• 5ឯកសារយោង
• 6តំណខាងក្រៅ

ច្រកតក្កវិជ្ជាបុរាណដែលត្រលប់វិញ

ច្រកទ្វារតក្កវិទ្យា បឋម របស់កុំព្យូទ័របុរាណមួយក្រៅពី ច្រកទ្វារ NOT គឺមិនអាច ត្រលប់មកវិញបាន ទេ។ ដូច្នេះឧទាហរណ៍សម្រាប់ ច្រកទ្វារ AND មួយមិនអាចសង្គ្រោះទិន្នន័យប៊ីតបញ្ចូលពីរពីប៊ីតលទ្ធផល។ ឧទាហរណ៍ប្រសិនបើប៊ីតលទ្ធផលគឺ 0 យើងមិនអាចប្រាប់ពីនេះបានទេថាប៊ីតបញ្ចូលគឺ 0,1 ឬ 1,0 ឬ 0,0 ។

ទោះជាយ៉ាងណាក៏ដោយច្រកទ្វារដែលត្រលប់មកវិញនៅក្នុងកុំព្យូទ័របុរាណត្រូវបានបង្កើតឡើងយ៉ាងងាយស្រួលសម្រាប់ខ្សៃតូចៗដែលមានប្រវែងណាមួយ។ លើសពីនេះទៅទៀតទាំងនេះគឺពិតជាមានការចាប់អារម្មណ៍ជាក់ស្តែងព្រោះច្រកទ្វារដែលមិនអាចវិលត្រឡប់បានត្រូវបង្កើននូវ entropy ខាងរាងកាយ ។ ការច្រកទ្វារញ្ច្រាស់គឺជាមុខងារបញ្ច្រាសនៅលើ n ទិន្នន័យ -bit ដែលត្រឡប់ n -bit ទិន្នន័យដែលជាកន្លែងមួយ n ទិន្នន័យ -bit ជា ខ្សែអក្សរ ប៊ីត x ₁ , x ₂ , ... , x _n ប្រវែង n ។ សំណុំ ទិន្នន័យ n -bit គឺជាចន្លោះ {0,1} ⁿ ដែលមាន ខ្សែ 2 ⁿ នៃ 0 និង 1's ។

កាន់តែច្បាស់ជាងនេះ: ជា n -bit ទ្វារញ្ច្រាស់ជា bijective ផែនទី ច ពីសំណុំ {0,1} ⁿ នៃ n ទិន្នន័យ -bit លើខ្លួនវាផ្ទាល់។ ឧទាហរណ៏នៃការច្រកទ្វារច្រក ត្រួសត្រាយ f នេះគឺជាការគូសផែនទីដែលអនុវត្តការផ្លាស់ប្តូរថេរទៅធាតុបញ្ចូលរបស់វា។ ចំពោះហេតុផលនៃវិស្វកម្មជាក់ស្តែងមួយការសិក្សាតាមធម្មតាច្រកទ្វារសម្រាប់តែតម្លៃតូចនៃ n ឧទាហរណ៍ n = 1, n = 2 ឬ n = 3 ។ ច្រកទាំងនេះអាចត្រូវបានពិពណ៌នាបានយ៉ាងងាយស្រួលដោយតារាង។

ច្រកទ្វារតក្កវិទ្យា 

ដើម្បីកំណត់ច្រកទ្វារ quantum មុនដំបូងយើងត្រូវបញ្ជាក់ការជំនួសកង្វះខាតទិន្នន័យឌីជីថល n -bit ។ នេះជា កំណែបរិមាណ នៃបុរាណ n អវកាស {0,1} -bit ⁿ គឺជា អវកាស Hilbert

$${\ displaystyle H_ {\ operatorname {QB} (n)} = \ ell ^ {2} (\ {0,1 \} ^ {n}) ។ }

នេះគឺតាមនិយមន័យចន្លោះនៃអនុគមន៍ដែលមានតម្លៃស្មុគស្មាញនៅលើ {0,1} ⁿ និងជាធម្មជាតិជា ផលិតផលផលិតផលខាងក្នុង ។ លំហនេះក៏អាចត្រូវបានចាត់ទុកថាមានការបញ្ចូលបន្ទាត់លីនេអ៊ែរនៃខ្សែអក្សរបូរាណធម្មតា។ ចំណាំថា H _{QB ( n )} គឺជាលំហវ៉ិចទ័រលើចំនួនកុំផ្លិចនៃ វិមាត្រ 2 ⁿ ។ ធាតុនៃចន្លោះនេះត្រូវបានគេហៅថា n -qubits ។

ប្រើ Dirac ket notation ប្រសិនបើ x ₁ , x ₂ , ... , x _n ជាខ្សែអក្សរតួលេខបុរាណ

$${\ displaystyle | x_ {1}, x_ {2}, \ cdots, x_ {n} \ ជួរដេក \ quad}

គឺជា n -qubit ពិសេស ដែលត្រូវគ្នាទៅនឹងអនុគមន៍ដែលផ្គូផ្គងខ្សែអក្សរប្រភាគបុរាណនេះទៅ 1 និងគូរខ្សែអក្សរប៊ីតផ្សេងទៀតទាំងអស់ទៅ 0; ទាំង 2 ⁿ ពិសេស n -qubits ត្រូវបានហៅថា រដ្ឋជាមូលដ្ឋានកុំព្យូទ័រ ។ ទាំងអស់ n -qubits គឺជាបន្សំលីនេអ៊ែរស្មុគស្មាញនៃរដ្ឋជាមូលដ្ឋានកុំព្យូទ័រទាំងនេះ។

ច្រកទ្វារមនោគមន៍វិជ្ជាផ្ទុយទៅនឹងច្រកទ្វារតក្កវិជ្ជាបុរាណតែងតែអាចត្រលប់មកវិញ។ មួយតម្រូវឱ្យមានប្រភេទពិសេសមួយនៃការផ្លាស់ប្តូរមុខងារពោលគឺការ ធ្វើផែនទី រួមគ្នា , ដែលជាការផ្លាស់ប្តូរលីនេអ៊ែរនៃ ចន្លោះផលិតផលផ្នែកខាងក្នុង ស្មុគស្មាញ ដែលការពារ ផលិតផលខាងក្នុង Hermitian ។ អាន n -qubit (បញ្ច្រាស់) ច្រកទ្វារកង់ទិចគឺជា ផែនទីរួម លោក U ពីអវកាស ក្រុមហ៊ុន H _{QB (n )} នៃ n -qubits លើខ្លួនវាផ្ទាល់។

ជាធម្មតាយើងចាប់អារម្មណ៍តែច្រកទ្វារសម្រាប់តម្លៃតូចនៃ n ប៉ុណ្ណោះ។

ការបញ្ច្រាស់ n ច្រកទ្វារតក្ក -bit បុរាណផ្ដល់នូវកំណើនមួយញ្ច្រាស់ n ទ្វារ -bit កង់ទិចដូចខាងក្រោម: ដើម្បីឱ្យគ្នាញ្ច្រាស់ n -bit ច្រកទ្វារតក្ក ច ត្រូវគ្នាជាច្រកទ្វារកង់ទិច សរសេរ _ច ដែលបានកំណត់ដូចខាងក្រោម:

$${\ displaystyle} {x} {x} {x} {x} {x} {x} ) \ ជួរ។ }

ចំណាំថា W _{f អនុ} ញ្ញាត្តិរដ្ឋមូលដ្ឋានគណនា។

មានសារៈសំខាន់ជាពិសេសគឺច្រកទ្វារ NOT ដែលបានគ្រប់គ្រង (ហៅផងដែរថា ច្រកទ្វារ CNOT ) W _CNOT បានកំណត់នៅលើបរិមាណ 2 qubit ។ ឧទាហរណ៍ខ្លះនៃច្រកទ្វារតក្កវិទ្យាដែលមានប្រភពមកពីបុរាណគឺ ច្រកទ្វារ Toffoli និង ច្រកទ្វារ Fredkin ។

ទោះជាយ៉ាងណាក៏ដោយរចនាសម្ព័ន្ធ Hilbert-space នៃ qubits អនុញ្ញាតឱ្យមានទ្វារ quantum ជាច្រើនដែលមិនត្រូវបានបណ្តាលមកពីបុរាណ។ ឧទាហរណ៍ការផ្លាស់ប្តូរដំណាក់កាលដែលទាក់ទងគឺ 1 ច្រក qubit ដែលបានផ្តល់ដោយគុណដោយម៉ាទ្រីតរួមមួយ:

{\ displaystyle U _ {theta} = {\ begin {bmatrix} e ^ {i \ theta} & 0 \\ 0 & 1 \ end {bmatrix}},}

ដូច្នេះ

$${\ displaystyle U_ {\ theta} | 0 \ rangle = e ^ {i \ theta} | 0 \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

សៀគ្វីតក្កវិជ្ជាប្រែប្រួល

អត្ថបទដើម: ការគណនាត្រលប់មកវិញ

ជាថ្មីម្តងទៀតយើងចាត់ទុក ការគណនាបុរាណចាស់ដែល អាចត្រលប់មកវិញបាន ។ គំនិតទាំងនេះគឺមានភាពខុសគ្នារវាងបញ្ច្រាស់នោះទេ n សៀគ្វី -bit និងបញ្ច្រាស់ n ច្រកទ្វារតក្ក -bit: ទាំងមួយគឺគ្រាន់តែជាមុខងារចុះឡើងនៅលើចន្លោះនៃ n ទិន្នន័យបន្តិច។ ទោះជាយ៉ាងណាក៏ដោយដូចដែលបានរៀបរាប់នៅផ្នែកមុនសម្រាប់ហេតុផលវិស្វកម្មយើងចង់មានច្រកទ្វារដែលអាចវិលត្រលប់វិញតូចៗមួយចំនួនតូចដែលអាចដាក់បញ្ចូលគ្នាដើម្បីផ្គុំសៀគ្វីដែលអាចបត់បែនបាន។

ដើម្បីពន្យល់ពីដំណើរការជួបប្រជុំគ្នានេះឧបមាថាយើងមានញ្ច្រាស់ n ទ្វារ -bit ច និងការបញ្ច្រាស់ ម៉ែត្រ -bit ទ្វារ ក្រាម ។ ការដាក់បញ្ចូលគ្នាជាមួយគ្នាមានន័យថាបង្កើតសៀគ្វីថ្មីមួយដោយភ្ជាប់បណ្តុំនៃ លទ្ធផល k មួយចំនួន នៃ f ទៅសំណុំនៃ ធាតុបញ្ចូល k មួយចំនួន នៃ g ដូចនៅក្នុងរូបខាងក្រោម។ ក្នុងតួលេខនោះ n = 5, k = 3 និង m = 7 ។ សៀគ្វីលទ្ធផលក៏អាចត្រលប់មកវិញហើយដំណើរការលើ n + m - k bits ។

យើងនឹងយោងទៅលើគ្រោងការណ៍នេះជា សមាសភាពបុរាណ មួយ (ទស្សនៈនេះត្រូវនឹងនិយមន័យបច្ចេកទេសនៅក្នុងក្រដាសត្រួសៗរបស់ Kitaev ដែលបានលើកឡើងខាងក្រោម) ។ ក្នុងការបង្កើតម៉ាស៊ីនត្រលប់ទាំងនេះវាជាការសំខាន់ណាស់ដើម្បីធានាថាម៉ាស៊ីនកណ្តាលក៏អាចត្រលប់មកវិញដែរ។ ស្ថានភាពនេះធានាថា មធ្យម "សំរាម" មិនត្រូវបានបង្កើតឡើង (ផលប៉ះពាល់រាងកាយសុទ្ធនឹងមានដើម្បីបង្កើនធាតុដែលជាផ្នែកមួយនៃការជម្រុញមួយសម្រាប់ឆ្លងកាត់តាមការធ្វើលំហាត់ប្រាណនេះ) ។

ឥឡូវនេះវាអាចបង្ហាញថា ច្រកទ្វារ Toffoli គឺជា ច្រកទ្វារសកល ។ នេះមានន័យថាបានផ្តល់ឱ្យណាញ្ច្រាស់បុរាណ n សៀគ្វី -bit ម៉ោង យើងអាចសង់ជាបង្គុំទ្វារ Toffoli បុរាណក្នុងលក្ខណៈខាងលើដើម្បីផលិត ( n + m ) សៀគ្វី -bit ច ដូចថា

$${\ displaystyle f (x_ {1}, \ ldots, x_ {n}, \ underbrace {0, \ dots, 0}) = (y_ {1}, \ ldots, y_ {n} ldots, 0})}

ដែលជាកន្លែងដែលមាន ម៉ែត្រ underbraced ធាតុចូលសូន្យនិង

$${\ displaystyle (y_ {1}, \ ldots, y_ {n}) = h (x_ {1}, \ ldots, x_ {n})}។

ចូរកត់សំគាល់ថាលទ្ធផលចុងតែងតែមានខ្សែអក្សរមួយនៃការ ម៉ែត្រ លេខសូន្យជា ancilla ប៊ីត! គ្មាន "សំរាម" ត្រូវបានផលិតឡើងហើយដូច្នេះការគណនានេះគឺជាការពិតមួយដែលនៅក្នុងន័យធម្មជាតិមិនបង្កើត entropy ទេ។ បញ្ហានេះត្រូវបានពិភាក្សាដោយប្រុងប្រយ័ត្ននៅក្នុងអត្ថបទរបស់ខៃថេវ។

ជាទូទៅមុខងារណាមួយ f (bijective ឬមិន) អាចត្រូវបានក្លែងបន្លំដោយសៀគ្វីនៃច្រកទ្វារ Toffoli ។ ជាក់ស្តែងប្រសិនបើការផ្គូផ្គងមិនត្រូវបាន ចាក់បញ្ចូល នៅចំណុចមួយចំនួនក្នុងការពិសោធន៏ (ឧទាហរណ៍ជំហានចុងក្រោយ) "សំរាម" ខ្លះត្រូវបានផលិត។

សម្រាប់សៀគ្វីកង់ស្យុងសមាសភាពប្រហាក់ប្រហែលនៃច្រក qubit អាចត្រូវបានកំណត់។ នោះគឺជាប់ទាក់ទងទៅនឹង ការស្ថាបនាបែបបុរាណ ណាមួយ ដូចខាងលើយើងអាចបង្កើតសៀគ្វីអាំងតេក្រាលនៅពេលជំនួស F យើងមាន n -qubit gate U ហើយជំនួសឱ្យ g យើងមាន ច្រក M -qubit W ។ សូមមើលរូបភាពខាងក្រោម:

ការពិតដែលថាការតភ្ជាប់ច្រកតាមវិធីនេះផ្តល់នូវការកើនឡើងនូវការផ្គូផ្គងឯកតានៅលើ n + m - k qubit ចន្លោះងាយស្រួលពិនិត្យ។ វាគួរតែត្រូវបានកត់សម្គាល់ថានៅក្នុងកុំព្យូទ័រកង់ទិចពិតប្រាកដមួយការភ្ជាប់រាងកាយរវាងច្រកទ្វារនេះគឺជាបញ្ហាប្រឈមវិស្វកម្មធំមួយចាប់តាំងពីវាគឺជាការមួយនៃកន្លែងដែលជាកន្លែងដែល decoherence អាចកើតមានឡើង។

វាក៏មាន ទ្រឹស្ដីសកល សម្រាប់សំណុំជាក់លាក់នៃច្រកទ្វារល្បី។ ដូចទ្រឹស្តីបទសកលមួយដែលមាន, ឧទាហរណ៍, សម្រាប់អ្នកទាំងពីរដែលមានទ្វារដំណាក់កាល qubit នេះតែ លោក U _θ ដែលបានរៀបរាប់ខាងលើ (សម្រាប់តម្លៃសមរម្យនៃθ) រួមជាមួយនឹង 2 qubit ទ្វារ CNOT សរសេរ _CNOT ។ ទោះជាយ៉ាងណាក៏ដោយទ្រឹស្តីបទសកលសម្រាប់ករណី quantum គឺខ្សោយជាងមួយសម្រាប់ករណីបុរាណ។ វាការពារតែមួយគត់ដែលបញ្ច្រាស់ណាមួយ n សៀគ្វី -qubit អាចនឹងត្រូវបាន ប៉ាន់ប្រមាណទៅ តាមអំពើចិត្តយ៉ាងល្អដោយសៀគ្វីប្រជុំពិភាក្សាគ្នាពីច្រកទ្វារទាំងពីរបឋមសិក្សា។ ចំណាំថាមាន រាប់មិនអស់ច្រកទ្វារបួន qubit តែមួយអាចធ្វើទៅបានមួយសម្រាប់គ្រប់មុំដែលអាចធ្វើបានθដូច្នេះពួកវាមិនអាចតំណាងឱ្យសៀគ្វីកំណត់បានពី { U _θ , W _CNOT }} ទេ។

គណនា Quantum 

រហូតមកដល់ពេលនេះយើងមិនបានបង្ហាញពីរបៀបដែលសៀគ្វីកង់តូសត្រូវបានប្រើដើម្បីធ្វើការគណនា។ ដោយសារបញ្ហាលេខសំខាន់ៗជាច្រើនត្រូវបានកាត់បន្ថយដើម្បីគណនាការបម្លែងឯកតាមួយ U លើទំហំវិមាត្រ (ការ បំបែក Fourier ដាច់ដោយឡែក ដែលជាគំរូដំបូង) គេរំពឹងថាសៀគ្វីជីនម៉េនមួយចំនួនអាចត្រូវបានបង្កើតឡើងដើម្បីអនុវត្ត U បំលែង ។ នៅក្នុងគោលការណ៍មួយត្រូវការតែមួយគត់ដើម្បីរៀបចំ រដ្ឋ n qubit ψជាការដាក់បញ្ចូលដ៏សមស្របនៃរដ្ឋមូលដ្ឋានគណនាសម្រាប់បញ្ចូលនិងវាស់លទ្ធផល U ψ។ ជាអកុសលមានបញ្ហាពីរជាមួយនេះ:

• គេមិនអាចវាស់ស្ទង់ដំណាក់កាលនៃψនៅគ្រប់ស្ថានភាពមូលដ្ឋានទិន្នន័យទេដូច្នេះគ្មានមធ្យោបាយអានចម្លើយពេញលេញទេ។ នេះគឺនៅក្នុងលក្ខណៈនៃ ការវាស់វែងនៅក្នុងមេកានិចកង់ទិច ។
• មិនមានមធ្យោបាយដើម្បីរៀបចំធាតុបញ្ចូលψបានយ៉ាងមានប្រសិទ្ធភាពទេ។

នេះមិនរារាំងសៀគ្វីអ៊ីនធឺណែតសម្រាប់ប្លែង Fourier ដាច់ដោយឡែកពីការប្រើជាជំហានមធ្យមនៅក្នុងសៀគ្វីកង់ទ្យុងដទៃទៀតទេប៉ុន្តែការប្រើប្រាស់គឺកាន់តែច្បាស់។ ជាការពិតការគណនាបរិមាណគឺមាន ប្រតិកម្ម ។

ឥឡូវយើងផ្តល់នូវគំរូគណិតវិទ្យាអំពីរបៀបដែលសៀគ្វីកង់តូសអាចស្រូបយក គណនាប្រូតេអ៊ីន ប៉ុន្តែ ប្រហាក់ប្រហែល ។ ពិចារណា r សៀគ្វី -qubit លោក U ដែលមានចន្លោះការចុះបញ្ជី ក្រុមហ៊ុន H _{QB ( ស្តាំ )} ។ លោក U គឺជាផែនទីរួមមួយ

$${\ displaystyle H _ {\ operatorname {QB} (r)} \ rightarrow H_ {\ operatorname {QB} (r)} ។ }

ដើម្បីភ្ជាប់សៀគ្វីនេះទៅនឹងការផ្គូរផ្គងបុរាណនៅលើ bitstrings យើងបញ្ជាក់

• ការ បញ្ចូលធាតុ X = {0,1} ^{ម៉ែត្រ} នៃ m (បុរាណ) ប៊ីត។
• អាន ទិន្នផលចុះឈ្មោះ អ៊ី = {0,1} ⁿ នៃ n ប៊ីត (បុរាណ) ។

មាតិកា x = x ₁ , ... , x _m នៃបញ្ជីធាតុបញ្ចូលបុរាណត្រូវបានប្រើដើម្បីចាប់ផ្ដើមបញ្ជី qubit តាមវិធីមួយចំនួន។ តាមឧត្ដមគតិនេះវានឹងត្រូវបានធ្វើជាមួយរដ្ឋមូលដ្ឋានគណនា

$${\ displaystyle | {\ vec {x}}, 0 \ rangle = | x_ {1}, x_ {2}, \ cdots, x_ {m}, \ underbrace {0, \ ចំណុច, 0} \ ជួរល,}

ដែលជាកន្លែងដែលមាន r - m ទាបជាង ធាតុបញ្ចូលសូន្យ។ យ៉ាងណាក៏ដោយការចាប់ផ្តើមដ៏ល្អឥតខ្ចោះនេះគឺមិនត្រឹមត្រូវទេ។ ចូរយើងសន្មតថាការចាប់ផ្តើមគឺជារដ្ឋលាយគ្នាដែលបានផ្តល់ឱ្យដោយប្រតិបត្តិករដង់ស៊ីតេមួយចំនួន S ដែលនៅជិតធាតុបញ្ចូលល្អប្រសើរបំផុតនៅក្នុងម៉ែត្រជាក់លាក់សមស្របមួយចំនួន។

$${\ displaystyle \ operatorname {Tr} \ left ({\ ធំ |} | {\ vec {x}}, 0 \\ rangle \ langle {\ vec {x}}, 0 | -S {\ big |} \ right) \ leq \ delta ។ }

ស្រដៀងគ្នានេះដែរទិន្នផលចន្លោះបញ្ជីដែលទាក់ទងទៅនឹងការចុះបញ្ជីត្រូវបាន qubit, ដោយ អ៊ី សង្កេតមានតម្លៃ មួយ ។ ចំណាំថាការសង្កេតនៅក្នុងមេកានិចកង់ទិចត្រូវបានកំណត់ជាធម្មតានៅក្នុងលក្ខខណ្ឌនៃ វិធានការព្យាករដែលមានតម្លៃ នៅលើ ៛ ; ប្រសិនបើអថេរកើតឡើងដាច់ដោយឡែកការវាស់វែងការវាស់វែងត្រូវបានកាត់បន្ថយចំពោះគ្រួសារ {E _λ } indexed លើប៉ារ៉ាម៉ែត្រមួយចំនួនλដែលមានចាប់ពីសំណុំដែលអាចរាប់បាន។ ស្រដៀងគ្នាដែរ អ៊ី មានតម្លៃសង្កេតបាន, អាចត្រូវបានផ្សារភ្ជាប់ជាមួយនឹងក្រុមគ្រួសាររបស់ព្យាករកែង pairwise {អ៊ីមួយ _y } លិបិក្រមដោយធាតុនៃ Y ។ ដូចនោះ

$${\ displaystyle I = \ sum _ {y \ in Y} \ operatorname {E} _ {y} ។ }

ដែលបានផ្តល់ឱ្យរដ្ឋចម្រុះ S , វាត្រូវគ្នានឹងរង្វាស់ប្រូបាប៊ីលីតេលើ អ៊ីដែល បានផ្តល់ឱ្យដោយ

$${\ displaystyle \ operatorname {Pr} \ {y \} = \ operatorname {Tr} (S \ operatorname {E} _ {y}) ។ }

អនុគមន៍ F : X → Y ត្រូវបានគណនាដោយសៀគ្វី U : H _{QB ( r )} → H _{QB ( r )} ទៅក្នុងεប្រសិនបើនិងប្រសិនបើមានតែសម្រាប់ខ្សែអក្សរ x ទាំងអស់ នៃប្រវែង m

$${\ showstyle \ left \ langle {\ vec {x}} 0 {\ big |} {} {{ }, 0 \ right \ rangle = \ left \ langle \ operatorname {E} _ {F (x)} U (| {\ ធំ |} {{ {x}}, 0 \ rangle) \ right \ rangle \ geq 1- \ epsilon ។ }

ឥឡូវ​នេះ

$${\ displaystyle \ left | \ operatorname {Tr} (SU ^ {}} \ operatorname {E} _ {F (x)} U) - \ ខាងឆ្វេង \ langle {\ vec {x}}, 0 {\ big |} U \ {0}} {{ធំ}} {\ vec {x}}, 0 \ right \ {} {\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}} 0 | -S {\ big |}) \ | U ^ {*} \ operatorname {E} _ {F ( x)} U \ | \ leq \ delta}

ដូច្នេះ

$${\ displaystyle \ operatorname {Tr} (SU ^ {*} \ operatorname {E} _ {ហ្វ (x)} U) \ geq 1- \ epsilon - del delta ។

ទ្រឹស្តីបទ ។ ប្រសិនបើε + δ <1/2 បន្ទាប់មកការចែកចាយប្រូបាប

$${\ displaystyle \ operatorname {Pr} \ {y \} = \ operatorname {Tr} (SU ^ {}} \ operatorname {E} _ {y} U)}

នៅលើ Y អាចត្រូវបានគេប្រើដើម្បីកំណត់ F ( x ) ដោយមានប្រូបាប៊ីលីតេតិចតួចនៃកំហុសដោយភាគច្រើនសម្រាប់គំរូទំហំធំគ្រប់គ្រាន់។ ជាពិសេសយក គំរូឯករាជ្យ ឃ ពីប្រូបាប៊ីលីតេនៃការចែកចាយ Pr លើ Y និងជ្រើសរើសយកតម្លៃដែលច្រើនជាងពាក់កណ្តាលនៃគំរូយល់ព្រម។ ប្រូបាប៊ីលីតេដែលតម្លៃ F ( x ) ត្រូវបានគេយកគំរូច្រើនជាង K / 2 ដងយ៉ាងហោចណាស់

$${\ displaystyle 1-e ^ {- 2 \ gamma ^ {2} k},}

ដែលγ = ½-e-δ។

នេះអនុវត្តតាមដោយការដាក់ពាក្យសុំរបស់ Chernoff ។

• Twitter
• Facebook
• Google
• Tumblr
• Pinterest