문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 양자컴퓨터 (문단 편집) === 고속 연산 === 흔히 양자컴퓨터에 대해 알려져 있는 오해는, 양자컴퓨터는 일종의 병렬 계산을 할 수 있어서 (양자 중첩으로) 고전 컴퓨터보다 훨씬 빠른 연산이 가능하다고 생각하는 것이다. 0과 1이라는 비트 대신에, 0이라는 상태와 1이라는 상태의 임의의 선형 결합이 가능하다는 양자역학적 특성을 보면 그 설명이 자연스러운듯이 느껴지기도 한다. 또한 일반적으로 양자컴퓨터에 대한 대중적인 설명을 할 때 거의 예외 없이 그런 설명이 나온다. 하지만 이는 올바른 설명이 아니다. 만일 정말로 그렇다면, 병렬 계산에 의해 임의의 [[P-NP 문제|NP 문제]]는 효율적으로 풀릴 수 있으므로[* 각각의 witness들에 대해 병렬적으로 이들이 올바른 NP witness인지 확인한다.] 양자 컴퓨터는 임의의 NP 문제를 효율적으로 풀 수 있어야 할 텐데, 아마도 그렇지 않을 것임을 시사하는 증거들이 있기 때문이다. 이를 이해하는 또 한 가지 방법은 양자 계산과 확률적 계산을 비교하는 것이다. 2^^n^^개의 상자가 있고, 그 상자들 중 단 하나에 공이 들어있다고 하자. 공이 들어있는 상자를 '''확실히''' 찾기 위해서는 고전 컴퓨터는 2^^n^^번 상자를 열어야 한다. 양자 컴퓨터가 만일 그 '병렬성'을 이용해서 이 문제를 풀 수 있다면, 상자를 한 번만 열어보면 될 것이다: 열어볼 상자의 번호를 n비트로 적어서, 그 번호에 해당하는 상자를 연다. 다만, 여는 동작을 하기 전에 가능한 2^^n^^개의 n비트 번호들을 양자 중첩 상태로 만들어서 이들을 각각 열면 될 것이다. 하지만, 비슷한 일을 확률적 알고리즘으로도 마찬가지로 수행할 수 있다: 동전을 n번 던져서 상자의 번호 n비트를 모두 결정한 뒤에, 결정된 번호의 상자를 열면 된다. 0번 상자를 여는 행위부터 2^^n^^-1번 상자를 여는 행위까지가 확률적으로 '중첩'되어 있고, 각각의 상자에 대해서 그 상자를 열고 공을 발견할 확률이 0보다 크기 때문이다. 위와 같은 말을 들으면 거의 누구라도 '하지만 그렇다면 상자를 열어서 공을 발견할 확률은 기하급수적으로 작은 2^^-n^^밖에 되지 않으므로 사실상 못 찾는다고 봐야겠네요'라고 곧장 반박할 것이다. 물론 그렇다. 그리고 정확히 같은 반박을 양자컴퓨터에 대해서도 적용할 수 있다. 확률적 알고리즘도 가능한 모든 상태의 확률적 중첩을 만들어낼 수 있지만 그렇게 하면 각각의 상태가 갖는 확률이 기하급수적으로 작아져서 의미없는 알고리즘이 되듯이, 양자알고리즘 또한 가능한 모든 상태의 양자적 중첩을 만들어낼 수 있지만 그렇게 하면 각각의 상태가 갖는 '진폭(amplitude)'이 기하급수적으로 작아져서 의미없는 알고리즘이 된다. 양자 알고리즘과 확률적 알고리즘의 가장 근본적인 차이점은, 가역성과 확률의 보존성이다. 양자역학의 확률 진폭은 음수일 수 있을 뿐만 아니라, 심지어 실수뿐만이 아닌 허수까지 포함해서 복소수일 수도 있다. 이들은 중첩의 원리에 따라 서로 상쇄될 수 있다. 그리고, 진폭의 절댓값의 제곱이 확률이 되고, 확률의 총합은 1로 보존되므로, 어떤 상태의 진폭이 상쇄되어 0이 된다면, 무엇인가 다른 상태의 진폭은 총합이 보존되기 때문에 커져야 한다. 대략 말하자면, 양자 컴퓨터는 오답을 상쇄시키고 정답을 증폭시킬 수 있다. 반면 고전 컴퓨터는 비가역적이라서 확률적 알고리즘에 따라 확률 진폭을 상쇄시키면 그대로 정보가 사라져 원래 정보를 복원시킬 수 없다. 따라서 고전 컴퓨터를 사용한 연산에선 확률이 보존되지 않아 정답의 확률만을 증폭시킬 수 없다. 양자역학을 설명할 때 아주 초반에 나오는 이중 슬릿 실험의 예를 생각해보자. 고전적인 상식에 의하면, 빛이 1번 슬릿 또는 2번 슬릿을 통과한 뒤에 스크린의 어딘가에 떨어질 확률 분포는, 빛이 1번 슬릿을 통과한 뒤에 스크린의 어딘가에 떨어질 확률 분포와 2번 슬릿을 통과한 뒤에 스크린의 어딘가에 떨어질 확률 분포를 더해놓은 형태가 되어야 할 것이다. 하지만 실제로 이 실험을 수행해 보면, 어떤 위치에서는 두 개 슬릿을 다 열어둘 때에 오히려 광자가 올 확률이 떨어지는 현상이 발생한다. 모두 0 이상인 확률로 계산을 하면 정보의 손실이 생겨서 이런 결과가 나올 수가 없지만, 복소수 값을 갖고 음수 값을 가질 수 있는 진폭으로 계산을 하면 이런 결과는 자연스럽게 발생할 수 있다. 비록 확률진폭의 절댓값의 제곱만이 물리적 의미를 가지며 복소수의 확률파동 자체는 물리적 의미가 없지만, 이들의 비물리적 성질이 계산에 활용될 때에는 오히려 커다란 이점이 된다. 물론, 양자컴퓨터는 컴퓨터니까 고전 컴퓨터가 할 수 있는 일들을 대부분 할 수 있고, 경우에 따라서는 같은 문제를 고전적인 컴퓨터에서 알려진 최선의 알고리즘보다 훨씬 더 빨리 풀기도 한다. 하지만 이는 소위 '처치-튜링 명제'를 뛰어넘는 능력을 양자컴퓨터가 가지고 있다는 의미는 아니다. 즉, 양자컴퓨터가 할 수 있는 계산은 고전컴퓨터도 시뮬레이션을 통해 따라하는 것이 가능하다. 다만 시뮬레이션의 속도가 느릴 뿐이다. 오히려 자명하지 않은 부분은 반대 방향이다. 고전컴퓨터가 할 수 있는 일은 과연 양자컴퓨터가 다 할 수 있는가? 양자컴퓨터는 비싸니까 당연히 더 좋겠지라고 생각하면 속은 편하겠지만, 여기에는 한 가지 문제가 있다. 양자역학에 의하면, 양자역학적인 시스템은 '유니터리'한 방식으로밖에는 변화할 수 없다. 유니터리 행렬은 항상 역행렬을 갖고, 따라서 역변환이 가능하므로, 계산의 결과로부터 계산의 입력값을 되찾는 것이 가능해야 한다. 그런데 함수 f(x)가 일대일이 아니라면, x라는 입력으로부터의 계산 결과가 y가 나왔을 때에, 해당 y에 대응하는 원래의 오리지널 x가 꼭 하나만 있을 필요가 없다. 예를 들어, 거듭제곱 함수 f(x)=x^^2^^를 생각하면, f(x)=f(-x)=x^^2^^가 되므로 x로부터 y가 나왔다고 해도 원래의 입력이 x였는지 -x였는지 알 방법이 없다. 즉, x로부터 y를 구하는 과정은 비가역적일 수 있다. 세상에는 고전 컴퓨터가 멀쩡하게 계산을 잘 하는 비가역적인 간단한 함수들이 널려있고, 이런 함수들은 아무리 간단해도 양자컴퓨터가 계산하지 못한다. 다만, 당연히도 이런 문제를 피해가는 방법이 있다. x로부터 f(x)를 구하는 대신에, x로부터 (x, f(x))를 구하면 된다. 즉, 양자컴퓨터가 일대일이 아닌 함수를 계산할 때에는, 출력과 함께 원래의 입력을 같이 출력하면 된다. 정보의 손실이 없으므로 이 입력과 출력의 관계는 일대일이 되므로, 이 비가역성의 문제를 비켜갈 수 있다. 하지만 그렇다고 해서 그런 방식으로 양자컴퓨터가 고전컴퓨터가 할 수 있는 일을 모두 다 시뮬레이션할 수 있는지는 결코 자명한 문제가 아니지만, 결론만 말하자면 가능하다. 모든 고전적인 계산은 가역적인 방식으로, [[엔트로피]]의 손실 없이(열을 내지 않고) 처리하는 것이 가능하다는 사실이 알려져 있고, 그러한 가역적인 계산은 양자컴퓨터도 수행하는 것이 가능하다. 따라서 양자컴퓨터는 고전컴퓨터가 할 수 있는 일을 최소한 고전컴퓨터만큼의 속도로는 처리할 수 있다. 최소한 이론적으로는. 그 다음의 문제는, 양자컴퓨터가 같은 문제를 고전컴퓨터보다 더 빨리 계산할 수 있느냐이다. 이는 문제에 따라 다르다. 풀어야 할 문제 자체에 그러한 규칙성이 별로 없는, 예를 들어 앞에서 언급한 2^^n^^개의 상자를 여는 문제 같은 경우에는 (상자 한 개를 연 결과가 다른 상자를 연 결과에 대해서 무엇을 말해주겠는가. 별로 말해줄 것이 없다.) 정답의 확률 진폭을 끌어올리고, 오답의 확률 진폭을 죽여버리는 작업이 필요한데, 이는 당연히 공짜가 아니다. 요약하자면, [[그로버 알고리즘]]에 의하면, 대략 2^^n/2^^번 정도 상자를 '양자적으로' 열어 보면 공이 어느 상자에 있는지를 유의미한 확률로 맞힐 수 있다. 이는 고전적인 결과에 비하면 엄청난 개선이지만, 여전히 지수적인 속도 향상이 아니라 다항식적인 속도 향상에 불과하다. 그리고 상자를 열어서 공을 찾는 문제의 경우에는 사실상 이 알려진 알고리즘이 최선이라는 사실이 증명되어 있고, 이것이 아마도 양자컴퓨터가 임의의 [[P-NP 문제|NP 문제]]를 다항식 시간 내에 풀지는 못할 것으로 보인다는 추측의 근거가 된다. 하지만 어떤 문제들은 양자컴퓨터가 기존에 알려진 고전 알고리즘보다 지수적으로 빠른 계산을 해낼 수 있다는 사실이 알려져 있다. 소인수분해, 이산 로그 등이 그러하다. 이러한 속도의 향상은 양자 중첩, 병렬성에서만 나오는 것이 아니다. 확률 진폭이 서로 상쇄가 가능하다는 것이 주된 원인이다. 소인수분해나 이산 로그를 효율적으로 풀 수 있으면, 현대 암호학의 공개키 알고리즘의 적지 않은 부분들을 깰 수 있기 때문에 이는 현재까지 알려진 양자컴퓨터의 가장 유력한 '킬러 어플리케이션'이다. [[쇼어 알고리즘]]은 소인수분해를 [math(O(\log^3 n))]번만에 풀 수 있는 '''양자 알고리즘'''이다. 고전적으로 알려진 (여태까지의) 최선의 알고리즘 [math(O(\exp(\sqrt[3]{\frac{64}{9}}(\log^{\frac{1}{3}} n )(\log(\log n))^{\frac{2}{3}})))]보다 지수적인 속도 향상이 있었다. 여담으로 [[쇼어 알고리즘]] 중 실제로 양자컴퓨터가 쓰이는 부분은 합동식 형식의 RSA 암호화로 a,N이 주어졌을 때 [math(a^b\equiv 1\left(\text{mod}\,N\right))]을 만족하는 주기성을 갖는 b를 찾는 부분으로 특수한 꼴의 이산로그를 푸는 셈이다. 나머지 과정은 확률상쇄를 필요하지 않는 분석이어서 일반적인 컴퓨터로도 충분히 시뮬레이션이 가능하다. 양자컴퓨터가 고전 컴퓨터에 비해 확실하게 독보적으로 우월한 것은 양자역학적인 시스템을 시뮬레이션하는 것이다. 이거야 말로 에뮬레이션과 네이티브 실행을 비교하는 격이다. 양자컴퓨터가 다항식 시간에 풀 수 있는 문제의 집합을 [[https://ko.wikipedia.org/wiki/BQP|BQP]]라고 하는데, 이와 NP와의 관계는 아직 정확히 밝혀지지 않았다. 양자 검색 문제를 양자컴퓨터가 다항식 시간에 풀지 못한다는 사실이 증명되어 있기 때문에, 아마도 NP가 BQP에 포함되지는 않을 것이라고 본다.[* 사실 NP가 P에 포함되는지 조차도 아직 증명하지는 못했다. [[P-NP 문제]] 참조] 그렇다면 반대방향은 어떠한가? 즉, BQP는 NP에 포함되는가? 다른 말로, 양자컴퓨터가 할 수 있는 일은 비결정적 컴퓨터가 모두 할 수 있는가? 역시 아직까지 확실하게 알려진 것은 없으나 아마도 BQP는 NP에 속하지 않는 문제를 담고있을 것이라고 본다. 뿐만 아니라, BQP는 PH, 즉 polynomial hierarchy도 벗어날 것으로 추측한다. [[http://www.scottaaronson.com/papers/bqpph.pdf|이에 대해서는 다음을 참고.]] 정리하면, BQP와 NP, 다른 말로, 양자컴퓨터와 비결정적 컴퓨터는 (아직 정확히는 모르지만) 서로 상대방보다 더 효율적인 부분이 있을 것이라는 말.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기