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

17

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

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

С другой стороны, было показано, что вероятностное и квантовое пространство с неограниченной ошибкой эквивалентны для любого конструируемого пространства (Watrous, 1999 и 2003 ).s(N)Ω(журнал(N))

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

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

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

Ответы:

5

Я думаю, что новый результат Амнона Та-Шмы - хороший ответ на мой собственный вопрос.

Ω(журнал2N)ε

Абузер Якарылмаз
источник