2023, випуск 1, c. 13-22
Одержано 17.02.2023; Виправлено 18.03.2023; Прийнято 25.04.2023
Надруковано 28.04.2023; Вперше Online 23.05.2023
https://doi.org/10.34229/2707-451X.23.1.2
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Дослідження впливу параметрів квантового відпалу на якість розв’язку задачі факторизації чисел
В.Ю. Корольов 
, О.М. Ходзінський *
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Сучасні системи захисту інформації використовують методи асиметричної криптографії для передачі ключів шифрування, що ґрунтуються на високій обчислювальній складності факторизації великих чисел. Квантові комп’ютери (КК) теоретично дозволяють прискорити розв’язання задачі факторизації чисел порівняно з класичними комп’ютерами та створюють потенційну загрозу для систем захисту інформації. Втім, реальні КК мають обмежену кількість кубіті зв’язків між ними та проблеми з підтримкою стабільно низької температури, що знижує імовірність знайдення глобального мінімуму.
Сумісне використання КК з класичними комп’ютерами на базі гібридних хмарних сервісів є доцільним, коли пошук оптимального розв'язку прямими методами це складна проблема як в теоретичному сенсі, так і в сенсі необхідного обсягу розрахунків для задач з конкретними даними.
У статті запропоновано спосіб підвищення точності розв’язування задачі факторизації на основі багатократного пошуку мінімуму за методом апаратного зворотного квантового відпалу з варіацією його параметрів. Наведено результати чисельних експериментів для двох різних процесорів КК та гібридного квантово-класичного комп’ютера фірми D-Wave, показано, що максимальне число, що можна факторизувати за виключно прямим відпалом є 143, а за комбінацією прямого і зворотного відпалів – 255.
Мета роботи. Дослідження впливу параметрів відпалу і відповідних режимів для КК адіабатичного типу, побудованого фірмою D-Wave, на якість розв’язку задачі факторизації. Подати рекомендації до покращення точності розв’язку задачі факторизації та підвищення статистичної частоти появи правильних пар множників.
Результати. Чисельні експерименти показали, що для задачі факторизації чисел послідовне застосування прямого і зворотного відпалу дозволяє покращити імовірність отримання правильної пари множників та підвищити більш ніж у два рази статистичну частоту її появи.
Режими квантового відпалу: пауза і загартовування знижують імовірність отримання правильного розв’язку та погіршують статистичну частоту появи правильних пар множників.
Висновки. Використання прямого і зворотного відпалу дозволяє підвищити імовірність отримання правильного розв’язку задачі факторизації для адіабатичного КК фірми D-Wave. Збільшення часу обчислення задачі виправдано, оскільки дозволяє підвищити імовірність правильного розв’язку. Використання гібридних квантово-класичних обчислень та хмарних сервісів дозволяє виконувати факторизацію для чисел з розрядністю до двадцяти двох біт.
Ключові слова: квантовий відпал, факторизація натуральних чисел, асиметричні шифри, загартовування, зворотній відпал, комбінаторна оптимізація.
Цитувати так: Корольов В.Ю., Ходзінський О.М. Дослідження впливу параметрів квантового відпалу на якість розв’язку задачі факторизації чисел. Cybernetics and Computer Technologies. 2023. 1. С. 13–22. https://doi.org/10.34229/2707-451X.23.1.2
Список літератури
1. Moguel E., Rojo J., Valencia D. et al. Quantum service-oriented computing: current landscape and challenges. Software Qual J. 2022. https://doi.org/10.1007/s11219-022-09589-y
2. Wang Y., Liu H. Quantum Computing in a Statistical Context. Annual Review of Statistics and Its Application. 2022. Vol. 9:1. P. 479–504. https://doi.org/10.1146/annurev-statistics-042720-024040
3. Gill S.S., Kumar A., Singh H. Quantum computing: A taxonomy, systematic review and future directions. Software: Practice and Experience. 2022. 52 (1). P. 66–114. https://doi.org/10.1002/spe.3039
4. Корольов В.Ю., Ходзінський О.М. Розв’язування задач комбінаторної оптимізації на квантових комп’ютерах. Cybernetics and Computer Technologies. 2020. 2. С. 5–13. https://doi.org/10.34229/2707-451X.20.2.1
5. What is Quantum Annealing? https://docs.dwavesys.com/docs/latest/c_gs_2.html (звернення: 08.09.2022)
6. QPU Solver Datasheet https://docs.dwavesys.com/docs/latest/doc_qpu.html (звернення: 08.09.2022)
7. Anschuetz E., Olson J., Aspuru-Guzik A., Cao Y. Variational Quantum Factoring. In: Feld, S., Linnhoff-Popien, C. (eds) Quantum Technology and Optimization Problems. QTOP 2019. (Lecture Notes in Computer Science). Vol. 11413. Springer, Cham. https://doi.org/10.1007/978-3-030-14082-3_7
8. Variational Quantum Factoring. https://github.com/mstechly/vqf (звернення: 08.09.2022)
9. D-Wave Examples. Factoring. https://github.com/dwave-examples/factoring (звернення: 08.09.2022)
10. Li Z.K., Dattani N.S., Chen X., Liu X. High-fidelity Adiabatic Quantum Computation Using the Intrinsic Hamiltonian of a Spin System: Application to the Experimental Factorization of 291311. Quantum Physics. 2017. P. 1–6. https://doi.org/10.48550/arXiv.1706.08061
11. Jiang S., Britt K.A., McCaskey A.J. et al. Quantum Annealing for Prime Factorization. Scientific Report. 2018. 8. 17667. P. 1–9. https://doi.org/10.1038/s41598-018-36058-z
12. Gidney C. Factoring with N+2 Clean Qubits and N-1 Dirty Qubits. Quantum Physics. 2018. P. 1–14. https://doi.org/10.48550/arXiv.1706.07884
13. Kieu T.D. A factorisation algorithm in Adiabatic Quantum Computation. Journal of Physics Communications. 3. 17667. 2019. https://doi.org/10.1088/2399-6528/ab060d
14. Baonan W., Feng H., Haonan Y., Chao W. Prime Factorization Algorithm Based on Parameter Optimization of Ising Model. Scientific Report. 2020. 10. 7106. P. 1–10. https://doi.org/10.1038/s41598-020-62802-5
15. Peng W., Wang B., Hu F. et al. Factoring larger integers with fewer qubits via quantum annealing with optimized parameters. Science China Physics, Mechanics, Astronomy. 2019. 62 (6). 60311. https://doi.org/10.1007/s11433-018-9307-1
16. Warren R. H. Factoring on a Quantum Annealing Computer. Quantum Information and Computation. 2019. 19 (3–4). P. 252–261. https://doi.org/10.26421/qic19.3-4-5
17. Wang B., Yang X., Zhang D. Research on Quantum Annealing Integer Factorization Based on Different Columns. Frontier Physics. 2022. 10. 914578. https://doi.org/10.3389/fphy.2022.914578
18. Factoring with Reverse Annealing. https://github.com/novice108/factorQuant/blob/main/factorRVS.py (звернення: 19.01.2023)
19. Корольов В.Ю., Огурцов М.І., Ходзінський О.М. Багаторівневе державне впізнавання об’єктів та аналіз застосовності пост-квантових криптографічних алгоритмів для захисту інформації. Cybernetics and Computer Technologies. 2020. 3. С. 74–84. https://doi.org/10.34229/2707-451X.20.3.7
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна