Month: 9월 2020

거시적인 양자 성질은 관측하기 어렵다

Hhan댓글 남기기

[주의: 글쓴이는 물리학적인 지식이 굉장히 부족하다. 그래서 아래 설명 중 세부적인 부분이나 이론적 배경, “썰”이 좀 틀릴 수 있다. 혹시 문제가 되는 부분을 발견하면 지적바람 -_-ㅋ]

아마 이 블로그의 독자들은 슈뢰딩거의 고양이 사고실험에 익숙할 것이라고 믿는다. 이 실험은 고양이를 외부와 차단된 방에 넣은 후, 0 또는 1의 상태를 가지는 입자를 (normalizing factor를 생략한) 다음과 같은 양자상태

|0〉+|1〉

로 만들고, 상태가 0일때 고양이를 죽이는 가스를 살포하고 1일때 아무일도 하지 않아 고양이의 상태를

|Dead〉+|Alive〉

으로 만드는 실험이다. 즉 주어진 입자의 양자상태에 따라 고양이의 삶과 죽음이 중첩되는 이상한 일이 벌어진다는 것이다. 지금 보니 굉장히 잔인하다 -_-…

여튼 원래 이 실험은 슈뢰딩거가 양자역학의 역설적인 부분을 지적하기 위해 제시했다고 한다. 지금은 아이러니하게 양자역학을 설명하는 대표적 실험으로 자리잡았지만 말이다ㅋㅋㅋ

대중적으로 설명될 때 이 실험은 사실 양자역학이 아니라 확률론적인 관점에서 설명이 된다. 즉, 입자의 상태가 양자상태로 중첩되어있는 (superposition) 설명이 아니라, 50%의 확률로 0, 50%의 확률로 1의 상태를 갖고 이에 따라 고양이도 50%의 확률로 살고 죽는다는 식의 설명. 근데 이 설명은 (예측불가능한) 난수가 있는 비결정론적(확률론적) 세계관에 더 가깝지, 양자역학적 세계관의 설명이 아니다!

여기서 다음과 같은 질문이 떠오른다:

슈뢰딩거의 고양이 실험, 혹은 비슷한 거시적인 실험으로 양자적 성질을 확인할 수 있을까?

물론 학자들은 우리 세계가 양자역학으로 잘 설명된다는 것은 이런저런 미시적 실험을 통해 이미 잘 이해했다. 그치만 이런 상상도 궁금하지 않은가 ㅋㅋ

며칠 전 (!) 이 문제에 대한 대답을 하는 논문 [1]이 올라왔다. 저자는 양자컴퓨터의 대가의 스콧 아론손과 끈이론, 우주론 등으로 유명한 레나드 써스킨드, 그리고 Yosi Atia라는 학생. 그들에 따르면 아마 그런 실험적 증명은 불가능할 것이라고 한다. 아론손의 발표는 [2]에서 확인할 수도 있다.

논문에서 설명하는 정확한 이유는 다음과 같다. 우선 슈뢰딩거의 고양이 실험에 해당하는 양자상태

|Dead〉+|Alive〉

와 이를 고전적으로 설명하는 (1/2로 살고 죽는) 확률론적 상태

[(1/2,|Dead〉), (1/2,|Alive〉)]

를 최적의 확률로 구별하는 양자회로 U가 존재한다고 가정하자. 그러면 이를 이용해서 비슷한 크기의, 다음 식을 만족하는 다른 양자회로 V를 만들수 있기 때문이라고 한다.

V|Dead〉=|Alive〉, V|Alive〉=|Dead〉

(물론 이건 엄청 간단하고, 저자들은 더 강력하게 이 명제가 정확하지 않은 측정 (즉, 특정확률로 틀리는 회로)에 대해서도 비슷하게 성립한다는 robustness와 그것의 tightness도 증명하였다.)

근데 이 회로 V의 결과를 보면 “죽음”과 “삶”을 바꾸는 연산이다. 즉, 죽은 고양이를 살리는 연산 (!!)이라는 것이다. 우리 세상에서는 이러한 연산이 (최소한 현실적으로는) 불가능할 것으로 보이고, 따라서 관찰자도 거시적인 고양이의 상태가 양자적인지 고전적인지 구별하기 어렵다는 것이다. 이에 따라 저자들은 거시적 실험을 통해 양자상태를 확인하는게 양자사령술만큼 어려운 문제라고 주장한다 ㅋㅋㅋ

비슷한 거시적 실험을 들고와도 두 상태는 확연히 구별될테고, 이를 바꾸는 것은 보통 쉽지 않으니 거시적 관점에서 양자상태를 확인하기 어렵다고. 예를 들어 고양이 대신 친구(!)를 넣고 그 측정 결과를 위그너의 친구 실험이 있는데, 이 경우에도 친구가 양자상태에 있는지 확률론적으로 있는지를 구별하려면 친구의 생각을 바꾸는 연산이 필요하다고.

이 해석을 좀 더 다양한 물리학적/철학적 관점으로 일반화 시키면, 만약 우리가 양자적으로 다중우주에 산다고 해도, 우리가 그 우주의 상태를 서로 바꿀 수 없다면 우리가 다중우주에 산다는 것을 경험/확인할 방법이 없다는 뜻을 가진다고 한다. (무슨말인지 사실 잘 모르겠지만..) 우리가 열역학적인 시간의 방향(Thermodynamic arrow of time)을 따른다면, 우리가 이를 반대방향으로 돌릴 능력이 없다면 이를 확인/경험한할 방법이 없다고.

물리학이란 아무리 봐도 참 신기하다 ㅋ. 아론손의 6월 발표를 담은 유튜브 [2]도 좀 참고하였다.

[1] On the Hardness of Detecting Macroscopic Superpositions, arxiv.org
[2] Schrödinger’s Cat and Quantum Necromancy, Workshop on Complexity from Quantum Information to Black Holes (Online, youtube record)

양자컴퓨터에 대한 최근 예측들

Hhan댓글 남기기

요 며칠간 양자컴퓨터의 미래에 대한 의견이 두개 등장했다. 하나는 IBM의 단기간 (수년)에 대한 긍정적인 주장 [1]이고, 다른 하나는 장기간 (수십년)에 대한 약간은 부정적인 예측 [2]이다. 약간은 상반된 것 같은데, 여기 아주아주 간단히 기록해본다. 사실 두 논문 모두 이론적인 설명이라기보단 주장/홍보나 지금까지의 발전에 의한 수치적 예측이여서 뭐 이론적으로 설명할 것이 없음 ㅋㅋ

우선 IBM은 최근 2023년까지 1121 qubit ㅡㅡ!의 크기를 갖는 양자컴퓨터를 발표할것이라고 발표했다. 아래는 IBM의 로드맵.

A look at IBM’s roadmap to advance quantum computers from today’s noisy, small-scale devices to larger, more advance quantum systems of the future. Credit: StoryTK for IBM
IBM’s roadmap to advance quantum computer. Taken from IBM blog

아니 뭐 IBM 블로그에 올라온 그림이 안선명하냐 -_-… 뭐 대충 1년에 2배이상의 큐비트를 다룰수 있는 양자컴퓨터를 설계하겠다는 주장인듯 하다. 근데 구글인가 어디에선가 누가 오류율(error rate)가 없는 큐비트에 대한 주장은 믿지 마라 그랬는데 ㅋㅋㅋ 그냥 간단한 소개글이라 그런지 딱히 오류율에 대한 얘기는 없다. 물론 저 큐비트들이 에러가 적은건 아닐테고, Sycamore랑 비슷하거나 더 심한 수준이 아닐까 싶다.

그 다음 주장은 NTT Research와 영국 애버딘 대학의 연구자의 결과로써, 지금까지의 발표된 연구결과를 바탕으로 통계적으로 양자컴퓨터의 미래를 예측하는 논문이다. 이런 미래를 예측하는게 아예 없었던건 아니고, 이전에 몇 개가 있었다고 한다. 두 개만 비교를 위해 살짝 들고와서 비교하자.

  • 스탠포드의 마크 호로위츠(Mark Horowitz)와 Emily Grumbling은 2019년 출판된 책에서 RSA-2048이 2020년대에 깨질일은 없을것이라고 추측했다고 한다 (It is highly unexpected that..). 그리고 여러 예측을 했다는데 파는 책이라서 딱히 찾아보고 싶지는 않다 -_-.
  • 워털루대학의 미셸 모스카(Michele Mosca)와 마르코 피아니(Marco Piani)는 연구자들에 대한 설문조사를 진행했는데, 22.7%의 학자가 RSA-2048이 2030년 내에 깨질것이라고 생각했고, 50%의 학자가 2035년까지는 깨질것이라고 생각했다고 한다. 아래가 해당 논문의 예측인듯.
Image
  • 이 논문에서는 통계적 추측을 통해 조금 더 부정적인 주장을 한다. 2026년까지는 (에러정정부호등을 이용해서) 오류율을 굉장히 작은 (10-18정도인듯) 하나의 큐비트를 만들 확률이 5%이하라고 예측했다. 그리고 2039년까지도 RSA-2048을 양자컴퓨터를 이용해 깰 확률이 5%이하라고 예측했다. 다만 이는 최근 50여개의 샘플논문을 통한 예측이긴 하다. 물론 이 보다 빠르려면 뭔가 새로운 혁신이 필요할 것이라고. 그게 그렇게 자주 나오려나 -_-? 아래는 2023년까지 달성할것으로 예측하는 양자컴퓨터의 범위.
Image
가로축은 큐비트의 수, 세로축은 오차율을 나타낸다. 그래프 내의 숫자는 확률. 즉, 90%이내의 확률로 2023년의 양자컴퓨터는 100큐비트정도를 달성할 것이라는 것.

신기하게도 2023년에 대한 두 예측이 완전 딴판이다 ㅋㅋ 3년 후면 확인할 수 있으니 그저 기다려본다.

[1] IBM’s Roadmap For Scaling Quantum Technology, IBM blog
[2] Forecasting timelines of quantum computing, arxiv.org

MS의 수중 데이터센터

Hhan댓글 남기기

Arstechnica의 기사 따르면 [1] (2차출처 [2], 3차출처 [3]) 마이크로소프트에서 추진한 수중 데이터센터 실험이 성공적으로 이루어졌다고 발표되었다고 한다. 2018년 처음으로 해저에 넣어져 이번에 꺼낸 모양이다.

해저에 서버를 넣을 때 가장 걱정이 되던 부분은 에러같은 부분을 잘 조절할 수 있느냐였던 모양이다. 왜냐면 큰 에러가 나면 사람이 고치러 가기 힘드니까 -_-. 하지만 서버가 담긴 탱크를 질소로 채운 모양인지, 훨씬 안정되어 보통 서버의 1/8정도의 에러만 냈다고 한다. 게다가 서버를 식히는 등의 문제는 감싼 해저의 온도가 대부분 해결해 준듯.

한국에서는 크게 신경쓰지 않는듯 하지만, (사실 쓰레기장 문제로 알게모르게 커져가는듯 하다.) 환경 문제는 해결하기 쉽지 않아보이는 문제이다. 한국은 에어컨을 굉장히 많이 쓰는것 같은데, 이런 인간의 접촉이 적으며 냉각기술/공간이 많이 필요한 서버 등의 물체를 해저로 내리는 것은 굉장히 훌륭한 생각인듯. 과거 많은 애니메이션에서 달 뒤를 서버로 쓰는 등을 보여주었다고 하는데, 어쩌면 멀지 않았을지도 모른다 ㅋㅋ

[1] Microsoft declares its underwater data center test was a success, Arstechnica
[2] MS의 수중 데이터센터 프로젝트, 2년만에 성공 선언, Gigglehd.com
[3] MS의 수중에 처박은 서버..2년후 결론을 보고 느낀점, pgr21.com

정지하는 튜링머신의 종료시간을 예측할 수 있을까?

Hhan댓글 남기기

이 블로그의 독자라면 아마 정지 문제(halting problem)이 결정불가능한 문제(undecidable problem)라는 것을 잘 알것이다. 그러니까 주어진 튜링머신 M과 입력값 x를 보고 이에 해당하는 M(x)의 튜링머신 계산이 정지할지 아닐지를 결정하는 문제는 임의의 알고리즘을 들고와도 풀 수 없다는 말. 이제욱씨의 페이스북 글이 괴델의 불완전성 정리와 정지 문제를 잘 엮어 설명해준다.

어찌보면 정지 문제를 푸는 것은 너무 야심찬 계획이였다는 말. 임의의 튜링머신과 입력값은 너무나 많다. 어쩌면 임의의 튜링머신이 아니라 적절한 한계가 있는 튜링머신을 생각하면 뭔가 나은 점이 있지 않을까? 예를 들어

정지하는것이 보장된 튜링머신이 있을때,
이 기계가 언제쯤 종료하는지 예측할 수 있을까?

정지하는 튜링머신은 훨씬 좋은 조건이지만, 거기서 우리의 문제는 정지시간의 예측이라는 약간 강한것으로 바뀌었다. 이게 효율적으로 가능하다면 실제 생활에의 응용, 예를 들어 여러 휴리스틱하거나 재귀적인 알고리즘의 종료시간 등을 먼저 예측하는 것도 가능해진다.

하지만 안타깝게도 답은 불가능하다이고, 우리는 위 문제보다 강한 다음 문제가 결정불가능함을 증명할 것이다.

다항식 시간 안에 끝나도록 보장된 튜링머신 M과 정수 k가 있을 때,
입력값의 길이 n에 대한 M의 점근적 실행시간이 O(nk)인지 결정할 수 있는가?

[증명] (Proof in TCS stack exchange by Emanuele Viola)

주어진 문제가 정지 문제보다 어려움을 보이면 충분하다. 정지문제의 인스턴스 (M,x)에 대해 우리는 다음과 같이 행동하는 새로운 튜링머신 M’을 만들것이다:

  • 입력값의 길이 n에 대해 M(x)를 n번째 스텝까지 계산해본다. 만약 M(x)가 종료됨을 확인했다면 n2스텝까지 아무 계산이나 하고 마친다.
  • 그렇지 않다면 n3스텝까지 아무 계산이나 하고 마친다.

이 M’=(M,x)은 어느 경우에나 n3스텝 안에 종료되니 다항식시간에 마치는 튜링머신이고, M,x는 n과 관계없는 인스턴스이므로 M(x)가 종료된다면 이는 t=O(1)시간에 종료된다고 말할 수 있다. (즉, n과 무관한 종료시간을 갖는다.) 따라서 M’의 점근적 시간은 (M,x)가 M(x)가 유한시간에 종료된다면 O(n2)이 되고, 그렇지 않다면 O(n3)이 되는것.

즉, 주어진 문제를 k=2에 대해 풀 수 있으면 정지 문제를 풀 수 있다. 다시말하면 주어진 문제는 결정 불가능하다.

이를 일반적으로 좀 더 연구한 이런 저런 논문들도 있는듯하다. 대충 결론은 M의 시간복잡도가 nlogn만 되어도 확인이 불가능하고, 이거보다 약간만 작아도 확인이 가능한듯.

GPT-3는 생각하지 않는다

Hhan댓글 한 개

지난 글에서 GPT-3에 대해 얘기를 이미 했다. 보통 같은 주제에 대해서 이론적 고찰이 없는 여러 글을 쓰지는 않지만, GPT-3는 꽤나 흥미롭게 따라가는 주제여서 기록해둔다.

아래는 MIT Tech Review에 Robust.AI의 창립자인 Gary Marcus와 NYU의 교수 Ernest Davis가 기고한 글에서 발췌/번역한 GPT-3의 “생각하지 않음”을 증명하기 위해 만든 예시들이다. 보통 글씨는 GPT-3의 입력문, 굵은 글씨는 GPT-3의 대답. 기울어진 글씨는 저자들, 혹은 내 생각이다. (GPT-3는 원래 대화가 아니라 “이어지는 문장”을 만드는 기계학습 모델임을 기억하자!) 또한 번역 과정에서 GPT-3의 대답이 나뉜 부분들이 있는데, 이건 번역상의 문제이고 GPT-3는 연속된 문장만을 대답했다.

계속 읽기 →