Квантові обчислення: огляд та аналіз
Зроблено огляд та аналіз основних понять і положень квантової моделі обчислень, ефективних квантових алгоритмів, останніх результатів, можливостей та перспектив у побудові масштабованого квантового комп'ютера. Розглянуто певний клас алгебраїчних задач у квантовій моделі обчислень, для яких існу...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2019 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/179388 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Квантові обчислення: огляд та аналіз / М.М. Савчук, А.В. Фесенко // Кибернетика и системный анализ. — 2019. — Т. 55, № 1. — С. 14-29. — Бібліогр.: 17 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-179388 |
|---|---|
| record_format |
dspace |
| spelling |
Савчук, М.М. Фесенко, А.В. 2021-05-04T17:56:17Z 2021-05-04T17:56:17Z 2019 Квантові обчислення: огляд та аналіз / М.М. Савчук, А.В. Фесенко // Кибернетика и системный анализ. — 2019. — Т. 55, № 1. — С. 14-29. — Бібліогр.: 17 назв. — укр. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/179388 004.383 Зроблено огляд та аналіз основних понять і положень квантової моделі обчислень, ефективних квантових алгоритмів, останніх результатів, можливостей та перспектив у побудові масштабованого квантового комп'ютера. Розглянуто певний клас алгебраїчних задач у квантовій моделі обчислень, для яких існує ефективний квантовий алгоритм розв'язку. Проведено детальний аналіз наявних практичних реалізацій квантового комп'ютера. Показано, що на сьогодні немає достатнього прогресу у побудові масштабованого квантового обчислювального пристрою, проте більшість дослідників очікують на створення повноцінного квантового комп'ютера впродовж наступних 10 15 років. Выполнен обзор и анализ основных понятий и положений квантовой модели вычисления, эффективных квантовых алгоритмов, последних результатов, возможностей и перспектив в построении масштабированного квантового компьютера. Рассмотрен некоторый класс алгебраических задач в квантовой модели вычислений, для которых существует эффективный квантовый алгоритм решения. Проведен детальный анализ существующих практических реализаций квантового компьютера и показано, что пока что нет достаточного прогресса в построении масштабированного квантового вычислительного устройства, но, тем не менее, большинство исследователей ожидают создание полноценного квантового компьютера в течение следующих 10 15 лет. The authors conduct a survey and analysis of the main concepts and postulates of the quantum computing model, efficient quantum algorithms, recent results, capabilities, and prospects in constructing a scalable quantum computer. A certain class of algebraic problems in a quantum computation model is considered, for which there and efficient quantum solution algorithm exists. A detailed analysis of available quantum computer implementations has been carried out and it has been shown that sufficient progress has yet been made in constructing a scalable quantum computing device; nevertheless, most of researchers expect a quantum computer to be created in the next 10–15 years. uk Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кібернетика Квантові обчислення: огляд та аналіз Квантовые вычисления: обзор и анализ Quantum computing: survey and analysis Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Квантові обчислення: огляд та аналіз |
| spellingShingle |
Квантові обчислення: огляд та аналіз Савчук, М.М. Фесенко, А.В. Кібернетика |
| title_short |
Квантові обчислення: огляд та аналіз |
| title_full |
Квантові обчислення: огляд та аналіз |
| title_fullStr |
Квантові обчислення: огляд та аналіз |
| title_full_unstemmed |
Квантові обчислення: огляд та аналіз |
| title_sort |
квантові обчислення: огляд та аналіз |
| author |
Савчук, М.М. Фесенко, А.В. |
| author_facet |
Савчук, М.М. Фесенко, А.В. |
| topic |
Кібернетика |
| topic_facet |
Кібернетика |
| publishDate |
2019 |
| language |
Ukrainian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Квантовые вычисления: обзор и анализ Quantum computing: survey and analysis |
| description |
Зроблено огляд та аналіз основних понять і положень квантової моделі обчислень, ефективних квантових алгоритмів, останніх результатів, можливостей та перспектив у побудові масштабованого квантового комп'ютера. Розглянуто певний клас алгебраїчних задач у квантовій моделі обчислень, для яких існує ефективний квантовий алгоритм розв'язку. Проведено детальний аналіз наявних практичних реалізацій квантового комп'ютера. Показано, що на сьогодні немає достатнього прогресу у побудові масштабованого квантового обчислювального пристрою, проте більшість дослідників очікують на створення повноцінного квантового комп'ютера впродовж наступних 10 15 років.
Выполнен обзор и анализ основных понятий и положений квантовой модели вычисления, эффективных квантовых алгоритмов, последних результатов, возможностей и перспектив в построении масштабированного квантового компьютера. Рассмотрен некоторый класс алгебраических задач в квантовой модели вычислений, для которых существует эффективный квантовый алгоритм решения. Проведен детальный анализ существующих практических реализаций квантового компьютера и показано, что пока что нет достаточного прогресса в построении масштабированного квантового вычислительного устройства, но, тем не менее, большинство исследователей ожидают создание полноценного квантового компьютера в течение следующих 10 15 лет.
The authors conduct a survey and analysis of the main concepts and postulates of the quantum computing model, efficient quantum algorithms, recent results, capabilities, and prospects in constructing a scalable quantum computer. A certain class of algebraic problems in a quantum computation model is considered, for which there and efficient quantum solution algorithm exists. A detailed analysis of available quantum computer implementations has been carried out and it has been shown that sufficient progress has yet been made in constructing a scalable quantum computing device; nevertheless, most of researchers expect a quantum computer to be created in the next 10–15 years.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/179388 |
| citation_txt |
Квантові обчислення: огляд та аналіз / М.М. Савчук, А.В. Фесенко // Кибернетика и системный анализ. — 2019. — Т. 55, № 1. — С. 14-29. — Бібліогр.: 17 назв. — укр. |
| work_keys_str_mv |
AT savčukmm kvantovíobčislennâoglâdtaanalíz AT fesenkoav kvantovíobčislennâoglâdtaanalíz AT savčukmm kvantovyevyčisleniâobzorianaliz AT fesenkoav kvantovyevyčisleniâobzorianaliz AT savčukmm quantumcomputingsurveyandanalysis AT fesenkoav quantumcomputingsurveyandanalysis |
| first_indexed |
2025-11-26T03:46:53Z |
| last_indexed |
2025-11-26T03:46:53Z |
| _version_ |
1850610535687520256 |
| fulltext |
ÓÄÊ 004.383
Ì.Ì. ÑÀÂ×ÓÊ, À.Â. ÔÅÑÅÍÊÎ
ÊÂÀÍÒβ ÎÁ×ÈÑËÅÍÍß: ÎÃËßÄ ÒÀ ÀÍÀ˲Ç
Àíîòàö³ÿ. Çðîáëåíî îãëÿä òà àíàë³ç îñíîâíèõ ïîíÿòü ³ ïîëîæåíü êâàíòîâî¿
ìîäåë³ îá÷èñëåíü, åôåêòèâíèõ êâàíòîâèõ àëãîðèòì³â, îñòàíí³õ ðåçóëüòàò³â,
ìîæëèâîñòåé òà ïåðñïåêòèâ ó ïîáóäîâ³ ìàñøòàáîâàíîãî êâàíòîâîãî êîìï’þ-
òåðà. Ðîçãëÿíóòî ïåâíèé êëàñ àëãåáðà¿÷íèõ çàäà÷ ó êâàíòîâ³é ìîäåë³ îá÷èñ-
ëåíü, äëÿ ÿêèõ ³ñíóº åôåêòèâíèé êâàíòîâèé àëãîðèòì ðîçâ’ÿçêó. Ïðîâåäåíî
äåòàëüíèé àíàë³ç íàÿâíèõ ïðàêòè÷íèõ ðåàë³çàö³é êâàíòîâîãî êîìï’þòåðà.
Ïîêàçàíî, ùî íà ñüîãîäí³ íåìຠäîñòàòíüîãî ïðîãðåñó ó ïîáóäîâ³ ìàñøòà-
áîâàíîãî êâàíòîâîãî îá÷èñëþâàëüíîãî ïðèñòðîþ, ïðîòå á³ëüø³ñòü
äîñë³äíèê³â î÷³êóþòü íà ñòâîðåííÿ ïîâíîö³ííîãî êâàíòîâîãî êîìï’þòåðà
âïðîäîâæ íàñòóïíèõ 10–15 ðîê³â.
Êëþ÷îâ³ ñëîâà: êâàíòîâà ìîäåëü îá÷èñëåíü, êâàíòîâà êðèïòîãðàô³ÿ, êâàíòî-
âèé êîìï’þòåð, åôåêòèâí³ êâàíòîâ³ àëãîðèòìè, ïîñòêâàíòîâ³ êðèïòîãðàô³÷í³
ïðèì³òèâè.
ÂÑÒÓÏ
Íàì ïîùàñòèëî áóòè ñâ³äêàìè ³ ñó÷àñíèêàìè âåëèêèõ òåîðåòè÷íèõ â³äêðèòò³â
òà ïðàêòè÷íèõ âèíàõîä³â ³ äîñÿãíåíü â ³íôîðìàö³éí³é ñôåð³, ÿê³ çì³íèëè âñå
íàøå æèòòÿ, íàø ñâ³ò òà éîãî ðîçóì³ííÿ. Íàâ³òü âàæêî óÿâèòè, ÿê³ íîâ³ çì³íè
î÷³êóþòü íàñ óæå â íàéáëèæ÷îìó ìàéáóòíüîìó çàâäÿêè íîâèì äîñÿãíåííÿì
ó ãàëóç³ òåëåêîìóí³êàö³é, êëàñè÷íèõ êîìï’þòåðíèõ òà êâàíòîâèõ îá÷èñëåíü.
Î÷åâèäíî, ùî ð³âåíü ðîçâèòêó ñóñï³ëüñòâà â åêîíîì³÷í³é òà ³íøèõ ñôåðàõ
éîãî æèòòÿ áåçïîñåðåäíüî çàëåæèòü â³ä îáñÿãó ³íôîðìàö³¿, ÿêîþ ìîæóòü àêòèâíî
êîðèñòóâàòèñÿ ð³çí³ ïðîøàðêè ñóñï³ëüñòâà, â³ä óì³ííÿ ¿¿ åôåêòèâíî çáåð³ãàòè,
øâèäêî îáðîáëÿòè òà ïåðåäàâàòè. Íàãàäàºìî, ùî ð³âí³ ðîçâèòêó ñóñï³ëüñòâà
³ ðàí³øå áóëè ò³ñíî ïîâ’ÿçàí³ ç ³íôîðìàö³éíèìè ðåâîëþö³ÿìè. Òàê, ôîðìóâàííÿ
ðîäîïëåì³ííîãî óêëàäó ïîâ’ÿçàíî ç âèíèêíåííÿì ³ ðîçâèòêîì ìîâ, ìîâíîãî
ñï³ëêóâàííÿ; ñòâîðåííÿ äåðæàâ äàâíüîãî ñâ³òó â³äáóâàëîñÿ îäíî÷àñíî ç âèíàõîä-
æåííÿì ³ ðîçâèòêîì ñèñòåì ïèñåìíîñò³, ÿê³ äàâàëè çìîãó çä³éñíþâàòè äîâãîñòðî-
êîâå çáåð³ãàííÿ ³íôîðìàö³¿ íà ìàòåð³àëüíèõ íîñ³ÿõ, ¿¿ åôåêòèâíó ïåðåäà÷ó â ïðî-
ñòîð³ ³ ÷àñ³; ºâðîïåéñüê³ â³äðîäæåííÿ ³ ïðîìèñëîâà ðåâîëþö³ÿ ïîâ’ÿçàí³ ç êíèãî-
äðóêóâàííÿì, ÿêå â äåñÿòêè òèñÿ÷ ðàç³â çá³ëüøèëî îáñÿã ³íôîðìàö³¿, ùî
âèêîðèñòîâóâàëàñÿ. Çà ð³çíèìè îö³íþâàëüíèìè äàíèìè îð³ºíòîâíà ê³ëüê³ñòü
³íôîðìàö³¿, ÿêó ï³ñëÿ çàçíà÷åíèõ ³íôîðìàö³éíèõ ðåâîëþö³é âèêîðèñòîâóâàëî
ñóñï³ëüñòâî, ñòàíîâèëà â³äïîâ³äíî 109 , 1011, 1017 á³ò³â ³íôîðìàö³¿.
Íà ïî÷àòêó ñó÷àñíî¿ ³íôîðìàö³éíî¿ åðè ïåðøà åëåêòðîííà öèôðîâà îá÷èñ-
ëþâàëüíà ìàøèíà ÅͲÀÊ (1945 ð.) âàæèëà 27 òîíí, ñïîæèâàëà 174 êÂò, ìàþ÷è
îáñÿã ïàì’ÿò³ 20 ÷èñëî-ñë³â ³ òàêòîâó ÷àñòîòó 100 êÃö. Ö³êàâî, ùî ÷åðåç ÷îòèðè
ðîêè ó êíèç³ 1949 ð. «Ïîïóëÿðíà ìåõàí³êà» áóëî äàíî òàêèé ïðîãíîç: «êîìï’þòå-
ðè ìàéáóòíüîãî ìîæóòü âàæèòè íå á³ëüøå 1,5 òîíí». Íèí³ ì³í³àòþðèçàö³ÿ òà
øâèäêîä³ÿ öèôðîâèõ îá÷èñëþâàëüíèõ ïðèñòðî¿â äîñÿãëè ð³âíÿ, ÿêèé äຠçìîãó
ãîâîðèòè ïðî ³íòåëåêòóàëüí³ ñèñòåìè ç ìàéæå ôàíòàñòè÷íèìè ìîæëèâîñòÿìè,
³ ìåæà â öüîìó íàïðÿìêó ùå íå äîñÿãíóòà. Ïðèïóñòèìî, ùî ðîçì³ð ïðîöåñîðà äî-
ñÿãíå ðîçì³ðó àòîìà âîäíþ ä³àìåòðîì áëèçüêî 10 10� ì. Òîä³ ÷àñòîòà ïðîöåñîðà
áóäå íå á³ëüøîþ í³æ ÷èñëî ðàç³â ïðîõîäæåííÿ ñâ³òëîì øëÿõó ÷åðåç àòîì çà 1 ñå-
êóíäó, ùî äîð³âíþâàòèìå 3 1018� îïåðàö³é íà ñåêóíäó àáî ïðèáëèçíî 1026 îïå-
ðàö³é íà ð³ê. Öüîãî íå äîñòàòíüî, ùîá çëàìàòè, íàïðèêëàä, àñèìåòðè÷íó êðèïòî-
ñèñòåìó RSA ç äîâæèíîþ ìîäóëÿ 1024 á³òà. À êðèïòîñèñòåìó RSA ç äîâæèíîþ
ìîäóëÿ 2048 á³ò³â íàâ³òü òàêèé êîìï’þòåð íå çëàìຠïðîòÿãîì ì³ëüÿðäà ðîê³â íå-
14 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1
© Ì.Ì. Ñàâ÷óê, À.Â. Ôåñåíêî, 2019
ïåðåðâíî¿ ðîáîòè. Ïðè÷îìó òóò, ÿê ³ â çàäà÷àõ ç åêñïîíåíö³àëüíèì çðîñòàííÿì
ñêëàäíîñò³ â çàãàëüíîìó âèïàäêó, ðîçïàðàëåëþâàííÿ íå äîïîìîæå. Íà ñüîãîäí³
íàéøâèäø³ ñóïåðêîìï’þòåðè ìàþòü øâèäêîä³þ áëèçüêî 1017 ôëîïñ. ×è áóäå
îáìåæåíî ëþäñòâî â îá÷èñëåííÿõ ò³ëüêè çàäà÷àìè ïîë³íîì³àëüíî¿ ñêëàäíîñò³?
Àëüòåðíàòèâíîþ îá÷èñëþâàëüíîþ ìîäåëëþ º êâàíòîâà ìîäåëü îá÷èñëåíü,
ÿêó ìîæíà áóäå ïîâíîö³ííî çàñòîñîâóâàòè íà ïðàêòèö³ ï³ñëÿ ñòâîðåííÿ ìàñøòà-
áîâàíîãî êâàíòîâîãî êîìï’þòåðà. Ó ö³é ñòàòò³ ïðîâåäåíî àíàë³ç îñíîâíèõ òåîðå-
òè÷íèõ ïîíÿòü, ³äåé ùîäî îá´ðóíòóâàííÿ êâàíòîâèõ îá÷èñëåíü òà ïåðñïåêòèâ
ïîáóäîâè ìàñøòàáîâàíîãî êâàíòîâîãî êîìï’þòåðà.
1. ÊÂÀÍÒÎÂÀ ÊÐÈÏÒÎÃÐÀÔ²ß
Êâàíòîâèìè îá÷èñëåííÿìè ââàæàþòü íå ò³ëüêè îá÷èñëåííÿ íà êâàíòîâîìó
êîìï’þòåð³. Äî ö³º¿ ñôåðè â³äíîñÿòü òàêîæ êâàíòîâó êðèïòîãðàô³þ, êâàíòîâó
òåëåïîðòàö³þ òà ³íø³ íàïðÿìêè. Ó òðàäèö³éí³é êðèïòîãðàô³¿ íîñ³ºì ³íôîðìàö³¿
ï³ä ÷àñ ïåðåäà÷³ º ³ìïóëüñè ñòðóìó, ñâ³òëà, ïó÷êè ðàä³îõâèëü, çðåøòîþ, ïàï³ð
òà ³íø³ ìàòåð³àëüí³ íîñ³¿. Äëÿ ïðåäñòàâëåííÿ ³ êîäóâàííÿ îäíîãî á³òà ³íôîð-
ìàö³¿ êîæíîãî ðàçó âèêîðèñòîâóºòüñÿ âåëè÷åçíà ê³ëüê³ñòü åëåêòðîí³â, ôîòîí³â,
ðàä³îõâèëü, ÷àñòèíîê. Ó êâàíòîâ³é êðèïòîãðàô³¿ äëÿ êîäóâàííÿ îäíîãî á³òà çà-
çâè÷àé âèêîðèñòîâóºòüñÿ êâàíòîâèé ñòàí îäí³º¿ åëåìåíòàðíî¿ ÷àñòèíêè (àòîìà,
³îíà, åëåêòðîíà, ôîòîíà) àáî ¿õ ïàðè.
Íà â³äì³íó â³ä òðàäèö³éíî¿ êðèïòîãðàô³¿, ó ÿê³é âèêîðèñòîâóþòüñÿ ìàòåìà-
òè÷í³ ìåòîäè ïåðåòâîðåííÿ òåêñò³â ³ ïîâ³äîìëåíü äëÿ çàáåçïå÷åííÿ ¿õíüî¿ çàõè-
ùåíîñò³ â³ä çëîâìèñíèêà òà çáåðåæåííÿ ñåêðåòíîñò³ ³íôîðìàö³¿, â îñíîâó êâàíòî-
âî¿ êðèïòîãðàô³¿ äëÿ çàõèñòó ³íôîðìàö³¿ ïîêëàäåíî ô³çè÷í³ ïðîöåñè òà çàêîíè
êâàíòîâî¿ ìåõàí³êè, à êîäóâàííÿ òà ïåðåíåñåííÿ ³íôîðìàö³¿ çä³éñíþºòüñÿ çà äî-
ïîìîãîþ îá’ºêò³â êâàíòîâî¿ ìåõàí³êè, íàïðèêëàä, çà äîïîìîãîþ åëåêòðîí³â
ó åëåêòðè÷íîìó ñòðóì³ àáî ôîòîí³â ó ë³í³ÿõ âîëîêîííî-îïòè÷íîãî çâ’ÿçêó. Ïðèé-
ìàííÿ ïîâ³äîìëåíü, àáî ï³äñëóõîâóâàííÿ (ïåðåõîïëåííÿ ïîâ³äîìëåííÿ) ìîæíà
ðîçãëÿäàòè ÿê âèì³ðþâàííÿ ïåâíèõ ïàðàìåòð³â êâàíòîâèõ îá’ºêò³â–ïåðåíîñíèê³â
³íôîðìàö³¿.
Âïåðøå ³äåÿ çàõèñòó ³íôîðìàö³¿ ç âèêîðèñòàííÿì êâàíòîâèõ îá’ºêò³â áóëà
çàïðîïîíîâàíà Ñ. ³çíåðîì ó 1970 ð. Ïåðøèé òà íàéá³ëüø â³äîìèé ïðîòîêîë
êâàíòîâî¿ êðèïòîãðàô³¿ BB84, çàïðîïîíîâàíèé ×. Áåííåòîì ³ Æ. Áðàññàðîì
â 1984 ð. íà îñíîâ³ ³äåé Ñ. ³çíåðà, äຠçìîãó ðîçâ’ÿçàòè ïðîáëåìó ñèìåòðè÷íî¿
êðèïòîãðàô³¿ — ïåðåäà÷ó òàºìíîãî êëþ÷à ç âèêîðèñòàííÿì ëèøå â³äêðèòèõ êà-
íàë³â çâ’ÿçêó [1]. Ó 70-õ ðîêàõ XX ñòîë³òòÿ ó çâ’ÿçêó ç áóðõëèâèì ðîçâèòêîì êîì-
ï’þòåðíèõ ìåðåæ, òåëåêîìóí³êàö³éíèõ êàíàë³â, åêñïîíåíö³àëüíèì çðîñòàííÿì
ê³ëüêîñò³ ³íôîðìàö³¿ òà ïîòðåáîþ â ¿¿ çàõèñò³ ìàéæå â óñ³õ ãàëóçÿõ ïåðåäà÷à
êëþ÷³â ñïåö³àëüíèìè çàêðèòèìè êàíàëàìè ñòàëà ïðîáëåìîþ, ÿêà çäàâàëàñÿ íåðîç-
â’ÿçíîþ. Ó 1976 ð. Ó. ijôô³ òà Ì. Õåëëìàí ÷³òêî ñôîðìóëþâàëè ïîíÿòòÿ âàæêîî-
áîðîòíî¿ ôóíêö³¿ òà âàæêîîáîðîòíî¿ ôóíêö³¿ ç ëàç³âêîþ ³ çàïðîïîíóâàëè íîâó
êîíöåïö³þ â êðèïòîãðàô³¿ — àñèìåòðè÷íó êðèïòîãðàô³þ àáî êðèïòîãðàô³þ
ç â³äêðèòèìè êëþ÷àìè. Ïåðøèì ïðîòîêîëîì àñèìåòðè÷íî¿ êðèïòîãðàô³¿ áóâ ñàìå
ïðîòîêîë ðîçïîâñþäæåííÿ êëþ÷³â â³äêðèòèìè êàíàëàìè, ÿê³ ó ñèìåòðè÷í³é êðèï-
òîãðàô³¿ âèêîðèñòîâóâàëèñÿ äëÿ êðèïòîãðàô³÷íèõ ïåðåòâîðåíü çàõèñòó
³íôîðìàö³¿. Êâàíòîâèé ïðîòîêîë ðîçïîâñþäæåííÿ êëþ÷³â ïîáóäîâàíî íà îñíîâ³
³íøèõ ïðèíöèï³â.
Çàäà÷à êâàíòîâîãî ïðîòîêîëó ðîçïîâñþäæåííÿ êëþ÷³â ÂÂ84 — áåç âèêîðèñ-
òàííÿ çàêðèòèõ êàíàë³â ïåðåäàòè â³ä â³äïðàâíèêà À äî îäåðæóâà÷à  âèïàäêîâó
ïîñë³äîâí³ñòü íóë³â òà îäèíèöü, ç ÿêî¿ ïîò³ì êîðèñòóâà÷³ À ³  îáèðàþòü òàºìíèé
êëþ÷. Çãåíåðîâàíà â³äïðàâíèêîì À äâ³éêîâà âèïàäêîâà ïîñë³äîâí³ñòü, êîæíèé
ñèìâîë ÿêî¿ 0 ³ 1 êîäóºòüñÿ íàïðÿìêîì ïîëÿðèçàö³¿ îäèíè÷íîãî ôîòîíà (íàïðÿì-
êîì êîëèâàíü åëåêòðè÷íîãî ïîëÿ ôîòîíà), ïåðåäàºòüñÿ ïîñë³äîâí³ñòþ ôîòîí³â âî-
ëîêîííî-îïòè÷íîþ ë³í³ºþ. Íàïðÿìêîì ïîëÿðèçàö³¿ ôîòîí³â ìîæíà êåðóâàòè òà
âèì³ðþâàòè éîãî, íàïðèêëàä, çà äîïîìîãîþ îïòè÷íî àêòèâíèõ êðèñòàë³â.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1 15
Ïîñë³äîâí³ñòü á³ò³â ïåðåäàºòüñÿ ïîñë³äîâí³ñòþ ôîòîí³â ó áàçèñ³, îáðàíîìó
â³äïðàâíèêîì À âèïàäêîâèì ÷èíîì äëÿ êîæíîãî á³òà — ïðÿìîêóòíîìó àáî ä³àãî-
íàëüíîìó. Ó ïðÿìîêóòíîìó áàçèñ³ 0 àáî 1 êîäóþòüñÿ ãîðèçîíòàëüíèì òà âåðòè-
êàëüíèì íàïðÿìêîì ïîëÿðèçàö³¿ ôîòîíà, à â ä³àãîíàëüíîìó — ç íàõèëîì ï³ä êó-
òîì 45 òà 135 ãðàäóñ³â. Ôàêòè÷íî äî âèì³ðþâàííÿ ³íôîðìàö³ÿ çíàõîäèòüñÿ ó
êâàíòîâèõ á³òàõ — êóá³òàõ ³ ëèøå ï³ñëÿ âèì³ðþâàííÿ ïåðåòâîðþºòüñÿ ó çâè÷àéí³
êëàñè÷í³ á³òè. Îäåðæóâà÷  îáèðຠäëÿ âèì³ðþâàííÿ âèïàäêîâèì ÷èíîì ñâîþ
ïîñë³äîâí³ñòü áàçèñ³â. ßêùî áàçèñè ó êîðèñòóâà÷³â À ³  äëÿ îêðåìîãî ôîòîíà
çá³ãàþòüñÿ, òî ï³ä ÷àñ âèì³ðþâàííÿ  îòðèìຠòîé ñàìèé ñèìâîë ïîñë³äîâíîñò³
(0 àáî 1), ÿêèé áóâ â³äïðàâëåíèé êîðèñòóâà÷åì À. ßêùî áàçèñè À ³  íå çá³ãàþòü-
ñÿ, òî â³äïîâ³äí³ ñèìâîëè ó À ³  áóäóòü îäíàêîâèìè ç ³ìîâ³ðí³ñòþ 0.5 çà çàêîíà-
ìè êâàíòîâî¿ ô³çèêè. ϳñëÿ âèì³ðþâàííÿ À ³ Â, âèêîðèñòîâóþ÷è áóäü-ÿêèé
â³äêðèòèé êàíàë, ç’ÿñîâóþòü, ÿê³ áàçèñè ó íèõ çá³ãëèñÿ. Çà â³äñóòíîñò³ ïðîñëóõî-
âóâàííÿ çëîâìèñíèêîì ó ñåðåäíüîìó êîðèñòóâà÷³ À ³ Â ìàòèìóòü 50% îäíàêîâèõ
ñèìâîë³â âèõ³äíî¿ ïîñë³äîâíîñò³, ç ÿêî¿ îáèðàþòüñÿ òàºìí³ êëþ÷³ äëÿ
ñèìåòðè÷íèõ ñèñòåì øèôðóâàííÿ êîðèñòóâà÷³â À ³ Â.
Ñò³éê³ñòü êâàíòîâîãî ïðîòîêîëó ïåðåäà÷³ òàºìíîãî êëþ÷à çóìîâëåíà òèì,
ùî ôàêò ï³äêëþ÷åííÿ äî âîëîêîííî-îïòè÷íî¿ ë³í³¿ ³ ïðîñëóõîâóâàííÿ íå-
ñàíêö³îíîâàíîþ îñîáîþ ìîæå áóòè ãàðàíòîâàíî âèÿâëåíèé êîðèñòóâà÷àìè À ³ Â.
Öå, ñâîºþ ÷åðãîþ, çàáåçïå÷óºòüñÿ çàêîíàìè êâàíòîâî¿ ìåõàí³êè òà îáì³íîì ì³æ
À ³  ï³ñëÿ êâàíòîâî¿ ïåðåäà÷³ ïåâíîþ óòî÷íþâàëüíîþ ³íôîðìàö³ºþ ç âèêîðèñ-
òàííÿì áóäü-ÿêîãî â³äêðèòîãî êàíàëó. Çëîâìèñíèê íå çíຠîáðàíèõ êîðèñòóâà÷åì
À áàçèñ³â, òîìó ï³ä ÷àñ ïðîñëóõîâóâàííÿ áóäóòü ñïîòâîðåí³ òàêîæ ò³ ñèìâîëè
ó îäåðæóâà÷à Â, ÿê³ çà óìîâè îáðàííÿ êîðèñòóâà÷àìè À ³  îäíàêîâèõ áàçèñ³â
ìàþòü çá³ãàòèñÿ, ùî áóäå âèÿâëåíî êîðèñòóâà÷àìè. Ó öüîìó ðàç³ îòðèìàíà êî-
ðèñòóâà÷àìè À ³  ïîñë³äîâí³ñòü íå âèêîðèñòîâóºòüñÿ. ßêùî íå áóëî ñïðîáè ïðî-
ñëóõîâóâàííÿ, òî ÷àñòèíîþ ïîñë³äîâíîñò³ ìîæíà ñêîðèñòàòèñÿ ÿê òàºìíèì
êëþ÷åì (â³äîìèì ëèøå â³äïðàâíèêó ³ îäåðæóâà÷ó) ³ çàñòîñîâóâàòè ¿¿ íàäàë³
ó ñèìåòðè÷íèõ êðèïòîñèñòåìàõ.
Ïåðøà ðåàë³çàö³ÿ êâàíòîâîãî ïðîòîêîëó íà ô³çè÷íîìó ïðèñòðî¿ â³äáóëàñÿ
â 1989 ð. ç ïåðåäà÷åþ íà â³äñòàíü, ùî ñòàíîâèëà ìåíøå í³æ îäèí ìåòð. ϳçí³øå
äàëüí³ñòü ïåðåäà÷³ íåîäíîðàçîâî çá³ëüøóâàëàñü. Íèí³ ïåðåäà÷à ââàæàºòüñÿ äîñ-
òàòíüî ñòàá³ëüíîþ íà â³äñòàíü, ÿê ïðàâèëî, äî 200 êì. Äàëüí³ñòü ïåðåäà÷³ ïåðø
çà âñå îáìåæóºòüñÿ çàòóõàííÿì ñâ³òëîâèõ ñèãíàë³â ó âîëîêîííî-îïòè÷íèõ êàáå-
ëÿõ ³ âòðàòîþ ôîòîí³â, à òàêîæ çîâí³øí³ìè çàâàäàìè.
Ç ïîÿâîþ êâàíòîâî¿ êðèïòîãðàô³¿ ¿¿ åíòóç³àñòè ïðîãíîçóâàëè, ùî íåâäîâç³
êâàíòîâà êðèïòîãðàô³ÿ ñòâîðèòü êîíêóðåíö³þ äëÿ «çâè÷àéíî¿» êðèïòîãðàô³¿
³ íàâ³òü áóäå á³ëüø íàä³éíîþ òà åôåêòèâíîþ. Àëå ïîêè ùî öå íå ñòàëîñÿ ïåðåä-
óñ³ì ÷åðåç íèçêó òåõí³÷íèõ òðóäíîù³â. Òàê, íàïðèêëàä, ÿêùî â êëàñè÷íèõ ³íôîð-
ìàö³éíèõ ïåðåäà÷àõ âîëîêîííî-îïòè÷íèìè êàíàëàìè ÷åðåç êîæí³ äåê³ëüêà äå-
ñÿòê³â ê³ëîìåòð³â îáîâ’ÿçêîâî ñòàâëÿòü åëåêòðîíí³ àáî îïòè÷í³ ï³äñèëþâà÷³, òî
çðîáèòè öå â êâàíòîâîìó ïðîòîêîë³ ÂÂ84 íåìîæëèâî, áî ñòàí ôîòîíà, íå çíàþ÷è
áàçèñ³â â³äïðàâíèêà À, â³äòâîðèòè ï³ñëÿ âèì³ðþâàííÿ íåìîæëèâî çà êâàíòîâèìè
çàêîíàìè. Öå â³äðàçó íàêëàäຠæîðñòê³ îáìåæåííÿ íà äàëüí³ñòü ïåðåäà÷³. Íà ñüî-
ãîäí³ íàéá³ëüøà â³äñòàíü, äîñÿãíóòà ó ðàç³ ïåðåäà÷³ çà êâàíòîâèì ïðîòîêîëîì âî-
ëîêîííî-îïòè÷íèìè êàíàëàìè, ñòàíîâèòü 404 êì.
²íøèé òèï êâàíòîâîãî êðèïòîãðàô³÷íîãî ïðîòîêîëó áàçóºòüñÿ íà çàïëóòàíèõ
êâàíòîâèõ ñòàíàõ äâîõ ÷àñòèíîê, íàïðèêëàä, ôîòîí³â. Çàðàç ó ð³çíèõ êðà¿íàõ ïðî-
âîäÿòü ³íòåíñèâí³ äîñë³äæåííÿ êâàíòîâîãî çâ’ÿçêó, êâàíòîâèõ êðèïòîãðàô³÷íèõ
ïðîòîêîë³â ç âèêîðèñòàííÿì øòó÷íèõ ñóïóòíèê³â. Äàëüí³ñòü êâàíòîâèõ ïåðåäà÷ ç
âèêîðèñòàííÿì ñóïóòíèê³â ñÿãຠñîòåíü ê³ëîìåòð³â ³ íàâ³òü ïåðåâèùóº òèñÿ÷³
ê³ëîìåòð³â. Öå â³äêðèâຠíîâ³ ïåðñïåêòèâè äëÿ ðîçâèòêó êâàíòîâîãî çâ’ÿçêó òà
êâàíòîâî¿ êðèïòîãðàô³¿.
16 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1
2. ÎÑÍÎÂͲ ÏÎÍßÒÒß ÊÂÀÍÒÎÂί ÌÎÄÅ˲ ÎÁ×ÈÑËÅÍÜ
2.1. Õðîíîëîã³ÿ ³äåé òà ïåðøèõ ïîëîæåíü. Ó çá³ðö³ [2] ïðåäñòàâëåíî äåâ’ÿòü
êëàñè÷íèõ ðîá³ò ó ãàëóç³ êâàíòîâèõ êîìï’þòåð³â òà êâàíòîâèõ îá÷èñëåíü,
ó òîìó ÷èñë³ ðîáîòè Ä. Äîé÷à, Ä. Äæîçè òà Ï. Øîðà, ïðèñâÿ÷åí³ äîñë³äæåííþ
åôåêòèâíèõ êâàíòîâèõ àëãîðèòì³â. Ñòèñëî â³äçíà÷èìî îñíîâí³ åòàïè òåî𳿠ïî-
áóäîâè êâàíòîâîãî êîìï’þòåðà òà êâàíòîâèõ àëãîðèòì³â:
• 1980 ð. — Þ.². Ìàí³í ó âñòóï³ äî êíèãè «Îá÷èñëþâàíå òà íå îá÷èñëþâàíå»
(«Âû÷èñëèìîå è íåâû÷èñëèìîå») âèñóíóâ ³äåþ êâàíòîâèõ àâòîìàò³â;
• 1982 ð. — Ï. Áåí³îô ³ Ð. Ôåéíìàí ïðîàíàë³çóâàëè ô³çè÷í³ îáìåæåííÿ òà
ìîæëèâ³ñòü ïîáóäîâè êâàíòîâîãî êîìï’þòåðà (êâàíòîâèé ³ì³òàòîð);
• 1985 ð. — Ä. Äîé÷ íàäàâ ³äå¿ Ð. Ôåéíìàíà êîíêðåòíó ôîðìó — åôåê-
òèâí³ñòü ó ðàç³ êâàíòîâîãî ïàðàëåë³çìó;
• 1992 ð. — Ä. Äîé÷ òà Ä. Äæîçà çàïðîïîíóâàëè àëãîðèòì ðîçâ’ÿçàííÿ çàäà÷³
ïðî ðîçð³çíåííÿ (ðîçï³çíàâàííÿ) ñòàëî¿ òà çáàëàíñîâàíî¿ áóëåâèõ ôóíêö³é â³ä n
çì³ííèõ çà n îïåðàö³é íà êâàíòîâîìó êîìï’þòåð³;
• 1994 ð. — Ï. Øîð ðîçðîáèâ àëãîðèòìè ôàêòîðèçàö³¿ ³ äèñêðåòíîãî ëîãà-
ðèôìóâàííÿ, ÿê³ äàþòü çìîãó ðîçâ’ÿçàòè â³äïîâ³äí³ çàäà÷³ çà ïîë³íîì³àëüíèé ÷àñ
íà êâàíòîâîìó êîìï’þòåð³;
• 1996 ð. — Ë. Ãðîâåð ðîçðîáèâ êâàíòîâèé àëãîðèòì ïîøóêó â íåóïîðÿäêîâàí³é
ìíîæèí³, çîêðåìà éîãî àëãîðèòì çàáåçïå÷óº ðîçâ’ÿçàííÿ çàäà÷³ ïåðåáîðó, íàïðèê-
ëàä, çíàõîäæåííÿ ðîçâ’ÿçêó ð³âíÿííÿ f x( ) �1 äëÿ áóëåâî¿ ôóíêö³¿ f â³ä n çì³ííèõ çà
O n( )/2 2 çâåðíåíü äî îá÷èñëåííÿ ôóíêö³¿ f ç âèêîðèñòàííÿì O n( ) êóá³ò³â.
Ç äåòàëüíîþ ³íôîðìàö³ºþ ïðî íàâåäåí³ åòàïè ðîçâèòêó, îñíîâè òåî𳿠êâàí-
òîâèõ îá÷èñëåíü, ñó÷àñí³ äîñë³äæåííÿ, ïåðñïåêòèâè ïîáóäîâè êâàíòîâîãî êîì-
ï’þòåðà òà ìîæëèâ³ íàñë³äêè äëÿ ñóñï³ëüñòâà ³ ðîçóì³ííÿ ô³çè÷íèõ òà ³íôîð-
ìàö³éíèõ ïðîöåñ³â ìîæíà îçíàéîìèòèñü ó ìîíîãðàô³ÿõ [2–4]. Ñòèñëèé îïèñ ðå-
çóëüòàò³â äîñë³äæåíü êè¿âñüêî¿ øêîëè òåîðåòè÷íî¿ êðèïòîãðàô³¿ ó ö³é ãàëóç³
ïðåäñòàâëåíî â ðîáîò³ [5].
2.2. Êâàíòîâ³ ñòàíè òà çàãàëüíà êîíöåïö³ÿ êâàíòîâèõ îá÷èñëåíü.
Îäíîêóá³òíà êâàíòîâà ñèñòåìà. Ó êâàíòîâîìó êîìï’þòåð³ îäèíèöåþ
³íôîðìàö³¿ º êóá³ò (êâàíòîâèé á³ò), ô³çè÷íà ðåàë³çàö³ÿ ÿêîãî îïèñóºòüñÿ õâèëüî-
âîþ ôóíêö³ºþ éìîâ³ðíîñòåé ó äâîâèì³ðíîìó ã³ëüáåðòîâîìó ïðîñòîð³.
Îäèí êëàñè÷íèé á³ò ìîæå ïåðåáóâàòè ò³ëüêè â îäíîìó ç äâîõ ñòàí³â, ÿê³ ïî-
çíà÷àþòüñÿ (êîäóþòüñÿ) 0 òà 1. Ñòàí êâàíòîâîãî á³òà (êóá³òà) îïèñóþòü ç âèêî-
ðèñòàííÿì áðà ³ êåò ïîçíà÷åíü ijðàêà çà äîïîìîãîþ âèðàçó | | |�� � � � �a b0 1 , äå a
³ b — êîìïëåêñí³ ÷èñëà, à | | | |a b2 2 1� � . Òàê áè ìîâèòè, êóá³ò îäíî÷àñíî ïåðåáó-
âຠâ óñ³õ òî÷êàõ ïðîñòîðó, àëå ç ð³çíîþ éìîâ³ðí³ñòþ. Ó ðåçóëüòàò³ âèì³ðþâàííÿ
êóá³òà, ÿêå ôàêòè÷íî º ïðîåêö³ºþ íà îðòîãîíàëüí³ ï³äïðîñòîðè, îòðèìàºìî çàêî-
äîâàíå çíà÷åííÿ êëàñè÷íîãî á³òà: 0 ç ³ìîâ³ðí³ñòþ | |a 2 àáî 1 ç ³ìîâ³ðí³ñòþ | |b 2 .
Òàêèì ÷èíîì, ï³ñëÿ âèì³ðþâàííÿ êóá³ò â³äðàçó ïåðåõîäèòü â îäèí ç áàçèñíèõ
ñòàí³â, ùî â³äïîâ³äຠêëàñè÷íîìó ðåçóëüòàòó. Íàïðèêëàä, ï³ñëÿ âèì³ðþâàííÿ
êóá³òà, ÿêèé îïèñóºòüñÿ ñòàíîì | | |�� � � � �
3
5
0
4
5
1 , îòðèìóºìî â³äïîâ³äíå
çíà÷åííÿ 0 ç ³ìîâ³ðí³ñòþ 0,36 òà çíà÷åííÿ 1 ç ³ìîâ³ðí³ñòþ 0,64.
Êâàíòîâà ñèñòåìà ç äâîìà òà á³ëüøèì ÷èñëîì êóá³ò³â. Ñòàí ñèñòåìè ç äâîõ
êóá³ò³â ìàòåìàòè÷íî ìîæå áóòè çàïèñàíèé ÿê îäèíè÷íèé âåêòîð ó 4-âèì³ðíîìó
ã³ëüáåðòîâîìó ïðîñòîð³ | | | | |�� � � � � � � � �a b c d00 01 10 11 , äå a, b, c, d —
êîìïëåêñí³ ÷èñëà ³ | | | | | | | |a b ñ d2 2 2 2 1� � � � . Áàçèñíèìè êâàíòîâèìè ñòàíàìè º
| , | , | , |00 01 10 11� � � �, ÿê³ â³äïîâ³äàþòü ÷îòèðüîì êëàñè÷íèì çíà÷åííÿì 00, 01, 10 òà
11, êîæíå ç ÿêèõ ï³ñëÿ ïîâíîãî âèì³ðþâàííÿ ìຠéìîâ³ðí³ñòü | | , | | , | | , | |a b ñ d2 2 2 2
â³äïîâ³äíî. Àíàëîã³÷íî ñèñòåìà, ÿêà ì³ñòèòü N êóá³ò³â, îïèñóºòüñÿ â 2 N -âèì³ðíîìó
ã³ëüáåðòîâîìó ïðîñòîð³ òà ìàòèìå 2 N áàçèñíèõ ñòàí³â, ÿê³ â³äïîâ³äàþòü 2 N êëàñè÷-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1 17
íèì çíà÷åííÿì. Òàêèì ÷èíîì, ðåçóëüòàòîì ïîâíîãî âèì³ðþâàííÿ N -êóá³òíî¿
êâàíòîâî¿ ñèñòåìè áóäå îäíå ç 2 N ð³çíèõ êëàñè÷íèõ çíà÷åíü, çàãàëüíà ê³ëüê³ñòü
ÿêèõ åêñïîíåíö³àëüíî çðîñòຠâ³äíîñíî ÷èñëà êóá³ò³â, ³ êîæíå çíà÷åííÿ ìîæå
áóòè îòðèìàíî â ðåçóëüòàò³ âèì³ðþâàííÿ ç äåÿêîþ éìîâ³ðí³ñòþ. Íåõàé ³ñíóº
ïîñë³äîâí³ñòü ïåðåòâîðåíü êâàíòîâî¿ ñèñòåìè, ÿê³ ìîæíà ðåàë³çóâàòè ô³çè÷íî,
òàêà, ùî ñóòòºâî çá³ëüøèòü ³ìîâ³ðí³ñòü ñòàíó, ÿêèé â³äïîâ³äຠøóêàíîìó ðîçâ’ÿç-
êó ö³º¿ çàäà÷³. Òîä³ òàêà êâàíòîâà ñèñòåìà ìîæå ï³ñëÿ áàãàòîêðàòíî¿ ðåàë³çàö³¿ òà
âèì³ðþâàííÿ çíàéòè ç âèñîêîþ éìîâ³ðí³ñòþ â³äïîâ³äü íà ìîæëèâî íåïîñèëüíó
äëÿ êëàñè÷íîãî êîìï’þòåðà çàäà÷ó.
Çàãàëüíà êîíöåïö³ÿ êâàíòîâèõ îá÷èñëåíü. Ñïðîùåíó ñõåìó îá÷èñëåííÿ ìîæ-
íà îïèñàòè òàê. Ñèñòåìà ç äîñòàòí³ì ÷èñëîì ñï³ëüíî ïðàöþþ÷èõ êóá³ò³â ïåðåâî-
äèòüñÿ â ïåâíèé ïî÷àòêîâèé ñòàí, ùî â³äïîâ³äຠóìîâàì çàäà÷³. Äàë³ ñòàí ñèñòå-
ìè àáî ¿¿ ï³äñèñòåì çì³íþºòüñÿ øëÿõîì çàñòîñóâàííÿ ïîñë³äîâíîñò³ ïåðåòâîðåíü,
ÿêèì ó ìàòåìàòè÷í³é ìîäåë³ â³äïîâ³äàþòü óí³òàðí³ ïåðåòâîðåííÿ â ã³ëüáåðòîâîìó
ïðîñòîð³ (óí³òàðí³ ìàòðèö³). Ó ïåâíîìó ðîçóì³íí³ êâàíòîâà ñèñòåìà ïàðàëåëüíî
âèêîíóº îá÷èñëåííÿ ç óñ³ìà ìîæëèâèìè êëàñè÷íèìè ñòàíàìè, ÷èñëî ÿêèõ çðîñòàº
åêñïîíåíö³àëüíî ç³ çá³ëüøåííÿì ÷èñëà êóá³ò³â, à â³äïîâ³ääþ º ºäèíå êëàñè÷íå
çíà÷åííÿ. ϳñëÿ çàñòîñóâàííÿ âñ³õ óí³òàðíèõ ïåðåòâîðåíü, ÿê ïðàâèëî, âèêî-
íóºòüñÿ âèì³ðþâàííÿ ñòàíó ñèñòåìè ³ îòðèìàíå êëàñè÷íå çíà÷åííÿ º ðåçóëüòàòîì
îá÷èñëåíü. Çàçâè÷àé, êâàíòîâà ñèñòåìà äຠïðàâèëüíèé ðåçóëüòàò ò³ëüêè ç ïåâ-
íîþ éìîâ³ðí³ñòþ. Äëÿ çá³ëüøåííÿ äîâ³ð÷î¿ éìîâ³ðíîñò³ îá÷èñëåííÿ ³ â³äïîâ³äí³
âèì³ðþâàííÿ ïîâòîðþþòü ïîòð³áíó ê³ëüê³ñòü ðàç³â. Öþ éìîâ³ðí³ñòü, ÿêùî ïîìèë-
êè ï³ä ÷àñ âèì³ðþâàííÿ íå çðîñòàþòü äóæå øâèäêî (íàïðèêëàä, åêñïîíåíö³àëüíî
ç³ çá³ëüøåííÿì ÷èñëà êóá³ò³â), ìîæíà çðîáèòè ÿê çàâãîäíî áëèçüêîþ äî îäèíèö³.
Ìîæíà ñêàçàòè, ùî öÿ êâàíòîâà ñèñòåìà º àíàëîãîâèì êâàíòîâèì êîìï’þòåðîì.
Òàêà êîíöåïö³ÿ êâàíòîâîãî êîìï’þòåðà ³ êâàíòîâèõ âåíòèë³â — ïðîñòèõ
óí³òàðíèõ ïåðåòâîðåíü, ÿê³ â³äïîâ³äàþòü ëîã³÷íèì îïåðàö³ÿì ó êëàñè÷íîìó êîì-
ï’þòåð³, áóëà çàïðîïîíîâàíà Ä. Äîé÷åì ó 1989 ð. Ó 1995 ð. Ä. Äîé÷ âèíàéøîâ
óí³âåðñàëüíèé ëîã³÷íèé áëîê, çà äîïîìîãîþ ÿêîãî ìîæíà âèêîíàòè áóäü-ÿê³
êâàíòîâ³ îá÷èñëåííÿ. Âèÿâëÿºòüñÿ, ùî äëÿ ïîáóäîâè àëãîðèòìó áóäü-ÿêîãî îá-
÷èñëåííÿ äîñòàòíüî äâîõ áàçîâèõ îïåðàö³é — êâàíòîâèõ âåíòèë³â.
Òåîðåòè÷íî êâàíòîâèé êîìï’þòåð äຠçìîãó âèêîíàòè ³íòó¿òèâíî çðîçóì³ë³
àëãîðèòìè òàê ñàìî ÿê ³ êëàñè÷íèé êîìï’þòåð. Ñêëàäí³ñòü áóäü-ÿêî¿ îá÷èñëþ-
âàëüíî¿ çàäà÷³, ùî âèêîíóºòüñÿ ç âèêîðèñòàííÿì êâàíòîâîãî êîìï’þòåðà, çã³äíî ç
ðåçóëüòàòîì Ãðîâåðà, ìîæíà çìåíøèòè ïðèíàéìí³ ó êâàäðàòíèé êîð³íü ïîð³âíÿ-
íî ç³ ñêëàäí³ñòþ ö³º¿ çàäà÷³, ùî âèêîíóºòüñÿ çà äîïîìîãîþ êëàñè÷íîãî êîìï’þòå-
ðà, à äåÿê³ åêñïîíåíö³àëüíî ñêëàäí³ çàäà÷³ ìîæóòü áóòè ðîçâ’ÿçàí³ çà
ïîë³íîì³àëüíèé ÷àñ. Íà æàëü, íà ñüîãîäí³ â³äîìî ìàëî çàäà÷, ðîçâ’ÿçàííÿ ÿêèõ çà
äîïîìîãîþ êâàíòîâîãî êîìï’þòåðà ìîæå äàòè ñóòòºâèé âèãðàø. Äî òàêèõ çàäà÷
íàëåæàòü çàäà÷³ ôàêòîðèçàö³¿ òà äèñêðåòíîãî ëîãàðèôìóâàííÿ, íà ñêëàäíîñò³
ÿêèõ áàçóºòüñÿ ñò³éê³ñòü áëèçüêî 95% ðåàë³çàö³é àëãîðèòì³â ³ ïðîòîêîë³â
àñèìåòðè÷íî¿ êðèïòîãðàô³¿.
Îñíîâí³ ïðîáëåìè ó ïîáóäîâ³ êâàíòîâîãî êîìï’þòåðà º òàêèìè:
— ïðèíöèïîâà ìîæëèâ³ñòü ïîáóäîâè ìàñøòàáîâàíîãî êâàíòîâîãî
êîìï’þòåðà;
— íåñòàá³ëüí³ñòü, äåêîãåðåíö³ÿ ÷åðåç âïëèâ çîâí³øíüîãî ñåðåäîâèùà;
— ô³çè÷íà ðåàë³çàö³ÿ ìàñøòàáîâàíîãî êâàíòîâîãî êîìï’þòåðà ç äîñòàòíüîþ
äëÿ ïðàêòè÷íèõ çàäà÷ ê³ëüê³ñòþ ñï³ëüíî ïðàöþþ÷èõ êóá³ò³â;
— íåâ³äîì³ñòü ñòåïåíÿ çàëåæíîñò³ ïîìèëîê, îñê³ëüêè íàäòî øâèäêå íàêîïè-
÷åííÿ ïîìèëîê ç³ çðîñòàííÿì ÷èñëà êóá³ò³â íå äàñòü çìîãè îòðèìàòè ïîòð³áíèé
ðåçóëüòàò ó ðàç³ âèêîíàííÿ îá÷èñëåíü ç ïðèéíÿòíîþ ê³ëüê³ñòþ ïîâòîð³â;
— ïîáóäîâà íîâèõ ìàòåìàòè÷íèõ àëãîðèòì³â, ÿê³ äàäóòü çìîãó ñóòòºâî ïðè-
ñêîðèòè îá÷èñëåííÿ òà ïîøóê ð³øåíü äëÿ øèðîêîãî êëàñó çàäà÷.
18 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1
2.3. Îñíîâí³ ìàòåìàòè÷í³ ïîíÿòòÿ êâàíòîâî¿ ìîäåë³ îá÷èñëåíü. Îñíîâîþ
êâàíòîâîãî êîìï’þòåðà º êâàíòîâî-ìåõàí³÷íà ñèñòåìà, îáîâ’ÿçêîâî ³çîëüîâàíà
â³ä íàâêîëèøíüîãî ñåðåäîâèùà òàêèì ÷èíîì, ùîá ¿¿ ïîâåä³íêîþ ìîæíà áóëî êå-
ðóâàòè ççîâí³, àëå ùîá æîäíà ïîä³ÿ, íå ïîâ’ÿçàíà ç ïðîöåäóðàìè êîíòðîëþ, íå
ìîãëà çì³íèòè öþ ïîâåä³íêó.
Çã³äíî ç íàâåäåíèìè íèæ÷å ïîñòóëàòàìè [6] ñòâîðþºòüñÿ ìîäåëü äëÿ òàêî¿
ñèñòåìè:
— ïðîñòîðîì ñòàí³â ñèñòåìè º àñîö³éîâàíèé ç ³çîëüîâàíîþ êâàíòîâî-ìå-
õàí³÷íîþ ñèñòåìîþ âåêòîðíèé ïðîñò³ð íàä ïîëåì êîìïëåêñíèõ ÷èñåë ç âèçíà÷å-
íèì ñêàëÿðíèì äîáóòêîì (ã³ëüáåðò³â ïðîñò³ð), ñòàí ñèñòåìè â áóäü-ÿêèé ìîìåíò
÷àñó ïîâí³ñòþ îïèñóºòüñÿ âåêòîðîì ñòàíó, ùî º îäèíè÷íèì âåêòîðîì ó ïðîñòîð³
ñòàí³â;
— åâîëþö³ÿ ñòàíó (çì³íà ñòàíó) çàìêíåíî¿ êâàíòîâî-ìåõàí³÷íî¿ ñèñòåìè
îïèñóºòüñÿ ò³ëüêè óí³òàðíèì ïåðåòâîðåííÿì. ßêùî ñèñòåìà ìຠñòàí | �1� ó ìî-
ìåíò ÷àñó t1 ³ ñòàí | � 2 � ó ìîìåíò ÷àñó t2 , òî ö³ ñòàíè ïîâ’ÿçàí³ óí³òàðíèì ïåðå-
òâîðåííÿìU , ÿêå çàëåæèòü ò³ëüêè â³ä ìîìåíò³â t1 ³ t2 , òàêèì, ùî | |� �2 1� � �U ;
— âèì³ðþâàííÿ êâàíòîâî¿ ñèñòåìè ñêëàäàºòüñÿ ç íàáîðó ë³í³éíèõ îïåðà-
òîð³â, ùî ä³þòü íà ïðîñò³ð ñòàí³â ñèñòåìè, ³ ôàêòè÷íî º ïðîåêö³ºþ íà îðòîãî-
íàëüí³ ï³äïðîñòîðè;
— ïðîñò³ð ñòàí³â ñêëàäíî¿ êâàíòîâî-ìåõàí³÷íî¿ ñèñòåìè º òåíçîðíèì äîáóò-
êîì ïðîñòîð³â ñòàí³â ¿¿ ñêëàäîâèõ ÷àñòèí.
Ðîçãëÿíåìî ïîíÿòòÿ ïàðàëåëüíîãî êâàíòîâîãî îá÷èñëåííÿ. Îñíîâíèì ³íñòðó-
ìåíòîì â îïåðàö³ÿõ ö³º¿ ñõåìè º ñ³ìåéñòâî ôóíêö³é, ÿê³ áóäóòü îïèñàí³ íèæ÷å.
Îçíà÷åííÿ 1. Îäíîêóá³òíå ïåðåòâîðåííÿ Óîëøà–Àäàìàðà (Walsh–Hadamard)
— öå óí³òàðíèé îïåðàòîð H , ùî 䳺 íà îäíîêóá³òíó ñèñòåìó ³ çàäàºòüñÿ
ñï³ââ³äíîøåííÿìè H ( | ) (| | )0
1
2
0 1� � � � � ³ H ( | ) ( | | )1
1
2
0 1� � � � � .
Îïåðàòîð H ìîæíà çàïèñàòè ñòèñëî ó âèãëÿä³ H x(| )� �
1
2
0 1 1( | ( ) | )� � � � �x
� � �
�
�
1
2
1
0
1
( ) |kx
k
k . Òàêîæ áåçïîñåðåäí³ì îá÷èñëåííÿì ìîæíà ïåðåâ³ðèòè, ùî îïå-
ðàòîð H º ³íâîëþòèâíèì, òîáòî H I2
2� . Êð³ì òîãî, ÿêùî çíåõòóâàòè êîìïëåê-
ñíèìè êîåô³ö³ºíòàìè, òî H º ñèìåòðè÷íèì â³äîáðàæåííÿì â³äíîñíî ïðÿìî¿, ÿêà
óòâîðþº êóò
�
8
ç |0�-â³ññþ.
Çàóâàæèìî, ùî n-êóá³òíå ïåðåòâîðåííÿ Óîëøà–Àäàìàðà H n âèçíà÷àºòüñÿ ÿê
H n� (îïåðàö³ÿ � îçíà÷ຠòåíçîðíèé äîáóòîê). Îñê³ëüêè H — ³íâîëþòèâíèé îïå-
ðàòîð, òî H I In
n
n
2
2 2
� �� , òîáòî H n òàêîæ º ³íâîëþòèâíèì îïåðàòîðîì. Ó âèïàä-
êó çàñòîñóâàííÿ äî ñòàíó |0� �nîïåðàòîð H n ãåíåðóº îäíîð³äíó ë³í³éíó
êîìá³íàö³þ ö³ëèõ ÷èñåë â³ä 0 äî 2 1n � , òîáòî H xn
n x
n
(| .. ) |0 0
1
2 0
2 1
� � �
�
�
� .
Ïåðåòâîðåííÿ Óîëøà–Àäàìàðà äàþòü çìîãó ï³äãîòóâàòè âõ³äí³ äàí³ äëÿ ïà-
ðàëåëüíîãî îá÷èñëåííÿ. Ðîçãëÿíåìî ïðîöåäóðó îá÷èñëåííÿ ÿê òàêó. Íåõàé
f Z Zm k: 2 2 — äåÿêà ôóíêö³ÿ, íå îáîâ’ÿçêîâî îáîðîòíà. Îñê³ëüêè îáîðîòí³ñòü
ôóíêö³¿ f íå âèìàãàºòüñÿ, òî ¿¿ â òàêîìó âèãëÿä³ íå ìîæíà âèêîðèñòîâóâàòè ÿê
ïåðåòâîðåííÿ â êâàíòîâîìó êîìï’þòåð³. Îäíàê çà ðàõóíîê âèêîðèñòàííÿ ïåâíîãî
äîäàòêîâîãî îá’ºìó ïàì’ÿò³ ìîæíà ñòâîðèòè óí³òàðíå ïåðåòâîðåííÿ äëÿ ìîäåëþ-
âàííÿ ôóíêö³¿ f . Äëÿ öüîãî ïîòð³áíà êâàíòîâà ñèñòåìà V , ùî º òåíçîðíèì äîáóò-
êîì m-êóá³òíî¿ òà k-êóá³òíî¿ êâàíòîâèõ ñèñòåì. Íàãàäàºìî, ùî ñèñòåìà V ìຠáà-
çèñ, ÿêèé ñêëàäàºòüñÿ ç âåêòîð³â | |x y�� �, äå x ³ y — äâ³éêîâ³ ïðåäñòàâëåííÿ ö³ëèõ
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1 19
÷èñåë â Z m
2
³ Z k
2
â³äïîâ³äíî. Âèçíà÷èìî ë³í³éíå ïåðåòâîðåííÿU x yf : | |� � � �
� | | ( )x y f x� �
�, äå
ïîçíà÷ຠîïåðàö³þ äîäàâàííÿ â ãðóï³ Z k
2
(â³äîìå òàêîæ
ÿê XOR). Äëÿ ô³êñîâàíîãî çíà÷åííÿ x âåëè÷èíà y f x
( ) íàáóâຠêîæíîãî çíà-
÷åííÿ â Z k
2
òî÷íî îäèí ðàç, îñê³ëüêè y íàáóâຠçíà÷åíü ç Z k
2
. Òîìó ðåçóëüòàòîì
ïåðåòâîðåííÿ U f º ïðîñòî ïåðåñòàíîâêà âñ³õ 2m k� åëåìåíò³â áàçèñó V ³ ç öüîãî
âèïëèâàº, ùî âîíî º óí³òàðíèì. Êð³ì òîãî, U x x f xf ( | | ) | | ( )� � � � � � �0 . Ó öüîìó
ñåíñ³ U f ìîäåëþº îá÷èñëåííÿ çíà÷åííÿ ôóíêö³¿ f . Òàêå â³äîáðàæåííÿ U f íàçè-
âàþòü ñòàíäàðòíèì îðàêóëîì äëÿ ôóíêö³¿ f . Òàêèì ÷èíîì, ñòàíäàðòíèé îðàêóë
ìîæíà çàñòîñîâóâàòè äëÿ ìîäåëþâàííÿ áóäü-ÿêî¿ ôóíêö³¿, îáîðîòíî¿ ÷è í³, íà
êâàíòîâîìó êîìï’þòåð³. Ç öüîãî ñâîºþ ÷åðãîþ âèïëèâàº, ùî áóäü-ÿêó ôóíêö³þ,
ÿêó ìîæíà îá÷èñëèòè çà äîïîìîãîþ êëàñè÷íîãî êîìï’þòåðà, òàêîæ ìîæíà
îá÷èñëèòè çà äîïîìîãîþ êâàíòîâîãî êîìï’þòåðà.
Ó òîìó ðàç³, êîëè ôóíêö³ÿ f º ᳺêòèâíîþ (³ ëèøå çà ö³º¿ óìîâè), ìîæíà âèç-
íà÷èòè ïðîñò³øèé ³ á³ëüø î÷åâèäíèé îðàêóë | | ( )x f x� �. Éîãî íàçèâàþòü
ì³í³ìàëüíèì àáî çàòèðàþ÷èì îðàêóëîì äëÿ f (³ñíóº çàäà÷à, äëÿ ÿêî¿ ïîêàçàíî,
ùî âèêîðèñòàííÿ äëÿ ¿¿ ðîçâ’ÿçêó ì³í³ìàëüíîãî îðàêóëó º åêñïîíåíö³àëüíî á³ëüø
âèã³äíèì â³äíîñíî ê³ëüêîñò³ ðåñóðñ³â, í³æ ñòàíäàðòíîãî îðàêóëó).
Ìîæíà ðîçãëÿäàòè öå ÿê îäíî÷àñíå îá÷èñëåííÿ ôóíêö³¿ f äëÿ âñ³õ ìîæëè-
âèõ çíà÷åíü àðãóìåíòó x , õî÷à òå, ùî | ( )f x � ìຠçâ’ÿçîê ç³ ñòàíîì | x�, äëÿ âñ³õ x
³íîä³ ìîæå ñòâîðþâàòè òðóäíîù³. Ôîðìóâàííÿ ñòàíó òàêîãî âèäó ÷àñòî íàçèâà-
þòü êâàíòîâèì ïàðàëåë³çìîì. Öå — ïðîñòèé ³ ñòàíäàðòíèé ïåðøèé êðîê ó áà-
ãàòüîõ êâàíòîâèõ îá÷èñëåííÿõ. Íàéâàæ÷èé åòàï — çäîáóòòÿ êîðèñíî¿ ³íôîðìàö³¿
ç öüîãî (íàäçâè÷àéíî ïåðåïëóòàíîãî) ðåçóëüò³âíîãî ñòàíó.
Ïîä³áíî äî êëàñè÷íî¿ ìîäåë³ îá÷èñëåíü ìîæíà ñòâîðèòè ìîäåëü áóäü-ÿêî¿
êâàíòîâî¿ ñõåìè, âèêîðèñòîâóþ÷è ëèøå ïðîñò³ óí³òàðí³ ïåðåòâîðåííÿ âåêòîðíîãî
ïðîñòîðó — êâàíòîâ³ âåíòèë³. Êîæåí êâàíòîâèé âåíòèëü îïåðóº ëèøå ê³ëüêîìà
êóá³òàìè çà îäèí ðàç. Ó êâàíòîâ³é ìîäåë³ ³ñíóþòü ñê³í÷åíí³ íàáîðè âåíòèë³â, ÿê³ äà-
þòü çìîãó ïîáóäóâàòè äîâ³ëüíå óí³òàðíå ïåðåòâîðåííÿ ç áàæàíîþ òî÷í³ñòþ.
Î. ʳòàºâ ïîêàçàâ, ùî òàêå íàáëèæåííÿ ìîæíà âèêîíàòè ç ì³í³ìàëüíèì çá³ëüøåííÿì
âèêîðèñòîâóâàíèõ ðåñóðñ³â [7], òîáòî ó êâàíòîâ³é ìîäåë³ âñ³ îá÷èñëåííÿ ìîæíà ìî-
äåëþâàòè ç âèêîðèñòàííÿì ïåâíîãî íàáîðó ïðîñòèõ ñõåì. Äî òîãî æ, ó ðîáîò³ [8]
À. ßî ïðîäåìîíñòðóâàâ åêâ³âàëåíòí³ñòü ìîäåë³ ç âèêîðèñòàííÿì ñõåì òà êâàíòîâî¿
ìàøèíè Òþð³íãà, ÿêó çàïðîïîíóâàâ Ä. Äîé÷. Òàê ñàìî ÿê ³ â êëàñè÷í³é ìîäåë³ îá-
÷èñëåíü, ó êâàíòîâ³é ìîäåë³ åôåêòèâíèìè îá÷èñëåííÿìè º ò³, ÿê³ ìîæíà âèêîíàòè
ç âèêîðèñòàííÿì ïîë³íîì³àëüíî îáìåæåíî¿ ïîñë³äîâíîñò³ åëåìåíòàðíèõ âåíòèë³â.
Îçíà÷åííÿ 2. Ðîçì³ðîì êâàíòîâî¿ ñõåìè (ïåðåòâîðåííÿ) º ì³í³ìàëüíà
ê³ëüê³ñòü åëåìåíòàðíèõ îïåðàö³é íàä ô³êñîâàíèì íàáîðîì ïðîñòèõ âåíòèë³â,
ïîòð³áíà äëÿ ïîáóäîâè ö³º¿ ñõåìè (ïåðåòâîðåííÿ).
Ó òàêèé ñïîñ³á ìîæíà îö³íþâàòè ñêëàäí³ñòü êâàíòîâèõ îïåðàö³é àáî ïåðå-
òâîðåíü. Á³ëüø òîãî, öÿ îö³íêà ÿê³ñíî íå çì³íþºòüñÿ ó ðàç³ çàì³íè íàáîðó òâ³ðíèõ
âåíòèë³â íà ³íøèé, ùî º çàãàëüíîïðèéíÿòèì.
Çäåá³ëüøîãî îñíîâíèé ³íòåðåñ ñòàíîâëÿòü ñàìå åôåêòèâí³ êâàíòîâ³ îá÷èñëåííÿ.
ßê ïðàâèëî, òàê³ îá÷èñëåííÿ ñêëàäàþòüñÿ ç äâîõ ÷àñòèí, ÿê³ äîñèòü ÷àñòî º íåçàëåæ-
íèìè: åôåêòèâíîãî êâàíòîâîãî ïðîöåñó ³ åôåêòèâíî¿ êëàñè÷íî¿ îáðîáêè äàíèõ,
îòðèìàíèõ â ðåçóëüòàò³ ïðîâåäåíèõ âèì³ðþâàíü âïðîäîâæ êâàíòîâîãî ïðîöåñó.
Êâàíòîâ³ êîìï’þòåðè º éìîâ³ðí³ñíèìè çà ñâîºþ ïðèðîäîþ. Òîìó àáñîëþòíà
á³ëüø³ñòü àëãîðèòì³â º òàêîæ ³ìîâ³ðí³ñíèìè, àëå öüîãî äîñèòü äëÿ åôåêòèâíîãî
ðîçâ’ÿçàííÿ çàäà÷³ (çà óìîâè åôåêòèâíîñò³ éìîâ³ðí³ñíîãî àëãîðèòìó). Äîñòàòíüî
ïðîâåñòè åêñïåðèìåíò äåê³ëüêà ðàç³â ³ âèçíà÷èòè îñòàòî÷íèé ðåçóëüòàò çà
á³ëüø³ñòþ ðåçóëüòàò³â åêñïåðèìåíòó. Òàêèé ï³äõ³ä ìîæå ãàðàíòóâàòè â³ðíó
â³äïîâ³äü ç ³ìîâ³ðí³ñòþ, ÿêà º ÿê çàâãîäíî áëèçüêîþ äî îäèíèö³.
20 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1
3. ÅÔÅÊÒÈÂͲ ÊÂÀÍÒβ ÀËÃÎÐÈÒÌÈ
Íà ñüîãîäí³ çàäà÷à ïðî ïðèõîâàíó ï³äãðóïó º âäàëèì îá’ºäíàííÿì ïðèêëàä³â
çàäà÷, ÿê³ ìîæíà åôåêòèâíî ðîçâ’ÿçàòè çà äîïîìîãîþ êâàíòîâîãî êîìï’þòåðà,
íà â³äì³íó â³ä íàÿâíèõ àëãîðèòì³â äëÿ êëàñè÷íîãî êîìï’þòåðà, ùî âïåðøå
â³äçíà÷åíî â ðîáîò³ [9].
Çàäà÷à 1 (ïðî ïðèõîâàíó ï³äãðóïó, àíãë. Hidden Subgroup Problem, HSP).
Íåõàé çàäàíî ìíîæèíó òâ³ðíèõ åëåìåíò³â ãðóïè G, äåÿêó ñê³í÷åííó ìíîæèíó X
³ â³äîáðàæåííÿ f G X: ç äîäàòêîâîþ óìîâîþ, ùî ³ñíóº òàêà ï³äãðóïà H G� ,
ùî äëÿ äîâ³ëüíèõ åëåìåíò³â g g G1 2, � âèêîíóºòüñÿ òîòîæí³ñòü f g f g( ) ( )1 2�
òîä³ é ò³ëüêè òîä³, êîëè g H g H1 2� (çà òàêèõ óìîâ áóäåìî êàçàòè, ùî â³äîáðàæåí-
íÿ f ïðèõîâóº ï³äãðóïó H). Ïîòð³áíî çíàéòè ìíîæèíó òâ³ðíèõ åëåìåíò³â ï³äãðó-
ïè H çà äîïîìîãîþ îá÷èñëåííÿ ôóíêö³¿ f .
Çàóâàæåííÿ 1. ×àñòêîâèé âèïàäîê çàäà÷³ ïðî ïðèõîâàíó ï³äãðóïó, êîëè ãðó-
ïà G º àáåëåâîþ, íàçèâàºòüñÿ àáåëåâîþ çàäà÷åþ ïðî ïðèõîâàíó ï³äãðóïó.
Òâåðäæåííÿ 1 [7]. ßêùî â óìîâàõ çàäà÷³ 1 ôóíêö³ÿ f º åôåêòèâíî îá÷èñëþ-
âàíîþ â êëàñè÷í³é ìîäåë³ îá÷èñëåíü, à ãðóïà G — àáåëåâà, òî ó êâàíòîâ³é ìîäåë³
îá÷èñëåíü ³ñíóº åôåêòèâíèé àëãîðèòì ðîçâ’ÿçêó ö³º¿ çàäà÷³.
Î. ʳòàºâ ó ðîáîò³ [7] âèä³ëèâ âëàñòèâ³ñòü êîìóòàòèâíîñò³ ãðóïè ÿê äîñòàòíþ
óìîâó ³ñíóâàííÿ åôåêòèâíîãî ðîçâ’ÿçêó çàäà÷³ 1 ó êâàíòîâ³é ìîäåë³ îá÷èñëåíü.
Äîñ³ ó á³ëüøîñò³ ðîá³ò ùîäî äîâåäåííÿ ³ñíóâàííÿ åôåêòèâíîãî â êâàíòîâ³é ìî-
äåë³ îá÷èñëåíü àëãîðèòìó ðîçâ’ÿçêó äåÿêî¿ çàäà÷³ âèêîðèñòîâóþòü ¿¿ çâåäåííÿ äî
àáåëåâî¿ çàäà÷³ ïðî ïðèõîâàíó ï³äãðóïó, òîáòî òâåðäæåííÿ 1.
Îñíîâíîþ ïðîáëåìîþ º ïîáóäîâà òàêèõ êâàíòîâèõ àëãîðèòì³â, ùîá îáðîá-
ëåííÿ ðåçóëüòàò³â ç â³äíîâëåííÿ ïðèõîâàíî¿ ï³äãðóïè âèêîíóâàëîñÿ çà
ïîë³íîì³àëüíèé ÷àñ íà êëàñè÷íîìó êîìï’þòåð³.  àáåëåâîìó âèïàäêó çðîáèòè öå
äàþòü çìîãó àëãîðèòì Åâêë³äà òà åôåêòèâíèé àëãîðèòì ðîçâ’ÿçàííÿ ñèñòåìè
ë³í³éíèõ ð³âíÿíü.
гçíèöÿ ì³æ êâàíòîâèìè îá÷èñëåííÿìè òà éìîâ³ðí³ñíèì ìåòîäîì ðîçâ’ÿçàí-
íÿ ïîëÿãຠëèøå â òîìó, ùî ìàòðèö³ ïåðåòâîðåíü ó êâàíòîâîìó âèïàäêó ìîæóòü
ì³ñòèòè äîâ³ëüí³ êîìïëåêñí³ ÷èñëà, à â ³ìîâ³ðí³ñíîìó — ëèøå íåâ³ä’ºìí³ ä³éñí³
÷èñëà, äî òîãî æ óí³òàðí³ ïåðåòâîðåííÿ çáåð³ãàþòü íîðìó âåêòîðà â ïðîñòîð³ L2 ,
à ³ìîâ³ðí³ñí³ ïåðåòâîðåííÿ — â L1.
Ä. Äîé÷ ïåðøèì ïîêàçàâ, ùî, ìîæëèâî, êâàíòîâà ìîäåëü îá÷èñëåíü ìຠïå-
ðåâàãó íàä êëàñè÷íîþ ìîäåëëþ. Àëå âàðòî çàçíà÷èòè, ùî éäåòüñÿ ïðî îö³íêó
ñêëàäíîñò³ â³äíîñíî ê³ëüêîñò³ çàïèò³â äî îðàêóëà, ùî îá÷èñëþº äîñë³äæóâàíó
ôóíêö³þ. Ôóíêö³þ f Z Z: 2 2 íàçèâàþòü ñòàëîþ, ÿêùî f f( ) ( )0 1� , ³ çáàëàíñî-
âàíîþ, ÿêùî f f( ) ( )0 1
. Íåõàé çàäàíî äåÿêó ôóíêö³þ f Z Z: 2 2 çà äîïîìîãîþ
îðàêóëà. Âèêîðèñòîâóþ÷è çàïèòè äî îðàêóëà ùîäî îá÷èñëåííÿ çíà÷åíü ôóíêö³¿,
ïîòð³áíî âèçíà÷èòè, äî ÿêîãî òèïó âîíà íàëåæèòü. Ó ðàç³ âèêîðèñòàííÿ êëàñè÷-
íèõ äåòåðì³íîâàíèõ îá÷èñëåíü ïîòð³áíî çðîáèòè äâà çàïèòè äî îðàêóëà, à ó êâàí-
òîâ³é ìîäåë³ îá÷èñëåíü äîñòàòíüî îäíîãî.
Óçàãàëüíåííÿ ïîïåðåäíüî¿ çàäà÷³ çðîáëåíî â ðîáîò³ [10], äå ðîçãëÿäàþòüñÿ
ôóíêö³¿ f Z Zm: 2 2 , m N� . Ôóíêö³þ f íàçèâàþòü çáàëàíñîâàíîþ, ÿêùî ïîòóæ-
íîñò³ ïðîîáðàç³â 0 òà1 îäíàêîâ³, òà ñòàëîþ, ÿêùî çíà÷åííÿ ôóíêö³¿ f º îäíàêîâèì
íà âñ³é îáëàñò³ âèçíà÷åííÿ. Àëãîðèòì Äîé÷à–Äæîçè ó êâàíòîâ³é ìîäåë³ îá÷èñ-
ëåíü äຠçìîãó ðîçð³çíèòè ö³ äâà âèïàäêè ç âèêîðèñòàííÿì îäíîãî çàïèòó äî îðà-
êóëà ùîäî îá÷èñëåííÿ ôóíêö³¿ f [10]. Öÿ çàäà÷à º ÷àñòêîâèì âèïàäêîì çàäà÷³ 1
ïðî ïðèõîâàíó ï³äãðóïó, äå ãðóïà G Z m� 2
, ìíîæèíà X Z� 2 , à â³äîáðàæåííÿ
f Z Zm: 2 2 ïðèõîâóº ï³äãðóïó H , ÿêà çá³ãàºòüñÿ ç ãðóïîþ G ó âèïàäêó ñòàëî¿
ôóíêö³¿ f òà ì³ñòèòü ïîëîâèíó åëåìåíò³â ãðóïè G ó âèïàäêó çáàëàíñîâàíî¿
ôóíêö³¿ f . Äëÿ m �1 çàäà÷à çâîäèòüñÿ äî îðèã³íàëüíî¿ çàäà÷³ Äîé÷à.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1 21
Ó 1993 ð. Å. Áåðíøòåéí òà Ó. Âàç³ðàí³ ðîçãëÿíóëè òàêó çàäà÷ó: ïðî â³äîáðà-
æåííÿ f n: { , } { , }0 1 0 1 â³äîìî, ùî ³ñíóº òàêå çíà÷åííÿ a n�{ , }0 1 , ùî f x a x( ) � �
äëÿ âñ³õ çíà÷åíü x n�{ , }0 1 , äå îïåðàö³ÿ « � » º ïîçíà÷åííÿì ñóìè çà ìîäóëåì 2 äî-
áóòê³â â³äïîâ³äíèõ á³ò³â (àíàëîã³÷íî ñêàëÿðíîìó äîáóòêó íàä Z2), ³ ïîòð³áíî
çíàéòè íåâ³äîìå çíà÷åííÿ a . Öþ çàäà÷ó áóëî åôåêòèâíî ðîçâ’ÿçàíî â êâàíòîâ³é
ìîäåë³ îá÷èñëåíü ç âèêîðèñòàííÿì îäíîãî çàïèòó ùîäî îá÷èñëåííÿ ôóíêö³¿ f ,
õî÷à ó êëàñè÷í³é ìîäåë³ îá÷èñëåíü ïîòð³áíî n çàïèò³â. Çàäà÷à Áåðíøòåé-
íà–Âàç³ðàí³ òàêîæ º ÷àñòêîâèì âèïàäêîì àáåëåâî¿ çàäà÷³ ïðî ïðèõîâàíó ï³äãðó-
ïó, êîëè ãðóïà G Z n� 2
, ìíîæèíà X Z� 2 , à â³äîáðàæåííÿ f Z Zn: 2 2 ïðèõîâóº
ï³äãðóïó H y a y� � �{ | }0 .
Ó 1994 ð. Ä. Ñàéìîí ðîçãëÿíóâ â³äîáðàæåííÿ f Z Zm m: 2 2 ïðî ÿêå â³äîìî,
ùî àáî âñ³ çíà÷åííÿ f x( ) , x Z m� 2
, º ð³çíèìè (âèïàäîê 1–1), àáî ³ñíóº òàêå çíà-
÷åííÿ s Z m� 2
, ùî äëÿ äîâ³ëüíèõ åëåìåíò³â x y Z m, � 2
âèêîíóºòüñÿ ð³âí³ñòü
f x f y( ) ( )� òîä³ ³ ò³ëüêè òîä³, êîëè x y� àáî x y s�
(âèïàäîê 2–1). ³í çàïðîïî-
íóâàâ êâàíòîâèé àëãîðèòì ðîçâ’ÿçàííÿ çàäà÷³ ðîçð³çíåííÿ öèõ âèïàäê³â, âèêîðèñ-
òîâóþ÷è â ñåðåäíüîìó O m( ) çàïèò³â äî îðàêóëà ùîäî îá÷èñëåííÿ ôóíêö³¿ f
(ï³çí³øå Æ. Áðàññàð ³ Ï. Õîºð ïîë³ïøèëè ðåçóëüòàò O m( ) çàïèò³â â ñåðåäíüîìó äî
O m( ) çàïèò³â ó íàéã³ðøîìó âèïàäêó). Äëÿ áóäü-ÿêîãî àëãîðèòìó, íàâ³òü
³ìîâ³ðí³ñíîãî, ó êëàñè÷í³é ìîäåë³ îá÷èñëåíü íåîáõ³äíîþ ê³ëüê³ñòþ çàïèò³â äëÿ
ðîçâ’ÿçàííÿ ö³º¿ çàäà÷³ º � ( )/2 2m . Îòæå ñàìå êâàíòîâèé àëãîðèòì Ñàéìîíà áóâ
ïåðøèì àëãîðèòìîì, ÿêèé ðîçâ’ÿçóâàâ ïåâíó çàäà÷ó åêñïîíåíö³àëüíî øâèäøå
í³æ áóäü-ÿêèé àëãîðèòì â êëàñè÷í³é ìîäåë³ îá÷èñëåíü â³äíîñíî íåîáõ³äíî¿
ê³ëüêîñò³ çàïèò³â äî îðàêóëà. Ðîçãëÿíóòà çàäà÷à º ÷àñòêîâèì âèïàäêîì çàäà÷³ 1
ïðî ïðèõîâàíó ï³äãðóïó, äå ãðóïà G Z m� 2
ç îïåðàö³ºþ
, ìíîæèíà X Z m� 2
,
à â³äîáðàæåííÿ f Z Zm m: 2 2 ïðèõîâóº ï³äãðóïó H , ÿêà çá³ãàºòüñÿ ç òðèâ³àëüíîþ
H � { }0 ó âèïàäêó 1–1 òà H s� { , }0 ó âèïàäêó 2–1.
Ó 1994 ð. ç’ÿâëÿºòüñÿ ðîáîòà Ï. Øîðà [11], ÿêà é äîñ³ º îäíèì ç íàéâè-
äàòí³øèõ ðåçóëüòàò³â äîñë³äæåííÿ êâàíòîâî¿ ìîäåë³ îá÷èñëåíü. Ó í³é ïðåäñòàâ-
ëåíî ïîë³íîì³àëüí³ àëãîðèòìè ðîçâ’ÿçàííÿ çàäà÷ ôàêòîðèçàö³¿ ö³ëèõ ÷èñåë òà
äèñêðåòíîãî ëîãàðèôìóâàííÿ ó êâàíòîâ³é ìîäåë³ îá÷èñëåíü. Á³ëüø òî÷íî â [11] ³
â íàñòóïí³é ðîáîò³ [12] ó 1997 ð. Ï. Øîð âèêîðèñòàâ â³äîìå çâåäåííÿ çàäà÷³ ôàê-
òîðèçàö³¿ ö³ëîãî ÷èñëà n N� äî çàäà÷³ ïîøóêó ïîêàçíèêà �, ÿêîìó íàëåæèòü âè-
ïàäêîâî îáðàíå ö³ëå ÷èñëî 1� �a n çà ìîäóëåì n.
Çàäà÷à ïîøóêó ïîêàçíèêà, çàäà÷à äèñêðåòíîãî ëîãàðèôìóâàííÿ òà ³íø³ ïðåä-
ñòàâëåí³ âèùå çàäà÷³ çâîäÿòüñÿ äî àáåëåâî¿ çàäà÷³ ïðî ïðèõîâàíó ï³äãðóïó, ùî
äຠçìîãó ñêîðèñòàòèñÿ òâåðäæåííÿì 1.
Íåçâàæàþ÷è íà òå, ùî äîñèòü áàãàòî çóñèëü áóëî äîêëàäåíî äî ïîøóê³â
åôåêòèâíèõ êâàíòîâèõ ðîçâ’ÿçê³â çàäà÷³ ïðî ïðèõîâàíó ï³äãðóïó äëÿ íåàáåëåâèõ
ãðóï G , ìàéæå âñ³ â³äîì³ êâàíòîâ³ àëãîðèòìè ç ïîë³íîì³àëüíèì ÷àñîì áóëè çíàé-
äåí³ äëÿ ãðóï, äóæå áëèçüêèõ äî àáåëåâèõ. Áóëî çàïðîïîíîâàíî ö³ëèé êëàñ çàäà÷,
ïîä³áíèõ äî çàäà÷³ ïðî ïðèõîâàíó ï³äãðóïó ³, ÿê íàñë³äîê, ïîâ’ÿçàíèõ ç íåþ.
Çàäà÷à 2 (ïðî ïðèõîâàíèé çñóâ, àíãë. Hidden Shift Problem, Hidden
Translation Problem, DHSP) [13]. Íåõàé çàäàíî ìíîæèíó òâ³ðíèõ åëåìåíò³â ãðóïè
G , òà äâ³ ³í’ºêòèâí³ ôóíêö³¿ — f 0 ³ f1, ÿê³ â³äîáðàæàþòü ãðóïó G ó äåÿêó ìíîæè-
íó X ç äîäàòêîâîþ óìîâîþ, ùî ³ñíóº òàêèé åëåìåíò u G� , ÿêèé íàçèâàºòüñÿ çñó-
âîì, ùî äëÿ áóäü-ÿêîãî çíà÷åííÿ g G� âèêîíóºòüñÿ ñï³ââ³äíîøåííÿ
f g f g u0 1( ) ( )� � . Ïîòð³áíî çíàéòè íåâ³äîìå çíà÷åííÿ çñóâó u , ñêîðèñòàâøèñü
îá÷èñëåííÿì ôóíêö³é f 0 ³ f1.
22 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1
Òâåðäæåííÿ 2. Àáåëåâà çàäà÷à ïðî ïðèõîâàíèé çñóâ äëÿ öèêë³÷íî¿ ãðóïè
Z N º åêâ³âàëåíòíîþ çàäà÷³ ïðî ïðèõîâàíó ï³äãðóïó äëÿ ä³åäðàëüíî¿ ãðóïè D N .
Çíà÷íà ãíó÷ê³ñòü ïîñòàíîâêè çàäà÷ ïðî ïðèõîâàíó ï³äãðóïó òà ïðî ïðèõîâà-
íèé çñóâ äຠçìîãó âèêîðèñòîâóâàòè ¿õ ï³ä ÷àñ ðîçâ’ÿçàííÿ äîñèòü âåëèêî¿
ê³ëüêîñò³ ð³çíîìàí³òíèõ çàäà÷, íàïðèêëàä, ÿê öå áóëî çðîáëåíî â ðîáîò³ [14] äëÿ
äåÿêèõ çàäà÷ êîìá³íàòîðíî¿ òåî𳿠ãðóï.
4. ÎÃËßÄ ÍÀßÂÍÈÕ ÐÅÀ˲ÇÀÖ²É ÊÂÀÍÒÎÂÈÕ ÎÁ×ÈÑËÞÂÀËÜÍÈÕ ÏÐÈÑÒÐίÂ
Ïîáóäîâà äîñòàòíüî ïîòóæíîãî êâàíòîâîãî êîìï’þòåðà ó âèãëÿä³ ðåàëüíîãî
ô³çè÷íîãî ïðèñòðîþ º îäí³ºþ ç ôóíäàìåíòàëüíèõ çàäà÷ ñó÷àñíî¿ ô³çèêè. Íà
ñüîãîäí³ ³ñíóþòü ëèøå îáìåæåí³ ðåàë³çàö³¿ êâàíòîâèõ îá÷èñëþâàëüíèõ ïðè-
ñòðî¿â.
³äîìî, ùî º äâà îñíîâíèõ âèäè ðåàë³çàö³é êâàíòîâèõ îá÷èñëþâàëüíèõ ïðè-
ñòðî¿â: óí³âåðñàëüí³ (íàïðèêëàä, 50-êóá³òíèé êâàíòîâèé êîìï’þòåð IBM) òà
íåóí³âåðñàëüí³ (íàïðèêëàä, ïðèñòðî¿ êîìïàí³¿ D-Wave). Ãîëîâíîþ â³äì³íí³ñòþ º
òå, ùî óí³âåðñàëüí³ êâàíòîâ³ îá÷èñëþâàëüí³ ïðèñòðî¿ ðîçðîáëÿþòü ç ìåòîþ âèêî-
íàííÿ äîâ³ëüíèõ äîçâîëåíèõ îïåðàö³é òà ðîçâ’ÿçàííÿ äîâ³ëüíèõ çàäà÷. Íåóí³âåð-
ñàëüí³ îá÷èñëþâàëüí³ ïðèñòðî¿ ñòâîðþþòü äëÿ ðîçâ’ÿçàííÿ äåÿêîãî îáìåæåíîãî
êëàñó çàäà÷, íàïðèêëàä, äëÿ îïòèì³çàö³¿ ïåâíèõ àëãîðèòì³â ìàøèííîãî íàâ÷àííÿ.
Çã³äíî ç Ä. ij³í÷åíöî ³ñíóº âèçíà÷åíèé íàá³ð âèìîã äî ðåàëüíîãî óí³âåð-
ñàëüíîãî êâàíòîâîãî îá÷èñëþâàëüíîãî ïðèñòðîþ, à ñàìå:
• ìàñøòàáîâàí³ñòü (ìîæëèâ³ñòü çá³ëüøåííÿ) ÷èñëà êóá³ò³â;
• ìîæëèâ³ñòü ³í³ö³àë³çàö³¿ êâàíòîâèõ ðåã³ñòð³â (êóá³ò³â) ó áóäü-ÿêèé ïî÷àò-
êîâèé ñòàí;
• çäàòí³ñòü êâàíòîâèõ âåíòèë³â â³äïðàöüîâóâàòè ïðîòÿãîì ÷àñó, ìåíøîãî,
í³æ ÷àñ äåêîãåðåíö³¿;
• ðåàë³çàö³ÿ ïîâíîãî íàáîðó âåíòèë³â (Òþð³íãà);
• ìîæëèâ³ñòü ç÷èòóâàííÿ ³íôîðìàö³¿ ç êâàíòîâèõ ðåã³ñòð³â.
Ñåðåä îñíîâíèõ òåõíîëîã³é ðåàë³çàö³¿ êâàíòîâîãî îá÷èñëþâàëüíîãî ïðèñòðîþ
ñë³ä âèä³ëèòè òàê³:
• òâåðäîò³ëüí³ êâàíòîâ³ òî÷êè (ëîã³÷íèì êóá³òîì º íàïðàâëåí³ñòü åëåêòðîí-
íîãî àáî ÿäåðíîãî ñï³íó â êâàíòîâ³é òî÷ö³, êåðóâàííÿ çä³éñíþºòüñÿ çà äîïîìîãîþ
çîâí³øí³õ ïîòåíö³àë³â ÷è ëàçåðíîãî ³ìïóëüñó);
• íàäïðîâ³äí³ åëåìåíòè (ëîã³÷íèì êóá³òîì º ïðèñóòí³ñòü àáî â³äñóòí³ñòü êó-
ïåð³âñüêî¿ ïàðè â ïåâí³é îáëàñò³, êåðóâàííÿ çä³éñíþºòüñÿ çà äîïîìîãîþ
çîâí³øíüîãî ïîòåíö³àëó ÷è ìàãí³òíîãî ïîòîêó);
• ³îíè â âàêóóìíèõ ïàñòêàõ Ïàóëÿ (ëîã³÷íèì êóá³òîì º îñíîâíèé àáî çáóä-
æåíèé ñòàí çîâí³øíüîãî åëåêòðîíó â ³îí³, êåðóâàííÿ çä³éñíþºòüñÿ çà äîïîìîãîþ
ëàçåðíèõ ³ìïóëüñ³â);
• âèêîðèñòàííÿ çàïëóòàíèõ ñòàí³â ôîòîí³â.
Îñíîâíèìè ïðîáëåìàìè â ïîáóäîâ³ äîñòàòíüî âåëèêèõ êâàíòîâèõ îá÷èñëþ-
âàëüíèõ ïðèñòðî¿â º çîâí³øí³é âïëèâ, ÿêèé ìîæå çðóéíóâàòè ñòàí êâàíòîâî¿ ñèñ-
òåìè àáî çíà÷íî éîãî ñïîòâîðèòè, òà ïîìèëêè, ùî âèíèêàþòü ï³ä ÷àñ âèì³ðþâàíü
³ âèêîíàííÿ åëåìåíòàðíèõ ïåðåòâîðåíü.
Ìîëîäà êàíàäñüêà êîìïàí³ÿ D-Wave (https://www.dwavesys.com/) ùå
â 2007 ð. çàÿâèëà ïðî ñòâîðåííÿ 16-êóá³òíîãî êâàíòîâîãî êîìï’þòåðà. Êîìï’þòåð
ì³ã ðîçâ’ÿçóâàòè ïàçëè ñóäîêó òà ³íø³ çàäà÷³ ïîøóêó çà øàáëîíîì. Äîñë³äíèêè
ñòâåðäæóâàëè, ùî âîíè çìîæóòü ñòâîðèòè ïðàêòè÷í³ ñèñòåìè äî 2008 ð. Ñêåïòè-
êè â³äðàçó çàïåðå÷èëè, ùî äî ñòâîðåííÿ ïðàêòè÷íèõ êâàíòîâèõ êîìï’þòåð³â ìàº
ìèíóòè ùå ê³ëüêà äåñÿòèë³òü.
Íàïðèê³íö³ 2007 ð. áóëî ïîâ³äîìëåíî ïðî êâàíòîâèé ïðîöåñîð Orion íà 28
êóá³òàõ. Âæå 11 òðàâíÿ 2011 ðîêó áóëî àíîíñîâàíî íîâèé ïðîöåñîð One, ÿêèé áóâ
íàçâàíèé «ïåðøèì êîìåðö³éíèì êâàíòîâèì êîìï’þòåðîì» ³ ïðàöþâàâ íà
128-êóá³òíîìó ÷³ïñåò³. Ó 2012 ð. â ðîáîò³ [15] ñòâåðäæóâàëîñÿ, ùî êîìïàí³ÿ
D-Wave Systems ïîáóäóâàëà êâàíòîâèé ïðèñòð³é, ÿêèé îïåðóº 84 êóá³òàìè. Òîãî
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1 23
ñàìîãî ðîêó áóâ àíîíñîâàíèé êâàíòîâèé êîìï’þòåð Vesuvius (àáî D-Wave Two) ç
512 êóá³òàìè, à 20 ñåðïíÿ 2015 ðîêó áóëî ñòâîðåíî âåðñ³þ D-Wave 2X ç 1152
êóá³òàìè.
24 ñ³÷íÿ 2017 ðîêó êîìïàí³ÿ D-Wave Systems Inc. îïóáë³êóâàëà çâ³ò, çã³äíî ç
ÿêèì êîìïàí³ÿ, ùî çàéìàºòüñÿ ê³áåðçàõèñòîì äåðæàâíèõ òà êîìåðö³éíèõ
îðãàí³çàö³é Temporal Defense Systems Inc. (TDS, http://temporaldefense.com), ñòàëà
ïåðøèì ïîêóïöåì ìàéáóòíüîãî íîâîãî ïðèñòðîþ D-Wave 2000Q, ÿêèé êîøòóº 15
ì³ëüéîí³â äîëàð³â òà îïåðóº 2000 êóá³òàìè.
Ïîïðè íàâåäåí³ íåïðÿì³ äîêàçè ³ñíóâàííÿ ïåðåïëóòàíîñò³ â ïðîöåñ³ îá÷èñ-
ëåííÿ ïðèñòðîþ D-Wave â äåÿêèõ ðîáîòàõ, á³ëüø³ñòü äîñë³äíèê³â íå âèçíàþòü
ïðèñòð³é D-Wave êâàíòîâèì. Õî÷à ïîêàçàíî, ùî äåÿê³ â³äîì³ êâàíòîâ³ àëãîðèòìè,
òàê³ ÿê àëãîðèòìè Ñàéìîíà òà Áåðíøòåéíà-Âàç³ðàí³, ìîæíà âèêîðèñòîâóâàòè â
àä³àáàòè÷í³é êâàíòîâ³é ìîäåë³, ïðîòå íåìຠæîäíèõ ïîâ³äîìëåíü ïðî ñïðîáè çðî-
áèòè öå íà ïðèñòðîÿõ D-Wave. Á³ëüø òîãî, çàçíà÷åíà âèùå êîìïàí³ÿ íàãîëîøóâà-
ëà íà òîìó, ùî àëãîðèòìè Ãðîâåðà òà Øîðà íå ìîæíà ðåàë³çóâàòè íà ïðèñòðîÿõ
D-Wave.
Ó 2015 ð. äîñë³äíèêè êîìïàí³¿ Google çàÿâèëè (áåç ïðÿìèõ äîêàç³â), ùî
çã³äíî ç ¿õí³ìè äîñë³äæåííÿìè ïðèñòð³é D-Wave âèêîðèñòîâóº êâàíòîâ³ åôåêòè,
îäíàê ïðè öüîìó â òàê çâàíîìó «1000-êóá³òíîìó» êîìï’þòåð³ êóá³òè íàñïðàâä³
ç³áðàíî â êëàñòåðè ïî 8 êóá³ò³â êîæíèé. Ó ðîáîò³ [16] ïðîàíàë³çîâàíî âñþ äîñ-
òóïíó ³íôîðìàö³þ ïðî ïðèñòðî¿ D-Wave, âíàñë³äîê ÷îãî çðîáëåíî âèñíîâîê, ùî
ïðèñòðî¿ D-Wave íå äàþòü æîäíî¿ îá÷èñëþâàëüíî¿ ïåðåâàãè íàä êëàñè÷íèì
êîìï’þòåðîì.
Ó 2001 ð. â÷åí³ ç êîìïàí³¿ IBM çàÿâèëè ïðî óñï³øíå âèïðîáóâàííÿ êâàíòîâî-
ãî êîìï’þòåðà ºìí³ñòþ 7 êóá³ò³â (3 êóá³òè â ïåðøîìó ðåã³ñòð³ ³ 4 êóá³òè â äðóãî-
ìó ðåã³ñòð³), ðåàë³çîâàíîãî íà îñíîâ³ ÿâèùà ÿäåðíîãî ìàãí³òíîãî ðåçîíàíñó.
Íèìè áóëî âèêîíàíî ôàêòîðèçàö³þ ÷èñëà 15 çà äîïîìîãîþ àëãîðèòìó Øîðà.
Ó 2007 ð. ãðóïà â÷åíèõ óí³âåðñèòåòó Êâ³íñëåíäà ïîâ³äîìèëà ïðî åêñïåðè-
ìåíòàëüíó äåìîíñòðàö³þ âèêîíàííÿ àëãîðèòìó Øîðà ç âèêîðèñòàííÿì êâàíòîâèõ
ëîã³÷íèõ âåíòèë³â íà îñíîâ³ ïîëÿðèçàö³¿ ôîòîí³â. Äëÿ äåìîíñòðàö³¿ áóëî ôàêòî-
ðèçîâàíî òàêîæ ÷èñëî 15 çà äîïîìîãîþ 7 êóá³ò³â (3 êóá³òè â ïåðøîìó ðåã³ñòð³ ³ 4
êóá³òè â äðóãîìó ðåã³ñòð³).
Òîãî ñàìîãî 2007 ð. â÷åí³ Óí³âåðñèòåòó íàóêè ³ òåõíîëîã³é Êèòàþ òàêîæ
ïîâ³äîìèëè ïðî åêñïåðèìåíòàëüíó äåìîíñòðàö³þ ðåàë³çàö³¿ àëãîðèòìó Øîðà
ç âèêîðèñòàííÿì êâàíòîâèõ ëîã³÷íèõ âåíòèë³â íà îñíîâ³ ôîòîí³â. Âîíè òàê ñàìî
ôàêòîðèçóâàëè ÷èñëî 15 ç âèêîðèñòàííÿì ëèøå 6 êóá³ò³â (2 êóá³òè â ïåðøîìó
ðåã³ñòð³ ³ 4 êóá³òè â äðóãîìó ðåã³ñòð³).
Ó 2009 ð. îïèñàíî óñï³øíó åêñïåðèìåíòàëüíó äåìîíñòðàö³þ àëãîðèòìó
Øîðà ç âèêîðèñòàííÿì ³íòåãðîâàíîãî õâèëüîâîäó íà îñíîâ³ êðåìí³ºâîãî ÷³ïà. ×î-
òèðè êóá³òè íà îñíîâ³ ôîòîí³â áóëî âèêîðèñòàíî äëÿ ôàêòîðèçàö³¿ ÷èñëà 15:
1 êóá³ò ó ïåðøîìó ðåã³ñòð³ ³ 3 êóá³òè â äðóãîìó ðåã³ñòð³.
Ó 2012 ð. ãðóïà äîñë³äíèê³â óí³âåðñèòåòó Êàë³ôîðí³¿ ïîâ³äîìèëà ïðî íîâó
åêñïåðèìåíòàëüíó äåìîíñòðàö³þ àëãîðèòìó Øîðà ç âèêîðèñòàííÿì ôàçîâèõ
êóá³ò³â òà íàäïðîâ³äíèõ õâèëüîâèõ ðåçîíàòîð³â. Öÿ ãðóïà òàêîæ ðîçêëàëà íà
ìíîæíèêè ÷èñëî 15 ç âèêîðèñòàííÿì 4 êóá³ò³â: 2 êóá³òè â ïåðøîìó ðåã³ñòð³
³ 2 êóá³òè â äðóãîìó ðåã³ñòð³.
Òàêîæ ó 2012 ð. â ðîáîò³ Å. Ìàðò³íà-Ëîïåçà òà ³í. áóëî ïðåäñòàâëåíî åêñïå-
ðèìåíòàëüíó äåìîíñòðàö³þ àëãîðèòìó Øîðà äëÿ ôàêòîðèçàö³¿ ÷èñëà 21 ç âèêî-
ðèñòàííÿì ëèøå äâîõ êóá³ò³â íà îñíîâ³ ôîòîí³â.
Ó 2012 ð. ïðîâåäåíî åêñïåðèìåíòàëüíó äåìîíñòðàö³þ êâàíòîâîãî àëãîðèòìó ôàê-
òîðèçàö³¿ ö³ëèõ ÷èñåë íà îñíîâ³ ÿäåðíîãî ìàãí³òíîãî ðåçîíàíñó äëÿ ôàêòîðèçàö³¿ ÷èñëà
143 ç âèêîðèñòàííÿì 4 êóá³ò³â ³ àä³àáàòè÷íîãî ï³äõîäó. Îñíîâíîþ â³äì³íí³ñòþ ö³º¿ ðî-
áîòè º ðåàë³çàö³ÿ íå àëãîðèòìó Øîðà, à éîãî àëüòåðíàòèâè — ïåðåòâîðåííÿ çàäà÷³
ôàêòîðèçàö³¿ ö³ëèõ ÷èñåë íà çàäà÷ó îïòèì³çàö³¿. Öþ ³äåþ âïåðøå áóëî ïðåäñòàâëåíî
Ê. Áóðãåñîì ó 2001 ð. òà óäîñêîíàëåíî â 2010 ð. Øåëëåðîì òà Øóòöõîëüäîì.
24 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1
Ó 2015 ð. ãðóïà äîñë³äíèê³â íà ÷îë³ ç Ò. Ìîíöåì ïîâ³äîìèëà ïðî íîâó åêñïå-
ðèìåíòàëüíó äåìîíñòðàö³þ àëãîðèòìó Øîðà ç âèêîðèñòàííÿì ³îííèõ ïàñòîê äëÿ
ðîçêëàäàííÿ ÷èñëà 15. Äëÿ öüîãî âèêîðèñòîâóâàëè ï’ÿòü 40Ca � ³îí³â ó ë³í³éí³é
ïàñòö³ Ïàóë³. Áóëî çàñòîñîâàíî ìàñøòàáîâàíó ñõåìó àëãîðèòìó Øîðà, àëå ç³
çìåíøåíîþ ê³ëüê³ñòþ êóá³ò³â — 1 êóá³ò â ïåðøîìó ðåã³ñòð³ ³ 4 êóá³òè â äðóãîìó
ðåã³ñòð³.
Ó çàçíà÷åíèõ âèùå ðîáîòàõ îïèñàíî ðåàëüí³ åêñïåðèìåíòàëüí³ äåìîíñòðàö³¿
ðåàë³çàö³¿ àëãîðèòìó Øîðà, ïðè öüîìó ïîêàçîâîþ º ðîáîòà Í. Äàòòàí³ òà
Í. Áðàºíñà [17]. Ó ïåðø³é ðåäàêö³¿ âîíà ìàëà íàçâó «Êâàíòîâà ôàêòîðèçàö³ÿ ÷èñ-
ëà 44929 çà äîïîìîãîþ 4 êóá³ò³â» ³ ì³ñòèëà ³íôîðìàö³þ ïðî ðîçêëàä ÷èñåë 3599,
13081 òà 44929 çà äîïîìîãîþ êâàíòîâîãî àëãîðèòìó, ÿêèé âèêîðèñòîâóº 4 êóá³òè.
Òðåòÿ ðåäàêö³ÿ ðîáîòè [17] ìàëà íàçâó «Êâàíòîâà ôàêòîðèçàö³ÿ ÷èñëà 56153 çà
äîïîìîãîþ 4 êóá³ò³â» ³ ì³ñòèëà ³íôîðìàö³þ ïðî ðîçêëàäàííÿ íà ìíîæíèêè âæå
á³ëüøîãî ÷èñëà — 56153 òà, íà äîäàòîê, ÷èñëà 11663. Ö³ ðåçóëüòàòè ìîæíà ââà-
æàòè ñâîºð³äíèì ðåêîðäîì, îñê³ëüêè ó ïîïåðåäí³õ ðîáîòàõ áóëî îïèñàíî ôàêòî-
ðèçàö³þ íàáàãàòî ìåíøèõ ÷èñåë. Îñîáëèâ³ñòü ö³º¿ ðîáîòè ïîëÿãຠâ òîìó, ùî àâ-
òîðè íå ïðîâåëè æîäíèõ íîâèõ åêñïåðèìåíò³â, à ëèøå ñêîðèñòàëèñÿ ïîïåðåäí³ìè
åêñïåðèìåíòàëüíèìè ðåçóëüòàòàìè ³ ïîêàçàëè, ùî ìîæíà ðîçêëàñòè íà ìíîæíèêè
ïåâíèé êëàñ ö³ëèõ ÷èñåë çà äîïîìîãîþ äîäàòêîâèõ îá÷èñëåíü ó ðàìêàõ êëàñè÷íî¿
ìîäåë³ îá÷èñëåíü.
 îðèã³íàëüí³é âåðñ³¿ êâàíòîâîãî àëãîðèòìó Øîðà ôàêòîðèçàö³¿ ö³ëèõ ÷èñåë
äëÿ ðîçêëàäàííÿ ÷èñëà N , ùî ôàêòè÷íî îçíà÷ຠïîøóê ïåð³îäó ôóíêö³¿
f x a Nx( ) � mod , x Z N� , äëÿ äåÿêîãî çíà÷åííÿ a Z N� * (òîáòî ïîøóê ìóëü-
òèïë³êàòèâíîãî ïîðÿäêó åëåìåíòà a Z N� * ), ïåðøèé ðåã³ñòð ïîâèíåí ìàòè ðîçì³ð
2 log N êóá³ò³â (äëÿ îá÷èñëåííÿ êâàíòîâîãî ïåðåòâîðåííÿ Ôóð’º òà çàáåçïå÷åííÿ
îáìåæåíî¿ ïîìèëêè ó âèïàäêó âèêîðèñòàííÿ â³äïîâ³äíèõ äðîá³â), à äðóãèé
ðåã³ñòð — ðîçì³ð log N êóá³ò³â, äîñòàòí³é äëÿ çíà÷åíü ôóíêö³¿. Òàêèì ÷èíîì, çà-
ãàëüíà ê³ëüê³ñòü íåîáõ³äíèõ êóá³ò³â äîð³âíþº 3 log N . Ó ñâî¿õ äîñë³äæåííÿõ
Ê. Çàëêà ïîêàçàâ, ùî ìîæíà çìåíøèòè ê³ëüê³ñòü íåîáõ³äíèõ êóá³ò³â äî
2
3
2
� log N . ϳçí³øå öþ ³äåþ áóëî ï³äòâåðäæåíî, ³ ôàêòè÷íî â ïåðøîìó ðåã³ñòð³ âè-
êîðèñòîâóºòüñÿ ëèøå îäèí êóá³ò ³ òàê çâàíå íàï³âêëàñè÷íå ïåðåòâîðåííÿ Ôóð’º.
Îñê³ëüêè óìîâîþ äîñÿãíåííÿ òàêîãî çìåíøåííÿ íåîáõ³äíèõ ðåñóðñ³â º íåîäíîðàçîâå
âèêîðèñòàííÿ òà ïîâòîðíà ³í³ö³àë³çàö³ÿ îäíîãî êóá³òà íóëüîâèì çíà÷åííÿì ó ìåæàõ
îäíîãî ïðîõîäæåííÿ ñõåìè êâàíòîâîãî àëãîðèòìó, öåé ìåòîä íàçâàëè ìåòîäîì ïî-
âòîðíîãî âèêîðèñòàííÿ êóá³òà (àíãë. qubit recycling). Éîãî çàñòîñîâóþòü ìàéæå ó
âñ³õ çàçíà÷åíèõ âèùå åêñïåðèìåíòàëüíèõ äåìîíñòðàö³ÿõ âèêîíàííÿ àëãîðèòìó
Øîðà.
Á³ëüø òîãî, â óñ³õ íàâåäåíèõ ðîáîòàõ âèêîðèñòàíî â³äîìîñò³ ïðî øóêàíèé
ðåçóëüòàò áåçïîñåðåäíüî ï³ä ÷àñ éîãî îá÷èñëåííÿ, îñê³ëüêè ðîçêëàä íåâåëèêèõ
÷èñåë ³ òàê º â³äîìèì. ²ñíóþòü äåÿê³ ÷èñëà, ìóëüòèïë³êàòèâíèé ïîðÿäîê ÿêèõ º
íåâåëèêèì, àëå éîãî çíà÷åííÿ äຠçìîãó îòðèìàòè áàæàíèé ðîçêëàä âõ³äíîãî
ö³ëîãî ÷èñëà. Òîìó ê³ëüê³ñòü íåîáõ³äíèõ êóá³ò³â çíà÷íî ñêîðîòèòüñÿ, ÿêùî âèêî-
íàòè ïåâí³ îá÷èñëåííÿ çàçäàëåã³äü çà äîïîìîãîþ êëàñè÷íî¿ ìîäåë³. Òàêó âåðñ³þ
àëãîðèòìó Øîðà íàçèâàþòü êîìïîíîâàíèì (àíãë. compiled) àëãîðèòìîì Øîðà.
Ñàìå âîíà âèêîðèñòîâóºòüñÿ â á³ëüøîñò³ ïðàêòè÷íèõ ðåàë³çàö³é. Äî òîãî æ, ÷èñëî
15 ìຠïåâíó îñîáëèâ³ñòü — âñ³ åëåìåíòè ìóëüòèïë³êàòèâíî¿ ãðóïè ê³ëüöÿ
ëèøê³â Z15 ìàþòü ìóëüòèïë³êàòèâíèé ïîðÿäîê, ùî äîð³âíþº 2 àáî 4, òîáòî ñòå-
ïåíÿ 2. Öå îçíà÷àº, ùî íåìຠïîòðåáè ó âèêîðèñòàíí³ â³äïîâ³äíèõ äðîá³â òà äî-
äàòêîâèõ êóá³ò³â, íàâ³òü ó ðàç³ çàñòîñóâàííÿ îðèã³íàëüíî¿ âåðñ³¿ àëãîðèòìó Øîðà.
Ìîæíà òàêîæ âèêîðèñòàòè ÷èñëî 11, ÿêå â³äïîâ³äຠïîêàçíèêó 2 ³ äຠçìîãó ðîç-
êëàñòè ÷èñëî 15, ùî áóëî çðîáëåíî â äåÿêèõ åêñïåðèìåíòàõ.
Íåùîäàâíî Æ. Æó òà Ì. Ãåëëåð ïîêàçàëè, ÿê ìîæíà ðîçêëàñòè ÷èñëà 51 ³ 85
ç âèêîðèñòàííÿì ëèøå 8 êóá³ò³â (áåç ïðîâåäåííÿ åêñïåðèìåíòó). ßê ³ ÷èñëî 15,
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1 25
÷èñëà 51 ³ 85 º äîáóòêîì äâîõ ïðîñòèõ ÷èñåë Ôåðìà (âèäó 2 12k
� ). Áóëî ïîêàçàíî,
ó ÿêèé ñïîñ³á ìîæíà çíàéòè ÷èñëà, ùî ìàþòü íåâåëèêèé ìóëüòèïë³êàòèâíèé ïî-
ðÿäîê çà ìîäóëåì äîáóòêó ïðîñòèõ ÷èñåë Ôåðìà.
Äæ. Ñìîë³í òà ³íø³ ðîçâèíóëè öþ ³äåþ òà äîâåëè, ùî äëÿ äîâ³ëüíîãî ñêëàäå-
íîãî ÷èñëà pq, äå p ³ q — ïðîñò³ ÷èñëà, ³ñíóº ÷èñëî a, ÿêå íàëåæèòü ïîêàçíèêó 2
çà ìîäóëåì pq, ³ äຠçìîãó ðîçêëàñòè ÷èñëî pq íà ìíîæíèêè.
Ç òî÷êó çîðó äåìîíñòðàö³¿ ìîæëèâîñòåé ñó÷àñíèõ åêñïåðèìåíòàëüíèõ êâàí-
òîâèõ îá÷èñëþâàëüíèõ ïðèñòðî¿â ñë³ä ïðèïèíèòè âèêîðèñòàííÿ êîìïîíîâàíèõ
âåðñ³é àëãîðèòì³â ³, íàïðèêëàä, çàì³ñòü äåìîíñòðàö³¿ àëãîðèòìó Øîðà çîñåðåäè-
òèñÿ íà éîãî îñíîâí³é êâàíòîâ³é ÷àñòèí³ — ïîøóêó ïåð³îäó ïåð³îäè÷íî¿ ôóíêö³¿.
²íøèìè ñëîâàìè, ðåçóëüòàòîì ðåàë³çàö³¿ àëãîðèòìó ìຠáóòè çíàõîäæåííÿ
ïåð³îäó äîâ³ëüíî¿ ôóíêö³¿ ç îáìåæåííÿì ùîäî ðîçì³ð³â îáëàñò³ âèçíà÷åííÿ òà
çíà÷åíü. Ç îãëÿäó íà äàí³ ùîäî ê³ëüêîñò³ âèêîðèñòîâóâàíèõ êóá³ò³â, íàâåäåí³
ó â³äîìèõ ðîáîòàõ, ìîæíà ä³éòè âèñíîâêó, ùî ïðîòÿãîì îñòàíí³õ 15–20 ðîê³â íå
â³äáóëîñÿ ìàéæå æîäíèõ çì³í â îá÷èñëþâàëüíèõ ìîæëèâîñòÿõ â³äïîâ³äíèõ åê-
ñïåðèìåíò³â. Òàê, â³äáóëèñÿ çì³íè â ìåòîäàõ ³ òåõíîëîã³ÿõ, ÿê³ äàëè çìîãó ïîêðà-
ùèòè êîíòðîëü òà çîâí³øí³ óìîâè, à íå â ìîæëèâîñòÿõ äëÿ çíàõîäæåííÿ ïåð³îäó
ïåð³îäè÷íî¿ ôóíêö³¿ ç á³ëüøîþ îáëàñòþ âèçíà÷åííÿ.
Ó 2016 ð. êîìïàí³ÿ IBM çàÿâèëà ïðî ñòâîðåííÿ êâàíòîâîãî êîìï’þòåðà
ºìí³ñòþ 5 êóá³ò³â, îäèí ç ÿêèõ âèêîðèñòîâóºòüñÿ äëÿ êîðåêö³¿ ïîìèëîê. Öåé îá-
÷èñëþâàëüíèé ïðèñòð³é áàçóºòüñÿ íà ï’ÿòèêóá³òíîìó íàäïðîâ³äíîìó ÷³ï³ ç ãåî-
ìåòð³ºþ ç³ðêè òà ðåàë³çàö³ºþ ïîâíî¿ àëãåáðè Êë³ôîðäà. Â³í º ïðîãðàìîâàíèì
³ äຠçìîãó ñòâîðþâàòè âåíòèë³ òà ìîäåëþâàòè ¿õ ðîáîòó.
Ó òðàâí³ 2017 ðîêó êîìïàí³ÿ IBM çàÿâèëà ïðî ðåàë³çàö³þ êâàíòîâèõ îá÷èñ-
ëþâàëüíèõ ïðèñòðî¿â ç 16 ³ 17 êóá³òàìè, à â ëèñòîïàä³ 2017 ðîêó IBM àíîíñóâàëà
50-êóá³òíèé êâàíòîâèé îá÷èñëþâàëüíèé ïðèñòð³é (äëÿ îá÷èñëåíü âèêîðèñòîâó-
þòüñÿ ëèøå 20 êóá³ò³â, à ðåøòà ñëóãóº äëÿ êîðåêö³¿ ïîìèëîê). Ó íüîìó êîæíèé
êóá³ò ìîæå ïåðåáóâàòè â êîãåðåíòíîìó ñòàí³ äî 90 ì³êðîñåêóíä, à öå îçíà÷àº, ùî
÷àñ äëÿ âñ³õ îïåðàö³é íå ìîæå ïåðåâèùóâàòè öüîãî çíà÷åííÿ. Îäíàê, òðåáà çàçíà-
÷èòè, ùî 50-êóá³òíèé êâàíòîâèé îá÷èñëþâàëüíèé ïðèñòð³é IBM º äîñòàòíüî
åíåðãîåôåêòèâíèì — â³í ñïîæèâຠâ³ä 10 äî 15 êÂò, ùî ïðèáëèçíî äîð³âíþº
ñïîæèâàííþ åíåð㳿 10 òèïîâèõ ñåð³éíèõ ì³êðîõâèëüîâèõ ïå÷åé (áåç óðàõóâàííÿ
åíåð㳿, ïîòð³áíî¿ äëÿ îõîëîäæåííÿ ïðèñòðîþ ïåðåä ðîáîòîþ, ÿêå çä³éñíþºòüñÿ
ïðîòÿãîì 36 ãîäèí).
Ïðîãðàìà Quantum Experience äຠçìîãó îòðèìàòè â³ääàëåíèé äîñòóï äî öüî-
ãî îá÷èñëþâàëüíîãî ïðèñòðîþ, ìîäåëþâàòè òà çàïóñêàòè ð³çí³ àëãîðèòìè, âêëþ-
÷àþ÷è àëãîðèòì Øîðà, ç âèêîðèñòàííÿì êëàñè÷íî¿ ìåðåæ³ ²íòåðíåò äëÿ ç’ºäíàí-
íÿ ç õìàðîþ IBM. Íà ñüîãîäí³ ïðîãðàìà Quantum Experience çàáåçïå÷óº äîñòóï
äî äâîõ 5-êóá³òíèõ ïðèñòðî¿â òà îäíîãî 16-êóá³òíîãî ïðèñòðîþ ³ ìຠáëèçüêî 75
òèñÿ÷ êîðèñòóâà÷³â, ÿê³ çàïóñòèëè áëèçüêî äâîõ ç ïîëîâèíîþ ì³ëüéîí³â åêñïåðè-
ìåíò³â. Çäåá³ëüøîãî öå íàóêîâö³, ÿê³ çà ðåçóëüòàòàìè ìîäåëþâàííÿ îïóáë³êóâàëè
äåê³ëüêà äåñÿòê³â ðîá³ò.
Ó ñ³÷í³ 2018 ðîêó êîìïàí³ÿ Intel òàêîæ ïðèºäíàëàñÿ äî ãîíêè êâàíòîâèõ îá-
÷èñëþâàëüíèõ ïðèñòðî¿â ³ îãîëîñèëà ïðî ñòâîðåííÿ íàäïðîâ³äíîãî êâàíòîâîãî
÷èïó ç íàçâîþ Tangle Lake, ÿêèé ì³ñòèòü 49 êóá³ò³â.
5 áåðåçíÿ 2018 ðîêó ñï³âðîá³òíèêè êîìïàí³¿ Google ïðåäñòàâèëè íîâèé êâàí-
òîâèé ïðîöåñîð ï³ä íàçâîþ Bristlecone ºìí³ñòþ 72 êóá³òè, ïîáóäîâàíèé íà îñíîâ³
9-êóá³òíîãî êâàíòîâîãî ïðèñòðîþ, ïðåäñòàâëåíîãî êîìïàí³ºþ ê³ëüêà ðîê³â òîìó.
Ïî÷àòêîâèé 9-êóá³òíèé êâàíòîâèé ïðèñòð³é ïåðåäáà÷àâ âèêîðèñòàííÿ êóá³ò³â,
îá’ºäíàíèõ ó ë³í³éíèé ìàñèâ. Äëÿ íüîãî âäàëîñÿ äîñÿãòè äîñèòü íèçüêîãî ð³âíÿ
ïîìèëîê — ÷àñòêà ïîìèëîê áóëà íà ð³âí³ 1% äëÿ ç÷èòóâàííÿ äàíèõ, 0,1% äëÿ îä-
íîêóá³òíèõ êâàíòîâèõ âåíòèë³â ³ 0,6% äëÿ äâîêóá³òíèõ êâàíòîâèõ âåíòèë³â. Ó íî-
26 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1
âîìó êâàíòîâîìó ïðèñòðî¿ âèêîðèñòîâóþòüñÿ äâîì³ðí³ ñòðóêòóðè. Êóá³òè óòâî-
ðþþòü äâà êâàäðàòíèõ ìàñèâè 6 íà 6, ðîçòàøîâàí³ îäèí íàä îäíèì, çàâäÿêè ÷îìó
ñèñòåìà ìîæå â³äñòåæóâàòè òà âèïðàâëÿòè ïîìèëêè ï³ä ÷àñ îá÷èñëåíü. Íà ìî-
ìåíò àíîíñó äåòàëüí³ õàðàêòåðèñòèêè íîâîãî ïðèñòðîþ íå áóëè ðîçêðèò³, àëå
äîñë³äíèêè ñïîä³âàþòüñÿ, ùî â³í äåìîíñòðóâàòèìå ïðèáëèçíî òàêèé ñàìèé
ð³âåíü ïîìèëîê ÿê ³ éîãî ïîïåðåäíèê. Á³ëüø òîãî, âîíè ìàþòü îïòèì³ñòè÷íó
íàä³þ äîñÿãòè òàê çâàíî¿ êâàíòîâî¿ ïåðåâàãè.
ϳä òåðì³íîì «êâàíòîâà ïåðåâàãà» ðîçóì³þòü äåìîíñòðàö³þ òîãî, ùî êâàíòî-
âèé îá÷èñëþâàëüíèé ïðèñòð³é ðîçâ’ÿæå ïåâíó îá÷èñëþâàëüíó çàäà÷ó (ìîæëèâî,
ñïåö³àëüíî ñòâîðåíó äëÿ òàêî¿ ìåòè) øâèäøå, í³æ áóäü-ÿêèé êëàñè÷íèé ñó÷àñíèé
ñóïåðêîìï’þòåð (àáî âñ³ ñó÷àñí³ ñóïåðêîìï’þòåðè ðàçîì). Äîñÿãíåííÿ öüîãî
ð³âíÿ ôàêòè÷íî îçíà÷àòèìå ïî÷àòîê åðè êâàíòîâèõ ïðèñòðî¿â òà êâàíòîâî¿ ìîäåë³
îá÷èñëåíü. Á³ëüø³ñòü â÷åíèõ ñïîä³âàþòüñÿ, ùî çà òåïåð³øíüîãî ð³âíÿ ïîìèëîê öå
ñòàíåòüñÿ òîä³, êîëè êâàíòîâ³ ïðèñòðî¿ îïåðóâàòèìóòü 100 òà á³ëüøå êóá³òàìè.
Îäíàê, ðåçóëüòàòè îá÷èñëåíü, âèêîíàíèõ ñïåö³àë³ñòàìè êîìïàí³¿ Google, ñâ³ä÷àòü
ïðî òå, ùî äëÿ öüîãî äîñòàòíüî 49 êóá³ò³â, ÿêùî ÷èñëî âåíòèë³â áóäå ïåðåâèùó-
âàòè ÷èñëî 40, à ïîìèëêà äâîêóá³òíèõ êâàíòîâèõ âåíòèë³â áóäå ìåíøîþ, í³æ
0,5%. Ïîäàëüø³ äîñë³äæåííÿ öüîãî ïðèñòðîþ äàäóòü çìîãó á³ëüø òî÷íî îá÷èñëè-
òè ð³âåíü â³äïîâ³äíèõ ïîìèëîê òà ïðîàíàë³çóâàòè éîãî ìîæëèâîñò³.
Êâàíòîâ³ îá÷èñëþâàëüí³ ïðèñòðî¿ êîìïàí³é IBM, Google òà Intel íà âèãëÿä º
óí³âåðñàëüíèìè ïðèñòðîÿìè ç ðåàëüíèìè õàðàêòåðèñòèêàìè. Îäíàê, ê³ëüê³ñòü
êóá³ò³â, äîñòóïíèõ äëÿ âèêîðèñòàííÿ, çàçâè÷àé º ñóòòºâî ìåíøîþ çàÿâëåíî¿
ê³ëüêîñò³ ÷åðåç ïîòðåáó â äîäàòêîâèõ îïåðàö³ÿõ äëÿ êîðåêö³¿ ïîìèëîê. Òîìó
ñòâåðäæóâàòè ïðî äîñÿãíåííÿ êâàíòîâî¿ ïåðåâàãè ùå çàðàíî, îñê³ëüêè íà ñüî-
ãîäí³ íàâ³òü çâè÷àéíèé íîóòáóê ìîæå çìîäåëþâàòè ðîáîòó 30–40 êóá³ò³â çà äîïî-
ìîãîþ ïðîãðàìíèõ çàñîá³â. Íàïðèêëàä, äîñòóïí³ äëÿ îá÷èñëåíü 20 êóá³ò³â äàþòü
çìîãó çíàéòè ïåð³îäè òàêèõ ïåð³îäè÷íèõ ôóíêö³é, ùî ó âèïàäêó ðåàë³çàö³¿ çâè-
÷àéíîãî àëãîðèòìà Øîðà ìîæíà ãàðàíòîâàíî çä³éñíèòè óñï³øíå ðîçêëàäàííÿ íà
ìíîæíèêè ìàêñèìóì äëÿ ÷èñëà 89. Öå ãîâîðèòü ïðî òå, ùî íàðàç³ â³äáóâàºòüñÿ
íàêîïè÷åííÿ åêñïåðèìåíò³â, òåõíîëîã³é òà äîñâ³äó ³ íà ïðèñòðîÿõ ç òàêîþ
ê³ëüê³ñòþ êóá³ò³â ñòàâèòè ðåêîðäè ùå çàðàíî, àëå çàãàëüíà çàäà÷à ïîøóêó
ïåð³îäó ïåð³îäè÷íî¿ ôóíêö³¿ ìîæå ñòàòè åôåêòèâíèì ì³ðèëîì ïîòóæíîñò³
³ «êâàíòîâîñò³» ìàéáóòí³õ îá÷èñëþâàëüíèõ ïðèñòðî¿â.
ÂÈÑÍÎÂÊÈ
Çðîáëåíî îãëÿä òà àíàë³ç îñíîâíèõ ïîíÿòü ³ ïîëîæåíü êâàíòîâî¿ ìîäåë³ îá÷èñ-
ëåíü, åôåêòèâíèõ êâàíòîâèõ àëãîðèòì³â, îñòàíí³õ ðåçóëüòàò³â, ìîæëèâîñòåé òà
ïåðñïåêòèâ ó ãàëóç³ ïîáóäîâè ìàñøòàáîâàíîãî êâàíòîâîãî êîìï’þòåðà. Ðîçãëÿ-
íóòî ðåçóëüòàòè îñòàíí³õ äîñë³äæåíü ùîäî ðîçâ’ÿçàííÿ àëãåáðà¿÷íèõ çàäà÷
ó êâàíòîâ³é ìîäåë³ îá÷èñëåíü ³ ìîæëèâîãî çàñòîñóâàííÿ öèõ ðåçóëüòàò³â äëÿ
ïîáóäîâè íîâèõ òà àíàë³çó äàâíî â³äîìèõ êðèïòîãðàô³÷íèõ ïåðåòâîðåíü. Ç’ÿñî-
âàíî, ùî íà ñüîãîäí³ º ëèøå íåâåëèêà ê³ëüê³ñòü çàäà÷, äëÿ ÿêèõ ³ñíóþòü åôåê-
òèâí³ êâàíòîâ³ àëãîðèòìè, ùî áóäóòü ðîçâ’ÿçóâàòè ¿õ íà ïðàêòèö³ çà
ïîë³íîì³àëüíèé ÷àñ íà ïðîòèâàãó êëàñè÷íîìó êîìï’þòåðó. Äî êëàñó òàêèõ çà-
äà÷ íàëåæàòü çàäà÷³ ôàêòîðèçàö³¿ âåëèêèõ ÷èñåë òà äèñêðåòíîãî ëîãàðèôìó-
âàííÿ, íà ñêëàäíîñò³ ÿêèõ ´ðóíòóºòüñÿ ñò³éê³ñòü ïåðåâàæíî¿ á³ëüøîñò³ àëãî-
ðèòì³â ³ ïðîòîêîë³â àñèìåòðè÷íî¿ êðèïòîãðàô³¿. ²íøèìè ñëîâàìè, ï³ñëÿ ñòâî-
ðåííÿ ìàñøòàáîâàíîãî êâàíòîâîãî êîìï’þòåðà ö³ àëãîðèòìè ³ ïðîòîêîëè
áóäóòü çëàìàí³. Àëå íàâ³òü ÿêùî êîëî åôåêòèâíî ðîçâ’ÿçóâàíèõ çàäà÷ íå áóäå
ðîçøèðåíî, çàâäÿêè àëãîðèòìó Ãðîâåðà ñêëàäí³ñòü áóäü-ÿêî¿ çàäà÷³ íà êâàíòî-
âîìó êîìï’þòåð³ áóäå ó êâàäðàòíèé êîð³íü ðàç³â ìåíøà í³æ íà êëàñè÷íîìó
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1 27
êîìï’þòåð³. Òîä³ ìàñøòàáîâàí³ êâàíòîâ³ êîìï’þòåðè ìîæíà áóäå çàñòîñîâóâà-
òè äëÿ ðîçâ’ÿçàííÿ çàäà÷ ó ãàëóç³ åêîíîì³êè, ïëàíóâàííÿ, êîìá³íàòîðíî¿
îïòèì³çàö³¿ òîùî.
Îòðèìàí³ íà ñüîãîäí³ åêñïåðèìåíòàëüí³ ³ ïðàêòè÷í³ ðåçóëüòàòè ñâ³ä÷àòü ïðî
â³äñóòí³ñòü äîñòàòíüîãî ïðîãðåñó ó ïîáóäîâ³ ìàñøòàáîâàíîãî êâàíòîâîãî îá÷èñ-
ëþâàëüíîãî ïðèñòðîþ ç òî÷êè çîðó ðåàë³çàö³¿ â³äîìèõ êâàíòîâèõ àëãîðèòì³â. Äî-
ïîêè ïðàêòè÷í³ ðåàë³çàö³¿ êâàíòîâèõ ñèñòåì íå áóäóòü îïåðóâàòè á³ëüøîþ
ê³ëüê³ñòþ êóá³ò³â í³æ ê³ëüê³ñòü êóá³ò³â, ðîáîòà ÿêèõ ìîæå áóòè çìîäåëüîâàíà çà
ïðèéíÿòíèé ÷àñ íà êëàñè÷íîìó êîìï’þòåð³, âàæêî ñòâåðäæóâàòè ïðî ÿê³ñü ïåðåâà-
ãè òà ìåòîäè îö³íþâàííÿ. Ïðîòå á³ëüø³ñòü äîñë³äíèê³â î÷³êóþòü íà ñòâîðåííÿ
ïîâíîö³ííîãî êâàíòîâîãî êîìï’þòåðà, ÿêèé çìîæå, íàïðèêëàä, çëàìàòè
RSA-4096, âïðîäîâæ íàñòóïíèõ 10–15 ðîê³â, ùîïðàâäà, ç ³ìîâ³ðí³ñòþ ïðîãíîçó
0.5. Òîìó âæå çàðàç ïîòð³áíî ï³äãîòóâàòè â³äïîâ³äí³ âàð³àíòè çàì³íè äëÿ ïî-
ñòêâàíòîâèõ êðèïòîãðàô³÷íèõ ïåðåòâîðåíü òà ïðîòîêîë³â ç îö³íêîþ ñò³éêîñò³ òà
ñêëàäíîñò³ âïðîâàäæåííÿ, à òàêîæ äåòàëüíî ðîçðîáèòè ð³çí³ ìîäèô³êàö³¿ ïåðåòâî-
ðåíü ç óðàõóâàííÿì ìîæëèâîñòåé àëãîðèòìó Ãðîâåðà.
ÑÏÈÑÎÊ Ë²ÒÅÐÀÒÓÐÈ
1. Bennett C., Brassard G. Quantum cryptography: Public-key distribution and coin tossing. Proc.
International Conference on Computers, Systems and Signal Processing (Bangalore, India. 1984).
P. 175–179.
2. Êâàíòîâûé êîìïüþòåð è êâàíòîâûå âû÷èñëåíèÿ. Èæåâñê: Èæåâñêàÿ ðåñïóáëèêàíñêàÿ òèïîãðà-
ôèÿ, 1999. 288 ñ.
3. Ïðåñêèëë Äæ. Êâàíòîâàÿ èíôîðìàöèÿ è êâàíòîâûå âû÷èñëåíèÿ. Òîì 1. Ìîñêâà-Èæåâñê: ÍÈÖ
«Ðåãóëÿðíàÿ è õàîòè÷åñêàÿ äèíàìèêà»; Èíñòèòóò êîìïüþòåðíûõ èññëåäîâàíèé, 2008. 464 ñ.
4. Ààðîíñîí Ñ. Êâàíòîâûå âû÷èñëåíèÿ ñî âðåìåí Äåìîêðèòà. Ìîñêâà: Àëüïèíà íîí-ïèêøí,
2018. 494 ñ.
5. Ñàâ÷óê Ì.Í. Î ðàáîòàõ êèåâñêîé øêîëû òåîðåòè÷åñêîé êðèïòîãðàôèè. Êèáåðíåòèêà è ñèñ-
òåìíûé àíàëèç. 2010. Ò. 46, ¹ 3. Ñ. 52–68.
6. Nielsen M.A., Chuang I.L. Quantum computation and quantum information. Cambridge: Cambridge
University Press,. 2000. 676 p.
7. Kitaev A. Quantum computations: algorithms and error correction. Russian Mathematical Surveys.
1997. Vol. 52, N 6. P. 53–112.
8. Yao A. Quantum circuit complexity. Proc. 34th Annual Symposium on Foundations of Computer
Science. 1993. P. 352–361.
9. Boneh R., Lipton R. Quantum cryptanalysis of hidden linear functions. Proc. 15th Annual
International Cryptology Conference (Santa Barbara, California, USA, August 27, 1995). Advances
in Cryptology. Crypto’95. Lecture Notes in Computer Science. 1995. Vol. 31. P. 424–437.
10. Deutsch D., Jozsa R. Rapid solution of problems by quantum computation. Proc. Royal Society of
London, Series A. 1992. N 439. P. 553–558.
11. Shor P.W. Algorithms for quantum computation: discrete logs and factoring. Proc. 35th Symposium
on the Foundations of Computer Science (Santa Fe, NM, USA, 20–22 Nov., 1994), 1994.
P. 124–134.
12. Shor P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum
computer. SIAM Journal on Computing. 1997. Vol. 26, Iss. 5. P. 1484–1509.
13. van Dam W., Hallgren S., Ip L. Quantum algorithms for some hidden shift problems. SIAM Journal
on Computing. 2006. Vol. 36, N 3. P. 763–778.
14. Ôåñåíêî À.Â. Óÿçâèìîñòè êðèïòîïðèìèòèâîâ íà îñíîâå çàäà÷è ïîèñêà ñîïðÿãàþùåãî ýëåìåí-
òà è ñòåïåíè â êâàíòîâîé ìîäåëè âè÷èñëåíèé. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2014. Ò. 50,
¹ 5. Ñ. 184–186.
28 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1
15. Bian Z., Chudak F., Macready W., Clark L. , Gaitan F. Experimental determination of Ramsey
numbers. Physical Review Letters. 2012 Vol. 111, Iss. 13. P. 130505. DOI: https://doi.org/10.1103/
PhysRevLett.111.130505. URL: https://arxiv.org/abs/1201.1842.
16. Cho A. Quantum or not, controversial computer yields no speedup. Science. 2014. Vol. 344, N 6190.
P. 1330–1331. DOI: https://doi.org/10.1126/science.344.6190.1330.
17. Dattani N.S. , Bryans N. Quantum factorization of 56153 with only 4 qubits. Quantum Physics
Archive. arXiv:1411.6758 [quant-ph]. 2014. URL: https//arxiv.org/abs/1411.6758.
Íàä³éøëà äî ðåäàêö³¿ 20.09.2018
Ì.Í. Ñàâ÷óê, À.Â. Ôåñåíêî
ÊÂÀÍÒÎÂÛÅ ÂÛ×ÈÑËÅÍÈß: ÎÁÇÎÐ È ÀÍÀËÈÇ
Àííîòàöèÿ. Âûïîëíåí îáçîð è àíàëèç îñíîâíûõ ïîíÿòèé è ïîëîæåíèé
êâàíòîâîé ìîäåëè âû÷èñëåíèé, ýôôåêòèâíûõ êâàíòîâûõ àëãîðèòìîâ, ïî-
ñëåäíèõ ðåçóëüòàòîâ, âîçìîæíîñòåé è ïåðñïåêòèâ â ïîñòðîåíèè ìàñøòàáèðî-
âàííîãî êâàíòîâîãî êîìïüþòåðà. Ðàññìîòðåí íåêîòîðûé êëàññ àëãåáðàè÷åñ-
êèõ çàäà÷ â êâàíòîâîé ìîäåëè âû÷èñëåíèé, äëÿ êîòîðûõ ñóùåñòâóåò ýôôåê-
òèâíûé êâàíòîâûé àëãîðèòì ðåøåíèÿ. Ïðîâåäåí äåòàëüíûé àíàëèç
ñóùåñòâóþùèõ ïðàêòè÷åñêèõ ðåàëèçàöèé êâàíòîâîãî êîìïüþòåðà è ïîêàçà-
íî, ÷òî ïîêà ÷òî íåò äîñòàòî÷íîãî ïðîãðåññà â ïîñòðîåíèè ìàñøòàáèðîâàí-
íîãî êâàíòîâîãî âû÷èñëèòåëüíîãî óñòðîéñòâà, íî, òåì íå ìåíåå, áîëüøè-
íñòâî èññëåäîâàòåëåé îæèäàþò ñîçäàíèå ïîëíîöåííîãî êâàíòîâîãî êîìïüþ-
òåðà â òå÷åíèå ñëåäóþùèõ 10–15 ëåò.
Êëþ÷åâûå ñëîâà: êâàíòîâàÿ ìîäåëü âû÷èñëåíèé, êâàíòîâàÿ êðèïòîãðàôèÿ,
êâàíòîâûé êîìïüþòåð, ýôôåêòèâíûå êâàíòîâûå àëãîðèòìû, ïîñòêâàíòîâûå
êðèïòîãðàôè÷åñêèå ïðèìèòèâû.
M.M. Savchuk, A.V. Fesenko
QUANTUM COMPUTING: SURVEY AND ANALYSIS
Abstract. The authors conduct a survey and analysis of the main concepts and
postulates of the quantum computing model, efficient quantum algorithms, recent
results, capabilities, and prospects in constructing a scalable quantum computer.
A certain class of algebraic problems in a quantum computation model is
considered, for which there and efficient quantum solution algorithm exists.
A detailed analysis of available quantum computer implementations has been
carried out and it has been shown that sufficient progress has yet been made in
constructing a scalable quantum computing device; nevertheless, most of
researchers expect a quantum computer to be created in the next 10–15 years.
Keywords: quantum computing model, quantum cryptography, quantum
computer, efficient quantum algorithms, postquantum cryptographic primitives.
Ñàâ÷óê Ìèõàéëî Ìèêîëàéîâè÷,
÷ë.-êîð. ÍÀÍ Óêðà¿íè, äîêòîð ô³ç.-ìàò. íàóê, â.î. çàâ³äóâà÷à êàôåäðè Íàö³îíàëüíîãî òåõí³÷íîãî
óí³âåðñèòåòó Óêðà¿íè «Êè¿âñüêèé ïîë³òåõí³÷íèé ³íñòèòóò ³ìåí³ ²ãîðÿ ѳêîðñüêîãî»,
e-mail: mikhail.savchuk@gmail.com.
Ôåñåíêî Àíäð³é Â’ÿ÷åñëàâîâè÷,
êàíäèäàò ô³ç.-ìàò. íàóê, ñòàðøèé âèêëàäà÷ Íàö³îíàëüíîãî òåõí³÷íîãî óí³âåðñèòåòó Óêðà¿íè
«Êè¿âñüêèé ïîë³òåõí³÷íèé ³íñòèòóò ³ìåí³ ²ãîðÿ ѳêîðñüêîãî», e-mail: andrey.fesenko@gmail.com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 1 29
|