Почему BQPSPACE в PSPACE, если он может иметь вдвое экспоненциально большое время работы?

11

Стандартное доказательство того, что BQPSPACE находится в PSPACE, основано на анализе типа игры Савича на интегралах пути. Однако предполагается, что длительность BQPSPACE не должна превышать экспоненциально большую длину. Это верно для PSPACE, но для замкнутых квантовых систем с фиксированным числом степеней свободы, как правило, требуется вдвое экспоненциальное время, прежде чем повторение Пуанкаре из-за экспоненциальной природы вектора состояния. Итак, доказательство все еще проходит или нет?

Пушка Лутин
источник

Ответы:

2

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

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

Джошуа Кук
источник