QMA

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

Взаимосвязь между QMA и BQP аналогична взаимосвязи между классами сложности NP и P ^{[ Цитация необходима ]}Полем Это также аналогично взаимосвязи между класс вероятностной сложности и 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 )$ больше, чем $c$ .
$\forall x\notin L$ , для всех квантовых состояний $|\psi \rangle$ , вероятность того, что V принимает вход $(|x\rangle ,|\psi \rangle )$ меньше, чем $с$ .

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

Класс сложности ${\mathsf {QMA}}$ определяется как равное ${\mathsf {QMA}}({2}/{3},1/3)$ Полем Тем не менее, константы не слишком важны, поскольку класс остается неизменным, если $и$ S $устанавливаются$ на любые константы, так что $C$ больше $S.$ C Более того, для любых полиномов $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-Hard, аналогичный NP-Hard , если каждая проблема в QMA может быть уменьшена до нее. Проблема, как говорят, завершена QMA, если она QMA-Hard и в QMA.

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

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

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

Генеральная задача k-local hamiltonian, учитывая K-локальный гамильтониан $H$ , чтобы найти наименьшее собственное значение $\lambda$ из $H$ . ^{[ 4 ]} $\lambda$ также называется основным государством энергии гамильтониана.

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

Местная гамильтонианская проблема является квантовым аналогом Max-Sat . Проблема K-локальной гамильтонианской проблемы является QMA-полной для k ≥ 2. ^{[ 5 ]}

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

Результаты QMA-Hardness известны для простых моделей Qubits , таких как ZX Hamiltonian ^{[ 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 ]}), который означает квантовый классический Мерлин Артур (или Мерлин Квант -Артур), похож на 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, поскольку проверка может заставить Prover отправить классическое доказательство, измеряя доказательства, как только они будут получены. Тот факт, что 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}}$ или наоборот.

Ссылки

^ Ааронов, Дорит ; Naveh, Tomer (2002). «Квант -NP - опрос». arxiv : Quant-ph/0210077v1 .
^ Jump up to: ^а ^{беременный} Watrous, John (2009). «Квантовая вычислительная сложность». В Мейерсе Роберт А. (ред.). Энциклопедия сложности и системной науки . С. 7174–7201. Arxiv : 0804.3401 . doi : 10.1007/978-0-387-30440-3_428 . ISBN 978-0-387-75888-6 Полем S2CID 1380135 .
^ Гарибиан, Севаг; Хуан, Йихен; Ландау, Зеф; Shin, Seung Woo (2015). «Квантовая гамильтонианская сложность». Основы и тенденции в теоретической информатике . 10 (3): 159–282. Arxiv : 1401.3916 . doi : 10.1561/040000000066 . S2CID 47494978 .
^ О'Доннел, Райан. «Лекция 24: QMA: Quantum Merlin Arthur» (PDF) . Получено 18 апреля 2021 года .
^ Кемпе, Джулия ; Китаев, Алексей ; Regev, Oded (2006). «Сложность местной гамильтонианской проблемы». Siam Journal on Computing . 35 (5): 1070–1097. arxiv : Quant-ph/0406180v2 . doi : 10.1137/s0097539704445226 . Полем
^ Оливейра, Роберто; Терхал, Барбара М. (2008). «Сложность квантовых спиновых систем на двумерной квадратной решетке». Квантовая информация и вычисления . 8 (10): 900–924. arxiv : Quant-ph/0504050 . Bibcode : 2005quant.ph..4050o . doi : 10.26421/QIC8.10-2 . S2CID 3262293 .
^ Ааронов, Дорит ; Готтесман, Даниэль ; Ирани, Сэнди; Кемпе, Джулия (2009). «Мощность квантовых систем на линии». Общение в математической физике . 287 (1): 41–65. Arxiv : 0705.4077 . Bibcode : 2009cmaph.287 ... 41a . doi : 10.1007/s00220-008-0710-3 . S2CID 1916001 .
^ Ааронов, Дорит; Готтесман, Даниэль; Ирани, Сэнди; Кемпе, Джулия (1 апреля 2009 г.). «Мощность квантовых систем на линии». Общение в математической физике . 287 (1): 41–65. Citeseerx 10.1.1.320.7377 . doi : 10.1007/s00220-008-0710-3 . S2CID 1916001 .
^ Бауш, Йоханнес; Кубит, Тоби; Озолс, Марис (ноябрь 2017 г.). «Сложность переводчиво инвариантных вращений с низким локальным измерением» . Анналес Анри Пуанкаре . 18 (11): 3449–3513. Arxiv : 1605.01718 . doi : 10.1007/s00023-017-0609-7 .
^ Biamonte, Jacob; Любовь, Питер (2008). «Реализуемые гамильтонианцы для универсальных адиабатических квантовых компьютеров». Физический обзор а . 78 (1): 012352. Arxiv : 0704.1287 . Bibcode : 2008 Phrva..78a2352b . doi : 10.1103/physreva.78.012352 . S2CID 9859204 . Полем
^ Юэн, Генри. «Сложность запутывания» (PDF) . henryyuen.net . Получено 20 апреля 2021 года .
^ Джайн, Рахул; Упадхьяй, Сарвагья; Watrous, John (2009). «Квантовые интерактивные доказательства с двумя местами в PSPace». Материалы 50 -го ежегодного симпозиума IEEE по фондам информатики (FOCS '09) . IEEE Computer Society. С. 534–543. Arxiv : 0905.1300 . doi : 10.1109/focs.2009.30 . ISBN 978-0-7695-3850-1 Полем S2CID 6869749 .
^ Watrous, John (2003). «PSPACE имеет постоянные квантовые интерактивные системы доказательства» . Теоретическая информатика . 292 (3): 575–588. doi : 10.1016/s0304-3975 (01) 00375-9 .
^ Джайн, Рахул; Джи, Чжэнфенг; Упадхьяй, Сарвагья; Watrous, John (2011). "QIP = pspace". Журнал ACM . 58 (6): A30. doi : 10.1145/2049697.2049704 . S2CID 265099379 .
^ Vyalyi, Mikhail N. (2003). «QMA = PP подразумевает, что PP содержит pH» . Электронный коллоквиум по вычислительной сложности .
^ Гарибиан, Севаг; Йирка, Джастин (2019). «Сложность моделирования локальных измерений в квантовых системах» . Квант . 3 : 189. Arxiv : 1606.05626 . doi : 10.22331/Q-2019-09-30-189 .

Внешние ссылки

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

[1] Ааронов, Дорит ; Naveh, Tomer (2002). «Квант -NP - опрос». arxiv : Quant-ph/0210077v1 .

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

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

[4] О'Доннел, Райан. «Лекция 24: QMA: Quantum Merlin Arthur» (PDF) . Получено 18 апреля 2021 года .

[5] Кемпе, Джулия ; Китаев, Алексей ; Regev, Oded (2006). «Сложность местной гамильтонианской проблемы». Siam Journal on Computing . 35 (5): 1070–1097. arxiv : Quant-ph/0406180v2 . doi : 10.1137/s0097539704445226 . Полем

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

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

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

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

[10] Biamonte, Jacob; Любовь, Питер (2008). «Реализуемые гамильтонианцы для универсальных адиабатических квантовых компьютеров». Физический обзор а . 78 (1): 012352. Arxiv : 0704.1287 . Bibcode : 2008 Phrva..78a2352b . doi : 10.1103/physreva.78.012352 . S2CID 9859204 . Полем

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

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

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

[14] Джайн, Рахул; Джи, Чжэнфенг; Упадхьяй, Сарвагья; Watrous, John (2011). "QIP = pspace". Журнал ACM . 58 (6): A30. doi : 10.1145/2049697.2049704 . S2CID 265099379 .

[15] Vyalyi, Mikhail N. (2003). «QMA = PP подразумевает, что PP содержит pH» . Электронный коллоквиум по вычислительной сложности .

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

v Т и Сложность классов
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL FL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete TFNP FNP AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system
List of complexity classes