ប្រធានបទ (Topic)៖ ឯកសារនេះដោះស្រាយលើការយល់ដឹងពីមូលដ្ឋានគ្រឹះនៃការគណនាកង់ទិច (Quantum computation) ដោយប្រៀបធៀបវាទៅនឹងទ្រឹស្តីកុំព្យូទ័របុរាណ និងថ្នាក់នៃភាពស្មុគស្មាញ (Complexity classes)។
រចនាសម្ព័ន្ធ (Structure)៖ អត្ថបទនេះប្រើប្រាស់វិធីសាស្ត្រពន្យល់ពីប្រវត្តិសាស្រ្ត ទ្រឹស្តី និងគំរូគណិតវិទ្យា ដោយផ្តើមចេញពីការគណនាសៀគ្វីបុរាណ រហូតដល់គោលការណ៍កង់ទិច។
ចំណុចសំខាន់ៗ (Key Takeaways)៖
បន្ទាប់ពីអានឯកសារនេះ អ្នកគួរអាច៖
ជំពូកនេះផ្តល់នូវសេចក្តីផ្តើមអំពីការគណនាកង់ទិច ដោយចាប់ផ្តើមពីការរំលឹកឡើងវិញនូវទ្រឹស្តីកុំព្យូទ័របុរាណ ម៉ាស៊ីនធូរីង (Turing Machine) និងថ្នាក់ភាពស្មុគស្មាញនៃការគណនា (Complexity classes)។ បន្ទាប់មក វាពន្យល់ពីការគណនាដែលអាចត្រឡប់ដើមវិញបាន មុននឹងឈានចូលដល់ការណែនាំគំរូនៃសៀគ្វីកង់ទិច ការប្រើប្រាស់ច្រកកង់ទិចសកល និងការប្រៀបធៀបថ្នាក់ភាពស្មុគស្មាញកង់ទិច BQP ទៅនឹងថ្នាក់គណនាបុរាណ រួមទាំងសក្តានុពលនៃការដោះស្រាយបញ្ហាបានលឿនជាអិចស្ប៉ូណង់ស្យែល។
| គោលគំនិត (Concept) | ការពន្យល់ (Explanation) | ឧទាហរណ៍ (Example) |
|---|---|---|
| Turing Machine and Church-Turing Thesis ម៉ាស៊ីនធូរីង និងសម្មតិកម្ម Church-Turing |
ម៉ាស៊ីន Turing គឺជាគំរូទ្រឹស្តីនៃម៉ាស៊ីនកុំព្យូទ័រដែលត្រូវបានបង្កើតឡើងដើម្បីដោះស្រាយរាល់បញ្ហាគណិតវិទ្យាដែលអាចគណនាបាន។ សម្មតិកម្ម Church-Turing បញ្ជាក់ថារាល់អនុគមន៍ដែលចាត់ទុកថាអាចគណនាបានដោយធម្មជាតិ គឺអាចគណនាបានដោយម៉ាស៊ីនធូរីងសកលនេះឯង។ | ទោះបីជាយើងសរសេរកូដនៅលើកុំព្យូទ័រយួរដៃទំនើប ឬម៉ាស៊ីនមេដ៏ធំក៏ដោយ តាមទ្រឹស្តីក្បួនដោះស្រាយនោះអាចបំប្លែងឱ្យរត់លើម៉ាស៊ីនធូរីងបានដោយគ្រាន់តែប្រើប្រាស់ពេលវេលាបន្ថែមក្នុងកម្រិតពហុធា (Polynomial overhead) ប៉ុណ្ណោះ។ |
| Complexity Classes (P, NP, BPP, BQP) ថ្នាក់ភាពស្មុគស្មាញ (P, NP, BPP, BQP) |
ថ្នាក់ភាពស្មុគស្មាញចាត់ថ្នាក់បញ្ហាគណិតវិទ្យាផ្អែកលើពេលវេលា និងធនធានដែលត្រូវការដើម្បីដោះស្រាយវា។ ថ្នាក់ P តំណាងឱ្យបញ្ហាដែលងាយស្រួលដោះស្រាយ ចំណែក BQP (Bounded error quantum polynomial) គឺជាថ្នាក់នៃបញ្ហាដែលអាចដោះស្រាយបានដោយប្រសិទ្ធភាពតាមរយៈកុំព្យូទ័រកង់ទិច។ | បញ្ហាបំបែកកត្តាចំនួនបឋមដ៏ធំ (FACTORING) ត្រូវបានគេជឿថាមិនស្ថិតក្នុងថ្នាក់ P ទេ (កុំព្យូទ័របុរាណត្រូវការពេលរាប់ពាន់ឆ្នាំដើម្បីដោះស្រាយ) ប៉ុន្តែវាស្ថិតក្នុងថ្នាក់ BQP ដែលកុំព្យូទ័រកង់ទិចអាចដោះស្រាយបានលឿន។ |
| Reversible Computation ការគណនាដែលអាចត្រឡប់ដើមវិញបាន |
ជាដំណើរការគណនាដែលមិនមានការបាត់បង់ ឬលុបព័ត៌មានចោលឡើយ ដែលជួយជៀសវាងការប្រើប្រាស់ថាមពលកម្ដៅដែលរាយប៉ាយ (ផ្អែកលើគោលការណ៍ Landauer)។ រាល់សៀគ្វីបុរាណអាចបំប្លែងទៅជាសៀគ្វីដែលអាចត្រឡប់ដើមវិញបាន ដោយប្រើច្រកសកលពិសេសៗ។ | ការប្រើប្រាស់ច្រក C-NOT ដើម្បីធ្វើឱ្យប្រតិបត្តិការច្រក XOR បុរាណអាចត្រឡប់ដើមវិញបាន ដោយការបន្ថែមប៊ីត (Bit) លទ្ធផលមួយទៀតដើម្បីរក្សាទិន្នន័យដើមមិនឱ្យបាត់បង់។ |
| Quantum Circuits and No-Cloning Theorem សៀគ្វីកង់ទិច និងទ្រឹស្តីហាមការថតចម្លង (No-Cloning) |
សៀគ្វីកង់ទិចដំណើរការលើ Qubits ជំនួសឱ្យ Bits ហើយរាល់ប្រតិបត្តិការទាំងអស់គឺជាការផ្លាស់ប្តូរយូនីតារី (Unitary) ដែលអាចត្រឡប់ដើមវិញបានជានិច្ច។ ដោយសារទ្រឹស្តីកង់ទិច (No-cloning theorem) វាជារឿងមិនអាចទៅរួចទេក្នុងការថតចម្លងស្ថានភាពកង់ទិចដែលមិនស្គាល់អត្តសញ្ញាណបានយ៉ាងល្អឥតខ្ចោះ។ | នៅក្នុងការរចនាសៀគ្វីកង់ទិច យើងមិនអាចមានច្រក FANOUT ដូចក្នុងកុំព្យូទ័របុរាណ ដើម្បីចម្លងទិន្នន័យពី Qubit មួយទៅ Qubit មួយទៀតដោយផ្ទាល់នោះទេ។ |
| Quantum Speed-ups ការបង្កើនល្បឿនតាមបែបកង់ទិច |
នេះគឺជាសមត្ថភាពនៃក្បួនដោះស្រាយកង់ទិចក្នុងការដោះស្រាយបញ្ហាជាក់លាក់បានលឿនជាងក្បួនដោះស្រាយកុំព្យូទ័របុរាណដ៏ល្អបំផុត។ វាមានច្រើនទម្រង់ ដូចជាការបង្កើនល្បឿនជាអិចស្ប៉ូណង់ស្យែល (Exponential) ឬកម្រិតការ៉េ (Quadratic)។ | ក្បួនដោះស្រាយ Shor (Shor's algorithm) ផ្តល់នូវការបង្កើនល្បឿនជាអិចស្ប៉ូណង់ស្យែលលើបញ្ហាបំបែកកត្តា ដែលធ្វើឱ្យកុំព្យូទ័រកង់ទិចអាចដោះស្រាយវាបានក្នុងរយៈពេលខ្លី ខណៈកុំព្យូទ័របុរាណមិនអាចដោះស្រាយបានទាល់តែសោះ។ |
ទោះបីជាបច្ចេកវិទ្យាកង់ទិចស្ថិតក្នុងដំណាក់កាលស្រាវជ្រាវកម្រិតខ្ពស់នៅលើពិភពលោកក៏ដោយ ការយល់ដឹងពីមូលដ្ឋានទ្រឹស្តីនៃការគណនានេះមានសារៈសំខាន់ខ្លាំងសម្រាប់ការអភិវឌ្ឍធនធានមនុស្សនៅកម្ពុជាឱ្យស្របតាមការវិវឌ្ឍនៃបច្ចេកវិទ្យានាពេលអនាគត។
ការណែនាំគោលគំនិតនៃការគណនាកង់ទិចដល់និស្សិតកម្ពុជានឹងបើកផ្លូវឱ្យពួកគេអភិវឌ្ឍការគិតបែបស៊ីជម្រៅ ត្រៀមខ្លួនប្រកួតប្រជែងក្នុងវិស័យវិទ្យាសាស្ត្រកុំព្យូទ័រអន្តរជាតិ និងចាប់យកឱកាសក្នុងបដិវត្តន៍បច្ចេកវិទ្យាជំនាន់ទី៤។
លំហាត់ និងសកម្មភាពសិក្សាដើម្បីពង្រឹងការយល់ដឹង៖
| ពាក្យបច្ចេកទេស (English) | ការពន្យល់ជាខេមរភាសា (Khmer Explanation) | និយមន័យសាមញ្ញ (Simple Definition) |
|---|---|---|
| Universal Turing Machine | គំរូទ្រឹស្តីនៃម៉ាស៊ីនកុំព្យូទ័រដែលស្នើឡើងដោយលោក Alan Turing ដែលអាចគណនារាល់បញ្ហាគណិតវិទ្យាដែលអាចដោះស្រាយបានដោយប្រើក្បួនដោះស្រាយ។ វាជាមូលដ្ឋានគ្រឹះក្នុងការសិក្សាពីដែនកំណត់នៃកុំព្យូទ័រទំនើប និងទ្រឹស្តីនៃភាពស្មុគស្មាញ។ | ដូចជាចុងភៅដ៏ចំណានម្នាក់ដែលអាចចម្អិនរាល់មុខម្ហូបទាំងអស់នៅលើលោក ឱ្យតែអ្នកមានសៀវភៅរូបមន្ត (ក្បួនដោះស្រាយ) ត្រឹមត្រូវប្រាប់គាត់។ |
| Church-Turing Thesis | សម្មតិកម្មដែលចែងថារាល់អនុគមន៍ដែលចាត់ទុកថា "អាចគណនាបានដោយធម្មជាតិ" គឺអាចគណនាបានដោយម៉ាស៊ីន Universal Turing Machine។ ទោះបីវាមិនអាចបញ្ជាក់ជាទ្រឹស្តីបទគណិតវិទ្យាដាច់ខាត ប៉ុន្តែវាត្រូវបានទទួលស្គាល់យ៉ាងទូលំទូលាយថាជាការពិតក្នុងរូបវិទ្យា។ | ដូចជាការសន្មត់ថា "រាល់ការធ្វើដំណើរលើគោកទាំងអស់អាចធ្វើទៅបានដោយការដើរ" ទោះបីជាមានយានយន្តទំនើបៗក៏ដោយ ក៏ការដើរនៅតែអាចទៅដល់គោលដៅដដែលឱ្យតែមានផ្លូវ។ |
| Complexity classes | ការបែងចែកប្រភេទបញ្ហាគណិតវិទ្យាទៅតាមបរិមាណធនធាន (ដូចជាពេលវេលា ឬទំហំអង្គចងចាំ) ដែលត្រូវការដើម្បីដោះស្រាយពួកវា ដោយប្រើថ្នាក់ដូចជា P (ដោះស្រាយបានលឿន) និង NP (ពិបាកដោះស្រាយ តែងាយស្រួលផ្ទៀងផ្ទាត់ចម្លើយ)។ | ដូចជាការបែងចែកកម្រិតលំបាកនៃវិញ្ញាសាប្រឡង ខ្លះងាយស្រួលធ្វើ (P) ខ្លះពិបាកធ្វើតែបើមានចម្លើយស្រាប់គឺងាយស្រួលផ្ទៀងផ្ទាត់ថាត្រូវឬខុស (NP)។ |
| Reversible computation | ដំណើរការគណនាដែលមិនមានការលុបបំបាត់ចោលនូវព័ត៌មាន (bits) ឡើយ ដែលមានន័យថាគេអាចយកលទ្ធផលត្រឡប់ទៅរកទិន្នន័យដើមវិញបានជានិច្ច។ នេះជួយកាត់បន្ថយការបញ្ចេញកម្តៅនៃកុំព្យូទ័រ (តាមគោលការណ៍ Landauer's principle) និងជាមូលដ្ឋានគ្រឹះនៃច្រកកង់ទិច។ | ដូចជាការចងខ្សែស្បែកជើងដែលយើងអាចស្រាយវាត្រឡប់មកសភាពដើមវិញបានដោយមិនបាច់កាត់ខ្សែចោល ខុសពីការដុតក្រដាសដែលមិនអាចប្រែជាក្រដាសវិញបាន។ |
| Universal set of gates | សំណុំនៃច្រកតក្កវិទ្យា (logic gates) តិចតួចបំផុត (ឧទាហរណ៍៖ ច្រក NAND សម្រាប់កុំព្យូទ័របុរាណ ឬច្រក Toffoli/Deutsch សម្រាប់កង់ទិច) ដែលអាចផ្សំគ្នាដើម្បីបង្កើតជាប្រតិបត្តិការសៀគ្វីដ៏ស្មុគស្មាញណាមួយក៏បាន។ | ដូចជាដុំឡេហ្គោ (Lego) ជាមូលដ្ឋានមួយចំនួនតូច ដែលយើងអាចយកមកតភ្ជាប់គ្នាដើម្បីសាងសង់ជារូបរាងអ្វីក៏បានតាមការស្រមើស្រមៃ។ |
| no-cloning theorem | ទ្រឹស្តីបទក្នុងមេកានិចកង់ទិចដែលបញ្ជាក់ថា វាជារឿងមិនអាចទៅរួចទេក្នុងការបង្កើតច្បាប់ចម្លង (copy) ដ៏ល្អឥតខ្ចោះនៃស្ថានភាពកង់ទិចដែលយើងមិនស្គាល់ជាមុន។ នេះជាមូលហេតុដែលសៀគ្វីកង់ទិចមិនអាចមានច្រក FANOUT (ច្រកថតចម្លងទិន្នន័យ) ដូចកុំព្យូទ័របុរាណ។ | ដូចជាការមិនអាចថតចម្លង (Photocopy) ឯកសារសម្ងាត់វេទមន្តមួយបានឡើយ ព្រោះពេលដែលម៉ាស៊ីនចាប់ផ្តើមស្កេនវា អក្សរនៅលើឯកសារនោះនឹងប្រែប្រួល ឬរលាយបាត់អស់ភ្លាមៗ។ |
| BQP | មកពីពាក្យពេញ Bounded error Quantum Polynomial time គឺជាថ្នាក់នៃបញ្ហាដែលអាចដោះស្រាយបានដោយកុំព្យូទ័រកង់ទិចក្នុងរយៈពេលសមស្រប (polynomial time) ជាមួយនឹងប្រូបាប៊ីលីតេនៃកំហុសតិចតួចដែលអាចទទួលយកបាន។ វាជាសំណុំបញ្ហាដែលកង់ទិចពូកែដោះស្រាយជាងកុំព្យូទ័របុរាណ។ | ជាក្រុមប្រភេទបញ្ហាដែលកុំព្យូទ័រកង់ទិចអាចដោះស្រាយបានយ៉ាងរលូន និងលឿន ដូចជាការប្រើប្រាស់ម៉ាស៊ីនគិតលេខដើម្បីដោះស្រាយលំហាត់គុណលេខធំៗ ជំនួសឱ្យការគិតដោយប្រើក្រដាសនិងប៊ិច។ |
| Quantum algorithm | លំដាប់លំដោយនៃប្រតិបត្តិការកង់ទិច (រួមមានការរៀបចំ qubit ដើម ការអនុវត្តសៀគ្វីកង់ទិចតាមរយៈច្រកសកល និងការវាស់វែងចុងក្រោយ) ដើម្បីដោះស្រាយបញ្ហាណាមួយដោយទាញយកអត្ថប្រយោជន៍ពីបាតុភូតកង់ទិចដូចជា Superposition និង Entanglement។ | ដូចជារូបមន្តធ្វើម្ហូបពិសេសមួយដែលប្រើប្រាស់ចង្ក្រានវិទ្យាសាស្ត្រទំនើប (កុំព្យូទ័រកង់ទិច) ដើម្បីចម្អិនម្ហូបដ៏ស្មុគស្មាញក្នុងរយៈពេលខ្លីបំផុត ដែលចង្ក្រានធម្មតាមិនអាចធ្វើបាន។ |
អត្ថបទដែលបានបោះពុម្ពនៅលើ KhmerResearch ដែលទាក់ទងនឹងប្រធានបទនេះ៖
ប្រធានបទ និងសំណួរស្រាវជ្រាវដែលទាក់ទងនឹងឯកសារនេះ ដែលអ្នកអាចស្វែងរកបន្ថែម៖
