[양자정보과학] 양자 컴퓨터란?

양자컴퓨터란?

양자 컴퓨터(quantum computer)는 얽힘(entanglement)이나 중첩(superposition) 같은 양자역학적인 현상을 활용하여 자료를 처리하는 계산 기계입니다. '양자 컴퓨팅'(量子 - , quantum computing)이라고도 부릅니다. '꿈의 컴퓨터'라는 별명을 갖고 있습니다.

양자 정보 통신은 정보 사회의 패러다임을 바꿀 신기술로 여겨졌습니다. 양자 정보 통신을 활용한 양자 컴퓨터는 한 개의 처리 장치에서 여러 계산을 동시에 처리할 수 있어 정보처리량과 속도가 지금까지의 컴퓨터에 비해 뛰어납니다. 하지만 정보 교환을 위해 발생하는 '얽힘(entanglement)'에 큰 비용이 드는 단점이 있기 때문에 양자 정보 통신에서 필수적이지만 비용이 많이 발생하는 얽힘을 가능한 한 줄이고 부정보(side information)를 활용해 정보를 교환하는 방식이 개발되었습니다.

고전 컴퓨터에서 자료의 양은 비트로 측정됩니다. 그러나 양자 컴퓨터에서 자료의 양은 큐비트로 측정됩니다. 양자 계산의 기본적인 원칙은 입자의 양자적 특성이 자료를 나타내고 구조화할 수 있다는 것과 양자적 메카니즘이 고안되어 이러한 자료들에 대한 연산을 수행할 수 있도록 만들어질 수 있다는 것에 기인 합니다. 양자 컴퓨팅이 여전히 유아기에 있지만, 매우 작은 수의 큐비트를 가지고 양자 수치 계산이 수행되는지에 관한 실험들이 행해져 왔다.

양자 컴퓨팅과 계산복잡도 이론

양자 컴퓨터가 효율적으로 풀 수 있는 문제군을 BQP라 합니다. 여기서 효율적이란, '정해진 오차범위 내에서 다항 시간 안에' 푼다는 뜻이라고 할수 있습니다. 양자 컴퓨터는 확률적 알고리즘을 실행할 뿐이므로 양자 컴퓨터에 대한 BQP는 기존 컴퓨터에 대한 BPP에 대응합니다. BPP는 오차 확률을 1/4로 제한하며 다항 시간에 풀 수 있는 문제의 집합으로 정의됩니다.

2019/05/20 - [경제] - [양자정보과학] BQP란?

 양자 컴퓨터가 문제를 "푼다"는 것은 모든 예제에 대해 높은 확률로 올바른 결과가 나온다는 뜻입니다. 그 결과가 다항 시간에 나왔다면 그 문제는 BQP에 속하는 것입니다.

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

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

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

최근에 수많은 연구자들이 양자 역학을 하이퍼 계산에 사용할 수 있는지를 연구하기 시작하였습니다. 

즉, 결정 불가능 문제를 풀 수 있을지를 연구하는 것인데요. 그러한 주장은 이론적으로도 가능하지 않을 것으로 보는 회의적인 견해가 많습니다. 

양자컴퓨터의 상용화

2011년 5월 11일, 캐나다의 D-Wave Systems에서 128큐비트 프로세스가 장착된 세계최초의 상용화 양자컴퓨터인 D-Wave One을 내놓았으며, 5월 20일 1000만 달러의 가격으로 시장에 내놓았습니다.

D-Wave One 은 범용 양자 컴퓨터는 아니며, Quantum Annealing 이라는 특정한 양자 알고리즘에 특화된 하드웨어를 갖고 있습니다.

2013년 NASA와 구글이 공동으로 설립할 인공지능 연구소에서 D-Wave 2를 구매할 계획이라고 밝혔다.

이후 D 웨이브는 D 웨이브 1의 후속으로 512개의 큐비트를 사용하는 D 웨이브 2(D-WAVE 2)를 출시했는데 구글이 이를 구입했습니다. D-Wave 2는 머신러닝과 음성인식, 자연어 처리를 위해 방대한 데이터를 분석할 수 있고, 싱글코어 칩을 활용하는 일반 컴퓨터보다 1억배 이상 빠른 속도로 처리할 수 있는 것으로 알려졌습니다.