Квантовое превосходство

Ква́нтовое превосхо́дство — способность квантовых вычислительных устройств решать проблемы, которые классические компьютеры практически не могут решить. Квантовое преимущество — возможность решать проблемы быстрее^[1]. С точки зрения теории сложности вычислений под этим обычно подразумевается обеспечение суперполиномиального ускорения по сравнению с наиболее известным или возможным классическим алгоритмом^[2]. Термин был популяризирован Джоном Прескиллом, но концепция квантового вычислительного преимущества, особенно в моделировании квантовых систем, восходит к предложению квантовых вычислений, которое дали Юрий Манин (1980)^[3] и Ричард Фейнман (1981)^[4].

Алгоритм Шора для факторизации целых чисел, который выполняется за полиномиальное время на квантовом компьютере, обеспечивает такое суперполиномиальное ускорение по сравнению с наиболее известным классическим алгоритмом^[5]. Хотя это ещё предстоит доказать, факторизация считается сложной задачей при использовании классических ресурсов. Трудность доказательства того, что нельзя сделать с помощью классических вычислений, является общей проблемой для безусловной демонстрации квантового превосходства. Это также влияет на предложение по семплингу бозонов Ааронсона и Архипова, специализированные проблемы компании D-Wave о frustrated cluster loop и семплинг выходного результата для случайных квантовых схем.

Подобно факторизации целых чисел, задача о выборке выходных распределений случайных квантовых схем считается сложной для классических компьютеров на основе разумных предположений о сложности.

История

Google ранее объявила о планах продемонстрировать квантовое превосходство до конца 2017 года, используя массив из 49 сверхпроводящих кубитов^[6]. Однако по состоянию на начало января 2018 года только Intel анонсировала такое оборудование^[7].

В октябре 2017 года IBM продемонстрировала моделирование 56 кубитов на обычном суперкомпьютере, увеличив число кубитов, необходимых для квантового превосходства^[8].

В ноябре 2018 года Google объявила о партнёрстве с НАСА, в рамках которого НАСА будет «анализировать результаты от квантовых схем, запущенных на квантовых процессорах Google, и … обеспечивать сравнение с классическим моделированием, чтобы поддержать Google в проверке его аппаратуры и установить базовые показатели для квантового превосходства»^[9].

Теоретическая работа 2018 года предполагает, что квантовое превосходство возможно достигнуть на «двумерной решётке 7 × 7 кубитов и около 40 тактовых циклах», но если частота ошибок будет достаточно низкой^[10].

21 июня 2019 года Scientific American предположил, что по закону Невена квантовое превосходство будет достигнуто в 2019 году^[11].

20 сентября 2019 Financial Times сообщила, что «Google утверждает, что достигла квантового превосходства на массиве из 54 кубитов, из которых 53 были функциональными и использовались для выполнения вычислений за 200 секунд, на что обычному суперкомпьютеру потребовалось бы около 10 000 лет»^[12]. Изначально доклад об этом появился на сайте НАСА, но вскоре после публикации был удалён^[13]. Позже, 23 октября, о достижении квантового превосходства было объявлено официально^[14]. Однако, специалисты из IBM проанализировав представленные данные, указали что некоторые моменты являются неоптимальными и что на самом деле подобный расчет на классическом суперкомпьютере займет всего 2,5 дня вместо заявленных 10 000 лет.^[15][16][17]

3 декабря 2020 года китайские ученые сообщили, что их квантовый компьютер Цзючжан, работающий на запутанных фотонах, достиг квантового превосходства. За 200 секунд они успешно провели вычисление задачи, для решения которой самому быстрому в мире классическому компьютеру потребовалось считать бы более полумиллиарда лет^[18].

Вычислительная сложность

Вопрос сложности относится к тому, как объём ресурса, необходимого для решения проблемы, масштабируется с размером входных данных. Как расширение классической теории вычислительной сложности, теория квантовой сложности описывает работу универсального квантового компьютера без учёта сложности его создания или устранения эффектов декогерентности и шума^[19]. Поскольку квантовая информация является обобщением классической информации, квантовый компьютер может моделировать любой классический алгоритм.

Класс сложности задач с квантовым полиномиальным временем и ограниченной ошибкой (BQP) — это класс задач о решениях, который может быть решён за полиномиальное время универсальным квантовым компьютером. Класс BPQ связан с классическими классами сложности иерархией ${\displaystyle P\subseteq BPP\subseteq BQP\subseteq PSPACE}$^[20]. Остаётся открытым вопросом, является ли какое-либо из этих вложений строгим.

В отличие от задач о решениях, требующих ответа «да» или «нет», проблемы семплинга требуют выборки из распределений вероятностей^[21]. Если существует классический алгоритм, который может семплировать выходные данные произвольной квантовой схемы, полиномиальная иерархия переместится на третий уровень, что считается очень маловероятным. BosonSampling — это более конкретное предложение, классическая сложность которого зависит от неразрешимости задачи вычисления перманента большой матрицы со сложными элементами, которая является P# -полной проблемой. Аргументы, использованные для получения этого утверждения, были также применены к IQP-семплингу^[22], где необходима только гипотеза о том, что сложность задачи в среднем и наихудшем случаях одинакова.

Суперполиномиальное ускорение

Следующие алгоритмы обеспечивают суперполиномиальное ускорение по сравнению с наиболее известными классическими алгоритмами^[23]:

Алгоритм Шора для факторизации целых чисел

Этот алгоритм находит факторизацию на простые числа n- битного целого числа за время ${\displaystyle {\tilde {O}}(n^{3})}$^[5], самый известный классический алгоритм требует ${\displaystyle 2^{O(n^{1/3})}}$ времени и лучшая верхняя оценка сложности этой задачи ${\displaystyle O(2^{n/3+o(1)})}$. Он также может обеспечить ускорение любой задачи, которая сводится к целочисленной факторизации, в том числе проблемы принадлежности групп матриц к полям нечётного порядка.

Для квантовых вычислений этот алгоритм важен как практически, так и исторически. Он стал первым полиномиальным квантовым алгоритмом, предложенным для задачи, которая считается сложной для классических компьютеров^[5]. Уверенность в этой сложности настолько сильна, что на алгоритме факторизации основана безопасность самого распространённого сегодня протокола шифрования RSA^[24]. Квантовый компьютер, успешно и воспроизводимо запускающий этот алгоритм, может сломать данную систему шифрования^[25]. Этот риск взлома получил название проблемы Y2Q, по аналогии с «Y2K» — проблема 2000 года.

Семплинг бозонов

Эта вычислительная парадигма основана на идентичных фотонах, посылаемых через линейно-оптическую сеть, она может решить определённые проблемы с семплингом и поиском, которые, принимая несколько гипотез, неразрешимы для классических компьютеров^[26]. Тем не менее было показано, что семплинг бозонов в системе с достаточно большими потерями и шумом может быть эффективно смоделирован^[27].

Наибольшая экспериментальная реализация семплинга бозонов на сегодняшний день имеет 6 режимов, и поэтому может обрабатывать до 6 фотонов одновременно^[28]. Лучший классический алгоритм моделирования семплинга бозонов работает за время порядка ${\displaystyle O(n2^{n}+mn^{2})}$ для системы с n фотонами и m режимами выхода^[29]. BosonSampling — это реализация алгоритма на языке R с открытым исходным кодом. Алгоритм даёт оценку в 50 фотонов, которые необходимы для демонстрации квантового превосходства с помощью семплинга бозонов.

Семплинг выходного распределения случайных квантовых схем

Самый известный алгоритм моделирования произвольной случайной квантовой схемы требует время, которое экспоненциально масштабируется с количеством кубитов, на основе этого одна группа исследователей даёт оценку, что около 50 кубитов может быть достаточно для демонстрации квантового превосходства^[10]. Google объявила о своём намерении продемонстрировать квантовое превосходство к концу 2017 года, создав и запустив 49-кубитовый чип, который сможет за разумное время семплировать распределения, недоступные для любых современных классических компьютеров^[6]. Но самое масштабное моделирование квантовых схем, успешно выполненное на суперкомпьютере, имеет 56 кубитов. Поэтому может потребоваться увеличение числа кубитов, необходимых для демонстрации квантового превосходства^[8].

Критика

Квантовые компьютеры гораздо более подвержены ошибкам, чем классические компьютеры, из-за декогеренции и шума. Пороговая теорема гласит, что зашумлённый квантовый компьютер может использовать квантовые коды с исправлением ошибок^[30][31] для моделирования незашумленного квантового компьютера, в предположении, что ошибка, вносимая в каждый компьютерный цикл, меньше некоторого числа. Численное моделирование показывает, что это число может достигать 3 %^[32].

Однако неизвестно, как ресурсы, необходимые для исправления ошибок, будут масштабироваться с количеством кубитов. Скептики^{[какие?]} указывают на то, что поведение шума неизвестно в масштабируемых квантовых системах в качестве потенциальных препятствий для успешной реализации квантовых вычислений и демонстрации квантового превосходства.

Примечания

1. Леонид Федичкин На пороге квантового превосходства Архивная копия от 8 июля 2023 на Wayback Machine // Наука и жизнь, 2023, № 7. — с. 14-20
2. Anargyros; Papageorgiou. Measures of quantum computing speedup (англ.) // Physical Review A : journal. — 2013. — 12 August (vol. 88, no. 2). — P. 022316. — ISSN 1050-2947. — doi:10.1103/PhysRevA.88.022316. — Bibcode: 2013PhRvA..88b2316P. — arXiv:1307.7488.
3. Manin, Yu. I. Vychislimoe i nevychislimoe (неопр.). — Sov.Radio, 1980. — С. 13—15.
4. Richard P.; Feynman. Simulating Physics with Computers (англ.) // International Journal of Theoretical Physics^[англ.] : journal. — 1982. — 1 June (vol. 21, no. 6—7). — P. 467—488. — ISSN 0020-7748. — doi:10.1007/BF02650179. — Bibcode: 1982IJTP...21..467F.
5. P.; Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (англ.) // SIAM Review : journal. — 1999. — 1 January (vol. 41, no. 2). — P. 303—332. — ISSN 0036-1445. — doi:10.1137/S0036144598347011. — Bibcode: 1999SIAMR..41..303S. — arXiv:quant-ph/9508027.
6. "Google Plans to Demonstrate the Supremacy of Quantum Computing". IEEE Spectrum: Technology, Engineering, and Science News. Архивировано 25 апреля 2021. Дата обращения: 11 января 2018.
7. "CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy". IEEE Spectrum: Technology, Engineering, and Science News. Архивировано 23 марта 2021. Дата обращения: 22 июля 2017.
8. Google's quantum computing plans threatened by IBM curveball  (неопр.) (20 октября 2017). Дата обращения: 22 октября 2017. Архивировано 25 января 2021 года.
9. Harris, Mark. "Google has enlisted NASA to help it prove quantum supremacy within months". MIT Technology Review (англ.). Архивировано 10 марта 2020. Дата обращения: 30 ноября 2018.
10. Sergio; Boixo. Characterizing quantum supremacy in near-term devices (англ.) // Nature Physics : journal. — 2018. — 23 April (vol. 14, no. 6). — P. 595—600. — doi:10.1038/s41567-018-0124-x. — arXiv:1608.00263.
11. https://www.scientificamerican.com/article/a-new-law-suggests-quantum-supremacy-could-happen-this-year/ Архивная копия от 2 марта 2021 на Wayback Machine A New «Law» Suggests Quantum Supremacy Could Happen This Year], Scientific American, Daily Digest, June 21, 2019
12. "Google claims to have reached quantum supremacy". The Financial Times (англ.). 2019-09-21. Архивировано 29 апреля 2021. Дата обращения: 23 октября 2019.
13. Карпухин, Владимир The Financial Times: Google заявила о создании мощнейшего квантового компьютера, но затем удалила доклад — Технологии на TJ  (неопр.). TJ (21 сентября 2019). Дата обращения: 23 октября 2019. Архивировано 23 октября 2019 года.
14. Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin. Quantum supremacy using a programmable superconducting processor (англ.) // Nature. — 2019. — October (iss. 7779, no. 574). — P. 505—510. — ISSN 1476-4687. — doi:10.1038/s41586-019-1666-5. Архивировано 23 октября 2019 года.
15. What the Google vs. IBM debate over quantum supremacy means | ZDNet  (неопр.). www.zdnet.com. Дата обращения: 12 февраля 2020. Архивировано 5 марта 2020 года.
16. On "Quantum Supremacy"  (неопр.). IBM Research Blog (22 октября 2019). Дата обращения: 24 октября 2019. Архивировано 11 ноября 2021 года.
17. Google Claims To Achieve Quantum Supremacy — IBM Pushes Back  (неопр.). NPR.org. Дата обращения: 24 октября 2019. Архивировано 23 октября 2019 года.
18. Light-based quantum computer Jiuzhang achieves quantum supremacy | Science News  (неопр.). Дата обращения: 4 декабря 2020. Архивировано 2 ноября 2021 года.
19. Watrous, John. Quantum Computational Complexity // Encyclopedia of Complexity and Systems Science (англ.). — Springer New York, 2009. — P. 7174—7201. — ISBN 9780387758886. — doi:10.1007/978-0-387-30440-3_428.
20. Umesh; Vazirani. A Survey of Quantum Complexity Theory (неопр.) // Proceedings of Symposia in Applied Mathematics. Архивировано 7 мая 2021 года.
21. A. P.; Lund. Quantum sampling problems, BosonSampling and quantum supremacy (англ.) // Npj Quantum Information^[англ.] : journal. — 2017. — 13 April (vol. 3, no. 1). — ISSN 2056-6387. — doi:10.1038/s41534-017-0018-2. — Bibcode: 2017npjQI...3...15L. — arXiv:1702.03061. Архивировано 8 марта 2021 года.
22. Michael J.; Bremner. Average-case complexity versus approximate simulation of commuting quantum computations (англ.) // Physical Review Letters : journal. — 2016. — 18 August (vol. 117, no. 8). — ISSN 0031-9007. — doi:10.1103/PhysRevLett.117.080501. — Bibcode: 2016PhRvL.117h0501B. — arXiv:1504.07999. — PMID 27588839.
23. Jordan. Quantum Algorithm Zoo  (неопр.). math.nist.gov. Дата обращения: 29 июля 2017. Архивировано из оригинала 29 апреля 2018 года.
24. R. L.; Rivest. A Method for Obtaining Digital Signatures and Public-key Cryptosystems (англ.) // Commun. ACM : journal. — 1978. — February (vol. 21, no. 2). — P. 120—126. — ISSN 0001-0782. — doi:10.1145/359340.359342.
25. Bernstein, Daniel. Post-Quantum Cryptography (неопр.). Архивировано 11 мая 2021 года.
26. Aaronson, Scott. The Computational Complexity of Linear Optics (англ.).
27. Saleh; Rahimi-Keshari. Sufficient Conditions for Efficient Classical Simulation of Quantum Optics (англ.) // Physical Review X : journal. — 2016. — 20 June (vol. 6, no. 2). — P. 021039. — doi:10.1103/PhysRevX.6.021039. — Bibcode: 2016PhRvX...6b1039R. — arXiv:1511.06526.
28. Jacques; Carolan. Universal linear optics (англ.) // Science. — 2015. — 14 August (vol. 349, no. 6249). — P. 711—716. — ISSN 0036-8075. — doi:10.1126/science.aab3642. — arXiv:1505.01182. — PMID 26160375. Архивировано 16 декабря 2020 года.
29. Alex; Neville. No imminent quantum supremacy by boson sampling (англ.) // Nature Physics : journal. — 2017. — 2 October (vol. 13, no. 12). — P. 1153—1157. — ISSN 1745-2473. — doi:10.1038/nphys4270. — arXiv:1705.00686. Архивировано 6 августа 2020 года.
30. Peter W.; Shor. Scheme for reducing decoherence in quantum computer memory (англ.) // Physical Review A : journal. — 1995. — 1 October (vol. 52, no. 4). — P. R2493—R2496. — doi:10.1103/PhysRevA.52.R2493. — Bibcode: 1995PhRvA..52.2493S.
31. A. M.; Steane. Error Correcting Codes in Quantum Theory (англ.) // Physical Review Letters : journal. — 1996. — 29 July (vol. 77, no. 5). — P. 793—797. — doi:10.1103/PhysRevLett.77.793. — Bibcode: 1996PhRvL..77..793S. — PMID 10062908.
32. E.; Knill. Quantum computing with realistically noisy devices (англ.) // Nature. — 2005. — 3 March (vol. 434, no. 7029). — P. 39—44. — ISSN 0028-0836. — doi:10.1038/nature03350. — Bibcode: 2005Natur.434...39K. — arXiv:quant-ph/0410199. — PMID 15744292. Архивировано 28 июня 2009 года.

Литература

• Митио Каку. Квантовое превосходство. Революция в вычислениях, которая изменит всё = Michio Kaku. Quantum Supremacy: How the Quantum Computer Revolution Will Change Everything. — М.: Альпина нон-фикшн, 2024. — С. 412. — ISBN 978-5-00139-728-1.