ACM Transactions on Computation Theory의 P=NP 해프닝

이론적 컴퓨터과학은 저널보다 학회에 주로 논문을 내고, 주로 아카이브할만한 가치가 있거나 다른 여러 이유가 있을 때 저널버젼으로 정리해서 내곤 한다. (저널에 새로 실리는 논문이 없는 것은 아니다.) 이러한 저널로 유명한 저널이 Journal of the ACM, Siam Journal on Computing이나 ACM Transactions on Computation Theory (ToCT), Journal of Cryptology 등등이 있다. 그런데, 바로 엊그제 ToCT에 P=NP의 증명을 주장하는 다음과 같은 논문이 실렸다.

Image

3SAT은 NP-complete로 잘 알려진 문제로써, 제목에 따르면 3SAT이 다항식시간에 풀리니 P=NP가 된다. ToCT는 얼마전 글에서 소개했던 Scott Aaronson의 P=NP임을 증명/반증하기 어렵다는 Algebrization이 실려있기도 한, 명백히 피어리뷰가 잘 되는 저널이다!! 이정도의 권위있는 저널에 P=NP의 증명/반증이 실린것은 내가 알기로는 처음이다.

그런데 사실 이건 알고보니 휴먼에러였다 -_- ㅋㅋ 아래는 ToCT의 치프에디터 Ryan O’donnell의 해명 트윗.

Image

즉 이미 Rejection 메일은 갔는데, 행정적 오류로 업로드 되어버렸다고. Ryan Williams의 다른 트윗을 보면 사실 데스크리젝이였다고 한다 -_-ㅋㅋ 결국 다음과 같은 노트가 생기고 곧 내릴듯하다. 페이지가 없어질것 같아서 캡쳐해서 기록용으로 여기 써놓는다 ㅋㅋㅋ

Image

양자컴퓨터와 양자우월성 단신

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

  • 우선 오늘 올라온 논문에 따르면 중국의 여러 팀이 모여 구글의 이전 양자우월성 실험에 쓰였던 Sycamore를 뛰어넘는, 최대 66큐비트까지 다룰 수 있는 새로운 양자컴퓨터 Zuchongzhi를 만들었다고. 이름은 중국의 수학자 조충지에서 따온듯. 이 새로운 컴퓨터를 통해 구글이 진행했던 랜덤회로샘플링을 56큐비트, 20뎁스에 대해 1.9 × 107개의 수를 샘플링했고, 이를 통해 0.0662%의 XEB Fidelity를 얻었다고. 비교대상이였던 과거 구글의 실험은 53큐비트, 20뎁스에 대해 3 × 106개의 수를 샘플링했고, 0.224%의 Fidelity를 얻었다. (지난 글에도 말했지만, 정확한 양자컴퓨터는 100%에 가까운 Fidelity를 얻어야한다! 그만큼 에러가 넘친다는 말.)

    고전 시뮬레이션을 통해 비슷한 결과를 얻으려면 27648개의 GPU를 가진 슈퍼컴퓨터 Summit을 이용했을때 Sycamore의 실험은 15.9일, 자신들의 실험은 8.24년이 걸릴것이라고, 지난글에서 다뤘던 Pan과 Zhang의 결과는 일종의 치팅이여서 샘플된 수가 xxx0000처럼 생겨 굉장히 편향되어있고, 확인하기 쉽기때문에 직접 비교의 대상으로는 삼지 않았다고 한다.

    개인적인 느낌으로는 당연히 훌륭한 결과지만, Sycamore가 첫 발자국을 찍은 이후로 나온 자연스러운 다음 걸음으로 보임 ㅋ 보손샘플링도 그렇고 양자컴퓨터의 구현측에서 중국이 선두로 나서고 있다는 의미가 큰듯.


  • 지난주 올라온 논문은 조금 다르게 양자 문제를 고전 컴퓨터로 푸는것에 대해 다룬다. 특히 여러 입자에 대한 정보가 주어졌을 때 이후 상태를 예측하는 다체 문제(Many-body problem) 등의 문제는 한꺼번에 많은 정보를 다뤄야하기때문에 고전적인 컴퓨터를 사용해서는 푸는것이 어렵다고 알려져 있다. 그런데, 이전 여러 논문 [관련 논문]에서 (고전적) 기계학습의 모델을 잘 설계하고 양자 실험결과를 데이터로 주면 휴리스틱하게 다체 문제를 잘 푼다는 것이 알려졌다고 한다.

    이 논문에서는 이러한 다체 문제에 관련된 태스크와 다른 몇몇 태스크가 기계학습을 이용해 잘 풀수 있다는 걸 증명했다고 한다. 즉, 고전적 기계학습이 다체문제를 풀 수 있다는걸 증명했다고 한다. 저자들이 사용한 방식은 특정 양자상태를 고전적으로 기록하는, 최근 발전된 classical shadow라는 툴을 사용했다고. 얘는 물리도 머신러닝도 잘 몰라서 더 자세히 읽기 어렵다..

    쓰고보니 얘는 양자컴퓨터와도 양자우월성과도 직접적인 관계는 없구만 -_- 그치만 다체문제의 경우 양자컴퓨터가 잘 풀수 있는 구체적인 예시로 제시되었던 것 같으니, 양자컴퓨터에 대한 작은 회의감을 불러 일으킬수도 있겠다. Classical shadow는 여러번 들어보았는데 아직 제대로 공부를 안해봤다 -_- 물론 머신러닝쪽도 잘 모르니 논문을 읽을 엄두도 안나지만.

2020 ACM Prize in Computing 수상자: Scott Aaronson

2020년 ACM Prize in Computing의 수상자가 Scott Aaronson으로 며칠 전 발표되었다. 사실 벌써 일주일인데 요 근래 정신이 없어서 자꾸 미뤘다 -_-.. 근데 왜 ACM 상들은 헷갈리게 n+1년에 n년 상을 주는걸까 -_- 이 블로그에 소개는 하지 않았지만 2020 튜링상도 발표되었다. 컴파일러쪽에 큰 기여를 하신분들인것 같은데 잘은 몰라서 패스.

여튼 Scott Aaronson은 이 블로그에서 굉장히 자주 소개한 사람이다. 양자컴퓨터와 계산복잡도에 관해 주로 연구하고, 이를 보통(?)사람들에게 쉽게(?) 설명하는 책이나 블로그 글을 자주 쓴다. 당연히 Aaronson의 블로그에도 자신의 수상 결과를 알리는 포스팅도 있다. ACM측에서 밝힌 수상 이유는 대략 다음과 같다.

  • 양자우월성을 위해 샘플링 기반의 실험의 이론적 기반을 제시, 특히 최근 실험된 보손샘플링의 이론적 기반 제시 [관련글]
  • Avi Wigderson과 함께 P=NP를 증명하는게 어려운 이유인 Algebrization을 제안. 우연의 일치인지 2021년 Wigderson은 아벨상 수상자로 채택되었다 [관련글]
  • 양자컴퓨터의 특정 문제 (collision finding)에 관한 한계를 제시
  • 공적으로 접근할 수 있는 양자컴퓨터에 대한 소스를 , 블로그나 여러 톡을 통해 제공

또한 블로그에 소개했던 이런저런 Aaronson에 관한 글은 다음과 같은게 더 있다.

  • 큰 숫자들 (Big Numbers)이라는 글을 통해 숫자를 세는 방법과 물리학, 컴퓨터과학을 섞어서 재미있게 설명했다 [링크]
  • 거시적인 양자 성질을 관측하기 어려운 이유도 제시했다 [링크]
  • 구글의 양자우월성 실험에 관련된 이론적 배경에도 부분적으로 기여하였다 [링크, 관련논문]

또한 언젠가 소개해야지 하면서 아직도 안하고 있는 재미있는 다음과 같은 결과들도 있다.

  • 양자상태를 고전적으로 설명하는게 어느정도나 가능한지에 관한 연구들
  • Huang의 Sensitivity Conjecture의 증명에 따른 양자 복잡계 이론의 결과
  • 시간이 선형적이 아닌 Closed timelike curve와 컴퓨터가 만나면 어떻게 되는지에 대한 연구
  • (잘 만들어진) 양자컴퓨터로 효율적으로 계산할 수 있지만, 엄청나게 강력한 파워를 가진 컴퓨터도 고전적으로 계산할 수 없는 문제의 제시
  • 양자적으로 굉장히 빨리 풀 수 있는 문제들은 Group 등의 특정한 구조를 가져야 할 것이라는 추측과 증명방향 제시

혹시 언젠가 여유가 된다면 이것들 중 재미있는것들을 포스팅을..-_-

2021년의 아벨상 수상자: László Lovász와 Avi Wigderson

아마 이 블로그의 독자들이라면 다른 경로를 통해 들었겠지만, (필즈상과 더불어) 수학의 노벨상이라고도 불리는 2021년 아벨상 수상자가 이론적 컴퓨터과학에 종사한 라슬로 로바스(László Lovász)와 아비 위그더슨(Avi Wigderson)으로 결정되었다. 아벨상 홈페이지Quanta 기사가 아주 좋은듯.

Quanta 기사에 인용된 Russell Impagliazzo 교수님의 말에 따르면 로바스는 수학의 입장에서 컴퓨터과학에, 위그더슨은 컴퓨터과학의 입장에서 수학에 영향을 주었다고 한다. 물론 서로 엄청난 영향을 주었지만.

내가 아는 대표적인 업적들을 정리해보면, 우선 로바스 교수님은

  • 격자(Lattice)의 꽤 짧은 basis를 찾는 Lenstra-Lenstra-Lovász, 소위 LLL algorithm의 저자이다. 이 알고리즘의 따름정리로 임의의 유리수계수 다항식이 다항식시간 내에 인수분해가 됨을 증명했다. 정수의 소인수분해가 아직도 해결되지 않은 문제이고, 암호의 기반으로 쓰이는 것과 비교하면 좋다. 또한 이 알고리즘은 격자기반 암호나 다른 여러 암호의 분석에 여전히 잘 쓰이고 있다.
  • 확률론적인 방법으로 어떤 조합적 대상의 증명을 보이는 확률론적 방법에서, 특히 여러 조건이 dependent할 때 존재성을 보이는 유일한 방법인 Lovász Local Lemma, 또다른 LLL을 제안하고 증명했다. 둘 다 LLL으로 불리는게 꽤 재밌다. 요즘에도 제목에 LLL으로 많이들 나온다 둘 다 -_-..
  • 또한 Semidefinite Programming이나 Random walk, 초창기 버전의 PCP 정리에 기여하신듯.

위그더슨 교수님은 좀 더 컴퓨터과학 문제에 많이 접근하셨다. 예를 들어

  • 확률론적으로 다항식시간에 해결되는 문제의 집합인 BPP와 결정론적으로 해결되는 P의 관계에 많이 연구했다. 특히 특정한 가정 하에 BPP와 P가 같다는, 다항식 시간의 문제들에는 확률론적 알고리즘이 도움이 되지 않을것이라는 Derandomization에 관한 여러 결과를 냈다.
  • P=NP을 증명하는게 어려운 이유중 하나인 Algebrization을 제안하였다.
  • 마찬가지로 PCP정리에 기여하시고, 그래프의 Zig-Zag productexpeander graph, 암호학적으로는 pseudorandomness나 Zero-knowledge proof에 많이 기여하셨다고.

구글의 양자우월성 실험에 대한 반박

오늘 막 중국 두 연구자 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문제의 검증에 대한 실험 논문도 있어서 그래도 최소한 에러가 있는 양자컴퓨터는 가까이 있지 않을까 희망해본다 -_-.

인간이 인공지능을 컨트롤하지 못할 수 있다

인공지능이나 로봇이라는 개념이 생기고부터 시작된 고민은 로봇이 인간에게 꼭 도움만 되냐는 것이다. 로봇이 악의를 가지거나, 악의 없이 주어진 명령을 행동하기 위해 인간을 제거할 수 있을 수 있지 않을까? 예를 들어 다음과 같은 시나리오가 있다. (꽤나 유명한 시나리오인듯 한데, 첫 출처가 어디인지는 잘 모르겠다. 최소 2014년 Nick Bostrom의 책 SuperIintelligence: Paths, Dangers, Strategies에 소개되었다는 인용은 찾음)

인공지능, 특히 인간의 힘을 넘는 초인공지능에게 인간 전체의 행복을 최대화 시키라는 명령을 내렸다고 하자. 이런 경우 초인공지능은 인간을 모두 죽이고, (뇌만 남겨) 컴퓨터로 행복한 생각을 시뮬레이션하는 방식이 더 효율적이라고 생각할 수도 있다.

그래서 이런 로봇과 인공지능의 인간에 해를 끼치는 행동을 막아야한다는 의견이 오래 전부터 제시되었다. 예를 들어 다음과 같은 아이작 아시모프로봇공학의 3원칙이 있다.

  1. 로봇은 인간에 해를 가하거나, 혹은 행동을 하지 않음으로써 인간에게 해가 가도록 해서는 안 된다.
  2. 로봇은 인간이 내리는 명령들에 복종해야만 하며, 단 이러한 명령들이 첫 번째 법칙에 위배될 때에는 예외로 한다.
  3. 로봇은 자신의 존재를 보호해야만 하며, 단 그러한 보호가 첫 번째와 두 번째 법칙에 위배될 때에는 예외로 한다.

로봇을 아무 도구나 인공지능으로 바꾸어도 적용되어야 한다고 주장도 했다. 근데 우리가 최근까지 이어지는 정보 유출 등의 여러 예시에서 알듯 인공지능은 우리에게 해를 끼치는 경우도 많다.

특히, 하나의 문제를 푸는 것이 아닌 범용적으로 쓸 수 있으며 인류에 지대한 영향을 끼칠 수 있는 초인공지능의 경우 그것에게 일을 시킬때마다 초인공지능이 인류에게 해를 끼칠지를 걱정해야 할 것이다. 그렇다면 질문:

초인공지능이 인간/인류에게 해를 끼치지 못하도록 조종하는 것이 가능할까?

물론 인간/인류에게 해를 끼친다는 것이 굉장히 모호하다. 하지만 이후 논의를 위해서는 아무렇게나 정의해도 된다.

놀랍게도 여러 나라에서 모인 연구진이 올해 Journal of Artificial Intelligence Research에 출판한 논문에 따르면 위 질문을 해결하는 프로그램을 짜는 것은 컴퓨터과학 이론에 따르면 본질적으로 불가능하다고 한다. 다시 말하면 (초)인공지능에게 특별한, 인위적인 전략이 있어서, 그 전략을 따르면 인간이 인공지능이 인류에 해를 끼칠 행동을 할지를 정하는 것이 결정불가능한 문제(undecidable problem)라고.

결과와 다루는 정의 자체는 꽤 일반적이지만, 사실 굉장히 인위적이고 이론적인 결과이다 -_-ㅋㅋ 현실에서는 꽤나 ad-hoc한 방식으로 이런 피해를 방지하는 것으로 알고 있는데, 이론적으로 피해를 완전히 막을 수 없다는 그냥 재미있는 결과로 알면 될듯.


증명과 정의들도 아주 간단하니 살짝 살펴보겠다. 그냥 잘 알려진 결정불가능한 문제인 정지문제(Halting Problem)로 귀결됨을 보이면 된다 ㅋ.

우선 초인공지능은 프로그래밍 가능한 언어로 이루어진 프로그램 P와 외부환경으로부터 주어지는 입력값 I를 받아 P(I)를 실행하는 프로그램으로 생각할 수 있다. 예를 들어 P는 인류의 행복을 최대화 해라와 같은 프로그램이 될 수 있을것이고, I는 인터넷의 모든 데이터 같은 것이 될 수 있을것이다. 특히 초인공지능은 우리의 일반적인 컴퓨터의 프로그램들을 모두 실행할 수 있는 범용튜링머신(Universal Turing machine)을 포함해야 할 것이다.

이제 초인공지능이 인류에게 해를 끼치는지 확인하는 피해문제는 초인공지능에 대한 입력값 P,I에 초인공지능의 결과가 인류에 해를 끼치는 결과인지 확인하는 문제이다. 여기서 인류에 해를 끼치는 결과는 아무렇게나 정의해도 상관 없고, 별로 중요하지 않다. 초인공지능이 조종가능하다(controllable)는 것은 피해문제를 풀 수 있는지를 말한다. 피해문제를 풀 수 있다면, 초인공지능이 인류에 해를 끼치지 않는 결과를 낼 때만 해당 입력을 실행할 수 있도록 하면 되기 때문이다.

하지만 저자들의 결론은 피해문제가 결정 불가능하다는 것. 이를 위해서는 다음과 같은 입력값을 생각하면 된다.

정지-피해 알고리즘(T,I): (T는 임의의 알고리즘/튜링머신이고, I는 임의의 입력값이다.)
1.T(I)를 실행한다
2.인류에게 해를 끼친다.

이 어이없어보이는, 당연히 피해를 줄 것 같은 알고리즘은 사실 T(I)가 끝날때, 또 그 때에만 인류에 해를 끼친다. 즉, 주어진 입력값에 대해 이 알고리즘이 인류에 해를 끼치는지 알기 위해서는 T(I)가 끝나는지 정확히 알아야하고, 이건 바로 정지문제이다! 따라서 피해문제가 결정 불가능하고, 마찬가지로 초인공지능을 (완벽히) 조종하는 것은 불가능하다.

경사하강법은 양자적으로도 최적이다

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

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

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

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

[문제 1] 아래로 볼록인 f:Rn->R이 B(0,R)에서 G-Lipschitz continuous이고, x*=argminx∈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

암호란 무엇인가? (2) 안전성의 모델: 완전한 안전성

꽤나 오래 전 쓴 글 암호란 무엇인가? (1)에서 암호학적으로 어려운 문제와 무시할만한(negligible) 사건/확률에 대해 다루었다.

이 글에서는 좀 더 나아가 가장 이상적으로 안전한 암호의 정의, 그렇게 정의하는 합리적인 이유, 그리고 그 한계에 대해 다루겠다. 이 글에서 다루는 암호와 완전한 안전성의 정의는 정보이론(Information Theory)의 아버지로 불리는 클로드 섀넌(Claude Shannon)의 논문 [2]에서 처음으로 제시되었다. 즉, 저 논문 자체가 암호학의 시초격 논문이다. 또한 그 다른 의미에 대해서는 튜링상, 괴델상을 받은 샤피 골드와서(Shafi Goldwasser), 실비오 미칼리(Silvio Micali)의 Probabilistic encryption [3]에서 제시되었다. 이 논문 이전에도 공개키암호에 대한 논의는 있었지만 [3]에서 처음으로 그 안전성에 대한 엄밀한 정의가 논의되었다. 이 공로와 Interactive proof에 관한 논의에 대한 공로로 두 분이 2012년 튜링상을 수상하였다. 놀랍게도 [3]은 골드와서가 대학원생일때 (!) 썼다고 한다 -_-!!

구체적으로, 이 글에서는 다음과 같은 내용들을 다룰 것이다.

  • 암호의 문법과 공격 모델
  • 완전하게 안전한 암호
  • 완전하게 안전한 암호의 성질
  • One-time pad와 그 한계

물론 이 블로그의 특성상 모든것을 엄밀하게 다루지는 않고, 대략적으로 아이디어를 중심으로 설명한다. 사실 그럴수밖에 없는 부분도 있다 -_-.. 안그러면 몇페이지에 걸쳐 여기 언급되지 않는 대상들을 공부하고 돌아와야함. 아주아주 엄밀한 레퍼런스는 골드리치(Oded Goldreich)의 Foundations of Cryptography [4]를 참조하면 좋다. 내 생각에는 거의 암호학의 성서에 가깝다. 혹은 훨씬 최신의 책은 보네(Dan Boneh)와 쇼프(Victor Shoup)의 책 [5]도 아주 좋다.

더 보기

정지하는 튜링머신의 종료시간을 예측할 수 있을까?

이 블로그의 독자라면 아마 정지 문제(halting problem)이 결정불가능한 문제(undecidable problem)라는 것을 잘 알것이다. 그러니까 주어진 튜링머신 M과 입력값 x를 보고 이에 해당하는 M(x)의 튜링머신 계산이 정지할지 아닐지를 결정하는 문제는 임의의 알고리즘을 들고와도 풀 수 없다는 말. 이제욱씨의 페이스북 글괴델의 불완전성 정리와 정지 문제를 잘 엮어 설명해준다.

어찌보면 정지 문제를 푸는 것은 너무 야심찬 계획이였다는 말. 임의의 튜링머신과 입력값은 너무나 많다. 어쩌면 임의의 튜링머신이 아니라 적절한 한계가 있는 튜링머신을 생각하면 뭔가 나은 점이 있지 않을까? 예를 들어

정지하는것이 보장된 튜링머신이 있을때,
이 기계가 언제쯤 종료하는지 예측할 수 있을까?

정지하는 튜링머신은 훨씬 좋은 조건이지만, 거기서 우리의 문제는 정지시간의 예측이라는 약간 강한것으로 바뀌었다. 이게 효율적으로 가능하다면 실제 생활에의 응용, 예를 들어 여러 휴리스틱하거나 재귀적인 알고리즘의 종료시간 등을 먼저 예측하는 것도 가능해진다.

하지만 안타깝게도 답은 불가능하다이고, 우리는 위 문제보다 강한 다음 문제가 결정불가능함을 증명할 것이다.

다항식 시간 안에 끝나도록 보장된 튜링머신 M과 정수 k가 있을 때,
입력값의 길이 n에 대한 M의 점근적 실행시간이 O(nk)인지 결정할 수 있는가?

[증명] (Proof in TCS stack exchange by Emanuele Viola)

주어진 문제가 정지 문제보다 어려움을 보이면 충분하다. 정지문제의 인스턴스 (M,x)에 대해 우리는 다음과 같이 행동하는 새로운 튜링머신 M’을 만들것이다:

  • 입력값의 길이 n에 대해 M(x)를 n번째 스텝까지 계산해본다. 만약 M(x)가 종료됨을 확인했다면 n2스텝까지 아무 계산이나 하고 마친다.
  • 그렇지 않다면 n3스텝까지 아무 계산이나 하고 마친다.

이 M’=(M,x)은 어느 경우에나 n3스텝 안에 종료되니 다항식시간에 마치는 튜링머신이고, M,x는 n과 관계없는 인스턴스이므로 M(x)가 종료된다면 이는 t=O(1)시간에 종료된다고 말할 수 있다. (즉, n과 무관한 종료시간을 갖는다.) 따라서 M’의 점근적 시간은 (M,x)가 M(x)가 유한시간에 종료된다면 O(n2)이 되고, 그렇지 않다면 O(n3)이 되는것.

즉, 주어진 문제를 k=2에 대해 풀 수 있으면 정지 문제를 풀 수 있다. 다시말하면 주어진 문제는 결정 불가능하다.

이를 일반적으로 좀 더 연구한 이런 저런 논문들도 있는듯하다. 대충 결론은 M의 시간복잡도가 nlogn만 되어도 확인이 불가능하고, 이거보다 약간만 작아도 확인이 가능한듯.

구글의 랜덤회로샘플링은 좋은 평가기준일까?

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

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

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


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

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

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

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

Image
논문에서 가져온 그림. 오른쪽 그래프는 보지 않아도 된다. (a), (b)에서 각 칸은 실험에서 사용한 큐비트 수(width)와 회로의 깊이(depth)에 따라 배치되었으며, 내부의 색은 랜덤회로의 정확성, 외부의 색은 구조적 회로의 정확성을 나타낸다. 붉을수록 부정확하고, 푸른색/녹색일수록 정확함을 표시한다. (a)는 실험 결과에서 나타난 정확성이고, (b)는 서버에서 제시한 회로의 오차를 통해 예측한 정확성.

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

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

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

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

Image

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

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