Читая некоторые недавние темы о квантовых вычислениях ( здесь , здесь и здесь ), я вспоминаю интересный вопрос о мощности некоторой машины, сохраняющей норму.
Для людей, работающих в области теории сложности, которые идут на квантовую сложность, хорошим вступительным текстом является статья Фортнау, ссылка на которую была размещена Джошуа Грохоу здесь . В этой статье квантовая машина Тьюринга представлена как обобщенная вероятностная машина Тьюринга. По сути, вероятностная машина имеет состояние нормализованное по , т.е. . Эволюция машины во времени определяется применением стохастической матрицы такой что , т. сохраняет . Таким образом, состояние в момент времени является ∥ s ∥ 1 = 1 P ∥ P s ∥ 1 = 1 P ℓ 1 t P t s(нотация может быть не точной, потому что умножение влево или вправо зависит от того, является ли вектором строки или столбца или строки или столбцы являются подпространствами, сохраняющими норму). Таким образом, в этом смысле вероятностная машина Тьюринга является сохранения обозначаемой .сек Р ℓ 1 М ℓ 1
Тогда квантовую машину Тьюринга можно рассматривать как имеющую состояние с и унитарной матрицей (которая сохраняет -нормы), такое, что - это состояние в момент времени где . Это машина сохранения обозначаемая .∥ s ∥ 2 = 1ℓ 2 P t s t ∥ P t s ∥ 2 = 1 ℓ 2 M ℓ 2
Пусть в общем случае машина обозначается через .М ℓ р
Итак, мои вопросы:
(1) Какова сила сохраняющих машин для конечного ? Более формально, можем ли мы доказать, что для любых заданных и , если то существует язык и машина такие, что эффективно решает и нет машины , которая эффективно решает . Например, это может быть обобщением вопроса, является ли ?
(2) Как насчет ? Здесь максимальное значение компонент вектора состояния равно 1.
(3) Эти вопросы выходят за рамки унитарности, поэтому не следует соглашаться с квантовой механикой. В общем, что происходит с вычислениями, если вы ослабляете ограничение унитарности операций? Есть работы о разрешении нелинейных операторов (см. Aaronson 2005 ).
(4) Может быть, самое главное, универсально ли это? Я думаю, что это понятно, потому что для частных случаев это универсально. Но что происходит с универсальностью, когда ?
источник
Ответы:
Это не полный ответ на вопросы, но это слишком долго, чтобы написать в качестве комментария. Это расширяет мой предыдущий комментарий.
Вопрос «Что происходит с вычислениями, если аксиомы квантовой механики немного модифицированы?» Очень подробно рассмотрен в забавной статье [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
источник
Была некоторая статья Ааронсона, в которой показано, что при в действительности не существует нормосохраняющих матриц. Но вместо этого можно рассматривать матрицы , которые не увеличивают ℓ р норму. Естественно, вы бы хотели, чтобы правило Борна давало вероятности | ψ я | стр . Проблема состоит в том, что если норма вектора состояния уменьшается, вероятности больше не составляют единицу. Ааронсон рассмотрел случай, когда вы должны перенормировать вектор после каждого шага (см. Ссылки в ответе @ Tsuyoshi выше). Я считаю, что вывод состоит в том, что эти машины будут иметь большую мощность.p∉{1,2} ℓp |ψi|p
источник