| '''이론 컴퓨터 과학 {{{#!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-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | <keepall> 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| <keepall> 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| <keepall> 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| <keepall> 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| <keepall> 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
Topological Quantum Computation, 위상학적 양자 컴퓨팅
1. 개요
현대의 기존 양자 컴퓨터에서 나타나는 결맞음 붕괴(decoherence) 등의 문제로부터 큐비트 무결성을 보장하기 위해 2차원 준입자 애니온(anyon)[1]을 이용하는 위상학적 성질을[2] 이용한 양자 컴퓨팅 기술이다.[3] 알렉세이 키타에프가 고안했다.[4] 현대에는 마요라나 준입자(제로 모드)를 이용하여 구현하려는 시도가 절찬리에 시행 중이다.현재 실용적인 확장 가능한 양자 컴퓨터를 만들기 위해 요구되는 수준의 양자 게이트 신뢰성을 확보하고, 또한 혁신적으로 제고해줄 수 있는 기술로 평가받는다. 마이크로소프트의 Station Q 연구소와 구글 등에서 제일 적극적으로 연구/개발을 진행하고 있으며, IBM도 일부 연구를 시행하고 있다.
2. 관련 문서
A Short Introduction to Topological Quantum Computation, arXiv에 올라온 topological quantum computation에 대한 개론 논문이다.[1] 특히 여기에서는 비-아벨 애니온(Non-Abelian anyon)이 사용된다.[2] 간단하게 설명하자면, Non-abelian Holonomy로서의 World line Braiding으로 양자 게이트를 형성하여 그 위상적 구조가 신뢰성 높은(robust한) 형태의 양자 게이트를 만든다.[3] 좀 더 간단하게 직관적으로 비유하자면, 기존의 양자 컴퓨터는 불확정성 원리에 기반한 여러 섭동에 의해 게이트가 무너지는 것에 굉장히 취약했는데, 그것을 Non-abelian Holonomy의 구조로 '엮으면서', 즉 마치 얼기 설기 엮여있는 형태가 좀 몇번 툭툭 친다고 무너지지 않는것처럼, 그러한 "위상적" 방식으로 신뢰성을 고안한 것이다. 왜냐하면 기존의 양자 컴퓨터들은 그러한 양자적 섭동에 대응하여 저항성을 만드는 무언가의 내부적 회로 구조 자체가 부재했었다. (시간에 따른 애니온 입자들의 "궤적", 혹은 "형태 변환"을 엮는 것이다.)[4] A. Yu. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys. 303, 2(2003).