과학/창업

양자 알고리즘과 양자컴퓨터 시스템

첫째 착수 양자컴퓨터 알고리즘

양자컴퓨터 알고리즘은 기본 알고리즘과 응용 알고리즘이 있습니다. 우선 알고리즘의 정의를 알아봅니다.

1. 알고리즘의 정의

알고리즘(Algorithm)은 어떤 일, 특히 컴퓨터에서 수행하는 과업(課業)의 처리 절차나 방법을 단계적으로 정해 놓은 것입니다. 다시 말하여 알고리즘이란 어떤 일 처리 시스템에 입력(Input)이 주어졌을 때, 원하는 출력을 얻기 위하여 따라야 하는 명확한 작동들의 SW 집합입니다.

예를 들어 산술의 덧셈을 할 때, 일(1)의 자리부터 더하여 십(10)의 자리 이어서 백의 자리로 순차적으로 더하는 경우 그 더하는 순차적 절차를 알고리즘이라고 합니다. 그러나 이런 숫자 더하기 절차를 굳이 알고리즘이라고 부르지는 않습니다. 그것은 너무나 단순하여 누구나 쉽게 수행할 수 있기 때문입니다.

가장 유명한 알고리즘은 가우스(Gauss)의 연속 숫자(수열) 덧셈 방법 입니다. 1에서 10까지 연속된 숫자를 더하라는 선생님의 문제를 듣자 말자, 어린 가우스는 몇 초 후에 55라는 답을 내놓았습니다. 1+10=11, 2+9=11, 3+8=11, …10+1=11. 따라서 11이 10개 이니 110, 그것을 2로 나누면 55. 이 덧셈 절차를 함수로 나타내면 N(N+1)/2로 할 수가 있고, 앞의 문제에 대입하면 10X(10+1)/2=55가 됩니다.

1에서 1만까지 더하는 문제는 그냥 숫자를 순차적으로 더해 나가면; 1+2+3+…..+10,000이 되고, 이런 순서는 1만 번을 더해야 하는 것입니다.
그러나 알고리즘을 적용하면; 10,000(10,000+1)=
50,005,000으로 쉽게 답을 구해낼 수가 있습니다.

알고리즘은 이처럼 쉬운 계산 문제를 다루는 데는 잘 사용하지 않고, 컴퓨터처럼 복잡한 일(Task)의 처리 등에 적용합니다.

이러한 알고리즘이 되기 위하여는 몇 가지 조건을 갖추어야 합니다.

1) 명확성; 각 조작 단계는 누구나 알 수 있도록 명확해야 합니다.
2) 종결성; 해답이 반드시 나와야 합니다.
3) 절차성; 필요한 정보를 입력하고 출력하는 시스템에 적용하는 절차(Process) 여야 합니다.
4) 효율성; 가능한 한 간단하고 효율적으로 처리하여, 이를 구축하는 투자자금의 경제성이 있는 절차 여야 합니다. 그 절차가 비효율적 이라면, 이것은 비록 해답을 내더라도 알고리즘이라고 할 수는 없습니다.

2. 알고리즘의 유래

알고리즘은 고대 페르시아의 수학자 알 콰리즈미(Al Khwarizmi)가 창시하였습니다. 그의 이름이 라틴어로 옮겨지면서 Algorithm으로 쓰여져 왔습니다.

알 콰리즈미는 수학의 수식을 기호(문자)로 표현하여 간략히 계산을 하는 대수학을 정립하여 발전 시켰습니다. 대수학은 학창시절 배운 항등식과 방정식을 상기하면 이해가 빠릅니다.

이 대수학을 컴퓨터의 논리식으로 창안한 수학자가 바로 불 대수(Boolean Algebra)를 창안한 조지 불(George Bool)입니다. 이 불 대수로 기본 논리게이트 AND, OR, NOT Gate를 만듭니다.

3. 컴퓨터 대수학의 컴퓨터 실물 구현

기계가 계산을 할 수 있는 길을 문서화 하여 컴퓨터 개발의 계기를 제시한 앨런 튜링(Alan Turing)이, 대수학이 기계적으로 구현될 수 있게 발전 시켜서, 대수학 알고리즘이 컴퓨터 작동의 근간이 되게 하였습니다.

4. 양자 상태 결맞음 구현―양자컴퓨터 알고리즘의 전제 조건

양자 상태인 양자 중첩이나 양자 얽힘은 양자 상태의 결맞음이 유지되어야 양자 연산이나 양자 측정을 할 수가 있습니다. 그 결맞음이 깨어지면 Noise가 생겨서 양자컴퓨터 작동이 되지 않습니다. Noise란 양자컴퓨터 작동이 안되는 상태(오류)를 말합니다.

이렇게 양자 상태 결맞음이 유지되는 상태에서 양자 알고리즘은 실행이 됩니다.
양자 상태 결맞음(Coherence)이란 양자의 상태가 깨지지 않고 계속하여 유지되는 현상을 말합니다.
고전컴퓨터는 오류 발생이 다소 있더라도, 그 시스템 내에 오류정정 기능이 있어서 잘 작동됩니다. 그러나 양자컴퓨터는 다릅니다.
이제 본격적으로 양자 컴퓨터 알고리즘을 설명합니다.

5. 기본 알고리즘:
1) QFT(Quantum Fourier Transform)는 양자 푸리에 변환 알고리즘 입니다.
QFT는 양자 상태의 진폭(양자의 물성 파동의 진동폭)을 특정한 주파수(Frequency)로 변환하여 그 파동의 주기를 발견하는 알고리즘입니다. 뒤에 나오는 응용 알고리즘 항에서, 소인수분해(쇼어 알고리즘)를 위한 숫자의 반복성 주기를 찾는 데 활용합니다. 어떤 수열의 반복 집합이 바로 소인수 입니다.

2) QPE(Quantum Phase Estimation)는 양자위상추정 알고리즘입니다.
양자 연산에서 양자 상태의 위상(Ket 0이나 Ket 1을 결정하는 특정 지점)을 나타나게 하는 알고리즘 입니다. 양자 연산 후 이 위상을 측정을 하면 확률이 나오고, 그 확률을 이용하여 큐비트 0이나 큐비트 1이 결정되어 나오게 합니다.

3) Amplitude Amplification은 진폭 증대 알고리즘입니다.
양자 연산에서 양자 파동의 진폭을 증대함으로써, 양자 검색 연산의 정확도를 올리는 알고리즘 입니다. 뒤에 나오는 검색 알고리즘 그로버(Grover) 알고리즘에서 활용 됩니다.

4) 양자 오류 정정 알고리즘
양자 상태는 결맞음을 유지하여야 정상적 양자 연산이 됩니다. 양자 오류 정정 알고리즘은 결깨짐을 방지하는 알고리즘입니다.
결깨짐으로 인한 오류는 ① 큐비트 플립(Qubit Flip) 오류와 ②위상 플립(Phase Flip) 오류가 있습니다.

큐비트 플립 오류는 <Ket 0↔Ket 1> 형태의 오류 입니다. Ket 0과 Ket 1이 뒤바뀌는 오류 입니다. 이를 해결하는 알고리즘은 복수 큐비트를 사용하는 것 입니다. <Ket=Ket 000>처럼 사용하면 비록 0 하나가 뒤집혀 <Ket 100>이 되더라도 0이 다수 이므로 <Ket 0>이 되는 것입니다.

위상 플립 오류는 <Ket 111>에서 1이 하나 뒤바뀌어 <Ket 101>처럼 되는 오류 입니다. 위상 플립 오류 방지 알고리즘은 좀 복잡합니다. <Ket +(Plus)와 Ket –(Minus) 코드>를 활용하여 오류 발견과 정정 문제를 풀어 냅니다. 자세한 내용은 생략합니다.

6. 응용 알고리즘

1) 쇼어(Shor) 알고리즘
쇼어 알고리즘은 대단위 정수(예 조, 경, 해단위)의 소인수분해(Factorization)를 풀어내는 알고리즘 입니다.
인터넷 금융거래에서 사용하는 Password(암호)는, RSA 등 대단위 숫자의 소인수분해 어려움의 원리를 적용하여 안전성을 도모합니다. 15=3X5처럼 쉬운 인수분해는 초등생이라 하더라도 단번에 암산으로 척 풀어냅니다. 그러나 암호에 활용하는 조나 경 및 해 단위의 숫자 소인수분해는 슈퍼컴퓨터라도 풀어낼 수가 없어서, 그 암호가 매우 안전합니다.

양자 연산에서 QFT를 적용하면 비록 대단위 인수분해 알고리즘을 적용한 패스워드라도 쉽게 풀어낼 수가 있습니다.
금융업계의 On-Line 거래 상 암호 알고리즘에 비상이 걸렸습니다. 이번에는 양자 암호 알고리즘으로, 비록 쇼어 알고리즘이라 하더라도 풀어낼 수 없는 패스워드 개발이 진행 중입니다.

암호와 암호 깨기는 창과 방패의 싸움입니다. 모순(矛盾) 즉 창과 방패의 원리 입니다. 아무도 뚫을 수 없는 방패가 나오면 이를 뚫는 창이 나옵니다. 그러면 이 창으로도 뚫을 수 없는 방패가 나오고, 이런 모순 싸움은 순환적 입니다.

2) 그로버(Grover) 알고리즘
100개 처럼 다수의 도시를 돌면서 영업을 하는 Salesman이 중복 없이 최단기간 내에 전 도시를 방문하여 판매하는 경로 찾기를 Sales Man Shortest Route(판매사원 최단 경로 탐색 문제) 이라고 합니다.

이와 같은 경로를 찾아내는 것처럼, 양자 연산에서 복잡한 탐색 문제를 다루어 해답을 찾아내는 알고리즘입니다. 정렬되지 않은 데이터 집합에서 최적의 데이터를 찾는데 활용합니다.
예를 들면 보물찾기 게임과 같습니다. 100개의 상자 중 1개만 보물이 들어 있습니다. 고전 컴퓨터를 활용하면 일일이 다 점검을 해야 합니다. 최악의 경우 100번을 검색하여 보물을 찾아낼 경우도 있습니다. 그로버 알고리즘 적용하면 단 한 번의 양자 연산으로 보물을 찾아내는 것입니다.

양자 중첩과 얽힘, 쇼어 알고리즘과 그로버 알고리즘 등이 양자 우월성(Quantum Supremacy)을 결정하는 것입니다.

둘째 포석 양자컴퓨터 시스템

양자 컴퓨터는 양자 상태인 큐비트가 결깨짐 없이 정상적으로 유지되는 시스템 위에서 작동합니다. 바로 양자 컴퓨터 시스템(System) 입니다. 양자 컴퓨터 플랫폼(Flat-form) 이라고도 합니다.
양자 컴퓨터 시스템은 큐비트, 양자연산게이트, 양자연산회로를 생성하며 제어하는 구조와 방법 체계입니다.

그 여러가지 시스템 중에서 ①초전도 양자 컴퓨터 ② 이온 트랩 양자 컴퓨터 ③ 광자 양자 컴퓨터를 설명합니다.

1. 초전도 양자컴퓨터
큐비트의 물리적인 구현은 절대 온도에 가까운 초전도 회로를 사용합니다. 이 시스템에서 사용하는 절대 온도는 0K도나 -273.15도C를 말합니다.
K는 켈빈(Kelvin)이라는 절대 온도표기법에서 사용하는 단위이고, C는 섭씨(Celsius) C 온도 표기법에서 사용하는 단위입니다. 화씨 F(Fahrenheit) 온도 표기법도 있습니다. C는 100K로 나눈 것이고 F는 180K로 나누어, 각각 1도를 정하는 것입니다. 학창시절 배우던 <F 곱하기 5 나누기 9=C>를 기억하십니까? 90F는 <90*5/9>로서 50C 입니다.

이 시스템에서는 미세한 전류의 흐름을 양자화 시켜서, 그 에너지 상태를 Ket 0 및 Ket 1로 사용합니다. 이런 큐비트로 양자 연산을 합니다. 그 연산은 양자 게이트(X, Y, Z, CNOT 등)에서 합니다.

양자 게이트의 조작은 마이크로파를 사용합니다.

이처럼 <큐비트 따로 양자게이트 따로>와 같이 양자 연산 게이트에 사용하는 에너지 체계는 복잡 합니다. 그냥 에너지라고 이해하면 됩니다. 일일이 에너지에 신경을 쓰면 작동 과정의 이해를 놓치게 됩니다.

IBM, Google, Amazon, NVIDIA 등에서 사용하는 시스템입니다. 가장 산업화가 넓게 퍼져 있습니다.

장점은 연산 속도가 나노(Nano)초 정도로 매우 빠르다는 것입니다. 단점은 초저온 상태의 초전도 시스템 유지에 거액의 자금이 소요된다는 것입니다.

2. 이온 트랩 양자컴퓨터
진공으로 된 양자 컴퓨터 시스템 내에 Ca(Calcium, 칼슘) 이나 Yb(Ytterbium, 이터븀) 같은 금속의 이온(Ion, +나 – 전하를 띄는 파동)을 사용하는 시스템 입니다.

이온의 전자 에너지 상태를 큐비트 Ket 0 이나 Ket 1로 사용합니다.
큐비트의 조작은 레이저 빛을 사용합니다. 큐비트 간 상호작용은 공통 진동 상태를 사용합니다.

미국의 IonQ, NIST, Quantinum, 영국 Oxford Ionics, 오스트리아 AQT 등의 회사에서 사용합니다.

장점은 큐비트 결맞음 상태 유지 시간이 길다는 것입니다. 양자 컴퓨터 연산에서 큐비트의 결맞음 시간이 양자 연산 시간보다 길어야 합니다.
단점은 양자 연산 시간이 길다는 것입니다.

3. 광자 양자컴퓨터
빛의 편광(특정 방향으로 비추는 성질), 위상과 경로등의 상태를 큐비트 Ket 0과 Ket 1로 사용합니다.

양자 연산의 조작은 광학 소자를 이용합니다.
캐나다 Xanadu, 미국/영국 Psi Quantum, 프랑스 LIGHTON, 네델란드 Quix Quantum, 일본 Toshiba Quantum Lab 등에서 사용합니다.

장점은 상온에서 시스템 구현이 가능하다는 것입니다. 결깨짐이 거의없고, 광통신 인프라 시스템과 자연적으로 연결 가능하다는 것입니다.
단점은 광자의 생성과 검출이 어렵고 비효율적 이라는 것입니다.

4. 클라우드 양자컴퓨터 서비스
양자컴퓨터 시스템 개발 제작은 엄청난 자금을 소요로 합니다. IBM이나 Google 및 Amazon 등의 대기업 이라야 가능합니다.

그러면 Start-up 이나 연구소 등에서는 어떻게 양자컴퓨터를 사용할까요?

IBM은 Hello Quantum 양자컴퓨터 클라우드(Cloud) 서비스를 제공합니다. 다른 Big Company 들도 이런 서비스를 제공하지요. 연구소와 중소규모의 회사는 이런 Cloud Service를 사용합니다.

5. 우리나라의 양자 컴퓨터 개발 현황
정부는 2,035년까지 양자 경제 허브로 도약하겠다는 전략을 제시하였습니다. 또한 KQISA(Korea Quantum Industry Association)가 있습니다. 현재 Startup 기업이 몇 군데 양자컴퓨터 시스템 개발을 진행 중입니다.

아직까지 양자컴퓨터 시스템의 개발 정보는 공개되지 않았습니다. 그러나 학계와 기업의 연구소에서 양자 컴퓨팅, 양자 센싱, 양자 인터넷 관련 연구를 하고 있습니다.

세계의 양자컴퓨터 개발 현황과 미래로 이어집니다.

밴드

URL복사