IQP включает только элементы, диагональные в базисе Paul- X, поэтому не обеспечивает полной мощности квантовых вычислений. Однако считается, что это сложно смоделировать классическим способом. Ниже мы рассмотрим слабое моделирование семейства схем, когда, учитывая описание схемы, ее выходное распределение может быть выбрано с помощью классического компьютера с полиномиальным временем.
Теорема 3.1. Если бы выходные распределения вероятностей, генерируемые однородными семействами схем IQP, можно было бы слабо классически моделировать, то полиномиальная иерархия (PH) рухнула бы до своего третьего уровня.
Считается, что коллапс PH маловероятен, что дает нам уверенность в надежности IQP.
Хотя теорема является результатом наихудшего случая, мы можем сократить некоторые примеры из набора проблем, которые, как мы ожидаем, продемонстрируют квантовое преимущество. Например , когда результат вычисления классически вычислим. В протоколах, которые мы установили , придавая нам необходимую жесткость
Теоремаи аналогичные результаты впримечательны тем, что демонстрируют, что квантовые компьютеры, которые намного слабее универсальной машины BQP, невозможно моделировать классическим способом. Эти результаты, однако, подтверждаются в условиях, когда требуется, чтобы классический симулятор производил выборки, которые находятся в пределах мультипликативной ошибки, которая зависит от вероятности выборки, идеального квантового распределения. Более реалистично и ближе к истинным возможностям шумных квантовых компьютеров позволить классическому симулятору ошибаться с точностью до аддитивной ошибки. Это означает, что устройство не обязательно должно быть выборкой из идеального распределения P , но необходимо любое распределение со свойством
для некоторой константы . Эта мера расстояния между распределениями также называется -нормальным расстоянием. В этом случае тоже есть результаты по твердости.
Теорема 3.2. Предположим одну из двух гипотез, касающихся жесткости статистической суммы Изинга и разрыва многочленов степени 3, а также устойчивости PH, невозможно выполнить классическую выборку из распределения вероятностей выхода любой схемы IQP за полиномиальное время. , с точностью до аддитивной ошибки .
Мы возьмем твердость слабого моделирования до аддитивной ошибки как указание на то, что класс проблем является многообещающим для ранней демонстрации квантового преимущества. Это оправдано, потому что кажется правдоподобным, что шум будет иметь аналогичное влияние на проблемы среднего случая, которые мы моделируем, и проблемы наихудшего случая, для которых существуют результаты по твердости. Таким образом, мы можем сделать выводы о влиянии шума на тяжелые случаи, исходя из его воздействия на средние случаи.
В идеале мы хотели бы, чтобы наш класс продемонстрировал преимущество в среднем случае, поскольку доказательства этих результатов часто бывают конструктивными и предлагали бы нам схемы для реализации. Такие результаты, примером которых является следующий, труднее получить, особенно если требуется устойчивость к шуму и архитектурные ограничения.