КМА

---

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

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

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

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

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

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

---