Квантовое превосходство
Квантовое превосходство — способность квантовых вычислительных устройств решать проблемы, которые классические компьютеры практически не могут решить. Квантовое преимущество — возможность решать проблемы быстрее. С точки зрения теории сложности вычислений под этим обычно подразумевается обеспечение суперполиномиального ускорения по сравнению с наиболее известным или возможным классическим алгоритмом. Термин был популяризирован Джоном Прескиллом, но концепция квантового вычислительного преимущества, особенно в моделировании квантовых систем, восходит к предложению квантовых вычислений, которое дали Юрий Манин (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 года китайские ученые сообщили, что их квантовый компьютер Jiuzhang работающий на запутанных фотонах достиг квантового превосходства. За 200 секунд они успешно провели вычисление задачи, для решения которой самому быстрому в мире классическому компьютеру потребовалось считать бы более полумиллиарда лет.
Вычислительная сложность
Вопрос сложности относится к тому, как объём ресурса, необходимого для решения проблемы, масштабируется с размером входных данных. Как расширение классической теории вычислительной сложности, теория квантовой сложности описывает работу универсального квантового компьютера без учёта сложности его создания или устранения эффектов декогерентности и шума. Поскольку квантовая информация является обобщением классической информации, квантовый компьютер может моделировать любой классический алгоритм.
Класс сложности задач с квантовым полиномиальным временем и ограниченной ошибкой (BQP) — это класс задач о решениях, который может быть решён за полиномиальное время универсальным квантовым компьютером. Класс BPQ связан с классическими классами сложности иерархией P ⊆ B P P ⊆ B Q P ⊆ P S P A C E {displaystyle Psubseteq BPPsubseteq BQPsubseteq PSPACE} . Является ли какое-либо из этих условий правильным, остаётся открытым вопросом.
В отличие от задач о решениях, требующих ответа «да» или «нет», проблемы семплинга требуют выборки из распределений вероятностей. Если существует классический алгоритм, который может семплировать выходные данные произвольной квантовой схемы, полиномиальная иерархия переместится на третий уровень, что считается очень маловероятным. BosonSampling — это более конкретное предложение, классическая сложность которого зависит от неразрешимости задачи вычисления перманента большой матрицы со сложными элементами, которая является P# -полной проблемой. Аргументы, использованные для получения этого утверждения, были также применены к IQP-семплингу, где необходима только гипотеза о том, что сложность задачи в среднем и наихудшем случаях одинакова.
Суперполиномиальное ускорение
Следующие алгоритмы обеспечивают суперполиномиальное ускорение по сравнению с наиболее известными классическими алгоритмами:
Алгоритм Шора для факторизации целых чисел
Этот алгоритм находит факторизацию на простые числа n- битного целого числа за время O ~ ( n 3 ) {displaystyle { ilde {O}}(n^{3})} , самый известный классический алгоритм требует 2 O ( n 1 / 3 ) {displaystyle 2^{O(n^{1/3})}} времени и лучшая верхняя оценка сложности этой задачи O ( 2 n / 3 + o ( 1 ) ) {displaystyle O(2^{n/3+o(1)})} . Он также может обеспечить ускорение любой задачи, которая сводится к целочисленной факторизации, в том числе проблемы принадлежности групп матриц к полям нечётного порядка.
Для квантовых вычислений этот алгоритм важен как практически, так и исторически. Он стал первым полиномиальным квантовым алгоритмом, предложенным для задачи, которая считается сложной для классических компьютеров. Уверенность в этой сложности настолько сильна, что на алгоритме факторизации основана безопасность самого распространённого сегодня протокола шифрования RSA. Квантовый компьютер, успешно и воспроизводимо запускающий этот алгоритм, может сломать данную систему шифрования. Этот риск взлома получил название проблемы Y2Q, по аналогии с «Y2K» — проблема 2000 года.
Семплинг бозонов
Эта вычислительная парадигма основана на идентичных фотонах, посылаемых через линейно-оптическую сеть, она может решить определённые проблемы с семплингом и поиском, которые, принимая несколько гипотез, неразрешимы для классических компьютеров. Тем не менее было показано, что семплинг бозонов в системе с достаточно большими потерями и шумом может быть эффективно смоделирован.
Наибольшая экспериментальная реализация семплинга бозонов на сегодняшний день имеет 6 режимов, и поэтому может обрабатывать до 6 фотонов одновременно. Лучший классический алгоритм моделирования семплинга бозонов работает за время порядка O ( n 2 n + m n 2 ) {displaystyle O(n2^{n}+mn^{2})} для системы с n фотонами и m режимами выхода. BosonSampling — это реализация алгоритма на языке R с открытым исходным кодом. Алгоритм даёт оценку в 50 фотонов, которые необходимы для демонстрации квантового превосходства с помощью семплинга бозонов.
Семплинг выходного распределения случайных квантовых схем
Самый известный алгоритм моделирования произвольной случайной квантовой схемы требует время, которое экспоненциально масштабируется с количеством кубитов, на основе этого одна группа исследователей даёт оценку, что около 50 кубитов может быть достаточно для демонстрации квантового превосходства. Google объявила о своём намерении продемонстрировать квантовое превосходство к концу 2017 года, создав и запустив 49-кубитовый чип, который сможет за разумное время семплировать распределения, недоступные для любых современных классических компьютеров. Но самое масштабное моделирование квантовых схем, успешно выполненное на суперкомпьютере, имеет 56 кубитов. Поэтому может потребоваться увеличение числа кубитов, необходимых для демонстрации квантового превосходства.
Критика
Квантовые компьютеры гораздо более подвержены ошибкам, чем классические компьютеры, из-за декогеренции и шума. Пороговая теорема гласит, что зашумлённый квантовый компьютер может использовать квантовые коды с исправлением ошибок для моделирования незашумленного квантового компьютера, в предположении, что ошибка, вносимая в каждый компьютерный цикл, меньше некоторого числа. Численное моделирование показывает, что это число может достигать 3 %.
Однако неизвестно, как ресурсы, необходимые для исправления ошибок, будут масштабироваться с количеством кубитов. Скептики[какие?] указывают на то, что поведение шума неизвестно в масштабируемых квантовых системах в качестве потенциальных препятствий для успешной реализации квантовых вычислений и демонстрации квантового превосходства.