양자 알고리듬 (Quantum Algorithm) 편집하기 (부분)

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

== 양자 알고리듬 (Quantum Algorithm)==

양자 알고리듬은 [[쇼어 알고리듬|쇼어 알고리듬(Shor’s algorithm)]]이 나타나면서 각광받기 시작했다. [[쇼어 알고리듬]]은 [[양자 푸리에 변환|양자 푸리에 변환(quantum fourier transform)]]을 기반으로, 소인수분해나 이산대수문제를 기존 컴퓨터보다 기하급수적으로 빠른 속도로 연산이 가능하다. 그리고 현재 사용되는 [[양자 암호 통신|암호화 알고리듬]]은 RSA 알고리듬(Rivest-Shamir-Adleman algorithm)으로, 큰 정수의 소인수분해가 기존 컴퓨터로는 어렵다는 점에 착안해서 만들어진 방식이다. 이로 인해 양자 컴퓨터에 대비해서 암호화 분야에는 비상이 걸리고, 양자 컴퓨터는 각광을 받기 시작한다. 양자 컴퓨터의 성능이 좋아지면 기존 암호화 방식인 RSA 알고리듬이 무력화될 가능성이 있지만, 아직은 양자 컴퓨터는 많은 수의 큐비트 구현이 불가능해서 기존 암호화 방식을 위협하기엔 시간이 걸린다.

많이 알려진 양자 알고리듬 중에서 번스타인-바지라니 알고리듬(Bernstein-Vazirani algorithm)도 있다. 이는 임의의 수를 정하고, 이 수를 맞추는 알고리듬으로 기존 방식으로 연산하는 것보다 연산 단계가 적다. 예를 들어 4 비트의 길이를 갖는 숨겨진 임의의 수를 1001이라고 하자. 기존 알고리듬은 먼저 임의의 수와 0001을 비교한다. AND(1, 1)은 1이므로 첫번째 수가 1이라는 것을 알 수 있다. 다음으로 0010와 비교하며 각 비트를 비교한 후에 임의의 수를 알아낼 수 있다. 총 비교 수는 비트 수만큼 반복한다. 하지만 번스타인-바지라니 알고리듬은 [[큐비트]]의 수에 상관없이 단 한번의 연산으로 임의의 수를 알아낼 수 있다. 실용성 외에도, 이러한 알고리듬은 양자 우월성을 입증하고 양자 컴퓨터의 기하 급수적인 속도 향상을 증명하기도 한다.

현재는 양자 컴퓨터의 성능을 비교, 판단할 때 [[쇼어 알고리듬|쇼어 알고리듬(Shor’s algorithm)]], 번스타인-바지라니 알고리듬(Bernstein-Vazirani algorithm), [[그로버 알고리듬|그로버 알고리듬(Grover’s algorithm)]] 등을 사용한다. IonQ에서 발표한 11 큐비트 양자 컴퓨터에서 10 큐비트에 대한 번스타인-바지라니 알고리듬을 구현해본 결과, 그 정확도가 평균 78%로 측정되었다는 발표가 있었고 (2019) <ref name=Wright>K. Wright ''et al''., Benchmarking an 11-qubit quantum computer, Nature Communications '''10''', 5464 (2019). doi:[https://doi.org/10.1038/s41467-019-13534-2 10.1038/s41467-019-13534-2].</ref>, 최근에는 80% 이상으로 개선되기도 하였다 (2021).<ref name=Blinov>S. Blinov, B. Wu, and C. Monroe, Comparison of cloud-based ion trap and superconducting quantum computer architectures, arXiv:[https://arxiv.org/abs/2102.00371 2102.00371].</ref> IBM의 5 큐비트 양자 컴퓨터 ibmqx4에서 그로버 알고리듬을 구현해본 결과 정확도가 평균 65%로 측정되었으며, IBM의 ibmqx4와 16 큐비트 양자 컴퓨터 ibmqx5에서 2비트의 숨겨진 수에 대한 번스타인-바지라니 알고리듬을 실행했을 때는, 임의의 수가 “01”, “10”, “11”일 경우 정확도가 각각 38.6%, 44.9%, 43.7%였다 (2018).<ref name=Abhijith>J. Abhijith ''et al''., Quantum algorithm implementations for beginners, arXiv:[https://arxiv.org/abs/1804.03719 1804.03719].</ref> 5 큐비트 IBM 양자 컴퓨터 Vigo에서 4 비트 번스타인-바지라니 알고리듬의 정확도는 [[양자게이트|CNOT 게이트]]의 개수(즉, 숨겨진 임의의 수에서의 1의 개수)에 따라 90% 이상에서 60%대를 보였으며, 15 큐비트 IBM 양자 컴퓨터 Melbourne에서 10 비트의 숨겨진 수에 대한 번스타인-바지라니 알고리듬 테스트에서는 CNOT 게이트 개수가 0일때는 60% 이상이었으나 개수가 늘어날수록 점차 정확도가 낮아져 3개부터는 10% 이하인 것으로 나타났다 (2021).<ref name="Blinov"/>

요약:

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

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

원본 주소 "https://wiki.qisk.or.kr/양자_알고리듬_(Quantum_Algorithm)"

양자 알고리듬 (Quantum Algorithm) 편집하기 (부분)

둘러보기 메뉴

검색