Какие результаты делают квантовое пространство интересным?

Ограниченные во времени квантовые вычисления, очевидно, очень интересны. Как насчет квантовых вычислений, ограниченных пространством?

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

С другой стороны, было показано, что вероятностное и квантовое пространство с неограниченной ошибкой эквивалентны для любого конструируемого пространства (Watrous, 1999 и 2003 ). $s(n) \in \Omega(\log(n))$

Интересно, есть ли какие-то конкретные результаты, делающие квантовое пространство интересным ( исключая модели сублогарифмического пространства и автоматов).

(Мне известна эта запись: Квантовые аналоги классов сложности SPACE .)

quantum-computing space-bounded Абузер Якарылмаз
источник

Извините за невежество. Какова связь между ограниченным пространством квантовым вычислением и моделью квантового контура?

Алекс 'qubeat'

@ Alex'qubeat ': удобно использовать машины Тьюринга для ограниченных в пространстве вычислений. Схемная модель подходит для ограниченных по времени вычислений.

Abuzer Yakaryilmaz

Почему это удобнее? Это удобно в квантовом или классическом случае? С наивной точки зрения это неограниченное пространство, более удобное для (классических) машин Тьюринга.

Алекс 'qubeat'

@ Alex'qubeat ': это удобно как для классических, так и для квантовых случаев. Я настоятельно рекомендую вам основную статью по этому вопросу, написанную Стеарнсом, Хартманисом и Льюисом: «Иерархии вычислений с ограничением памяти» ( computer.org/portal/web/csdl/doi/10.1109/FOCS.1965.11 ). Вы также можете проверить обе статьи Watrous (упомянутые выше) и недавнюю статью Melkebeek and Watson ( theoryofcomputing.org/articles/v008a001 ).

Абузер Якарылмаз

Спасибо, я видел это, но есть также работа с использованием квантовых схем arxiv.org/abs/0908.1467, которая, по крайней мере, не страдает от необходимости управлять несколькими различными определениями QTM.

Алекс 'qubeat'

Какие результаты делают квантовое пространство интересным?

Ответы: