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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Критика

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

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

См. также

Примечания