| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
| 양자컴퓨터 Quantum Computer |
| |
| 2019년, IBM에서 개발한 최초의 회로 기반 상용 양자컴퓨터[1] IBM 퀀텀 시스템 원 (IBM Quantum System One) |
[clearfix]
1. 개요
양자역학에서 양자얽힘, 중첩, 텔레포테이션 등의 효과를 이용해 계산하는 컴퓨터를 말한다. 기존 컴퓨터가 0과 1만 구분할 수 있는 반면, 양자 컴퓨터는 0과 1을 동시에 공존시킬 수 있다.[2]양자 컴퓨팅은 컴퓨터과학, 물리학, 수학의 여러 측면으로 이루어진 종합적 분야로서 양자역학을 활용해 기존의 컴퓨터보다 빠르게 복잡한 문제를 해결할 수 있다.
이론적으로 현존 최고의 슈퍼 컴퓨터가 수백 년이 걸려도 풀기 힘든 문제도 단 몇 초 이내의 어마어마한 속도로 빠르게 풀 수 있을 것으로 전망되고 있다.[3] 특히 이런 무궁무진한 기술 때문에 군사적 이용 가치가 커서 미중 패권 경쟁에서도 주요 분야로 자리매김하고 있다. 실제로 미국 대통령 조 바이든은 중국의 양자 기술만 콕 집어 제재를 가하라고 행정 명령하기도 했다.
도전 골든벨 남양주청학고편에서 골든벨 문제로 출제되었다.
2. 상세
| 양자컴퓨터 - 인류 과학기술력의 한계[4] |
미국의 물리학자 리처드 파인만, 폴 베니오프, 찰스 베넷과 소련/러시아 수학자 유리 이바노비치 마닌[5]이 최초의 구상자로, 실질적인 작동원리는 옥스퍼드 대학교의 데이비드 도이치 박사가 고안하였다. 트랜지스터로 만들어진 게이트 대신 양자(量子) 게이트를 연산도구로 사용한다.
근래에는 반도체 회로 집적도가 한계에 가까워졌다는 신호들이 나타나면서 그 대안인 양자컴퓨터가 크게 주목받게 되었다. 상업적 측면에서 집적도를 늘리면 늘릴수록 단위면적당 생산량이 늘어나 비용이 절감되는게 아니라 가공에 돈이 더 들어가게 되어 집적도를 증가시킬 이유가 사라졌다. 제조비용적 측면을 제외하더라도 양자 터널링 현상이 발생하여 전자들을 통제할 수 없을 것이라고 전망되기 때문에[6] 집적화가 한계에 가까워졌다는 평이 많아졌고, 결과적으로 양자컴퓨터에 대한 관심이 커지게 되었다.
주요 선진국들의 최고 수준의 연구소들과 IBM, 구글, Microsoft, 인텔, NTT 등의 글로벌 기업들이 연구하고 있다. 그만큼 관심이 높고 상용화가 되는 순간 대박이 될 물건. 양자 컴퓨터를 어떻게 만드는가에 관해서는 아직 정해진 것이 없고, 물리적으로 수많은 난제들이 남아있기 때문에 국가, 연구소, 기업별로 다양한 방법들을 시도하고 있다.
한편, 또 다른 양자역학 효과를 이용한 계산기도 양자 컴퓨터라고 불리고 있어, 일반인들에게 혼란을 주고 있는데 대표적으로 양자 어닐링(Quantum Annealing), 양자 신경망(Quantum Neural Network)이 있다. 이러한 효과를 이용한 양자 컴퓨터들도 비슷한 규모 대비 기존 컴퓨터에 비해 효율적이고 빠르지만, 일반적으로 생각되는 양자 컴퓨터의 성능에는 택도 없이 못 미친다. 위에 언급했듯이 양자중첩과 양자얽힘 효과를 이용하여 계산하는 양자 컴퓨터의 성능은 현존 최고의 슈퍼 컴퓨터의 계산 속도보다 수억 배는 빠를 것으로 추측되고 있으며, 이러한 양자컴퓨터 개발분야 중 초전도체 방식은 IBM과 리게티(Rigetti)가 앞서가고 있으며, 이온트랩 방식은 IonQ가 빠른 진전도를 보이고 있다.
3. 하드웨어적 원리
3.1. 큐빗의 원리
원리상 양자역학적으로 중첩과 간섭을 구현할 수만 있으면 물리적 소자는 뭐든지 될 수 있는 것이 큐빗이라고 생각하기 쉬우나, 단순히 그러한 특정 양자계가 있다고 무조건 큐빗이라고 하지 않는다. 실제로 양자컴퓨터 연구 초창기 시절에 개념을 실험적으로 구현하는데는 NMR 방식이 주로 사용되었으나 현재는 더 이상 사용되지 않는다.양자컴퓨터의 큐빗으로 사용될 양자계는 DiVincenzo's criteria로 알려진 다음의 5가지 조건에 부합해야 한다.
*큐빗으로 기능하기 위한 충분한 이해도를 가지고 있으며, 확장 가능할 것.
*상태의 초기화(레지스터의 초기화)를 위해 명확한 기준점을 가질 것.
*충분히 긴[7] 간섭 시간을 가질 것.
*필요한 양자 게이트들을 갖출 수 있을 것
*특정 큐빗을 대상으로 한 측정이 가능할 것
디빈첸초 조건을 만족하는 큐빗으로는 초전도체, (포획)이온, 양자점, 다이아몬드 내의 질소 공극[8], 광자 등이 가장 유명하다.
포획 이온 큐빗을 사용한 양자컴퓨터를 예로 들면 다음과 같다. 우선 진공 상태의 공간에 자기장으로 덫을 만들어 주입된 이온을 붙잡아 둔다. 다음으로 포획된 이온에 알맞은 레이저를 발사하여 전자 스핀을 제어해 컴퓨팅을 하고, 최종적으로 분광법을 이용한 상태측정으로 결과를 얻는다. 즉 원자 하나하나를 분리하여 큐빗으로 제어할 수 있는 상태를 만드는 것이다.
이 외에도 P donor spins in Silicon, Rydberg atom과 같은 큐빗들이 알려져 있으며, 위상양자컴퓨터나 스핀트로닉스, 밸리트로닉스를 통한 접근 방법도 연구되고 있다. 최근에는 전통적인 큐빗들을 확장하여 실용성 있는 Universal 양자컴퓨터를 만드는 데는 수많은 큐빗들을 광자통신채널로 연결하여 대규모 양자네트워크를 구성하는 Hybrid 방식이 유력한 후보로 거론되고 있다.
2021년 기준으로 가장 앞선 성과를 보여주는 것은 역시 초전도 방식인데, IBM과 구글이 둘다 이쪽을 주로 개발하기 때문이다. 초전도 큐빗은 반드시 극저온을 필요로 하는 일부 단점도 있어, 초전도를 포함하여 다양한 양자 컴퓨터 방식에 걸쳐 심도있는 연구가 세계 각국에서 진행중이다. 예를 들어 국내에서 KRISS는 초전도 기반으로, KIST는 다이아몬드 기반 소자에, ETRI는 광자 큐빗 방식에 집중하고 있다.
4. 소프트웨어적 원리
자세한 기전은 아래 문단들로 후술하지만, 컴퓨터의 용도는 '정답(값)을 출력'하는 것이고, 양자컴퓨터 또한 이에 벗어나지 않는다는 것을 먼저 생각해야 한다. 양자컴퓨터는 고전 컴퓨터와 다른 점이 있다. 고전 컴퓨터는 '확정적인 정답'을 출력하는 기계다. 1+1은 무조건 2라는 식의 확정적인 정답만을 출력한다. 하지만 양자컴퓨터는 다르다. 정답을 정답으로써 출력하는 게 아니다. '정답일 확률이 가장 높은 값'을 정답으로 출력하는 것이다.4.1. 양자 알고리즘의 구조
일반적인 양자 알고리즘의 작동은 레지스터 초기화(양자 중첩 발생)[9] > 양자 중첩 제어[10] > 확률 분석(제어된 값들의 분석) 순으로 구성한다.4.2. 고속 연산
흔히 양자컴퓨터에 대해 알려져 있는 오해는, 양자컴퓨터는 일종의 병렬 계산을 할 수 있어서 (양자 중첩으로) 고전 컴퓨터보다 훨씬 빠른 연산이 가능하다고 생각하는 것이다. 0과 1이라는 비트 대신에, 0이라는 상태와 1이라는 상태의 임의의 선형 결합이 가능하다는 양자역학적 특성을 보면 그 설명이 자연스러운듯이 느껴지기도 한다. 또한 일반적으로 양자컴퓨터에 대한 대중적인 설명을 할 때 거의 예외 없이 그런 설명이 나온다. 하지만 이는 올바른 설명이 아니다. 만일 정말로 그렇다면, 병렬 계산에 의해 임의의 NP 문제는 효율적으로 풀릴 수 있으므로[11] 양자 컴퓨터는 임의의 NP 문제를 효율적으로 풀 수 있어야 할 텐데, 아마도 그렇지 않을 것임을 시사하는 증거들이 있기 때문이다.이를 이해하는 또 한 가지 방법은 양자 계산과 확률적 계산을 비교하는 것이다. 2n개의 상자가 있고, 그 상자들 중 단 하나에 공이 들어있다고 하자. 공이 들어있는 상자를 확실히 찾기 위해서는 고전 컴퓨터는 2n번 상자를 열어야 한다. 양자 컴퓨터가 만일 그 '병렬성'을 이용해서 이 문제를 풀 수 있다면, 상자를 한 번만 열어보면 될 것이다: 열어볼 상자의 번호를 n비트로 적어서, 그 번호에 해당하는 상자를 연다. 다만, 여는 동작을 하기 전에 가능한 2n개의 n비트 번호들을 양자 중첩 상태로 만들어서 이들을 각각 열면 될 것이다. 하지만, 비슷한 일을 확률적 알고리즘으로도 마찬가지로 수행할 수 있다: 동전을 n번 던져서 상자의 번호 n비트를 모두 결정한 뒤에, 결정된 번호의 상자를 열면 된다. 2n개 모든 상자를 여는 행위의 발생 가능성이 확률적으로 '중첩'되어 있고, 각각의 상자에 대해서 그 상자를 열고 공을 발견할 확률이 0보다 크기 때문이다.
위와 같은 말을 들으면 거의 누구라도 '하지만 그렇다면 상자를 열어서 공을 발견할 확률은 기하급수적으로 작은 2-n밖에 되지 않으므로 사실상 못 찾는다고 봐야겠네요'라고 곧장 반박할 것이다. 물론 그렇다. 그리고 정확히 같은 반박을 양자컴퓨터에 대해서도 적용할 수 있다. 확률적 알고리즘도 가능한 모든 상태의 확률적 중첩을 만들어낼 수 있지만 그렇게 하면 각각의 상태가 갖는 확률이 기하급수적으로 작아져서 의미없는 알고리즘이 되듯이, 양자알고리즘 또한 가능한 모든 상태의 양자적 중첩을 만들어낼 수 있지만 그렇게 하면 각각의 상태가 갖는 '진폭(amplitude)'이 기하급수적으로 작아져서 의미없는 알고리즘이 된다.
양자 알고리즘과 확률적 알고리즘의 가장 근본적인 차이점은, 가역성과 확률의 보존성이다. 양자역학의 확률 진폭은 음수일 수 있을 뿐만 아니라, 심지어 실수뿐만이 아닌 허수까지 포함해서 복소수일 수도 있다. 이들은 중첩의 원리에 따라 서로 상쇄될 수 있다. 그리고, 진폭의 절댓값의 제곱이 확률이 되고, 확률의 총합은 1로 보존되므로, 어떤 상태의 진폭이 상쇄되어 0이 된다면, 다른 상태의 진폭은 커져야 한다. 이러한 방식으로, 양자 컴퓨터는 오답을 상쇄시키고 정답을 증폭시킬 수 있다. 반면 고전 컴퓨터는 비가역적이라서 확률적 알고리즘에 따라 확률 진폭을 상쇄시키면 그대로 정보가 사라져 원래 정보를 복원시킬 수 없다. 따라서 고전 컴퓨터를 사용한 연산에선 확률이 보존되지 않아 정답의 확률만을 증폭시킬 수 없다.
양자역학을 설명할 때 아주 초반에 나오는 이중 슬릿 실험의 예를 생각해보자. 고전적인 상식에 의하면, 빛이 1번 슬릿 또는 2번 슬릿을 통과한 뒤에 스크린의 어딘가에 떨어질 확률 분포는, 빛이 1번 슬릿을 통과한 뒤에 스크린의 어딘가에 떨어질 확률 분포와 2번 슬릿을 통과한 뒤에 스크린의 어딘가에 떨어질 확률 분포를 더해놓은 형태가 되어야 할 것이다. 하지만 실제로 이 실험을 수행해 보면, 어떤 위치에서는 두 개 슬릿을 다 열어둘 때에 오히려 광자가 올 확률이 떨어지는 현상이 발생한다. 모두 0 이상인 확률로 계산을 하면 정보의 손실이 생겨서 이런 결과가 나올 수가 없지만, 복소수 값을 갖고 음수 값을 가질 수 있는 진폭으로 계산을 하면 이런 결과는 자연스럽게 발생할 수 있다.
비록 확률진폭의 절댓값의 제곱만이 물리적 의미를 가지며 복소수의 확률파동 자체는 물리적 의미가 없지만, 이들의 비물리적 성질이 계산에 활용될 때에는 오히려 커다란 이점이 된다.
양자컴퓨터는 컴퓨터니까 고전 컴퓨터가 할 수 있는 일들을 대부분 할 수 있고, 경우에 따라서는 같은 문제를 고전적인 컴퓨터에서 알려진 최선의 알고리즘보다 훨씬 더 빨리 풀기도 한다. 하지만 이는 소위 '처치-튜링 명제'를 뛰어넘는 능력을 양자컴퓨터가 가지고 있다는 의미는 아니다. 즉, 양자컴퓨터가 할 수 있는 계산은 고전컴퓨터도 시뮬레이션을 통해 따라하는 것이 가능하다. 다만 시뮬레이션의 속도가 느릴 뿐이다.
오히려 자명하지 않은 부분은 반대 방향이다. 고전컴퓨터가 할 수 있는 일은 과연 양자컴퓨터가 다 할 수 있는가? 양자컴퓨터는 비싸니까 당연히 더 좋을 거라고 생각하면 속은 편하겠지만, 여기에는 한 가지 문제가 있다. 양자역학에 의하면, 양자역학적인 시스템은 '유니터리'한 방식으로 밖에는 변화할 수 없다. 유니터리 행렬은 항상 역행렬을 갖고, 따라서 역변환이 가능하므로, 계산의 결과로부터 계산의 입력값을 되찾는 것이 가능해야 한다. 그런데 함수 f(x)가 일대일이 아니라면, x라는 입력으로부터의 계산 결과가 y가 나왔을 때에, 해당 y에 대응하는 원래의 오리지널 x가 꼭 하나만 있을 필요가 없다. 예를 들어, 거듭제곱 함수 f(x)=x2를 생각하면, f(x)=f(-x)=x2가 되므로 x로부터 y가 나왔다고 해도 원래의 입력이 x였는지 -x였는지 알 방법이 없다. 즉, x로부터 y를 구하는 과정은 비가역적일 수 있다. 세상에는 고전 컴퓨터가 멀쩡하게 계산을 잘 하는 비가역적인 간단한 함수들이 널려있고, 이런 함수들은 아무리 간단해도 양자컴퓨터가 계산하지 못한다.
다만, 당연히도 이런 문제를 피해가는 방법이 있다. x로부터 f(x)를 구하는 대신에, x로부터 (x, f(x))를 구하면 된다. 즉, 양자컴퓨터가 일대일이 아닌 함수를 계산할 때에는, 출력과 함께 원래의 입력을 같이 출력하면 된다. 정보의 손실이 없으므로 이 입력과 출력의 관계는 일대일이 되므로, 이 비가역성의 문제를 비켜갈 수 있다. 하지만 그렇다고 해서 그런 방식으로 양자컴퓨터가 고전컴퓨터가 할 수 있는 일을 모두 다 시뮬레이션할 수 있는지는 결코 자명한 문제가 아니지만, 결론만 말하자면 가능하다. 모든 고전적인 계산은 가역적인 방식으로, 엔트로피의 손실 없이(열을 내지 않고) 처리하는 것이 가능하다는 사실이 알려져 있고, 그러한 가역적인 계산은 양자컴퓨터도 수행하는 것이 가능하다. 따라서 양자컴퓨터는 고전컴퓨터가 할 수 있는 일을 최소한 고전컴퓨터만큼의 속도로는 처리할 수 있다. 최소한 이론적으로는.
그 다음의 문제는, 양자컴퓨터가 같은 문제를 고전컴퓨터보다 더 빨리 계산할 수 있느냐이다. 이는 문제에 따라 다르다. 풀어야 할 문제 자체에 그러한 규칙성이 별로 없는, 예를 들어 앞에서 언급한 2n개의 상자를 여는 문제 같은 경우에는 (상자 한 개를 연 결과가 다른 상자를 연 결과에 대해서 무엇을 말해주겠는가. 별로 말해줄 것이 없다.) 정답의 확률 진폭을 끌어올리고, 오답의 확률 진폭을 죽여버리는 작업이 필요한데, 이는 당연히 공짜가 아니다. 요약하자면, 그로버 알고리즘에 의하면, 대략 2n/2번 정도 상자를 '양자적으로' 열어 보면 공이 어느 상자에 있는지를 유의미한 확률로 맞힐 수 있다. 이는 고전적인 결과에 비하면 엄청난 개선이지만, 여전히 지수적인 속도 향상이 아니라 다항식적인 속도 향상에 불과하다. 그리고 상자를 열어서 공을 찾는 문제의 경우에는 사실상 이 알려진 알고리즘이 최선이라는 사실이 증명되어 있고, 이것이 아마도 양자컴퓨터가 임의의 NP 문제를 다항식 시간 내에 풀지는 못할 것으로 보인다는 추측의 근거가 된다.
하지만 어떤 문제들은 양자컴퓨터가 기존에 알려진 고전 알고리즘보다 지수적으로 빠른 계산을 해낼 수 있다는 사실이 알려져 있다. 소인수분해, 이산 로그 등이 그러하다. 이러한 속도의 향상은 양자 중첩, 병렬성에서만 나오는 것이 아니다. 확률 진폭이 서로 상쇄가 가능하다는 것이 주된 원인이다. 소인수분해나 이산 로그를 효율적으로 풀 수 있으면, 현대 암호학의 공개키 알고리즘의 적지 않은 부분들을 깰 수 있기 때문에 이는 현재까지 알려진 양자컴퓨터의 가장 유력한 '킬러 어플리케이션'이다.
쇼어 알고리즘은 소인수분해를 [math(O(\log^3 n))]번만에 풀 수 있는 양자 알고리즘이다. 고전적으로 알려진 (여태까지의) 최선의 알고리즘 [math(O(\exp(\sqrt[3]{\frac{64}{9}}(\log^{\frac{1}{3}} n )(\log(\log n))^{\frac{2}{3}})))]보다 지수적인 속도 향상이 있었다. 여담으로 쇼어 알고리즘 중 실제로 양자컴퓨터가 쓰이는 부분은 합동식 형식의 RSA 암호화로 a,N이 주어졌을 때 [math(a^b\equiv 1\left(\text{mod}\,N\right))]을 만족하는 주기성을 갖는 b를 찾는 부분으로 특수한 꼴의 이산로그를 푸는 셈이다. 나머지 과정은 확률상쇄를 필요하지 않는 분석이어서 일반적인 컴퓨터로도 충분히 시뮬레이션이 가능하다.
양자컴퓨터가 고전 컴퓨터에 비해 확실하게 독보적으로 우월한 것은 양자역학적인 시스템을 시뮬레이션하는 것이다. 이거야 말로 에뮬레이션과 네이티브 실행을 비교하는 격이다.
양자컴퓨터가 다항식 시간에 풀 수 있는 문제의 집합을 BQP라고 하는데, 이와 NP와의 관계는 아직 정확히 밝혀지지 않았다. 양자 검색 문제를 양자컴퓨터가 다항식 시간에 풀지 못한다는 사실이 증명되어 있기 때문에, 아마도 NP가 BQP에 포함되지는 않을 것이라고 본다.[12] 그렇다면 반대방향은 어떠한가? 즉, BQP는 NP에 포함되는가? 다른 말로, 양자컴퓨터가 할 수 있는 일은 비결정적 컴퓨터가 모두 할 수 있는가? 역시 아직까지 확실하게 알려진 것은 없으나 아마도 BQP는 NP에 속하지 않는 문제를 담고있을 것이라고 본다. 뿐만 아니라, BQP는 PH, 즉 polynomial hierarchy도 벗어날 것으로 추측한다. 이에 대해서는 다음을 참고. 정리하면, BQP와 NP, 다른 말로, 양자컴퓨터와 비결정적 컴퓨터는 (아직 정확히는 모르지만) 서로 상대방보다 더 효율적인 부분이 있을 것이라는 말.
4.3. 보안
| 그래서 양자컴퓨터는 왜 빠른 걸까?[13] |
간단한 예시로 치환하여 설명하자면 다음과 같다. 1103 * 1117 = ? 이 문제를 푸는 데에는 그리 오랜 시간이 걸리지 않을 것이다. 간단한 곱셈이니까. 그런데 1232051을 소인수분해 하면? 이 문제를 푸는 데에는 앞의 문제에 비해 정말 오랜 시간이 걸릴 것이다. 실제로 1232051 = 1103 * 1117 인데, 1103과 1117이 둘 다 소수라 분해하기가 매우 힘들다. 쉽게 말해 곱셈보다 나눗셈이 더 어렵다는 것은, 인간의 수준에서도 그렇고 컴퓨터의 수준에서도 그렇다는 것이다. 바로 이 점을 이용하여 현재의 보안시스템 알고리즘이 체계화되어 있다고 생각하면 된다.
2023년 현재의 컴퓨터에서도 이러한 알고리즘을 해킹하는 데에는 너무나 오랜 시간이 걸린다. 예를 들어 1994년 RSA129로 알려진 129자리 숫자(426비트)를 소인수분해하는 데에는 알고리즘을 이용하여 세계에 있는 1,600여 대의 워크스테이션을 병렬로 연결해도 8개월이 걸렸다. 이 알고리즘을 사용하는 경우 250자리의 수(829비트)라면 800,000년이 걸릴 것이며, 1,000자리라면 1,025억년이 걸릴 것이다.[14] 이것은 우주의 나이보다 몇 배는 더 많은 시간이다.
하지만 양자컴퓨터라면 앞서 이야기했듯이 순식간에 계산되므로 현재 사용되는 보안 알고리즘은 더이상 사용할 수 없고, 우리가 사용하는 시디키도 마찬가지로 소인수분해 알고리즘을 사용하기 때문에 무한정 복사기마냥 시디키를 복제해서 찍어낼 수 있게 된다. 2011년의 양자컴퓨터는 겨우 21을 소인수분해하는 데 성공한 수준이었지만, 컴퓨터 분야의 발전 속도는 이쪽 방면 학자들의 상상마저 초월하는 경우가 많다.[15]
소인수분해 문제 이외에도 수많은 암호 알고리즘이 바탕을 두고 있는 이산로그 문제 역시 양자컴퓨터로 해결할 수 있다. 따라서 양자컴퓨터가 본격적으로 실용화되면 현재까지 개발된 대부분의 암호 알고리즘이 쓸모없어지게 된다.
그렇다고 양자컴퓨터가 모든 암호 문제를 박살내는 건 또 아니다. 양자컴퓨터가 NP-완전 문제를 다항 시간에 풀 수 있다는 잘못된 인식이 널리 퍼져 있으나 확실히 증명된 바는 없다. 그리고 컴퓨터가 진화했던 만큼 더 안전한 알고리즘을 만들면 되기 때문에 기존과는 차원이 다른 보안 알고리즘을 사용할 가능성이 남아있다. 게다가 현재 제안된 알고리즘들 중 격자 기반(lattice based) 암호계는 아직 양자컴퓨터로 해결할 알고리즘은 없다.[16] 따라서 양자컴퓨터가 실용화된다면, 그리고 그때까지 격자 기반 알고리즘을 양자컴퓨터로 해결할 알고리즘이 개발되지 않는다면, 격자 기반 알고리즘이 공개키 암호계의 대세를 차지하게 될 가능성도 있다. 그 외에도 AES와 같은 블록 암호들 역시 아직 양자컴퓨터로 깨뜨릴 알고리즘이 나오지 않았으므로 현재로서는 '양자컴퓨터가 급격히 실용화되더라도' 안전하다고 볼 수 있을 것이다. 결정적으로 폰 노이만 구조의 한계를 그대로 답습하고 있는 한, 모든 NP문제를 P 시간에 풀 수 있을 거라고 장담할 수도 없다.
양자 겹침과 얽힘 현상을 충분히 유지시킬 수 있다면, 큐비트 전송은 이론적[17]#으로는 무적의 전송기술이 된다. 외부에서 큐비트 정보에 접촉했을 때, 큐비트들은 큐비트의 성질을 잃어 전자적 상태로 돌아간다.(0 또는 1이 된다.) 이것을 수송신자는 바로 알아차릴 수 있으며, 그 정보를 수정/폐기하고 침입자를 제거하는 것으로 보안성을 크게 높인다. 침입자도 1회의 침입으로는 정보를 알아낼 수 없기에 헛수고가 되는, 신뢰성 높은 보안방식이다.
양자 컴퓨터 자체와는 큰 관련이 없지만 양자를 보안에 활용하는 기술은 이미 상용화되어 쓰이고 있다. 주로 통신망이나 서버망에 사용되는데, 양자의 무작위성을 이용해서 예측 불가능하고 패턴이 없는 난수를 생성하여 개인정보나 금융거래 정보 등이 담긴 통신을 할 때 사용된다. 해당 기기가 통신사에서 금융거래할때나 쓰는 등 B2B[18]에서만 사용되고 B2C[19]에서 쓰이는 일은 없었는데, 갤럭시 A 퀀텀이 SKT와 삼성이 함께 개발한 2.5x2.5mm 규격의 초소형 저전력 칩셋을 탑재한 채로 출시하면서 개인기기에서의 상용화가 실현되었다. 기존 고전컴퓨터의 난수생성 알고리즘이 생성하는 난수는 순수한 난수가 아닌 의사난수에 불과한데 해당 칩은 전력의 랜덤발생을 이용하기 때문에 패턴이 없는 순수한 난수를 생성할 수 있다. 이렇게 해당 칩에서 생성된 순수 난수를 사용하여 통신을 할 경우 현재 기술로는 해킹이 불가능하다는 장점을 가진다.[20]
이와 관련해서 비트코인 등의 암호화폐가 양자컴퓨터가 대중화될 시 보안이 취약해질 것이라는 우려가 나타나고 있다. #
5. 실용화 가능성
아직까지는 일상에서 쉽게 활용할 정도로 실용화되기엔 많은 시간이 남았다고 할 수 있다. 그 근본적인 이유는 일단 현재 인류가 가진 기술로는 양자를 효과적으로 통제하기 어렵다는 것.
현재의 기술로는 양자로 구성되는 큐비트를 충분한 시간 동안 유지시킬 수가 없고, 외부 환경의 경미한 영향에 의해 큐비트가 변형되는 것을 막을 수가 없다. 일단 IBM이 만드는 범용 양자컴퓨터의 프로세서나 D-WAVE가 만드는 양자 어닐링 컴퓨터의 프로세서는, 큐비트를 최대한 오랜 시간 동안 유지시키기 위해 절대영도에 근접한 극저온 + 진공상태에서 전기 저항이 0이 되는 초전도체를 주재료로 만드는데, 이로 인해 제조단가가 무지막지하게 올라가고 작동시에는 초전도 상태를 유지해야 하므로 우주환경을 조성할 수 있는 진공 냉각장치가 요구되기 때문에 운용 비용도 상당히 비싸다. 또, 큐비트가 외부 환경에 의해 영향을 받는 것을 차단하기 위해 고도의 방음, 차진 설비를 두어야 하기 때문에 컴퓨터의 부피도 매우 크다. 또한, 현재는 큐비트를 고도로 집적시킬 수 있는 기술이 아예 없기 때문에 아주 제한된 수준의 컴퓨팅 성능만을 이끌어 낼 수 있는 것으로 알려져 있다.
이러한 문제를 해결하기 위해서는 일단 큐비트를 항구적으로 유지할 수 있는 기술을 개발해야 한다. 큐비트만 항구적으로 유지하고 효과적으로 통제할 수 있다면 굳이 프로세서를 제조하는 데 초전도체를 사용하지 않아도 되고, 외부 환경에 의해서 변형되는 것도 어느 정도 관리할 수 있기 때문이다. 큐비트 안정화에는 마요라나 페르미온이라는, 물질과 반물질의 경계에 있는 특수한 입자가 도움을 줄 수 있을 것으로 기대 되었는데, 특히 마이크로소프트가 이 입자에 주목해 이를 이용한 궁극의 양자 컴퓨터 개발을 연구하고 되는 중이었다.
허나 마이크로소프트의 연구진들이 출간한 관련 논문에 대한 신빙성 논란이 잇따랐고, 결국 Nature는 전문 외부 조사단을 창설하였으며 2021년 3월 8일 조사단이 발표한 조사 결과에 따르면 논문의 저자들이 지나치게 낙관적인 해석을 하였다고 한다. 이에 Nature는 과학적 엄밀성 부족[21]을 근거로 마이크로소프트 연구진들이 낸 마요라나 페르미온에 대한 논문을 공식적으로 철회하였다. 허나 이는 해당 논문이 마요나라 페르미온, 그 자체를 부정하는 것이 아닌 마이크로소프트 연구진이 자신들의 실험에서 해당 현상을 만들었다고 주장하며 Nature에 기재한 논문이 철회된 것이다. 실제로 마요나라 페르미온은 이론적 주장 이후 80년 동안 발견되지 않고 있다가 2012년 네덜란드 에인트호번 대학을 시작으로 한국의 포스텍, 미국 스탠포드 및 캘리포니아 대학교, 일본 교토대 연구팀들이 잇따라 마요라나 페르미온의 존재를 실증하거나 관측하는데 성공했다. 또한 마이크로소프트 연구진은 논문 철회 이후에도 연구를 지속하여 마요라나 페르미온을 양자컴퓨터에 적용하는 실험적 테스트를 여전히 수행하고 있다. 2022년 3월자(논문 철회 1년 후) 관련 기사
일단, 양자 컴퓨팅을 사용하려는 목적은 성능 자체보다는 큐비트 프로세싱의 알고리즘적 특성에 있기 때문에 성능은 당장 문제가 되지는 않는다고 한다.
한편, 소프트웨어도 심각한 문제가 될 것이라 전망되었다. 양자 연산은 기본적으로 양자의 성질에 의해 확률적인 값을 갖게 되는데 이 때문에 정확도가 떨어져 오류가 발생하기도 한다. 이런 오류를 최소화 하는 것이 소프트웨어를 이루고 있는 양자 알고리즘의 과제이다. 현재 이 문제를 해결하기 위해 투입되고 있는 알고리즘으로는 대표적으로 쇼어 알고리즘이 있다.
일단 현재 수준에서는 양자 컴퓨터가 실용화된다고 하더라도, 단순한 수학적 계산에만 활용되는 수준이며, 엔드 유저 입장에서는 게임은 커녕 워드프로세서도 사용할 수 없는 수준이다. 다만 현재처럼 반도체 공정이 계속해서 극미세 단계로 접어들게 되면 반도체의 한 비트 할당 공간이 분자, 원자, 소립자 단계까지 내려가게 되는데, 이때는 전기 동력원인 전하보다 회로가 더 작아지는 사태가 발생할 수 있다.[22][23] 이렇게 될 때의 대안이 바로 양자 메커니즘에 의한 컴퓨팅이다.
2016년 5월 4일, IBM에서 자사 클라우드에서 양자컴퓨터를 사용할 수 있게 하였다. 양자 게이트들의 조합을 업로드하면 5bit 양자컴퓨터가 실행해서 계산 결과를 알려주는 방식 http://www.research.ibm.com/quantum
양자컴퓨터만 사용하는 시대가 온다는 것은 아직까지는 가능성이 매우 낮다. 두 종류의 컴퓨터가 서로 얻고자 하는 결과값을 얻고자 할때 최적화 된 중간과정이 다를뿐더러[24] 양자컴퓨터만으로 현대 컴퓨터의 모든 기능을 대체한다는 것은 에뮬레이터, 가상머신을 구동하는 것과 같은 매우 낮은 효율을 보여주게 된다. 결국 이와 같은 문제를 해결하기 위해서는 양자 컴퓨터와 기존의 폰 노이만 컴퓨터가 서로 상호 보완해주는 시대가 올 가능성이 높다.
5.1. 양자 우위와 오류
양자 우위(quantum supremacy)란 양자 컴퓨터가 기존의 디지털 컴퓨터의 성능을 앞지르는 것이다. 미국 물리학자 존 프레스킬(캘리포니아공대 교수)가 처음 사용한 개념이다. 50 큐비트의 양자 컴퓨터라면 양자 우위를 달성할 수 있다고 알려져 있다.Intel ISEF 2019 systems software 부문에 출품된 양자컴퓨터 시뮬레이터 초록에 따르면, 25 큐비트 기준 기존 푸리에 변환연산의 120배 이상의 속도를 달성한 것을 알 수 있는데, 고등학생이 주변 대학교의 슈퍼컴퓨터를 빌려서 했더라도 대학에 있는 슈퍼컴퓨터와 세계 10위 권 이내의 슈퍼컴퓨터의 성능차이는 상당하고, 컴퓨팅 아키텍처가 지속적으로 발전하고 있는 만큼, 단순히 물리적으로 50 큐비트의 시뮬레이션이 불가능하다고 단정지을 수는 없다.
2018년 3월, 구글에서 브리슬콘이라고 명명된 72 큐비트 양자컴퓨터를 선보였지만 아직 양자 우위에는 도달하지 못했다는 의견이 있다. 양자 오류라고 불리는 현상 때문이다.구글 , 양자컴퓨터 개발 새 장...72큐빗 칩 선보여 참고.
외부 환경의 영향을 받지 않도록 완전하게 격리된 채 연산을 실행해야 하는 매우 민감한 조건의 양자 프로세서 칩에서는 불가피하게 연산 오류가 생기는데, 이런 양자 오류를 보정하는 데에는 또 다른 보정용 큐비트들의 기술과 비용이 추가로 들어간다.
양자 컴퓨터 전문가들은 논리 연산에 쓰이는 큐비트 1개가 오류 없이 보호를 받으며 실행하는 데에는 양자 오류 보정용으로서 수백 내지 수천 큐비트가 추가로 필요할 것으로 보고 있다. 왜냐하면 오류보정도 양자연산으로 이루어지므로 여기서 추가적인 오류가 들어오기 때문이다. 구체적인 회로 구조에 따라 다르지만 브리스콜 같은 2차원 격자 구조의 경우 오류율이 0.7%를 넘는 경우 오류보정을 하면 오류가 오히려 늘어나는 경향을 보인다. 현재 50 내지 수백 큐비트 규모의 시스템에서는 이런 오류 보정이 적절하게 이뤄지기 힘들다는 것이고, 이런 상황에서는 양자 컴퓨터가 내놓은 답이 과연 정확한 답인지 확인하기도 어렵다는 것이다.[25] 프레스킬 교수는 연산 알고리즘에서 오류를 보정하면서 수천 큐비트를 연산에 쓰려면 수백만 개의 큐비트가 더 필요할 것이라고 추산했다. 참고.
수학자 길 칼라이(Gil kalai)는 양자 오류를 보정하는 것이 불가능하다고 주장한다. 수학자 길 칼라이가 양자컴퓨터가 동작하지 않을 것이라 생각하는 이유에 자세한 내용이 나와 있다. 칼라이의 주장에 따르면, 자신의 의견은 소수 의견에 속하지만 상당한 확신을 가지고 있다고 한다.
2019년 모스크바 물리 기술 연구소(MIPT)의 러시아, 미국, 스위스 공동 연구 팀은 시간 역행 알고리즘을 이용한 양자 오류 보정 방법을 사이언티픽 리포트에 보고하였다.#
2019년 9월 20일 구글이 양자우위에 도달했다는 발표가 있었다. 구글은 여기에 대해 공식적으로 긍정도 부정도 하지 않고 있다. https://www.cnet.com/news/google-reportedly-attains-quantum-supremacy/?utm_source=reddit.com
2019년 10월 23일, 구글은 네이처에 양자우위에 도달한 양자칩인 일명 '시커모어' 에 대한 논문을 발표했다. 9월에 나사에서 발표했다가 사라진 정보를 기준으로 하면, 기존 슈퍼컴퓨터가 1만 년이 걸리는 계산을 2분 30초 내로 계산할 수 있는 성능에 도달했다고 한다. 하지만 양자컴퓨터를 개발하는 경쟁사인 IBM의 연구소 내 전문가들에 따르면 구글은 기존 슈퍼컴퓨터의 성능을 너무 낮게 잡은 것으로, 실제로는 시커모어가 2분 30초 정도의 계산 시간으로 푼 문제는 기존 슈퍼컴퓨터가 이틀 정도 걸리는 계산 시간으로 풀 수 있다고 한다. 결론적으로 양자 우위에 도달했다고 보기에는 부족하지만 제한적인 영역에서 양자 컴퓨터가 기존 수퍼 컴퓨터를 훨씬 능가하는 성능을 보여준 것은 큰 성과라고 할 수 있다. https://news.v.daum.net/v/20191023155017935
사실 IBM이 구글의 양자우위 발표에 대해 상세히 논평할 수 있었던 배경은, 현재 양자 컴퓨터의 양자 게이트 언어를 IBM 양자컴퓨터 연구소에서 개발했기 때문에 구조를 간접적으로 알 수 있었기 때문이다. IBM이 개발한 양자 게이트는 양자 컴퓨터 연구의 표준으로 여겨지고 있다. http://www.research.ibm.com/quantum
2021년 3월, 중국 베이징의 연구팀은 60개의 그래픽카드를 5일 동안 가동하여 시커모어의 계산을 따라하는데 성공하였다. IBM은 실제 계산을 수행하지 않았으나 중국 연구팀은 계산을 실제 수행하여 양자우위를 반박했다.https://arxiv.org/abs/2103.03074https://www.scmp.com/news/china/science/article/3125539/chinese-scientists-challenge-googles-quantum-supremacy-claim-new
2021년 11월, IBM에서 127 큐비트의 양자 프로세서를 발표하였다. IBM은 2023년 즈음에 1121 큐비트의 양자 프로세서와 양자 우위를 달성할 것이라고 말하였다. https://www.tomshardware.com/news/ibm-127-qubit-eagle-quantum-processor
대신 2022년 말 IBM에서 433 큐빗을 가진 오스프리 양자 프로세서가 출시되며 기술의 지수함수적 발전속도를 보여주고 있다. 제대로 작동하는 수천큐빗 수준의 양자 프로세서를 이용하면 여전히 많은 기관에서 쓰이고 있는 2048 비트 규모 RSA 암호화의 브루트포스 공격이 현실화 될 수 있기에 귀추가 주목된다.
2023년 말 IBM이 최초로 1000 큐빗이 넘는 양자 프로세서를 개발해냈다. https://www.nature.com/articles/d41586-023-03854-1
5.2. 위상학적 양자 컴퓨팅
6. 이온트랩 양자컴퓨터
Trapped ion quantum computer포획된 이온 양자컴퓨터라고도 한다. 이온트랩은 초전도체의 인공 큐비트의 방식이 아닌 자연 그대로의 큐비트를 사용하며, 정확성이 매우 뛰어나고 실제로도 업계 최저 수준의 오류율을 보여주고 있다. 큐비트의 숫자를 중요시 하는 초전도체 방식과 다른점은 큐비트의 질적 우월성을 강조하는 방식이라는 점이다. 전하를 띈 원자인 이온을 전자기장을 통해 붙잡아두는 장치인 이온트랩을 통해서 양자회로를 구성한다. 이온을 통해 만들어진 큐비트는 두개의 이온에 레이저를 조사해서 양자중첩과 양자 얽힘을 생성해 양자회로를 구성한다. 또한 포획된 이온이 장시간 유지하기에 용이하고 상온에서도 작동하는 것으로 알려져있다.
7. 상용 제품 개발
양자컴퓨터에 대한 연구는 현재까지 미국과 중국이 가장 앞서가고 있으며 그외 유럽(EU),일본,핀란드를 중심으로 연구 되고 있는 것으로 알려져 있다. 참고로 한국은 2023년 10월 양자 과학기술 및 양자 산업 육성에 관한 법률이 이제 막 통과되었다. 양자분야는 스타트업이 진입하기 매우 여려운 분야이며 엄청난 연구비용과 인력비용이 드는 분야인 만큼 이미 어느정도 성숙해진 기업이 우위를 차지할 가능성이 높다. IBM이나 구글, 마이크로소프트, 인텔 등 기존 컴퓨터 회사에서도 많은 인력을 동원하여 양자컴퓨터를 연구하고 있으며, 아이온큐나 리게티 디웨이브등 초창기 양자분야에 뛰어든 스타트업에서도 많은 연구개발비와 인력등을 동원하며 노력하고 있다.7.1. D-Wave 시리즈
2011년 캐나다의 D-Wave 시스템즈라는 회사에서 양자 어널링을 이용한 특수목적형 컴퓨터인 D-Wave 1을 출시하였지만, 이는 여기에서 이야기하는 범용 양자 컴퓨터와는 좀 다르다.7.1.1. D-Wave 양자 어닐링(quantum annealing) 컴퓨터
D-WAVE는 도쿄공업대학의 니시모리 히데토시(西森秀稔) 교수가 만든 양자 어닐링 개념을 이용해 캐나다에서 개발한 대체한 특수목적형 컴퓨터로서 궁극적인 목표인 양자게이트를 사용하는 범용 양자 컴퓨터와는 거리가 멀다. 128-qubit 프로세서를 사용하며, 크기는 10m2(...)약 3평 정도 극저온 냉각 시스템 때문에 저런 크기가 나온 듯하다. 개발 회사에서는 정부 및 회사용으로 생각하고 개발한 듯.양자암호통신의 대가로 유명한 IBM의 John Smolin은 이 컴퓨터는 양자 컴퓨터라 부를 수 없다고 말했으며, 양자 어닐링 관측을 통한 해당 컴퓨터의 실질적인 성능도 기존 어닐링 방식과 비교해봐도 우월할 것이 없다는 얘기를 했다. 실제로 비교 실험에서 이 컴퓨터의 우월성은 증명되지 않았고 심지어 기존의 어닐링 방식보다 느리기도 했다.
D-WAVE사 컴퓨터의 구입처 중 하나인 구글의 엔지니어들이 발표한 논문에 따르면 2000큐비트 모델인 D-Wave 2X 의 경우 싱글코어 컴퓨터의 1억 배에 해당하는 속도를 보였다.
미국의 방위산업체인 록히드마틴에서 100억 원에 구입했는데, 얼핏 돈지랄 같지만 기업 입장에선 싼 거다.# 이후 구글 및 NASA 역시 D-WAVE의 컴퓨터를 구입했다.
2011년 D-Wave Systems 사에서 D-Wave 1을 발표하였다. 가격은 약 천만 달러. 하지만 D-Wave 1은 일반적으로 알려진 범용 양자 컴퓨터는 아니며[26] 특정한 종류의 최적화 문제에 특화된 하드웨어를 갖고 있다. 양자 어닐링을 이용하는 특수목적형 컴퓨터이며, 양자 어닐링은 기존 어닐링 방식에 비해 특별히 나은 성능을 지니는지에 대해서도 아직 확실하게 알려져 있지 않다. 관련내용 참고.
2013년 7월, 구글과 NASA가 공동 설립하는 인공지능 연구소에서 차기 모델인 D-Wave 2를 구매하였으며, NASA에서는 우주 관련 연구, 구글에서는 인공지능 검색엔진 개발에 사용할 것이라고 밝혔다.
D-Wave 2는 512-qubit 프로세서를 사용한다고 알려져 있는데, 이것이 양자 중첩 현상을 이용한 기존의 정의대로 만들어진 물건이라면 이는 이론적으로 2^512(약 2*10^212)번의 계산을 한번에 할 수 있는 속도이다. 더 놀라운 건 D-wave1이 나온 지 2년 만에 성능이 4제곱만큼 좋아졌다는 것. 문제는 이 컴퓨터는 양자 어닐링을 관측하는 방식으로 만들어졌을 뿐이지(양자 터널 현상은 이용한다) 양자 중첩 현상을 이용한다는 기존 양자컴퓨터의 정의와는 전혀 다르다.
2014년 1월 16일(현지시각) 실시한 이 양자 어닐링 컴퓨터의 성능 테스트 결과가 기존 시스템을 이용한 고전적인 어닐링 연산과 크게 다르지 않은 것으로 알려졌다.
이번 성능 테스트에는 D-Wave 2와 일반 PC를 이용했다. 비교를 진행한 결과 D-Wave 2는 양자 어닐링의 장점을 증명하지 못했고 일반 컴퓨터와 크게 다르지 않은 결과를 냈다고 한다. 그럼에도 불구하고 구글은 나사와 D-Wave 2를 구입하여 나사 연구 센터에 설치했다. 하지만 이 시스템이 실제로 사용된 건 구글글라스 눈꺼풀의 깜박임을 감지하는 알고리즘 작성 정도다. 많은 물리학자들이 해당 컴퓨터를 이런저런 기관에서 구입하는 것에 대해 의문을 표하고 있다.
스위스 취리히연방공대의 마티아스 트로이아 교수의 연구에서 상용화된 D-Wave Systems 사의 양자 어닐링 컴퓨터가 기존의 컴퓨터보다 몇몇 경우에는 100배 이상 연산이 느리다는 연구 결과가 나왔다. 번역 링크
확실한 것은, 해당 컴퓨터가 양자 어닐링을 관측하는 방식으로 만들어졌다는 것, 그리고 기존의 양자 컴퓨터와는 전혀 다른 물건이라는 것이다.
7.1.2. D-Wave 2X
1097 큐비트 모델이다. 위 모델처럼 제한된 특수목적용인지, 실제 성능은 어떤지는 아직 알려져 있지 않다. 다만 현재 관련 연구 진척을 보면 범용 양자 컴퓨터일 확률은 거의 제로이다.2015년 말, 구글과 나사에서 특정 알고리즘[27]에서 일반컴퓨터 보다 약 1억 배 더 빠르다고 주장하는 양자컴퓨터의 실물을 공개했으며, 2016년 9월에 에임스 연구소의 양자 인공지능 연구소에 설치가 완료될 예정이다.
작동 환경은 열, 전기장, 자기장, 진동을 철저히 격리하고 절대영도보다 약간 높은 0.015 K(켈빈)을 유지한다. 이는 우주의 온도인 약 3K 보다 낮은 온도이다.
속도 테스트는 양자컴퓨터에 맞춰 주의깊게 고안된 '개념 증명용' 문제를 푸는 것으로 했으며 하이엔드 싱글코어 CPU를 비교군으로 했을 때 약 1억 배 더 빠르다는 것이 구글의 주장이다. 특정 유형의 문제를 다뤘기에 단순 일반화 할 수는 없지만 양자 컴퓨터의 잠재력을 입증하는 데 의미가 있는 것으로 풀이된다. DW2X에 대한 분석 자료
2016년 9월, 구글은 50큐빗급의 양자컴퓨터를 내년 말까지 선보이겠다고 발표했다. 관련기사
7.1.3. D-Wave 2000Q
D-Wave 는 2017년 1월에 2000큐비트 모델을 출시하였다. 관련정보판매가는 대략 1500만달러 수준이라고 한다.
7.2. Gemini 시리즈
2022년 중국 SpinQ에서 세계 최초 상용 PC형 양자 컴퓨터 Gemini 시리즈를 출시했다.
Gemini는 핵 자기 공명 (NMR) 기술을 기반으로 한다. 특정 물질에 고주파 방사선을 발사하면 물질 원자의 스핀 방향이 변경된다. 즉, 분자 내 원자의 스핀을 제어하고 인접한 원자가 각 원자와 상호 작용하도록 "강제"할 수 있다. 다른 원자의 스핀(0에서 1)과 이웃 원자의 스핀 상호 작용을 변경하면 수학적 연산을 시뮬레이션하고 결과를 얻을 수 있다.
크기는 일반 데스크톱 PC 크기이며 무게는 모델에 따라 14kg~55kg 내외이다. 부피가 작다는 한계로 보급형은 2 큐비트 고급형은 3 큐비트로 대형 양자 컴퓨터 보다는 성능이 떨어진다.
2021년 2월을 기준으로 국립타이완대학, 워털루 대학교, 베이징이공대학 등 중국, 대만, 일본, 미국에 위치한 20여개의 대학 및 연구기관에서 구입한 것으로 알려져있다.
판매 가격은 모델별로 다르며 최저 사양 모델이 8,700불~최고 사양 모델은 58,000불로 알려져있다.
가장 높은 성능의 모델이 3큐비트이다 보니, 일부 대학 및 연구 기관에서 사용하고는 있지만, 대부분 교육용으로 사용한다. 해당 사양에서의 실질적 연구개발은 힘들기 때문이다.
7.3. 기타 개발현황
- 2017년 1월, 최근 일련의 물리학자들이 주축이 되어, 대규모 양자컴퓨터 '건설' 계획을 추진하고 있다는 기사가 나왔다. BBC 기사
- 2017년 3월 7일, IBM에서 상용화 가능한 범용 양자컴퓨터 “IBM Q”를 몇 년 이내로 공개할 것이라고 발표하였다. http://www-03.ibm.com/press/us/en/pressrelease/51740.wss
- 2017년 9월 11일 중국이 세계 최대의 양자연구소를 지어 그 연구 결과물을 적군 암호 해독 등 군사 분야에 응용할 계획을 하고 있다.
- 2017년 10월 23일 IBM에서 49큐비트 양자컴퓨터 시뮬레이션에 성공했다고 발표했다. 이제는 양자우위의 차원을 넘어섰다는 평가다. 다만, 유용하게끔 되기까지는 시간이 걸린다고 한다. #1 #2
- 2018년 3월 초 구글에서 브리슬콘(Bristlecone)'이라 명명한 72 큐빗 칩을 선보였다. http://news.naver.com/main/read.nhn?mode=LSD&mid=sec&sid1=105&oid=092&aid=0002132902
- 2017년 마이크로소프트는 양자 컴퓨터의 프로그래밍을 위한 양자 프로그래밍 언어인 Q#을 발표하였고, 작성한 프로그램의 실행 확인을 위해 40 큐비트급 양자 컴퓨터를 애뮬레이팅해 제공하고 있다.
- 2019년 1월 9일, IBM에서 IBM Q라는 이름의 최초의 상용 양자 컴퓨터를 선보였다. https://techcrunch.com/2019/01/08/ibm-unveils-its-first-commercial-quantum-computer/?sr_share=facebook&utm_source=tcfbpage
- 2019년 9월 20일, 구글이 양자우위에 도달했다고 발표. https://www.cnet.com/news/google-reportedly-attains-quantum-supremacy/?utm_source=reddit.com 다만 IBM에서는 이 발표에 대해서 부정적인 입장을 표했다.
- 2019년 10월, 구글은 시카모어(sycamore)란 이름의 양자 컴퓨터를 만들고 테스팅한 결과를 네이처에 논문으로 발표했다. 53큐비트이며, 이후 2020년 8월엔 12큐비트로 화학 반응의 양자 시뮬레이션을 풀어 사이언스에 논문을 발표했다.
- 주요 급성장 기업에는 1위 Red Hat, 2위 Ionq, 3위 Beijing Baidu Netcom Science and Technology 등이 있다. https://wiki.patentpia.com/detail/89
- 2024년, 일본 산업기술종합연구소(AIST)는 미국 IBM과 공동으로 1만 큐비트급의 차세대 양자컴퓨터를 공동개발하기로 했다. #
- 2024년, 둠이 이식되었다.# 다만 최소사양이 약 7만3천 큐비트, 8천만 게이트, 6GB 램이 필요하여 2024년 기준으로는 최소사양 수준의 양자컴퓨터가 개발되지 않아 QASM 시뮬레이터로 실행했다.
8. 모방
양자컴퓨터는 개발이 어렵다는 난제를 안고 있어, 양자중첩의 원리를 모방하고자 하는 시도가 이루어지고 있다. 대표적으로 나노 크기의 자석을 이용한 피비트를 연산단위로 하는 확률컴퓨터가 존재한다.9. 창작물
아직 상용화되지 않은, 엄청난 성능의 컴퓨터...라는 이미지가 있어, 각종 창작물에 등장하는 슈퍼컴퓨터로써 양자 컴퓨터가 제시되고 있다.- 총몽시리즈의 양자컴퓨터
- 9S의 LAFI 시리즈
- 가사라키 - 24화 초반 미군의 도쿄 고와 그룹 본사 공격 브리핑에서 공격 목표로 언급된다. 냉각을 위해 영하 180도 이하의 극저온실에 위치해있다.
- 기동전사 건담 더블오의 베다
- 기동전사 건담 SEED 시리즈에서는 널리 보급되어있는 상태다. 일반적인 MS를 비롯한 시설의 컴퓨터도 모두 양자컴퓨터. 오히려 양자컴퓨터가 아닌 컴퓨터를 찾기 힘들다는 듯. 통신 또한 양자 통신을 사용해 지연없는 통신을 사용하는 중. 아스트레이의 하치는 양자 컴퓨터와는 다른 존재.[28]
- 고스트 리콘 브레이크포인트에서는 스켈 테크놀로지가 개발에 성공했다.
- 나노리스트의 방공용 양자컴퓨터. 홍싸리가 나노를 조종하는데 필요한 연산을 보조하기 위해 쓰였다. 나노의 동작 제어 시스템의 처리 데이터가 워낙 방대해 두 대씩이나 동원해야 했다.
- 데브스의 양자 컴퓨터
- 덴마의 양자 통신
- 붕괴3rd의 구 문명의 컴퓨터: 붕괴3rd에서 구 문명은 현 문명보다 훨씬 발전한 오버 테크놀러지 사회였으며, 당연히 양자컴퓨터도 존재했다. 또한 그 양자컴퓨터를 금속덩어리나 수은구슬 비슷한 형태 등 다양한 형상과 성질로 보존하는 것도 가능. 인게임 무기 중 복희의 서가 그런 양자컴퓨터 중 하나다.
- 소드 아트 온라인의 「STL」. 후술할 액셀 월드의 뉴로링커의 전신이다.
- Supreme Commander]의 시리즈에 등장하는 ACU에 기본 탑재돼있으며 UEF, 사이브런, 에이온 등 모든 진영에서 사용하는 건물에서조차 양자 컴퓨터를 사용한다.
- 아쿠다마 드라이브의 칸토: 칸사이와 벌인 전쟁의 여파로 황폐해진 주민들의 정신을 데이터화한 후 하나로 통합하여 양자 컴퓨터 안에 집어넣었다.
- 어떤 마술의 금서목록의 트리 다이어그램[29]
- 어떤 마술의 금서목록 신약 7권에 AIM확산역장을 이용한 양자컴퓨터가 등장한다.
- 제가페인의 양자서버(양자컴퓨터)
- 오리진의 합성지능 윈스턴이 양자컴퓨터에 본체를 두고있다. 이름은 E-WAVE 이다.
- 액셀 월드의 4세대 NERDLES.[30]
- 콜 오브 듀티: 블랙 옵스 2에 등장하는 셀레륨 장치. 에릭 브라이너의 말에 따르면 양자 얽힘을 이용했다고 한다.
- 톰 클랜시의 소설 넷포스 시리즈 세번째 작품인 나이트 무브에서 양자 컴퓨터가 등장해 세계 각지의 보안을 제집 드나들 듯이 돌아다니며 문제를 일으켰다.
- EDEN 프로퍼테일 연방이 관리하는 다섯 대의 스탠드 얼론형 양자컴퓨터. 개개의 이름은 나오지 않는다. 우주로부터 쏟아지는 감마선 폭우로 지구의 대기와 바다가 작살나자 이를 회복시키기 위해 한 과학자가 연구하던 나노머신 우라노스와 오케아노스가 방안으로 대두되는데, 실제로 사용하기 전에 양자컴퓨터로 지구 규모 시뮬레이션을 돌리는데 쓰인다. 나노머신을 개발한 과학자의 말로는 기상은 카오스계 이론이라 일반 컴퓨터로는 도저히 행성규모의 시뮬레이션을 할 수가 없었다고...
- 요르문간드 계획 - 양자 컴퓨터가 사용된 결과 하늘의 항공로가 통제된다.
- 트랜센던스 - 윌의 정신이 업로드 된 양자프로세서를 가진 슈퍼컴퓨터 : 본래 핀이라는 양자컴퓨터의 프로세서를 빼와서 윌을 우선 컴퓨터에 업로드 시키는 것을 성공한 뒤, 후에 대규모 데이터 센터를 건설하여 내부에 엄청나게 많은 양자 프로세서가 장착된 슈퍼컴퓨터에 윌이 들어간다.
- 바츠(레스큐 포스) -
- TYPE-MOON/세계관 - 문 셀 오토마톤이 양자컴퓨터다. 그것도 달 크기의.
- 블루 아카이브에 등장하는 아트라하시스의 방주와 우트나피쉬팀의 배는 우주선 내지는 세계를 파멸로 이끌 병기로 취급받지만 실상은 항행이 가능한 양자컴퓨터에 가깝다.
- 유랑지구 2에 550c라는 인공지능 양자컴퓨터와 그 후속작 550w(유랑지구 1의 '모스')가 나온다
10. 관련 문서
[1] 프로그래밍은 IBM에서 고안한 Qiskit이라는 Python 기반 언어로 한다. 127큐비트[2] 이를 큐비트라고 부르는데 Quantum bit를 Q bit라고 줄인 것으로 기존 컴퓨터의 정보 단위인 비트와 달리 여러 값을 동시에 가질 수 있다.[3] 다만, 모든 형태의 문제에 대해 이렇게까지 강력한 것은 아니고, 양자컴퓨터가 기존 컴퓨터보다 특화되어 수만 배 빠르게 해결하는 특정한 문제 종류들이 있다.[4] 쿠르츠게작트의 영상.[5] 양자컴퓨터 개념을 꺼내면서 덤으로 스트루가츠키 형제의 세상이 끝날때까지 아직 10억년의 우주가 양자역학적 계산기라고 했다.[6] Apple Silicon, 삼성 엑시노스 1000, 퀄컴 스냅드래곤/8XX 라인업 등 14나노 칩에서도 양자 터널링으로 인한 누설전류가 심각한 상황이고, 때문에 16nm 공정에선 FinFET 공정으로 잡을 수 있었던 누설전류가 GAAFET(Gate All Around)이나 MBCFET의 도입까지 고려하게 될 정도로 많았으나, FinFET 공정에서 EUV 공정을 적용시키며 한숨 돌린 상황. 다만 3nm부터는 EUV 공정 도입에도 불구하고 TSMC마저 수율과 누설전류 문제가 심해지고 있다.[7] 즉 필요한 기능들을 수행할 만큼[8] Nitrogen-Vacancy center in Diamond[9] 대부분 아다마르 변환이 사용된다.[10] 대표적으로 쇼어 알고리즘에 푸리에 변환이 사용되고, 그로버 알고리즘에는 오라클이라는 N차 특수 유니터리 행렬군, SU(N)가 사용된다.[11] 각각의 witness들에 대해 병렬적으로 이들이 올바른 NP witness인지 확인한다.[12] 사실 NP가 P에 포함되는지 조차도 아직 증명하지는 못했다. P-NP 문제 참조[13] 베리타시움 한국채널의 설명[14] 보안시스템 알고리즘에서 실제로 사용되고 있는 RSA 모듈러스는 대개 1024비트 혹은 2048비트의 크기이다. 일부는 4096비트도 사용하기도 한다.[15] 일반인들에게 어필할 수 있는 예시로, 우리 손 안에 있는 스마트폰의 연산능력은 1990년대의 슈퍼컴퓨터를 압도한다.[16] 격자 관련 문제들 중에는 NP 완전 문제가 있는 것이 사실이고, 아마도 양자컴퓨터가 NP 완전 문제를 다항식 시간 내에 풀지 못할 것을 시사하는 증거들이 있는 것을 감안하면, NP 완전성 때문에 격자 기반 암호가 양자컴퓨터에 대해 안전하지 않을까 생각되기도 하지만, 정확히 그렇지는 않다. 대부분의 경우, NP 완전 문제에서 출발하는 암호 시스템의 경우에도, 임의의 문제가 아니라 답을 알고 있는 문제를 생성해야 하기 때문에, 원래의 NP 완전 문제를 변형하는 과정이 들어간다. 즉, 현재까지 순수하게 그 안전성을 'NP 문제가 효율적으로 풀리지 않는다'는 가정에만 의존하는 암호 체계는 발견된 적이 없고, 이는 격자 기반 암호의 경우에도 마찬가지이다. 즉, 격자 기반 암호를 효율적으로 푼다고 해서 어떤 NP 완전 문제를 효율적으로 풀게되는 것은 아닐 가능성이 높다.[17] 실제로 2010년경에 양자암호의 취약점을 발견한 사례도 있다.[18] 기업과 기업 사이의 거래[19] 기업과 소비자 사이의 거래[20] 물론 기존 난수생성 알고리즘을 이용한 OTP 보안도 해킹된 적이 없는 등 기존의 보안 방식도 점점 강화되면서 이상한 짓만 골라서 하지 않는 이상 웬만해선 털리지 않는 높은 보안을 자랑하기 때문에, 양자 보안 기술을 실질적인 보안 강화라고 부를 수 있는지에 대해서는 이견이 있다.[21] insufficient scientific rigor[22] 실제로 나노 단위 크기로 도달해도 양자현상이 일어나기 때문에 고성능화 반도체레이저, 트랜지스터에 양자사이즈효과를 응용하고 있다.[23] 전자가 너무 작아서 아직까지의 모든 실험에서는 크기가 0으로 측정됐다.[24] 이는 CPU의 RISC 방식의 아키텍처와 CISC 방식의 아키텍처 설계와 같이 서로 목적에 맞게 최적화 되어있다,[25] 구글은 현재 0.3% 정도의 오류율에 도달한 것으로 알려져 있으나 여전히 측정 등 일부 연산에서 1% 이상의 큰 오류율을 보인다.[26] 양자컴퓨터라며 언플과 광고를 엄청 해댔다. 그래서 처음엔 학계에서도 이 물건이 정확하게 무엇이냐고 아리송해 하는 사람들이 많았다. 이 위키에도 그 광고에 낚인 내용이 잔뜩 쓰여 있었지만 지금은 수정.[27] 퀀텀 몬테 카를로 알고리즘이라고 알려져 있음.[28] 그렇기에 양자 컴퓨터 전용의 바이러스에 영향을 받지 않았다.[29] 추정, 그리고 이쪽은 양자 역학을 씹어먹는 존재다.[30] 내부에 양자컴퓨터가 들어있다고 한다.