QMA

QMA는 양자 멀린 아서(영어: Quantum Merlin Arthur)의 약자로, 계산 복잡도 이론에서의 복잡도 종류를 의미한다. 이는 다음 속성을 만족하는 모든 형식 언어의 집합이다.

1. 만약 어떤 문자열이 언어에 포함된다면, 해당 사실을 높은 확률로 확신시켜 줄 수 있는 다항 크기의 양자 증명(양자 상태로 표현 가능)이 다항 시간 양자 검증자(양자 컴퓨터에서 실행)에게 존재한다.
2. 만약 어떤 문자열이 언어에 포함되지 않는다면, 모든 다항 크기의 양자 상태는 검증자에 의해 높은 확률로 거부된다.

QMA와 BQP 사이의 관계는 NP와 P라는 복잡도 종류 사이의 관계와 유사하다. 또한 이는 확률적 복잡도 종류인 MA와 BPP 사이의 관계와도 유사하다.

QAM은 관련된 복잡도 종류로, 허구의 인물인 아서와 멀린이 다음과 같은 순서를 수행한다. 아서가 임의의 문자열을 생성하고, 멀린이 양자 인증서로 응답하며, 아서가 이를 BQP 기계로서 검증한다.

정의

언어 L이 ${\displaystyle {\mathsf {QMA}}(c,s)}$에 속한다는 것은 다항 시간 양자 검증자 V와 다항식 ${\displaystyle p(x)}$가 존재하여 다음과 같은 만족함을 의미한다.

• ${\displaystyle \forall x\in L}$에 대하여, 검증자 V가 입력 ${\displaystyle (|x\rangle ,|\psi \rangle )}$를 수락할 확률이 c보다 큰 양자 상태 ${\displaystyle |\psi \rangle }$가 존재한다.
• ${\displaystyle \forall x\notin L}$에 대하여, 그리고 최대 ${\displaystyle p(|x|)}$개의 큐비트를 가진 모든 양자 상태 ${\displaystyle |\psi \rangle }$에 대하여, 검증자 V가 입력 ${\displaystyle (|x\rangle ,|\psi \rangle )}$를 수락할 확률은 s보다 작다.

복잡도 종류 ${\displaystyle {\mathsf {QMA}}}$는 ${\displaystyle {\mathsf {QMA}}({2}/{3},1/3)}$과 동일하게 정의된다. 그러나 c가 s보다 크기만 하다면 상수를 어떻게 설정해도 해당 종류는 변하지 않으므로 상수 값은 크게 중요하지 않다. 더욱이 임의의 다항식 ${\displaystyle q(n)}$과 ${\displaystyle r(n)}$에 대하여 다음이 성립한다.

${\displaystyle {\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의 문제들

P, BQP, NP와 같이 흥미로운 많은 종류가 QMA에 포함되어 있으므로, 해당 종류의 모든 문제 역시 QMA에 포함된다. 그러나 QMA에는 속하지만 NP나 BQP에 속하는지는 알려지지 않은 문제들도 존재한다. 잘 알려진 몇 가지 문제는 다음과 같다.

QMA에 있는 모든 문제가 특정 문제로 환산될 수 있다면, 그 문제는 NP-난해와 유사하게 QMA-난해(QMA-hard)라고 한다. 어떤 문제가 QMA-난해이면서 동시에 QMA에 속한다면, 그 문제를 QMA-완전이라고 한다.

관련 종류

QCMA(또는 MQA)는 양자 고전 멀린 아서(Quantum Classical Merlin Arthur)의 약자로, QMA와 유사하지만 증명이 고전적인 문자열이어야 한다. QCMA가 QMA에 포함되는 것은 자명하지만, QMA와 QCMA가 동일한지는 알려져 있지 않다.

QIP(k)는 양자 대화형 다항 시간 (k 메시지)의 약자로, 멀린과 아서가 k 라운드 동안 상호작용할 수 있는 QMA의 일반화이다. QMA는 QIP(1)이다. QIP(2)는 PSPACE에 속하는 것으로 알려져 있다.

QIP는 k가 큐비트 수의 다항식이 될 수 있는 QIP(k)이다. QIP(3) = QIP임이 알려져 있다. 또한 QIP = IP = PSPACE임이 알려져 있다.

다른 종류와의 관계

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에 대한 최선의 상한은 다음과 같다.

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

여기서 ${\displaystyle {\mathsf {A_{0}PP}}}$와 ${\displaystyle {\mathsf {P^{QMA[log]}}}}$ 둘 다 ${\displaystyle {\mathsf {PP}}}$에 포함된다. ${\displaystyle {\mathsf {QMA}}={\mathsf {P^{QMA[log]}}}}$가 성립하면 ${\displaystyle {\mathsf {QMA}}={\mathsf {co}}}$-${\displaystyle {\mathsf {QMA}}}$를 의미하게 되므로, 이 등식은 성립할 가능성이 낮다. ${\displaystyle {\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}}$인지, 혹은 그 반대인지는 알려져 있지 않다.

각주

외부 링크

• Aaronson, Scott. “PHYS771 Lecture 13: How Big are Quantum States?”. 
• Gharibian, Sevag. “Lecture 5: Quantum Merlin Arthur (QMA) and strong error reduction” (PDF). 2019년 11월 4일에 원본 문서 (PDF)에서 보존된 문서. 2020년 2월 28일에 확인함. 
• 컴플렉시티 주: QMA