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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

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

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

Вычислительная сложность[править | править код]

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

Класс сложности задач с квантовым полиномиальным временем и ограниченной ошибкой (BQP) — это класс задач о решениях, который может быть решён за полиномиальное время универсальным квантовым компьютером. Класс BPQ связан с классическими классами сложности иерархией [18]. Является ли какое-либо из этих условий правильным, остаётся открытым вопросом.

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

Суперполиномиальное ускорение[править | править код]

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

Алгоритм Шора для факторизации целых чисел[править | править код]

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

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

Семплинг бозонов[править | править код]

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

Наибольшая экспериментальная реализация семплинга бозонов на сегодняшний день имеет 6 режимов, и поэтому может обрабатывать до 6 фотонов одновременно[26]. Лучший классический алгоритм моделирования семплинга бозонов работает за время порядка для системы с n фотонами и m режимами выхода[27]. BosonSampling — это реализация алгоритма на языке R с открытым исходным кодом. Алгоритм даёт оценку в 50 фотонов, которые необходимы для демонстрации квантового превосходства с помощью семплинга бозонов.

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

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

Критика[править | править код]

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

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

См. также[править | править код]

Примечания[править | править код]

  1. 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. — Bibcode2013PhRvA..88b2316P. — arXiv:1307.7488.
  2. Manin, Yu. I. Vychislimoe i nevychislimoe (неопр.). — Sov.Radio, 1980. — С. 13—15.
  3. 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. — Bibcode1982IJTP...21..467F.
  4. 1 2 3 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. — Bibcode1999SIAMR..41..303S. — arXiv:quant-ph/9508027.
  5. 1 2 Google Plans to Demonstrate the Supremacy of Quantum Computing, IEEE Spectrum: Technology, Engineering, and Science News. Дата обращения 11 января 2018.
  6. CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy, IEEE Spectrum: Technology, Engineering, and Science News. Дата обращения 22 июля 2017.
  7. 1 2 Google's quantum computing plans threatened by IBM curveball (20 октября 2017). Дата обращения 22 октября 2017.
  8. Harris. Google has enlisted NASA to help it prove quantum supremacy within months (англ.), MIT Technology Review. Дата обращения 30 ноября 2018.
  9. 1 2 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.
  10. https://www.scientificamerican.com/article/a-new-law-suggests-quantum-supremacy-could-happen-this-year/ A New «Law» Suggests Quantum Supremacy Could Happen This Year], Scientific American, Daily Digest, June 21, 2019
  11. Google claims to have reached quantum supremacy (англ.), The Financial Times (21 September 2019). Дата обращения 23 октября 2019.
  12. Карпухин, Владимир The Financial Times: Google заявила о создании мощнейшего квантового компьютера, но затем удалила доклад — Технологии на TJ. TJ (21 сентября 2019). Дата обращения 23 октября 2019. Архивировано 23 октября 2019 года.
  13. 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 года.
  14. What the Google vs. IBM debate over quantum supremacy means | ZDNet. www.zdnet.com.
  15. On "Quantum Supremacy". IBM Research Blog (22 октября 2019). Дата обращения 24 октября 2019.
  16. Google Claims To Achieve Quantum Supremacy — IBM Pushes Back. NPR.org. Дата обращения 24 октября 2019.
  17. 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.
  18. Umesh; Vazirani. A Survey of Quantum Complexity Theory (неопр.) // Proceedings of Symposia in Applied Mathematics.
  19. 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. — Bibcode2017npjQI...3...15L. — arXiv:1702.03061.
  20. 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. — Bibcode2016PhRvL.117h0501B. — arXiv:1504.07999. — PMID 27588839.
  21. Jordan. Quantum Algorithm Zoo (недоступная ссылка). math.nist.gov. Дата обращения 29 июля 2017. Архивировано 29 апреля 2018 года.
  22. 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.
  23. Bernstein, Daniel. Post-Quantum Cryptography (неопр.).
  24. Aaronson, Scott. The Computational Complexity of Linear Optics (англ.).
  25. 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. — Bibcode2016PhRvX...6b1039R. — arXiv:1511.06526.
  26. 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.
  27. 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.
  28. 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. — Bibcode1995PhRvA..52.2493S.
  29. 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. — Bibcode1996PhRvL..77..793S. — PMID 10062908.
  30. 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. — Bibcode2005Natur.434...39K. — arXiv:quant-ph/0410199. — PMID 15744292.