-
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되지 않았다. 그러니 어떤...
-
트리 압축의 다른 접근
문제 상황 아래의 문제 상황은 BOJ 16216번 문제에서 만나볼 수 있다. 정점이 가중치가 없는 트리 $T$가 주어진다. $T$는 $N$개의 정점과 $N-1$개의 간선을 가지고 있다. 정점들 가운데, 출발 정점 $v$와, 방문하고 싶은 $K$개의 정점들 $u_1, \cdots, u_K$이 주어진다. 정점 $v$에서 출발해서, $u_1, \cdots, u_K$ 중 1개, 2개, …, K개를 방문하는 가장 짧은 경로의 길이를 각각 구하여라. 아래부터 이 문제에 대한 풀이로 개념에 대한 설명을 시작하려 하니, 아직 이 문제에 대해 고민해보지 않았다면 (스포일러를 피하고 싶다면) 스크롤을...