На самом деле в исследованиях квантовых алгоритмов имеется немало работ по неабелевым задачам со скрытой подгруппой, поэтому я, конечно, надеюсь, что это не так!
Джо Фицсимонс
@Joe: я думал, что большая часть работы по неабелевым HSP была для групп, которые как-то «близки к абелевым» - но, пожалуйста, поправьте меня, если я не прав, так как я не эксперт в этой области. Но если это действительно так, то положительный ответ на вопрос может не противоречить тем работам, на которые вы ссылаетесь.
С другой стороны, BPP ^ {HSP} является содержащееся в СЗК, по крайней мере , если цель состоит в том, чтобы определить размер скрытой подгруппы. Это включает в себя даже абелеву HSP, хотя я не уверен, как именно найти генераторы произвольной скрытой подгруппы в SZK. Причина, по которой мы можем определить размер скрытой подгруппы, заключается в том, что если f: G-> S имеет скрытую подгруппу H, и мы выбираем g равномерно случайным образом из G, то f (g) является равномерно случайным по набору размеров | G | / | H |. В частности, f (g) имеет энтропию log | G | - журнал | H |. И оценка энтропии в СЗК.
Я понятия не имею, как можно было бы опровергнуть подобное утверждение, но я сомневаюсь, что это правда. У нас есть другие экспоненциальные ускорения с помощью квантовых алгоритмов, которые не основаны на абелевом HSP. Более того, абелев HSP не известен как BQP-полный.
С другой стороны, проблемы, которые, как известно, являются BQP-полными, представляют собой такие проблемы, как вычисление инвариантов узла, других инвариантов многообразия, функций разбиения и выполнение гамильтонового моделирования. С оракулом для любой из этих проблем, BPP будет таким же мощным, как BQP.
Наконец, я уверен, что можно построить разделение оракула между двумя упомянутыми вами классами, но это не будет справедливым способом сравнить их, поскольку один класс может выполнять квантовые запросы, а другой - нет, поэтому разделение просто отражает этот факт. ,
@ Джошуа: Эти разделения оракула в порядке, потому что они пытаются продемонстрировать силу квантовых запросов. Позвольте мне привести пример того, что я имею в виду. Если для 3SAT существовал алгоритм polytime, и пусть этот алгоритм называется X. Ясно, что P ^ X содержит NP. Тем не менее, мы можем построить разделение оракула между P ^ X и NP, потому что в первом случае только P-машина может получить доступ к оракулу, и разделение просто отражает тот факт, что недетерминированные запросы лучше, чем детерминированные запросы. Точно так же, даже если BPP ^ AHSP содержал BQP, мы могли бы довольно легко отделить их от оракула.
Робин Котари
2
Спасибо за ответы на все вопросы. В частности, спасибо за напоминание мне о полиномах Джонса и HOMFLY, которые не имеют ничего общего с HSP. Оценка полинома Джонса точно по пятым корням единства является # P-сложной, но аппроксимировать их с точностью до некоторой доли эпсилона с некоторой вероятностной точностью можно в BQP.
Джейсон
10
Я должен согласиться с Робином, что это не обязательно легко опровергнуть, хотя это почти наверняка неверно. Непосредственная причина, которая заставляет меня сомневаться, состоит в том, что поствыборные квантовые вычисления равны PP, и это, похоже, намекает на то, что статистику будет трудно воссоздать. У Скотта Ааронсона есть статья в STOC, показывающая, что существует проблема отношений оракула, которая разрешима в BQP, но не в PH.
Ответы:
Как и во многих разделениях класса сложности, мы полагаем, что ответ таков: BPP ^ {HSP}! = BQP, но мы можем только строго доказать это относительно оракулов. Такое разделение наблюдал Скотт Ааронсон в этом сообщении в блоге, где он заметил, что ускорение сварных деревьев по Чайлдсу, Клеве, Деотто, Фархи, Гутману и Спилману не содержалось в SZK.
С другой стороны, BPP ^ {HSP} является содержащееся в СЗК, по крайней мере , если цель состоит в том, чтобы определить размер скрытой подгруппы. Это включает в себя даже абелеву HSP, хотя я не уверен, как именно найти генераторы произвольной скрытой подгруппы в SZK. Причина, по которой мы можем определить размер скрытой подгруппы, заключается в том, что если f: G-> S имеет скрытую подгруппу H, и мы выбираем g равномерно случайным образом из G, то f (g) является равномерно случайным по набору размеров | G | / | H |. В частности, f (g) имеет энтропию log | G | - журнал | H |. И оценка энтропии в СЗК.
источник
Я понятия не имею, как можно было бы опровергнуть подобное утверждение, но я сомневаюсь, что это правда. У нас есть другие экспоненциальные ускорения с помощью квантовых алгоритмов, которые не основаны на абелевом HSP. Более того, абелев HSP не известен как BQP-полный.
С другой стороны, проблемы, которые, как известно, являются BQP-полными, представляют собой такие проблемы, как вычисление инвариантов узла, других инвариантов многообразия, функций разбиения и выполнение гамильтонового моделирования. С оракулом для любой из этих проблем, BPP будет таким же мощным, как BQP.
Наконец, я уверен, что можно построить разделение оракула между двумя упомянутыми вами классами, но это не будет справедливым способом сравнить их, поскольку один класс может выполнять квантовые запросы, а другой - нет, поэтому разделение просто отражает этот факт. ,
источник
Я должен согласиться с Робином, что это не обязательно легко опровергнуть, хотя это почти наверняка неверно. Непосредственная причина, которая заставляет меня сомневаться, состоит в том, что поствыборные квантовые вычисления равны PP, и это, похоже, намекает на то, что статистику будет трудно воссоздать. У Скотта Ааронсона есть статья в STOC, показывающая, что существует проблема отношений оракула, которая разрешима в BQP, но не в PH.
источник