Аргументы и доказательства в пользу квантового преимущества
Добро пожаловать в часть 2 мини-серии о демонстрации квантового преимущества. В первой части я рассказал вам об идее случайной выборки схем (RCS) и её экспериментальной реализации. В этом посте я обсужу аргументы и доказательства, почему я убеждён, что эксперименты демонстрируют квантовое преимущество.
Проверка экспериментальных утверждений о квантовом преимуществе
Чтобы оценить экспериментальное утверждение о квантовом преимуществе, нам нужно проверить три критерия:
* Правильно ли эксперимент решает вычислительную задачу?
* Достигает ли он масштабируемого преимущества перед классическими вычислениями?
* Достигает ли он практического преимущества перед лучшими классическими попытками решения задачи?
Проблема с ранними квантовыми компьютерами
При оценке этих критериев для экспериментов с RCS возникает важная проблема: ранние квантовые компьютеры, на которых они проводились, были далеки от надёжности, и вычисления значительно искажались шумом. Как нам интерпретировать эти зашумлённые данные?
Более кратко: остаётся ли задача случайной выборки схем сложной для классических вычислений, даже если мы допускаем любой уровень шума, который был в реальных экспериментах?
Шум и сложность
Задача с зашумленной выборкой
Давайте начнём с ответа на основной вопрос: какую вычислительную задачу на самом деле решили эксперименты?
В идеальном сценарии RCS нам даётся случайная схема CC на nn кубитах, и задача состоит в том, чтобы выбрать выходные данные из распределения состояний, полученных |C⟩\ket C при применении схемы CC к простому эталонному состоянию.
Но что делает зашумлённый квантовый компьютер, когда я выполняю все операции и применяю их к своему состоянию? Он готовит зашумлённую версию ρC\rho_ C идеального состояния |C⟩\ket C и после измерения кубитов я получаю выборки из выходного распределения этого зашумлённого состояния.
Мы не должны делать задачу зависимой от особенностей этого состояния или шума, который его определил, но мы можем определить вычислительную задачу, основанную на этом наблюдении, зафиксировав, насколько точной является подготовка этого зашумлённого состояния.
Выборка с конечной точностью
Учитывая типичную случайную схему CC, выберите выходные данные из распределения любого квантового состояния, чья точность с идеальным выходным состоянием |C⟩\ket C составляет не менее δ\delta.
Обратите внимание, что выборка с конечной точностью не требует успеха для каждой схемы, а только для типичных схем из ансамбля случайных схем. Это соответствует тому, что делают эксперименты: они выбирают случайные схемы и требуют, чтобы устройство хорошо работало с подавляющим большинством этих схем.
Эксперименты утверждают, что они решили задачу выборки с конечной точностью для значений δ\delta около 0,1%. Более того, они последовательно достигают этого значения даже при увеличении размеров схем в последующих экспериментах.
Сложность выборки с конечной точностью
Квантовое преимущество при выборке с конечной точностью
Давайте начнём с предположения, что квантовые вычисления выполняются (почти) идеально, поэтому требуемая точность δ\delta достаточно велика, скажем, 90%. В этом сценарии у нас есть очень веские доказательства, основанные на теории вычислительной сложности, что существует масштабируемое и практическое квантовое преимущество для RCS.
Вопрос теперь в том, насколько далеко в точности эта классическая сложность сохраняется? Интуитивно, чем меньше мы делаем δ\delta, тем легче должна становиться задача выборки с конечной точностью для классического алгоритма (и для квантового компьютера).
Однако, как ни удивительно, выборка с конечной точностью, по-видимому, остаётся сложной даже для очень малых значений δ\delta. Я не знаю ни одного эффективного классического алгоритма, который бы решал задачу с конечной точностью для δ\delta, значительно отличающейся от базового тривиального значения 2−n2^{-n}.
Переведено с сохранением научной точности и доступности изложения. Если вам нужно перевести ещё что-нибудь, пожалуйста, сообщите мне.