Последствия ?

20

Хотя теорема Адлемана показывает, что , мне неизвестна литература, исследующая возможное включение . Какие теоретически сложные последствия будет иметь такое включение?B Q PP / полиBPPP/polyBQPP/poly

Теорема Адлемана иногда называется «прародителем аргументов дерандомизации». считается дерандомизируемым, в то время как нет никаких доказательств того, что «квантовость» можно каким-то образом удалить. Является ли это возможным доказательством того, что вряд ли будет в ?BPPB Q P P / полиBQPBQPP/poly

Мартин Шварц
источник

Ответы:

14

Я бы сказал, что у нас нет веских причин думать, что BQP в P / Poly. У нас есть основания полагать, что BQP находится не в P / poly, но они более или менее идентичны нашим основаниям считать, что BQP ≠ BPP. Например, если BQP⊂P / poly, тогда Factoring находится в P / poly, что достаточно для взлома большого количества криптографии в соответствии со стандартными определениями безопасности.

Кроме того, как вы правильно заметили, нет квантового аналога уловки Адлемана - на самом деле, нет способа «извлечь квантовость из квантового алгоритма», аналогичного тому, как можно извлечь случайность из рандомизированного алгоритма. Поэтому я не думаю, что у кого-то есть догадки о том, из чего вообще должен состоять совет P / poly по моделированию квантового компьютера (больше, чем у них есть предположение, скажем, в случае NP против P / poly).

Последнее замечание: мою работу с Алексом Архиповым (и независимую работу Бремнера-Джозе-Шепарда) можно легко адаптировать, чтобы показать, что если QUANTUM-SAMPLING находится в P / poly (ОК, в «BPP-SAMPLING / poly») , тогда P #P ⊂BPP NP / poly и, следовательно, полиномиальная иерархия разрушается - в этом случае, я думаю, до четвертого уровня. В настоящее время, однако, мы не знаем, как адаптировать результаты такого рода из задач выборки к решению проблем.

Скотт Ааронсон
источник
2
Большое спасибо за ответ, Скотт! Мне интересно одно: каковы известные результаты, связывающие P ^ # P с уровнями PH / poly? Что на самом деле известно о P ^ # P против PH / поли? (Например, существует ли какая-то неоднородная версия теоремы Тоды?). Зачем P ^ # P в PH / poly свернуть PH / poly, если мы не знаем PH / poly в P ^ # P? Или чего мне не хватает?
Мартин Шварц
1
Здесь нужно обобщить доказательство теоремы Карпа-Липтона. В качестве первого шага нетрудно показать (используя рассуждения в стиле KL), что если coNP находится в NP / poly, то PH падает до 3-го уровня. Но тогда это должно быть релятивизировано, чтобы показать, что если coNP ^ NP ^ NP находится в NP ^ NP ^ NP / poly, то PH падает до 5-го уровня. И, конечно, P ^ # P в BPP ^ NP / poly подразумевает, что coNP ^ NP ^ NP находится в NP ^ NP ^ NP / poly. Но, хм, у меня только провал до 5-го уровня здесь! Предполагая, что это правильно, кто-нибудь может улучшить его до краха 4-го уровня? (Если нет, то это «самый высокий» коллапс PH, который я когда-либо видел! :))
Скотт Ааронсон
1
3-й уровень подойдет. И и Карп-Липтон релятивизируются, поэтому сначала и, во-вторых, если , то . Б Р Р Н Р / р ö л у = P N P / р о л у Σ P 2( Б Р ) Р Н Р / р о л у Е Р 3 = Π П 3BPPP/polyBPPNP/poly=PNP/polyΣ2P(BP)PNP/polyΣ3P=Π3P
Эмиль Йержабек поддерживает Монику
1
(И различные известные укрепления KL также релятивизируются в этом отношении, в частности, предположение выше фактически сворачивает PH в , за исключением того, что я никогда не видел с индексом, отличным от 2, так что, скорее всего, это нестандартная запись.) S PS3PZPPNPNPΣ3PΠ3PSP
Эмиль Йержабек поддерживает Monica