-
Multi Key Homomorphic Encryption - 2
Introduction 저번 글에서, 이어서, 이 논문의 내용을 기준으로 하여, MKHE에 대한 설명을 이어서 진행합니다. 따라서, 저번 글을 읽고 오시는 것이 여러 면에서 도움이 됩니다. 아래에 정리해둔 Notation에 잘 모르겠다는 부분이 있다면, 저번 글과 BFV를 설명한 글들을 읽고 오시는 것을 추천드립니다. Backgrounds Notation 이 글에서는 논문에서 사용한 Notation을 거의 따릅니다. 저번 글에도 썼지만, 다시 정리하면 다음과 같습니다. 먼저, $\textbf{u}, \textbf{v}$처럼 굵은 소문자들은 vector를 나타냅니다. 그리고, $\langle \textbf{u} , \textbf{v} \rangle$는 vector의 innner product를 나타냅니다. real number...
-
Barren Plateaus
이 글에서는 현재 양자 인공신경망이 직면한 가장 큰 문제인 Barren Plateaus에 대해 다룬다. 이 현상은 큐비트가 늘어나면 gradient가 사라져서 학습이 불가능해지는 현상을 말한다. 본 글에서는 이 현상을 소개하고, 수학적으로 기술하고자 한다. 이때 논문 [2]의 내용을 참고하였다. 글의 말미에는 코드를 통해 이 현상이 실재함을 확인한다. 서론 앞으로 당분간의 양자컴퓨터 시대를 NISQ area라고 부르는데, 이 뜻은 적당한 큐빗 수(~1000개)이면서, 에러를 제거할 수 없는 양자컴퓨터를 말한다. 큐빗 수에 제한을 둔 이유는 큐빗 수가 엄청나게 많다면 이들을 사용해서 에러가...
-
Mojo Overview
소개 https://www.modular.com/mojo Mojo는 파이썬의 생태계를 그대로 흡수하면서 C와 비견할 만한 성능과 low-level 기능들까지 갖추는 것을 지향하는 언어입니다. 주로 AI 연구 및 서비스, 데이터 분석 및 처리를 타겟층으로 하여 개발되고 있습니다. Mojo는 Modular라는 기업에서 개발하고 있으며, Co-Founder인 Chris Lattner는 Swift, LLVM, Clang, MLIR를, 또 다른 Co-founder인 Tim Davis는 Tensorflow, Android ML에서 각각 주도적인 역할을 한 것으로 알려져 있습니다. 특히 수십명에 달하는 Modular 팀에 AI Infra, Dev 직군이 무척 많다는 것으로부터 현재 팀의 방향성은 AI 생태계를 개선하는...
-
CDQ Divide and Conquer, Relaxed Convolution
개요 CDQ Divide and Conquer는 중국 프로그래머 CDQ의 이름을 딴 분할정복 기법의 일종입니다. 딱히 이름이 붙을 정도로 거창한 기법은 아니지만, 이후에 다룰 Relaxed Convolution의 이해를 돕기 위해 간단하게 소개하겠습니다. Relaxed Convolution은 CDQ Divide and Conquer를 사용해서 Convolution을 온라인으로 처리하는 알고리즘으로, Online Convolution, Online FFT, Relaxed Multiplication, Divide and Conquer FFT 등의 다양한 이름으로 불리기도 합니다. 이 글에서는 Relaxed Convolution이라는 용어를 일관적으로 사용하겠습니다. 이 글은 FFT의 작동 원리를 이해하지 않고 빠른 다항식 곱셈 라이브러리를 blackbox로 사용하더라도...
-
Interior Point Methods for Maximum Flow
Introduction 2021년 Maximum Flow는 Almost-Linear Time에 풀린다는 결과가 발표되었다 (이는놀랍게도 Minimum cost Flow에 대해서도 성립하는 명제이다). 이에 관련하여 공부할 수 있는 자료로는 Rasmus Kyng의 Advanced Graph Algorithms and Optimization 강의가 있어 이에 대한 스터디를 진행하였다. 이 강의의 Chapter 17인 “Interior point mehods for maximum flow” 를 정리해서 소개하려고 한다. 17장에서는 16장까지 다루었던 테크닉을 통해 undirected graph의 maximum flow 문제를 $\tilde{O}(m^{1.5})$ 시간에 해결하는 알고리즘을 제시한다. 16장까지 많은 정보가 소개된 만큼, 이 글은 self-contained되지 않았다. 그러니 어떤...