ക്വാണ്ടം അൽഗോരിതം

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/Quantum_algorithms

ഒരു ക്വാണ്ടം കമ്പ്യൂട്ടറിൽ (ശരിയായ രീതിയിൽ ക്വാണ്ടം കണക്കുകൂട്ടലുകൾ നടത്താനുള്ള ഒരു ഉപകരണം) ഓടിയ്ക്കാൻ സാധിയ്ക്കുന്ന ക്വാണ്ടം ബലതന്ത്രത്തിന്റ ആശയങ്ങൾ നേരിട്ട് ഉപയോഗിയ്ക്കുന്ന ഒരു അൽഗോരിതത്തെ ആണ് ക്വാണ്ടം അൽഗോരിതം എന്ന് വിളിയ്ക്കുന്നത്.^[1]^[2] ഒരു സാധാരണ കമ്പ്യൂട്ടറിൽ ഓടിയ്ക്കാൻ സാധിയ്ക്കുന്ന, അനുക്രമമായ, ഉപകാരപ്രദമായ ഒരു കണക്കുകൂട്ടൽ നടത്താൻ സാധിയ്ക്കുന്ന ഒരു കൂട്ടം നിർദ്ദേശങ്ങളെയാണ് പൊതുവേ അൽഗോരിതം എന്നു വിളിയ്ക്കുന്നത്. ഇതുപോലെ തന്നെ അനുക്രമമായ ഒരു കൂട്ടം നിർദ്ദേശങ്ങളാണ് ക്വാണ്ടം അൽഗോരിതം. ഇതിനെ ഒരു ക്വാണ്ടം കമ്പ്യൂട്ടറിൽ ഓടിയ്ക്കാൻ സാധിയ്ക്കും. സാധാരണ അൽഗോരിതങ്ങളും വേണമെങ്കിൽ ക്വാണ്ടം കമ്പ്യൂട്ടറിൽ ഓടിയ്ക്കാൻ സാധിയ്ക്കുമെങ്കിലും^[3]^:126 പൊതുവേ ക്വാണ്ടം വിശിഷ്ടസ്ഥിതി, ക്വാണ്ടം കെട്ടുപിണച്ചിൽ തുടങ്ങിയ ക്വാണ്ടം പ്രതിഭാസങ്ങളെ ചൂഷണം ചെയ്ത് ഉപകാരപ്രദമായ ഒരു കണക്കുകൂട്ടൽ ചെയ്യാൻ സാധിയ്ക്കുന്ന അൽഗോരിതങ്ങളെയാണ് പൊതുവെ ഈ പേരിൽ വിളിയ്ക്കുന്നത്.

സാധാരണ കമ്പ്യൂട്ടർ വെച്ചു നിർധാരണം ചെയ്യാനാകാത്ത പ്രശ്നങ്ങൾ (Undecidable Problems) ക്വാണ്ടം കമ്പ്യൂട്ടർ വെച്ചും നിർധാരണം ചെയ്യാനാകില്ല.^[4]^:127 എന്നാൽ സാധാരണ കമ്പ്യൂട്ടറിൽ പതിയെ മാത്രം നിർധാരണം ചെയ്യാൻ കഴിയുന്ന ചില പ്രശ്നങ്ങൾ (സമയ സങ്കീർണ്ണത (time complexity) കൂടിയ പ്രശ്നങ്ങൾ ആണ് ഇവിടെ ഉദ്ദേശിയ്ക്കുന്നത്, കൂടുതൽ ശേഷി കൂടിയ പ്രൊസസ്സറുകൾ അല്ല ക്വാണ്ടം കംപ്യൂട്ടറുകൾ) ക്വാണ്ടം അൽഗോരിതങ്ങൾ ഉപയോഗിച്ച് വേഗത്തിൽ നിർധാരണം ചെയാൻ സാധിയ്ക്കും.

ഭാജ്യസംഖ്യകളെ ഘടകക്രിയ ചെയ്യാനുള്ള ഷോറിന്റെ അൽഗോരിതം, അനുക്രമമല്ലാത്ത ഒരു ലിസ്റ്റിലോ ഡാറ്റാബേസിലോ ഡാറ്റാ തിരയാനുള്ള ഗ്രോവർ'സ് അൽഗോരിതം തുടങ്ങിയവയാണ് പ്രശസ്തമായ ക്വാണ്ടം അൽഗോരിതങ്ങൾ. ഘടകക്രിയ ചെയ്യാൻ സാധാരണ കമ്പ്യൂട്ടറിൽ ലഭ്യമായ ഏറ്റവും വേഗതയേറിയ ജനറൽ നമ്പർ ഫീൽഡ് സീവ് എന്ന അൽഗോരിതത്തെക്കാൾ അനേകമടങ്ങ് (exponential increase) ഭേദമാണ് ഷോറിന്റെ അൽഗോരിതത്തിന്റെ സമയ സങ്കീർണ്ണത. അതുപോലെ ഏറ്റവും മികച്ച തിരച്ചിൽ അൽഗോരിതത്തെന്റെ സമയ സങ്കീർണ്ണതയുടെ (അനുക്രമമല്ലാത്ത ലിസ്റ്റിലെ തിരച്ചിൽ) ഒരു വർഗമൂലം മാത്രമാണ് ഗ്രോവർ'സ് അൽഗോരിതത്തിന്റെ സമയ സങ്കീർണ്ണത.

അവലോകനം[തിരുത്തുക]

സാധാരണയായി ക്വാണ്ടം കമ്പ്യൂട്ടിങ്ങിന്റെ സർക്യൂട്ട് മാതൃകയിലാണ് ക്വാണ്ടം അൽഗോരിതങ്ങൾ വിവരിയ്ക്കപ്പെടുന്നത്. ഈ മാതൃകയിൽ ഒരു ക്വാണ്ടം സർക്യൂട്ട് ഒരു കൂട്ടം ക്യൂബിറ്റുകളിൽ പ്രവർത്തിയ്ക്കുകയും അവയുടെ വിലകൾ മാറ്റിക്കൊണ്ടിരിയ്ക്കുകയും ചെയ്യുന്നു. ഇതിന്റ അവസാനം ഒരു ക്വാണ്ടം അളക്കൽ നടത്തുകയും ഒരു സാധാരണ സംഖ്യ ഉത്തരമായി പുറത്തെടുക്കുകയും ചെയ്യുന്നു. ക്വാണ്ടം സർക്യൂട്ട് എന്നത് ഒരു കൂട്ടം ക്വാണ്ടം ഗേറ്റുകളുടെ സമാഹാരമാണ്.

ഒരു അൽഗോരിതത്തിൽ ഉപയോഗിയ്ക്കുന്ന പ്രധാന ക്വാണ്ടം കമ്പ്യൂട്ടിങ് സങ്കേതത്തെ അടിസ്ഥാനപ്പെടുത്തിയാണ് ഇവയെ തരം തിരിയ്ക്കുന്നത്. ഫേസ് കിക്ക്‌ ബാക്, ക്വാണ്ടം ഫ്യൂറിയേ ട്രാൻസ്‌ഫോം, ക്വാണ്ടം വോക്‌സ്, ആംപ്ലിറ്റ്യൂട് ആംപ്ലിഫിക്കേഷൻ തുടങ്ങിയവയാണ് ഇത്തരം സങ്കേതങ്ങൾ.

ക്വാണ്ടം ഫ്യൂറിയേ ട്രാൻസ്‌ഫോമിനെ അടിസ്ഥാനപെടുത്തിയ അൽഗോരിതങ്ങൾ[തിരുത്തുക]

ഡിസ്ക്രീറ്റ് ഫ്യൂറിയേ ട്രാൻസ്‌ഫോമിന്റെ ക്വാണ്ടം പതിപ്പാണ് ക്വാണ്ടം ഫ്യൂറിയേ ട്രാൻസ്‌ഫോം. പല ക്വാണ്ടം അൽഗോരിതങ്ങളിലും ഇത് ഉപയോഗിയ്ക്കുന്നുണ്ട്. നിർധാരണം ചെയ്യേണ്ട പ്രശ്‌നത്തിന്റെ ഇന്പുട് വിലകളുടെ എണ്ണം $N$ ആണെങ്കിൽ പരമാവധി $O(N)$ ക്വാണ്ടം ഗേറ്റുകൾ മാത്രം ഉപയോഗിച്ച് ക്വാണ്ടം ഫ്യൂറിയേ ട്രാൻസ്‌ഫോം നടത്താനുള്ള ഒരു ക്വാണ്ടം സർക്യൂട്ട് ഉണ്ടാക്കിയെടുക്കാവുന്നതാണ്.

പൊതുവെ ഇത്തരം അൽഗോരിതങ്ങളിൽ തന്നിരിയ്ക്കുന്ന പ്രശ്നത്തിന്റെ സെറ്റ് അപ്പിനെ ആദ്യം ഒരു തരംഗമായി മോഡൽ ചെയ്യുന്നു. അതിനുശേഷം തന്നിരിയ്ക്കുന്ന പ്രശ്നത്തെ ഈ തരംഗത്തിന്റെ തരംഗദൈർഘ്യം കണ്ടെത്തുന്ന ഒരു പ്രശ്നമായി രൂപാന്തരണം നടത്തുന്നു. അതിനു ശേഷം ക്വാണ്ടം ഫ്യൂറിയേ ട്രാൻസ്‌ഫോം ഉപയോഗിച്ച് തരംഗദൈർഘ്യം കണ്ടുപിടിയ്ക്കുന്നു.^[5]

ഡോയ്ഷ്-ജോസ അൽഗോരിതം (Deutsch–Jozsa algorithm)[തിരുത്തുക]

ഇത് പ്രത്യേകിച്ച് ഉപകാരം ഒന്നും ഇല്ലാത്ത, എന്നാൽ ക്വാണ്ടം കമ്പ്യൂട്ടിങ്ങിന്റെ പ്രത്യേകതകൾ എടുത്തു കാണിയ്ക്കാനായി ഡേവിഡ് ഡോയ്‌ഷും റിച്ചാർഡ് ജോസയും 1992 ൽ മുന്നോട്ടു വെച്ച ഒരു അൽഗോരിതം ആണ്. ഇവിടെ ഒരു പ്രത്യേക ഫങ്ക്ഷൻ ഉണ്ട്. ഇത് ഒന്നുകിൽ അതിലേയ്ക്ക് പാസ് ചെയ്യുന്ന ഏതു ബിറ്റ് കോമ്പിനേഷനും ഒരേ ഔട്ട്പുട്ട് (ഒന്നുകിൽ എല്ലാ കോമ്പിനേഷനും ഔട്ട്പുട്ട് ആയി 0; അല്ലെങ്കിൽ എല്ലാ കോമ്പിനേഷനും 1) തരും അല്ലെങ്കിൽ പകുതി ഇൻപുട്ടുകൾക്ക് ഉത്തരം 0 വും ബാക്കി പകുതി ഇൻപുട്ടുകൾക്ക് ഉത്തരം 1 ഉം തരും. നമുക്ക് കണ്ടു പിടിയ്ക്കേണ്ടത് ഈ ഫങ്ക്ഷൻ ആദ്യത്തേത് പോലെ ആണോ അതോ രണ്ടാമത്തേത് പോലെ ആണോ പ്രവർത്തിയ്ക്കുന്നത് എന്നാണ്. സാധാരണ ഒരു കമ്പ്യൂട്ടറിൽ ഇത് തീരുമാനിയ്ക്കാനായി പകുതി എണ്ണം ഇന്പുട് എങ്കിലും കൊടുത്തു നോക്കണമല്ലോ. അതായത് $n$ ബിറ്റുകൾ ഉള്ള ഒരു കോമ്പിനേഷൻ ആണ് ഇന്പുട് എങ്കിൽ $O(2^{n})$ ആണ് ഇതിന്റ സമയ സങ്കീർണ്ണത. എന്നാൽ ഒറ്റ ഇന്പുട് മാത്രം കൊടുത്തു ഉത്തരം കണ്ടു പിടിയ്ക്കാവുന്ന ഒരു ക്വാണ്ടം അൽഗോരിതം ഇതിനു വേണ്ടി ഡിസൈൻ ചെയ്യാൻ സാധിയ്ക്കും.

സൈമണിന്റെ അൽഗോരിതം(Simon's algorithm)[തിരുത്തുക]

ഇതും മുകളിൽ പറഞ്ഞ അൽഗോരിതം പോലെ തന്നെ പ്രായോഗിക ഉപകാരങ്ങൾ ഒന്നുമില്ലാത്ത, എന്നാൽ ക്വാണ്ടം കമ്പ്യൂട്ടിങ്ങിന്റെ ശക്തി എടുത്തു കാണിയ്ക്കാനുള്ള മറ്റൊരു ക്വാണ്ടം അൽഗോരിതം ആണ്. ഷോറിന്റെ അൽഗോരിതത്തിന് ഒരു പ്രേരണ ഈ അൽഗോരിതമാണ്.

ഷോറിന്റെ അൽഗോരിതം(Shor's algorithm)[തിരുത്തുക]

ഇത് വളരെ പ്രായോഗിക ഉപകാരങ്ങളുള്ള വളരെ പ്രധാനപ്പെട്ട ഒരു ക്വാണ്ടം അൽഗോരിതം ആണ്. ഭാജ്യസംഖ്യകളെ ഘടകക്രിയ ചെയ്യുക എന്നുള്ളതാണ് ഇതിന്റെ കർത്തവ്യം. പോളിനോമിയൽ സമയ സങ്കീർണ്ണതയിൽ ഘടകക്രിയ ചെയ്യാം എന്നുള്ളതാണ് ഇതിന്റെ നേട്ടം. ഏറ്റവും മികച്ച സമയ സങ്കീർണ്ണതയുള്ള സാധാരണ കംപ്യൂട്ടറിലെ അൽഗോരിതം പോലും ഇതിനു വേണ്ടി എക്സ്പോണെൻഷ്യൽ സമയം എടുക്കും.^[6]

ഹിഡൻ സബ്ഗ്രൂപ് പ്രോബ്ലം (Hidden Subgroup Problem), ബോസോൺ സാംപ്ലിങ് പ്രോബ്ലം (Boson Sampling Problem), ഗൗസ് സം എസ്റ്റിമേഷൻസ് (Gauss Sum Estimations), ഫ്യൂറിയേ ഫിഷിങ്, ഫ്യൂറിയേ ചെക്കിങ് തുടങ്ങിയവയും ക്വാണ്ടം ഫ്യൂറിയേ ട്രാൻസ്‌ഫോമിനെ അടിസ്ഥാനപെടുത്തിയ മറ്റു അൽഗോരിതങ്ങൾ ആണ്.^[7]

ആംപ്ലിറ്റ്യൂട് ആംപ്ലിഫിക്കേഷൻ അടിസ്ഥാനമായുള്ള അൽഗോരിതങ്ങൾ[തിരുത്തുക]

ഒരു ക്വാണ്ടം അവസ്ഥയുടെ ഹിൽബെർട് സ്പേസ് ഡിസൈൻ ചെയ്ത ശേഷം അതിന്റെ ഒരു 'നല്ല' ഉപ സ്പേസ് (subspace) കണ്ടെത്തിയ ശേഷം അതിന്റെ ആംപ്ലിറ്റ്യൂട് വർധിപ്പിച്ചാണ് ഇത്തരം അൽഗോരിതങ്ങൾ പ്രവർത്തിയ്ക്കുന്നത്. സാദാ അൽഗോരിതങ്ങളുടെ ഒരു വർഗമൂലം അധ്വാനം മാത്രമാണ് ഇത്തരം അൽഗോരിതങ്ങൾ എടുക്കുക. ഗ്രോവേഴ്സ് അൽഗോരിതം (Grover's Algorithm) ആണ് ഇത്തരം അൽഗോരിതങ്ങളിൽ ഏറ്റവും പ്രശസ്തം. അനുക്രമമല്ലാത്ത ഒരു ലിസ്റ്റിലെയോ ഡാറ്റാബേസിലെയോ ഒരു അംഗത്തെ തെരയാനുള്ള അൽഗോരിതമാണ് ഇത്. $N$ അംഗങ്ങളുള്ള ഇത്തരം ഒരു ലിസ്റ്റിൽ തിരയാൻ സാദാ അൽഗോരിതങ്ങൾ വെച്ച് $O(N)$ സ്റ്റെപ്പുകൾ (വരികൾ) വേണം. എന്നാൽ ഗ്രോവേഴ്സ് അൽഗോരിതം ഉപയോഗിച്ച് $O({\sqrt {N}})$ സ്റ്റെപ്പുകളിൽ ഇത് തെരഞ്ഞു കണ്ടു പിടിയ്ക്കാം.^[8]

ക്വാണ്ടം വോക്കുകളെ അടിസ്ഥാനപ്പെടുത്തിയ അൽഗോരിതങ്ങൾ[തിരുത്തുക]

സാധാരണ കമ്പ്യൂട്ടറിൽ ചെയ്യുന്ന റാൻഡം വോക് എന്ന ടൈപ്പ് അൽഗോരിതങ്ങളുടെ ക്വാണ്ടം പതിപ്പാണ് ഇവ. ഒരു സെറ്റ് അവസ്ഥകളിൽ ഒരു പ്രത്യേക സംഭാവ്യതാ വിതരണത്തെ (probability distribution) അടിസ്ഥാനപ്പെടുത്തി ഒന്നിൽ നിന്നും മറ്റൊന്നിലേക്ക് നീങ്ങുന്ന പ്രക്രിയയെ സിമുലേറ്റ് ചെയ്യുന്നതാണ് റാൻഡം വോക് അൽഗോരിതങ്ങൾ ചെയ്യുന്നത്. ക്വാണ്ടം വോക് അൽഗോരിതങ്ങൾ ഇത്തരം അവസ്ഥകളുടെ വിശിഷ്ടസ്ഥിതിയെ ചൂഷണം ചെയ്താണ് കൂടുതൽ വേഗത കൈവരിയ്ക്കുന്നത്.^[9]^[10] എലമെന്റ് ഡിസ്റ്റിംക്ട്നെസ്സ് (Element Distinctness), ട്രയാങ്കിൾ ഫൈൻഡിങ് പ്രോബ്ലം (Triangle-finding Problem), ഫോർമുല ഇവാലുവേഷൻ (Formula Evaluation), ഗ്രൂപ്പ് കമ്മ്യൂറ്റേറ്റിവിറ്റി (group commutativity) തുടങ്ങിയവ ഈ ഗണത്തിൽ പെടുന്ന അൽഗോരിതങ്ങളാണ്.

ഇവ കൂടി കാണുക[തിരുത്തുക]

അവലംബം[തിരുത്തുക]

↑ Nielsen, M.; Chuang, I. (2000). Quantum Computation and Quantum Information. Cambridge University Press. ISBN 0-521-63503-9.
↑ Mosca, M. (2008). "Quantum Algorithms". arΧiv: 0808.0369 [quant-ph].
↑ Lanzagorta, Marco; Uhlmann, Jeffrey K. (2009-01-01). Quantum Computer Science. Morgan & Claypool Publishers. ISBN 9781598297324.
↑ Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3.
↑ "QFT, Period Finding & Shor's Algorithm" (PDF).
↑ Shor, P. W. (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Scientific and Statistical Computing. 26: 1484–1509. arXiv:quant-ph/9508027. Bibcode:1995quant.ph..8027S. doi:10.1137/s0097539795293172.
↑ Regev, O. (2003). "Quantum Computation and Lattice Problems". arΧiv: cs/0304005 [cs.DS].
↑ Grover, L. K. (1996). "A fast quantum mechanical algorithm for database search". arΧiv: quant-ph/9605043 [quant-ph].
↑ Childs, A. M.; Cleve, R.; Deotto, E.; Farhi, E.; Gutmann, S.; Spielman, D. A. (2003). "Exponential algorithmic speedup by quantum walk". Proceedings of the 35th Symposium on Theory of Computing. Association for Computing Machinery. pp. 59–68. arXiv:quant-ph/0209131. doi:10.1145/780542.780552. ISBN 1-58113-674-9. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
↑ Childs, A. M.; Schulman, L. J.; Vazirani, U. V. (2007). "Quantum Algorithms for Hidden Nonlinear Structures". Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. IEEE. pp. 395–404. arXiv:0705.2784. doi:10.1109/FOCS.2007.18. ISBN 0-7695-3010-9. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)

[1] Nielsen, M.; Chuang, I. (2000). Quantum Computation and Quantum Information. Cambridge University Press. ISBN 0-521-63503-9.

[2] Mosca, M. (2008). "Quantum Algorithms". arΧiv: 0808.0369 [quant-ph].

[3] Lanzagorta, Marco; Uhlmann, Jeffrey K. (2009-01-01). Quantum Computer Science. Morgan & Claypool Publishers. ISBN 9781598297324.

[nielchuan-4] Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3.

[5] "QFT, Period Finding & Shor's Algorithm" (PDF).

[6] Shor, P. W. (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Scientific and Statistical Computing. 26: 1484–1509. arXiv:quant-ph/9508027. Bibcode:1995quant.ph..8027S. doi:10.1137/s0097539795293172.

[7] Regev, O. (2003). "Quantum Computation and Lattice Problems". arΧiv: cs/0304005 [cs.DS].

[8] Grover, L. K. (1996). "A fast quantum mechanical algorithm for database search". arΧiv: quant-ph/9605043 [quant-ph].

[9] Childs, A. M.; Cleve, R.; Deotto, E.; Farhi, E.; Gutmann, S.; Spielman, D. A. (2003). "Exponential algorithmic speedup by quantum walk". Proceedings of the 35th Symposium on Theory of Computing. Association for Computing Machinery. pp. 59–68. arXiv:quant-ph/0209131. doi:10.1145/780542.780552. ISBN 1-58113-674-9. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)

[10] Childs, A. M.; Schulman, L. J.; Vazirani, U. V. (2007). "Quantum Algorithms for Hidden Nonlinear Structures". Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. IEEE. pp. 395–404. arXiv:0705.2784. doi:10.1109/FOCS.2007.18. ISBN 0-7695-3010-9. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]