양자 컴퓨팅은 어떤 문제를 빠르게 풀 수 있을까

[디지털비즈온 김맹근 기자] 양자 컴퓨팅이 기존 컴퓨팅보다 빠른 속도 향상을 가질 수 있는 이유는 단순히 말하자면 근본적인 연산 방식의 차이 때문에 발생한다. 기존 컴퓨팅이 Bit 단위의 연산(0과 1로 구분해 계산)을 진행‌ 했다면, 양자컴퓨팅은 Qubit 단위의 연산(0과 1을 동시에 계산)을 진행해서 기존 컴퓨터보다 계산 속도가 빠를 수 있다는 것이 양자 컴퓨팅에 대한 현재의 기술적 기대이다.

이에 따라 IBM, 구글, 마이크로소프트, IONQ 등 많은 기업들이 양자 컴퓨터를 연구 개발하고 있다. 이 기업들은 초전도체(Superconducting) Qubit와 이온 트랩(Ion Trapped) Qubit와 같은 다양한 기술을 활용하여 양자 컴퓨터의 성능을 향상시키고 있다.

양자 알고리즘 측면에서는 쇼어 알고리즘(Shor’s algorithm)과 그로벌 알고리즘‌ (Grover’s Algorithm)이 대표적인 예로 꼽힌다. 쇼어 알고리즘은 큰 수를 소인수분해하는 데 있어 고전 컴퓨터보다 훨씬 빠른 속도를 제공하며, 그로벌 알고리즘은 데이터베이스 검색에서 획기적인 성능 향상을 제공한다.

국가 단위에서는 미국이 2023년 $1 Billion 정도의 큰 금액을 향후 4~5년간 양자 컴퓨팅에 투자한다는 발표를 했고, 중국과 EU 역시 마찬가지로 큰 투자를 향후 해 나갈 계획이다.

이러한 양자 컴퓨팅에 관한 관심은 양자 컴퓨팅이 곧 상용화될 것처럼 그리고 모든 분야에 양자 컴퓨터가 적용된다면 게임 체인저가 될 수 있다는 기대와 이야기들이 많이 있는 것도 사실이다. 하지만 현재 양자 컴퓨터의 발전 속도와 어떤 문제에서 기존 컴퓨팅 대비 양자 컴퓨팅이 속도를 더 빨리 가져갈 수 있을지는 아직 불명확하다.

양자 경제적 우위 프레임워크

양자 알고리즘의 속도를 결정하는 것은 시간 복잡도(Time Complexity)와 입력 데이터의 크기(Problem Size)에 따라 달라질 수 있다. 시간 복잡도는 개의 입력 데이터에 대하여 알고리즘이 문제를 해결하는데 얼마큼의 시간이 걸리는지를 나타내며, 이 복잡도는 알고리즘 수행에 필요한 Step 수로 측정된다. 이는 입력 데이터의 크기에 달려 있으며, Step 수가 많을수록 복잡도가 높다는 것을 의미하고 이는 알고리즘의 속도가 더 느리다는 것을 의미한다.

다시 말해, 해당 프레임워크의 시사점은 기존 컴퓨터가 더 빠르기 때문에, 양자 컴퓨터는 더 나은 알고리즘을 가졌을 때만 기존 컴퓨터보다 더 빠를 수 있다는 것이다. 하지만 그렇다 하더라도, 양자 컴퓨터가 충분히 큰 알고리즘적 이점을 제공하려면, 입력 데이터의 크기(N*)가 충분히 커야 한다. 이 경우, 기업들이 양자컴퓨터 개발 계획을 밝힌 양자 로드맵을 확인하여 N* 크기의 문제를 계산할 수 있는 충분한 Qubit가 언제쯤 가능한지 알 수 있다. 이때가 양자 컴퓨터가 경제적 우위를 가지는 순간일 것이다.

기존의 양자 우위(Quantum Advantage)는 ‘특정 문제에 대한 모든 기존 컴퓨터를 능가할 수 있는 양자 컴퓨터가 존재한다.’는 개념이다. 하지만, 이 글에서 말하는 양자의 우위는 양자 경제적 우위(Quantum Economic Advantage)로 ‘특정 문제(및 입력 데이터의 크기)에 대해 비슷한 비용의 기존 컴퓨터를 능가할 수 있는 양자 컴퓨터가 존재한다.’는 것이다.

첫째 실행 가능성(Feasibility)은 문제가 양자 컴퓨터에 대해 실행 가능해지려면, 그 컴퓨터가 실제로 문제를 실행할 수 있을 만큼 충분히 강력해야 한다. 오늘날의 하드웨어에서, 양자 실행 가능성에 가장 중요한 기여 요소는 시스템이 구현 가능한 오류 수정 기능을 사용하여 문제를 실행할 수 있을 만큼 충분한 Qubit를 가지고 있는지 여부이다. Qubit 수가 증가하고 오류 수정이 개선됨에 따라 더 많은 문제가 실행 가능해질 것이다. 이 정의에서 알 수 있듯이, 양자 실행 가능성은 해결할 수 있는 문제에 대한 제약 조건이다.

둘째 알고리즘적 이점(Algorithmic Advantage)은 문제가 알고리즘적 이점을 가지려면, 그 문제 크기에 대해 양자 컴퓨터가 비슷한 비용의 고전 컴퓨터보다 더 빠르게 계산할 수 있어야 한다. 이 글의 제목에서 비유한 ‘경주’와 같이 양자 컴퓨터와 비슷한 비용의 고전 컴퓨터는 서로 경쟁한다. 양자 컴퓨터가 알고리즘적 이점을 가지려면, 더 나은 알고리즘이 고전 컴퓨터의 속도를 극복할 만큼 충분한 이점을 제공해야 한다. 또한, 필요한 오류 수정 오버헤드도 극복해야 한다.

셋째 예시 – DNA 검색은 위의 프레임워크를 적용할 예시를 찾는다면 DNA 검색을 들 수 있다. 사람의 유전체는 약 30억 개의 염기쌍으로 구성되어 있으며, 이를 입력 데이터 크기로 표현하자면 109 정도의 크기다. 기존의 선형 검색 알고리즘은 개의 입력 데이터 크기가 필요했다면, 양자 선형 검색 알고리즘은 루트n 의 크기가 필요하다.

결론적으로 양자 컴퓨팅이 모든 면에서 경제적으로 우위에 있는 것은 아니다. 특정한 상황에 따라 이점이 다르다. 제목의 비유처럼 고전적인 토끼(기존 컴퓨팅)는 더 빠르고, 작은 입력 데이터 크기에 적합한 반면, 양자 거북이(양자 컴퓨팅)는 더 느리지만, 더 나은 알고리즘으로 큰 입력 데이터 크기에 적합하다.

따라서 미래의 연구들은 다음과 같다. 첫째, 현재는 IBM의 양자 로드맵을 활용한 분석을 하였지만 IONQ와 같이 다른 기술들에 이 프레임워크를 적용할 수 있다. 둘째, 기업들의 알고리즘 사용 정보를 활용하여 그들이 어떻게 양자 기술을 적용할지 예측할 수 있다. 셋째, 기업이나 산업 수준으로 양자 노출 지수를 계산할 수 있다. 넷째, 양자 컴퓨팅이 거시 경제 생산성에 미칠 영향을 예측할 수 있다.