-
Learning shallow quantum circuits
올해 1월 18일, Learning shallow quantum circuits라는 제목의 연구가 arxiv에 올라왔고, 가장 큰 양자정보 학회인 QIP에서 해당 논문을 가지고 발표까지 진행되었다. 이 연구는 양자 회로를 학습하던 방식을 바꿔놓을 가능성이 있는 연구이고, 어쩌면 Quantum Machine Learning(QML)의 미래 자체에 영향을 줄 수도 있을것 같아 보인다. 굉장히 좋은 아이디어도 얻어갈 것이 많은 연구라고 생각하여서 공유해보고자 한다. 요약 이 논문에서 해결하고자 하는 문제는 두 가지이다. Unknown unitary $U$에 여러 입력으로 여러 번 접근할 수 있을 때, 최대한 가까운 unitary...
-
양자컴퓨팅으로 PS하는법
제목을 조금 자극적이게 “양자컴퓨팅으로 PS하는 법”이라고 설명했지만, 아직 일반적인 PS를 하는 데 양자컴퓨터를 사용하는것은 어렵다. 그래도 그나마 PS스러운 max cut 문제를 양자컴퓨터로 해결하는 방법을 최대한 쉽게 소개하고자 한다. 나중에도 양자컴퓨터를 사용한 소개할만한 알고리즘이 있다면 소개해볼 계획이다. Max cut 문제란? Max cut 문제는 주어진 그래프를 두 집합으로 잘 분리하여 두 집합 사이를 연결하는 간선의 수를 최대화하는 문제이다. 그림 1. Maxcut 예시.흰색과 검은색 정점 집합으로 위와 같이 분리하면 둘 사이를 연결하는 간선(빨간색)이 5개로 최대가 된다. 따라서 이...
-
Barren Plateaus
이 글에서는 현재 양자 인공신경망이 직면한 가장 큰 문제인 Barren Plateaus에 대해 다룬다. 이 현상은 큐비트가 늘어나면 gradient가 사라져서 학습이 불가능해지는 현상을 말한다. 본 글에서는 이 현상을 소개하고, 수학적으로 기술하고자 한다. 이때 논문 [2]의 내용을 참고하였다. 글의 말미에는 코드를 통해 이 현상이 실재함을 확인한다. 서론 앞으로 당분간의 양자컴퓨터 시대를 NISQ area라고 부르는데, 이 뜻은 적당한 큐빗 수(~1000개)이면서, 에러를 제거할 수 없는 양자컴퓨터를 말한다. 큐빗 수에 제한을 둔 이유는 큐빗 수가 엄청나게 많다면 이들을 사용해서 에러가...
-
QGAN in Finance
Keywords: GAN, QGAN, copula, finance data 아이온큐 공식 블로그에 소개되어 있기도 하고, 2022년 11월에 실린 논문인데 아직 한국에 소개하는 글이 없어서 블로그 글로 작성한다. arxiv엔 2021년에 올라왔는데 왜이리 늦게 실렸는지 모르겠다. PRX저널에 실으려고 꽤 오래 존버했나..? 서론 이 논문은 특정한 결합확률 분포를 양자 생성기 (QGAN)으로 모델링하는것이 주제입니다. 꽤 흥미로운 접근법을 많이 보여주고 있어서 소개하고자 하였습니다. 이 논문에서 얻어갈만한 아이디어는 아래와 같습니다. 생성 문제를 probability integral transform을 통해 uniform distribution으로 바꾸고, 이걸 생성한 뒤 역변환 하는...
-
symmetry in variational quantum algorithm
서론 Keywords: VQC(Variational Quantum Circuit), VQA(Variational Quantum Algorithm), VQE(Variational Quantum Eigensolver), Observable, Hamiltonian 기본적인 양자상태의 표현과 gate가 어떻게 작동하는지는 이해하고 있다는 가정하에 글을 작성하였다. Variational quantum cirquit, variational quantum algorithm등에 대한 개념이 생소하다면 이전 글을 참고하길 바란다. 이번 글에서는 Variational Quantum Algorithm(VQA) 을 굉장히 효율적으로 사용할 수 있게 해주는 방법 중 하나를 다뤄보고자 한다. 바로 symmetry를 사용하는 것이다. 저번 글에서는 Parameterized Quantum Cirquit(PQC)와 Variational Quantum Algorithm(VQA)를 다루었다. 하지만 기존의 단순한 PQC기반 VQA는 한계가 존재한다. 이번...
-
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 등등이 있듯이 양자 회로에도 다양한...
-
bound entanglement
서론 양자 얽힘 (quantum entanglement)는 크게 두 가지로 분류할 수 있다. 대부분의 entanglement는 free enntanglement이며, 일부가 bound entanglement이다. 특히, bound entanglement는 아직 한국에 잘 소개되지 않았으며, 한국어 명칭도 정착되지 않은 개념이다. 그리고 bound entanglement와 깊게 관련된 LOCC(Local Operations and Classical Communication)도 일반 사람들을 대상으로 많이 소개되지 않아 이에 대해 이번 글에서 간단히 소개해 보고자 한다. 양자 상태부터 설명을 시작해서 bound entanglement까지 설명하기에는 너무 긴 분량이 될 것이므로 초반부는 간략하게 설명하였으니 이 글을 읽고 흥미가 생긴...
-
Quantum Graph
서론 그래프는 수학과 컴퓨터 과학에서 굉장히 중요하게 다루는 내용이다. 알고리즘 문제풀이만 하더라도 그래프와 관련된 알고리즘이 수 없이 많다. 이러한 그래프 이론은 최단 경로, 효율적인 네트워크 구조, 데이터 분석 등에 폭넓게 응용된다. 다들 기존에 자주 보던 그래프 (고전 그래프)에 대해서는 어느정도 익숙할 것이라 생각한다. 양자 컴퓨팅 분야가 발전하면서 고전 컴퓨팅에 존재하던 다양한 개념들을 양자 컴퓨팅으로 옮겨오는 연구들도 많이 진행되었다. 이는 한 학문이 발전하면서 흔히 보이는 현상이다. 본 글에서는 Graph의 개념을 옮겨온 Quantum Graph에 대해 소개해 보고자...
-
Introduction to Classical Shadow
Quantum state tomography 서론 양자컴퓨팅에는 다양한 양자 알고리즘이 존재한다. 하지만 양자컴퓨터의 결과를 해석하는 법은 computational basis를 기준으로 측정하는 것 뿐이다. Grover algorithm이나 Quantum Phase Estimation 알고리즘 등의 알고리즘은 결과 큐빗이 0인지 1인지 관측하는 것 만으로 충분하다. 하지만 임의의 n-qubit 양자상태는 $2^n \times 2^n$의 복소 행렬로 표현된다. 따라서 원래의 상태 행렬 자체를 알아내는 것 또한 활발하게 연구되었다. 이를 Quantum state tomography라고 한다. 하지만 n-qubit의 양자상태 $\rho$를 알아내는 것은 최소한 O($rank(\rho)2^n$)번의 측정이 필요한 것이 증명되어 있다. 10-qubit...
-
Using linear-optical quantum computing model to prove #P-hardness of Permanent
Introduction 지난 달 작성한 글과, 최근 진행하는 project-hardness 스터디를 진행하면서 $\sharp P$-hardness에 대한 내용을 자주 다루었습니다. 하지만 $\sharp P$라는 complexity가 고안된 근본적인 이유와도 같은 permanent에 대해서는 언급하지 않았습니다. Shortest Even Cycle Problem을 다룬 문제에서 지나가듯 이야기했지만 길게 이야기하지 않았죠. 실제로 이 문제를 해결한 Valiant(1979)의 논문은 3000회가 넘는 인용수를 기록했으며, Permanent를 비롯한 수많은 복잡도 이론에 대한 공헌으로 Valiant은 튜링상까지 수상하게 됩니다. 이런 위대한 업적에도 불구하고 Valiant이 어떤 아이디어로 Permanent의 hardness를 증명했는지는 비교적 알려져 있지 않은데, 문제...
-
SABER: Mod-LWR based KEM
1. Introduction 저번 글에서는 양자 컴퓨터와 Post Quantum Cryptography에 대해 다루었습니다. 이번 포스팅에서는 어떤 암호 시스템을 다루어볼까 고민하다가 NIST에서 진행하는 PQC contest의 3라운드 7개의 후보 중에서 5개가 Lattice-based인 만큼 Lattice를 기반 문제로 사용하는 SABER 암호의 동작 원리, 장단점을 소개해보려고 합니다. 저도 불과 한달 전까지만 해도 PQC에서 사용하는 Lattice에 대해 아주 얕은 지식만을 가지고 있었기 때문에 Lattice를 잘 모르더라도 글을 이해하는데 큰 어려움은 없습니다. 다만 Group Theory가 많이 쓰이기 때문에 Group Theory에 대한 이해가 약하시면 내용을...
-
Post-Quantum Cryptography
1. Introduction 양자 컴퓨터가 언제 상용화가 가능할지는 예측이 힘들지만 양자 컴퓨터의 개발 이후 영향을 받을 분야는 굉장히 많고 그런 분야들에서는 관련 연구를 활발하게 진행하고 있습니다. 한편 양자 컴퓨터의 이론적 개념은 양자 역학과 컴퓨터 과학에서의 계산 이론 분야의 깊은 이해를 요구하기 때문에 (저를 포함한) 많은 사람들은 양자 컴퓨터의 개념을 매우 피상적으로 알고 있거나 기능을 잘못 이해해서 양자 컴퓨터가 상용화되면 모든 암호 체계가 붕괴된다고 착각하는 경우가 종종 있습니다. 이번 글에서는 양자 컴퓨터 시대를 대비하는 Post-Quantum Cryptography에 대해...
-
양자 컴퓨팅 - Surface Code
최근 양자 컴퓨팅의 error detection 및 correction에 사용되는 surface code의 기초를 잘 설명한 논문인 Surface codes: Towards practical large-scale quantum computation을 접했습니다. 이 포스트를 통해 양자 컴퓨팅에서 어떻게 error detection을 진행하고, surface code가 어떤 개념인지 설명하고자 합니다. 배경 지식 Shor’s Algorithm이나 Grover’s Algorithm 등의 양자 알고리즘이 개발되며 양자 컴퓨팅에 대한 관심이 커졌습니다. 2020년 현재 IBM Q Experience나 Amazon Braket, Microsoft QDK 등으로 양자 컴퓨팅 프로그래밍 언어를 사용할 수도 있습니다. 그러나 이런 시스템이 물리적인 양자 체계와...
-
양자 컴퓨팅 입문 (2) - Grover's Algorithm
Grover’s Algorithm은 정렬되지 않은 데이터베이스에 있는 $N$개의 항목 중 특정한 조건을 만족하는 항목을 $O(\sqrt{N})$에 찾는 알고리즘입니다. 고전 컴퓨팅에서 이 문제를 해결하려면, 간단하지만 느리게 갈 수밖에 없습니다. 전수 조사(brute force)가 유일한 해결책입니다. 당연히 시간 복잡도는 $O(N)$이며, 랜덤하게 셔플해서 순서를 바꾼다 해도 마찬가지입니다. 그리고 이보다 더 나은 시간복잡도로 찾을 수는 없습니다. Grover’s Algorithm은 이 시간복잡도를 $O(\sqrt{N})$으로 낮추는데 성공하였고, 이 시간복잡도가 최적이라는 것이 알려져 있습니다. 또다른 유명한 양자 알고리즘인 Shor’s Algorithm과는 달리 알고리즘 자체가 간단하면서도 심도 있기 때문에...
-
양자 컴퓨팅 입문 (1) - 개요
“양자(quantum)를 이용해서 상태를 저장하는 컴퓨터를 만들면 어떨까?” 이 허무맹랑할 수도 있는 1981년 리처드 파인만에 의해 제기되었습니다. 양자 컴퓨팅은 암호학 쪽에서 1997년 Shor가 다항 시간에 인수분해를 할 수 있는 양자 알고리즘을 발견하면서 각광받기 시작했습니다. 지금까지도 고전 컴퓨팅으로 인수분해를 다항 시간 안에 할 수 없고, 또 RSA 같은 많은 암호체계가 인수분해의 수학적 어려움(infeasibility)을 기반으로 두고 있는데 다항 시간에 인수분해를 할 수 있다는 소식은 획기적인 발전이었습니다. 또 Grover는 정렬되지 않은 $N$개의 항목 중 특정 조건을 만족하는 항목을 $O(\sqrt{N})$에...