The Practicality of Randomized Quantum Linear Systems Solvers

당신이 일반적인 컴퓨터로는 적절한 시간 내에 풀 수 없는, 너무 거대하고 뒤엉킨 수학 문제의 매듭을 풀려고 노력하고 있다고 상상해 보십시오. 이것이 바로 양자 컴퓨팅의 세계이며, 이곳에서 과학자들은 미립자의 기묘한 규칙을 사용하여 이러한 불가능한 퍼즐을 해결하는 기계를 만듭니다. 그들이 해결하고자 하는 가장 유명한 퍼즐 유형 중 하나는 "선형 시스템(linear system)"으로, 이는 본질적으로 특정 답이 숨겨져 있는 거대한 숫자 격자와 같습니다. 이 암호를 해독하기 위해 연구자들은 "해밀토니안 시뮬레이션(Hamiltonian simulation)"이라고 불리는 기술을 사용하는데, 이는 양자 시스템이 시간에 따라 어떻게 변하는지 보여주는 영화를 실행하는 것과 같습니다. 오랫동안 이 방법을 수행하는 최선의 방법은 믿을 수 없을 정도로 깊고 복잡한 회로를 구축하는 것이었습니다. 마치 젠가 블록으로 고층 빌딩을 쌓으면서 무너지지 않게 만드는 것과 같았습니다. 하지만 최근, 새로운 아이디어가 등장했습니다. 만약 건물을 한꺼번에 다 짓지 않는다면 어떨까요? 만약 우리가 건물에 대한 무작위적이고 빠른 스냅샷을 여러 번 찍고, 그것들을 평균 내어 사진이 충분히 선명하기를 바란다면 어떨까요? 이 "무작위화된(randomized)" 접근 방식은 훨씬 더 단순하고 초기 양자 컴퓨터에서 구현하기 쉬울 것이라는 약속을 했습니다.

하지만 로런스 버클리 국립 연구소와 BlueQubit Inc.의 시다르트 하리프라카쉬(Siddharth Hariprakash)와 그의 팀은 이 유망한 아이디어를 궁극적인 테스트에 부치기로 결정했습니다. 그들은 단순히 이론을 살펴본 것이 아니라, 이 무작위 스냅샷 방식이 실제로 작동하기 위해 얼마나 많은 자원(시간과 컴퓨터 전력 등)이 필요한지를 알아내기 위해 정교한 수학 계산을 수행했습니다. 이것은 마치 모든 사람이 달까지 갈 수 있다고 주장하는 자동차의 연료 게이지를 확인하는 것과 같습니다. 연구진은 여정의 상세한 지도를 만들었고, 선명한 답을 얻기 위해 필요한 모든 단계를 계산했습니다. 그들의 결과는 일종의 현실 자각 타임입니다. 무작위 방식이 구축하기에는 확실히 더 단순하지만, 실제로는 믿을 수 없을 정도로 비효율적이라는 사실이 밝혀졌습니다. 그들은 심지어 아주 작고 단순한 문제(4x4 격자)에 대해서도, 이 방법이 제대로 된 답을 얻기 위해 약 10의 15승 개에 달하는 논-클리포프 게이트(non-Clifford gates)라는 엄청난 양의 연산을 필요로 한다는 것을 발견했습니다. 이를 체감해 보자면, 이 숫자는 현재 또는 가까운 미래의 기술로는 달성하는 것이 거의 불가능할 정도로 거대합니다.

이 논문은 이러한 "스냅샷"을 찍는 두 가지 방법을 비교합니다. 한 방법은 엄격한 레시피(Product Formula라고 불림)를 따르는 것이고, 다른 한 방법은 다음 움직임을 결정하기 위해 주사위를 굴리는 것(Random Taylor Expansion이라고 불림)입니다. 연구진은 "주사위 굴리기" 방식이 엄격한 레시피보다 더 나은 선택지라는 것을 발견했는데, 이는 더 적은 자원을 요구한다는 의미입니다. 하지만 핵심은, 이 더 나은 방법조차 실세계의 문제를 해결하기에는 너무 비싸다는 점입니다. 연구는 이 무작위 방식이 초기 양자 컴퓨팅 시대에 우리가 기대했던 마법의 탄환이 아닐 수도 있음을 시사합니다. 저자들은 이 특정 문제들에 대해 비용이 너무 높다는 것을 (단순히 끝에서 추측한 것이 아니라 정확한 숫자를 계산해 낸) 명확한 비점근적(non-asymptotic) 증명을 제공했습니다.

무작위 솔버의 이야기

저자들이 실제로 무엇을 했는지 자세히 살펴보겠습니다. 그들은 선형 방정식을 풀기 위해 설계된 특정 유형의 양자 알고리즘을 조사했습니다. 거대하고 복잡한 기계(행렬)가 있다고 가정하고, 특정 입력을 넣었을 때 어떤 결과가 나올지 알고 싶다고 상상해 보십시오. 목표는 출력을 찾는 것이지만, 기계가 너무 복잡해서 한 번만 실행해서는 안 됩니다.

연구진은 "무작위적" 접근 방식에 집중했습니다. 기계를 완벽하게 실행하는 대신, 이 방법은 많은 무작위 샘플을 취함으로써 답을 근사하려 합니다. 이는 경기장에 있는 모든 사람의 키를 측정하는 것과 같습니다. 모든 사람을 일일이 측정하는 것은 어렵고 시간이 오래 걸립니다. 대신 몇 명의 사람을 무작위로 골라 키를 묻고, 그 추측값들을 평균 내는 것입니다. 많은 무작위 추측을 통해 복잡한 설정 없이도 정답에 도달할 수 있다는 희망이었습니다.

논문은 이 과정을 세 가지 주요 단계로 나누어 매우 정밀하게 분석했습니다:

1. 레시피 (푸리에 급수): 먼저, 수학 문제를 샘플링할 무작위 "시간"들의 급수로 변환하는 방법을 알아내야 했습니다. 그들은 행렬의 역행렬을 근사하기 위해 푸리에 급수라는 수학적 트릭을 사용했습니다. 이것은 당신에게 정확히 어느 무작위 시점에 관찰해야 하는지를 알려주는 레시피를 만드는 것과 같습니다. 저자들은 좋은 근사치를 얻기 위해 얼마나 많은 재료(급수의 항)가 필요하고 얼마나 정밀한 측정이 필요한지를 정확히 계산했습니다. 그들은 작은 문제에 대해서도 많은 재료가 필요하다는 것을 발견했습니다.
2. 스냅샷 (해밀토니안 시뮬레이션): 다음으로, 각 무작위 시간마다 양자 컴퓨터는 시스템을 시뮬레이션해야 합니다. 이것이 어려운 부분입니다. 저자들은 이 시뮬레이션을 수행하는 두 가지 방법을 조사했습니다:
   • 곱 공식 (Product Formula, PF): 이것은 긴 여정을 작은 단계들로 나누는 것과 같습니다. 조금 걷고, 멈추고, 다시 조금 더 걷는 식입니다. 매우 구조화된 방식입니다.
   • 랜덤 테일러 전개 (Random Taylor Expansion, RTE): 이것은 더 혼란스럽습니다. 마치 주사위를 굴려 몇 걸음을 가고 어느 방향으로 갈지 결정하는 것과 같습니다. 여기에는 두 번째 층위의 무작위성이 도입됩니다.
3. 평균 (샘플링): 마지막으로, 이 스냅샷들로부터 얻은 모든 결과를 평균 내어 최종 답을 얻습니다. 더 많은 스냅샷을 찍을수록 실제 답에 더 가까워집니다.

대형 공개: 너무 비싸다

이 논문의 가장 중요한 부분은 "비용"을 계산하는 것입니다. 양자 컴퓨팅의 세계에서 비용은 컴퓨터가 수행하는 기본 연산인 "게이트"로 측정됩니다. 저자들은 특정 정확도를 달amat기 위해 얼마나 많은 게이트가 필요한지 정확히 계산했습니다.

그들은 비용이 믿을 수 없을 정도로 빠르게 증가한다는 것을 발견했습니다. 심지어 아주 작은 문제인 4x4 행렬(조건수(condition number)가 100인 경우)에 대해서도, 이 방법은 수렴하기 위해 약 10^15 (1 뒤에 0이 15개 붙는 숫자) 개의 논-클리포프 게이트를 필요로 합니다. 이 숫자는 현재 또는 가까운 미래에 우리가 만들 수 있는 그 어떤 양자 컴퓨터도 감당할 수 없는 수준입니다. 이것은 마치 이쑤시개만을 사용하여 대양을 가로지르는 다리를 놓으려는 것과 같습니다. 수학적으로는 가능할지 몰라도, 재료가 뒷받침되지 않는 것입니다.

저자들은 두 가지 시뮬레이션 방법(PF와 RTE)을 비교했습니다. 그들은 랜덤 테일러 전개(RTE) 방식이 곱 공식(PF)보다 훨씬 더 낫다는 것을 발견했습니다. 구체적으로, RTE는 동일한 정확도에 도달하기 위해 PF보다 약 한 자릿수(10배) 적은 게의를 요구합니다. 하지만 이 10배의 개선 효과가 있음에도 불구하고, 전체 게이트 수는 여전히 천문학적으로 높습니다. 논문은 두 방법 모두 현재 또는 근미래의 하드웨어에는 실용적이지 않다고 명시적으로 밝히고 있습니다.

이것이 미래에 의미하는 바

이 논문은 단순히 "어렵다"고 말하는 것이 아니라, 왜 어려운지에 대한 명확한 지도를 제공합니다. 주요 병목 현상은 문제의 "조건수(condition number)"입니다. 문제가 어려워질수록(조건수가 높아질수록), 필요한 게이트의 수는 4제곱으로 증가합니다. 즉, 문제의 난이도가 두 배가 되면 자원이 16배 더 필요하다는 뜻입니다. 이러한 스케일링 법칙 때문에 무작위 접근 방식은 과학자들이 실제로 해결하고자 하는 종류의 문제들에 대해 매우 비싼 비용을 치르게 만듭니다.

저자들은 자신들의 결과가 단순한 추측이 아니라 명시적인 계산과 시뮬레이션에 기반하고 있음을 매우 신중하게 밝히고 있습니다. 그들은 수학을 작은 무작위 행렬들에 대해 테스트했으며, 그들의 예측이 실제 시뮬레이션 결과와 완벽하게 일치함을 확인했습니다. 이는 결론에 대한 높은 신뢰를 줍니다: 양자 알고리즘을 무작위화하는 아이디어는 영리하고 회로의 복잡성을 줄여주기는 하지만, 요구되는 샘플의 양이 너무 많아 가까운 미래에 선형 시스템을 해결하는 데는 비실용적이라는 결론입니다.

결국, 이 논문은 중요한 현실 자각을 제공합니다. 유망하고 화제가 되는 아이디어를 물리학과 공학의 냉혹한 숫자와 대조해 본 것입니다. 결과적으로 무작위 접근 방식은 이론적으로는 흥미로운 연구이지만, 초기 양자 컴퓨터를 위한 마법의 탄환은 아닙니다. 저자들은 우리가 진전을 이루고자 한다면, 예를 들어 클래식 컴퓨터를 사용하여 문제를 먼저 단순화하거나, 이토록 방대한 양의 무작위 샘플을 요구하지 않는 새로운 수학적 트릭을 찾는 등 문제를 분해하는 다른 방법을 찾아야 할 수도 있다고 제언합니다. 하지만 현재로서는, 복잡한 선형 시스템을 간단한 무작위 양자 지름길로 해결하겠다는 꿈은 여전히 하드웨어나 알고리즘 설계의 돌파구가 나타나기를 기다리는 하나의 꿈으로 남아 있습니다.