양자 컴퓨터

위키백과 ― 우리 모두의 백과사전.

양자 컴퓨터(quantum computer)는 얽힘(entanglement)이나 중첩(superposition) 같은 양자역학적인 현상을 이용하여 자료를 처리하는 계산 기계이다. 고전적인(전통적인) 컴퓨터에서 자료의 양은 비트로 측정된다. 양자 컴퓨터에서 자료는 큐비트로 측정된다. 양자 계산의 기본적인 원칙은 입자의 양자적 특성이 자료를 나타내고 구조화할 수 있다는 것과 양자적 메카니즘이 고안되어 이러한 자료들에 대한 연산을 수행할 수 있도록 만들어질 수 있다는 것에 기한다.

양자 컴퓨팅이 여전히 유아기에 있지만, 매우 작은 수의 큐비트을 가지고 양자 수치 계산이 수행되는지에 관한 실험들이 행해져 왔다.

[편집] 양자 컴퓨팅과 계산 복잡도 이론

이 절에서는 양자 컴퓨터의 능력에 대해 현재 알려진 수학적인 결과를 조사한다. 이 결과는 양자 컴퓨터와 관계된 계산 복잡도 이론과 계산 이론에서 나온 것이다.

양자 컴퓨터가 효율적으로 풀 수 있는 문제군을 BQP라 한다. 여기서 효율적이란, "정해진 오차범위 내에서 다항 시간 안에" 푼다는 뜻이다. 양자 컴퓨터는 확률적 알고리즘을 실행할 뿐이므로 양자 컴퓨터에 대한 BQP는 기존 컴퓨터에 대한 BPP에 대응한다. BPP는 오차 확률을 1/4로 제한하며 다항 시간에 풀 수 있는 문제의 집합으로 정의된다.^[2] 양자 컴퓨터가 문제를 "푼다"는 것은 모든 예제에 대해 높은 확률로 올바른 결과가 나온다는 뜻이다. 그 결과가 다항 시간에 나왔다면 그 문제는 BQP에 속한다.

BQP는 NP-완전과 서로소 집합이고, P가 BQP의 진부분집합일 것으로 추정되나 아직 증명되지는 않았다. 소인수분해와 이산 로그 문제가 BQP에 속한다. 두 문제 모두 NP문제이고, BPP가 아닐 것으로 추정되므로 P에도 속하지 않는다. 또한 NP-완전도 아닐 것으로 추정된다. 양자 컴퓨터가 NP-완전 문제를 다항 시간에 풀 수 있다는 잘못된 인식이 널리 퍼져 있으나 확실히 증명된 바는 없다. 양자 컴퓨터도 NP-완전 문제는 다항 시간에 풀 수 없다는 견해가 일반적이다.

양자 컴퓨터의 연산자는 벡터에 특정한 행렬을 곱해서 바꾸는 것으로 생각할 수 있다. 행렬을 곱하는 연산은 선형 연산이다. 대니얼 S. 에이브럼스와 세트 로이드는 양자 컴퓨터가 비선형 연산자로 설계될 수 있다면 NP-완전 문제를 다항 시간에 풀 수 있음을 보였다. #P-완전 문제 역시 가능하다. 그러나 그러한 기계는 불가능하다고 보았다.

양자 컴퓨터가 기존 컴퓨터보다 빠를 수는 있지만, 기존 컴퓨터로 풀 수 없는 문제는 양자 컴퓨터 역시 풀 수 없다. 충분한 시간과 메모리가 주어지더라도 마찬가지이다. 튜링 기계가 양자 컴퓨터를 시뮬레이트할 수 있기 때문에 양자 컴퓨터가 정지 문제 같은 결정 불가능 문제를 풀 수는 없다. "표준" 양자 컴퓨터의 존재가 처치-튜링 명제를 반증하지는 않는다. ^[3]

최근에 수많은 연구자들이 양자 역학을 하이퍼 계산에 사용할 수 있는지를 연구하기 시작하였다. 즉, 결정 불가능 문제를 풀 수 있을지를 연구하는 것이다. 그러한 주장은 이론적으로도 가능하지 않을 것으로 보는 회의적인 견해가 많다.

[편집] 참고

• 쇼어 알고리즘
• NMR 양자 컴퓨터

[편집] 주석

1. ↑ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
2. ↑ (Nielsen & Chuang 2000)
3. ↑ Nielsen, Michael and Isaac Chuang (2000), p. ?

v • d • e 컴퓨터 과학의 주요 분야
수학적 기초	수리논리학 · 집합론 · 정수론 · 그래프 이론 · 형 이론 · 범주론 · 수치 해석 · 이산수학
계산 이론	오토마타 이론 · 계산 가능성 이론 · 계산 복잡도 이론 · 양자 계산 이론
알고리즘 & 자료 구조	알고리즘 · 자료 구조 · 계산 기하학
프로그래밍 언어 & 컴파일러	구문 분석 · 컴파일러 · 인터프리터 · 프로그래밍 언어 · 구조적 프로그래밍 · 객체 지향 프로그래밍
병렬 & 분산 시스템	병렬 컴퓨팅 · 클러스터 컴퓨팅 · 분산 컴퓨팅 · 그리드 컴퓨팅 · 클라우드 컴퓨팅 · IaaS · PaaS · SaaS
소프트웨어 공학	요구 분석 · 소프트웨어 설계 · 컴퓨터 프로그래밍 · 형식수법 · 소프트웨어 테스트 · 소프트웨어 개발
시스템 아키텍처	컴퓨터 아키텍처 · 마이크로아키텍처 · 운영 체계
통신 & 네트워크	컴퓨터 오디오 · 라우팅 · 네트워크 토폴로지 · 암호학
데이터베이스	데이터 마이닝 · RDBMS · SQL
인공 지능	자동추론 · 전산언어학 · 컴퓨터 비전 · 진화 연산 · 기계 학습 · 자연 언어 처리 · 로봇학
컴퓨터 그래픽	시각화 · 영상 처리
인간과 컴퓨터 상호 작용	Computer accessibility · 사용자 인터페이스 · 착용 컴퓨터 · 유비쿼터스 컴퓨팅 · 가상현실
계산과학	인공생명 · 생물정보학 · 인지과학 · 계산화학 · 계산론적 신경과학 · 계산물리학 · 수치 해석 · Symbolic mathematics
정보보호	암호학 · 물리 보안 · 소프트웨어 보안 · 인터넷 보안 · 네트워크 보안 · 해킹 · 크래킹

이 글은 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.

이 글은 정보에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.