Ква́нтовое превосхо́дство — способность квантовых вычислительных устройств решать проблемы, которые классические компьютеры практически не могут решить. Квантовое преимущество — возможность решать проблемы быстрее[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].