쇼어 알고리즘과 더불어 가장 유명한 양자알고리즘 중 하나인 그로버 알고리즘은 흔히 unstructured database search로도 불린다. 즉, 딱히 조건이 없는 N개의 데이터 중 원하는 데이터값의 존재성/위치를 결정하는데 양자적으로 O(√N)번의 데이터 확인으로 충분하다는 말.
그런데, 이게 얼마나 사실일까? 이 글에서는 Grover algorithm에 대한 설명과 의의를 Quantum Random Access Memory, 즉 QRAM과 아주 살짝 엮어서 얘기하고자 한다. 목차는 다음과 같다.
볼록최적화(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
꽤나 오래 전 쓴 글 암호란 무엇인가? (1)에서 암호학적으로 어려운 문제와 무시할만한(negligible) 사건/확률에 대해 다루었다.
이 글에서는 좀 더 나아가 가장 이상적으로 안전한 암호의 정의, 그렇게 정의하는 합리적인 이유, 그리고 그 한계에 대해 다루겠다. 이 글에서 다루는 암호와 완전한 안전성의 정의는 정보이론(Information Theory)의 아버지로 불리는 클로드 섀넌(Claude Shannon)의 논문 [2]에서 처음으로 제시되었다. 즉, 저 논문 자체가 암호학의 시초격 논문이다. 또한 그 다른 의미에 대해서는 튜링상, 괴델상을 받은 샤피 골드와서(Shafi Goldwasser), 실비오 미칼리(Silvio Micali)의 Probabilistic encryption [3]에서 제시되었다. 이 논문 이전에도 공개키암호에 대한 논의는 있었지만 [3]에서 처음으로 그 안전성에 대한 엄밀한 정의가 논의되었다. 이 공로와 Interactive proof에 관한 논의에 대한 공로로 두 분이 2012년 튜링상을 수상하였다. 놀랍게도 [3]은 골드와서가 대학원생일때 (!) 썼다고 한다 -_-!!
구체적으로, 이 글에서는 다음과 같은 내용들을 다룰 것이다.
물론 이 블로그의 특성상 모든것을 엄밀하게 다루지는 않고, 대략적으로 아이디어를 중심으로 설명한다. 사실 그럴수밖에 없는 부분도 있다 -_-.. 안그러면 몇페이지에 걸쳐 여기 언급되지 않는 대상들을 공부하고 돌아와야함. 아주아주 엄밀한 레퍼런스는 골드리치(Oded Goldreich)의 Foundations of Cryptography [4]를 참조하면 좋다. 내 생각에는 거의 암호학의 성서에 가깝다. 혹은 훨씬 최신의 책은 보네(Dan Boneh)와 쇼프(Victor Shoup)의 책 [5]도 아주 좋다.
더 보기
Pseudorandom Things 