-
variational quantum algorithm
서론 Keywords: VQC(Variational Quantum Circuit), VQA(Variational Quantum Algorithm), VQE(Variational Quantum Eigensolver), Observable, Hamiltonian 기본적인 양자상태의 표현과 gate가 어떻게 작동하는지는 이해하고 있다는 가정하에 글을 작성하였다. VQC, VQA, VQE 모두 양자 컴퓨팅에서 중요한 개념들이지만 한국어로 제대로 소개된 글이 없기에 이 글을 통해 소개하고자 한다 Quantum Circuit 그림 1. 양자회로의 모습 위 그림 1은 일반적인 양자회로의 모습을 나타내고 있다. 고전 회로에서 1-input gate인 Inverter과 2-input gate인 AND, OR, XOR게이트, 3-input gate인 3-input OR 등등이 있듯이 양자 회로에도 다양한...
-
Faster Matroid Intersection - Part 1
0. Introduction 필자는 Matroid를 소개하는 글 및 Matroid Intersection을 소개하는 글을 2019년에 작성한 바 있다. Matroid Intersection은 해당 글에도 나와 있듯 다양한 문제들을 해결할 수 있는 툴이 되며, 이에 따라 많은 연구가 진행되었다. 특히, 2019년을 기점으로 하여 Matroid Intersection을 어떻게 하면 빠르게 할 수 있을지에 대해 여러 논문의 결과가 발표되기 시작했다. 대표적인 예시로 다음과 같은 4가지 논문이 존재하고, 앞으로는 다음 논문들의 결과에 대해 다룰 것이다. A note on Cunningham’s algorithm for matroid intersection(2019) Faster Matroid...
-
Choice Coordination Problem
개요 문제 상황 $n$개의 프로세서가 존재한다. 각 프로세서는 $m$개의 선택지 중 하나를 선택해야 한다. 그런데, 프로세서들이 완전히 비동기적으로 작동한다. 프로세서가 공유하는 일관적인 시계 (global clock)이 존재하지도 않을 뿐더러, 프로세서의 응답 속도에 대한 가정을 할 수도 없다. 이러한 상황에서 모든 프로세서가 동일한 선택으로 합의하도록 하는 알고리즘이 필요하다. 인격을 부여해 이러한 비유 상황을 만들어낼 수 있다: $n$명의 관광객이 존재한다. 그들이 머무는 여행지는 $m$개의 방으로 이루어져 있다. 이 때 관광객 모두가 방 하나에 모일 수 있도록 행동 규약을...
-
Variation of Mo's Algorithm 2
안녕하세요 jthis 입니다. 이 글에서는 Variation of Mo’s Algorithm 1에 이어 또다른 Mo’s Algorithm의 variation에 대해 소개하겠습니다. Mo’s Algorithm with Update Mo’s Algorithm은 쿼리 문제를 효율적으로 해결하는 알고리즘입니다. 하지만 일반적인 Mo’s Algorithm은 업데이트 연산을 처리할 수 없어, 해당 제약으로 인해 사용하기 어려운 경우가 있습니다. 이런 상황에서 사용할 수 있는 3D Mo’s Algorithm이라고도 불리는 Update Mo’s Algorithm에 대해 소개하고자 합니다. 예를 들어, 쿼리문제를 생각해 봅시다. 이 문제에서는 다음과 같은 연산이 주어집니다: 1 i x: $A_i$를 x로...
-
그래프 채색 개론
서론 (무향) 그래프 $G$는 정점 집합 $V$와 간선 집합 $E$ 로 이루어진 구조입니다. 간선은 두 원소를 잇는 (순서가 없는) 선입니다. 여기서 그래프의 정점을 색칠한 다는 것은, 간선의 양 끝이 다른 색이 되도록 색칠한다는 것입니다이 게시글에서는 그래프 색칠에 대한 다양한 주제를 다룹니다. 해당 주제는 그래프 색칠에 대한 시각을 늘려줄 것이라고 생각합니다. 다룰 주제는 다음과 같습니다. 주제 이분그래프 색칠 그리디 색칠, $(\Delta+1)$색 정리, $6$색 정리 $5$색 정리, $4$색 정리, Kempe Chain, $\Delta$색 정리 채색 다항식 표기법 이...