Квантовые аналоги классов сложности SPACE

Мы часто рассматриваем классы сложности, где мы ограничены количеством пространства, которое может использовать наша машина Тьюринга, например: или . Похоже, что в начале теории сложности были достигнуты большие успехи с этими классами, такими как теорема о пространственной иерархии и создание важных классов, таких как и . Есть ли аналогичные определения для квантовых вычислений? Или есть какая-то очевидная причина, почему квантовый аналог не был бы интересен? $\textbf{DSPACE}(f(n))$ $\textbf{NSPACE}(f(n))$ $\textbf{L}$ $\textbf{PSPACE}$

Кажется, что было бы важно иметь такой класс, как - квантовую версию : требовать логарифмическое число кубитов (или, возможно, квантовая ТМ использует логарифмическое пространство). $\textbf{QL}$ $\textbf{L}$

cc.complexity-theory complexity-classes quantum-computing space-bounded Артем Казнатчеев
источник

Упс, кажется, что квантовый аналог PSPACE уже определен: BQPSPACE и он равен PSPACE.

Артем Казнатчеев

Возможно, вы захотите проверить « Квантовую сложность, ограниченную пространством», Джона Уотроуса ( cs.uwaterloo.ca/~watrous/Papers/… )

Абель Молина,

@ Абель, это может быть ответом.

Суреш Венкат

Для пространственных классов над полиномиальным классом квантовые и классические классы равны. Что касается квантового логарифмического пространства, я не могу сказать много. Я предполагаю, что все, что мы можем сказать, это

L \subseteq B Q L \subseteq D S P A C E (\log^{2} n)

$L \subseteq BQL \subseteq DSPACE(\log^2 n)$

Робин Котари

@Suresh Конечно, я добавил ссылку в качестве ответа и включил часть информации в аннотацию.

Абель Молина

Ответы:

Возможно, вы захотите проверить квантовую сложность , ограниченную пространством , Джоном Уотроусом.

В результате получается, что для любого квантовая машина Тьюринга, работающая в пространстве может моделироваться вероятностной машиной Тьюринга с неограниченной ошибкой, работающей в пространстве . У вас также есть, что любая Квантовая машина Тьюринга, работающая в пространстве может быть смоделирована в $s=\Omega(\log n)$ $s$ $O(s)$ $s$ $NC^2(2^s) \subseteq DSPACE(s^2) \cap DTIME(2^{O(s)})$

Абель Молина
источник

Вы имеете в виду

? Кроме того, что такое

Ω (\log n)

$\Omega(\log n)$

N C^{2} (2^{s})

$NC^2(2^s)$

Робин Котари

N C^{2} (2^{s})

$NC^2(2^s)$

s

$s$

2^{O (s)}

$2^{O(s)}$

O (s^{2})

$O(s^2)$

N C^{2} (2^{s})

$NC^2(2^s)$

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

Abuzer Yakaryılmaz, AC Cem Say, “Квантовые вычисления с неограниченной ошибкой с малыми границами пространства”, Информация и вычисления, Vol. 209, pp.873-892, 2011. (немного более старая версия в arXiv: 1007.3624 )

Abuzer Yakaryılmaz, AC Cem Say, «Языки, распознаваемые недетерминированными квантовыми конечными автоматами», Квантовая информация и вычисления, Vol. 10, стр. 747-770, 2010. ( arXiv: 0902.2081 )

для случая неограниченной ошибки. Бумага

А. Амбайнис и Дж. Уотроус. Двусторонние конечные автоматы с квантовыми и классическими состояниями. Теоретическая информатика, 287 (1): 299–311, 2002 ( arXiv: cs / 9911009v1 )

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

Cem Say
источник