최근 양자컴퓨터와 양자우월성에 관한 흥미로운 두 논문이 아카이브에 올라왔다. 이전 글들 [글 1, 글 2, 글 3, 글 4, 글 5]보다 훨씬 간단하게 정리해봄. 앞선 글에서 찾을 수 있겠지만, 양자우월성 실험은 고전컴퓨터로 수행하기 어렵거나 굉장히 오랜 시간이 걸리는 일을 양자컴퓨터를 통해 빠르게 수행하는 실험을 말한다. 그러한 일을 찾는것도 꽤나 중요한 문제이고, 현재 실험에서는 랜덤회로샘플링 [관련 지난 글]이나 보손샘플링 [관련 지난 글]을 쓴다.

• 우선 오늘 올라온 논문에 따르면 중국의 여러 팀이 모여 구글의 이전 양자우월성 실험에 쓰였던 Sycamore를 뛰어넘는, 최대 66큐비트까지 다룰 수 있는 새로운 양자컴퓨터 Zuchongzhi를 만들었다고. 이름은 중국의 수학자 조충지에서 따온듯. 이 새로운 컴퓨터를 통해 구글이 진행했던 랜덤회로샘플링을 56큐비트, 20뎁스에 대해 1.9 × 10⁷개의 수를 샘플링했고, 이를 통해 0.0662%의 XEB Fidelity를 얻었다고. 비교대상이였던 과거 구글의 실험은 53큐비트, 20뎁스에 대해 3 × 10⁶개의 수를 샘플링했고, 0.224%의 Fidelity를 얻었다. (지난 글에도 말했지만, 정확한 양자컴퓨터는 100%에 가까운 Fidelity를 얻어야한다! 그만큼 에러가 넘친다는 말.)
  
  고전 시뮬레이션을 통해 비슷한 결과를 얻으려면 27648개의 GPU를 가진 슈퍼컴퓨터 Summit을 이용했을때 Sycamore의 실험은 15.9일, 자신들의 실험은 8.24년이 걸릴것이라고, 지난글에서 다뤘던 Pan과 Zhang의 결과는 일종의 치팅이여서 샘플된 수가 xxx0000처럼 생겨 굉장히 편향되어있고, 확인하기 쉽기때문에 직접 비교의 대상으로는 삼지 않았다고 한다.
  
  개인적인 느낌으로는 당연히 훌륭한 결과지만, Sycamore가 첫 발자국을 찍은 이후로 나온 자연스러운 다음 걸음으로 보임 ㅋ 보손샘플링도 그렇고 양자컴퓨터의 구현측에서 중국이 선두로 나서고 있다는 의미가 큰듯.
  
  
  
• 지난주 올라온 논문은 조금 다르게 양자 문제를 고전 컴퓨터로 푸는것에 대해 다룬다. 특히 여러 입자에 대한 정보가 주어졌을 때 이후 상태를 예측하는 다체 문제(Many-body problem) 등의 문제는 한꺼번에 많은 정보를 다뤄야하기때문에 고전적인 컴퓨터를 사용해서는 푸는것이 어렵다고 알려져 있다. 그런데, 이전 여러 논문 [관련 논문]에서 (고전적) 기계학습의 모델을 잘 설계하고 양자 실험결과를 데이터로 주면 휴리스틱하게 다체 문제를 잘 푼다는 것이 알려졌다고 한다.
  
  이 논문에서는 이러한 다체 문제에 관련된 태스크와 다른 몇몇 태스크가 기계학습을 이용해 잘 풀수 있다는 걸 증명했다고 한다. 즉, 고전적 기계학습이 다체문제를 풀 수 있다는걸 증명했다고 한다. 저자들이 사용한 방식은 특정 양자상태를 고전적으로 기록하는, 최근 발전된 classical shadow라는 툴을 사용했다고. 얘는 물리도 머신러닝도 잘 몰라서 더 자세히 읽기 어렵다..
  
  쓰고보니 얘는 양자컴퓨터와도 양자우월성과도 직접적인 관계는 없구만 -_- 그치만 다체문제의 경우 양자컴퓨터가 잘 풀수 있는 구체적인 예시로 제시되었던 것 같으니, 양자컴퓨터에 대한 작은 회의감을 불러 일으킬수도 있겠다. Classical shadow는 여러번 들어보았는데 아직 제대로 공부를 안해봤다 -_- 물론 머신러닝쪽도 잘 모르니 논문을 읽을 엄두도 안나지만.

오늘 막 중국 두 연구자 Feng Pan과 Pan Zhang이 아카이브에 발표한 결과에 따르면 구글의 양자우월성 실험 [지난글 1, 지난글 2, 지난글 3]이 양자우월성을 보여주지 못한다고 한다. 즉, 고전컴퓨터를 이용한 시뮬레이션으로 양자컴퓨터 실험보다 더 정확한 샘플링 결과를 얻었다는 것. 아직 검증이 되지는 않았지만, 논문에서 주장하는 결과와 논의를 요약하면 다음과 같다.

• 0에 가까울수록 고전컴퓨터에, 1에 가까울수록 (더 좋은) 양자컴퓨터에 가까운 척도가 되는 XEB Fidelity 값이 구글의 실험(0.002)을 압도하는 0.739를 달성했다고 한다. 실험은 60개의 GPU를 이용해 5일간 진행하여 2백만개의 샘플을 얻어냈다고.
• 다만 고전적 알고리즘 자체는 (랜덤 회로의 depth/qubit 수의) 지수적시간이 필요해서 구글의 양자컴퓨터 실험이 더 큰 범위로 된다면 다시 양자우월성을 보일수 있을 것이라고.
• 또한 구글의 실험과 다르게 2백만개의 샘플이 서로 correlated 되어있다는 문제도 있다고 한다. 그치만 별 문제는 아닌듯.

이전 다른 논문이 슈퍼컴퓨터를 이용해 20일정도에 구글의 실험과 비슷한 결과를 얻을 수 있을거라고 했는데, 그거보다 훨씬 좋은 결과인듯. 결과의 참거짓은 모르지만, 다행히 보손샘플링을 이용한 양자우월성 실험 [지난글]이나 여기는 언급하지 않은 불완전한 증명이 주어진 NP문제의 검증에 대한 실험 논문도 있어서 그래도 최소한 에러가 있는 양자컴퓨터는 가까이 있지 않을까 희망해본다 -_-.

볼록최적화(Convex optimization)의 대표적인 방식으로 유명한 경사하강법(Gradient Descent)이 있다. 이 방법은 f:Rⁿ->R의 함수값 중 일정 범위에서 최솟값을 (정확히는 극값 local minimum을) 찾는 유용한 방법이다. 특히 f가 아래로 볼록인 경우 항상 최솟값을 잘 찾아줌이 알려져 있다.

경사하강법은 굉장히 직관적이라는 장점이 있다. 최적화를 해 나가는 과정에서 각 점의 함수값 f(x)과 기울기(gradient) ∇f(x)만을 계산하고, 다음 점을 찾을 때 현재 점에서 기울기방향으로 조금씩 진행해 나가는 것. 이런식으로 f와 ∇f만을 이용해 최적값을 구하는 문제를 1차 볼록최적화(first-order convex optimization)이라고 한다. 놀랍게도 1차 볼록최적화의 경우 고전적으로 경사하강법이 최적임이 알려져 있다고 한다.

그런데 오늘 올라온 마이크로소프트 팀의 로빈 코타리(Robin Kothari)등의 논문 [1]에 따르면 일반적으로 경사하강법이 양자알고리즘을 고려해도 최적이라고 한다. 정확한 저자들의 결과만 보면 (대충) 다음과 같다.

우선 저자들의 목표는 다음 문제를 푸는 것이다.

[문제 1] 아래로 볼록인 f:Rⁿ->R이 B(0,R)에서 G-Lipschitz continuous이고, x*=argmin_x∈B(0,R)(f(x))일 때, f(x)≤f(x*)+ε인 x를 함수값 f와 기울기 ∇f를 최소한으로 계산하며 찾는것이다. 양자알고리즘은 해당 값을 양자적으로 계산할 수 있다.

우선 이전에 알려진 결과는 다음과 같다.

정리 1. 사영 경사강하법은 (GR/ε)2번의 함수값과 기울기 계산을 통해 문제 1을 풀 수 있다.

여기서 사영 경사강하법은 B(0,R)으로 나간 경우 B(0,R)으로 사영해버리는 방식으로 진행하는 경사강하법이다.

정리 2. (G,R,ε이 정해졌을 때) 어떤 볼록함수들의 집합이 존재해서, 문제 1을 푸는 임의의 고전알고리즘 (e.g. 에러가 있는, 확률론적..)은 최악의 경우 Ω((GR/ε)2)번의 함수값과 기울기 계산을 해야만 한다.

이 결과는 여러번 다른 방법으로 증명되었다고 한다. 예를 들어 Nemirovsky와 Yudin의 오래된 교과서 [2]에서나, NeurIPS’19에 게제된 논문 [3]에서도 그 결과를 증명했다고. 이 논문에서 이 결과를 새로 증명하기도 하는데, 저자들의 주장으로는증명이 더 간단하고 필요한 f의 정의역의 차원 n이 비교적 작다고.

그리고 저자들의 결과는 정리 2의 양자버젼. 다음과 같다.

정리 3. (G,R,ε이 정해졌을 때) 어떤 볼록함수들의 집합이 존재해서, 문제 1을 푸는 임의의 양자알고리즘은 최악의 경우 Ω((GR/ε)2)번의 함수값과 기울기 계산을 해야만 한다.

다만, 두 정리에서 잡는 함수들의 집합이 좀 다르다. 특히 저자들은 정리 2에서 사용한 함수들의 집합의 경우 양자적으로는 O(GR/ε)번의 계산만 해도 충분함을 보였다고.

전공분야는 아니지만 재미있어보여서 약간 정리해봄 -_-ㅋㅋ 논문도 엄청 어려운것 같지는 않고, 증명 자체는 BBBV97 [4]부터 내려온 스탠다드한 hybrid argument를 쓰는듯 하다. 그치만 그래도 길고 별로 흥미롭지도 않으니 생략.

[1] No quantum speedup over gradient descent for non-smooth convex optimization, arxiv.org
[2] Problem complexity and method efficiency in optimization, Wiley
[3] Complexity of highly parallel non-smooth convex optimization, NeurIPS 2019
[4] Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing

작년 화제가 된 구글의 양자우월성 증명은 양자랜덤회로를 만들고, 그 결과를 측정(measure)하여 얼마나 올바른 분포를 만들었는지를 관측하는 XEB Fidelity benchmark를 사용했다. 지난번 관련된 글을 두개 써서 현황을 설명하기도 했다.

그런데 실제로 우리가 쓸 것으로 예상되는 회로들은 Grover의 알고리즘이나 HHL의 선형방정식 알고리즘, 양자 머신러닝, Shor의 알고리즘등 같은 연산을 반복하거나 (Grover, HHL) 비슷한 연산을 반복하는 양자 Fourier 변환등을 이용하게 된다. 즉, 우리가 실제로 쓸 연산은 랜덤회로와 달리 굉장히 구조적이라는 것.

그렇다면 과연 구글의 양자랜덤회로 샘플링을 통한 평가가 우리가 실제로 쓸 것으로 예상되는 “구조적”인 알고리즘을 평가하는데에 얼마나 도움이 될까? 가장 이상적으로는 랜덤회로나 구조적인 회로나 비슷한 수준의 에러를 갖거나, 구조적인 회로가 더 적은(!)에러를 갖는 경우일 것이다.

하지만 안타깝게도, 어제 아카이브에 올라온 논문에 따르면 실제로는 그 반대인듯 하다고 한다. 즉,

현재 기술로는 양자랜덤회로 샘플링이 구조적 알고리즘보다 쉽다

라는 것. 그러니까, 양자랜덤회로의 에러가 구조적 알고리즘의 에러보다 더 작다는 말.

다만 이 실험은 구글의 Sycamore가 아닌, 실험하기 더 쉬운 IBM Q와 Rigetti의 양자컴퓨터를 이용해서 진행했다고 하니 Sycamore의 경우는 어떤지 아직 알수는 없다. 그 실험적 결과는 아래와 같다.

위 그림을 살펴보면 꽤나 부정적인 결과를 여럿 얻을 수 있다.

• 전체적으로 회로의 정확성이 예측보다 훨씬 못한 편이다.
• 대체적으로 구조적 회로가 랜덤회로보다 훨씬 부정확하다. (가끔 그렇지 않은 경우도 있긴 하다)
• 7큐비트정도부터는 depth를 조금만 늘려도 전부 다 제 멋대로 나오는듯 하다.
• IBM Q Melbourne은…. 뭔가 문제가 있어 보인다.

근데, 지난 글에서 구글의 실험 자체가 옳은지를 검증하는게 어렵다는 말을 한적이 있다. 이 논문에서 어떻게 구조적 회로와 랜덤회로의 정확성/에러를 확인한걸까? 마지막으로 논문에서 이 부분을 어떻게 해결했는지 살펴보자.

저자들이 사용한 방식은 거울회로, 혹은 실험에 사용한 회로 C의 역인 C^-1, 혹은 그의 변형을 생각하는 것이다. 논문에서는 다음과 같이 그림으로도 설명해준다.

대충 원래 적용한 회로의 역, 혹은 그거를 약간 변형한 방식을 한번 더 적용함으로써 답이 고전상태로 정해지는 독특한 회로를 만든것.

이 회로의 결과는 고전컴퓨터로 계산/검증이 쉽지만 에러가 있는 양자컴퓨터로는 계산하기 어렵다. 어찌보면 양자우월성에서 필요했던 회로의 듀얼 버젼인데, 이걸 이렇게 간단히 만들 수 있다는 사실이 신기하군ㅋ