WikiDer > QMA

В теория сложности вычислений, QMA, что означает Квантовая Мерлин Артур, является квантовым аналогом маловероятной класс сложности НП или вероятностный класс сложности MA. Это связано с BQP таким же образом НП относится к п, или же MA относится к BPP.

Неформально это набор проблемы решения для которого, когда ответ - ДА, существует квантовое доказательство полиномиального размера (квантовое состояние), которое с высокой вероятностью убеждает квантового верификатора полиномиального времени в этом факте. Более того, когда ответ - НЕТ, каждое квантовое состояние полиномиального размера отклоняется верификатором с высокой вероятностью.

Точнее, доказательства должны быть проверены в полиномиальное время на квантовый компьютер, так что если ответ действительно ДА, проверяющий принимает правильное доказательство с вероятностью более 2/3, а если ответ НЕТ, то не существует доказательства, которое убеждает проверяющего принять его с вероятностью более 1/3. Как это обычно бывает, постоянные 2/3 и 1/3 можно изменять. Изменение 2/3 на любую константу строго между 1/2 и 1 или изменение 1/3 на любую константу строго между 0 и 1/2 не изменяет класс QMA.

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

Определение

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

• ${displaystyle forall xin L}$, существует квантовое состояние ${displaystyle | psi angle}$ такая, что вероятность того, что V примет вход ${displaystyle (| xangle, | psi angle)}$ больше, чем ${displaystyle c}$.
• ${displaystyle forall xotin L}$, для всех квантовых состояний ${displaystyle | psi angle}$, вероятность того, что V примет вход ${displaystyle (| xangle, | psi angle)}$ меньше чем ${displaystyle s}$.

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

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

${displaystyle {mbox {QMA}} left ({frac {2} {3}}, {frac {1} {3}} ight) = {mbox {QMA}} left ({frac {1} {2}} + {frac {1} {q (n)}}, {frac {1} {2}} - {frac {1} {q (n)}} ight) = {mbox {QMA}} (1-2 ^ { -r (n)}, 2 ^ {- r (n)})}$.

Проблемы в QMA

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

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

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

Локальная гамильтонова проблема является квантовым аналогом МАКС-СБ. Гамильтониан - это Эрмитова матрица действуя на квантовые состояния, таким образом ${displaystyle 2 ^ {n} imes 2 ^ {n}}$ для системы n кубиты. K-локальный гамильтониан - это гамильтониан, который можно записать как сумму гамильтонианов, каждый из которых нетривиально действует не более чем на k кубитов (вместо всех n кубитов).

K-локальная гамильтонова проблема, которая является проблема обещания, определяется следующим образом. Вход - это k-локальный гамильтониан, действующий на n кубитов, который представляет собой сумму полиномиально многих эрмитовых матриц, действующих только на k кубитов. Вход также содержит два числа ${displaystyle a$, так что ${displaystyle {frac {1} {b-a}} = O (n ^ {c})}$ для некоторой постоянной c. Проблема состоит в том, чтобы определить, меньше ли наименьшее собственное значение этого гамильтониана, чем ${displaystyle a}$ или больше чем ${displaystyle b}$, пообещал, что один из таких случаев.

K-локальный гамильтониан является QMA-полным при k ≥ 2.^[4]

Результаты определения твердости QMA известны даже простыми и физически реалистичными решетчатые модели из кубиты Такие как ^[5]${displaystyle H = sum _ {i} h_ {i} Z_ {i} + sum _ {i$ куда ${displaystyle Z, X}$ представляют Матрицы Паули ${displaystyle sigma _ {z}, sigma _ {x}}$. Такие модели применимы к универсальным адиабатические квантовые вычисления.

Гамильтонианы для QMA-полной задачи также можно ограничить, чтобы действовать на двумерной сетке кубиты^[6] или линия квантовых частиц с 12 состояниями на частицу.^[7]

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

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

Родственные классы

QCMA (или же MQA^[2]), что означает квантовый классический Мерлин Артур (или квантовый Мерлин Артур), похож на QMA, но доказательство должно быть классической струной. Неизвестно, равно ли QMA QCMA, хотя QCMA явно содержится в QMA.

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

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

Отношение к другим классам

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

${displaystyle {mathsf {P}} substeq {mathsf {NP}} substeq {mathsf {MA}} substeq {mathsf {QCMA}} substeq {mathsf {QMA}} substeq {mathsf {PP}} substeq {mathsf {PSPACE}} }$

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

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

${displaystyle {mathsf {QMA}} substeq {mathsf {A_ {0} PP}}}$ и ${displaystyle {mathsf {QMA}} substeq {mathsf {P ^ {QMA [log]}}}}$,

где оба ${displaystyle {mathsf {A_ {0} PP}}}$ и ${displaystyle {mathsf {P ^ {QMA [журнал]}}}}$ содержатся в ${displaystyle {mathsf {PP}}}$. Вряд ли ${displaystyle {mathsf {QMA}}}$ равно либо ${displaystyle {mathsf {A_ {0} PP}}}$ или же ${displaystyle {mathsf {P ^ {QMA [журнал]}}}}$, поскольку равенство с первым разрушило бы Полиномиально-временная иерархия (PH), а равенство с последним означало бы ${displaystyle {mathsf {QMA}} = {mathsf {co}}}$-${displaystyle {mathsf {QMA}}}$. Неизвестно, были ли ${displaystyle {mathsf {P ^ {QMA [log]}}} subteq {mathsf {A_ {0} PP}}}$ или наоборот.

Рекомендации

внешняя ссылка

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