양자복잡성이론

이 문서에는 일반 참조 목록이 포함되어 있지만 해당 인라인 인용이 충분하지 않습니다. 좀 더 정확한 인용문을 소개하여 이 글을 개선할 수 있도록 도와주시기 바랍니다. (2020년 3월) (템플 제거 도움말)

양자 복잡도 이론은 양자역학에 기반한 계산 모델인 양자 컴퓨터를 사용하여 정의된 복잡도 클래스를 다루는 계산 복잡도 이론의 하위 분야입니다. 이러한 복잡도 클래스와 관련하여 계산 문제의 경도와 양자 복잡도 클래스와 고전적(즉, 비양자) 복잡도 클래스 간의 관계를 연구합니다.

두 가지 중요한 양자 복잡도 클래스는 BQP와 QMA입니다.

배경

복잡도 클래스는 특정 자원 제약 하에서 계산 모델에 의해 해결될 수 있는 계산 문제의 모음입니다. 예를 들어, 복잡도 클래스 P는 다항 시간 내에 튜링 기계에 의해 풀 수 있는 문제들의 집합으로 정의됩니다. 마찬가지로, 양자 복잡도 클래스는 양자 회로 모델 또는 동등한 양자 튜링 기계와 같은 계산의 양자 모델을 사용하여 정의될 수 있습니다. 양자 복잡도 이론의 주요 목적 중 하나는 이러한 클래스가 P, NP, BPP, PSPACE와 같은 고전적인 복잡도 클래스와 어떻게 관련되는지를 알아내는 것입니다.

양자 복잡도 이론이 연구되는 이유 중 하나는 현대 교회-튜링 논문에 대한 양자 컴퓨팅의 함의입니다. 간단히 말해서, 현대의 Church-Turing 논문은 모든 계산 모델이 확률적 튜링 기계로 다항 시간 내에 시뮬레이션될 수 있다고 말합니다.^[1][2] 그러나 교회-튜링 논문 주변의 질문은 양자 컴퓨팅의 맥락에서 발생합니다. Church-Turing 논문이 양자 계산 모델을 유지하는지 여부는 불분명합니다. 그 논문이 성립하지 않는다는 많은 증거가 있습니다. 확률론적 튜링 기계가 다항식 시간에 양자 계산 모델을 시뮬레이션하는 것은 불가능할 수 있습니다.^[1]

함수의 양자 계산 복잡도와 함수의 고전적 계산 복잡도는 모두 종종 점근 표기법으로 표현됩니다. 점근적 함수 개념의 일반적인 형태는 $O{\displaystyle (T(n))}$ ${\displaystyle$ O$(T(n$${\displaystyle }$ω${\displaystyle (}$T$($n)) ${\displaystyle \Omega$$T$(n${\displaystyle ))\},}$θ$($T(n))${\displaystyle$\Theta(T(n))}입니다. ${\displaystyle O(T(n))}$ expresses that something is bounded above by ${\displaystyle cT(n)}$ where ${\displaystyle c}$ is a constant such that ${\displaystyle c>0}$ and ${\displaystyle T(n)}$ is a function of ${\displaystyle n}$, ${\displaystyle \Omega (T(n))}$ expresses that something is bounded below by ${\displaystyle cT(n)}$ where ${\displaystyle c}$ is a constant such that ${\displaystyle c>0}$ and ${\displaystyle T(n)}$ is a function of ${\displaystyle n}$, 그리고${\displaystyle }$θ${\displaystyle (}$T$n))$ ${\displaystyle \Theta($T(n))}는 ${\displaystyle O(}$T$(n$)) ${\displaystyle$O(T($n{\displaystyle ))\}}$와$$ω(T(n))${\displaystyle$\Omega(T(n))}를${\displaystyle \mathrm{모두}}$ 표현합니다. 이 표기법에는 고유한 이름도 있습니다. ${\displaystyle O(T(n)}$ ${\$$displaystyle$ O$(T(n))}$를 Big O 표${\displaystyle 기}$법,${\displaystyle }$${\displaystyle \omega }$${\displaystyle (}$T$($n)) {\$displaystyle \Omega$(T(n)}를 Big ${\displaystyle \mathrm{Omega}}$ $표$${\displaystyle 기}$$법{\displaystyle ,}$θ(T($n)) {\displaystyle$ \Theta(T(n)}를 Big Theta 표기법이라고 합니다.

복잡도 클래스 개요

중요한 복잡도 클래스 P, BPP, BQP, PP, PSPACE는 약속 문제를 기준으로 비교할 수 있습니다. 약속 문제는 가능한 모든 입력 문자열의 집합에서 선택되는 것으로 가정되는 입력을 갖는 결정 문제입니다. 약속 문제는 쌍 $A$ =${\displaystyle }$($,$ $아니오$) ${\$displaystyle A = (A_{\$text{yes}})$입니다.$A_{\text{no$ 여기서 ${\displaystyle {\text{Ayes}}_{}}$ ${\$는 예 인스턴스의 집합이고 ${\displaystyle {\text{Ano}}_{}}${\$displaystyle A_{\text{no}}$는 인스턴스가 없는 집합이며 이러한 집합의 교집합은 비어 있습니다. ${\displaystyle {}_{}{}_{}{\text{예}}_{}}$ ${\displaystyle {}_{}}$ $o =$ ∅ ${\$displaystyle A_{\text{yes}\cap A_{\text${\displaystyle {\{}_{}}$no}}=\varnothing} 이전의 모든 복잡도 클래스에 약속 문제가 포함되어 있습니다.

복잡도 클래스	기준
P	${\displaystyle {\text{다항}}_{}}$ 시간 결정론적 튜링 기계가 예 ${\$의 모든 문자열을 받아들이고$$ 예 ${\$의 모든 문자열을 거부하는 약속 문제
BPP	다항 시간 확률론적 튜링 기계가 ${\displaystyle {\text{A예}}_{}}$ ${\$의 모든 문자열을 $최소{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{23}{}}${\$displaystyle {\frac$ {$2}{3}}$의 확률로$$ 받아들이는 약속 문제$,$ ${\displaystyle {\text{A}}_{}}$ ${\displaystyle \frac{\mathrm{no}}{}}$ ${\$no$}}$의 모든 문자열을 최대 13 ${\$의 확률로$$ 허용합니다.
BQP	함수 $a{\displaystyle ,}$ ${\displaystyle b}$: ${\displaystyle N}$ →${\displaystyle }$[${\displaystyle 0}$, 1${\displaystyle \mathrm{]}}$ ${\displaystyle a,b :\mathbb {N}$\ $to [0,1]}$에 대하여$,$ 양자 회로 $Q$ = ${\displaystyle \{Q}$ ${\displaystyle n_{}}$: $n$∈ N} {\displaystyle Q = {\{Q_{n}:n\in \mathbb {N} \}}, $여기$서 ${\displaystyle {Qn}_{}}$ ${\$은 $n개$의$${\$displaystyle n}$ 큐비트를$$ 수신하고 1 큐비트의 출력을 제공하는 회로입니다. ${\displaystyle {\text{A}}_{}}$yes {\$displaystyle A_{\text${yes$$$}}$의 요소$$x {\$displaystyle$ x$}$은${\displaystyle }$($)$ {\$displaystyle a(\left\vert x\$right\$vert )}$ 이상의$$ $확률$로$$Q {\$displaystyle$ Q$}$에서 허용됩니다$.$ $A{\displaystyle }$ ${\displaystyle {\text{no}}_{}}$ ${\$의 $요소{\displaystyle }$ x${\displaystyle$ $x$$}$는 $b{\displaystyle (x)}$ ${\displaystyle b(\left\vert x\right\vert )}$ 이하의 확률로$$ Q ${\displaystyle$ Q$}$에서 허용됩니다$.$[4]
피피	다항 시간 확률론적 튜링 기계가 ${\displaystyle \frac{\mathrm{확률}}{}}$이$$12보다$$ 큰 예${\$$displaystyle$$A_{\$$text{$$yes}}$의 모든 문자열을 받아들이는 약속 문제$,$ $최대$ ${\displaystyle \frac{12}{}}$ ${\$ ${\text{no}}$의 확률로 A no {\displaystyle {\frac ${1}{2}}$의 모든 문자열을 허용합니다$.$
PSPACE	다항식 공간에서 실행되는 결정론적 튜링 기계가 ${\displaystyle {\text{A예}}_{}}${\$displaystyle A_{\text{yes}}$의 모든 문자열을 받아들이고$$ ${\displaystyle {\text{A예}}_{}}${\$displaystyle A_{\text{no}}$의 모든 문자열을 거부하는 약속 문제

BQP

BQP 알고리즘 (1회 실행)

정답. 생산된 맞아요. 정답.	네.	아니요.
네.	≥ 2/3	≤ 1/3
아니요.	≤ 1/3	≥ 2/3

경계 오류가 있는 양자 컴퓨터가 효율적으로 해결할 수 있는 문제의 종류를 BQP("경계 오류, 양자, 다항 시간")라고 합니다. 좀 더 공식적으로 BQP는 오차 확률이 최대 1/3인 다항 시간 양자 튜링 기계로 풀 수 있는 문제의 종류입니다.

BQP는 확률론적 문제의 한 종류로서, BPP의 양자 대응물로서, 제한된 오류가 있는 확률론적 튜링 기계에 의해 효율적으로 해결될 수 있는 문제의 한 종류입니다.^[6] ${\displaystyle \mathsf{BPP}}$ ⊆ $BQP$ {\$displaystyle {\mathsf$ {$BPP\subseteq$ BQP}},$BQP$ ⊈ BP${\displaystyle${\$mathsf$ {$BQP$\nsubseteq BPP}}라고 널리 의심되지만 $입증$되지 않은 것으로 알려져 있는데, 이는 양자 컴퓨터가 고전 컴퓨터보다 시간 복잡도 측면에서 더 강력하다는 것을 직관적으로 의미할 것입니다. BQP는 PP의 하위 집합입니다.

BQP와 P, NP, PSPACE의 정확한 관계는 알려져 있지 않습니다. $그러나$, ${\displaystyle \mathsf{P}}$⊆ ${\displaystyle \mathsf{B}}$ ${\displaystyle \mathsf{QP}}$ ⊆ $PSPACE {\displaystyle${\$mathsf {$P\subseteq $BQP\$subseteq PSPACE}}; 즉$,$ 양자 컴퓨터가 효율적으로 해결할 수 있는 문제의 종류에는 결정론적 고전 컴퓨터가 효율적으로 해결할 수 있는 모든 문제가 포함되지만 다항식 공간 자원을 가진 고전 컴퓨터가 해결할 수 없는 문제는 포함되지 않습니다. BQP가 P의 엄밀한 초집합이라는 의심은 더 나아가 결정론적 고전 컴퓨터가 효율적으로 해결할 수 없는 양자 컴퓨터가 효율적으로 해결할 수 있는 문제들이 있다는 것을 의미합니다. 예를 들어, 정수 인수분해와 이산 로그 문제는 BQP에 있는 것으로 알려져 있고 P를 벗어난 것으로 의심됩니다. BQP와 NP의 관계에 대해서는 일부 NP 문제가 BQP에 있다는 사실 외에는 거의 알려져 있지 않습니다(예를 들어, 정수 인수분해와 이산 로그 문제는 둘 다 NP에 있습니다). ${\displaystyle \mathsf{NP}}$ ⊈ $BQP {\displaystyle {\mathsf$ {$NP\nsubseteq$BQP}}; 즉, 양자 컴퓨터로 효율적으로 해결할 수 없는 효율적으로 확인할 수 있는 문제가 있는 것으로 추정됩니다. 이러한 믿음의 직접적인 결과로, BQP가 NP-완전 문제의 클래스와 분리되어 있다는 의심도 있습니다(만약 NP-완전 문제가 BQP에 있다면, NP-경도에서 NP의 모든 문제가 BQP에 있다는 것이 뒤따릅니다).^[8]

BQP와 본질적인 고전적 복잡성 클래스의 관계는 다음과 같이 요약될 수 있습니다.

${\displaystyle {\mathsf {P\subseteq BPP\subseteq BQP\subseteq PP\subseteq PSPACE}}}$

${\displaystyle \mathsf{또한}}{\displaystyle \mathsf{}}$BQP는 PSPACE의 하위 $집합$인 복잡도 클래스$#$ P {\$displaystyle \color$ {Blue}{\mathsf ${\#P}}($또는 더 정확하게는 연관된 결정 문제 클래스 ${\displaystyle {\mathsf{P}\mathsf{}}^{}}$# P ${\${\$mathsf {P^{\#P}}})$^[8]에 포함되어 있다고 알려져 있습니다.

양자회로 시뮬레이션

고전 컴퓨터로 양자 계산 모델을 효율적으로 시뮬레이션할 수 있는 방법은 알려진 바가 없습니다. 이것은 고전 컴퓨터가 다항식 시간에 양자 계산 모델을 시뮬레이션할 수 없다는 것을 의미합니다. $그러나{\displaystyle }$ $T{\displaystyle (n)}$ ${\displaystyle T(n)}$개의$$ 양자 게이트를 갖는 S${\displaystyle (n)}$ ${\displaystyle S(n)}$ 큐비트의$$ 양자 회로는 $O{\displaystyle ({\mathrm{}}^{}}$ ${\displaystyle {S(n)}^{}}$ ${\displaystyle {}^{}({n\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$ ${\displaystyle$ O$(2^{S(n)}T(n)^{3)}$개의 고전 게이트를 갖는 고전 회로에 의해 시뮬레이션될 수 있습니다.^[3] 이 고전적인 게이트의 수는 양자 회로를 시뮬레이션하기 위해 얼마나 많은 비트 연산이 필요한지를 결정함으로써 얻어집니다. 이를 위해서는 먼저 $S{\displaystyle (n)}$ ${\displaystyle$ S$(n)}$ 큐비트와$$ 관련된 진폭을 설명해야 합니다. $S{\displaystyle (n)}$ ${\displaystyle$ S$(n)}$ 큐비트의$$ 각 상태는 2차원 복소 벡터 또는 상태 벡터로 설명할 수 있습니다. 이러한 상태 벡터는 진폭이라고 불리는 계수를 가진 구성 요소 벡터의 선형 조합으로도 설명할 수 있습니다. 이러한 진폭은 1로 정규화된 복소수로, 진폭의 절대값 제곱의 합은 1이어야 함을 의미합니다.^[3] 상태 벡터의 항목은 이러한 진폭입니다. 각 진폭이 성분 벡터의 0이 아닌 성분에 해당하는 성분은 선형 조합 설명의 계수에 해당합니다. As an equation this is described as ${\displaystyle \alpha {\begin{bmatrix}1\\0\end{bmatrix}}+\beta {\begin{bmatrix}0\\1\end{bmatrix}}={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}}$ or ${\displaystyle \alpha$$\left\vert$ 1$\right\rangle +\beta \left\$vert 0\right\rangle $=${\$begin${bmatrix}\alpha \\\\$beta$ \end{bmatrix}}}를 디랙 표기법을 사용합니다. 전체 $S{\displaystyle (n)}$ ${\displaystyle$ S$(n)}$ 큐비트$$ 시스템의 상태는 단일 상태 벡터로 설명할 수 있습니다. 전체 시스템을 설명하는 이 상태 벡터는 시스템의 개별 큐비트를 설명하는 상태 벡터의 텐서 곱입니다. $S{\displaystyle (n)}$ ${\displaystyle S(n)}$ 큐비트의$$ 텐서 곱의 결과는 $2{\displaystyle {\mathrm{}}^{}}$ S${\displaystyle {(n)}^{}}$ ${\$ 2$^{S(n)}$ 차원$$ 및 각 기본 상태 또는 구성 요소 벡터와 관련된 진폭인 엔트리를 갖는 단일 상태 벡터입니다. $따라서{\displaystyle {\mathrm{}}^{}}$ 2 ${\displaystyle {S(n}^{}}$) ${\$ 2$^{S(n)}}$ 진폭은$$ $S{\displaystyle (n)}$ ${\$$displaystyle$ $2$$^{S(n$$)}$ 큐비트$$ 시스템의 상태 벡터인 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {S(n)}^{}}$ ${\$$displaystyle$ 2^{S$(n$)} 차원$$ 복소 벡터로 설명해야 합니다.^[9] 양자 회로를 시뮬레이션하는 데 필요한 게이트 수에 대한 상한을 얻으려면 2 S(${\displaystyle {n)}^{}}$ ${\$개의 진폭$$ 각각에 대한 정보를 지정하는 데 사용되는 양 데이터에 대한 충분한 상한이 필요합니다. $이렇게{\displaystyle }$ 하려면 O${\displaystyle O(T(n))}$비트의$$ 정밀도로 각 진폭을 인코딩할 수 있습니다.^[3] $따라서{\displaystyle }$ S${\displaystyle (n)}$ ${\displaystyle S(n)}$ 큐비트$$ 시스템의 상태 벡터를 설명하려면 $O{\displaystyle ({\mathrm{}}^{}}$ ${\displaystyle {S(n)}^{}}$ ${\displaystyle {}^{}(n)}$ ${\displaystyle O(2^{S(n))}T(n)}$ 고전$$ 비트가 필요합니다. $다음$으로 ${\displaystyle {2S(n)}^{}}$ ${\$ 진폭의$$ T${\displaystyle (n)}$ ${\displaystyle T(n)}$ 양자$$ 게이트 적용을 설명해야 합니다. 양자 게이트는 $2{\displaystyle {\mathrm{}}^{}}$ S${\displaystyle {(n)}^{}}$× ${\displaystyle 2^{}}$ ${\displaystyle {\mathrm{}}^{(n)}}$ ${\$ 2$^{S(n)}\times 2^{S(n)}}$ 희소$$ 행렬로 표현할 수 있습니다.^[3] 따라서 각 $T{\displaystyle }$${\displaystyle (n}$${\displaystyle {}^{}}$$${\$displaystyle$T($n)}$ 양자$$$$ 게이트의 적용을 설명하려면 상태 ${\displaystyle {벡터}^{}}$에 T${\displaystyle {(}^{}}$${\displaystyle n)}$ ${\displaystyle T(n)}$ 양자 ${\displaystyle {\mathrm{게이트}}^{}}$ 각각에 대해 2 S(n) × 2 S(n$)$ {\displaystyle $2^{S(n)}\times$ 2$^{S(n$)}} 희소$$ 행렬을 곱해야 합니다. 상태 벡터에 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {S(n)}^{}}$× ${\displaystyle 2^{}}$ ${\displaystyle {\mathrm{}}^{(n)}}$ ${\$ 2$^{S(n)}\times$ 2$^{S(n)}}$ 희소$$ 행렬이 곱해질 때마다 $O{\displaystyle ({\mathrm{}}^{}}$ ${\displaystyle {S(n}^{}}${\$displaystyle O(2^{S(n)}}$ 산술$$ 연산을 수행해야 합니다.^[3] 따라서 상태 벡터에 적용되는 모든 양자 게이트에 대해 $O{\displaystyle ({2S(n)}^{}}$ ${\displaystyle {}^{}(n{}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle$ O$(2^{S(n)}T(n)^{2)}$ 비트$$ 연산이 있습니다. 따라서 단 하나의 양자 게이트로 $S{\displaystyle (n)}$ ${\displaystyle S(n)}$ $큐비트$$$ 회로를 시뮬레이션하려면 $($ $(n$ T$(n)^{2)}$ 고전$$ $게이트$가 필요합니다. $따라서{\displaystyle }$${\displaystyle ,}$ $T{\displaystyle }$(${\displaystyle {\mathrm{}}^{)}}$ {\displaystyle $T$(${\displaystyle n{}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$ ${\displaystyle O(2^{S(n)}T(n)^{3)}$ 고전$$ 게이트는 T${\displaystyle (n)}$ ${\displaystyle$ T$(n)}$ 양자$$ 게이트를 갖는 S(n) {\$displaystyle S(n)}$ 큐비트의$$ 양자 회로를 시뮬레이션하기 위해 필요합니다.^[3] 양자 컴퓨터를 고전 컴퓨터로 효율적으로 모사할 수 있는 방법은 알려져 있지 않지만 양자 컴퓨터로 고전 컴퓨터를 효율적으로 모사할 수 있습니다. $이$는 ${\displaystyle \mathsf{BPP}}$ ⊆ $BQP$ {\$displaystyle {\mathsf$ {$BPP\subseteq$BQP}}을(를) 표시하는 것에서 분명합니다.

양자 질의 복잡도

고전적인 것 대신 양자 계산 시스템을 사용하는 것의 한 가지 큰 장점은 고전적인 다항 시간 알고리즘이 존재하지 않는 어떤 문제에 대해 양자 컴퓨터가 다항 시간 알고리즘을 제공할 수 있을지도 모른다는 것이지만, 더 중요한 것은, 양자 컴퓨터는 고전 컴퓨터가 이미 효율적으로 풀 수 있는 문제의 계산 시간을 크게 줄일 수 있습니다. 근본적으로 양자 컴퓨터는 문제를 해결하는 데 걸리는 시간을 결정할 수 있는 반면 고전 컴퓨터는 문제를 해결하지 못할 수 있으며 특정 문제의 해결과 관련된 계산 효율성을 크게 향상시킬 수 있습니다. 양자 질의 복잡도는 문제를 해결하기 위해 특정 문제의 해결책과 관련된 그래프에 얼마나 많은 질의가 필요한지 또는 얼마나 많은 질의가 필요한지를 나타냅니다. 쿼리 복잡성에 대해 자세히 살펴보기 전에 특정 문제에 대한 그래핑 솔루션과 이러한 솔루션과 관련된 쿼리에 대한 몇 가지 배경을 고려해 보겠습니다.

방향 그래프의 모형 쿼리

양자 컴퓨팅이 더 쉽게 해결할 수 있는 문제의 한 유형은 그래프 문제입니다. 주어진 문제를 해결하는 데 필요한 그래프에 대한 쿼리의 양을 고려하려면 먼저 이러한 유형의 계산 모델링과 관련된 가장 일반적인 유형의 그래프인 지시 그래프를 고려해 보겠습니다. 간단히 말해서, 방향 그래프는 정점 사이의 모든 간선이 단방향인 그래프입니다. 방향 그래프는 그래프 $G$ =${\displaystyle }$(${\displaystyle N,}$E) {\displaystyle G = (N, E)}로 공식적으로 정의됩니다. 여기서 N은 정점 또는 노드의 집합이고 E는 간선의 집합입니다.

인접행렬모형

방향 그래프 문제에 대한 솔루션의 양자 계산을 고려할 때 이해해야 할 두 가지 중요한 쿼리 모델이 있습니다. First, there is the adjacency matrix model, where the graph of the solution is given by the adjacency matrix: ${\displaystyle M\in \{0,1\}a^{n\mathrm {X} n}}$, with ${\displaystyle M_{ij}=1}$, if and only if ${\displaystyle (v_{i},v_{j})\in E}$.^[11]

인접 배열 모델

다음으로, 인접 목록의 아이디어를 기반으로 구축된 약간 더 복잡한 인접 배열 모델이 있으며, $모든$ 정점 u${\display u}$은 ${\displaystyle {fi}_{}}$:${\displaystyle }$[${\displaystyle {di}_{}^{}}$+${\displaystyle {}_{}^{}}$] →${\displaystyle }$[${\displaystyle n}$] ${\displaystyle f_{i}:[d_{i}^{+}]\rightarrow [n$ ${\displaystyle {정점}_{}^{}{}_{}^{}}$+${\displaystyle }$.${\displaystyle }$. . ${\displaystyle {}_{}^{}}$+$${\$displaystyle d_{$i}^{+}, $...,d_{$n$\}^\{+\}$의 아웃 degrees에 대해 n$${\$displaystyle$n}은 이 모델의 상한의 최소값입니다. $그리고$ ${\displaystyle {fi}_{}}$(${\displaystyle j)}$ ${\displaystyle f_{i}(j))$는 $i$ ${\displaystyle$ i$}$에 인접한 "${\displaystyle {\mathrm{j번째}}^{}}$ ${\displaystyle j^{th$ 정점을 반환합니다$.$ 또한 인접 배열 모델은 단순 그래프 ${\displaystyle \mathrm{조건}}$인 ∀${\displaystyle }$i ∈${\displaystyle }$[n${\displaystyle \mathrm{],}}$ j, j' ∈ [k]를 만족합니다.$≠$ $j$':${\displaystyle {}^{}}$ ${\displaystyle (j_{}}$≠ fi (j')${\displaystyle \forall i\in$ [$n],j,j'\in [k],j\neq j':f_{i}($j$)\backslash$neq f_{i}(j')}. 즉, 임의의 정점 쌍 사이에는 하나의 간선만 있고 전체 모델에서 간선의 수가 최소화됩니다(자세한 배경은 스패닝 트리 모델 참조).

특정 유형의 그래프 문제의 양자 쿼리 복잡성

위의 두 모델 모두 연결, 강력한 연결(연결 모델의 지시된 그래프 버전), 최소 스패닝 트리 및 그래프의 단일 소스 최단 경로 모델을 포함하여 특정 유형의 그래프 문제의 쿼리 복잡성을 결정하는 데 사용할 수 있습니다. 고려해야 할 중요한 주의 사항은 특정 유형의 그래핑 문제의 양자 복잡도가 솔루션을 결정하는 데 사용되는 쿼리 모델(즉, 행렬 또는 배열)에 따라 변경될 수 있다는 것입니다. 다음 표는 이러한 유형의 그래핑 문제의 양자 질의 복잡도를 잘 보여줍니다.

특정 유형의 그래프 문제의 양자 쿼리 복잡성

문제	행렬모형	배열모형
최소 신장 트리	${\displaystyle \Theta(n^{3/2})}$	${\displaystyle \Theta({\sqrt {nm}})}$
커넥티비티	${\displaystyle \Theta(n^{3/2})}$	${\displaystyle \Theta(n)}$
강력한 연결성	${\displaystyle \Theta(n^{3/2})}$	${\displaystyle \mathrm{}}$($n$m ) ${\$displaystyle \$Omega ({\$sqrt {nm}}}, O (n m ${\displaystyle \mathrm{l}}$og ⁡ (n)) {\displaystyle O ({\sqrt {nm\log(n))}}
단일 소스 최단 경로	${\displaystyle \mathrm{}}$n 3 / $2$) ${\displaystyle$\Omega$($${\displaystyle n^{}}$$^\{$$3{\displaystyle /{\})\},}^{}}$ O($n$ ${\displaystyle 3^{}}$/${\displaystyle }$2 ${\displaystyle \mathrm{lo}}$${\displaystyle \mathrm{g}}$$$2 ⁡$n) {\displaystyle$ O$($n^{3/2}\log ^{2}n)}	${\displaystyle \mathrm{}}$($n$m) ${\$displaystyle \Omega$({\$sqrt {$nm}}},$ O(n m lo${\displaystyle \mathrm{g}}$ 2 ⁡(n)) {\displaystyle O({\sqrt {nm}}\log ^{2}(n))}

복잡성을 결정하는 데 사용된 쿼리 모델에 따라 특정 유형의 문제와 관련된 양자 쿼리 복잡성 사이의 불일치에 주목하십시오. 예를 들어 행렬 모델을 사용할 경우 Big O 표기법에서 연결 모델의 양자 복잡도는${\displaystyle {}^{}}$θ$$θ(${\displaystyle n^{}}$3$$/ 2) ${\displaystyle \Theta($n$^\{$3/ 2})}이지만 배열 모델을 사용할 경우${\displaystyle }복잡도$는${\displaystyle }$θ ((n)${\displaystyle$\Theta(n)}입니다. 추가적으로 간결성을 위해, 특정한 $경우$에 단축 m ${\displaystyle m}$을 사용합니다. 여기서 $m$ = θ (n 2) {\displaystyle m=\$theta(n^{2$^[11] 여기서 중요한 의미는 그래프 문제를 해결하는 데 사용되는 알고리즘의 효율성이 그래프 모델링에 사용되는 쿼리 모델의 유형에 따라 달라진다는 것입니다.

다른 유형의 양자 계산 쿼리

쿼리 복잡성 모델에서 입력은 오라클(블랙박스)로도 제공될 수 있습니다. 알고리즘은 오라클을 쿼리하여 입력에 대한 정보만 가져옵니다. 알고리즘은 어떤 고정된 양자 상태에서 시작하고 오라클에 질의할 때 상태가 진화합니다.

그래핑 문제의 경우와 마찬가지로 블랙박스 문제의 양자 쿼리 복잡도는 함수를 계산하기 위해 필요한 오라클에 대한 쿼리 중 가장 적은 수의 쿼리입니다. 이것은 양자 쿼리 복잡성을 함수의 전체 시간 복잡성에 대한 하한으로 만듭니다.

그로버 알고리즘

양자 컴퓨팅의 힘을 보여주는 예로 비정형 데이터베이스를 검색하는 Grover의 알고리즘을 들 수 있습니다. 알고리즘의 양자 쿼리 복잡도는 $O(N)$ ${\$이며$,$ 선형 검색인 최상의 고전 쿼리 복잡도 $O{\displaystyle (N)}$ ${\displaystyle$ O$(N)}$보다 2차 개선된 것입니다. Grover의 알고리즘은 점근적으로 최적이며, 실제로 가능한 최상의 알고리즘보다 많은 쿼리를 사용하는 $최대{\displaystyle \mathrm{}}$ 1${\displaystyle }$+ ${\displaystyle o}$(${\displaystyle 1)}$ ${\displaystyle 1+o$ ($1)}$ 분율입니다$$.^[12]

Deutsch-Jozsa 알고리즘

Deutsch-Jozsa 알고리즘은 고전적 알고리즘으로 가능한 것보다 더 작은 질의 복잡도로 장난감 문제를 해결하도록 설계된 양자 알고리즘입니다. 장난감 문제는 $함수$ f${\displaystyle :}${ ${\displaystyle 0,}$ ${\displaystyle 1^{}}$ ${\displaystyle {}^{}}$ n →${\displaystyle }${ ${\displaystyle 0}$, ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle$ f$:\{0,1\}^{n}\rightarrow \{0,1\}$가 상수인지 균형이 잡히는지 묻는 것으로, 이는 두 가지 가능성뿐입니다. ${\displaystyle f}$ 기능을 $평가$하는 유일한 방법은 블랙박스 또는 오라클을 참조하는 것입니다$$. 고전적인 결정론적 알고리즘은 함수가 일정한지 균형이 잡혔는지를 확인하기 위해 가능한 입력의 절반 이상을 확인해야 합니다. ${\displaystyle {2n}^{}}$ ${\$ 2$^{n}}$ 가능한$$ 입력으로 가장 효율적인 고전적 결정론적 알고리즘의 쿼리 복잡도는 ${\displaystyle {2n}^{}}$- ${\displaystyle 1^{}}$+ ${\displaystyle 1}$ ${\displaystyle$ 2$^{n-1}+1}$입니다$.$^[2] Deutsch-Jozsa 알고리즘은 양자 병렬성을 활용하여 도메인의 모든 요소를 한 번에 확인하고 오라클을 한 번만 쿼리하면 되므로 쿼리 복잡성이 $1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$이 됩니다$.$^[2]

양자물리학의 다른 이론들

물리학의 더 많은 발전은 더 빠른 컴퓨터로 이어질 수 있다고 추측되어 왔습니다. 예를 들어, Bohmian Mechanics 기반의 비국소 은닉 변수 양자 컴퓨터는 기껏해야 O$($ {\$displaystyle O({\sqrt[{3}]}}$에서 N-항목 데이터베이스 검색을 구현할 수 있는 것으로 나타났습니다.$N{\displaystyle }$$})}$ 단계$$, O${\displaystyle (N)}$ ${\display O({\sqrt {N}}$ 단계에서$$ 실행되는 Grover의 알고리즘보다 약간 더 빠른 속도입니다. 그러나 두 검색 방법 모두 양자 컴퓨터가 다항식 시간 내에 NP-완전 문제를 해결하는 것을 허용하지는 않습니다.^[13] M이론이나 고리양자중력과 같은 양자중력 이론은 더 빠른 컴퓨터를 만들 수 있게 해줍니다. 그러나 이러한 이론에서 계산을 정의하는 것은 시간의 문제로 인해 미해결 문제입니다. 즉, 이러한 물리적 이론 내에서는 관찰자가 한 시점에서 컴퓨터에 입력을 제출한 후 나중 시점에서 출력을 수신하는 것이 무엇을 의미하는지 명확한 설명 방법이 현재 없습니다.^[14][15]

참고 항목

• 양자전산
• 양자 튜링 기계
• 다항식 계층(PH)

메모들

참고문헌

• Nielsen, Michael; Chuang, Isaac (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 978-0-521-63503-5. OCLC 174527496.
• Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. pp. 201–236. ISBN 978-0-521-42426-4.
• Watrous, John (2008). "Quantum Computational Complexity". arXiv:0804.3401v1 [quant-ph].
• 와트러스 J. (2009) 양자 계산 복잡도. 인: 마이어스 R. (eds) 복잡성과 시스템 과학 백과사전. 스프링어, 뉴욕, 뉴욕

외부 링크

• 스콧 애런슨의 MIT 강의