BQP

계산 복잡도 이론에서, 유계 오차 양자 다항 시간(BQP)은 양자 컴퓨터가 다항 시간에 풀 수 있는 결정 문제의 종류로, 모든 경우에 대해 ^[1]오차 확률은 최대 1/3이다.이것은 복잡도 클래스 BPP의 양자 유사체이다.

결정문제는 결정문제를 높은 확률로 해결하고 다항식으로 실행이 보증되는 양자알고리즘(양자컴퓨터상에서 실행되는 알고리즘)이 존재하는 경우 BQP의 구성원이다.알고리즘을 실행하면 최소 2/3의 확률로 결정 문제가 올바르게 해결됩니다.

BQP 알고리즘(1회 실행)
정답. 생산되었다 맞아요. 정답.	네.	아니요.
네.	≥ 2/3	≤ 1/3
아니요.	≤ 1/3	≥ 2/3
BQP 알고리즘(k회 실행)
정답. 생산되었다 맞아요. 정답.	네.	아니요.
네.	> 1 ~ 2^−ck	2^−ck 미만
아니요.	2^−ck 미만	> 1 ~ 2^−ck
어떤 상수 c > 0일 경우

정의.

BQP는 양자회로의 ^[1]특정 유계 오차 균일한 패밀리와 관련된 언어라고 볼 수 있습니다. $\{Q_{n}\colon n\in \mathbb {N} \}$ L은 양자회로 {Q $\{Q_{n}\colon n\in \mathbb {N} \}$ n : $\{Q_{n}\colon n\in \mathbb {N} \}$ $}(\displaystyle$ \{ $Q_{n}\colon$ n $\in \mathbb {N$ 의 다항식 시간 균일한 패밀리가 존재하는 경우에만 BQP에 있습니다.

$n\in \mathbb {N}$ $(\$ n $\in \mathbb {N$ 에 대해 Q는_n n개의 큐비트를 입력으로 받아 1비트를 출력합니다.
L의 모든 $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$ 에 대해 $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$ r ( $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$ ( $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$ ) $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$ ) 2 $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$ 3 $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$ ( \ $displaystyle$ \ $mathrm$ { $Pr }$ ( $x$ ) $= 1$ ) \ $geq$ { $tfrac {$ 2} ${3}$ }
L에 포함되지 않은 $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$ x에 대해 $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$ ( $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$ x ( x ) $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$ $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$ ) $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$ 2 $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$ 3 $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$ \ $display$ \ $mathrm$ { $Pr$ } ( Q $_$ { x $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$ } ( x ) = $0$ )\ $geq$ { $tfrac {$ 2} ${3}$ }

양자 튜링 기계의 관점에서 BQP를 정의할 수도 있다.언어 L은 모든 ^[2]인스턴스에 대해 최대 1/3의 오류 확률을 가진 L을 받아들이는 다항식 양자 튜링 기계가 존재하는 경우에만 BQP에 있습니다.

다른 "경계 오차" 확률론적 분류와 마찬가지로 정의에서 1/3의 선택은 임의적이다.체르노프 바운드를 사용하여 알고리즘을 일정 횟수 실행하고 다수결로 1 미만의 원하는 정확성을 달성할 수 있습니다.복잡도 클래스는 1/2 - n의^−c 오차를 허용하거나 2의 작은^{−n^c} 오차를 요구함으로써 변경되지 않습니다.여기서 c는 임의의 양의 상수이고 n은 ^[3]입력 길이입니다.

BQP 완전 문제

NP 완전성 및 기타 완전한 문제의 개념과 마찬가지로 BQP 완전성 문제를 BQP 내의 문제로 정의할 수 있으며 BQP 내의 모든 문제가 다항식 시간 내에 감소합니다.

BQP의 정의에서 직접 기인하는 직관적인 BQP 완전 문제를 다음에 나타냅니다.

ABAL-QECURIT-PROB 문제

n{n\displaystyle}qubits에 n{n\displaystyle}에서 m{m\displaystyle}은 다항식, 하나 또는 두가지의 qubits에 각 게이트 흡수되고, 두 숫자,β ∈[0,1],α 을 α, β{\displaystyle \alph m{m\displaystyle}하고, 기름 부음 받은 연기와{C\displaystyle} 양자 회로 C에 대한 설명이다.a,\ $syslog \in [ 0$ , $1$ ] , \ $alpha$ > \ $syslog$ $\alpha ,\beta \in [0,1],\alpha >\beta$ \ 、 다음 두 가지 경우를 구분합니다.

$C|0\rangle ^{\otimes n}$ $C|0\rangle ^{\otimes n}$ $C|0\rangle ^{\otimes n}$ \ $displaystyle C$ 0 \ $rangle$ ^ { \ $otimes$ n $C|0\rangle ^{\otimes n}$ } 의 $C|0\rangle ^{\otimes n}$ 첫 번째 큐비트를 측정하면 $\geq \alpha$ { \ $displaystyle$ \ $geq$ \ $alpha$ } 의 확률로 1 $|1\rangle$ µ $|1\rangle$ 이 $|1\rangle$ 됩니다.
$C|0\rangle ^{\otimes n}$ $C|0\rangle ^{\otimes n}$ $C|0\rangle ^{\otimes n}$ \ $displaystyle$ C $0$ \ $rangle$ ^ { \ $otimes$ n $C|0\rangle ^{\otimes n}$ } measuring $C|0\rangle ^{\otimes n}$ 、 β \ $displaystyle \ leq$ \ beta $\leq \beta$ ${\$ {\ $1$ {\1 $。$

인스턴스가 이들 2가지 케이스에 포함되지 않는 경우 이 문제는 동작을 특정하지 않습니다.

주장. 모든 BQP 문제는 ALTUM-QECURIT-PROB로 감소한다.

증명하기 위해서요 우리는 양자 회로 Cn{n\displaystyle}qubits에 작용하는{C\displaystyle}를 주어진 알고리즘에서는 APPROX-QCIRCUIT-PROB를 해결한{A\displaystyle}, 즉 되고 즐기고 두 숫자,β ∈[0,1],α>β{\displaystyle \alpha ,\beta\in[0,1],\alpha>\beta},{A\displaystyle}disti α다고 가정해 보자.nguish특히 위의 두 경우 사이에서요.이 오라클에서는 $\alpha =2/3,\beta =1/3$ 2 / 3, $=$ $\alpha =2/3,\beta =1/3$ / $\alpha =2/3,\beta =1/3$ (\ $displaystyle$ \ $alpha = 2$ / 3, \ displaystyle $= 1 / 3$ )을 $\alpha =2/3,\beta =1/3$ 하여 BQP의 문제를 해결할 수 있습니다.

$L\in \mathrm {BQP}$ 의 L $L\in \mathrm {BQP}$ $n\in \mathbb {N}$ $L\in \mathrm {BQP}$ $L\in \mathrm {BQP}$ P $L\in \mathrm {BQP}$ \ $displaystyle$ L \ $in$ \ $mathrm$ { $BQP$ 에 대해 n $n\in \mathbb {N}$ n $n$ $\{Q_{n}\colon n\in \mathbb {N} \}$ : $\{Q_{n}\colon n\in \mathbb {N} \}$ N $n\in \mathbb {N}$ $}$ \ $displaystyle$ \ { $Q$ n } \ $colon n$ \ $in$ $\{Q_{n}\colon n\in \mathbb {N} \}$ \ $mathbb n$ { N $n\in \mathbb {N}$ } \ such $\{Q_{n}\colon n\in \mathbb {N} \}$ n \ $n\in \mathbb {N}$ n such n such n $\{Q_{n}\colon n\in \mathbb {N} \}$ n 。 $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ L , $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ ( $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ ) $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ ) ) $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ / $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ ( x \ $style$ x \ $in$ L , $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ _ { $n$ $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ ( x \ $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ ) $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ 1 $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ $geq$ 2 / $display$ 3 $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ ponding $quantum$ $circuit$ $Q_{n}$ Qn {\displaystyle $Q_{$ $n$ $Q_{n}$ . C $C_{x}|0\rangle ^{\otimes n}=|x\rangle$ 0 $C_{x}$ $C_{x}|0\rangle ^{\otimes n}=|x\rangle$ n $=$ \ $rangle ^{\displaystyle$ $C_$ ${x}$ = $x$ $\$ $rangle$ $C_{x}|0\rangle ^{\otimes n}=|x\rangle$ 의 $C_{x}|0\rangle ^{\otimes n}=|x\rangle$ 를 먼저 구성할 수 있습니다.이것은 $xrangle$ 로 쉽게 할 수 있습니다 $|x\rangle$ 큐비트를 뒤집을 수 있는 T 게이트.그런 다음 2개의 회로를 조합하여 C $C'=C_{x}Q_{n}$ = C $C'=C_{x}Q_{n}$ Q n \ $displaystyle$ C' $C_{$ $x$ } $Q_{$ n $C'=C_{x}Q_{n}$ 를 $C'=C_{x}Q_{n}$ 수 있습니다. $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ C $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ 0 $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ n $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ and { $displaystyle$ C' $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ 0 \ $rangle$ { \ $times$ = $Q$ _ n $} x$ \ $rangle$ 을 얻을 수 있습니다 $.$ 결과는 필연적으로 다음과 같습니다.논리적으로 관문을 열게 됩니다.C^[4]^[5] $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ 0 $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ x $⟩$ \ $display$ C $' 0$ \ $rangle$ ^ { \ $otimes$ n } = $Q$ _ { $n }$ x \ $rangle$ 의 $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ 번째 큐비트를 측정하여 출력을 얻을 수 있도록 항상 측정을 연기할 수 있습니다.이것은 $회선$ C(\ $displaystyle$ C $C$ 가 됩니다.또, A $C)(\displaystyle$ A $(C))$ 를 $A(C)$ $\alpha =2/3,\beta =1/3$ $\alpha =2/3,\beta =1/3$ / $\alpha =2/3,\beta =1/3$ , $\alpha =2/3,\beta =1/3$ β $(\displaystyle$ \ $alpha = 2/3,\displaystyle$ = $1/3$ 로 실행하여 L $(\displaystyle$ L $)$ 의 $L$ x(\ $displaystyle$ x $)$ 멤버십을 $x$ $x$ 합니다.정의: B.또는 두 번째 케이스(거부)로 L $L\in \mathrm {BQP}$ B $L\in \mathrm {BQP}$ P {\ $displaystyle L\in$ \mathrm { $BQP}}$ 가 $L\in \mathrm {BQP}$ ALTIC-QECURIT-PROB로 감소합니다.

ACTUL-QECURIT-PROB는 일부 잘 알려진 복잡도 클래스와 BQP 사이의 관계를 증명하려고 할 때 유용합니다.

다른 복잡도 클래스와의 관계

컴퓨터 과학에서 해결되지 않은 문제:

${\mathsf {NP}}$ ${\mathsf {BQP}}$ P $({displaystyle$ ${$ $BQP$ $}})$ 와 N P ({ $displaystyle$ { $NP$ 의 ${\mathsf {BQP}}$ 관계는 무엇입니까?

(컴퓨터 사이언스의 미해결 문제 증가)

BQP와 다른 문제^[1] 공간과의 관계가 의심됩니다.

BQP는 양자 컴퓨터를 위해 정의된다. 고전적인 컴퓨터(또는 확률론적 튜링 기계)에 대응하는 복잡도 클래스는 BPP이다.P 및 BPP와 마찬가지로 BQP는 그 자체로 낮습니다.즉^BQP, BQP ^[2]= BQP입니다.비공식적으로 이것은 다항 시간 알고리즘이 구성 하에서 닫히기 때문에 사실이다.다항 시간 알고리즘이 다항 시간 알고리즘을 서브루틴으로 호출해도 결과 알고리즘은 여전히 다항 시간입니다.

BQP에는 P와 BPP가 포함되어 있으며 AWPP,^[6]^[2] PP^[7] 및 PSPACE에 포함되어 있습니다.사실, PP에 대한 BQP는 낮습니다. 즉, PP 머신은 BQP 문제를 즉시 해결할 수 있는 이점을 달성하지 못한다는 것을 의미하며, 이는 이러한 유사한 클래스 간에 가능한 힘의 차이를 나타냅니다.기존의 복잡도 클래스와의 관계는 다음과 같습니다.

{P\subseteq BPP\subseteq AWPP\subseteq PP\subseteq PSPACE\subseteq EXP}

P p PSPACE의 문제는 아직 해결되지 않았기 때문에, BQP와 상기의 클래스간의 불평등성의 증명은 ^[2]곤란할 것으로 생각된다.BQP와 NP의 관계는 불명확합니다.2018년 5월 프린스턴 대학의 컴퓨터 과학자 Ran Raz와 스탠포드 대학의 Avishay Tal은 오라클에^[8] 비해 BQP가 PH에 포함되지 않았다는 논문을 발표했습니다.BQP^A ${\$ { $displaystyle \nsubseteq$ } ^[9]PH의 $\nsubseteq$ ^A Oracle A가 존재함을 증명할 수 있습니다.극히 비공식적인 의미에서 이는 PH와 BQP에 동일하지만 추가 기능을 부여하고 오라클(BQP^A)을 사용하는 BQP가 PH가 수행할 수 없는 작업을^A 수행할 수 있는지 확인하는 것으로 간주할 수 있습니다.Oracle 분리는 검증되었지만 BQP가 PH에 포함되어 있지 않다는 사실은 검증되지 않았다.오라클 분리는 복잡도 클래스가 동일한지 여부를 증명하지 않습니다.오라클 분리는 BQP가 PH에 포함되지 않을 수 있다는 직감을 준다.

푸리에 샘플링은 다항식 계층 내에는 존재하지 않지만 BQP 내에 존재하는 문제라는 것은 오랫동안 의심되어 왔다.최근의 추측은 유사한 문제인 푸리에 체크가 다항식 계층에 포함되지 않고 클래스 BQP에도 존재한다는 증거를 제공했다.이 추측은 BQP에 존재하는 문제가 NP-Complete 문제보다 더 어려운 것으로 분류될 수 있음을 시사하기 때문에 특히 주목됩니다.많은 실용적인 BQP 문제가 P 이외에서 존재할 것으로 생각된다는 사실과 함께(P NP의 증거가 없기 때문에 의심되고 검증되지 않음) 이는 고전 ^[9]컴퓨팅과 관련된 양자 컴퓨팅의 잠재력을 보여준다.

BQP에 사후 선택을 추가하면 PP와 동일한 ^[10]^[11]복잡도 클래스 PostBQP가 됩니다.

이하에, 이러한 결과의 일부를 실증 또는 토의합니다.

BQP 및 EXP

먼저 좀 더 쉬운 봉쇄부터 시작하죠 ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ P ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ X ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ { $displaystyle$ { $mathsf$ { $BQP$ } $sub$ subseteq { $mathsf$ { EXP $}$ that ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ 、 ARTUL-QECURIT-PROB는 BQP-complete이므로 ARTUL-QCURIT-P-P가 EXP에 있음을 나타내는 것으로 충분합니다.

주장하다— $디스플레이 스타일약 QCircuit-PROB}}\in {\mathsf {EXP}}$

증명

아이디어는 간단하다.우리는 기하급수적인 힘을 가지고 있기 때문에 $양자회로$ C가 주어지면 고전적인 컴퓨터를 사용하여 $C$ 의 각 게이트를 자극하여 최종 상태를 얻을 수 있습니다.

좀 더 형식적으로, C를 n개의 $큐비트$ 와 m개의 $게이트$ 에서 다항식 크기의 양자회로라고 $하자$ . 여기서 m은 n개의 다항식이다. $|\psi _{i-1}\rangle$ 0 $|\psi _{i-1}\rangle$ $|\psi _{0}\rangle =|0\rangle ^{\otimes n}$ $|\psi _{0}\rangle =|0\rangle ^{\otimes n}$ $|\psi _{0}\rangle =|0\rangle ^{\otimes n}$ $|\psi _{0}\rangle =|0\rangle ^{\otimes n}$ $|\psi _{0}\rangle =|0\rangle ^{\otimes n}$ \ $displaystyle$ $\$ $psi _$ { $0$ $|\psi _{0}\rangle =|0\rangle ^{\otimes n}$ } \ $rangle$ $= 0$ \ $rangle$ ^ { \ $|\psi _{i}\rangle$ $otimes$ $|\psi _{i}\rangle$ n $|\psi _{0}\rangle =|0\rangle ^{\otimes n}$ } $|\psi _{i}\rangle$ iψψψ $|\psi _{i}\rangle$ iψ i $⟩ displaydisplay$ { $|\psi _{i-1}\rangle$ { $|\psi _{i-1}\rangle$ let let let let let $|\psi _{i-1}\rangle$ let let ${$ - - - - - - - - - - - - - - - - - let let let let let let let let - - - - - - - - - - - let let let - - - - let let let let let let let let let let let let let let let let let let let let let let let let $gle은$ $\mathbb {C} ^{2^{n}}$ 에서 $단위$ 벡터로 나타낼 수 있습니다. $또한$ 각 게이트는 $\mathbb {C} ^{2^{n}\times 2^{n}}$ n × $\mathbb {C} ^{2^{n}\times 2^{n}}$ \ $mathbb$ { $C$ } $\mathbb {C} ^{2^{n}}$ $^$ { $2$ $\mathbb {C} ^{2^{n}}$ } ^ { 2 ^ { $n$ } \ $times$ 2 ^ { n $}$ } { $|\psi _{m}\rangle$ { { { a a $|\psi _{m}\rangle$ a a gle gle gle gle gle gle gle gle gle $|\psi _{m}\rangle$ $|\psi _{m}\rangle$ gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle gle $|\psi _{m}\rangle$ }은 $|\psi _{m}\rangle$ (는) $O(m2^{2n})$ 2n $)$ { $displaystyle$ O $(m2^{2n})$ 시간으로 $O(m2^{2n})$ $O(m2^{2n})$ 할 수 있으므로 최종 상태를 계산하는 $n)$ { $Displaystyle$ 2^{ $O($ n $2^{O(n)}$ )}} $2^{O(n)}$ 알고리즘이 $2^{O(n)}$ 첫 번째 큐비트가 1이 될 가능성이 있습니다 $.$ 즉, ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}$ ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}$ X P \ $displaystyle$ \ text { text ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}$ }를 의미합니다. $ABUT-QECURIT-PROB}:\in$ { $mathsf {EXP$

이 알고리즘에는 벡터 및 매트릭스를 저장하기 위한 $2^{O(n)}$ ( $2^{O(n)}$ n $2^{O(n)}$ ) \ $displaystyle$ 2 $^{O(n)}$ 공간도 $2^{O(n)}$ $2^{O(n)}$ 합니다.다음 섹션에서는 공간의 복잡성을 개선할 수 있음을 보여 줍니다.

BQP 및 PSPACE

${\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}$ ${\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}$ P ${\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}$ ${\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}$ ${\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}$ ${\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}$ E ( \ $displaystyle$ \ $mathsf$ { $BQP$ } )\ $subseteq$ ( \ $mathsf$ { PSPACE $}$ )를 증명하기 위해 먼저 이력합이라는 기법을 도입합니다.

이력 합계

역사 합계는 물리학자 리처드 파인만이 경로 적분 공식을 위해 도입한 기술입니다.우리는 이 기술을 양자 컴퓨팅에 적용하여 ARTUM-QCURIT-PROB를 해결한다.

기록의 합계 트리

양자회로 $C$ 는 $g_{1},g_{2},\cdots ,g_{m}$ $g_{1},g_{2},\cdots ,g_{m}$ g2, $g_{1},g_{2},\cdots ,g_{m}$ g2, $g_{1},g_{2},\cdots ,g_{m}$ {{ $displaystyle$ $g_{$ $1$ }, $g_{2},\cdots,g_$ ${m$ $g_{1},g_{2},\cdots ,g_{m}$ 로 $g_{j}$ $구성$ 되어 있습니다. $g_{j}$ 서 각 g $g_{j}$ 는 유니버설게이트 세트에서 최대 2개의 큐비트로 동작합니다.이력의 합계가 무엇인지 이해하기 위해 양자회로가 주어진 양자상태의 진화를 나무처럼 시각화합니다.루트는 입력 $|0\rangle ^{\otimes n}$ $|0\rangle ^{\otimes n}$ ( \ $displaystyle$ 0 \ $rangle$ ^ { \ $otimes$ n $|0\rangle ^{\otimes n}$ } )입니다.트리의 각 노드에는 $(\$ 2 $^{n})$ 의 $2^{n}$ 자녀가 $2^{n}$ 각각 $(\$ {C $})^{$ n $\mathbb {C} ^{n}$ 의 상태를 나타냅니다. $|x\rangle$ 의 노드x ${\$ { $displaystyle$ x \ $rangle$ }에서 $|x\rangle$ j $j+1$ + $j+1$ 의 $j+1$ (\ $displaystyle$ j $+$ $1$ } $-$ $|y\rangle$ ${\$ \ $displaystyle$ $\langle y|g_{j+1}|x\rangle$ y \ $rangle$ })까지의 $j+1$ $|y\rangle$ 트리 엣지에서의 가중치는 $\langle y|g_{j+1}|x\rangle$ $\langle y|g_{j+1}|x\rangle$ + 1 $\langle y|g_{j+1}|x\rangle$ ${\$ { \ $displaystyle$ \ $langle$ y g $+ 1$ \ $langle$ $\langle y|g_{j+1}|x\rangle$ 입니다 $.$ $|y\rangle$ $|x\rangle$ 에 $g_{j+1}$ j + 1 $(\$ $displaystyle$ x $\rangle$ 을 $g_{j+1}$ $g_{j+1}$ 한 $|y\rangle$ 후 {\ $displaystyle$ $y\rangle$ $}.$ 루트-리프 경로의 전이 진폭은 경로를 따라 가장자리에 있는 모든 가중치의 곱입니다 $.$ 최종 상태가 " $|\psi \rangle$ " $|\psi \rangle$ " $일$ 가능성을 얻기 위해 $"$ $|\psi \rangle$ " " $|\psi \rangle$ 를 $|\psi \rangle$ 노드에서 끝나는 모든 루트 투 $|\psi \rangle$ $리브$ 경로의 진폭을 $합계$ 합니다 $|\psi \rangle$

$양자회로$ C의 경우 이력 트리의 합계는 $깊이$ m의 트리로 루트 외에 $g_{i}$ $(\$ })마다 $g_{i}$ 1개의 레벨이 있으며 분기 $2^{n}$ $(\$ 2 $^{n$ 이 있습니다.

정의: 이력은 이력 트리의 합계 경로입니다.이력을 시퀀스 $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ 0 $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ 0 $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ n $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ 1 → ⋯ $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ m - $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ m $=$ ) { $style$ ( $u_{0$ }= $0\rangle ^{\$ otimes n}\ $right 화살표 u_$ {1}\ $right$ 화살표 $u_cdots$ \cdots\rightarrow u_ ${m-1}$ u_{m})로 $나타냅니다$ .

$u,v\in \{0,1\}^{n}$ — $u,v\in \{0,1\}^{n}$ u , $u,v\in \{0,1\}^{n}$ $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ { $u,v\in \{0,1\}^{n}$ , $u,v\in \{0,1\}^{n}$ $u,v\in \{0,1\}^{n}$ { $displaystyle u$ , $u,v\in \{0,1\}^{n}$ $v$ \ $in$ $u,v\in \{0,1\}^{n}$ \ { $0$ , 1 \ $u,v\in \{0,1\}^{n}$ $(|u\rangle ,|v\rangle )$ $n$ . $(|u\rangle ,|v\rangle )$ 、 $displaydisplay$ 、 $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ $(|u\rangle ,|v\rangle )$ 、 $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ display $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ $display$ $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ style $(|u\rangle ,|v\rangle )$ $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ g $.$ . $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ h $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ ( $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ 0 $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ 1 $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ m - $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ m ) $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ { $displaystyle$ h = ( $u _$ { 0 } \ $rightarrow$ \ $cdots$ \ $rightarrow u$ _ { m - 1 } \ $rightarrow$ u _ { m u _ rightarrow $u$ _ { $m$ } $\alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)$ _ rightarrow u _ { m u } $=$ 1 $\alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)$ } )에 대하여 이력의 전이 $\alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)$ 은 $\alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)$ $\alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)$ 이다. $displaystyle \alpha$ _ ${h}=\alpha$ _{ $1}(0\rangle$ ^{\ $otimes$ n $}\rightarrow u_{1}\alpha$ _ ${2}\cdots \alpha$ _ ${m-1}\rightarrow$ x $\alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)$

Claim : $(u_{0}\rightarrow \cdots \rightarrow u_{m})$ u $(u_{0}\rightarrow \cdots \rightarrow u_{m})$ $(u_{0}\rightarrow \cdots \rightarrow u_{m})$ m )의 경우 $,$ { $displaystyle (u_{0}\rightarrow \cdots$ \ $rightarrow$ u_{ $m}).$ 이력의 전이 진폭은 다항식 시간으로 계산할 수 있습니다.

증명

각 $g_{j}$ $g_{j}$ j $({$ 는 $g_{j}$ g $g_{j}=I\otimes {\tilde {g}}_{j}$ $=$ $g_{j}=I\otimes {\tilde {g}}_{j}$ $g_{j}=I\otimes {\tilde {g}}_{j}$ ~ $g_{j}=I\otimes {\tilde {g}}_{j}$ ({ $displaystyle g_{j$ })로 분해할 수 있습니다.일반성을 잃지 않고 ${\tilde {g}}_{j}$ 두 ${\tilde {g}}_{j}$ 의 큐비트에 대해 동작하는 일부 ${\tilde {g}}_{j}$ 연산자 g ~ ${\tilde {g}}_{j}$ j ( $디스플레이 스타일$ { $g$ $}_{j})$ 의 $g_{j}=I\otimes {\tilde {g}}_{j}$ ${\tilde {g}}_{j}$ 경우 첫 번째 두 개의 큐비트가 될 수 $있습니다$ .따라서 $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ 「 $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ u $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ 「 $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ 、「 v $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ ~ $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ 1 、 $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ 2 $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ 「 $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ 3 $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ 「 $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ $」({$ $displaystyle$ \ $displaystyle v_{j} u\rangle$ = \ $displayle v_1, v_{2$ } { $tilde {g}$ {g} { $u}{$ 1},나는 n에 $있습니다$ .m은 $n$ 의 $다항식$ 이므로 이력의 전이 진폭은 다항식 시간으로 계산할 수 있습니다.

Claim : C $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ { $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ , $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ { \ $displaystyle$ C $0$ \ $rangle$ ^ { \ $otimes$ n }= \ $sum$ _ { $x$ \ $in$ \ { $0$ , $1$ \ }^{ $n$ } = \ sum _ { x \ n \ alpha _ { x $}x }$ x \ rangle $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ } be $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ circuit circuit circuit circuit circuit circuit circuit circuit circuit circuit circuit circuit circuit circuit circuit circuit circuit circuit circuit $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ circuit 。 $x\in \{0,1\}^{n}$ x $x\in \{0,1\}^{n}$ { $x\in \{0,1\}^{n}$ 0 , $x\in \{0,1\}^{n}$ $x\in \{0,1\}^{n}$ { { \ $displaystyle x$ \ $in$ \ { $0$ , 1 \ }^{ $x\in \{0,1\}^{n}$ n $x\in \{0,1\}^{n}$ }의 $\alpha_x$ 경우 $\alpha _{x}$ $\alpha _{x}$ x x { \ $displaystyle$ $\ alpha$ $_$ { x }}는 α x $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ ( 0 $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ n $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ n $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ 1 $→$ - $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ $x$ ） $h$ h h h h h $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ h h h h h \ alpha $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ h h h h h h h h h h ${t-1}\rightarrow$ x $\rangle}\alpha$ _ ${h$

증명

$\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ x $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ 0 $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ ⟩ $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ x $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ t $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ t $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ - $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ 1 C 0 $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ n $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ \ $displaystyle \alpha _$ { x }= \ $rangle ^$ { \ $otimes$ n = \ $displayle$ x C 0 \ $rangle$ x $g _$ { t - $1 } =$ \ rangle x g _ { t - 1 ^ { \ $rangle$ } ^ { \ rangle $}$ 가 $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ .결과는 I $=$ $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ { $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ , $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ } $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ x $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ x $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ x $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ {\x x x {\x { $x$ \ $sum$ _ { 0 , 1 \ }^{ n $}x\rangle$ \ $rangle$ x $}$ 를 $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ $g_{1},g_{2}$ $,$ $display$ $style$ $g_{2$ } $g_{1},g_{2}$ $사이$ 에 $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ 으로써 직접 얻을 수 있습니다.각 용어는 $\alpha _{h}$ h ${\$ _ ${h$ 에 대응합니다. $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$ 서 h $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$ ( $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$ $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$ t $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$ - $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$ $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$ $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$ $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$ { $displaystyle$ h = ( 0 \ $rangle$ ^ { \ $otimes$ n $}$ \ $rightarrow$ \ $cdots u$ _ $right$ arrow _ { 1 $arrow$ } x 1 }

주장하다— $디스플레이 스타일약 QCircuit-PROB}\in {mathsf {PSPACE}}$

$\alpha _{x}$ x \displaystyle $\alpha$ _ ${x$ 을(를) 계산하는 Sum over histories 알고리즘에서는 계산의 임의의 지점에 하나의 이력만 저장됩니다.따라서 O( $O(nm)$ m $)\displaystyle$ O $(nm$ )\displaystyle O(nm $)$ 알고리즘에서는 O $($ $n$ m)\displaystyle O $(nm)$ 비트가 $O(nm)$ 일부 워크스페이스 변수와 함께 저장되어야 $O(nm)$ O $O(nm)$ $)\$ $displaystyle$ O $(nm$ )_ ${x}$ 비트를 $O(nm)$ $\alpha _{x}$ 사용하여 $임의$ 의 x를 $\alpha _{x}$ 합니다.

따라서 다항식 공간에서는 첫 번째 큐비트가 1인 $모든$ x에 대해 $\sum _{x}|\alpha _{x}|^{2}$ $\sum _{x}|\alpha _{x}|^{2}$ $\sum _{x}|\alpha _{x}|^{2}$ x $\sum _{x}|\alpha _{x}|^{2}$ (\ $displaystyle \sum$ _{ $x}$ \ $alpha$ _ ${x} ^{2$ }})를 계산할 수 있습니다.이것은 첫 번째 큐비트가 회로 끝에 1이 될 확률입니다.

${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ P ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ P (\ $style\mathsf {BQP}}\subseteq$ {\ $mathsf {EXP$ 의 증명에 대해 주어진 시뮬레이션과 비교할 때 이 알고리즘은 훨씬 적은 공간을 차지하지만 대신 훨씬 더 많은 시간을 소비합니다.실제로 단일 진폭을 계산하는 데 O $O(m2^{mn})$ $O(m2^{mn})$ m $O(m2^{mn})$ )(\ $displaystyle$ O $(m2^{mn})$ 시간이 $O(m2^{mn})$ .

BQP 및 PP

유사한 sum-over-histories 인수를 사용하여 ${\mathsf {BQP}}\subseteq {\mathsf {PP}}$ ${\mathsf {BQP}}\subseteq {\mathsf {PP}}$ P ${\mathsf {BQP}}\subseteq {\mathsf {PP}}$ P ${\mathsf {BQP}}\subseteq {\mathsf {PP}}$ { $display$ { $mathsf$ { $BQP}}$ \ $subseteq$ { $mathsf {PP}$ ${\mathsf {BQP}}\subseteq {\mathsf {PP}}$ 를 ${\mathsf {BQP}}\subseteq {\mathsf {PP}}$ 할 수 있습니다.

BQP, P 및 NP

우선 양자회로에 의해 모든 고전회로를 시뮬레이션할 수 있기 때문에 P ${\mathsf {P}}\subseteq {\mathsf {BQP}}$ Q ${\mathsf {P}}\subseteq {\mathsf {BQP}}$ { $displaystyle$ } \ $subseteq$ { $mathsf$ { $BQP$ } ${\mathsf {P}}\subseteq {\mathsf {BQP}}$ ^[14]

BQP는 P 이외의 어려운 문제, 구체적으로는 NP의 문제를 해결하는 것으로 추측됩니다.P=NP인지 알 수 없기 때문에 클레임은 무기한이기 때문에 실제로 P에 문제가 있는지 알 수 없습니다.다음은 추측의 몇 가지 증거입니다.

정수 인수 분해(쇼어 [15]알고리즘 참조)
이산 로그^[15]
양자 시스템의 시뮬레이션(범용 양자 시뮬레이터 참조)
통합의 특정 근에 대한 존스 다항식
Harrow-Hassidim-Loyd(HHL) 알고리즘

단, 블랙박스(black-box)라는 ${\mathsf {NP}}\not \subseteq {\mathsf {BQP}}$ 에서 N ${\mathsf {NP}}\not \subseteq {\mathsf {BQP}}$ ${\mathsf {NP}}\not \subseteq {\mathsf {BQP}}$ Q ${\mathsf {NP}}\not \subseteq {\mathsf {BQP}}$ P의 ${\mathsf {NP}}\not \subseteq {\mathsf {BQP}}$ (\ $displaystyle\subseteq\mathsf {BQP}$ 가 ${\mathsf {NP}}\not \subseteq {\mathsf {BQP}}$ 아님)도 알고 있습니다.구조화되지 않은 검색 문제에 대해 생각해 보십시오. $f:\{0,1\}^{n}\to \{0,1\}$ 수 $f:\{0,1\}^{n}\to \{0,1\}$ 함수 $f:\{0,1\}^{n}\to \{0,1\}$ f $f:\{0,1\}^{n}\to \{0,1\}$ : $f:\{0,1\}^{n}\to \{0,1\}$ { $f:\{0,1\}^{n}\to \{0,1\}$ , $}$ $f:\{0,1\}^{n}\to \{0,1\}$ { 0 , $1$ }^{n} \ $to$ \ { $0$ , $1$ \ $f:\{0,1\}^{n}\to \{0,1\}$ 에 대한 오라클 액세스가 주어지면 $f(x)=1$ f ( $f(x)=1$ ) $f(x)=1$ $f(x)=1$ { $displaystyle$ f ( x ) = $1$ = $f(x)=1$ 1 $f(x)=1$ $f(x)=1$ 문제는 분명히 NP에 $있습니다$ .한편,^[16] 이 문제의 최적의 양자 알고리즘은 Grover 알고리즘입니다. $O({\sqrt {2^{n}}})$ ( 2 $O({\sqrt {2^{n}}})$ ) \ $displaystyle$ O ( { \ $sqrt$ { $2$ ^ { $n$ } } } $O({\sqrt {2^{n}}})$ if the $O({\sqrt {2^{n}}})$

「」를 참조해 주세요.

숨겨진 부분군 문제
다항식 계층(PH)
양자 복잡도 이론
QMA, NP에 해당하는 양자.
QIP , IP에 상당하는 양자.

레퍼런스

^ ^a ^b ^c 마이클 닐슨과 아이작 츄앙(2000).양자 계산 및 양자 정보.케임브리지:케임브리지 대학 출판부 ISBN 0-521-63503-9.
^ ^a ^b ^c ^d Bernstein, Ethan; Vazirani, Umesh (October 1997). "Quantum Complexity Theory". SIAM Journal on Computing. 26 (5): 1411–1473. CiteSeerX 10.1.1.655.1186. doi:10.1137/S0097539796300921.
^ Barak, Sanjeev Arora, Boaz (2009). Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak. Cambridge. p. 122. Retrieved 24 July 2018.
^ Michael A. Nielsen; Isaac L. Chuang (9 December 2010). "4.4 Measurement". Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. p. 186. ISBN 978-1-139-49548-6.
^ Odel A. Cross (5 November 2012). "5.2.2 Deferred Measurement". Topics in Quantum Computing. O. A. Cross. p. 348. ISBN 978-1-4800-2749-7.
^ Fortnow, Lance; Rogers, John (1999). "Complexity limitations on Quantum computation" (PDF). J. Comput. Syst. Sci. 59 (2): 240–252. arXiv:cs/9811023. doi:10.1006/jcss.1999.1651. ISSN 0022-0000. S2CID 42516312.
^ L. 애들먼, J. 드마라, M.-D.황. 양자 계산 능력.SIAM J. Comput., 26(5): 1524–1540, 1997.
^ George, Michael Goderbauer, Stefan. "ECCC - TR18-107". eccc.weizmann.ac.il. Retrieved 2018-08-03.
^ ^a ^b Aaronson, Scott (2010). "BQP and the Polynomial Hierarchy" (PDF). Proceedings of ACM STOC 2010.
^ Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 (2063): 3473–3482. arXiv:quant-ph/0412187. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005.1546. S2CID 1770389.. 프리프린트는 [1]에서 이용 가능합니다.
^ Aaronson, Scott (2004-01-11). "Complexity Class of the Week: PP". Computational Complexity Weblog. Retrieved 2008-05-02.
^ E. 번스타인과 U. Vazirani.양자 복잡도 이론, SIAM Journal on Computing, 26(5): 1411-1473, 1997.
^ L. Adleman, J. DeMarrais, M.Huang. 양자 계산 가능성, SIAM Journal on Computing 26:1524-1540, 1997.
^ 닐슨, 마이클 A;Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, 캠브리지:케임브리지 대학 출판부, ISBN 0-521-63235-8, MR 1796805.
^ ^a ^b arXiv:quant-ph/9508027v2 양자 컴퓨터의 소수 인수분해 및 이산 대수를 위한 다항식-시간 알고리즘, Peter W.쇼르
^ Zalka, Christof (1999-10-01). "Grover's quantum searching algorithm is optimal". Physical Review A. 60 (4): 2746–2751. arXiv:quant-ph/9711070. doi:10.1103/PhysRevA.60.2746.

외부 링크

Wayback Machine에서 BQP Archived 2013-06-03에 대한 복잡성 동물원 링크

[Chuang2000-1] 마이클 닐슨과 아이작 츄앙(2000).양자 계산 및 양자 정보.케임브리지:케임브리지 대학 출판부 ISBN 0-521-63503-9.

[BernVazi-2] Bernstein, Ethan; Vazirani, Umesh (October 1997). "Quantum Complexity Theory". SIAM Journal on Computing. 26 (5): 1411–1473. CiteSeerX 10.1.1.655.1186. doi:10.1137/S0097539796300921.

[3] Barak, Sanjeev Arora, Boaz (2009). Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak. Cambridge. p. 122. Retrieved 24 July 2018.

[NielsenChuang2010-4] Michael A. Nielsen; Isaac L. Chuang (9 December 2010). "4.4 Measurement". Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. p. 186. ISBN 978-1-139-49548-6.

[Cross2012-5] Odel A. Cross (5 November 2012). "5.2.2 Deferred Measurement". Topics in Quantum Computing. O. A. Cross. p. 348. ISBN 978-1-4800-2749-7.

[6] Fortnow, Lance; Rogers, John (1999). "Complexity limitations on Quantum computation" (PDF). J. Comput. Syst. Sci. 59 (2): 240–252. arXiv:cs/9811023. doi:10.1006/jcss.1999.1651. ISSN 0022-0000. S2CID 42516312.

[7] L. 애들먼, J. 드마라, M.-D.황. 양자 계산 능력.SIAM J. Comput., 26(5): 1524–1540, 1997.

[8] George, Michael Goderbauer, Stefan. "ECCC - TR18-107". eccc.weizmann.ac.il. Retrieved 2018-08-03.

[:0-9] Aaronson, Scott (2010). "BQP and the Polynomial Hierarchy" (PDF). Proceedings of ACM STOC 2010.

[PostBQP=PP-10] Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 (2063): 3473–3482. arXiv:quant-ph/0412187. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005.1546. S2CID 1770389.. 프리프린트는 [1]에서 이용 가능합니다.

[11] Aaronson, Scott (2004-01-11). "Complexity Class of the Week: PP". Computational Complexity Weblog. Retrieved 2008-05-02.

[12] E. 번스타인과 U. Vazirani.양자 복잡도 이론, SIAM Journal on Computing, 26(5): 1411-1473, 1997.

[13] L. Adleman, J. DeMarrais, M.Huang. 양자 계산 가능성, SIAM Journal on Computing 26:1524-1540, 1997.

[14] 닐슨, 마이클 A;Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, 캠브리지:케임브리지 대학 출판부, ISBN 0-521-63235-8, MR 1796805.

[Shor-15] rXiv:quant-ph/9508027v2 양자 컴퓨터의 소수 인수분해 및 이산 대수를 위한 다항식-시간 알고리즘, Peter W.쇼르

[16] Zalka, Christof (1999-10-01). "Grover's quantum searching algorithm is optimal". Physical Review A. 60 (4): 2746–2751. arXiv:quant-ph/9711070. doi:10.1103/PhysRevA.60.2746.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[14]

[15]

[16]

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

BQP

네임스페이스

더

목차

정의.