양자 컴퓨팅을 할 때 크게 두 가지 방향이 있다. 첫 번째 방식은 양자 시스템을 초기화 시킨 다음 해밀토니안을 제어를 해서 원하는 문제의 답을 높은 확률로 줄 수 있는 양자 상태를 만드는 것이다. 이 때 사용하는 양자 상태는 0 또는 1 상태만 사용하는 것이 아니고, 해밀토니안이 연속적으로 변하기 때문에 본질적으로 양자 정보는 아날로그이다. 이러한 방식을 아날로그 양자 컴퓨팅이라 하고 단열 양자 컴퓨팅, 양자 어닐링 등을 포함한다. 두 번째 방식은 오늘날의 컴퓨터 에서의 접근 방법처럼 문제를 가장 기초적인 연산인 게이트 단위로 나눠서 해결하는 것이다. 이러한 방식은 게이트 기반 양자 컴퓨팅이라 불린다.
하나의 큐비트의 양자 상태를 Bloch sphere에 표현한 예시. 참고문헌 [1]의 그림을 재구성함.
기존 컴퓨터에서는 반도체 소자가 증폭기 및 스위치 역할을 할 수 있고, 반도체 제작 기술이 발달하면서[2], 하나의 집적 회로에 수 억 개의 게이트를 넣을 수 있게 되었다. 각각의 게이트의 출력들은 0 또는 1의 값을 나타내는 전기 신호로 전선을 통해 다른 게이트의 입력으로 들어간다. 게이트를 공정을 통해 만들 때의 오차, 칩 안에서 한 부분이 다른 부분들로부터 받는 영향 등으로 신호에 잡음이 생기게 되는데, 디지털 논리 게이트는 이러한 잡음이 있더라도 게이트의 논리 연산에는 영향을 받지 않을 정도로 잡음에 둔감하고, 전기 신호가 많은 수의 게이트를 통과하더라도 실제 출력 결과의 논리식은 의도한 것과 같도록 오류 정정을 할 수가 있다. 따라서 이 경우 신호를 여러 게이트들로 계속 전달시키는 것이 가능하다.
반면에 양자 신호는 아날로그 신호로 잡음에 민감하기 때문에 기존 컴퓨터 칩을 설계할 때와는 다른 방식을 사용한다. 설계를 할 때 크게 고려를 하는 부분은 양자 신호에 가해지는 잡음을 최소화하는 것이다. 따라서 일반적으로 양자 신호를 게이트에 통과시키며 전달하기보다는 양자 정보를 가지는 큐비트를 두고 큐비트의 양자 상태를 의도한대로 변화시키도록 시스템을 설계한다.
기존 컴퓨터에서는 0과 1을 이용해 정보를 나타내기 때문에 게이트 연산을 표현하기 위해서 논리 게이트 추상화를 사용했지만 양자 컴퓨터에서 사용하는 양자 상태는 0 또는 1 하나로 나타내는 상태가 아니기 때문에 게이트 연산을 나타내기 위해서도 다른 추상화를 사용한다. 하나의 양자 게이트는 레이저와 전자기장 같은 물리적 변화의 적용을 통해 하나 또는 여러 개의 큐비트의 해밀토니안을 특정 시간만큼 바꾸어 원하는 양자 상태의 변환을 만드는 것으로 구현된다. 이러한 기초적인 단계의 연산은 기존 컴퓨터의 논리 게이트에 대응되기 때문에 이러한 방식을 사용한 양자 컴퓨터를 디지털 양자 컴퓨터라고 부른다.
양자 게이트는 양자 역학의 법칙을 따른다. 첫 번째로 양자 게이트는 에너지를 방출하지 않는다. 이것은 시스템에서 외부로 열이 빠져나가지 않는다는 것을 의미하고, 양자 상태가 외부의 영향으로 결맞음을 잃지 않는다는 것을 말한다. 이러한 경우 하나의 입력 양자 상태에 양자 게이트를 적용하여 출력된 양자 상태를 얻었을 때, 반대로 출력된 양자 상태에 반대의 양자 게이트를 적용해 기존의 입력한 양자 상태를 얻을 수 있고, 이를 가역 게이트(reversible gate)라 한다. 두 번째로 연산을 하는 동안 가능한 양자 상태들의 진폭의 크기의 제곱의 합은 1이다. $$n$$개의 큐비트의 양자 상태를 $$2^{n}$$ 차원의 복소수 벡터로 나타내면 크기가 1인 벡터가 된다. 모든 양자 게이트는 상태 벡터의 크기를 1로 보존하면서 다른 상태의 벡터로 회전시키는 연산이다. 큐비트의 수가 증가할수록 차원의 크기는 지수적으로 증가하지만 벡터의 크기는 여전히 1이다. 벡터의 크기를 보존하며 변화시키는 연산을 $$2^{n} \times 2^{n}$$ 크기의 행렬로 표현한 것을 유니타리(unitary) 행렬이라 한다.
기존의 논리 게이트에서 구현하는 것처럼 양자 게이트를 구현할 때, 많은 수의 입력을 한꺼번에 받는 게이트를 만드는 것 대신 적은 수의 입력을 간단한 게이트들을 여러개 적절히 구성하여 최종적으로 많은 수의 입력을 받는 게이트를 구현한다. 일반적으로 최소 단위로 사용하는 양자 게이트의 입력 큐비트 수는 세 개 이하이다. 그 중 예를 하나 들면 하다마드 게이트(Hadamard gate)는 |0⟩ 상태를 입력으로 받아서 $$\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$$을 출력하고 |1⟩ 상태를 입력으로 받아서 $$\frac{1}{\sqrt{2}}\left| 0 \right\rangle - \frac{1}{\sqrt{2}}|1\rangle$$을 출력한다. 2-큐비트 CNOT 게이트는 XOR 논리 연산을 한다. T 게이트, Hadamard 게이트, CNOT 게이트 만을 이용해서 다른 모든 유니타리(unitary) 게이트를 만들 수 있는데 이러한 게이트 조합을 범용(universal) 게이트라 한다.
양자 게이트는 가역(reversible) 연산이고 유니타리(unitary) 행렬로 나타낼 수 있는데 반해, 일반적인 양자 상태 측정은 원래의 양자 상태를 붕괴(collapse)시키기 때문에 가역적 작용이 아니다. $$n$$개의 큐비트의 양자 상태는 $$2^{n} $$차원의 양자 상태이므로 이를 측정하면 $$n$$개의 비트를 얻는다.[1]
Transmon 큐비트를 이용한 양자 오류 정정 회로. 참고문헌 [4]의 그림을 재구성함.
양자 컴퓨터를 이용한 의미 있는 연산을 수행하기 위해서는 연산 과정 도중에 큐비트의 상태가 일정하게 유지되어야 한다. 하지만 큐비트의 양자 상태는 주변 환경에서 발생한 열이나 잡음에 취약하기 때문에 쉽게 변하며, 이러한 오류를 정정하기 위한 기술이 추가적으로 필요하다. 이러한 오류를 해결하기 위해 고전 컴퓨터의 경우 RAID 시스템과 같이 저장된 정보를 여럿 복제하여 함께 저장하는 방식을 택하고 있으며, 오류가 발생했을 때 정보의 복사본들을 비교하여 오류를 찾아내고 정정할 수 있다. 하지만 큐비트의 양자 상태는 복제 불가능성 정리(no-cloning theorem)에 의해 동일한 여러 개의 상태로 복제할 수 없으며, 오류 확인을 위해 양자 상태를 측정할 경우 원래의 상태가 붕괴된다.[5] 따라서 이러한 근본적 한계로 인해 고전 오류 정정 방식과는 근본적으로 다른 접근이 필요하다. 최초의 양자 오류 정정 기술인 Shor code[6] 이후로 Steane code[7], Stabilizer code[8][4] 등 다양한 양자 오류 정정 기술들이 제안되었으며 현재에도 Surface code[9]를 비롯한 다양한 기술들이 활발히 연구되고 있다. 본 내용에서는 양자 오류 정정 기술의 가장 기초적인 형태인 Shor code에 초점을 맞추어 기술하였다.
3-큐비트 비트 플립 코드(3-qubit bit flip code)는 한 큐비트의 비트가 뒤집히는 오류를 정정하기 위하여 두 개의 보조 큐비트를 추가적으로 활용하는 오류 정정 코드이다. 고전 비트 플립 오류와 유사하나 큐비트의 상태를 복제하는 것이 불가능하므로 대신 큐비트들 간의 양자 얽힘을 활용하여 오류를 정정한다.
한 큐비트의 비트가 뒤집히는 오류를 정정하기 위해서 큐비트의 초기 상태가 $$\left| \psi \right\rangle= \alpha\left| 0 \right\rangle + \beta|1\rangle$$일 때, $$\left| 0 \right\rangle$$ 상태로 초기화된 두 큐비트를 준비한다. 세 큐비트들이 처음 두 개의 CNOT 게이트들을 통과하게 되면 모두 양자 얽힘이 있게 되며 세 큐비트의 상태는 다음과 같은 GHZ 상태로 표현된다.
하지만 오류 정정을 위해 추가한 두 큐비트에는 관심이 없기 때문에 무시할 수 있고, 오류가 발생한 큐비트는 원래의 상태로 다시 돌아옴을 확인할 수 있다. 두 번째, 세 번째 큐비트가 오류로 뒤집힌 경우에도 마찬가지로 오류가 정정된다.
이와 같이 큐비트의 상태를 붕괴시키지 않고도 양자 게이트들을 활용하여 오류를 정정할 수 있다. 하지만 3-큐비트 비트 플립 코드에서 만약 두 개 이상의 큐비트가 오류로 인해 뒤집힐 경우 오류를 정정하는 것이 불가능하며, 이러한 경우의 오류를 해결하기 위해서는 더 많은 보조 큐비트가 필요하다.
3-큐비트 위상 플립 코드(3-qubit phase flip code)는 한 큐비트의 위상이 바뀌는 오류를 정정하기 위하여 두 개의 보조 큐비트를 추가적으로 활용하는 오류 정정 코드이다. 기본적으로 3-큐비트 비트 플립 코드와 기본적인 원리는 동일하며 다만 큐비트의 기저를 하다마드 기저(Hadamard basis)로 바꾼 후 오류를 정정한다.
한 큐비트의 위상이 뒤집히는 오류를 정정하기 위하여 큐비트의 초기 상태가 $$\left| \psi \right\rangle= \alpha\left| 0 \right\rangle + \beta|1\rangle$$일 때, $$\left| 0 \right\rangle$$ 상태로 초기화된 두 큐비트를 준비한다. 세 큐비트들이 처음 두 개의 CNOT 게이트와 하다마드 게이트를 통과하게 되면 큐비트의 상태는 다음과 같이 하다마드 기저에서 얽힘이 있는 상태로 표현된다.
Shor 코드는 한 큐비트의 오류를 정정하기 위하여 여덟 개의 보조 큐비트를 추가적으로 활용하는 오류 정정 코드이며, 2015년 Peter Shor[6]에 의해 최초로 소개되었다. Shor 코드는 3-큐비트 비트 플립 코드와 3-큐비트 위상 플립 코드가 합쳐져 있는 형태로 파울리 행렬(Pauli matrix)의 형태로 표현되는 일반적인 단일 큐비트 오류를 정정할 수 있다.
Shor 코드에서는 오류를 보정하고자 하는 큐비트와 $$\left| 0 \right\rangle$$ 상태로 초기화된 여덟 개의 큐비트를 추가적으로 준비한다. 아홉 개의 큐비트는 양자 얽힘이 있는 상태에 따라 각각 세 그룹으로 나뉜다. 이 때 첫 번째, 네 번째, 일곱 번째 큐비트는 원래 큐비트의 위상 오류 보정을 위해 사용되며, 연속되는 큐비트 세 개씩 묶인 각 세 그룹은 해당하는 큐비트의 비트 오류 보정을 위해 사용된다.
현재 성능면에서 대표적인 시스템으로 꼽을 수 있는 이온 트랩의 경우, 순수하게 게이트 충실도 성능 측면에서는 미국 NIST에서 마이크로파 기반 단일 큐비트 게이트의 충실도 99.9999%를 얻었고, 레이저 기반 2-큐비트 게이트 충실도 99.92%를 얻은 바 있다.[11] 이후 실제 양자컴퓨터 개발을 위한 시스템에서 벤치마킹으로 얻은 충실도의 경우, IonQ에서 개발 중인 이온 트랩 기반 11-큐비트 양자 컴퓨터가 대표적인데, 이 시스템에서는 단일 큐비트 게이트의 충실도는 평균 99.5%, 2-큐비트 게이트 충실도는 평균 97.5%로 나타났다.[12]
한편 확장성 측면에서 주목을 받고 있는 초전도 큐비트의 경우, 2019년 구글이 양자 컴퓨터 시카모어(Sycamore)를 이용하여 유사 무작위 양자회로(pseudo-random quantum circuit)에서의 양자 우위를 보이는 실험에서 게이트 충실도를 발표하였는데, 단일 게이트를 각각 따로 할 때(isolated)인 경우 단일 큐비트 게이트에 대해 0.15%, 2-큐비트 게이트에 대해 0.36%의 오류율을 얻었고, 여러 개의 게이트를 같이 하는 경우(simultaneous)에는 각각 0.16%, 0.62%의 오류율을 얻었다고 보고했다.[13]
양자 컴퓨터가 실용화되기 위해서는 수많은 게이트들을 적용했을 때에도 신뢰할 수 있을만한 결과값이 나와야 하고, 이를 위해서는 게이트 충실도가 현재보다 더 100%에 가까울 필요가 있으므로 게이트 충실도를 향상시키는 것은 여전히 하드웨어 개발에 있어서 중요한 요소로 다루어지고 있다.
IonQ의 이온 트랩 기반 양자 컴퓨팅 시스템의 2-큐비트 게이트 충실도를 각 큐비트 조합에 대해 나타낸 것. 참고문헌 [12]의 그림을 재구성함.
측정-기반 양자 계산 (Measurement-based Quantum Computation)[편집]
현재 양자 계산 방식에는 양자 회로 모형, 양자 튜링 기계(quantum turing machine), 단열 양자 계산 그리고 측정-기반 양자 계산이 있다. 가장 대표적인 양자 계산 방식인 양자 회로 모델에서의 경우 양자 논리 게이트 혹은 유니타리 연산자를 이용하여 양자 계산을 수행한다. 반면 측정-기반 양자 계산(measurement-based quantum computation)은 양자 논리 게이트가 아닌 측정(measurement)을 통하여 범용 양자 계산을 수행한다. 측정-기반 양자 계산에는 두가지 모델이 있는데, 하나는 전송-기반 양자 계산(teleportation-based quantum computation) 모델이고, 다른 하나는 일방향 양자 계산(One-way quantum computation) 모델이다. 전송-기반 양자 계산의 경우, 초기 곱 상태(product state)에 2-큐비트 측정(two-qubit measurements) 혹은 몇 개의 큐비트 측정(few-qubit measurements)을 이용하는 반면, 일방향 양자 계산에서는 얽힌 초기 상태와 단일 큐비트 측정(one-qubit measurement)을 이용한다. 이들은 언뜻 보기에는 서로 달라보이지만 결국 서로 동치 모형이며, 범용 양자 계산(universal quantum computation)이다.
전송-기반 양자 계산 (Teleportation-based Quantum Computation)[편집]
아주 간단한 양자 전송(quantum teleportation)을 생각해 보자. 앨리스(Alice)는 입자 A와 B를 가지고 있고 밥(Bob)은 입자 C를 가지고 있고 B와 C입자는 양자 얽힘 상태이다. 앨리스는 자신이 가지고 있는 임의의 양자 상태 A를 밥에게 전송하고 싶어 한다. 그래서 앨리스는 양자 얽힘 상태에 있는 한 쪽 입자 B와 입자 A에 대해 벨 측정(Bell measurement)을 수행하여 양자 얽힘 상태에 있는 다른 쪽 입자 C에게 A의 상태를 전송한다. 이 때, 밥은 앨리스가 A,B 입자들의 측정 결과값 정보를 받아서 C입자의 양자 상태를 보정(파울리 연산자 적용)하면 제대로 된 입자 A의 양자 상태를 받을 수 있다.
이 양자 전송 원리를 기반으로 하여 전송-기반 양자 계산(teleportation-based quantum computation)을 수행할 수 있다. 초기 상태를 곱 상태로 입력하고 앞에서 언급한 양자 전송 원리처럼 2-큐비트 측정(two-qubit measurement)을 연속적으로 적용하면, CNOT 게이트(Controlled-NOT gate) 혹은 CZ 게이트(Controlled-Z gate)와 동일한 연산이 수행된다. 물론, 파울리 연산자로 보정해야 한다. 전송-기반 CNOT 게이트 연산의 간단한 예시를 아래처럼 양자 회로로 표현할 수 있다.
전송-기반 양자 계산과는 달리 초기 상태가 양자 얽힘 상태이다. 이는 일방향 양자 알고리듬하고 상관없이 독립적으로 준비한다. 일방향 계산의 재료 상태(resource state)라고도 부르며 양자 게이트 및 정보 흐름 역할을 한다. 대표적인 얽힘 상태로는 클러스터 상태(cluster state), 그래프 상태(graph state), AKLT 상태(AKLT state), 위상 클러스터 상태(topological cluster state) 등이 있다. 이러한 양자 얽힘 상태만 준비된다면, 이중 다중 큐비트 측정보다 더 단순한 단일 큐비트 측정만 하기 때문에 양자 계산을 하는데 있어서 특히 실험적으로 구현하는데 있어서 용이하다. 일방향이라고 부르는 이유는 초기 재료 상태에 대해 일련의 측정을 하여 얻은 결과 상태는 다시 초기 상태로 되돌릴 수 없기 때문이다.
처음 제안된 일방향 양자 계산 모형에서 얽힘 상태의 재료로 클러스터 상태를 사용하였다.[16] 클러스터 상태를 재료로 하는 일방향 양자 계산의 과정은 다음과 같다.
고전 데이터와 프로그램에 대한 고전 입력을 준다.
충분히 큰 2D-클러스터 상태(cluster state)를 준비한다. 이는 이 양자 계산의 재료로 사용한다.
클러스터 안에 있는 큐비트들에 대해 일련의 적응(adaptive) 단일 양자 측정을 수행한다. 즉, 매 측정 단계마다, 이전 측정결과와 프로그램을 고려하여 다음 측정 방향을 설정해 주어야 한다.
측정 후 계의 상태는 $$\left| \xi^{\alpha} \right\rangle|\psi_{\text{out}}^{\alpha}\rangle$$의 형태이다. 여기서 𝛼는 측정 결과값을 의미한다.$$ |\psi_{\text{out}}^{\alpha}\rangle$$는 클러스터 상태의 일부를 측정하고 남은 상태에 적당한 파울리 연산을 한 후의 결과(output) 상태이다. 측정 값에 의존하는 양자상태 $$\left| \xi^{\alpha} \right\rangle$$는 측정된 여러 개의 큐비트로써 곱 상태로 되어있다.[17]
클러스터 양자 상태를 근원으로 하는 측정-기반 양자 계산:가장 왼쪽 줄이 입력 상태이다. 일련의 적응 측정을 통하여 맨 오른쪽 줄에서 결과 상태를 얻는다. 참고문헌 [17]의 그림을 재구성함.
단열 양자 컴퓨팅(Adiabatic quantum computing, AQC)은 계산하고자 하는 바를 양자 시스템의 해밀토니안(Hamiltonian)의 형태로 변환하고 이를 조작하여 결과값을 유도하는 양자 컴퓨팅의 한 형태이다. 게이트 기반 양자 컴퓨팅 모델(양자 회로 모델)과 같이 임의의 연산을 모델링 할 수 있다는 점에서, 즉 범용성(universality)을 보장한다는 점에서 큰 의미를 지닌다.[18] 그러나 대개 AQC는 특정 최적화 문제를 빠른 시간 안에 풀기 위한 양자 이점(quantum advantage)의 목적으로 사용되며, 보다 나은 성능을 위해 양자 어닐러(quantum annealer, QA) 혹은 양자 교대 연산자 가설풀이(quantum alternating operator ansatz)의 형태로 변용된다.
단열 양자 컴퓨팅은 Max Born과 Vladimir Fock이 정리한 단열 정리에 이론적 뿌리를 두고 있다[19]. 단열 정리에 따르면 임의의 양자 시스템에 대해 외부 조건이 충분한 시간 동안 천천히 변화하고, 해밀토니안의 에너지 스펙트럼 간의 차이가 존재할 때(non-degenerate) 해당 양자 시스템의 고유 상태(instantaneous eigenstate)가 지속된다. 해밀토니안이 변화하여 양자 시스템의 상태 공간도 변하지만, 변화가 충분히 천천히 일어난다면 시스템이 이에 적응하여 에너지 상태의 확률 분포도 대응하여 변화한다는 것이다.
단열 정리가 함의하는 바는 주어진 계산(혹은 최적화) 문제를 양자 시스템의 단열 과정(adiabatic process)으로 표현할 수 있다는 것이다. 우선, 이미 잘 알려진 바닥 상태를 지니는 초기 해밀토니안($$H_{\text{init}}$$)을 설정한다. 그리고 주어진 계산 문제의 해를 바닥 상태로 지니는 해밀토니안($$H_{\text{final}})$$을 설정한 뒤, 최종 해밀토니안($$H(t)$$)을 둘의 가중 평균($$H(s)= (1 - s)H_{\text{init}} + sH_{\text{final}}$$)으로 나타낸다. 슈뢰딩거 방정식에 따라 단열 과정을 진행하면 adiabatic 정리에 의해 초기 해밀토니안의 바닥 상태는 최종 해밀토니안의 바닥 상태로 변화하게 된다. 따라서 주어진 계산 문제는 최종 해밀토니안의 바닥 상태를 알아내는 쉬운 문제로 전환된다.
이 때 외부 조건이 얼마나 천천히 변화해야 하는지, 바꿔 말해 AQC가 완료되기까지 요구되는 실행 시간에 대해 정확히 알아내는 것은 어렵다. 나아가 실제 고전 컴퓨터보다 성능 상의 이점(양자 이점)이 있는지에 대해서도 알려진 바가 없다. 다만 해밀토니안의 에너지 스펙트럼 간의 차이가 클수록 고유 상태가 다른 상태로 변화할 가능성이 낮아져 빠른 실행이 가능하다. 실행 시간은 해밀토니안의 에너지 스펙트럼 간의 차이의 최소값의 제곱에 반비례하는 것으로 알려져 있다[20]
단열 양자 컴퓨팅(AQC)은 범용성(universality)을 지닌 것으로 알려져 있지만, 임의의 문제를 AQC 문제로 변환하는 것은 쉽지 않기 때문에 대부분의 범용 양자 컴퓨터는 게이트 기반 모델을 채택하여 연구되고 있다. 그러나 고전 컴퓨터가 해결하기 어려운 것으로 잘 알려진 NP 문제들의 전역적 최적해를 찾는 문제들에 대해서는 AQC 문제로 변환하는 과정이 간단하며, 현재 대부분의 AQC 기반 모델들은 이러한 최적화 문제를 해결하기 위해 사용되고 있다.
AQC 모델을 기반으로 알고리듬을 설계할 때 최종 해밀토니안($$H_{\text{final}})$$의 바닥 상태를 찾아내는 것은 매우 어렵다. 반면 최적화 문제에 대해서는 최종 해밀토니안의 바닥 상태가 계산하고자 하는 최적화 문제의 해답과 일치하도록 구성하는 것은 쉽다. 이는 대개 NP 문제의 특성에서 기인한다. NP 문제의 특징은 문제 공간은 지수적으로 크지만, 문제를 기술하거나 찾은 답을 확인하기 위한 절차는 간소하다는 것이다. 대부분의 경우 최적해가 만족해야 할 성질은 사람이 쉽게 모델링 할 수 있다. 이러한 모델링을 기반으로 최적해가 만족해야 할 성질을 만족하지 않는 상태에 대해 페널티를 부과하면 아무런 페널티도 없는 상태, 즉 바닥 상태는 최적해의 답이 된다. 나아가, 이러한 모델링은 최적해를 찾을 수 없는 문제에 대해서도 페널티를 최소화하는 답을 도출해낸다는 점이다. SAT, Max-Cut 등 유명한 문제에 대해서는 해밀토니안 구성 방법이 이미 개발되어 있다.
최적화 문제를 AQC 모델을 이용해 푸는 과정은 다음 같다.
쉽게 구성할 수 있는 초기 상태를 그라운드로 지니는 초기 해밀토니안을 설정한다. 임의의 상태를 그라운드로 설정하는 것은 어려운 일이므로 쉽게 만들 수 있는 초기 상태를 그라운드로 설정하는 것이 중요하다. 일반적으로 초기 상태는 균등 분포를 지니도록 한다.
계산하고자 하는 최적화 문제의 해답을 바닥 상태로 가지는 최종 해밀토니안을 설정한다. 대부분의 경우 이 과정은 간단하게 수행된다.
예. 3-SAT 문제
3-SAT 문제는 3개의 부울 표현식으로 구성된 항들을 모두 만족시키는 해가 있는지 찾는 문제로 대표적인 NP 문제이다.$$ C_{1}, C_{2},\ldots, C_{M}$$ 의 $$M$$개의 항으로 구성된 3-SAT 문제가 주어졌다고 가정하자. 이 때, AQC를 위한 목적 해밀토니안을 아래와 같이 구성하면 각 항들을 만족시키지 않는 상태에 대해서 페널티를 부과하게 된다. 따라서 아무런 페널티도 없는 바닥 상태와 최적해가 일치하게 된다.
최종 해밀토니안은 시간에 따라 초기 해밀토니안에서 최종 해밀토니안으로 변화하도록 두 해밀토니안의 가중 평균으로 설정한다. 이 때, 최종 해밀토니안은 초기 상태$$(t= 0)$$에서는 1)에서 구성한 바닥 상태에 머물게 되며, 단열 정리에 의해 단열 과정이 끝난 뒤$$(t \rightarrow \infty)$$에는 최종 해밀토니안의 바닥 상태, 즉 최적해와 같은 상태에 놓이게 된다. 실제로는 여러 제반 사항을 고려하여 최대 사용할 시간 $$T$$를 정한 뒤 시간에 따른 변화를 기술한다.
이론적으로 충분한 시간이 주어지면$$(time \rightarrow \infty),$$ 최종 측정 결과는 100% 확률로 최적해와 동일해야 한다. 당연하게도 실제 상황에서는 제약 조건 등을 고려하여 최대 사용할 시간 $$T$$를 정한 뒤, 오차 범위 이내에서 근사하는 과정이 필요하다.
특정 경우에 대해서는 AQC를 이용한 최적화 문제 해결이 다항 시간 안에 수행되는 것으로 알려져 있지만, 일반적인 경우에 대해서 다항 시간을 보장할 수 없고, 나아가 양자 이점이 있는지도 명확하지 않다. 오히려 단순한 AQC 모델은 실행 시간과 관련하여 결함을 지니고 있을 것으로 예측되며, 이러한 시간 문제를 해결하기 위한 양자 어닐링과 같은 기술이 사용된다.
양자 어닐링 (Quantum Annealing, QA)과 양자 교대 연산자 가설풀이 (Quantum Alternating Operator Ansatz)[편집]
양자 어닐링(quantum annealing)은 AQC와 유사한 방식으로 최적화 문제를 풀기 위해 고안된 기술로 효율적인 실행 시간이 보장되지 않는 AQC의 문제점을 해결하기 위해 열역학적 현상을 이용해 양자 터널링(quantum tunneling) 기술을 이용하여 빠른 시간 안에 많은 상태를 탐색하도록 하는 기술이다. 양자 어닐링의 경우 AQC와 달리 범용성을 보장하지 않기 때문에 실제 특정 최적화 문제를 풀기 위해서만 사용된다. 캐나다의 D-wave systems는 양자 어닐링을 이용한 양자 컴퓨터를 상용화한 바 있다[21].
양자 어닐링은 양자 터널링 현상을 이용해 AQC에 비해 단열 과정을 구현하기 쉽고 빠르게 작동하도록 만든다는 특징이 있다. 단열 정리의 조건을 만족시키기 위해서는 상태 공간의 변화 속도를 충분히 느리게 해야 하는데, AQC의 문제점은 현실적으로 이러한 조건을 만족시키는 것이 매우 어렵고 계산 시간이 느리다는 것에 있다. 빠르게 변화하는 상태 공간에 대해서는 해밀토니안의 고유 상태가 이를 쫓아가지 못하게 되고, 이에 따라 변화하는 시스템에서의 에너지 준위는 달라지게 된다. 쉽게 말해, 단열 과정에서 바닥 상태가 더 이상 유지되지 못하게 되어 오랜 시간이 지나도 전역적 해와 일치하지 않게 될 확률이 증가하는 것이다. 현실적으로 AQC는 구현하기 어려우며 여러가지 제약으로 인해 단열 과정에서 고유 상태가 극소(local minimum)에 머무르게 되는 현상이 발생할 수 있다.
이러한 문제를 해결하기 위해 양자 어닐링은 수직 방향 장(transverse field)를 가하여 양자 터널링(quantum tunneling) 현상을 발생시켜 극소에서 벗어날 수 있도록 한다. 양자 터널링 현상은 임의성을 지니고, 결정적이지 않으므로 최종 결과값의 최적성을 보장할 수 없는 휴리스틱(heuristic) 기술이다. 대신 양자 어닐러는 다수의 시뮬레이션을 실행하여 전역해에 가까운 값을 찾도록 시도한다. 양자 어닐러의 성능에 관해서는 논란이 있지만 현재 시점에서는 양자 이점이 없는 것으로 결론이 모아지고 있다[22].
양자 교대 연산자 가설풀이(quantum alternating operator ansatz)도 AQC에 기반하여 최적화 문제를 푸는 양자 컴퓨팅 기술로 AQC와 달리 초기 해밀토니안과 최종 해밀토니안을 교대로 적용하는 방식으로 작동한다. 본질적으로 임의성을 지니는 양자 어닐링에서와 달리 양자 교대 연산자 가설풀이의 경우 교대(alternation) 적용 횟수를 늘릴수록 최적해를 찾을 확률을 높일 수 있다. 양자 교대 연산자 가설풀이는 이론적으로 완벽하지만 현실에서 구현하기 어려운 AQC와 현실에서 잘 동작하지만 최적해를 찾기 어려운 QA의 절충된 형태로 볼 수 있다[23].
NISQ 시대로의 돌입을 의미하는 53 큐비트 양자 연산을 위한 구글의 Sycamore 프로세서 사진.[13]
양자 연산은 인수분해 문제와 같이 고전적으로 오래 걸리는 어려운 연산을 가능케 할 것으로 기대되는 양자현상에 기반한 연산 방식이다. 샘플링 문제와 같이 복잡도 이론에 기반하여 고전적으로는 성취하기 어렵다는 것이 알려진 문제들의 해결 역시 양자 연산을 통하여 가능케 될 것으로 기대된다. 다양한 이점을 가질 것으로 예상되는 양자 컴퓨터의 개발이 어려운 이유는 양자 역학의 근본 성질에 기인한다. 양자 물리계는 본질적으로 측정 시 물리계에 교란이 발생한다. 교란 없는 정보 생성과 가공을 위해서는 물리계가 외부로부터 가능한 고립되어야 한다. 외부로부터의 영향을 최소화하면서, 큐비트를 안정적으로 생성하고 완벽하게 다른 큐비트들과 연결하는 것은 매우 높은 기술적 성숙도를 필요로 한다.
이러한 어려움을 극복하기 위해서는 ‘양자 오류 정정(quantum error correction)’ 기술이 필요하다.[25] 양자 오류 정정은 높은 얽힘 상태를 이용하여 외부로부터의 교란을 막는 방식을 활용한다. 보다 구체적으로 양자 오류 정정의 얽힘은 대상 물리계의 일부에 대한 측정 및 연산을 수행할 때 다른 물리계가 교란할 수 없는 방식으로 고안된다. 문제는 양자 오류 정정 구현에 큰 비용이 든다는 데에 있다. 오류 정정 기술을 통해 큐비트들이 연결된 시스템을 만들기 위해서는 많은 수의 추가적인 큐비트가 필요하다. 가령 수천 개의 큐비트를 보호하기 위해서는 수백만개의 추가적인 물리 정정 큐비트가 필요하다. 이에 양자 오류 정정에 기반한 이른바 오류허용(fault-tolerant) 양자 연산은 아직 그 실현 시점이 언제가 될지 불확실한 것으로 보인다.[26]
이와 같이 매우 큰 규모의 큐비트 시스템을 필요로 하는 오류허용 양자 연산이 어려운 상황에서, 가까운 미래에 현실적으로 실현 가능한 규모의 큐비트 시스템에 대한 논의를 하는 것은 의미 있는 일이다. NISQ(Noisy Intermediate-Scale Quantum) 연산은 이러한 문제의식을 바탕으로 2017년 Preskill이 처음 제안한 개념이다. NISQ에서 ‘intermediate-scale’은 가까운 미래에 실현 가능한 규모의 큐비트 시스템을 지칭한다. Preskill의 예측에 따르면, 50에서 수백 큐비트 규모가 이에 해당한다. 2019년도에는 53큐비트로 구성된 양자 연산 프로세서가 IBM과 구글 양자 연산 연구그룹에서 각각 제안되었다.[13] 이는 현재 NISQ 양자 연산의 실험적 구현이 시작되는 단계에 있다는 사실을 시사하는 결과이다. 아래 그림 14은 구글에서 개발한 53큐비트 Sycamore 프로세서를 보여준다. NISQ에서 ‘noisy’는 다루는 양자 물리계가 외부 환경의 영향을 받는다는 사실을 강조한다. 현재까지 최선의 이온 트랩이나 초전도 회로 방식으로 양자 연산을 구현할 때, 하나의 2-큐비트 게이트 당 0.1% 이상의 오류가 존재한다.[27][28] 잡음으로 인한 오류는 양자 연산 프로세서의 규모를 키우는데 큰 제약이 된다. 이에 대해서는 수 천 개 큐비트 시스템에서 잡음이 신호를 압도할 것이라는 정성적 예측이 존재한다.[26]
NISQ 연산을 통해 유용한 결과를 제공할 것으로 기대되는 연구 분야로, 최적화 분야, 양자 어닐링 현상을 활용한 연산 분야, 잡음-회복(noise-resilient) 회로를 통한 잡음 제어 연구 분야, 양자 기계 학습(machine learning) 분야, 양자 화학 분야 등이 있다. IBM Q에서 발표한 NISQ 시대 양자 연산을 통해 양자 이점(quantum advantage)이 나타날 것으로 기대되는 몇 가지 중요 분야에서 어떠한 방식으로 양자 연산 기술이 발전될 것으로 기대되는 지 아래 항목을 통하여 설명한다.
IBM Q에서 발표한 NISQ 시대 양자 연산을 통해 양자 이점(quantum advantage)이 나타날 것으로 기대되는 연산 분야. 참고문헌 [29]의 그림을 재구성함.
양자 컴퓨터가 고전 컴퓨터와 다른 방식으로, 고전 컴퓨터가 풀 수 없는 문제를 풀어낼 것은 확실해 보인다. 하지만 양자 컴퓨터의 연산 능력이 무제한적일 것으로 예상되지는 않는다. 예컨대 양자 컴퓨터는 유한한 대상(object) 집합으로부터 최적화된 집합을 구해내는 조합 최적화(combinatorial problem) 문제와 같이 어려운 NP-hard 문제를 풀지는 못할 것이다. 양자 컴퓨터가 이점을 보일 것으로 기대되는 연산 분야는 어려운 NP-hard 문제를 ‘근사적’으로 해결하는 분야이다. 예컨대, $$x$$개의 제한 조건에 대하여 길이 $$l$$의 수열을 구해야 하는 문제라면 양자 연산을 사용하여 근사적으로 가능한 많은 $$x'$$개의 제한 조건을 푸는 수열을 구할 수 있을 것이라 기대된다[26]. NP-hard 복잡도와 현재 고전 컴퓨터가 풀 수 있는 문제의 복잡도 격차가 크므로 그 중간 정도의 복잡도 문제를 상기 방식으로 양자 연산을 통해 해결할 것으로 기대할 수 있다.
고전-양자 하이브리드 알고리듬을 이용한 연산 방식은 NISQ 시대에 최적화 분야에서 양자 컴퓨터가 연산 효율을 높일 것으로 기대되는 또 다른 분야 중 하나이다. 이 방식에서 양자 컴퓨터는 상태를 준비하고 측정하는 과정을 담당하며, 고전 연산을 통하여 최적화 결과를 도출한다. 고전 최적화 장치와 양자 연산 장치 사이의 피드백 시스템을 반복하여, 근사적으로 최적화된 결과를 도출할 수 있을 것으로 기대된다. 고전 조합 최적화 문제에 이러한 방식이 적용될 경우 이와 같은 연산 방식은 QAOA(Quantum Approximate Optimization Algorithm)이라 부른다. 해밀토니안의 해를 구하는 등의 양자역학적 문제를 해결하는 데 사용될 경우 고전-양자 알고리듬은 VQE(Variational Quantum Eigensolver) 등의 이름으로 지칭된다.
오류허용(fault-tolerant) 양자 연산은 고비용 문제로 인하여 NISQ 단계에서는 실현 불가능할 것으로 보인다. 하지만, NISQ 기술은 그 정의상 어떤 방식으로든 잡음을 고려하고, 이를 줄이는 문제를 해결해야 한다. 이러한 목적으로 고려되는 기술로서 잡음-회복 양자 회로가 있다. 모든 게이트에서 단일 결함이 있을 수 있는 일반적인 회로라면 일반적으로 게이트마다 게이트 수의 역수에 비례하는 오류율만 허용된다[26]. 이에 반해 잡음-회복 양자 회로의 경우, 연산 능력에 치명적인 오류를 가져올 수 있는 게이트의 수를 제한적으로 둘 수 있다. 잡음-회복 특성은 회로의 깊이(depth)가 작거나, 최종 측정값 당 오류율이 일정하게 주어지는 등의 요인으로 나타난다. 2017년에는, 회로의 규모, 즉 깊이 정도와 상관없는 오류허용에 대해 분석하는 동시에 VQE를 사용하여 특정 해밀토니안의 최저 에너지 상태를 계산한 연구 결과가 보고된 바 있다.[30]
기계 학습(machine learning)은 다양한 분야에 파급력을 갖고 있는 연구 방법론으로, NISQ 시대에 기계 학습이 갖게 될 영향에 대해서 논의하는 것은 자연스러운 일일 것이다. 현재 기술 단계에서는 양자 기계 학습이 고전 기계 학습에 비하여 어느 정도 양자 이점(quantum advantage)을 가져올지 알 수 없지만, 최근 진행되고 있는 양자 기계 학습 연구는 양자 연산의 효율을 높이는 한 방향으로 고려되고 있다.[31] 양자 기계 학습이 중요한 연구 방향으로 여겨지는 이유 중 하나는 해당 방식에서 QRAM(Quantum Random Access Memory)의 활용이 가능할 것으로 기대되기 때문이다. 큐비트를 메모리로 사용할 경우 큰 길이의 벡터, 즉 큰 고전 데이터 정보를 적은 수의 큐비트에 저장할 수 있다. 반면, QRAM 기술에도 양자 상태에 정보 입력과 출력시 정보 손실이 일어난다는 난점이 존재한다. 입/출력을 모두 양자 시스템으로 한다면 이런 문제를 피할 수 있을 것으로 예상된다. 이와 같이 입/출력이 모두 양자 시스템으로 주어진 양자 기계 학습 모델은 복잡계 양자 물리 문제를 푸는 등의 양자 고유 문제에 적용되기 용이할 것으로 기대된다[26].
↑ 1.01.1National Academies of Sciences, Engineering, and Medicine, Quantum computing: Progress and prospects. (The National Academies Press, 2019). doi:10.17226/25196.
↑ 4.04.1J. Kelly et al., State preservation by repetitive error detection in a superconducting quantum circuit, Nature 519, 66 (2015). doi:10.1038/nature14270.
↑ 5.05.1M. A. Nielsen, & I. L. Chuang, Quantum computation and quantum information (Cambridge University Press, 2002)
↑ 6.06.1Peter W. Shor, Scheme for reducing decoherence in quantum computer memory, Physical Review A 52, R2493(R) (1995). doi:10.1103/PhysRevA.52.R2493.
↑Andrew M. Steane, Error correcting codes in quantum theory, Physical Review Letters 77, 793 (1996). doi:10.1103/PhysRevLett.77.793.
↑D. Gottesman, Stabilizer codes and quantum error correction, arXiv:quant-ph/9705052 (1997).
↑A. G. Fowler, M. Mariantoni, J. M. Martinis & A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Physical Review A 86, 032324 (2013). doi:10.1103/PhysRevA.86.032324.
↑J. P. Gaebler et al., High-fidelity universal gate set for Be 9+ ion qubits, Physical Review Letters 117, 060505 (2016). doi:10.1103/PhysRevLett.117.060505.
↑ 12.012.1K. Wright et al., Benchmarking an 11-qubit quantum computer, Nature Communications 10, 5464 (2019). doi:10.1038/s41467-019-13534-2.
↑ 13.013.113.2F. Arute et al., Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019). doi:10.1038/s41586-019-1666-5.
↑D. Gottesman & I. L. Chuang, Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations, Nature 402, 390 (1999). doi:10.1038/46503.
↑R. Raussendorf, D. E. Browne & H. J. Briegel, Measurement-based quantum computation on cluster states, Physical Review A 68, 022312 (2003). doi:10.1103/PhysRevA.68.022312.
↑ 17.017.1H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf & M. Van den Nest, Measurement-based quantum computation, Nature Physics 5, 19 (2009). doi:10.1038/nphys1157.
↑S. J. Devitt, W. J. Munro, & K. Nemoto, Quantum error correction for beginners, Reports on Progress in Physics 76, 076001 (2013). doi:10.1088/0034-4885/76/7/076001.
↑C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol & D. M. Lucas, High-fidelity quantum logic gates using trapped-ion hyperfine qubits, Physical Review Letters 117, 060504 (2016). doi:10.1103/PhysRevLett.117.060504.
↑R. Barends et al., Superconducting quantum circuits at the surface code threshold for fault tolerance, Nature 508, 500 (2014). doi:10.1038/nature13171.
↑IBM Research Insights, Coming soon to your business: Quantum computing[1]
↑I. H. Kim, Noise-resilient preparation of quantum many-body ground states, arXiv:1703.00032 (2017).
↑X. Gao, Z. Zhang & L. Duan, An efficient quantum algorithm for generative machine learning, arXiv:1711.02038 (2017).
