Quantum Computing and Homomorphic Encrpytion

January 19, 2025

Quantum Computing Intro #

양자 컴퓨팅이 최근 화두로 떠오르고 있어서 공부를 시작해 보았습니다. 아직 깊이 이해한 것은 아니지만 (사실 모름), 배운 내용을 정리하며 개념을 확립하려는 목적으로 작성했습니다. 특히 암호학과 양자 컴퓨팅의 접점에 관심이 있어, 이 기술이 현재의 인공지능과 암호화 기술에 어떤 변화를 가져올지 알아보고 싶었습니다. (그리고 10번째 포스팅. 1과 0이 동시에 있으니 양자 알고리즘과 관련해서 글을 쓰고 싶었던 이상한 이유도 있습니다.)

Quantum Computing #

우선, 양자 컴퓨팅을 고전 컴퓨팅과 비교해보겠습니다.

양자 컴퓨팅은 고전 컴퓨팅과 비교해볼 때 본질적인 차이가 있습니다. 고전 컴퓨팅은 스위치의 on/off 상태를 이용해 1과 0으로 정보를 처리하며, 이를 통해 확률적인 결과를 계산하기도 합니다. 반면, 양자 컴퓨팅의 기본 단위는 큐비트(qubit)입니다.

큐비트는 단순히 1 또는 0이 아니라, 두 상태가 동시에 존재할 수 있는 중첩(superposition)을 나타냅니다. 예를 들어, 큐비트는 [1, 0] 또는 [0, 1]의 기저 벡터뿐만 아니라, [1/√2, -1/√2] 같은 상태도 가질 수 있습니다.

중요한 점은 이 모든 상태가 기저 벡터로 표현된다는 것입니다.

Linear Algebra and Quantum #

특징 3가지를 기점으로 작성했습니다.

1 특징으로는 양자 컴퓨팅은 유한 차원 벡터 공간을 사용합니다.

양자 컴퓨팅에서는 algebra 개념이 필수적입니다. 물론 무한 차원이 아닌 유한 차원 벡터 공간을 사용하며… 복소수(complex number)가 중요한 역할을 합니다. 이는 전자의 스핀 같은 양자 상태를 다양한 각도에서 측정할 때 필요합니다.

2 그리고 선형 대수에서 브라-켓 표기법을 채택하여 사용합니다. 양자 컴퓨팅에서 column 벡터는 ket 으로, row 벡터는 bra 로 표현됩니다. 예를 들어:

column vector를 v라고 했을 때,

|v> = [2 3 -2].Transpose

row vector를 w라고 했을 때

<w| = [1 0 -pi 23]

꺽쇠 모양이 열인지 행인지에 따라 다릅니다. 계산 방식은 기존 선형대수학과 동일하지만, 표현 방식만 다릅니다.

3 양자 컴퓨터의 단위는 큐비트입니다.

큐비트는 유한 차원 벡터 공간의 unit ket입니다.

기저 벡터로 이해하는 게 빠릅니다 [1 0] [0 1]

스핀해서 [1/root(2) -1/root(2)] [ 1/root(2) 1/root(2) ]

큐비트가 가질 수 있는 상태는 무한히 많으며, 이는 고전 컴퓨팅의 이진 상태와 근본적으로 다릅니다.

local realism debate #

• 국소적 실재론(local realism)

입자는 자신이 위치한 국소적 환경에만 영향을 받는다는 개념입니다.

아인슈타인과 보어의 논쟁은 이 국소적 실재론을 둘러싸고 진행되었습니다.

• 뉴턴과 양자역학의 차이

예를 들어, 뉴턴 역학에서는 초기 조건(질량, 거리 등)을 알면 결과를 완벽히 예측할 수 있습니다. 하지만 양자역학에서는 결과가 확률적으로 나타나며, 불확실성이 존재합니다.

좀 더 구체적으로는 지구는 태양 주위를 공전하는 예시를 들 수 있는데. 지구 질량, 태양 질량, 거리, 중력 상수가 주어지면 인력의 크기를 구할 수 있지만(뉴턴 법칙), 연결하는 매커니즘이 무엇인지 알려주지 못합니다. 국소적 실재론은 행성은 자신이 위치한 시공간의 모양에 따라 움직인다는 것이고, 아인슈타인의 국소적 실재론이 더 그럴듯하지 한 쪽의 상태가 관찰되면 다른 쪽 상태도 동시에 변하는 원격 작용은 너무 수수께끼 같은 이론이었습니다. 보어도 아인슈타인이 말한 것처럼 고전적인 관점이 더 그럴듯해서 해당 이론이 맞다고 주장하고 싶어할 정도로… 사실상 결정론적이고 모든 초기 조건을 알면 결과를 100% 확실하게 예측할 수 있는 이론이 그럴듯해보이죠.

Quantum Algorithm #

양자 알고리즘은 고전 알고리즘과 비교했을 때 특정 문제를 빠르게 해결할 수 있기도 합니다. 이는 모든 가능한 입력값을 중첩 상태로 동시에 계산할 수 있기 때문입니다. 하지만, 이러한 계산에서 정확한 답을 얻는 것은 중첩 상태를 적절히 조작하는 데 달려 있습니다. 따라서 뒤집어 해석하면, 틀릴 확률이 고전 컴퓨팅 계산 보다 높을 수 있습니다.

양자 컴퓨터의 등장은 암호학에 바로 영향을 줍니다. 그 중 속도 부분에서 암호학적 문제 해결에 큰 영향을 미칠 수 있습니다. 예를 들어, 현재 널리 사용되는 RSA 암호화 방식은 큰 수를 두 개의 소수로 분해하는 것이 계산적으로 불가능하다는 전제에 기반합니다.

좀 더 구체적으로, 자주 사용하는 암호인 RSA 방식은 300자리의 값을 두 개의 소수로 구하는 게 불가능하다는 걸 전제로 합니다. 예를 들어, 88631 이라는 값이 있는데, 해당 1개의 수를 소수 2개의 곱. 즉, 가장 큰 두 개의 소수이면서 정수 값을 찾는 걸 예시로 했을 때, 해당 문제를 푸는데 얼마나 시간이 걸릴까요? 일단 저 숫자도 300자리는 아니기 때문에 금방 풀 수 있겠지만 300자리를 넘어간다면? 고전 컴퓨팅에서는 exponential time 을 요구하는 문제라고 주장하지만, 양자 컴퓨팅에서는 풀 수도 있다는 걸 가정할 수 있습니다. 보통 해당 2개의 소수는 공개하지 않고 안전하게 보관해서 통신을 암호화하는데 사용합니다. 보안성은 도청자가 2개의 소수 값을 얻을 수 없다는 사실에 의존하기 때문이죠.

Homomorphic Encryption #

양자 컴퓨팅 시대의 보안에 대한 이슈가 떠오를 것으로 예측할 수 있습니다. 만약 양자 알고리즘이 기존 암호를 푼다면, 이를 대비한 새로운 암호화 방식이 필요합니다.

동형 암호(Homomorphic Encryption)는 이러한 대안 중 하나입니다. 동형 암호는 중간 과정에서 데이터가 노출되지 않은 채 연산이 가능한 방식입니다. 이 개념은 Linear Algebra의 homomorphism에서 유래했으며, 데이터의 구조를 유지하면서 안전하게 전송하고 처리할 수 있습니다. 구조를 잃지 않고 옮겨지는 함수입니다.

따라서 누가 ‘관찰’하느냐/중간 ‘intercept’당하는지와 상관없이 암호해독이 이뤄집니다.

추가적으로, alice, bob, eve는 암호학에서 자주 언급되는 용어입니다.

computing #

그렇다면 큐비트는 현실에서 어떻게 구현을 하는 걸까요.

큐비트를 안정적으로 유지하기 위해 다양한 물리적 구현 방법이 시도되고 있습니다. 광자, 전자 스핀, 이온, 원자핵 등의 방법이 시도되었습니다.

IBM과 구글은 초전도체 큐비트를 사용하는 양자 컴퓨터를 개발했습니다.

최근에는 전자를 다이아몬드에 가두는 방식과 같은 신기술도 연구되고 있습니다.

• 양자 우위(Quantum Supremacy)

큐비트의 수가 많아질수록, 양자 컴퓨터는 고전 컴퓨터가 따라잡을 수 없는 속도로 계산할 수 있습니다.

초기에는 72큐비트 수준에서 시작했지만,

최근에는 105큐비트 이상을 탑재한 시스템도 등장했습니다.

양자 우위에 도달하면, 양자 컴퓨터는 기존 컴퓨터로는 불가능했던 문제를 해결할 수 있게 될 것입니다.

그럼 고전 컴퓨터는 사라지고 양자 컴퓨터로 기존의 컴퓨팅이 해결한 문제들을 포함해서 새로운 문제들을 해결하는 시대가 오지 않을까 예상합니다.