양자컴퓨터란?

양자컴퓨터는 연산 체계 자체가 기존의 컴퓨터와 전혀 다른 방식으로 작동하는 컴퓨터입니다. 기존의 방식은 비트로 0, 1로만 표현되며 비트는 둘 중 하나만 가질 수 있습니다. 반면 양자컴퓨터은 0, 1, 그리고 0과 1의 조합을 동시에 나타내고 저장할 수 있는 양자 비트(quantum bits), -이를 줄여서 큐비트(qubits)라고도 말함- 를 이용하여 데이터를 처리합니다. 이러한 두 상태의 중첩이 가능해짐에 따라 양자 컴퓨터는 바이너리 비트를 이용하여 모든 정보를 0 아니면 1로만 저장할 수 있는 전통적인 컴퓨터보다 훨씬 더 데이터 처리의 속도를 가속화 할 수 있습니다. 즉, 양자컴퓨터는 양자 컴퓨터는 모든 가능한 상태가 중첩되어 얽혀있는 상태 -이를 양자 결집 상태(quantum-coherent state) 라 칭함- 를 이용합니다. 이를 더 설명하자면 양자 상태는 여러 가지 고유값을 가지는 서로 다른 고유 상태가 중첩되어 존재하는데 양자역학적으로 측정 혹은 섭동 행위는 중첩되어 존재하는 양자 상태를 붕괴시켜 허용된 고유상태 중 특정한 하나로 확정되도록 합니다. 여기서 고유 상태 중 어떤 상태로 확정될지는 아무도 알 수 없고 확률적으로 추정만 가능합니다. (어려워) 이러한 어려운 내용을 요약하면 양자는 간단하게 자연현상은 확률의 지배를 받으며. 측정 혹은 섭동 행위 자체가 상태에 영향을 미칩니다.

용어

위 설명에선 나오진 않았지만 자주 등장하는 단어입니다.

양자 중첩 (quantum superposition) : 어떤 입자가 에너지 또는 위치와 관련하여 가질 수 있는 모든 가능한 상태들로 동시에 존재하는 양자역학적 특성.
양자 얽힘 (quantum entanglement) : 둘 이상의 양자 상태를 밀접하게 연관시켜 서로 엮어 놓은 상태. 얽힘 상태의 양자들은 서로 분리된 물리계에서도 어느 한쪽의 상태가 결정되면 다른 쪽 상태도 그 결과에 따라 필연적으로 결정되는 현상을 보임

양자 컴퓨터의 작동원리

물리학 전공이 아니여서 아주 간단하게만 설명하고 넘어갑니다. (어려워..)

위에서 설명했지만 큐비트로 정보를 처리하기 위해서는 모든 것이 상호의존적인 중첩 상태에 있어야 합니다. 이러한 상태를 가리켜 양자 결집 상태(quantum-coherent state) 라고도 하는데, 큐비트가 서로 결집되어 뒤얽혀 있는 상태를 가리킵니다. 이 상태에서는 하나의 큐비트에 변화를 주면 이것이 나머지 큐비트에게도 영향을 미치게 됩니다. 큐비트는 아주 연약하기 때문에 약간의 온도 변화, 소음, 파동, 그리고 움직임만으로도 물리학자들이 결잃음(decoherence)이라 부르는 상태가 될 수 있습니다. 결잃음이란 에너지가 새어 나가 계산에 실패하는 상태를 가리킵니다. 오늘날 큐비트들은 결잃음이 발생하기 전까지 양자 상태를 고작 100 마이크로초 동안만 유지할 수 있다고 IBM 연구원들은 설명하고 있습니다.

위의 결잃음 상태를 보는 것과 같이 양자 컴퓨터는 아주 극단적입니다. 쿨링에는 약 0.015 켈빈도의 온도가 필요한데, 이는 항성간 우주의 온도보다 180배나 더 차가워야 함을 의미한다고 합니다. 또한 이들은 지구의 자기장보다 50배 약한 강도로 보도돼야 하고 대기 중의 압력보다 100억 배 더 압력이 약한 고진공 상태에 두어야 하며, 저진동 표면에 위치시켜야 합니다.

이렇게 양자를 유지하는 것이 어려운 것 처럼 임의의 양자 상태를 복사하는 것은 불가능 합니다. 이러한 양자의 속성을 사용하면 보안에 있어 절대적으로 해킹할 수 없는 암호체계를 만들 수 있습니다. 또한 해킹하고자 하는 행동이 양자의 정보상태를 망가뜨리기 때문에 금방 알아챌 수도 있습니다.

얼마나 빠를까?

양자 컴퓨팅의 우수성은 특히 오늘날 가장 빠른 슈퍼 컴퓨터 보다도 훨씬 빠르게 데이터를 처리할 수 있다는 점에서 주목받고 있습니다. 일반적으로 50큐비트에서 이러한 속도가 가능해진다고 알려져 있지만 큐비트 수가 증가할수록 양자 결집 상태를 유지하는 것이 어려워진다는 문제가 있습니다.

양자 컴퓨터와 현존하는 암호화 알고리즘

소인수분해 문제 이외에도 수많은 암호 알고리즘이 바탕을 두고 있는 이산로그 문제 역시 양자컴퓨터로 해결할 수 있습니다. 따라서 양자컴퓨터가 본격적으로 실용화되면 현재까지 개발된 대부분의 암호 알고리즘이 쓸모 없어지게 됩니다. 하지만 양자컴퓨터가 모든 암호를 풀 수 있는건 아닙니다. 현재 모든 암호는 NP문제입니다. 양자컴퓨터가 NP-완전 문제(NP-complete)를 다항 시간(P)에 풀 수 있다는 잘못된 인식이 널리 퍼져 있으나 확실하게 증명된 내용은 없습니다. (풀리면 7대 난제 해결) 그리고 컴퓨터가 진화했던 만큼 더 안전한 알고리즘을 만들면 되기 때문에 기존과는 차원이 다른 보안 알고리즘을 사용할 가능성이 남아있습니다. 게다가 현재 제안된 알고리즘들 중 격자 기반(lattice based) 알고리즘 은 아직 양자컴퓨터로 해결할 알고리즘은 없습니다. 그 외에도 AES와 같은 블록 암호들 역시 아직 양자컴퓨터로 깨뜨릴 알고리즘이 나오지 않았으므로 현재로서는 양자컴퓨터가 급격히 실용화되더라도 안전하다고 볼 수 있습니다.

P - NP 문제

P: 시간만 있으면 풀 수 있는 문제. O(n)과 같이 현실적으로 풀 수 있는 알고리즘의 복잡도
NP: 알고리즘의 복잡도가 너무 비현실적인 문제. 기하급수적으로 복잡도가 증가

NP 문제

그래프가 주어졌을 때 그래프의 모든 점을 정확하게 한번씩만 지나는 경로가 존재하는가?

위와 같은 문제가 주어졌을 때(= 해밀턴 경로 문제) 이 문제에 대해 어떤 경로를 입력으로 준다면, 컴퓨터는 이게 정답인지 아닌지 알려줄 수 있습니다. NP문제로 돌아가서, 비결정론적 튜링머신이 주어진 입력이 정답인지 아닌지 계산하는데 다항시간(P)이 걸린다고 하면 NP문제라고 합니다. 다시 말하면, 컴퓨터로 다항 시간에 풀어낼 수 없는 문제들을 NP 문제라고 칭합니다.

NP-난해 (NP-hard) 문제

위에 나오진 않지만 NP-완전문제를 설명하기 전, 간단히 소개합니다. 적어도 NP문제 보다 어렵고 모든 NP 문제를 다항 시간 내에 어떤 문제 A로 환원(reduction)할 수 있다면, 그 A 문제를 NP-난해(NP-hard) 문제라고 합니다.

환원(reduction)이란?

문제 A: 주어진 n개의 숫자를 크기 순서로 정렬하는 문제
문제 B: 주어진 n개 숫자의 중간값을 계산하는 문제

어떤 사람이 문제 A를 풀 수 있다면 당연히 B도 쉽게 풀 수 있습니다. A를 푼 다음 가운데 수만 뽑아내면 문제 B가 풀리기 때문입니다. 이와 같은 것을 문제 B를 문제 A로 환원(reduction)시킬 수 있다고 표현합니다.

NP-완전 (NP-complete) 문제

NP난해 문제에 포함되며, NP문제에도 포함된다면 이를 NP-완전(NP-complete) 문제라고 합니다. NP-완전 문제를 풀 수 있으면 모든 NP 문제를 풀 수 있게되므로 NP 문제들 중에서는 가장 핵심이 되는 문제입니다. 위에서 예를든 해밀턴 경로 문제도 대표적인 NP-완전 문제들 중 하나입니다.

만약 NP=P 가 옳은지 그른지 증명을 할 수 있다면 여러 교과서에 실릴 수 있습니다. (100만달러 상금은 덤)

격자 기반 암호

격자 암호화(lattice cryptography)로 불리는 차세대 양자암호화 방식이 현재 개발이 되었는데 이는 현존하는 컴퓨터나 양자 컴퓨터 조차도 해독할 수 없다고 합니다. 격자는 점으로 만들어진 무한 그리드를 나타내는데 격자 암호화 기술 방식을 사용하면 해커들에게 민감한 데이터를 노출시키지 않고도 파일을 작업하거나 암호화 할 수 있습니다. 격자암호화 기술은 정보를 숨기기 위해 고차원 기하 구조를 사용하는데 키가 없으면 양자 컴퓨터로도 풀 수 없는 문제를 생성해 냅니다.

격자_암호.png
출처: IBM

따라서 양자컴퓨터가 실용화되고 그 때까지 격자 기반 알고리즘을 양자컴퓨터로 해결할 알고리즘이 개발되지 않는다면, 격자 기반 알고리즘이 공개키 암호계의 대세를 차지하게 될 가능성도 있습니다.

양자 컴퓨터(quantum computer)란?