QMA

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

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

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

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

정의

언어 L이 $𝖰 𝖬 𝖠 (c, s)$ 에 속한다는 것은 다항 시간 양자 검증자 V와 다항식 $p (x)$ 가 존재하여 다음과 같은 만족함을 의미한다.^[1]^[2]^[3]

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

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

𝖰 𝖬 𝖠 (\frac{2}{3}, \frac{1}{3}) = 𝖰 𝖬 𝖠 (\frac{1}{2} + \frac{1}{q (n)}, \frac{1}{2} - \frac{1}{q (n)}) = 𝖰 𝖬 𝖠 (1 - 2^{- r (n)}, 2^{- r (n)})

.

QMA의 문제들

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

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

국소 해밀토니언 문제

k-국소 해밀토니언 $H$ 는 최대 $k$ 개의 큐비트에 각각 작용하는 $m$ 개의 해밀토니언 항의 합으로 표현될 수 있는 n개의 큐비트에 작용하는 에르미트 행렬이다.

$H = \sum_{i = 1}^{m} H_{i}$

일반적인 k-국소 해밀토니언 문제는 주어진 k-국소 해밀토니언 $H$ 에 대해 $H$ 의 가장 작은 고윳값 $λ$ 를 찾는 것이다.^[4] $λ$ 는 해밀토니언의 바닥 상태 에너지라고도 불린다.

k-국소 해밀토니언 문제의 판정 버전은 일종의 약속 문제이며, k-국소 해밀토니언과 $α > β$ 를 만족하는 $α, β$ 가 주어졌을 때, $H$ 의 대응하는 고윳값 $λ$ 를 가진 양자 고유 상태 $| ψ ⟩$ 가 존재하여 $λ \leq β$ 이거나 $λ \geq α$ 인지 판별하는 것이다.

국소 해밀토니언 문제는 MAX-SAT의 양자 대응물이다. k-국소 해밀토니언 문제는 k ≥ 2에 대하여 QMA-완전이다.^[5]

2차원 큐비트 격자에 작용하도록 제한된 2-국소 해밀토니언 문제 또한 QMA-완전이다.^[6] 입자당 12개의 상태를 가지며 가장 가까운 이웃과 상호작용하는 1차원 선상의 입자를 나타내는 해밀토니언에 대해서도 k-국소 해밀토니언 문제는 여전히 QMA-난해임이 증명되었다.^[7] 시스템이 병진 불변(translationally-invariant)이면, 그 국소 해밀토니언 문제는 QMA_EXP-완전이 된다(문제 입력이 시스템 크기로 인코딩되므로, 검증자는 약속 간격을 유지하면서 지수 시간 복잡도를 갖게 된다).^[8]^[9]

ZX 해밀토니언과 같은 큐비트의 단순한 격자 모델에 대해서도 QMA-난해 결과가 알려져 있다.^[10] $H_{Z X} = \sum_{i} h_{i} Z_{i} + \sum_{i} Δ_{i} X_{i} + \sum_{i < j} J^{i j} Z_{i} Z_{j} + \sum_{i < j} K^{i j} X_{i} X_{j}$ 여기서 $Z, X$ 는 파울리 행렬 $σ_{z}, σ_{x}$ 를 나타낸다. 이러한 모델은 보편적 단열 양자 컴퓨팅에 적용할 수 있다.

k-국소 해밀토니언 문제는 고전적인 제약 만족 문제와 유사하다.^[11] 다음 표는 고전적 CSP와 해밀토니언 사이의 유사한 장치들을 보여준다.

고전	양자	비고
제약 만족 문제	해밀토니언
변수	큐비트
제약	해밀토니언 항
변수 할당	양자 상태
만족된 제약의 수	해밀토니언의 에너지 항
최적 해	해밀토니언의 바닥 상태	최대한 많은 제약을 만족함

기타 QMA-완전 문제

알려진 QMA-완전 문제의 목록은 https://arxiv.org/abs/1212.6312 에서 찾을 수 있다.

다른 종류와의 관계

QMA는 다음 관계를 통해 다른 알려진 복잡도 종류와 연관된다.

𝖯 \subseteq 𝖭 𝖯 \subseteq 𝖬 𝖠 \subseteq 𝖰 𝖢 𝖬 𝖠 \subseteq 𝖰 𝖬 𝖠 \subseteq 𝖯 𝖯 \subseteq 𝖯 𝖲 𝖯 𝖠 𝖢 𝖤

첫 번째 포함 관계는 NP의 정의에서 따른다. 다음 두 포함 관계는 각 경우에 검증자가 더 강력해진다는 사실에서 따른다. QCMA는 검증자가 증명을 받는 즉시 측정함으로써 증명자에게 고전적 증명을 보내도록 강제할 수 있기 때문에 QMA에 포함된다. QMA가 PP에 포함된다는 사실은 알렉세이 키타예프와 존 와트러스에 의해 증명되었다. 또한 PP는 PSPACE에 포함됨을 쉽게 보일 수 있다.

P가 PSPACE에 엄격하게 포함되는지 혹은 P = PSPACE인지조차 알려져 있지 않기 때문에, 이러한 포함 관계 중 어느 것이 무조건적으로 엄격한지는 알려져 있지 않다. 그러나 현재까지 알려진 QMA에 대한 최선의 상한은 다음과 같다.^[15]^[16]

𝖰 𝖬 𝖠 \subseteq 𝖠_{𝟢} 𝖯 𝖯

및

𝖰 𝖬 𝖠 \subseteq 𝖯^{𝖰 𝖬 𝖠 [𝗅 𝗈 𝗀]}

이며,

여기서 $𝖠_{𝟢} 𝖯 𝖯$ 와 $𝖯^{𝖰 𝖬 𝖠 [𝗅 𝗈 𝗀]}$ 둘 다 $𝖯 𝖯$ 에 포함된다. $𝖰 𝖬 𝖠 = 𝖯^{𝖰 𝖬 𝖠 [𝗅 𝗈 𝗀]}$ 가 성립하면 $𝖰 𝖬 𝖠 = 𝖼 𝗈$ - $𝖰 𝖬 𝖠$ 를 의미하게 되므로, 이 등식은 성립할 가능성이 낮다. $𝖯^{𝖰 𝖬 𝖠 [𝗅 𝗈 𝗀]} \subseteq 𝖠_{𝟢} 𝖯 𝖯$ 인지, 혹은 그 반대인지는 알려져 있지 않다.

각주

↑ Aharonov, Dorit; Naveh, Tomer (2002). “Quantum NP – A Survey”. arXiv:quant-ph/0210077v1.
1 2 Watrous, John (2009). 〈Quantum Computational Complexity〉. Meyers, Robert A. (편집). 《Encyclopedia of Complexity and Systems Science》. 7174–7201쪽. arXiv:0804.3401. doi:10.1007/978-0-387-30440-3_428. ISBN 978-0-387-75888-6. S2CID 1380135.
↑ Gharibian, Sevag; Huang, Yichen; Landau, Zeph; Shin, Seung Woo (2015). “Quantum Hamiltonian Complexity”. 《Foundations and Trends in Theoretical Computer Science》 10 (3): 159–282. arXiv:1401.3916. doi:10.1561/0400000066. S2CID 47494978.
↑ O'Donnel, Ryan. “Lecture 24: QMA: Quantum Merlin Arthur” (PDF). 2021년 4월 18일에 확인함.
↑ Kempe, Julia; Kitaev, Alexei; Regev, Oded (2006). “The complexity of the local Hamiltonian problem”. 《SIAM Journal on Computing》 35 (5): 1070–1097. arXiv:quant-ph/0406180v2. doi:10.1137/S0097539704445226. .
↑ Oliveira, Roberto; Terhal, Barbara M. (2008). “The complexity of quantum spin systems on a two-dimensional square lattice”. 《Quantum Information and Computation》 8 (10): 900–924. arXiv:quant-ph/0504050. Bibcode:2005quant.ph..4050O. doi:10.26421/QIC8.10-2. S2CID 3262293.
↑ Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (2009). “The power of quantum systems on a line”. 《Communications in Mathematical Physics》 287 (1): 41–65. arXiv:0705.4077. Bibcode:2009CMaPh.287...41A. doi:10.1007/s00220-008-0710-3. S2CID 1916001.
↑ Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (2009년 4월 1일). “The Power of Quantum Systems on a Line”. 《Communications in Mathematical Physics》 287 (1): 41–65. arXiv:0705.4077. Bibcode:2009CMaPh.287...41A. doi:10.1007/s00220-008-0710-3. S2CID 1916001.
↑ Bausch, Johannes; Cubitt, Toby; Ozols, Maris (November 2017). “The Complexity of Translationally Invariant Spin Chains with Low Local Dimension”. 《Annales Henri Poincaré》 18 (11): 3449–3513. arXiv:1605.01718. Bibcode:2017AnHP...18.3449B. doi:10.1007/s00023-017-0609-7.
↑ Biamonte, Jacob; Love, Peter (2008). “Realizable Hamiltonians for universal adiabatic quantum computers”. 《Physical Review A》 78 (1). arXiv:0704.1287. Bibcode:2008PhRvA..78a2352B. doi:10.1103/PhysRevA.78.012352. S2CID 9859204. .
↑ Yuen, Henry. “The Complexity of Entanglement” (PDF). 《henryyuen.net》. 2025년 2월 28일에 원본 문서 (PDF)에서 보존된 문서. 2021년 4월 20일에 확인함.
↑ Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009). 〈Two-message quantum interactive proofs are in PSPACE〉. 《Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (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 has constant-round quantum interactive proof systems”. 《Theoretical Computer Science》 292 (3): 575–588. doi:10.1016/S0304-3975(01)00375-9.
↑ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2011). “QIP = PSPACE”. 《Journal of the ACM》 58 (6): A30. doi:10.1145/2049697.2049704. S2CID 265099379.
↑ Vyalyi, Mikhail N. (2003). “QMA = PP implies that PP contains PH”. 《Electronic Colloquium on Computational Complexity》.
↑ Gharibian, Sevag; Yirka, Justin (2019). “The complexity of simulating local measurements on quantum systems”. 《Quantum》 3. arXiv:1606.05626. Bibcode:2019Quant...3..189G. doi:10.22331/q-2019-09-30-189.

외부 링크

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

[1] Aharonov, Dorit; Naveh, Tomer (2002). “Quantum NP – A Survey”. arXiv:quant-ph/0210077v1.

[JW-2] 1 2 Watrous, John (2009). 〈Quantum Computational Complexity〉. Meyers, Robert A. (편집). 《Encyclopedia of Complexity and Systems Science》. 7174–7201쪽. arXiv:0804.3401. doi:10.1007/978-0-387-30440-3_428. ISBN 978-0-387-75888-6. S2CID 1380135.

[3] Gharibian, Sevag; Huang, Yichen; Landau, Zeph; Shin, Seung Woo (2015). “Quantum Hamiltonian Complexity”. 《Foundations and Trends in Theoretical Computer Science》 10 (3): 159–282. arXiv:1401.3916. doi:10.1561/0400000066. S2CID 47494978.

[4] O'Donnel, Ryan. “Lecture 24: QMA: Quantum Merlin Arthur” (PDF). 2021년 4월 18일에 확인함.

[5] Kempe, Julia; Kitaev, Alexei; Regev, Oded (2006). “The complexity of the local Hamiltonian problem”. 《SIAM Journal on Computing》 35 (5): 1070–1097. arXiv:quant-ph/0406180v2. doi:10.1137/S0097539704445226. .

[6] Oliveira, Roberto; Terhal, Barbara M. (2008). “The complexity of quantum spin systems on a two-dimensional square lattice”. 《Quantum Information and Computation》 8 (10): 900–924. arXiv:quant-ph/0504050. Bibcode:2005quant.ph..4050O. doi:10.26421/QIC8.10-2. S2CID 3262293.

[7] Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (2009). “The power of quantum systems on a line”. 《Communications in Mathematical Physics》 287 (1): 41–65. arXiv:0705.4077. Bibcode:2009CMaPh.287...41A. doi:10.1007/s00220-008-0710-3. S2CID 1916001.

[8] Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (2009년 4월 1일). “The Power of Quantum Systems on a Line”. 《Communications in Mathematical Physics》 287 (1): 41–65. arXiv:0705.4077. Bibcode:2009CMaPh.287...41A. doi:10.1007/s00220-008-0710-3. S2CID 1916001.

[9] Bausch, Johannes; Cubitt, Toby; Ozols, Maris (November 2017). “The Complexity of Translationally Invariant Spin Chains with Low Local Dimension”. 《Annales Henri Poincaré》 18 (11): 3449–3513. arXiv:1605.01718. Bibcode:2017AnHP...18.3449B. doi:10.1007/s00023-017-0609-7.

[10] Biamonte, Jacob; Love, Peter (2008). “Realizable Hamiltonians for universal adiabatic quantum computers”. 《Physical Review A》 78 (1). arXiv:0704.1287. Bibcode:2008PhRvA..78a2352B. doi:10.1103/PhysRevA.78.012352. S2CID 9859204. .

[11] Yuen, Henry. “The Complexity of Entanglement” (PDF). 《henryyuen.net》. 2025년 2월 28일에 원본 문서 (PDF)에서 보존된 문서. 2021년 4월 20일에 확인함.

[12] Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009). 〈Two-message quantum interactive proofs are in PSPACE〉. 《Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (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 has constant-round quantum interactive proof systems”. 《Theoretical Computer Science》 292 (3): 575–588. doi:10.1016/S0304-3975(01)00375-9.

[14] Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2011). “QIP = PSPACE”. 《Journal of the ACM》 58 (6): A30. doi:10.1145/2049697.2049704. S2CID 265099379.

[15] Vyalyi, Mikhail N. (2003). “QMA = PP implies that PP contains PH”. 《Electronic Colloquium on Computational Complexity》.

[16] Gharibian, Sevag; Yirka, Justin (2019). “The complexity of simulating local measurements on quantum systems”. 《Quantum》 3. arXiv:1606.05626. Bibcode:2019Quant...3..189G. 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 t e 복잡도 종류
효율적 해결 가능	DLOGTIME AC⁰ ACC⁰ REG TC TC⁰ L SL RL FL NL NL-완전 NC SC CC P P-완전 ZPP RP BPP BQP APX FP
비효율적 추정	UP NP NP-완전 NP-난해 Co-NP Co-NP-완전 TFNP FNP AM QMA PH ⊕P PP #P #P-완전 IP PSPACE PSPACE-완전
효율적 해결 불가능	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY NONELEMENTARY PR R RE ALL
기타 복잡도 종류	polyL QP
종류별 위계	다항 위계 지수 위계 그르제고르치크 위계 산술적 위계 불리언 위계
복잡도 계열	DTIME NTIME DSPACE NSPACE PCP 대화형 증명 시스템
복잡도 종류 목록

정의

QMA의 문제들

국소 해밀토니언 문제

기타 QMA-완전 문제

관련 종류

다른 종류와의 관계

각주

외부 링크