Квантовый алгоритм решения задачи коммивояжера методом квантовой оценки фазы и квантового поиска

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Рассмотрен квантовый алгоритм решения задачи коммивояжера методом квантовой оценки фазы и квантового поиска. Развивается подход, ранее предложенный для решения этой задачи. Использован один квантовый регистр для кодирования собственных состояний унитарного оператора, фаза которого задает длительность каждого из возможных маршрутов. Для оценки длительности маршрута используется алгоритм квантовой оценки фазы. Затем для нахождения минимальной длительности маршрута измеренные значения длительностей кодируются в состояния второго квантового регистра и проводится поиск оптимального маршрута с помощью модифицированного алгоритма Гровера. Проведено численное моделирование предложенного квантового алгоритма с использованием библиотеки Qiskit для одной и двух итераций модифицированного алгоритма Гровера.

Об авторах

Ч. Цзюньси

Институт физики полупроводников им. А. В. Ржанова Сибирского отделения Российской академии наук

Email: beterov@isp.nsc.ru
Новосибирск, 630090 Россия

И. И. Бетеров

Новосибирский государственный университет;Институт физики полупроводников им. А. В. Ржанова Сибирского отделения Российской академии наук;Институт лазерной физики Сибирского отделения Российской академии наук;Новосибирский государственный технический университет

Автор, ответственный за переписку.
Email: beterov@isp.nsc.ru
Новосибирск, 630090 Россия;Новосибирск, 630090 Россия;Новосибирск, 630090 Россия;Новосибирск, 630073 Россия

Список литературы

  1. B. Mott, J. Job, J. R. Vlimant, D. Lidar, and M. Spiropulu, Nature 550, 375 (2017).
  2. F. Arute, K. Arya, R. Babbush et al., Nature 574, 505 (2019).
  3. Y. Wu, W-S. Bao, S. Cao et al., Phys. Rev. Lett. 127, 180501 (2021).
  4. H.-S. Zhong, Y-H. Deng, J. Qin et al., Phys. Rev. Lett. 127, 180502 (2021).
  5. T. M. Graham, Y. Song, J. Scott et al., Nature 604, 457 (2022).
  6. C. Noel, P. Niroula, D. Zhu et al., Nat. Phys. 18, 760 (2022).
  7. K. Srinivasan, S. Satyajit, B. K. Behera, and P. K. Panigrahi, arXiv:1805.10928 (2018).
  8. https://qiskit.org/textbook/ch-paper-implementations/tsp.html
  9. R. Botez, I.-A. Ivanciu, I. Marian, and V. Dobrota, Proc. Rom. Acad. - Math. Phys. Tech. Sci. Inf. Sci. 22(41), 91 (2021).
  10. J. Zhu, Y. Gao, H. Wang et al., arXiv:2212.02735 (2022).
  11. G. L. Long, Phys. Rev. A 64, 022307 (2001).
  12. Y. Chen, S. Wei, X. Gao et al., arXiv:1908.07943 (2019).
  13. M. Ghosh, N. Dey, D. Mitra, and A. Chakrabarti, IET Quantum Communication 3(1), 13 (2022), doi: 10.1049/qtc2.12023.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2023