고전 컴퓨터와의 비교, 양자 이점 편집하기 (부분)

경고: 로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다. 로그인하거나 계정을 생성하면 편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.

= 개요 =
[[양자 우위|양자 우위(quantum supremacy)]]란 양자 컴퓨터의 연산 능력이 월등히 뛰어나 그 어떤 고전 컴퓨터로도 동등한 수준의 연산을 수행할 수 없는 경우를 의미한다. 양자 컴퓨터가 고전 컴퓨터보다 연산 능력이 얼마나 좋은지 알기 위해서는 각각의 연산 능력을 정량화하여 서로 비교를 해야 정확히 알 수 있다. 하지만, 불행하게도 대부분 문제들의 경우 고전컴퓨터가 얼마나 잘 풀 수 있는지에 관한 이론과 그 증명이 아직 잘 알려져 있지 않다. 또한, 현존하는 양자 컴퓨터는 아직 양자역학적인 오류들로부터 자유롭지 않은 원형(prototype)이기 때문에, 우위(supremacy)라는 표현이 적절하지 않다는 의견들이 나오면서 양자 이점(quantum advantage)라는 용어도 많이 사용하고 있다.

[[양자 컴퓨터]]를 이용한 연산이 양자 우위라고 주장하기 위해서는 주로 몇 가지 조건들이 필요하다는 것이 알려져 있다.<ref name="Harrow2017">Harrow, A. W. & Montanaro, A. Quantum computational supremacy. Nature '''549''', 203-209, (2017). doi: https://doi.org/10.1038/nature23458.</ref> 우선, 계산을 하기 위한 문제가 잘 정의되어 있어야한다. 두번째, 문제를 해결하기 위한 양자 알고리즘이 있어야 한다. 세번째, 동일한 문제를 고전컴퓨터로도 해결할 수 있어야 한다. 네번째, 복잡 이론의 가정(complexity-theoretical assumption)이 있어야한다. 마지막으로, 양자 알고리듬의 계산 성능과 고전 알고리듬의 계산 성능을 명확하게 구분할 수 있어야 한다.

자연수의 소인수분해 문제의 경우 위의 조건을 잘 만족한다. 이진법으로 기술된 자연수를 ''N''이라고 했을 때, 고전 알고리듬을 이용하여 소인수분해를 할 경우 그 연산량이 $$2^{O\left( N^{1/3} \right)}$$ 로 알려져 있다. 반면, 양자 알고리듬인 [[쇼어 알고리듬]]을 이용하면 $$O\left( \log N^{3} \right)$$의 다항 시간이 걸린다 . 따라서 적당한 크기의 자연수에 대해서는 고전컴퓨터와 양자 컴퓨터의 연산 능력을 명확하게 비교할 수 있고, 충분히 큰 자연수에 대해서는 쇼어 알고리듬이 더 빠르다는 것을 알 수 있다. 하지만 구글 팀에서 발표한 논문에 의하면, 쇼어 알고리듬이 2048비트의 정수를 인수분해하기 위해서는 이상적인 양자컴퓨터의 [[큐비트]]가 대략 20,000,000개 정도 필요하다고 예측하였다.<ref name="Gidney2021">Gidney, C. & Ekerå, M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum '''5''', 433, (2021). doi: https://doi.org/doi:10.22331/q-2021-04-15-433.</ref> 2021년 현재, 프로그래밍이 가능한 양자 컴퓨터는 여전히 오류를 가지고 있으며, 가장 많은 큐비트 개수는 IBM의 Hummingbird 칩으로 65개에 불과하다.

수십 개의 큐비트 개수와 여러 오류들을 가지고 있는 양자 컴퓨터이지만 이를 이용하여 양자 우월성을 보이는 연구가 최근 활발히 진행되고 있다. 특히, 현존하는 NISQ 컴퓨터로 샘플링 문제(무작위 양자 회로 샘플링 및 보손 샘플링 문제들)를 다루어 양자 우월성을 입증한 연구결과들이 있다. 이에 대해 간단하게 소개하고자 한다.

요약:

한국양자정보학회 위키에서의 모든 기여는 다른 기여자가 편집, 수정, 삭제할 수 있다는 점을 유의해 주세요. 만약 여기에 동의하지 않는다면, 문서를 저장하지 말아 주세요.
또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다(자세한 사항은 한국양자정보학회 위키:저작권 문서를 보세요). 저작권이 있는 내용을 허가 없이 저장하지 마세요!

취소 편집 도움말 (새 창에서 열림)

원본 주소 "https://wiki.qisk.or.kr/고전_컴퓨터와의_비교,_양자_이점"

고전 컴퓨터와의 비교, 양자 이점 편집하기 (부분)

둘러보기 메뉴

검색