Приблизительный подсчет проблем с захватом BQP

В модели черного ящика проблема определения выходного сигнала машины BPP на входе является приближенной задачей подсчета определения с аддитивной ошибкой 1/3 (скажем).$M(x,r)$$x$$E_r M(x,r)$

Есть ли похожая проблема для BQP? Этот комментарий Кена Ригана наводит на мысль о такой проблеме

Вы можете свести вопрос BPP к приближению к одной функции #P, но с помощью BQP вы получите разницу двух функций #P, назовите их и . Аппроксимация и отдельно не поможет вам приблизить когда близка к нулю!$f$$g$$f$$g$$f - g$$f - g$

BQP дает вам небольшую помощь: когда ответ на вопрос BQP на входе положительный , вы получите, что близко к квадратному корню из , где подсчет предикатов определяет и имеют m двоичных переменных после замены . (Здесь нет столбцов абсолютных значений; «магическим образом» вы всегда получаете . При общих представлениях квантовых цепей для BQP становится числом ворот Адамара.) Когда ответ отрицательный, разница близка к 0.$x$$f(x) - g(x)$$2^m$$f$$g$$x$$f(x) > g(x)$$m$

Можете ли вы точно сформулировать такую ​​проблему как можно ближе к BQP? Я надеюсь на что-то вроде: предоставленный черный ящик доступа к функциям отображающий на , с обещанием, что ... с точностью до .$f,g$$X$$Y$$f-g$$\varepsilon$

Эмануэле: К сожалению, мы не знаем ни одной проблемы черного ящика для захвата BQP, столь же простой, как та, которую вы упомянули для захвата BPP.

Интуитивно это объясняется тем, что трудно говорить о BQP, не вводя унитарность в той или иной форме. Возможность суммировать как положительные, так и отрицательные числа - это то, что делает BQP более мощным, чем BPP, но тогда унитарность - это то, что делает BQP менее мощным, чем #P! :-)

Сказав это, кроме Доусон и соавт. В статье, на которую ссылался Мартин Шварц, вы должны обязательно проверить это и это Джанцингом и Вочаном, которые дают «удивительно классически выглядящие» проблемы с обещаниями, которые охватывают BQP.

Также пусть S ⊆ {0,1} ⁿ и рассмотрим булеву функцию f: S → {0,1}. Тогда у меня есть гипотеза, сделанная много лет назад, которая гласит, что Q (f), сложность квантового запроса с ограниченной ошибкой для f, полиномиально связана с минимальной степенью действительного полинома p: R ⁿ → R, такой

(i) p (x) ∈ [0,1] для всех x∈ {0,1} ⁿ и

(ii) | p (x) -f (x) | ≤ ε для всех x∈S.

Если эта гипотеза верна, то «приближенная задача подсчета, фиксирующая BQP», будет просто аппроксимировать значение многочлена (n)-степени степени p: R ⁿ → R в указанной точке на булевом кубе, учитывая, что p ограничен везде на булевом кубе. Это может быть как можно ближе к ответу на ваш вопрос.

Эта статья подробно описывает идеи, изложенные выше.