양자컴퓨터 쉬운 이해 (3) 큐비트와 양자알고리즘

이번 포스팅에서는 “양자컴퓨터의 쉬운 이해” 시리즈의 마지막 글로 큐비트와 양자알고리즘에 대해서 정리해보려고 합니다.

참고로 양자컴퓨터의 기본 개념에 대해서 아래 3가지 글로 구성하였습니다.

(1) 이중슬릿 실험과 양자, 양자역학
(2) 양자중첩과 양자얽힘
(3) 큐비트와 양자알고리즘 (이번 포스팅)

이번 포스팅에서는 양자컴퓨터의 원리와 큐비트에 대해서 설명하고자 합니다. 양자컴퓨터는 앞선 포스팅에서 설명한 양자중첨과 양자얽힘의 현상을 이용합니다. 이번 포스팅에서는 지금도 일상생활에서 사용하는 (전통적인) 컴퓨터의 현상과 비교하면서 양자컴퓨터의 원리를 설명하도록 하겠습니다.


일반적인 컴퓨터(전통적인 컴퓨터) 정보처리 구조

컴퓨터는 기본적으로 비트(bit)라는 최소 단위로 정보 처리/연산을 합니다.
비트는 한번에 0 또는 1의 값만 가질 수 있습니다.
예를 들어 십진수인 10을 다룬다면 1010이 됩니다. 이러한 비트가 수없이 많이 보여서 복잡한 연산을 수행하게 됩니다.

큐비트와 양자알고리즘


큐비트와 양자컴퓨터 정보처리 구조

양자컴퓨터는 큐비트(qubit)라는 최소 연산 단위를 가지고 있습니다.

양자중첩은 확률적으로 가능한 상태들이 동시에 중첩되는 현상이므로
큐비트는 이러한 양자중첩 현상을 이용해서 비트처럼 0 또는 1의 값 둘 중 하나만을 가지는 것이 아니라 0과 1일 동시에 중첩되어 있는 상태를 갖게 됩니다. 즉, 0과 1로 확정되어 있는 것이 아니라 그 사이에 어딘가에 존재하는 것 입니다.

큐비트와 양자알고리즘

이는 여러가지 이점이 있는데요, 그 중에 하나가 동시에 가능한 정보의 표현 가능수 입니다.
예를 들어 전통적인 컴퓨터 비트 4개로 표현할 수 있는 정보의 가짓수는 16개
입니다.

각각 0,1이 가능하므로 2x2x2x2 = 16 입니다.
단 16개의 가능한 정보 중에 하나만 골라서 표현이 가능합니다.

그러나 큐비트는 양자 중첩 원리를 이용하므로 고전적인 비트처럼 한번에 하나씩만 표현하는게 아니라 가능한 정보 가짓수 16개를 모두 동시에 표현이 가능합니다.
즉 큐비트들은 모여서 동시에 2의 n큐비트 개의 정보를 표현할 수 있다는 것 입니다.

큐비트와 양자알고리즘

참고로 큐비트라는 용어 를 만든 사람은 벤자민 슈마허( Benjamin Schumacher)인데요, Schumacher는 1995년 논문의 승인에서 큐비트라는 용어 가 William Wootters와의 대화 중에 농담중에 만들어졌다고 합니다.


양자알고리즘 (1) 전통 컴퓨터와 양자 컴퓨터의 정답 맞추기

알고리즘이란 어떠한 문제를 해결하기 위한 프로세스를 의미합니다. 즉 컴퓨터는 어떤 주어진 문제 해결을 위해 알고리즘에 따라 정보처리/계산을 하게 됩니다.

기존의 전통적인 컴퓨터에서는 랜덤 방식으로 순차적으로 정보처리가 진행되었습니다.
예를 들어 0에서 9까지 정수를 랜덤으로 선택하여 4를 정하고, 컴퓨터에게 맞춰보라는 문제가 있다고 하면,

컴퓨터 또한 랜덤으로 0에서 9까지 숫자를 선택해서 비교하게 됩니다.
예를 들어
첫번째 시도에서는 1 = 비트 001을 입력하고 오류 임을 확인하고
두번째 시도에서는 3 = 비트 011을 입력하고 오류 임을 확인하고
세번째 시도에서는 5 = 비트 101을 입력하고 오류 임을 확인하고
네번째 시도에서는 4 = 비트 100을 입력하고 정답임을 확인하게 됩니다.
전통적인 컴퓨터에서는 이렇게 하나씩 순차적으로 확인하여 네번째 시도 후에 맞추게 되었지만,
10번이 걸릴 수도 있는 것이고 숫자의 범위가 넓어질 수록 정답을 맞출 확률과 시도 횟수는 늘어나게 됩니다.

큐비트와 양자알고리즘

양자컴퓨터의 경우에는 고전적인 비트가 아닌 큐비트를 넣게 되는데요,
보통은 “큐비트는 모든 상태가 중첩되어 있기 때문에 가능한 상태를 모두 병렬적으로 동시에 알 수 있다”고 오해하는 경우가 많은데, 사실 그렇지 않습니다. “관측” 상태에서 문제가 발생하기 때문입니다.

양자 중첩 상태는 관측을 하는 순간 하나의 상태로 결정되기 때문에 중첩인 상태가 풀리면, 중첩 상태인 큐비트를 넣어도 정답과 비교하기 위해 관측을 하는 이상 하나로 결정된 상태를 넣는 것과 다르지 않습니다.
즉 전통적인 컴퓨터와 똑같이 마지막에 관측을 했을 때 정답이 나올 확률은 그대로 1/10인 것 입니다. 나머지 9/10 확률로 오답을 관측하게 됩니다.


양자알고리즘 (2) 파동함수 예시

그러므로 양자 컴퓨터의 핵심은 양자 알고리즘에 있습니다. 관측하기 전에 양자역학의 원리를 활용하여 틀린 답안이 관측될 확률을 낮추고 정답이 관측될 확률을 높이는 것이 핵심 입니다.
관측을 했을 때 더 높은 확률로 맞는 답안이 나오도록 하고 전체 알고리즘 수행 시간을 줄여 무작위하게 대입하는 횟수를 줄이는 것 입니다.

가령 파동함수에서 확률 파동이 큰 곳은 정답을 발견할 확률이 높은 지점이고, 확률 파동이 낮은 곳은 정답이 발견될 확률이 낮은 곳 입니다. 물론 확률파동이 0인 곳은 정답이 발견되지 않는 지점입니다.
이러한 방식 등을 활용하여 알고리즘의 효율성을 증가 시켜 정답을 관측할 확률을 높이는 것이 양자 알고리즘의 핵심 입니다.

큐비트와 양자알고리즘

사실 양자알고리즘은 그로버의 알고리즘 외에도 도이치-조사 알고리즘, 쇼어 알고리즘 등이 있으며 아직은 많은 종류가 개발된 상태는 아니기 때문에 과학자들은 양자 컴퓨터로 더 효율적으로 해결할 수 있는 문제와 알고리즘이 존재하는지 연구하고 있습니다.

이번 포스팅에서는 양자컴퓨터의 원리와 큐비트에 대해서 정리하였습니다. 양자컴퓨터는 앞선 포스팅에서 설명한 양자중첨과 양자얽힘의 현상을 이용합니다. 이번 포스팅에서는 지금도 일상생활에서 사용하는 (전통적인) 컴퓨터의 현상과 비교하면서 양자컴퓨터의 기초적인 원리를 알아보았습니다.


양자컴퓨터의 기본 개념에 대해서 아래 3가지 글로 구성하였습니다.

(1) 이중슬릿 실험과 양자, 양자역학
(2) 양자중첩과 양자얽힘
(3) 큐비트와 양자알고리즘 (이번 포스팅)

Leave a Comment