안녕하세요 인턴 김준수입니다. 2022년 9월 22일 세미나 내용을 간략히 요약해드리겠습니다.
일반적인 컴퓨터는 exponential complexitiy를 가지는 문제들을 푸는데 한계가 존재하고, 이를 양자컴퓨팅을 통해 극복할 수 있습니다. 양자컴퓨팅은 기존의 정보단위인 bit대신 quantum bit (qubit)를 사용하고, 양자역학의 2가지 특성인 superposition과 entanglement를 이용합니다. superposition은 qubit 하나가 0또는 1의 상태를 동시에 가질 수 있음을 의미하고, entanglement는 서로 다른 큐빗들이 서로의 state에 간섭할 수 있음을 뜻합니다.
위 두가지 특성을 통해 여러가지 문제를 efficient하게 풀 수 있는데, 예를 들면 주어진 함수가 constant output을 내는 함수인 지, 아니면 50% 확률로 0또는 1의 output을 가지는 balanced 함수인 지 알아내는 Deutsch-Jozsa 알고리즘이 있습니다. classical computer의 경우 worst case 일 때, 주어진 인풋의 50% + 1번을 더 연산해야 주어진 함수가 balanced 인지 constant인지 알 수 있지만, 양자컴퓨팅으론 단 한번의 연산 만으로 구분할 수 있게됩니다.
이에 대한 증명은 아래 링크로 첨부하겠습니다.
https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html
Deutsch-Jozsa Algorithm
A university quantum algorithms/computation course supplement based on Qiskit
qiskit.org
비록 양자컴퓨팅을 통해 몇몇 문제들을 polynomial time 안에 풀 수 있다는 것은 증명되었지만, 실제 알고리즘을 돌리기 위해선 지금 보다 훨씬 더 많은 qubit의 개수와 noise-tolerant한 gate, qubit, system이 개발 되어야 합니다. 특히, quantum algorithm을 noise-robust한 qubit에 mapping하고, swap gate insertion을 줄일 수 있는 intelligent scheduling, compilation 방식들이 architecture에서 활발히 연구되고 있습니다.
당장은 약 100여개의 qubit을 사용할 수 있지만, 구글이나 IBM 같은 빅테크 기업들의 전폭적인 투자와 지원이 있기 때문에 10-20년 뒤에는 특정 어플리케이션들에 대해 양자컴퓨팅을 적극적으로 활용할 수 있을거라 기대됩니다.
감사합니다.
