Краткий ответ: да

Нужно быть немного более осторожным при постановке вопроса. Думая о том, что схема состоит из подготовки состояния, унитарных элементов и измерений, в принципе всегда можно «спрятать» все, что мы хотим, например запутывающие операции, внутри измерения. Итак, давайте будем точными. Мы хотим начать с отделимого состояния множества кубитов, и окончательные измерения должны состоять из измерений с одним кубитом. Должно ли вычисление переходить через запутанное состояние в какой-то момент вычисления?

Чистые состояния

Давайте сделаем еще одно предположение, что начальное состояние является чистым (продуктовым) состоянием. В этом случае система должна пройти через запутанное состояние. Если этого не произойдет, то будет легко смоделировать вычисления на классическом компьютере, потому что все, что вам нужно сделать, - это сохранить чистых однокбитных состояний в памяти и обновлять их по одному по мере выполнения вычислений. $n$

Можно даже спросить, сколько запутывания необходимо. Опять же, есть много разных способов, которыми запутанность можно перемещать в разное время. Хорошей моделью, которая обеспечивает достаточно справедливую меру присутствия запутанности, являются квантовые вычисления на основе измерений . Здесь мы подготавливаем некоторое начальное состояние ресурса, и именно измерения в одном кубите определяют вычисление, которое происходит. Это позволяет нам задавать вопросы о запутанности состояния ресурса. Должно быть запутывание, и, в некотором смысле, оно должно быть как минимум «двумерным», это не может быть просто запутывание, генерируемое между ближайшими соседями системы на линии [ref] . Более того, можно показать, что большинство состояний из кубитов слишком запутаны $n$ разрешить вычисления таким образом.

Смешанные состояния

Предостережение во всем, что я до сих пор говорил, заключается в том, что мы говорим о чистых состояниях. Например, мы можем легко смоделировать незапутывающее вычисление для чистых состояний продукта. Но как насчет смешанных государств? Смешанное состояние отделимо, если его можно записать в виде Важно отметить, что нет ограничения на значение , количество слагаемых в сумме. Если число слагаемых в сумме мало, то, исходя из предыдущего аргумента, мы можем смоделировать эффекты незапутывающей схемы. Но если число терминов велико, то (насколько мне известно) остается открытым вопрос о том, может ли оно быть классически смоделировано или оно может дать улучшенные вычисления.

ρ = \sum_{i = 1}^{N} p_{i} ρ_{i}^{(1)} \otimes ρ_{i}^{(2)} \otimes \dots \otimes ρ_{i}^{(n)} .

$\rho=\sum_{i=1}^Np_i\rho^{(1)}_i\otimes\rho^{(2)}_i\otimes\ldots\otimes\rho^{(n)}_i.$

N

$N$

DaftWullie
источник

Эта работа ( arxiv.org/pdf/quant-ph/0301063.pdf ) может быть интересна здесь. Запутывание в квантовой системе должно масштабироваться как многочлен от размера системы, чтобы ускорить экспоненциальную квантовую скорость. Квантовый алгоритм может быть классически смоделирован с ресурсами, которые масштабируются как с показателем запутанности.

бирьяни

хотя неэкспоненциальные ускорения, такие как Гровер, могут сойти с рук с небольшим количеством запутывания, моя собственная работа .

DaftWullie

Что вы думаете об этой статье ? У меня не было времени, чтобы пройти через это тщательно, но там говорится, что Гровера можно обойтись без запутывания (на более медленных скоростях).

Стивен

@ StevenSagona Это своего рода чит / рекламный ход. Хотя мы обычно говорим о кубитах с гильбертовым пространством размерности , вы можете получить это гильбертово пространство, используя одну частицу с гильбертовым пространством размерности (например, отправив частицу по различным путям) и, конечно, здесь нет запутанности (на самом деле, существует философский вопрос о суперпозиции / запутывании на основе пути). Это преобразование связано с затратами, но при использовании модели оракула, как и в модели Гровера, эти затраты скрываются, и, похоже, достигается то же самое.

n

$n$

2^{n}

$2^n$

2^{n}

$2^n$

2^{n}

$2^n$

DaftWullie

Ах я вижу. Спасибо за ответ, это фактически решает некоторые концептуальные вопросы в моей голове (поскольку для меня не было очевидным, почему простого наложения одной частицы недостаточно для обеспечения тех же механизмов, что и в этих запутанных системах).

Стивен

Необходима ли запутанность для квантовых вычислений?

Ответы:

Чистые состояния

Смешанные состояния