ИССЛЕДОВАНИЕ И РАЗРАБОТКА СХЕМ С ОПТИМИЗАЦИЕЙ ПО ГЛУБИНЕ В АЛГОРИТМЕ КВАНТОВОЙ ПРИБЛИЖЕННОЙ ОПТИМИЗАЦИИ
Аннотация
Одной из основных проблем, с которой сталкиваются исследователи в области
квантовых вычислений, является проблема шума в квантовых системах. Шум может су-
щественно ограничивать производительность квантовых алгоритмов. Именно в этом
контексте актуализируется наше исследование, направленное на разработку и оптимиза-
цию квантовых алгоритмов с фокусом на глубине. Глубина квантовых цепей – это один из
критически важных параметров в разработке квантовых алгоритмов. Оптимизированные
схемы с улучшенной глубиной имеют потенциал существенно снизить влияние шума, что, в
свою очередь, должно привести к повышению эффективности. Мы стремимся предло-
жить решения, которые не только учитывают технические ограничения, но и предостав-
ляют практически применимые результаты для квантовых вычислений в контексте оп-
тимизационных задач. В рамках данного исследования проводится анализ применения
квантового алгоритма приближенной оптимизации для решения сложных задач комбина-
торной оптимизации. Однако в процессе использования данного алгоритма сталкиваемся с
серьезным ограничением – шумом в квантовой системе, что существенно снижает его
эффективность. Для преодоления влияния шума и повышения эффективности квантовых
алгоритмов, было предложено несколько методов. В данной статье представлен жадный
эвристический алгоритм, направленный на уменьшение воздействия шума. Основная цель
этого алгоритма заключается в поиске остовного дерева минимальной высоты. Это, в
свою очередь, приводит к сокращению общей глубины квантовых схем и минимизации коли-
чества вентилей CNOT, что является ключевым моментом в оптимизации квантовых вы-
числений. Через проведение численного анализа было продемонстрировано, что предло-
женный жадный эвристический алгоритм способен существенно увеличить вероятность
успешного завершения каждой итерации в задаче поиска максимального разреза в графе в
10 раз. Кроме того, исследование подтверждает, что средняя глубина квантовой схемы,
созданной предложенным эвристическим алгоритмом, все еще линейно зависит от разме-
ра входных данных, но угол наклона этой линейной зависимости снижается с 1 до 0,11
благодаря использованию предложенного метода.
Литература
preprint arXiv:1411.4028, 2014.
2. Cerezo M., Arrasmith A., Babbush R., Benjamin S., Endo S., Fujii K., McClean J., Mitarai K.,
Yuan X., Cincio L., et al. Variational quantum algorithms, arXiv preprint arXiv:2012.09265,
2020.
3. Linke N.M., Gutierrez M., Landsman K.A., et al. Fault-tolerant quantum error detection, Science
Advances, 2017, 3 (10): e1701074. Available from: https://doi.org/10.1126/
sciadv.1701074.
4. Vuillot C. Is error detection helpful on IBM 5q chips?, Quantum Information and Computation,
2018, Vol. 18, No. 11-12, pp. 0949-0964.
5. Barron G. and Wood C. Measurement error mitigation for variational quantum algorithms,
arXiv preprint arXiv:2010.08520, 2020.
6. Endo S., Benjamin S., and Li Y. Practical quantum error mitigation for near-future applications,
Physical Review X, 2018, 8 (3):031027.
7. Endo S., Cai Z., Benjamin S., and Yuan X. Hybrid quantum-classical algorithms and quantum
error mitigation, Journal of the Physical Society of Japan, 2021, 90 (3):032001.
8. Zhu L., Tang H., Barron G., Calderon-Vargas F., Mayhall N., Barnes E., and Economou S. An
adaptive quantum approximate optimization algorithm for solving combinatorial problems on
a quantum computer, arXiv preprint arXiv:2005.10258, 2020.
9. Larkin J., Jonsson M., Justice D., and Guerreschi G. Evaluation of quantum approximate optimization
algorithm based on the approximation ratio of single samples, arXiv e-prints, pages
arXiv–2006, 2020.
10. Barkoutsos P., Nannicini G., Robert A., Tavernelli I., and Woerner S. Improving variational
quantum optimization using cvar, Quantum, 2020, 4:256.
11. Harper R, Flammia S.T. Fault-tolerant logical gates in the IBM quantum experience, Phys.
Rev. Lett., 2019, 122:080504. Available from: https://link.aps.org/doi/10.1103/
PhysRevLett.122.080504.
12. Hales S. Hallgren An improved quantum Fourier transform algorithm and applications, Proceedings
of the 41st Annual Symposium on Foundations of Computer Science, November
12–14, 2000, pp. 515.
13. Guzik V., Gushanskiy S., Polenov M., Potapov V. Complexity Estimation of Quantum Algorithms
Using Entanglement Properties, 16th International Multidisciplinary Scientific
GeoConference, Bulgaria, 2016, pp. 20-26.
14. Guzik V., Gushanskiy S., Polenov M., Potapov V. Models of a quantum computer, their characteristics
and analysis, 9th International Conference on Application of Information and Communication
Technologies (AICT). Institute of Electrical and Electronics Engineers, 2015,
pp. 583-587.
15. Collier D. The Comparative Method. In: Finifter A.W. (ed.) Political Sciences: The State of
the Discipline II. American Science Association. Washington, DC, 1993, pp. 105-119.
16. Olukotun K. Chip Multiprocessor Architecture – Techniques to Improve Throughput and Latency.
Morgan and Claypool Publishers, San Rafael, 2007.
17. Raedt K.D., Michielsen K., De Raedt H., Trieu B., Arnold G., Marcus Richter, Th Lip-pert,
Watanabe H., and Ito N. Massively parallel quantum computer simulator, Computer Physics
Communications, 176, pp. 121-136.
18. Williams C.P. Explorations in Quantum Computing, Texts in Computer Science, Chapter 2.
Quantum Gates. Springer, 2011, pp. 51-122.
19. Potapov V., Gushanskiy S., Guzik V., Polenov M. The Computational Structure of the Quantum
Computer Simulator and Its Performance Evaluation, In: Software Engineering Perspectives
and Application in Intelligent Systems. Advances in Intelligent Systems and Computing.
Springer, 2019, Vol. 763, pp. 198-207.
20. Rahman M. and Kaykobad M. Complexities of some interesting problems on spanning trees,
Information Processing Letters, 2005, 94 (2), pp. 93-97.
21. Bennett С.H., Shor P.W., Smolin J.A., Thapliyal A.V. Entanglement-assisted Capacity of a
Quantum Channel and the Reverse Shannon Theorem, IEEE Transactions on Information
Theory, 2002, 48, 2637.
22. Hector A. et al. Qiskit: An open-source framework for quantum computing, 2019.
23. Milner R.G. A Short History of Spin., In: Contribution to the XV International Workshop on
Polarized Sources, Targets, and Polarimetry. Charlottesville, Virginia, USA, September 9 –
13, 2013. arXiv:1311.5016 (2013);
24. Boneh D., Zhandry M. Quantum-secure message authentication codes, In: Proceedings of
Eurocrypt, 2013, pp. 592-608;
25. Potapov V., Gushansky S., Guzik V., Polenov M. Architecture and Software Implementation of
a Quantum Computer Model, In: Advances in Intelligent Systems and Computing. Springer,
2016, Vol. 465, pp. 59-68.
