Сложность зональных гамильтонианов

9

Недавно я подумал об «импорте» некоторых связанных с физикой вопросов в квантовую CS:

Понятие явления закона площади в гамильтоновых системах обычно означает локальный гамильтониан на некоторой решетке, у основного состояния которого есть свойство, при котором запутывание любой замкнутой области пропорционально поверхности области, а не ее объему (как это было бы для общего состояния). Известна гипотеза о том, все ли гамильтонианы с постоянными промежутками обладают этим свойством площади. Для одномерных систем на этот вопрос положительно ответил Гастингс (arXiv: 0705.2024).

Тем не менее, связь между такими системами и теорией сложности очень расплывчата: хотя результат Гастингса подразумевает, что 1-D системы, подчиняющиеся закону площади, могут быть классически смоделированы, для общих систем это неизвестно. Итак, мой вопрос: стоит ли пытаться решить гипотезу территориального права? Или, наоборот, можно ли придумать QMA-полный локальный гамильтониан, который также подчиняется закону площади. Небольшой взгляд на известные QMA-полные локальные гамильтонианы, которые по существу все основаны на квантовой теореме Кукаева-Левина, приводит к тому, что эти гамильтонианы не обладают свойством закона площади.

Суреш Венкат
источник
Нажмите клавишу Enter слишком быстро? :)
Даниэль Апон
Пожалуйста, игнорируйте мой голос, чтобы закрыть; Лиор заполнил остальную часть своего вопроса!
Даниэль Апон

Ответы:

10

Можно рассмотреть следующий слегка глупый пример двумерной системы, которая подчиняется закону области, которая является QMA-полной. Возьмем 2-мерную систему, один ряд которой равен одному из известных 1-мерных гамильтонианов, полных QMA (см. Ааронов, Готтесман, Ирани, Кемпе), а все остальные строки находятся в состоянии произведения. Затем это подчиняется закону площади (рассмотрим рисование прямоугольника, который включает данную строку, с k строками и l столбцами; переплетение ограничено постоянными временами l, а площадь также по меньшей мере равна l).

Однако это, на мой взгляд, определенно не означает, что доказательство закона области в 2d было бы бессмысленным с точки зрения сложности. Скорее, я думаю, что это означает, что нам нужно учитывать не только закон площади для энтропии запутывания, но и другие свойства запутывания. Одним из таких свойств будет наличие PEPS с полиномиальной размерностью связи. На самом деле, доказательство наличия закона площади в 2d не подразумевает наличие PEPS с полиномиальной размерностью связи. Импликация в 1d основана на том факте, что мы можем разрезать систему по различным связям, урезать до полиномиального ранга Шмидта по каждой связи и связать ошибку. Эта процедура не работает в 2d. Таким образом, доказательство существования PEPS для системы с пробелом в 2d будет следующим шагом. Мне кажется, что доказательство закона области в 2d было бы хорошим первым шагом к этому.

На самом деле, в физике конденсированных сред хорошо изучено, что существуют 2-мерные гамильтонианы без промежутков, подчиняющиеся закону площади. В то время как в 1d системы, которые описываются конформной теорией поля, имеют логарифмическое поведение энтропии запутанности, во 2d многие критические системы показывают закон площади, а затем бревна проявляются в подзадачах, поэтому энтропия равна L + const * log (L) + ... То есть, интересные, универсальные термины в энтропии - не ведущие, а подзадачи в таких 2-мерных теориях.

Мэтт Гастингс
источник
0

Спасибо за подробный и проницательный ответ и заострение различия между областью-законом и полиномиальной связью.


источник