Существуют ли описательные представления сложности классов квантовой сложности?

20

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

Теоретики описательной сложности, такие как Иммерман и Фагин, охарактеризовали многие из наиболее известных классов сложности с использованием логики. Например, NP может характеризоваться экзистенциальными запросами второго порядка; P можно охарактеризовать запросами первого порядка с добавленным оператором наименьшей фиксированной точки.

Мой вопрос: были ли какие-либо попытки, особенно успешные, придумать такие представления для классов квантовой сложности, как BQP или NQP? Если нет, то почему нет?

Спасибо.

Обновление (модератор) : этот вопрос полностью ответил на этот пост на mathoverflow .

Филип Уайт
источник
1
см. вопрос Каве о МО: mathoverflow.net/questions/35236/…
Алессандро
1
закрыть как дубликат?
Суреш Венкат
3
Тем, кто задается вопросом, почему этот вопрос был закрыт как не по теме (как я): Игнорируйте близкую причину, потому что она бессмысленна (пока этот вопрос касается). Закрытие вопроса требует одной из нескольких причин. «Точная копия» была бы подходящей причиной, но система не позволяет нам закрыть вопрос как точную копию вопроса о MathOverflow. Поэтому я предполагаю, что Суреш выбрал одну из доступных причин случайным образом.
Цуёси Ито
1
ps: я думаю, что было бы разумно рассмотреть эти случаи подобно перекрестной публикации и не закрывать их. Кто-то (например, OP) публикует CW-ответ на основании (или просто ссылки на) ответа на MO.
Каве
2
Я вновь открыл вопрос.
Райан Уильямс

Ответы:

7

Я думаю, что ответ Робинса на мой вопрос о МО также отвечает на этот.

Описательная сложность характеристика класса сложности дает язык , чьи запросы (т.е. формулы) в точности функции вычислимый C . Синтаксис языка, как правило, очень прост, т.е., учитывая строку q, легко проверить, является ли q правильно сформированным запросом языка, по крайней мере ожидается, что он будет решаем (но обычно проверка синтаксиса может быть выполнена в класс малой сложности). Это повлечет за собой эффективное enumerablity проблем в классе С и даст синтаксическую характеристику для C . (Если сложность проверки синтаксиса низкая, это также может означать существование полной проблемы для класса.)CCqqCC

В приведенных выше замечаний, Робин связан с Корд Eickmeyer и бумаги Мартина Grohe в « рандомизации и Derandomization в описательной теории сложности » , которая дает «описательная сложность» характеристику . Сами авторы отмечают во введении, что это отличается от того, что обычно подразумевается под описательной характеристикой сложности:BPP

Мы доказываем, что , вероятностный вариант логики с фиксированной точкой со счетом, захватывает класс сложности B P P даже на неупорядоченных структурах. Для упорядоченных структур этот результат является прямым следствием теоремы Иммермана-Варди [7, 8], а для произвольных структур из наблюдения следует, что мы можем определить случайный порядок с высокой вероятностью в BPIFP + C. Тем не менее, результат удивительно на первый взгляд , из -за его сходства с открытым вопрос о том , существует ли логика захвата Р , и потому , что , как полагают , что P = B P P .BPIFP+CBPPPP=BPP Ограничение в том , что логика не имеет эффективный синтаксис и , следовательно , не является «логика» в соответствии с [9] определением Гуревича , лежащим в основе вопроса для логики , которая захватывает P . BPIFP+CPТем не менее, мы считаем, что дает вполне адекватное описание класса сложности B P P , поскольку определение B P P также по своей сути неэффективно (в отличие от определения P в терминах разрешимого набор полиномиально синхронизированных машин Тьюринга).BPIFP+CBPPBPPP

SO(TC)PSpaceBQPBQPBQP

Кава
источник
8

PσσσMφMφσR1,R2,

σσρσρ, Это мой раздел «Определение 1» в статье Эйкмейера-Гроэ, на которую ссылается Робин Котари. В частности, словарь не конечен (ну, каждый словарь есть, но мы должны учитывать бесконечно много разных словарей), набор предложений этой логики неразрешим, а понятие выполнимости отличается от того, которое выдвинул Гуревич. ,

Аарон Стерлинг
источник