computing – 페이지 2 – Pseudorandom Things

악의적 비서 문제

2020년 8월 27일2021년 4월 3일Hhan댓글 남기기

n명의 후보자가 순서대로 면접을 보러 오는 상황에서, 각 면전에서는 각 후보자의 점수를 정확히 알 수 있고, 그 점수를 바탕으로 후보자의 합/불 여부를 면접하는 즉시 결정하여 최고의 점수를 가진 후보자를 뽑는 비서 문제에 대해서는 다들 들어보았으리라고 믿는다.

보통의 문제에서 (거의) 최적의 전략은 n명중 약 n/e을 먼저 확인하여 최고점을 측정한 후 나머지 사람중 그 점수를 넘는 사람을 고르는 것. 이러는 경우 약 1/e의 확률로 최고점수의 사람을 고를 수 있다는 것은 잘 알려져 있다.

사실 이 문제는 최근 많은 주목을 받고 있는, 데이터를 연속적으로 받는 온라인 알고리즘 혹은 스트리밍 알고리즘의 한 문제로 볼 수 있다. 그리고 이런 문제들은 데이터를 악의적으로 조작한 상황에 얼마나 우리가 잘 해낼 수 있는지를 많이들 궁금해 한다. 즉, 다음과 같은 상황을 생각해 볼 수 있다.

경쟁사에서 첫 후보자로 (다른 모든 후보를 뛰어넘는) 엄청난 능력자를 보내는 경우, 이 전략은 100%로 실패하게 된다!! 혹은 몇몇 후보자들이 회사가 이 전략을 쓴다는 것을 아는 순간 그 후보자들은 후반 순서를 받기를 원할 것이고, 이 경우에도 뭔가 이상해 질 것이고. 또, 만약 한 명이 아니라 여러명의 비서를 뽑고싶다면 어떻게 될까?

이러한 상황이 악의적 비서 문제, 혹은 음모적(Byzantine) 비서 문제라고 한다. 과연 이런 악의적으로 정해진 상황에서 훌륭한 비서를 뽑을 수 있을까? 이 글은 이 문제에 대한 ITCS 2020에 발표된 논문의 결과를 소개하는 것이 목표이다. 아쉽게도 알고리즘 자체는 꽤나 복잡하고, 대략적인 아이디어만 소개하는 것이 목표.

계속 읽기 →

양자컴퓨터도 XEB Fidelity를 더 잘 속일수는 없다

2020년 8월 21일2020년 8월 23일Hhan댓글 한 개

작년 구글의 양자컴퓨터 실험과 그 이후의 고전 시뮬레이션 발전에 대해 지난번 글에서 소개한 바 있다. 다음과 같이 정의되는 XEB Fidelity를 다시 불러오자.

$\displaystyle {F}_C(p):=2^n \sum_{x\in\{0,1\}^n} p(x)q_C(x) -1$

여기서 C는 타겟이 되는 random circuit이고, $p$ 는 테스트하고자하는 확률 분포, $q_C$ 는 C의 결과로 나오는 확률 분포. 이 XEB값은 $p$ 가 유니폼 랜덤이면 Fidelity가 0이 되고, $p=q_C$ 가 되면 (C의 structure때문에) 1이 된다고 한다.

이러한 설명 하에 지난번까지의 양자우월성 실험에 대한 결론은 다음과 같다.

XEB Fidelity는 구글 실험에서 0.00224를 달성한다.
강력한 가정하에, C의 depth d를 키우면 고전컴퓨터는 XEB Fidelity를 (구글 실험보다도) 크게 만들 수 없다.
(구글 실험과 겹치지 않는) 특정한 파라미터에서는 고전컴퓨터가 XEB Fidelity를 1에 가깝게 만들 수는 있다.

그치만 고전컴퓨터는 depth가 클 때 XEB Fidelity가 거의 항상 0에 가깝고, 양자컴퓨터로 구글의 실험을 하면 노이즈가 줄어들수록 XEB Fidelity가 1에 가까워지니 이걸로 “양자우월성”을 증명하겠다는 것이 구글의 전략이였다.

근데 여기서 잠깐 XEB Fidelity의 정의를 살펴보면, 이 값은 굳이 0~1 사이의 값이 될 필요는 없다. 괴상하게 p를 잘 잡으면 1보다 더 커질 수 있는 값이다!

그렇다면 여기서 질문: 양자컴퓨터를 이용하면 XEB Fidelity를 어떻게 잘 “속여서(Fool)” 1보다 더 크게 만들 수 있지 않을까? 예를들어 100이나 d²같은 값으로? 이렇게 하면 XEB Fidelity를 크게 키우는 것에 집중했을 때 (마지막 결과의) 고전컴퓨터를 이용한 시뮬레이션보다 훨씬 큰, 더 강력한 결과가 되지 않을까?

(안타깝게도) 오늘 나온 논문의 결과에 따르면, 그게 안될 가능성이 높다고 한다.

조금 자세하게는 C는 임의의 회로, 즉 uniform random unitary map으로 잡으면 임의의 ε>0에 대해 XEB Fidelity를 1+ε보다 크게 만드는 실험을 하려면

$\displaystyle\frac{2^{n/4}}{poly (n)}$

보다 큰 개수의 샘플이 필요하다고 한다. 그리고 샘플이 $2^{n/3}$ 개 정도 있으면 실제로 XEB Fidelity를 2에 가까운 정도로 크게 만들수 있다고.

그러니까, 신기하게도 구글의 실험에서 한 단순한 실험이 XEB Fidelity를 키우는데에는 어느정도 최적의 알고리즘 중 하나라는것!

다만 해석에는 여지가 약간 있는데, 논문에서 C를 depth가 작은 임의의 회로가 아닌 uniform random unitary map으로 잡았다. 이건 사실 효율적으로는 구현이 불가능한 회로이고, 이론적으로 뭔가를 증명하기가 훨씬 좋은 이상적인 대상이다. 뭐 여튼 구글의 단순한 실험이 XEB Fidelity 값을 최대로 만드는 방식일 것이라는 강력한 근거는 된다 ㅋ.

하드웨어와 알고리즘의 발전 중 무엇이 빠를까?

2020년 8월 10일Hhan댓글 남기기

컴퓨터 과학과 공학은 최근 수십년간 엄청난 주목을 받고, 특히 문제를 푸는 알고리즘과 그를 실행하는 하드웨어에서 큰 발전을 이루어내고 있다.

알고리즘쪽은 컴퓨터가 풀 수 있는 “효율적인” 문제가 무엇인지에 대답하기 위해 발전하고, 이 블로그의 글중 많은 부분에서 여러 발전을 소개하고있다.

하드웨어 부분에서는 최근까지도 상수년에 2배의 속도가 빨라진다는 무어의 법칙에 거의 따라가며 발전하고 있고, 이 발전은 많은 뉴스기사를 보거나, 당장 우리가 쓰는 컴퓨터를 실행해 봐도 실감할 수 있다.

그렇다면 여기서 질문: 최근의 하드웨어와 알고리즘은 무엇이 더 많이 발전했을까?

물론 일반적으로 두 발전을 비교하는 것은 불가능하다. 특히, 하드웨어는 일반적인 발전정도를 단위연산별로 계측하여 어느정도는 측정할 수 있지만, 알고리즘의 경우에는 어떤 문제를 푸냐에 따라 그 발전정도가 천차만별이다. 심지어 몇몇 문제의 경우는 특수한 경우에 훨씬 잘 풀기도 하고. 지난 글에서 슬쩍 언급했듯이 몇몇 문제는 수십년간 발전이 거의 없는 정도이다.

대신 얼마전 유럽의 연구자들이 Arxiv에 구체적인 문제를 대상으로 비교방식을 제시하는 논문을 포스팅했다. 논문에서는 구체적으로 주어진 식을 만족하는 해가 존재하냐고 묻는 SAT문제를 대상으로 비교를 진행했다. 찾아보니 SAT Competition이 계속 진행되고 있을정도로 활발하게 연구되는 분야이니, 꽤나 괜찮은 대상인듯.

논문의 결과를 간단히 요약하자면 다음과 같다.

여기서 각 항목은 200개의 SAT 인스턴스 중 해결한 인스턴스의 개수를 말하고, 가로축은 서로 다른 SAT-solver 알고리즘들을 뜻하고, 세로축은 1999년과 2019년의 하드웨어, 정확하게는 다음 세팅을 썼다고 한다.

1999년: Pentium III processor (467MHz) + 1.5GB RAM
2019년: Intel Xeon Silver 4112 CPU (2.60GHz) + 128GB RAM

저자들은 Team SW, Team HW를 나누어 각자 구현했다고 한다. 결과에 따르면 다음과 같이 말할수 있다.

SAT문제에 관해서는 알고리즘의 발전이 하드웨어의 발전보다 약간 더 빠르다!

몇가지 관찰이나 세팅은 아래에 정리해둔다.

각 결과들은 200개의 인스턴스중 900초안에 풀리는 인스턴스의 개수를 센 것이다.
인스턴스들은 알려진 벤치마크들로 여러가지 만들어진 것으로, 테스트를 위한 적절한 크기/방법을 골랐다고 한다. 아마 Random SAT등으로 고르면 일부 세팅은 거의 전부 푸는데 다른 세팅은 전혀 못푸는 그런 상황이 벌어졌을듯. 특히 set-asp-gauss라는 벤치마크가 가장 적절하여 이용했다고 한다.
2019년에 가장 좋은 알고리즘으로 알려진 Maple SAT solver가 1999년 하드웨어를 쓴 경우 다른 알고리즘보다 약간 더 못푸는 경우가 발생했다. 저자들도 정확한 이유를 알지는 못하고, 아마 좋은 알고리즘에서 사용한 특정한 자료구조가 현대 하드웨어에 훨씬 적합한게 아닐까.. 같은 추측을 한다.
사실 SAT 알고리즘은 1990년대 후반 등장한 CDCL (Conflict-Driven Clause Learning)이라는 방식을 아직 기반으로 사용하고 있다고 한다. 물론 다양한 발전이 있긴하다! 심지어 CDCL도 DPLL (Davis–Putnam–Logemann–Loveland)이라고 하는 1960년대 알고리즘을 기반으로 발전했다고 한다. 역시 알고리즘의 큰 줄기는 1960년대에 다 나온듯 ㅋㅋㅋ

과거의 알고리즘에 비해 얼마나 좋아졌는지 뭔가 직관적으로 볼 수 있는 결과가 있으면 좋을텐데 좀 아쉽다 ㅋㅋ 여튼 결론은 알고리즘의 연구가 하드웨어연구만큼 중요하다는 것으로 논문은 끝.

깔끔한 문제는 깔끔한 복잡도를 가질까?

2020년 8월 6일2020년 10월 26일Hhan댓글 남기기

이론적 컴퓨터과학의 많은 문제들을 보면, 최근 수십년간 이 학문이 엄청나게 발전했음에도 불구하고 대부분의 문제에서 최적인 알고리즘은 아주 오래전 (수십년 전, 길게는 거의 60년 정도까지!) 발견된 쉬운 알고리즘인 경우가 많다. 좀 발전했다 쳐봤자, 거기에서 조금 나아지는 정도? 구체적인 예들로는 다음과 같은 것들이 있다. O*(X)는 polylogX이나 다른 파라미터들에 대한 비슷한 팩터를 무시한 복잡도. 덧셈, 곱셈등의 복잡도는 대부분의 경우 O(1)로 생각한다.

n개의 점으로 이루어진 그래프에서 모든 쌍들 사이의 최단거리(All pair shortest path)를 모두 구하는 알고리즘은 (가장 일반적인 경우, 즉 대부분의 edge가 있는 경우) 1960년대 Floyd-Warshall 알고리즘의 복잡도인 점의 개수 n에 대해 O(n³)에서 수년 전 Ryan Williams가 발견한 알고리즘이 살짝 나아진 O(n³/exp( $\sqrt {\log n}$ ))정도를 달성하는데에 그친다.
길이가 n인 두 수열에서 같은 부분수열을 찾는 문제(Longest common subsequence, LCS)나 한 주어진 수열에서 특정한 규칙을 따라 다른 주어진 수열로 변화시키는데 최소 몇번의 변환을 해야하는지에 대한 문제(Edit distance)역시 간단한 동적계획법 알고리즘으로 O(n²)의 알고리즘에서 거의 개선되지 않았다. 비슷하게 1980년의 O(n²/log²n)정도가 지금까지 찾은 최고의 알고리즘.
n개의 수의 집합에서 a+b+c=0를 만족하는 쌍 (a,b,c)를 찾는 문제인 3-SUM문제는 아주 간단한 알고리즘인 정렬 후 체크방식인 O(n²)알고리즘보다 나은 방식은 Baran등이 제안한 알고리즘으로 기껏해야 O((nloglogn/logn)²)수준의 굉장히 미묘한 발전이 끝이다.
지난 글에서 말했듯이 외판원 문제(Traveling salesman problem)역시 1960년대 발견된 헬드-카프 알고리즘의 복잡도인 O*(2ⁿ)에서 거의 발전하지 않았다.
또, NP-hard문제의 대명사인 SAT문제를 일반적인 경우에 푸는 최고의 알고리즘도 역시 O*(2ⁿ)수준에 그친다. 물론 SAT문제의 형태를 제한한 3-SAT같은 경우에는 O*((4/3)ⁿ)정도의 알고리즘도 있다.

특히 마지막 두 문제는 NP-hard로 잘 알려진 문제들. 이 문제들을 가장 잘 푸는 방식은 이게 최선일까?

많은 컴퓨터과학자들은 사람들이 좋은 알고리즘을 개발하는 것을 문제의 어려움을 증명하는 것보다 훨씬 잘한다고 생각한다. 즉, 우리가 아는 최선의 알고리즘이 진짜 최선에서 그렇게 벗어나지 않았을 것이라고 믿는다!

이런 생각은 다음과 같은 가설로 구체화된다.

Exponential time hypothesis (ETH)는 n개의 변수에 대한 3-SAT 문제가 어떤 상수 c>1에 대해 O*(cⁿ)의 복잡도를 갖는 알고리즘이 최적이라는 가설이다. 좀 더 강하게, k-SAT의 최적의 복잡도 O*(c_kⁿ)를 만족하는 c_k를 생각하면 $\lim_{k\rightarrow \infty} c_k = 2$ 가 성립할것이라고 말하는 Strong exponential time hypothesis (SETH)도 있다. 최근에는 이것의 양자버젼인 QSETH도 제안되었다. (사실 다들 생각은 하고 있었고, 이걸로 의미있는 결과를 처음으로 얻어냈다.)
비슷하게 3-SUM hypothesis는 임의의 ε>0에 대해 3-SUM을 푸는 O*(n^2-ε) 알고리즘이 없을것이라는 가설이다.

많은 컴퓨터과학자와 나는 SETH가 참이라고 믿는다. 하지만 이를 증명하는것은… 글쎄다. 아마 이러한 관점에서 많은 컴퓨터과학자들이 두 n×n 행렬의 곱이 O*(n²)에 될것이라고 믿는듯 하다. 나는 이것은 아직 그렇게까지 믿지 않는다 -_-ㅋ 이 스택익스체인지에 관련 논의가 있다. 딱히 강력한 근거는 없는듯. 여튼, 이러한 관점에서 컴퓨터과학자들은

깔끔하게 정의된 문제는 깔끔한 복잡도를 갖는다

라고 믿는다. 물론 나도 믿는다 ㅋ

하지만: 지난 TSP에 관한 글에서 언급했듯 네더로프가 증명한 바에 따르면 행렬곱이 O*(n²)복잡도를 달성한다면 이분그래프에 대한 외판원 문제가 O*(1.9999ⁿ)에 풀린다고 한다!

그렇다면 가능성은 다음과 같다.

이분그래프에 대한 TSP는 “깔끔한 문제”가 아니다.
행렬곱은 “깔끔한 문제”가 아니다.
이분그래프에 대한 TSP는 사실 다른 깔끔한 복잡도(e.g. O*((4/3)ⁿ))를 갖는다.
행렬곱이 다른 깔끔한 복잡도를 갖는다.

나는 개인적으로 첫번째 가능성을 지지한다 ㅋㅋㅋ

조금 다른 관점에서, 답을 approximate하게 구하는 것은 어떨까? 예를 들어 TSP의 최적값에 가까운 해를 구하는 알고리즘이나, 선형시간에 LCS에 가까운 해를 찾는것은? 그 가까운의 범위도 깔끔한 값을 가질까?

오랫동안 사람들은 그렇게 믿어온듯 하다. 예를들어 metric TSP, 즉 외판원 문제에서 변들의 길이가 삼각부등식을 만족하는 경우에는 1.5-approximation 다항식 시간 알고리즘이 Christofides–Serdyukov에 의해 알려져 있었고, 이게 최적으로 믿고 있었다. 다음 블로그 글에 한글로도 잘 정리되어 있다.

그리고 LCS는 $\sqrt{n}$ -approximation 선형 알고리즘이 최적이고, 심지어 $n^t$ -approximation 근사는 O*(n^2-2t)에 되었다고 한다.

하지만: 최근 arixv에 올라온 논문에 따르면 metric TSP문제가 다항식시간에 1.49…9-approximation이 가능하다고 한다. 여기서 9는 36개 이하로 있다고 한다 -_- 저자들은 이 결과가 어쩌면 4/3-approximation일수도 있다고 생각하는듯 하다.

그리고, SODA2019에 발표된 결과에 따르면 LCS에 대한 O(n^0.497956)-approximation을 선형시간에 할 수 있다고 한다.

이런, 그렇다면 근사할 수 있는 정도는 깔끔하지 않은것일까? 이건 전혀 모르겠다 -_- 나는 참이라고 믿는데, 최근의 결과들은 그렇지 않다고 주장한다. metric TSP정도는 꽤나 깔끔한 문제처럼 느껴지는데……

서평: Quantum Computing Since Democritus

2020년 7월 27일Hhan댓글 남기기

최근 스콧 아론손(Scott Aaronson)의 저작 Quantum Computing Since Democritus (QCSD)를 읽고있다. 아론손은 일전에 번역하여 포스팅했던 큰 숫자들의 저자이기도 하다. 2006년 워털루 대학에서 가르쳤던 렉쳐에서 시작된 책이라고 한다.

QCSD는 양자컴퓨터의 시작부터 (2013년까지의) 현재 근황까지 발전하여 이어진 여러 생각들을 아론손의 아주 잘 정리하고 있다. 다루고 있는 내용은 컴퓨팅에 관한 고전적 이론부터 양자물리학이 왜 이렇게 이루어져야 하는지, 이와 양자컴퓨터가 만났을 때 일어나는 일들이 무엇인지, 양자물리학으로 (컴퓨터과학에) 어떤 이상한 일들이 벌어지는지, 양자컴퓨터와 우주 (예를들어 closed timelike curve)가 만나면 무슨일이 벌어지는지 등을 굉장히 다양하게 소개한다. 심지어는 타임머신, 자유의지, 마음 등 철학적인 주제마저도 넘나들며 논의한다 -_-!!

놀라운게 저런 개념들을 소개하며 아론손 자신이 쓴 논문들과 최근의 가장 화제가 된 논문들 -_-… 을 개념적으로 아주 잘 연관시켜 설명해준다. 예를 들어 “classical proof”와 “quantum proof”가 어떻게 다른지 [논문], 위에 살짝 말한 Closed timelike curve를 컴퓨터가 이용할 수 있을때 고전컴퓨터와 양자컴퓨터가 어떻게 달라지는지 [논문]라던가, 다른 결과로는 IP=PSPACE, 혹은 P≠NP문제가 증명하기 어렵다는 이전의 결과나 아론손 본인의 논문등.

양자컴퓨터의 “성서“를 쓴 미카엘 닐슨(Michael Nielsen)은 다음과 같은 코멘트를 하기도 했다.

“이 책은 우리가 과학의 근본에 대해 궁금한 점들에 대해 알아낸것들의 아름다운 조합이다. 정보란 무엇일까? 계산한다는 것은? 마음과 자유의지라는것은 무엇일까? 아론손은 그의 고유한 문장들을 통해 최근 과학에서 가장 놀라운 발견, 생각-예를 들어 영지식 증명이나 양자컴퓨터, 블랙홀 엔트로피 등-에 대한 지식을 맛있게 조리한다. 강력하게 추천한다.”
Michael Nielsen in Aaronson’s blog comment.

개인적인 생각으로는, 이 책이 정말 저런 지식들을 아름답게 정리하기는 한다. 근데 좀 어렵다! 분량때문이기도 하겠지만, 너무 많은 전문적인 지식을 간략한 설명으로 때우고 설명한다. 교양 서적이라기보다는 준-교양서적. 읽는데 꽤나 노력이 필요하다. 그치만 그 내용은 정말 놀랍고 아름다운 내용들을 담는다. 나도 강력하게 추천한다 ㅋ

혹시 관심이 있으면 아론손의 홈페이지에 책보다 훨씬 짧은 렉쳐노트들이 정리되어 있다. 한번 살펴보는것도 추천. 얼마전 아론손이 새로 쓴 새 서문에서 여러가지 재미있는 이야기도 있다. 2013-2020의 양자컴퓨터 관련 놀라운 결과들도 아주살짝 정리되어있으니 이것도 추천ㅋ.

외판원 문제를 얼마나 빨리 풀 수 있을까?

2020년 7월 15일2020년 7월 28일Hhan댓글 한 개

외판원 문제(Traveling salesman problem, TSP)는 n개의 도시들 사이의 음아닌 거리가 주어졌을 때 모든 도시를 정확히 한번씩 돌아 제자리로 돌아오는 외판원의 여행거리를 결정하는 문제이다. 이는 P대 NP문제와 NP완전문제를 소개할 때 가장 대표적으로 나오는 예시이기도 하다. 물론 실제 이론적인 배경을 설명할때는 문제 하나로 소개되는정도로 그치는것 같긴 하지만.

이 글에서는 일반적인 외판원 문제를 정확하게 푸는 지금까지 최고 알고리즘과 여러 시도들, 열린 문제들을 소개하는 것이 목표이다. 근사적인 답을 구하는 것도 큰 문제인데, 이 글에서는 다루지 않을것이다. 그리고 이 블로그의 글중에서는 드물게도 구체적인 알고리즘을 설명할것이다. 왜냐면 설명하기 좀 쉬우니까 ㅋ.

계속 읽기 →

양자컴퓨터를 이용한 소인수분해는 어디까지 왔을까?

2020년 7월 8일2020년 7월 15일Hhan댓글 2개

이 글에서는 피터 쇼어(Peter Shor)가 1994년 (Arxiv논문 링크), 이제는 쇼어의 알고리즘이라고 불리는 양자 소인수분해 알고리즘을 제안한 이후, 여러가지 측면에서 양자컴퓨터가 소인수분해 문제를 풀기에 얼마나 발전했는지, 그리고 얼마나 빨리 소인수분해를 할것으로 예측하고 있는지를 정리하고자 한다.

이 글은 다음과 같이 구성된다.

쇼어알고리즘의 간략한 설명
쇼어알고리즘의 구체적 구현과 최적화 논문들
양자컴퓨터를 이용한 실제 소인수분해 실험들

그치만 결론만 먼저 요약하면 앞선 글에서 소개했듯 RSA-240,250, 즉 약 800비트 정수를 소인수분해 하는데 2000 core-년이 필요한 반면, 2천만 큐비트의 에러가 있는 양자컴퓨터가 있다면 그럴듯한 가정 하에 RSA-2048, 즉 2048비트 정수를 소인수분해 하는데 8시간이면 충분하다고 한다! 이게 바로 양자컴퓨터의 위력 ㅡㅡ!

다만 쇼어알고리즘을 양자컴퓨터로 실제로 돌리는 것은 (내가 아는바에 의하면) 딱히 실험적으로 진행한 바가 없다. 쇼어알고리즘에 어느정도 치팅을 한 버젼이나, Adiabatic quantum computer등을 이용한 방식이 진행되었을 뿐이다. 치팅을 한 버젼도 최대한 치팅을 한것은 아니고, 그럴듯한 정도로 해서 양자 소인수분해에 대한 어느정도 근거를 주기는 하지만 말이다.

계속 읽기 →

양자 볼륨과 허니웰의 새로운 상업적(?) 양자컴퓨터

2020년 6월 20일2020년 8월 21일Hhan댓글 한 개

허니웰(Honeywell)이 64의 양자볼륨을 갖는, 세상에서 가장 좋은 새로운 양자컴퓨터를 선보였다는 이야기가 들린다. 허니웰 사이트와 영어기사, 한글기사가 있다. 근데 사이트나 영어기사에는 상용이라는 말이 딱히 안보이는데 한글기사에는 제목에 떡하니 있구만.

구글의 양자우월(quantum supremacy) 발표와 다르게 학계에서 이런 얘기를 딱히 들은게 아니라 이게 뭔가 싶었는데, 알고보니 측정하는 방식 자체가 다르다. 지난 글에서 얘기했듯이 구글의 양자우월은 XEB Fidelity를 측정하는 방식으로 증명되었는데, 허니웰은 IBM에서 2018년 제안한 양자볼륨(Quantum Volume)이라는 값을 처음으로 64를 달성한 양자컴퓨터를 달성했다는 것. 작년 발표된 구글 시커모어(Sycamore)는 딱히 양자볼륨에 대한 얘기를 하지는 않았다. 이 글에서는 양자 볼륨이 뭔지, 그리고 이를 토대로 허니웰의 양자컴퓨터에 대한 (약간은 부정적인) 논의를 하고자 한다. 여러 부분을 스콧 아론손(Scott Aaronson)의 블로그 글과 그 댓글들에서 참조하였음.

2020/08/21 추가: IBM Q의 개선으로 IBM Q가 양자볼륨 64를 달성했다고 한다. 이건 실험 논문까지 공개됨.

계속 읽기 →

새로운 양자프로그래밍 언어: Silq

2020년 6월 18일2020년 6월 22일Hhan댓글 남기기

ETH Zurich에서 Silq라는 새로운 고급 양자프로그래밍 언어를 발표했다는 소식. 프로그래밍 언어 학회로 유명한 PDLI 2020에서 한국기준 내일 새벽 6시 20분에 발표가 예정되어있다고 한다 -_-…… 온라인 컨퍼런스이지만 실시간으로 보는건 불가능하겠구만.

기존에 유명하던 Q# 등보다 반정도의 라이브러리와 소스코드 길이로 똑같은 일들을 할 수 있다고 한다. 원래 이 팀이 관심있던건 직접 프로그래밍을하던가 하는등의 문제였었는데, 기존의 언어들을 쓰다보니 양자컴퓨터에서 필요없는 ancila를 지우는 등의 uncomputation이나 여러 작업들이 너무 답답해서 새로운걸 만들기로 결정했다고 ㅋㅋㅋ 그래서 Silq는 uncomputation이나 코딩상에 (invalid한 measurement등) 에러를 잡아주는 등 여러 편의성이 있다고 한다.

여기 Q#코딩 콘테스트에서 다루었던 문제들에 대한 예시코드들이 있는듯. 생각보다 그럴듯하다 ㅋㅋㅋ 아래는 간단한 태스크인 주어진 첫비트가 1인 $b\in\{0,1\}^n$ 에 대해 superposition $(|0^n\rangle +|b\rangle)/\sqrt 2$ 를 만드는 코드.

Silq code for generating $(|0^n\rangle + |b\rangle)/\sqrt 2$ given $b\in \{0,1\}^n$ , taken from Silq site.

심심해서 Q#콘테스트 문제들도 찾아봤는데 문제들이 꽤나 그럴듯하다. 양자컴퓨터를 공부하면 항상 계산을 너무 적게해서 문제인데, 계산 연습할 겸 심심할때 한번 짜봐야겠다.

암호란 무엇인가? (1) 암호학적으로 어려운 문제

2020년 6월 15일2020년 10월 8일Hhan댓글 남기기

인터넷 세상에 살다보면 RSA니 SHA니 뭐니 암호란게 굉장히 자주 접하는 대상이고, 피할 수 없는 대상이다. 따라서 학술적 커뮤니티도 꽤나 크고 다양하게 연구되고, 그 나름의 엄밀성이 다 잘 정의되어있다. 그런데 한국 커뮤니티 여기저기에서는 (아마 외국에서도?) 이런 논의를 다루는 글을 찾아보기가 굉장히 힘들다. (개인적으로는) 더 이해하기 힘든 양자역학 등도 훨씬 다양한 글에서 소개하는데말이다. 기껏해야 암호 encryption, decryption이 뭔지, public key encryption이 뭔지 다루는 등등 정도이고 RSA라는게 있고, 이게 소인수분해가 안전하면 안전하다는 거짓말을 아무 설명없이 하는정도가 끝인듯. 심지어 대학교 수업들에서도 잘 깊게 다루지 않는듯. 그래서 언젠가 이걸 정리해야지 생각하고 지난달쯤 DC 수잘갤에 약간 정리하다가 힘이 빠져서 그만 둠. 그래도 공부하다보니 딴짓을 하고싶어서 여기 저 글들을 훨씬 더 다듬어서 새로 정리함.

계속 읽기 →