QMA

В теории сложности вычислений , QMA , которая выступает за Quantum Merlin Артура , является квантовым аналогом неслучайного класса сложности NP или вероятностного класс сложности М . Это связано с BQP так же, как NP связано с P , или MA связано с BPP .

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

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

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

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

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

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

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

Класс сложности определяется равным . Однако константы не слишком важны, поскольку класс остается неизменным, если и для него заданы любые константы, такие, что больше, чем . Более того, для любых многочленов и имеем${\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}}\right)={\mbox{QMA}}\left({\frac {1}{2}}+{\frac {1}{q(n)}},{\frac {1}{2}}-{\frac {1}{q(n)}}\right)={\mbox{QMA}}(1-2^{-r(n)},2^{-r(n)})}$.

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

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

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

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

Локальная гамильтонова проблема является квантовым аналогом MAX-SAT . Гамильтониан - это эрмитова матрица, действующая на квантовые состояния, то есть для системы из n кубитов . K-локальный гамильтониан - это гамильтониан, который можно записать как сумму гамильтонианов, каждый из которых нетривиально действует не более чем на k кубитов (вместо всех n кубитов).${\displaystyle 2^{n}\times 2^{n}}$

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

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

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

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

Другие проблемы 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. ^[10]

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

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

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

${\displaystyle {\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 - это ^{[13] [14]}

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

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

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

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

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