Существуют ли проблемы, при которых квантовые компьютеры обладают экспоненциальным преимуществом?

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

Одним из наиболее часто цитируемых примеров проблемы, в которой квантовые компьютеры будут превосходить классические устройства, является , но, опять же, также не известно, эффективно ли также решается с классическим компьютером (что есть ли ).Факторинг Факторинг ∈ $\text{Factoring}$$\text{Factoring}$$\text{Factoring}\in \text{P}$

Для других часто упоминаемых проблем, в которых квантовые компьютеры, как известно, обеспечивают преимущество, таких как поиск в базе данных, ускорение является только полиномиальным.

Существуют ли известные случаи проблем, в которых можно показать (доказано или доказано в предположениях о высокой сложности вычислений), что квантовые компьютеры обеспечивают экспоненциальное преимущество?

Предположим, что функция имеет следующее любопытное свойство: существует s ∈ { 0 , 1 } n такое, что f ( x ) = f ( y ) тогда и только тогда, когда x + y = s . Если s = 0 - единственное решение, это означает, что f равно 1-к-1; в противном случае существует ненулевое s такое, что f ( x $f\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$$s \in \{0,1\}^n$$f(x) = f(y)$$x + y = s$$s = 0$$f$$s$ для всех x , что, поскольку 2 = 0 , означает, что f равно 2-к-1.$f(x) = f(x + s)$$x$$2 = 0$$f$

Сколько стоит любая предписанная вероятность успеха на классическом или квантовом компьютере, чтобы отличить равномерную случайную функцию 1-к-1 от равномерной случайной функции 2-к-1, удовлетворяющей этому свойству, если каждая опция (1-к -1 или 2-к-1) имеет равную вероятность?

То есть я тайно подбрасываю монету честно; если я головы я руку вам черный ящик (классической или квантовой, соотв.) схема для равномерного случайного 1-к-1 функции , в то время как , если я получаю хвосты я руку вам цепь черного ящика для равномерной случайной 2-к -1 функция ф . Сколько вы должны заплатить , чтобы получить заданную вероятность успеха р рассказывания получил ли я орел или решка?$f$$f$$p$

Это сценарий алгоритма Саймона . Он имеет эзотерическое применение в бессмысленном криптоанализе , ^* и это было ранним инструментом в изучении классов сложности BQP и BPP и раннее вдохновение для алгоритма Шора.

Саймон представил квантовый алгоритм (§3.1, стр. 7), который стоит кубитов и ожидаемое время O ( n ⋅ T f ( n ) + G ( n ) ) для вероятности около 1 успеха, где T f ( n ) - время для вычисления суперпозиции значений f на входе размера n, а где G ( n ) - время для решения$O(n + |f|)$$O(n \cdot T_f(n) + G(n))$$T_f(n)$$f$$n$$G(n)$ система линейных уравнений в F 2 .$n \times n$$\mathbb F_2$

Далее Саймон сделал набросок доказательства (теорема 3.1, стр. 9), что классический алгоритм, оценивающий при не более 2 n / 4 различных дискретных значений, не может угадать монету с преимуществом лучше, чем 2 - n / 2, по сравнению с равномерным случайным предположением.$f$$2^{n/4}$$2^{-n/2}$

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

Алгоритм Deutsch-Jozsa служит подобной иллюстрацией к несколько иной проблеме искусственного изучения классов различной степени сложности, P и EQP, выяснить детали которого остается в качестве упражнения для читателя.

_{^* Simon's не имеет смысла для криптоанализа, потому что только непонятно запутанный идиот мог бы подать свой секретный ключ в квантовую схему противника для использования в квантовой суперпозиции входов, но по какой-то причине он вызывает всплеск каждый раз, когда кто-то публикует новую статью об использовании алгоритма Саймона сломать ключи идиотов воображаемым оборудованием, как все эти атаки работают. Исключение: возможно, это может сломать криптографию белого ящика , но история безопасности для криптографии белого ящика даже против классических противников не является многообещающей.}

Не уверен, что это именно то, что вы ищете; и я не знаю, что я бы квалифицировал это как «экспоненциальный» (я тоже не специалист по информатике, так что моя способность выполнять анализ алгоритмов более или менее отсутствует ...), но это недавний результат Bravyi et. Мы представили класс «2D-задач со скрытыми линейными функциями», в которых доказанно используется меньше ресурсов на квантовом параллельном устройстве.

$N\times N$$A$$b$$q$

$\log{N}$$>7/8$

Доказательство, по сути, сводится к тому, что классическому контуру сложно симулировать конкретное состояние графа, этот промежуточный результат был доказан несколько ранее . Затем в остальной части статьи показано, что в большом классе проблем есть эта сложная проблема.

$\neq$

$\textbf{BPP}^O \neq \textbf{BQP}^O$ $\neq$

Хотя я не могу предоставить формальное доказательство, имитация (временная эволюция) квантовой системы, как полагают, является таким случаем: не существует лучшего способа сделать это на классическом компьютере, чем в экспоненциальном времени, но квантовый компьютер может тривиально сделать это за полиномиальное время.

Идея такого квантового симулятора (см. Также статью в Википедии ) заключается в том, как квантовые компьютеры были впервые предложены.