КМА

В теории сложности вычислений , QMA что означает Quantum Merlin Arthur , представляет собой набор языков, для которых, когда строка находится в языке, существует квантовое доказательство полиномиального размера (квантовое состояние), которое убеждает полиномиального времени. верификатора квантового (работает на квантовом компьютере ) этого факта с высокой вероятностью. Более того, когда строка отсутствует в языке, каждое квантовое состояние полиномиального размера с высокой вероятностью отклоняется верификатором.

Связь между QMA и BQP аналогична взаимосвязи между классами сложности NP и P. ^{[ нужна ссылка ]}. Это также аналогично взаимосвязи вероятностного класса сложности MA и BPP. ^{[ нужна ссылка ]}.

QAM — это родственный класс сложности, в котором вымышленные агенты Артур и Мерлин выполняют последовательность действий: Артур генерирует случайную строку, Мерлин отвечает квантовым сертификатом , а Артур проверяет ее как машину BQP.

Определение [ править ]

Язык L находится в ${\mathsf {QMA}}(c,s)$ если существует полиномиальный верификатор квантового времени V и полиномиальный $p(x)$ такой, что: ^[1]^[2]^[3]

$\forall x\in L$ , существует квантовое состояние $|\psi \rangle$ такая, что вероятность того, что V примет входные данные $(|x\rangle ,|\psi \rangle )$ больше, чем $с$ .
$\forall x\notin L$ , для всех квантовых состояний $|\psi \rangle$ , вероятность того, что V примет входные данные $(|x\rangle ,|\psi \rangle )$ меньше, чем $с$ .

где $|\psi \rangle$ распространяется на все квантовые состояния с не более чем $p(|x|)$ кубиты.

Класс сложности ${\mathsf {QMA}}$ определяется как равный ${\mathsf {QMA}}({2}/{3},1/3)$ . Однако константы не слишком важны, поскольку класс остается неизменным, если $c$ и $s$ установлены на любые константы, такие, что $c$ больше, чем $s$ . Более того, для любых многочленов $q(n)$ и $r(n)$ , у нас есть

{\mathsf {QMA}}\left({\frac {2}{3}},{\frac {1}{3}}\right)={\mathsf {QMA}}\left({\frac {1}{2}}+{\frac {1}{q(n)}},{\frac {1}{2}}-{\frac {1}{q(n)}}\right)={\mathsf {QMA}}(1-2^{-r(n)},2^{-r(n)})

.

Проблемы в QMA [ править ]

Поскольку в QMA содержится много интересных классов, таких как P, BQP и NP, все задачи этих классов также относятся к QMA. Однако существуют проблемы, которые присутствуют в QMA, но не известны в NP или BQP. Некоторые такие хорошо известные проблемы обсуждаются ниже.

Задача называется QMA-сложной, аналогично NP-сложной любую задачу в QMA , если к ней можно свести . Задача называется QMA- полной , если она QMA-сложна и находится в QMA.

Локальная проблема Гамильтона [ править ]

k-локальный гамильтониан (квантовая механика) $H$ — эрмитова матрица, действующая на n кубитов, которую можно представить как сумму $m$ Гамильтоновы условия, действующие не более $k$ кубиты каждый.

$H=\sum _{i=1}^{m}H_{i}$

Общая k-локальная гамильтонианская проблема такова: для данного k-локального гамильтониана $H$ , чтобы найти наименьшее собственное значение $\lambda$ из $H$ . ^[4] $\lambda$ также называется энергией основного состояния гамильтониана.

Версия решения k-локальной гамильтоновой проблемы представляет собой тип проблемы обещания и определяется как, если задан k-локальный гамильтониан и $\alpha ,\beta$ где $\alpha >\beta$ , чтобы решить, существует ли собственное квантовое состояние $|\psi \rangle$ из $H$ с соответствующим собственным значением $\lambda$ , такой, что $\lambda \leq \beta$ или если $\lambda \geq \alpha$ .

Локальная гамильтонова задача является квантовым аналогом MAX-SAT . k-локальная гамильтонова задача является QMA-полной при k ≥ 2. ^[5]

2-локальная гамильтонова задача, ограниченная действием на двумерной сетке кубитов , также является QMA-полной. ^[6] Было показано, что проблема k-локального гамильтониана по-прежнему остается QMA-трудной даже для гамильтонианов, представляющих одномерную линию частиц с взаимодействиями ближайших соседей с 12 состояниями на частицу. ^[7]Если система трансляционно-инвариантна, ее локальная гамильтонова задача становится QMA _EXP -полной (поскольку входные данные задачи закодированы в размере системы, верификатор теперь имеет экспоненциальное время выполнения, сохраняя при этом тот же разрыв обещаний). ^[8]^[9]

Результаты QMA-твердости известны для простых решетчатых моделей кубитов , таких как гамильтониан ZX. ^[10] $H_{ZX}=\sum _{i}h_{i}Z_{i}+\sum _{i}\Delta _{i}X_{i}+\sum _{i<j}J^{ij}Z_{i}Z_{j}+\sum _{i<j}K^{ij}X_{i}X_{j}$ где $Z,X$ представляют матрицы Паули $\sigma _{z},\sigma _{x}$ . Такие модели применимы к универсальным адиабатическим квантовым вычислениям .

Проблемы с k-локальными гамильтонианами аналогичны классическим задачам удовлетворения ограничений . ^[11] Следующая таблица иллюстрирует аналогичные устройства между классическими CSP и гамильтонианами.

Классический	Квантовый	Примечания
Проблема удовлетворения ограничений	гамильтониан
Переменная	Кубит
Ограничение	Гамильтонов член
Назначение переменной	Квантовое состояние
Количество удовлетворенных ограничений	Энергетический член гамильтониана
Оптимальное решение	Основное состояние гамильтониана	Максимально возможные ограничения удовлетворяются

с QMA проблемы Другие

Список известных проблем, связанных с QMA, можно найти по адресу https://arxiv.org/abs/1212.6312 .

Связанные классы [ править ]

QCMA (или MQA ^[2]), что означает Quantum Classical Merlin Arthur (или Merlin Quantum Arthur), аналогичен QMA, но доказательством должна быть классическая строка. Неизвестно, равно ли QMA QCMA, хотя QCMA явно содержится в QMA.

QIP(k) , что означает квантовое интерактивное полиномиальное время (k сообщений), является обобщением QMA, где Мерлин и Артур могут взаимодействовать в течение k раундов. QMA — это QIP(1). Известно, что QIP(2) находится в PSPACE. ^[12]

QIP — это QIP(k), где k может быть полиномиальным по числу кубитов. Известно, что QIP(3) = QIP. ^[13] Также известно, что QIP = IP = PSPACE . ^[14]

Отношения с другими классами [ править ]

QMA связан с другими известными классами сложности следующими соотношениями:

{\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {MA}}\subseteq {\mathsf {QCMA}}\subseteq {\mathsf {QMA}}\subseteq {\mathsf {PP}}\subseteq {\mathsf {PSPACE}}

Первое включение следует из определения NP . Следующие два включения следуют из того, что верификатор в каждом случае делается более мощным. QCMA содержится в QMA, поскольку проверяющий может заставить доказывающую отправить классическое доказательство путем измерения доказательств, как только они будут получены. То, что QMA содержится в PP, показали Алексей Китаев и Джон Уотрус . Также легко показать, что PP находится в PSPACE .

Неизвестно, является ли какое-либо из этих включений безусловно строгим, поскольку неизвестно даже, содержится ли P строго в PSPACE или P = PSPACE. Однако наиболее известные на данный момент верхние границы QMA: ^[15]^[16]

{\mathsf {QMA}}\subseteq {\mathsf {A_{0}PP}}

и

{\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}

,

где оба ${\mathsf {A_{0}PP}}$ и ${\mathsf {P^{QMA[log]}}}$ содержатся в ${\mathsf {PP}}$ . Маловероятно, что ${\mathsf {QMA}}$ равно ${\mathsf {P^{QMA[log]}}}$ , поскольку это будет означать ${\mathsf {QMA}}={\mathsf {co}}$ - ${\mathsf {QMA}}$ . Неизвестно, является ли ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ или наоборот.

Ссылки [ править ]

^ Ааронов, Дорит ; Наве, Томер (2002). «Квантовый NP – Обзор». arXiv : Quant-ph/0210077v1 .
^ Jump up to: ^а ^б Уотрус, Джон (2009). «Квантовая вычислительная сложность». В Мейерсе, Роберт А. (ред.). Энциклопедия сложности и системных наук . стр. 7174–7201. arXiv : 0804.3401 . дои : 10.1007/978-0-387-30440-3_428 . ISBN 978-0-387-75888-6 . S2CID 1380135 .
^ Гарибян, Севаг; Хуан, Ичен; Ландау, Зеф; Шин, Сын У (2015). «Квантовая гамильтонова сложность». Основы и тенденции теоретической информатики . 10 (3): 159–282. arXiv : 1401.3916 . дои : 10.1561/0400000066 . S2CID 47494978 .
^ О'Доннел, Райан. «Лекция 24: QMA: Квантовый Мерлин Артур» (PDF) . Проверено 18 апреля 2021 г.
^ Кемпе, Джулия ; Китаев Алексей ; Регев, Одед (2006). «Сложность локальной гамильтоновой проблемы». SIAM Journal по вычислительной технике . 35 (5): 1070–1097. arXiv : Quant-ph/0406180v2 . дои : 10.1137/S0097539704445226 . .
^ Оливейра, Роберто; Терхал, Барбара М. (2008). «Сложность квантовых спиновых систем на двумерной квадратной решетке». Квантовая информация и вычисления . 8 (10): 900–924. arXiv : Quant-ph/0504050 . Бибкод : 2005quant.ph..4050O . дои : 10.26421/QIC8.10-2 . S2CID 3262293 .
^ Ааронов, Дорит ; Готтесман, Дэниел ; Ирани, Сэнди; Кемпе, Джулия (2009). «Сила квантовых систем на линии». Связь в математической физике . 287 (1): 41–65. arXiv : 0705.4077 . Бибкод : 2009CMaPh.287...41A . дои : 10.1007/s00220-008-0710-3 . S2CID 1916001 .
^ Ааронов, Дорит; Готтесман, Дэниел; Ирани, Сэнди; Кемпе, Джулия (1 апреля 2009 г.). «Сила квантовых систем на линии». Связь в математической физике . 287 (1): 41–65. CiteSeerX 10.1.1.320.7377 . дои : 10.1007/s00220-008-0710-3 . S2CID 1916001 .
^ Бауш, Йоханнес; Кабитт, Тоби; Озолс, Марис (ноябрь 2017 г.). «Сложность трансляционно-инвариантных спиновых цепей с низкой локальной размерностью» . Анналы Анри Пуанкаре . 18 (11): 3449–3513. arXiv : 1605.01718 . дои : 10.1007/s00023-017-0609-7 .
^ Биамонте, Джейкоб; С любовью, Питер (2008). «Реализуемые гамильтонианы для универсальных адиабатических квантовых компьютеров». Физический обзор А. 78 (1): 012352. arXiv : 0704.1287 . Бибкод : 2008PhRvA..78a2352B . дои : 10.1103/PhysRevA.78.012352 . S2CID 9859204 . .
^ Юэнь, Генри. «Сложность запутанности» (PDF) . henryyuen.net . Проверено 20 апреля 2021 г.
^ Джайн, Рахул; Упадхьяй, Сарвагья; Уотрус, Джон (2009). «Квантовые интерактивные доказательства с двумя сообщениями находятся в PSPACE». Материалы 50-го ежегодного симпозиума IEEE по основам информатики (FOCS '09) . Компьютерное общество IEEE. стр. 534–543. arXiv : 0905.1300 . дои : 10.1109/FOCS.2009.30 . ISBN 978-0-7695-3850-1 . S2CID 6869749 .
^ Уотрус, Джон (2003). «PSPACE имеет квантовые интерактивные системы доказательств с постоянным циклом» . Теоретическая информатика . 292 (3): 575–588. дои : 10.1016/S0304-3975(01)00375-9 .
^ Джайн, Рахул; Цзи, Чжэнфэн; Упадхьяй, Сарвагья; Уотрус, Джон (2011). «QIP = PSPACE». Журнал АКМ . 58 (6): А30. дои : 10.1145/2049697.2049704 . S2CID 265099379 .
^ Вялый, Михаил Н. (2003). «QMA = PP подразумевает, что PP содержит PH» . Электронный коллоквиум по вычислительной сложности .
^ Гарибян, Севаг; Йирка, Джастин (2019). «Сложность моделирования локальных измерений на квантовых системах» . Квантовый . 3 : 189. arXiv : 1606.05626 . doi : 10.22331/кв-2019-09-30-189 .

Внешние ссылки [ править ]

Ааронсон, Скотт. «Лекция PHYS771 13: Насколько велики квантовые состояния?» .
Гарибян, Севаг. «Лекция 5: Квантовый Мерлин Артур (QMA) и сильное снижение ошибок» (PDF) .
Зоопарк сложности : QMA

[1] Ааронов, Дорит ; Наве, Томер (2002). «Квантовый NP – Обзор». arXiv : Quant-ph/0210077v1 .

[JW-2] Jump up to: ^а ^б Уотрус, Джон (2009). «Квантовая вычислительная сложность». В Мейерсе, Роберт А. (ред.). Энциклопедия сложности и системных наук . стр. 7174–7201. arXiv : 0804.3401 . дои : 10.1007/978-0-387-30440-3_428 . ISBN 978-0-387-75888-6 . S2CID 1380135 .

[3] Гарибян, Севаг; Хуан, Ичен; Ландау, Зеф; Шин, Сын У (2015). «Квантовая гамильтонова сложность». Основы и тенденции теоретической информатики . 10 (3): 159–282. arXiv : 1401.3916 . дои : 10.1561/0400000066 . S2CID 47494978 .

[4] О'Доннел, Райан. «Лекция 24: QMA: Квантовый Мерлин Артур» (PDF) . Проверено 18 апреля 2021 г.

[5] Кемпе, Джулия ; Китаев Алексей ; Регев, Одед (2006). «Сложность локальной гамильтоновой проблемы». SIAM Journal по вычислительной технике . 35 (5): 1070–1097. arXiv : Quant-ph/0406180v2 . дои : 10.1137/S0097539704445226 . .

[6] Оливейра, Роберто; Терхал, Барбара М. (2008). «Сложность квантовых спиновых систем на двумерной квадратной решетке». Квантовая информация и вычисления . 8 (10): 900–924. arXiv : Quant-ph/0504050 . Бибкод : 2005quant.ph..4050O . дои : 10.26421/QIC8.10-2 . S2CID 3262293 .

[7] Ааронов, Дорит ; Готтесман, Дэниел ; Ирани, Сэнди; Кемпе, Джулия (2009). «Сила квантовых систем на линии». Связь в математической физике . 287 (1): 41–65. arXiv : 0705.4077 . Бибкод : 2009CMaPh.287...41A . дои : 10.1007/s00220-008-0710-3 . S2CID 1916001 .

[8] Ааронов, Дорит; Готтесман, Дэниел; Ирани, Сэнди; Кемпе, Джулия (1 апреля 2009 г.). «Сила квантовых систем на линии». Связь в математической физике . 287 (1): 41–65. CiteSeerX 10.1.1.320.7377 . дои : 10.1007/s00220-008-0710-3 . S2CID 1916001 .

[9] Бауш, Йоханнес; Кабитт, Тоби; Озолс, Марис (ноябрь 2017 г.). «Сложность трансляционно-инвариантных спиновых цепей с низкой локальной размерностью» . Анналы Анри Пуанкаре . 18 (11): 3449–3513. arXiv : 1605.01718 . дои : 10.1007/s00023-017-0609-7 .

[10] Биамонте, Джейкоб; С любовью, Питер (2008). «Реализуемые гамильтонианы для универсальных адиабатических квантовых компьютеров». Физический обзор А. 78 (1): 012352. arXiv : 0704.1287 . Бибкод : 2008PhRvA..78a2352B . дои : 10.1103/PhysRevA.78.012352 . S2CID 9859204 . .

[11] Юэнь, Генри. «Сложность запутанности» (PDF) . henryyuen.net . Проверено 20 апреля 2021 г.

[12] Джайн, Рахул; Упадхьяй, Сарвагья; Уотрус, Джон (2009). «Квантовые интерактивные доказательства с двумя сообщениями находятся в PSPACE». Материалы 50-го ежегодного симпозиума IEEE по основам информатики (FOCS '09) . Компьютерное общество IEEE. стр. 534–543. arXiv : 0905.1300 . дои : 10.1109/FOCS.2009.30 . ISBN 978-0-7695-3850-1 . S2CID 6869749 .

[13] Уотрус, Джон (2003). «PSPACE имеет квантовые интерактивные системы доказательств с постоянным циклом» . Теоретическая информатика . 292 (3): 575–588. дои : 10.1016/S0304-3975(01)00375-9 .

[14] Джайн, Рахул; Цзи, Чжэнфэн; Упадхьяй, Сарвагья; Уотрус, Джон (2011). «QIP = PSPACE». Журнал АКМ . 58 (6): А30. дои : 10.1145/2049697.2049704 . S2CID 265099379 .

[15] Вялый, Михаил Н. (2003). «QMA = PP подразумевает, что PP содержит PH» . Электронный коллоквиум по вычислительной сложности .

[16] Гарибян, Севаг; Йирка, Джастин (2019). «Сложность моделирования локальных измерений на квантовых системах» . Квантовый . 3 : 189. arXiv : 1606.05626 . doi : 10.22331/кв-2019-09-30-189 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

v т и Классы сложности
Считается возможным	ДЛОГТАЙМ переменного тока ⁰ АСС ⁰ ТК ⁰ л СЛ РЛ Флорида Нидерланды NL-полный Северная Каролина СК СС П P-полный ЗПП РП БПП Министерство национальной обороны АПХ ФП
Подозрение неосуществимое	ВВЕРХ НАПРИМЕР NP-полный NP-жесткий со-НП со-NP-полный ТФНП ФНП ЯВЛЯЮСЬ КМА PH ⊕P ПП #П #P-полное ИП PSPACE PSPACE-полный
Считается невозможным	ВРЕМЯ ЭКСПРЕСС СЛЕДУЮЩЕЕ ВРЕМЯ EXPSPACE 2-ВРЕМЯ ЭКСПЛУАТАЦИИ ЭЛЕМЕНТАРНЫЙ пиар Р РЭ ВСЕ
Иерархии классов	Полиномиальная иерархия Экспоненциальная иерархия Иерарх Гжегорчик Арифметическая иерархия Булева иерархия
Семьи классов	DTIME NTIME ДСПЕЙС НСПАСЕ Вероятностно проверяемое доказательство Интерактивная система доказательств
Список классов сложности