양자 컴퓨팅 공부 노트 – 1. 새로운 컴퓨팅의 시작

2014년 LA에 있는 한 연변 식당에서 늦깎이 유학생이었던 나는 어릴 때부터 알고 지내던 친구와 마주 앉아 있었다.
밥을 먹다가 친구가 물었다. “요즘은 무슨 공부해?”
그때 나는 학교에서 기초 컴퓨터 수학을 배우고 있었지만, 머릿속은 온통 최근에 본 양자 컴퓨터 영상으로 가득 차 있었다. 그래서 답했다.
“학교에서는 기초 컴퓨터 공부하고 있지만 요즘은 양자 컴퓨팅에 빠져있다.”

“그게 뭔데? 그걸로 뭘 할 수 있는데?”
그때의 나는 영상에서 본 대로, “손톱만 한 양자 컴퓨터 하나가 지금 제일 빠른 슈퍼컴퓨터보다 수백 배는 더 빨라질 거고, 인류가 풀지 못했던 수많은 문제를 해결할 거래”라고 어설프게 설명했었다.

그 후 많은 영상과 자료들을 찾고 읽어 봤지만 2022년에 와서야 처음으로 정식적인 양자 컴퓨터 교육을 받게 됐다. 물론 지금도 상업화된 개인 양자 컴퓨터가 없지만 멀지 않은 미래에는 누구나 사용할 수 있는 기술일 것 같았다. 그래서 지금까지 기록해 온 노트와 자료들을 정리하여 올리면 양자 컴퓨팅에 관심 있거나 공부하는 분들한테 도움이 될 것 같아서 글을 올리기로 했다.

“일반 컴퓨터보다 빠르다”는 말은 많이 들었지만, 도대체 왜 빠르고 어떻게 작동하는 걸까? 공부하고 있는 강의 자료들을 바탕으로, 수학적 원리부터 역사, 그리고 정의까지 상세하게 정리해 보았다.

양자 컴퓨터란 무엇인가?

“그냥 빠른 컴퓨터”가 아니다

많은 사람들이 양자 컴퓨터를 단순히 “현재 컴퓨터의 업그레이드 버전”이라고 생각한다. 하지만 이는 맞는 정의라고 말할 수 없다. 만약 단순히 속도만 빠른 것이라면 내 노트북도 언젠가 양자 컴퓨터가 될 수 있겠지만, 양자 컴퓨터는 계산 모델(Model of Computation) 자체가 완전히 다르다.

• 고전 컴퓨터(Classical Computing): 튜링 머신(Turing Machine) 모델 기반으로 모든 연산은 이산적인 단계(Discrete Steps)로 이루어진다.
• 양자 컴퓨터(Quantum Computing): 양자역학의 원리 중첩(Superposition), 얽힘(Entanglement)을 이용하여 데이터 연산을 수행한다.

1. Turing Machine: 긴 테이프에 기호를 읽고 쓰며 연산하는 가상의 기계로, 현대 컴퓨터의 이론적 기원.
2. Discrete Steps: 연속적이지 않고, 0과 1처럼 딱딱 끊어져서 순서대로 진행되는 과정.Model of Computation: 컴퓨터가 문제를 풀기 위해 데이터를 처리하는 수학적이고 논리적인 구조와 규칙.
3. Superposition: 하나의 입자가 측정 전까지 0과 1의 상태를 동시에 가지고 있는 현상.
4. Entanglement: 두 입자가 아무리 멀리 떨어져 있어도 운명처럼 연결되어 한쪽의 상태가 변하면 다른 쪽도 즉시 변하는 현상.

예를 들면 고전 컴퓨터로 2000비트 정수를 소인수 분해하려면 2²⁰⁰⁰번의 연산이 필요하다.
“우주에 존재하는 원자의 개수(10⁸⁰)보다 더 많은 프로세서를 동원해도, 우주의 수명보다 더 오랜 시간이 걸린다.” – Dr. David Zaret (2022)

하지만 양자 컴퓨터는 양자 병렬성(Quantum Parallelism)을 통해 지수적인(Exponential Time) 연산 횟수를 다항식 시간(Polynomial Time) 내에 처리할 수 있는 잠재력을 가지고 있다.

특정한 문제들을 양자 컴퓨터로 계산하면 고전 컴퓨터보다 훨씬 빠른 속도로 문제를 처리할 수 있지만, PPT를 만들거나 Excel을 정리하는 속도는 고전 컴퓨터가 아직까지 더 최적화되어 있다고 보면 된다.

1. Quantum Parallelism: 중첩 상태를 이용해 여러 가지 계산 가능성을 한 번에 동시에 처리하는 능력.
2. Exponential Time: 입력값이 조금만 커져도 계산 시간이 기하급수적으로 폭증하여 풀기 어려운 상태.
3. Polynomial Time: 입력값이 커져도 계산 시간이 비교적 완만하게 증가하여 현실적으로 풀 수 있는 상태.

왜 양자 컴퓨팅을 배워야 할까?

양자 컴퓨팅 기술은 양날의 검과 같다. 나쁜 점부터 얘기하자면 현재 인터넷 보안의 표준인 RSA, DSA 암호 체계가 무용지물이 될 수 있다. 양자 컴퓨터가 상용화되는 순간, 기존에 있는 모든 보안 시스템은 붕괴되고 은행, 국방, 핵 시설 같은 중요 인프라들은 엄청 큰 안전 위기를 겪을 수 있다. 하지만 이와 동시에 양자 시뮬레이션을 통해서 신약 개발, 신소재 발견 등 분자 단위의 시뮬레이션을 획기적으로 가속화할 수 있다. 그 외에 물류 최적화, 머신 러닝, 데이터 검색에서 엄청난 효율을 가져온다. 특히 AI 모델을 트레이닝하거나 빅데이터를 분석하는 데 있어서 혁신적인 속도 향상을 가져올 수 있다.

개인적으로 양자 컴퓨터는 next big thing(미래에 큰 영향을 미칠 것으로 예상) 이라고 생각한다.

양자역학(Quantum Mechanics)과 양자 컴퓨팅(Quantum Computing)

양자 컴퓨팅은 중첩, 간섭, 얽힘이라는 양자역학의 세 가지 핵심 원리를 기반으로 기존 컴퓨터와는 근본적으로 다른 방식으로 계산을 수행한다. 이 원리들은 양자 세계의 독특한 특성을 활용하여 정보 처리 능력의 비약적인 향상을 가능하게 한다.

중첩 (Superposition)

중첩은 양자 시스템이 측정되기 전까지 여러 가능한 상태를 동시에 가질 수 있는 현상을 말한다. 고전적인 비트가 0 또는 1 중 하나의 값만 가질 수 있는 반면, 양자 컴퓨터의 기본 단위인 큐비트(Qubit)는 0과 1의 상태를 동시에 표현할 수 있다.

• 정의: 이를 수학으로 표현하면 큐비트의 상태는 |ψ〉 = α|0〉 + β|1〉와 같이 표현된다.
  • |ψ〉라는 기호는 “켓 사이(Ket Psi)”라고 읽는다. 이는 폴 디랙(Paul Dirac)이 고안한 ‘브라-켓'(Bra-Ket) 표기법 중 하나로, 양자 시스템의 상태를 나타내는 벡터를 의미한다.
  • |0〉과 |1〉은 큐비트가 가질 수 있는 가장 기본적인 두 가지 상태다. |0〉은 고전 컴퓨터의 비트 ‘0’에 해당하고 |1〉은 고전 컴퓨터의 비트 ‘1’에 해당한다. 여기서 α와 β는 각 상태가 측정될 확률을 나타내는 복소수(Complex Number)이며, |α|² + |β|² = 1 확률의 합 법칙을 만족한다.
  • 측정하기 전까지 큐비트는 0과 1의 가능성을 모두 지닌 중첩 상태로 존재한다.
  • 예를 들어 큐비트 상태가 |ψ〉 = √0.6|0〉 + √0.4|1〉라면 측정하기 전에 이 큐비트는 0과 1이 섞여 있는 중첩 상태다. 하지만 측정하는 순간, 60%의 확률(|√0.6|² × 100% = 60%)로 0이 발견되고, 40%(|√0.4|² × 100% = 40%)의 확률로 1이 발견된다.
  • 측정 전까지는 0도 아니고 1도 아닌, 확률적으로만 존재하는 신비한 상태를 유지한다.

예를 들어 회전하는 동전은 좋은 비유가 될 수 있다. 땅에 떨어져 앞면(0) 또는 뒷면(1)으로 결정되기 전, 공중에서 회전하는 동안에는 앞면과 뒷면이 모두 나올 가능성이 열려 있다고 볼 수 있다. 이처럼 여러 상태가 확률적으로 동시에 존재하는 것처럼 보이는 상황을 직관적으로 설명하는 비유가 중첩이다.

또 다른 유명한 사고실험으로는 관측하기 전까지 살아 있는 상태와 죽어 있는 상태가 동시에 기술되는 “슈뢰딩거의 고양이”가 있다. 여기서는 상자 안의 고양이가 방사성 원자, 검출기, 독약 장치와 얽혀 있어서, 상자를 열어 보기 전까지는 ‘살아 있음’과 ‘죽어 있음’이 양자 상태로 함께 존재한다고 수학적으로 표현할 수 있다는 점을 강조한다. 다만 실제로 거시적인 고양이를 그런 중첩 상태로 직접 관측했다는 뜻은 아니고, 미시 세계의 중첩 개념을 거시 세계에까지 확장했을 때 생기는 역설을 보여 주기 위한 사고실험이다.

한편, 아인슈타인이 “내가 보지 않을 때도 달은 거기에 있다”고 말한 표현은, 관측이 현실을 ‘만든다’는 해석에 대한 비판적 입장을 드러내는 비유로 자주 인용된다. 달이 ‘볼 때만 존재한다’는 식으로 실제로 중첩 상태에 있다는 뜻이 아니라, 양자역학의 해석을 둘러싼 철학적 논쟁을 상징적으로 보여 주는 예로 이해하는 편이 더 정확하다.

간섭 (Interference)

양자 간섭은 큐비트의 중첩 상태들이 마치 파동처럼 서로에게 영향을 주어 특정 결과의 확률을 높이거나 낮추는 현상이다.

• 원리: 양자 알고리즘은 이 원리를 활용하여 정답에 해당하는 상태들의 확률 진폭은 보강 간섭을 통해 증폭시키고, 오답에 해당하는 상태들의 확률 진폭은 상쇄 간섭을 통해 소멸시킨다. 이를 통해 측정했을 때 정답을 얻을 확률을 극대화할 수 있다.

• 예시: 노이즈 캔슬링 이어폰은 소리의 간섭 현상을 이용한 좋은 예이다. 외부 소음이라는 파동에 반대되는 위상의 음파를 발생시켜 소음을 상쇄시키는 원리처럼, 양자 간섭은 원치 않는 계산 결과를 제거하는 데 사용될 수 있다. 이중 슬릿 실험에서 단일 전자를 발사해도 스크린에 여러 개의 밝고 어두운 띠, 즉 간섭 무늬가 나타나는 것도 전자가 파동처럼 두 슬릿을 동시에 통과하며 스스로 간섭했음을 보여주는 대표적인 예이다.

얽힘 (Entanglement)

얽힘은 두 개 이상의 큐비트가 서로 강하게 연결되어 하나의 통합된 시스템처럼 작동하는 현상이다. 얽혀있는 큐비트들은 물리적으로 아무리 멀리 떨어져 있어도 하나의 상태가 결정되면 다른 쪽의 상태가 즉시 결정되는 특별한 상관관계를 가진다.

• 특징: 예를 들어, 두 큐비트가 얽혀있을 때 하나의 큐비트를 측정하여 ‘0’ 상태로 확정되면, 그 즉시 다른 큐비트의 상태는 그와 쌍을 이루는 특정 상태로 결정된다. 이러한 즉각적인 상호작용은 정보 전달이 빛의 속도보다 빠를 수 없다는 기존의 물리 법칙을 넘어서는 것처럼 보이지만, 아직까지 실제로 정보를 전달하는 데 사용될 수는 없다.

• 예시: 한 쌍의 얽힌 장갑을 두 상자에 나눠 담고 하나는 서울에, 다른 하나는 뉴욕에 보냈다고 가정해 보자. 서울의 상자를 열어 왼쪽 장갑이 들어있는 것을 확인하는 순간, 뉴욕에 있는 상자에는 오른쪽 장갑이 들어있다는 사실을 즉시 알 수 있다. 이처럼 하나의 정보를 통해 다른 정보가 즉시 확정되는 관계가 얽힘의 핵심이다. 양자 컴퓨팅에서는 이러한 얽힘을 이용해 여러 큐비트 간의 복잡한 상관관계를 만들어냄으로써 동시에 수많은 연산을 처리할 수 있다.

양자 컴퓨터는 어떤 작업에 능숙한가?

양자 컴퓨터는 복잡도(Complexity)가 높은 문제에서 진가를 발휘한다. 곱셈은 스마트폰도 순식간에 계산한다. 하지만 소인수분해가 어떤 두 소수의 곱인지 찾는 건 어렵다. 예를 들어 800자리 숫자를 곱하는 건 쉽지만, 그걸 다시 소인수분해하는 건 슈퍼컴퓨터로 2,000년이 걸린다. 양자 컴퓨팅에 유명한 쇼어 알고리즘(Shor’s Algorithm)이라고 있다. 그 알고리즘을 쓰면 이 2,000년 걸릴 문제를 몇 시간 만에 풀 수 있다. 그 이유는 양자 중첩을 이용해 모든 가능성을 동시에 계산하기 때문이다.

오늘은 양자 컴퓨팅의 핵심 3대장(중첩, 간섭, 얽힘)과 이를 이해하기 위한 예제들을 정리해 봤다. 다음 편에서는 고전 컴퓨터 정보의 수학적 표현 그리고 양자 컴퓨터의 큐비트와의 관계에 대한 노트를 공유하겠다.

1. Complexity:  알고리즘이 어떤 문제를 풀기 위해 필요한 시간과 메모리 같은 자원의 양이 입력 크기에 따라 어떻게 증가하는지를 나타내는 수학적 척도이다.
2. Shor’s Algorithm:  큰 수를 소인수분해하는 일을 고전 컴퓨터보다 훨씬 빠르게 처리하도록 설계된 양자 컴퓨터용 대표 소인수분해 알고리즘이다.

참고자료

• Dr. David Zaret (2022), Johns Hopkins University: Quantum Computation Lecture Notes (01B Introduction, 01C Complex Vector Spaces, Quantum Mechanics Formalism Lecture)
• IBM, Introduction | IBM Quantum Learning. (n.d.). IBM Quantum Learning. https://quantum.cloud.ibm.com/learning/en/courses/basics-of-quantum-information/single-systems/introduction
• Educative, (n.d.). Hands-On Quantum Machine Learning with Python. Educative. https://www.educative.io/courses/hands-on-quantum-machine-learning-python/quantum-computing