품질 관리

계산 복잡도 이론에서, Quantum Merlin Arthur의 약자인 QMA는 답이 YES일 때, 다항 시간 양자 검증자를 높은 확률로 확신시키는 다항 크기의 양자 증명(양자 상태)이 존재하는 언어 집합이다.게다가 대답이 NO인 경우, 모든 다항식 크기의 양자 상태는 높은 확률로 검증자에 의해 거부된다.

QMA와 BQP의 관계는 복잡도 클래스 NP와 P의 관계와 유사합니다.또한 확률론적 복잡성 등급 MA와 BPP 사이의 관계와도 유사하다.

QAM은 가상 에이전트 Arthur와 Merlin이 시퀀스를 수행하는 관련 복잡도 클래스입니다.Arthur는 랜덤 문자열을 생성하고, Merlin은 양자 증명서를 사용하여 응답하며, Arthur는 BQP 기계로 검증합니다.

정의.

언어 L은 다음과 같이 ^[1]^[2]^[3]다항식 시간 양자 검증자 V와 $p(x)$ p $)$ { $displaystyle$ p(x)}가 존재하는 경우 ${\mathsf {QMA}}(c,s)$ ${\mathsf {QMA}}(c,s)$ A ${\mathsf {QMA}}(c,s)$ , ${\mathsf {QMA}}(c,s)$ ) { $displaystyle {QMA}}(c, s)$ { $displaystyle$ p $(x)}$ 에 ${\mathsf {QMA}}(c,s)$ $p(x)$ ${\mathsf {QMA}}(c,s)$ .

$\forall x\in L$ x $L$ ( $\forall x\in L$ \ $(|x\rangle ,|\psi \rangle )$ $displaystyle$ \ $forall$ x \ in $\forall x\in L$ L )양자 상태 $ψ$ {\ （ \ $displaystyle$ \ $psi$ \ $rangle$ $）$ 이 $|\psi \rangle$ 존재하여 V가 $x 、 )$ )을 $(|x\rangle ,|\psi \rangle )$ 받아들일 확률이 c보다 $크다$ $\forall x\in L$
$\forall x\notin L$ 양자 $|\psi \rangle$ $\forall x\notin L$ {\ $\forall x\notin L$ {\ $\forall x\notin L$ ${\$ { $displaystyle \forall$ $x$ \ $notin$ L $|\psi \rangle$ }에 대해 V가 $x ,$ , $)$ )을 $(|x\rangle ,|\psi \rangle )$ 받아들일 확률은 s $미만$ 입니다 $\forall x\notin L$

여기서 $|\psi \rangle$ { $displaystyle \psi \rangle }$ 은 $|\psi \rangle$ (는) 최대 p $)$ { $style$ p $(x)}$ 큐비트로 모든 $p(|x|)$ 양자 상태에 걸쳐 있습니다.

복잡도 ${\mathsf {QMA}}$ ${\mathsf {QMA}}$ M ${\mathsf {QMA}}$ { $displaystyle$ { $mathsf$ { $Q$ }MA $}}$ 은 ${\mathsf {QMA}}$ (는 ${\mathsf {QMA}}({2}/{3},1/3)$ M A ${\mathsf {QMA}}({2}/{3},1/3)$ / ${\mathsf {QMA}}({2}/{3},1/3)$ , ${\mathsf {QMA}}({2}/{3},1/3)$ 1 / ${\mathsf {QMA}}({2}/{3},1/3)$ ) ${\mathsf {QMA}}({2}/{3},1/3)$ { $displaystyle {QMA}({2}/{3}, 1/$ 3 ${\mathsf {QMA}}({2}/{3},1/3)$ 과(와) 동일하게 정의됩니다.다만, c와 $s$ 가 $s$ 보다 $큰$ 상수로 설정되어 있는 $경우$ 클래스는 변경되지 않기 때문에, 상수는 그다지 중요하지 않습니다.또한 모든 $q(n)$ q ( $q(n)$ $){displaystyle$ q ( $n$ ) $r(n)$ r ( $r(n)$ $){displaystyle$ r ( $n$ 에 대해 다음과 같이 합니다.

displaystyle

MA}}\left({\frac {2}{3}},{\frac {1}{3}}\right)=mathsf {Q

MA}}\left({\frac {1}{q(n)}+{\frac {1}{2}}-{\frac {1}{q(n)}}}\right)=parammathsf {QMA}(1-2^{-r(n

)},

2^{-r(n

QMA의 문제

P, BQP, NP 등 많은 대상 클래스가 QMA에 포함되어 있기 때문에 이들 클래스의 모든 문제는 QMA에도 있습니다.단, QMA에는 있지만 NP 또는 BQP에는 없는 문제가 있습니다.이와 같이 잘 알려진 몇 가지 문제는 다음과 같습니다.

문제는 QMA의 모든 문제를 줄일 수 있다면 NP-hard와 유사한 QMA-hard라고 불립니다.문제가 QMA-hard이고 QMA에 있는 경우 QMA-complete라고 합니다.

국소 해밀턴 문제

k-local Hamiltonian(양자역학) $H$ {\ $displaystyle$ H}는 $H$ n개의 큐비트에 작용하는 에르미트 행렬로, $k개$ (\displaystyle $k)$ 큐비트에 $k$ $m$ 하는 m개 $(\displaystyle$ m)의 해밀턴 항 합계로 나타낼 수 있습니다.

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

일반적인 k-local Hamiltonian $H$ 는 k-local HamiltonianH {\ $displaystyle$ H $H$ ^[4]에서H {\ $displaystyle\$ lambda}의 최소 $\lambda$ ${\$ {\ $displaystyle\lambda}$ 를 $\lambda$ 찾는 $\lambda$ 것입니다.

약속 문제의k-local 해밀턴 문제의 결정 버전은 형식과, 정의된k-local Hamiltonian과 α,α 을β{\displaystyle \alpha ,\beta};β{\displaystyle \alpha>\beta}, 그래서 H{\disp의 양자eigenstate ψ⟩{\displaystyle \psi \rangle}존재하는 결정하다.laysty $\lambda \leq \beta$ H} $\lambda \leq \beta$ {\ $\lambda \leq \beta$ {\ $、$ $style$ \ $displaystyle$ \ $lambda$ \ $\lambda \leq \beta$ $leq$ \ beta $\lambda \leq \beta$ } $\lambda \geq \alpha$ $\lambda \geq \alpha$ {\ {\ {\ {\ {\ {\ 、 ${\$ {\ {\ {\ {\ {\ {\ le 、 \ $displaystyle \ lambda$ \ $geq$ \ alpha $\lambda$ $\lambda \geq \alpha$ $\lambda$ 。

국소 해밀턴 문제는 MAX-SAT의 양자 유사체이다.k-local Hamiltonian 문제는 k 2 ^[5]2에 대해 QMA-완전이다.

큐비트의 2차원 그리드에 작용하도록 제한된 2-local Hamiltonian 문제도 ^[6]QMA-complete입니다.k-국소 해밀턴 문제는 ^[7]입자당 12개의 상태를 가진 가장 가까운 인접 상호작용을 가진 1차원 입자 라인을 나타내는 해밀턴인에게도 여전히 QMA-hard인 것으로 나타났다.시스템이 변환 불변인 경우 로컬 Hamiltonian 문제는 QMA-complete가_EXP 됩니다(문제 입력이 시스템사이즈로 부호화되기 때문에 검증자는 동일한 ^[8]^[9]약속갭을 유지하면서 기하급수적인 실행시간을 갖게 됩니다).

QMA-hardness 결과는 ZX해밀토니안[10]HZX등 qubits의 단순 격자형 모델의 ∑ 나는 h 나는 Z나는 + ∑ 나는 Δ 나는 X나는 + 나는 < ∑, j J나는 j Z나는 Zj+나는 < ∑, j K나는 j X나는 Xj{\displaystyle H_{ZX}=\sum _{나는}h_{나는}Z_{나는}+\sum _{나는}\Delta _{나는}X_{나는}+\sum _{i<, j} 알려져 있다.J^{ij}Z_{나는}Z_{j}+\sum _{i<, j} $K$ $^{ij}X_{i}X_{j}$ $Z,X$ 서 $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 $({displaystyle$ Z $,X)$ 는 $Z, X$ 파울리 행렬 $\sigma _{z},\sigma _{x}$ z $\sigma _{z},\sigma _{x}$ {\ $(\$ _ ${z},\sigma$ _ ${x$ 를 나타낸다. 이러한 모델은 범용 단열 양자 계산에 적용할 수 있다.

k-국소 해밀턴 문제는 기존의 제약 만족 ^[11]문제와 유사하다.다음 표는 기존의 CSP와 Hamiltonian 사이의 유사한 가젯을 보여줍니다.

고전적인	양자	메모들
제약 만족 문제	해밀턴식
변수	큐비트
제약	해밀턴 용어
변수 할당	양자 상태
충족된 제약 조건 수	해밀턴 에너지 항
최적의 솔루션	해밀턴 지반 상태	충족 가능한 최대 제약 조건

기타 QMA 완전 문제

이미 알려진 QMA 완료 문제의 목록은 https://arxiv.org/abs/1212.6312에서 확인할 수 있습니다.

다른 클래스와의 관계

QMA는 다음과 같은 관계에 의해 기존의 다른 복잡도 클래스와 관련지어집니다.

({displaystyle {mathsf {P}}\subseteq {mathsf {MA}}\subseteq {mathsf {QCMA}\subseteq {mathsf {Q})MA}}\subseteq(\mathsf {PP}}\subseteq {\mathsf {PSPACE})

첫 번째 포함은 NP의 정의에서 비롯됩니다.다음 두 가지 항목은 각 사례에서 검증자가 더욱 강력해지고 있다는 사실에서 비롯됩니다.QCMA는 QMA에 포함되어 있습니다.이는 검증자가 증명서를 받는 즉시 측정하여 고전적인 증명서를 보내도록 강제할 수 있기 때문입니다.PP에 QMA가 포함되어 있다는 사실은 Alexei Kitaev와 John Watures에 의해 증명되었다.PP는 또한 PSPACE에 있다는 것을 쉽게 알 수 있다.

P가 PSPACE에 엄격하게 포함되어 있는지 또는 P = PSPACE에 포함되어 있는지조차 알 수 없기 때문에 이러한 포함물 중 어느 것이 무조건 엄격한지는 알 수 없다.단, 현재 QMA에서 가장 잘 알려진 상한은 다음과 같습니다.

{\mathsf {QMA}}\subseteq {\mathsf {A_{0}PP}}

MA}}\subseteq {mathsf {A_{0}

PP}}

및

{\mathsf {QMA}}\subseteq {\mathsf {A_{0}PP}}

Q

{\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}

{\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}

{\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}

Q

{\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}

A [

{\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}

{\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}

]{

displaystyle

\

mathsf

{

Q

}

MA}}\subseteq {mathsf {P^{Q

MA[log]}

{\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}

${\mathsf {A_{0}PP}}$ 서 ${\mathsf {A_{0}PP}}$ $(\$ style $\mathsf {A_{0}$ $표시$ ) $PP}}$ 및 ${\mathsf {A_{0}PP}}$ ${\mathsf {P^{QMA[log]}}}$ Q ${\mathsf {P^{QMA[log]}}}$ A [ ${\mathsf {P^{QMA[log]}}}$ ${\mathsf {P^{QMA[log]}}}$ g ${\mathsf {P^{QMA[log]}}}$ ]{ $displaystyle$ \ $mathsf$ { $P^$ { $Q$ } $MA[log]}$ $}}$ 은 ${\mathsf {P^{QMA[log]}}}$ (는 $)$ ${\mathsf {PP}}$ ${{$ {PP ${\mathsf {PP}}$ 에 ${\mathsf {PP}}$ 되어 있습니다. ${\mathsf {QMA}}$ M ${\mathsf {QMA}}$ { $displaystyle$ { $Q}$ 은(는 $)$ 없을 것 ${\mathsf {QMA}}$ .MA $}}$ 은 ${\mathsf {QMA}}$ (는) A 0 P ${\mathsf {A_{0}PP}}$ \ $displaystyle$ \ $mathsf$ { A $_$ { $0$ } ${\mathsf {A_{0}PP}}$ $하나$ 입니다. $PP}}$ ${\mathsf {P^{QMA[log]}}}$ P ${\mathsf {P^{QMA[log]}}}$ ${\mathsf {P^{QMA[log]}}}$ ${\mathsf {P^{QMA[log]}}}$ [ ${\mathsf {P^{QMA[log]}}}$ g $]{$ $displaystyle$ \ $mathsf$ { $P^$ { $Q$ } $MA[log]}$ ${\mathsf {P^{QMA[log]}}}$ 전자와의 평등은 다항식 시간 계층(PH)을 붕괴시키는 반면, 후자와의 ${\mathsf {QMA}}={\mathsf {co}}$ 은 Q ${\mathsf {QMA}}={\mathsf {co}}$ M ${\mathsf {QMA}}={\mathsf {co}}$ = c o \ $style$ {Q $}$ 을(를) ${\mathsf {QMA}}={\mathsf {co}}$ 한다. $MA}}=mathsf {co$ ${\mathsf {QMA}}$ $(\$ }) $MA$ ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ A [ ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ g ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ ] ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ A ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ \ $displaystyle$ \ $mathsf$ { $P$ ^ { Q } $불명$ $MA[log]}$ $}}\subseteq {mathsf {A_{$ $PP}}}$ 또는 ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ 그 반대입니다.

레퍼런스

^ Aharonov, Dorit; Naveh, Tomer (2002). "Quantum NP – A Survey". arXiv:quant-ph/0210077v1.
^ ^a ^b Watrous, John (2009). "Quantum Computational Complexity". In Meyers, Robert A. (ed.). Encyclopedia of Complexity and Systems Science. pp. 7174–7201. arXiv:0804.3401. doi:10.1007/978-0-387-30440-3_428.
^ 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.
^ O'Donnel, Ryan. "Lecture 24: QMA: Quantum Merlin Arthur" (PDF). Retrieved 18 April 2021.
^ 를 클릭합니다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.
^ 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.
^ Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (1 April 2009). "The Power of Quantum Systems on a Line". Communications in Mathematical Physics. 287 (1): 41–65. doi:10.1007/s00220-008-0710-3.
^ 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. doi:10.1007/s00023-017-0609-7.
^ 를 클릭합니다Biamonte, Jacob; Love, Peter (2008). "Realizable Hamiltonians for universal adiabatic quantum computers". Physical Review A. 78 (1): 012352. arXiv:0704.1287. Bibcode:2008PhRvA..78a2352B. doi:10.1103/PhysRevA.78.012352..
^ Yuen, Henry. "The Complexity of Entanglement" (PDF). henryyuen.net. Retrieved 20 April 2021.
^ 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. pp. 534–543. doi:10.1109/FOCS.2009.30. ISBN 978-0-7695-3850-1.
^ 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.
^ 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: 189. 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).
복잡성 동물원: QMA

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

[JW-2] Watrous, John (2009). "Quantum Computational Complexity". In Meyers, Robert A. (ed.). Encyclopedia of Complexity and Systems Science. pp. 7174–7201. arXiv:0804.3401. doi:10.1007/978-0-387-30440-3_428.

[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.

[4] O'Donnel, Ryan. "Lecture 24: QMA: Quantum Merlin Arthur" (PDF). Retrieved 18 April 2021.

[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.

[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.

[8] Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (1 April 2009). "The Power of Quantum Systems on a Line". Communications in Mathematical Physics. 287 (1): 41–65. doi:10.1007/s00220-008-0710-3.

[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. 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): 012352. arXiv:0704.1287. Bibcode:2008PhRvA..78a2352B. doi:10.1103/PhysRevA.78.012352..

[11] Yuen, Henry. "The Complexity of Entanglement" (PDF). henryyuen.net. Retrieved 20 April 2021.

[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. pp. 534–543. doi:10.1109/FOCS.2009.30. ISBN 978-0-7695-3850-1.

[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.

[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: 189. doi:10.22331/q-2019-09-30-189.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[11]

[12]

[13]

[14]

v t 중요 복잡도 클래스(더 보기)
실현 가능하다고 생각되다	로그 타임 AC⁰ ACC⁰ TC⁰ L SL RL NL 엔씨 SC 참조 P P-완전 ZPP RP BPP BQP APX FP
실현 불가능한 것으로 생각됨	업. NP NP-완전 NP 하드 co-N co-NP-완전 오전 품질 관리 PH § P PP #P #P-완료 아이피 PSPACE PSPACE-완전
실현 불가능한 것으로 간주되다	제외 시간 넥스트 타임 엑스페이스 2회차 초등 홍보 R 재생 모든.
클래스 계층	다항식 계층 지수 계층 그르제고르치크 계층 산술적 계층 부울 계층
클래스 패밀리	DTime(DTIME) NTime(NTIME(NTIME) DSPACE 스페이스 확률적으로 확인할 수 있는 증거 인터랙티브 증명 시스템

Search