why-quantum-computing.ipynb

Kernel: Python 3

왜 양자 컴퓨팅인가?

컴퓨터란 무엇인가?

이 페이지에 접속하신 분들은 컴퓨터가 어떤 것인지 알고 계실 것입니다.오늘날 컴퓨터는 노트북이나 휴대전화부터 교통 신호기를 제어하는 시스템까지 다양한 형태로 이용되고 있습니다. 컴퓨터는 모든 것을 할 수있는 것 처럼 보입니다. 위에 나열된 시스템은 매우 복잡하고 특수한 것이지만, 공통적인 것은, 컴퓨터가 어떤 입력 정보에 대해서 일련의 명령을 실행해, 어떠한 새로운 (출력) 정보를 주는 것입니다.

컴퓨터에 주는 명령은 매우 구체적이고 모호함이 없어야 합니다.이러한 명령의 집합을 알고리즘 이라고 부르며 컴퓨터 연구의 대부분은 서로 다른 알고리즘의 작동방식 연구에 해당합니다.이번 과정에서는 키보드나 마우스, 화면은 사용하지 않고 정보와 알고리즘만으로 이루어진 가장 단순한 컴퓨터에 대해 생각해 봅니다.

컴퓨터 알고리즘 분류

최신의 고전적인 컴퓨터들 사이에서 양자컴퓨터가 수행하는 역할을 이해하기 위해서는 먼저 다양한 알고리즘의 성능을 어떻게 측정하는지 알아야 합니다.

컴퓨터 사이언스에서는, 입력의 크기에 따라서 사용하는 리소스가 어떻게 커지는지에 따라 알고리즘을 분류합니다.이것을 알고리즘의 복잡도라고 부릅니다.예를 들어 어떤 숫자가 짝수인지 아닌지를 판단하는 알고리즘은 그 숫자의 마지막 한 자리만 봐도 됩니다.이 경우 입력은 숫자이고 출력은 짝수 또는 홀수 중 하나입니다.알고리즘이 완료될 때까지의 시간은 입력된 수의 크기에 의존하지 않기 때문에 이를 정수 시간 알고리즘이라고 부릅니다.컴퓨터에 따라 이 결과를 얻는데 걸리는 시간은 다를 수 있지만 그것은 다른 요인에 의한 것이지 입력 길이에 의한 것이 아닙니다.

또 다른 예시를 살펴보겠습니다.이번에는 입력은 같은 길이의 두 개 수이고 문제는 그것들을 더하는 것입니다.이 경우 출력은 새로운 숫자가 됩니다.두 개의 여러 자리 숫자를 더할 경우 학교에서 배웠을 일반적인 알고리즘에서는 각각의 숫자의 오른쪽 끝 자리부터 시작하여 그것들을 더합니다.그리고 한 자리 왼쪽으로 이동하여(결과가 9보다 클 경우에는 '1'을 자리 올림함) 이 처리를 반복합니다.컴퓨터는 더해야 할 자리가 없어질 때까지 이를 반복하고 알고리즘을 종료합니다.

덧셈은 얼마나 복잡한 것일까?

이 덧셈 알고리즘이 완료되기까지 걸리는 시간은...

1. ...입력된 숫자의 길이에 선형으로 (비례하여) 증가한다(선형 시간).

1. 입력된 숫자의 길이에 영향을 받지 않는다(정수 시간)

1. ...입력된 숫자의 길이의 제곱으로 커진다 (2차 시간)

다시 말하자면, 컴퓨터 마다 이 알고리즘의 실행 속도는 다릅니다.노트북에서는 인간의 수백만 배 빠른 속도로 덧셈을 실행할 수 있습니다.하지만 1초에 100만 번의 연산을 할 수 있든 1회밖에 할 수 없든 증가율은 같습니다.

여기서 마지막으로 우리에게 매우 흥미로운 예시를 하나 소개해 드리겠습니다.비밀 번호(비밀번호등)를 가지고 있어서, 그것을 맞히는 문제가 있다고 가정해 봅시다.이 경우 문제의 크기는 번호의 길이입니다.

답이 맞는지 확인하는 유일한 방법은 바로 키패드에 숫자를 넣어서 확인하는 것입니다.그 숫자가 무엇인지에 대한 정보는 없기 때문에 이 비밀 번호를 찾기 위한 최적의 알고리즘은 '무차별 대입(brute-force)' 방식을 사용하는 것입니다. 즉, 전략이나 아이디어를 사용하는 것이 아닌 단순히 가능한 모든 숫자들을 시험해 보는 것입니다.

시간이 얼마나 걸릴까요? 자, 이론적으로는 운이 좋으면 한 번에 답을 맞힐 수 있는데 이것은 매우 낮은 확률입니다.평균적으로 가능한 입력의 약 절반을 시도해야 하기 때문에 알고리즘의 실행 시간은 가능한 조합의 수에 비례합니다. 이제 질문하겠습니다: 가능한 조합의 수는 비밀 번호의 길이에 따라 어떻게 증가하는 것일까요?

비밀 번호에 숫자를 추가할 때마다 가능한 조합의 수가 10배 됩니다.예를 들어 비밀 번호 한자리는 10가지의 가능한 숫자가 존재하고(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), 두 자리 번호는 100가지의 가능성이 있습니다.각 자리를 맞추는데 걸리는 시간이 (길이에 관계없이) 같다고 가정하면 다음과 같이 수학적으로 나타낼 수 있습니다.

ParseError: KaTeX parse error: Undefined control sequence: \cssId at position 1: \̲c̲s̲s̲I̲d̲{T}{T} \cssId{p…

이 식에서 자릿수(d)가 지수라는 것을 눈치채셨나요. 이처럼 이것은 지수 시간 알고리즘이고 실행 시간은 입력 길이에 대해 지수 함수적으로 증가한다고 합니다.

왜 이런 방식으로 알고리즘을 측정할까요?

컴퓨터에 따라 장점이 다르기 때문에 어떤 컴퓨터에서는 다른 컴퓨터보다 특정 연산이 빨라질 수 있습니다. 입력 크기에 대한 시간 증가를 연구함으로써 알고리즘과 컴퓨터의 특정 조합이 아닌 디바이스 고유의 세부 사항을 무시하고 실제로 알고리즘을 측정할 수 있습니다. 중요한 것은 알고리즘이 입력 크기에 대해 어떻게 변화하는지 알 수 있어야 알고리즘이 실행가능한 크기가 되는지도 알 수 있다는 점입니다.

위에서 본 선형 시간 덧셈 알고리즘에 대해 생각해 봅시다. 10자리 숫자를 1초에 2개를 더할 수 있었다면 성장률의 선형성으로 인해 20자리 숫자를 2초에 더할 수 있을 것입니다.10자리 늘어날 때마다 계산 시간은 대략 1초씩 늘어날 것입니다.

한편, 위에서 언급된 지수 시간 탐색 알고리즘을 사용하여, 10 자리수의 비밀번호를 1 초만에 찾아낼 수 있었다고 가정해 봅시다.이것은 당신의 컴퓨터가 1초에 ~5,000,000의 조합을 시험할 수 있을 정도로 빠른 계산 속도를 지녔음을 의미합니다. 이 알고리즘을 사용한 컴퓨터가 20자리 비밀번호를 찾아내려면 대략 5,000,000초(150년)가 걸릴 것으로 예상 할 수 있습니다. 10자리 더 늘어나면 약 150,000,000년(우주의 나이의 120배)이나 됩니다. 지수함수 시간의 알고리즘은 얼마 안 되는 입력 자리수(이 경우는~30자리)로도 실행하기가 어렵기는커녕 말 그대로 계산이 불가능해져 버리고 맙니다.

이 비밀번호 탐색 문제는 가능한 한 단순하게 만든 인공적인 예이지만, 컴퓨터 사이언스에는 비효율적인 알고리즘밖에 없는 현실의 문제들이 많이 존재합니다. 오늘날의 컴퓨터는 놀라울 정도로 빠르지만, 이러한 어려운 문제들은 가장 큰 슈퍼 컴퓨터에서도 너무 어려울 수 있습니다.

그러나 보다 효율적으로 시간이 증가하는 알고리즘을 발견하게 되면 비교적 느린 컴퓨터나 신뢰성이 낮은 컴퓨터에서도 이러한 어려운 문제들을 갑자기 처리할 수 있게 될지도 모릅니다.그래서 등장하는 것이 양자컴퓨터입니다.

양자컴퓨터는 어떻게 도움이 될까요?

그동안 알고리즘이라는 것을 굉장히 추상적으로 생각해 왔지만 그 알고리즘을 실행하는 컴퓨터는 현실 세계에 존재해야 합니다. 그 컴퓨터가 고성능 마이크로칩이든 종이와 펜을 가진 인간이든 모든 컴퓨터는 최종적으로 물리법칙에 지배되고 있으며 그 연산에 의해 우리가 만들 수 있는 알고리즘이 제한됩니다.

물리학은 우주에 존재하는 모든 것이 따르는 일련의 규칙을 규명하려는 학문입니다. 20세기 초, 실험실에서 진행된 정교한 실험을 통해 물리학자들은 현재의 물리학으로는 설명할 수 없는 기묘한 행동을 발견했습니다. 이는 물리법칙이 정확하지 않다는 것을 의미하며, 그래서 그들은 보다 완전한 '양자' 물리학을 개발했고, 이 거동을 아주 잘 설명하는 데 성공했습니다.

물리학자는, 지금까지 본 적도 없는 행동을 설명하기 위해서 양자 물리학을 만들어 냈고, 컴퓨터 과학자는, 새롭게 발견된 이 원리를 이용함으로써, 보다 효율적인 알고리즘을 작성할 수(이론적으로는) 있는 것을 발견했습니다. 그 결과, 기존의 컴퓨터에서는 해결 불가능한 문제라도, 이 원리를 이용할 수 있는 ‘양자’ 컴퓨터라면 해결할 수 있다고 생각되는 몇가지 문제들이 있습니다. 그 중 하나가 정수의 인수분해입니다.

'$x$'라고 부르는 정수가 있다고 합시다. 인수분해 알고리즘에서는 $p×q = x$를 만족하는 정수 $p$ 와 $q$를 구합니다. 가끔 한눈에 알아볼 수 있는 쉬운 경우도 있습니다; $2000 = 2 × 1000$의 경우 한눈에 알 수 있습니다. 하지만, $x$가 두 개의 큰 소수의 곱의 경우는 이 문제는 매우 어려워집니다. 정수의 인수분해에 대해 말할 때에는 가장 어려운 (최악의) 시나리오를 가정하게 됩니다. 아래 코드셀에서는 변수 x에 250자리 숫자를 대입하고 있습니다.

# pylint: disable=line-too-long, invalid-name
x = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

2020년에, 연구자들은 고전적인 슈퍼 컴퓨터와 ~2700 코어-년(core-year)의 처리 능력을 이용해 이 수를 인수 분해했습니다. 이는 대규모 작업으로 논문이 발표되던 시점에서는 새로운 기록이었습니다. 그들의 결과는 아래 코드 셀에서 확인할 수 있습니다(다행이도 곱셈이라는 효율적인 알고리즘으로 확인할 수 있습니다!).

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

p*q == x  # Evaluates to 'True'

True

표시되는 출력은 셀의 마지막 행 값입니다.이 경우 p*q == x는 True로 평가됨을 알 수 있습니다. 수학적으로 증명된 것은 아니지만 기존 컴퓨터에서 이러한 수의 인수 분해를 수행하는 효율적인 알고리즘이 존재하지 않는 것은 의심의 여지가 없습니다. 실제로 인터넷 암호화 대부분은 이 문제가 해결 불가능하다는 가정에 의존하고 있으며, 617자리 RSA 수의 인수 분해는 불가능한 것으로 알려져 있습니다. 한편 양자컴퓨터의 경우 충분한 크기의 양자컴퓨터가 생기면 하루 안에 이들 숫자를 인수분해할 수 있을 것으로 추정되는 효율적인 인수분해 알고리즘이 이미 개발되어 있습니다.

지금 우리는 어느 단계에 있을까?

양자컴퓨터는 보다 효율적인 알고리즘을 실행할 수 있는 것으로 알려져 있지만 현재 있는 양자컴퓨터는 작고 불안정하기 때문에 기존 컴퓨터와 비교했을 때 더 나은 점을 찾기 어렵습니다.

양자컴퓨터가 해결할 수 있는 문제의 크기를 제한하는 요인은 극히 단순하게 생각해도 두 가지가 있습니다. 첫 번째는 양자컴퓨터가 저장·처리할 수 있는 데이터의 양입니다. 이것은 통상 큐비트로 측정됩니다. 만약 충분한 큐비트가 없다면 어느 크기 이상의 문제를 저장하고 처리할 수 없습니다. 두번째는양자컴퓨터의 오차율입니다. 양자적인 행동은 실험실에서의 정교한 실험에서만 볼 수 있기 때문에 양자컴퓨터를 만드는 것은 상당히 정밀한 작업입니다. 현재의 양자컴퓨터는 잡음이 많기 때문에 잘 틀리고 결과에 ‘노이즈’가 삽입됩니다. 과도한 양의 노이즈로 인해 계산 결과가 의미를 잃게 됩니다!

현재 양자컴퓨터는 실험적인 것입니다. 큐비트의 수나 오류율에 제한이 있기 때문에 현재 해결할 수 있는 가장 큰 문제는 기존 컴퓨터로도 쉽게 해결할 수 있는 것입니다.

미래의 어느 시점에서 이것은 바뀌게 될 것입니다. 양자컴퓨터를 사용하는 것이 기존 컴퓨터보다 경제적으로 유리하게 문제를 해결할 수 있다는 ‘양자 이점’에 도달하게 될 것입니다. 어떻게 그것을 알 수 있냐구요? 왜냐하면 우리는 알고리즘을 그 증가율로 측정하고 있기 때문입니다! 양자컴퓨터가 순조롭게 계속 발전하는 한 언젠가는 고전적인 컴퓨터를 앞지르게 될 것입니다.

617자리인 RSA수를 1일 이내에 인수분해하려면 ~2,000만의 노이즈가 있는 큐비트가 필요하다고 합니다. 이 강의가 작성된 시점에서 IBM은 현재 65양자비트의 양자컴퓨터를 보유하고 있으며 2023년까지 1000양자비트가 넘는 시스템 구축을 목표로 하고 있습니다.이 마일스톤 훨씬 전에 양자 이점을 가져올 것으로 기대되는 또 다른 알고리즘들이 더 있지만, 아직 먼 훗날 이야기로 여겨질 수도 있습니다.

아래 코드를 사용하여 간단한 양자 프로그램을 만들고 IBM Quantum을 통해 실제 양자 컴퓨터에서 실행할 수 있습니다. IBM Quantum은 이 프로그램을 4000번 실행할 것입니다. 작성된 프로그램은 확률적이며 결과는 절반 은 000 이고 나머지는 111 이어야 합니다. 쉽게 볼 수 있듯이 이것이 유일한 결과는 아니며 노이즈로 인해 다른 출력을 측정할 적은 확률을 지닙니다.

# 1. Create a simple quantum program called a 'quantum circuit'.
from qiskit import QuantumCircuit
qc = QuantumCircuit(3)
qc.h(0)
qc.cx(0, [1, 2])
qc.measure_all()

# 2. Ask IBM Quantum for its least busy device that isn't a simulator.
#    If you're running this example locally, you need to load your
#    account with your IBM Quantum API token
# IBMQ.save_account(token="XYZ")
# IBMQ.load_account()
from qiskit.providers.ibmq import IBMQ, least_busy
provider = IBMQ.get_provider('ibm-q')
device = least_busy(
            provider.backends(
                filters= lambda x: not x.configuration().simulator
            )
        )
print(f'Running on {device.name()}')

# 3. Convert the program to a form the device can run.
#    This is known as 'transpiling'
from qiskit import transpile
transpiled_qc = transpile(qc, device)

# 4. Send the program off to IBM Quantum to run on a real device
#    and monitor its status.
from qiskit.tools import job_monitor
job = device.run(transpiled_qc)
job_monitor(job)

# 5. Plot the results as a histogram.
from qiskit.visualization import plot_histogram
plot_histogram(job.result().get_counts())

Running on ibm_geneva
Job Status: job has successfully run

기존의 컴퓨터가 어디서 왔는지 생각해 볼 필요가 있습니다.아래 사진은 1947년에 만들어진 최초의 트랜지스터의 사진입니다.트랜지스터는 현대 컴퓨터 프로세서의 구성요소입니다.

이미지 출처: 연방 직원 Link , Public Domain .

그로부터 70년이 지난 지금, 현대의 컴퓨터 칩에는, 수십억개의 트랜지스터가 탑재되어 있습니다.

이 과정의 나머지 부분에서는 보다 효율적인 알고리즘을 만들 수 있도록 하는 양자적인 효과를 찾아볼 예정입니다. 이 과정의 끝에는 소프트웨어 패키지인 Qiskit을 사용하여 이들 알고리즘 중 하나를 실행하는 양자컴퓨터를 프로그래밍 할 수 있게 될 것입니다.

짧은 퀴즈

양자 컴퓨터는 머지않아...

1. ...기존의 컴퓨터에게 너무 어려운 계산을 할 수 있게 된다

1. ...기존의 컴퓨터를 대체할 것이다.

1. ...기존의 컴퓨터의 계산 속도를 향상시키게 될 것이다.