норма сохраняя машины Тьюринга

20

Читая некоторые недавние темы о квантовых вычислениях ( здесь , здесь и здесь ), я вспоминаю интересный вопрос о мощности некоторой машины, сохраняющей p норму.

Для людей, работающих в области теории сложности, которые идут на квантовую сложность, хорошим вступительным текстом является статья Фортнау, ссылка на которую была размещена Джошуа Грохоу здесь . В этой статье квантовая машина Тьюринга представлена ​​как обобщенная вероятностная машина Тьюринга. По сути, вероятностная машина имеет состояние s нормализованное по , т.е. . Эволюция машины во времени определяется применением стохастической матрицы такой что , т. сохраняет . Таким образом, состояние в момент времени являетсяs 1 = 1 P P s 1 = 1 P 1 t P t s1s1=1PPs1=1P1tPts(нотация может быть не точной, потому что умножение влево или вправо зависит от того, является ли вектором строки или столбца или строки или столбцы являются подпространствами, сохраняющими норму). Таким образом, в этом смысле вероятностная машина Тьюринга является сохранения обозначаемой .сек Р 1 М 1PsP1M1

Тогда квантовую машину Тьюринга можно рассматривать как имеющую состояние с и унитарной матрицей (которая сохраняет -нормы), такое, что - это состояние в момент времени где . Это машина сохранения обозначаемая .s 2 = 1ss2=12 P t s t P t s 2 = 1 2 M 2P2PtstPts2=12M2

Пусть в общем случае машина обозначается через .М рpMp

Итак, мои вопросы:

(1) Какова сила сохраняющих машин для конечного ? Более формально, можем ли мы доказать, что для любых заданных и , если то существует язык и машина такие, что эффективно решает и нет машины , которая эффективно решает . Например, это может быть обобщением вопроса, является ли ?pppqq>pLMqMqLMpLNPBQP

(2) Как насчет ? Здесь максимальное значение компонент вектора состояния равно 1.p=

(3) Эти вопросы выходят за рамки унитарности, поэтому не следует соглашаться с квантовой механикой. В общем, что происходит с вычислениями, если вы ослабляете ограничение унитарности операций? Есть работы о разрешении нелинейных операторов (см. Aaronson 2005 ).

(4) Может быть, самое главное, универсально ли это? Я думаю, что это понятно, потому что для частных случаев это универсально. Но что происходит с универсальностью, когда ?p=

Маркос Вильягра
источник
4
Очень интересная статья Скотта Ааронсона. Является ли квантовая механика островом в теоретическом пространстве? scottaaronson.com/papers/island.pdf
Цуёси Ито
1
Цуёси, не могли бы вы превратить это в ответ? Похоже, что Скотт напрямую отвечает на вопрос Маркоса. Посмотрите на предложение 5 в газете ...
Райан Уильямс
Еще не прочитал его полностью, но, кажется, он отвечает на вопросы (1) и (3) выше.
Маркос Вильягра
@ Райан: Готово. В следующий раз добавьте знак «at» перед именем, чтобы он отображался на странице «Ответы».
Цуёси Ито

Ответы:

21

Это не полный ответ на вопросы, но это слишком долго, чтобы написать в качестве комментария. Это расширяет мой предыдущий комментарий.

Вопрос «Что происходит с вычислениями, если аксиомы квантовой механики немного модифицированы?» Очень подробно рассмотрен в забавной статье [Aar04] Скотта Ааронсона. Я полагаю, что на ваши вопросы в основном ответили в первой половине Раздела 2 [Aar04].

Ааронсон показывает, что если p> 0 и p ≠ 2, то матрица, которая сохраняет p-норму для всех векторов, обязательно является обобщенной матрицей перестановок (произведением матрицы перестановок и диагональной матрицы). Он утверждает, что то же самое имеет место в случае p = ∞. Все это верно как для over, так и для ℂ. Отметим, что это включает случай p = 1: стохастические матрицы сохраняют 1-норму для неотрицательных векторов, но не для всех векторов в целом.

Я предполагаю, что вероятностная машина Тьюринга, обобщенная, как в [For00], имеет обобщенную матрицу перестановок в качестве своей матрицы глобального перехода, только если она является детерминированной машиной Тьюринга, но у меня нет под рукой доказательства.

Аарсон обсуждает также несколько других модификаций аксиом квантовой механики в статье. Например, если мы изменим правило измерения (вместо набора разрешенных ворот) так, чтобы результат x происходил с вероятностью | α x | p / ∑ y | α y | p , где α y - амплитуда | y⟩, тогда этот «квантовый компьютер» может решать любые задачи в PP (включая NP-полные задачи) за полиномиальное время, если только p = 2 (предложение 5).

Ссылки

[Aar04] Скотт Ааронсон. Является ли квантовая механика островом в теоретическом пространстве? В материалах конференции Växjö «Квантовая теория: пересмотр оснований», 2004. arXiv: quant-ph / 0401062 v2.

[For00] Лэнс Фортноу. Один взгляд теоретика сложности на квантовые вычисления. В вычислительной технике: Австралазийский симпозиум по теории (CATS 2000), с. 58–72, январь 2000 г. http://dx.doi.org/10.1016/S1571-0661(05)80330-5

Цуёси Ито
источник
1
Для меня это лучшее обоснование того, почему это квадрат амплитуды, а не 4-я или более высокая степень. Хотелось бы мне знать о таких результатах, когда я впервые изучал QM, и выбор квадрата казался таким произвольным.
Артем Казнатчеев
0

Была некоторая статья Ааронсона, в которой показано, что при в действительности не существует нормосохраняющих матриц. Но вместо этого можно рассматривать матрицы , которые не увеличивают р норму. Естественно, вы бы хотели, чтобы правило Борна давало вероятности | ψ я | стр . Проблема состоит в том, что если норма вектора состояния уменьшается, вероятности больше не составляют единицу. Ааронсон рассмотрел случай, когда вы должны перенормировать вектор после каждого шага (см. Ссылки в ответе @ Tsuyoshi выше). Я считаю, что вывод состоит в том, что эти машины будут иметь большую мощность.p{1,2}p|ψi|p

p12Ω(N1/p)pq1/p+1/q=1pp

Дэн Шталке
источник