양자 컴퓨팅(Quantum Computing)은 고전적 컴퓨팅과는 달리 양자역학의 원리에 기반한 새로운 계산 패러다임이다. 양자 컴퓨터는 양자역학의 특성을 이용해 정보를 처리하며, 이를 통해 고전적 컴퓨터로는 매우 어렵거나 불가능한 계산을 효율적으로 수행할 수 있다.

고전적 컴퓨터는 정보를 이진법으로 처리하며, 0과 1 두 상태만을 가질 수 있는 비트를 사용한다. 반면, 양자 컴퓨터의 정보 처리의 기본 단위는 큐빗(qubit)으로, 0과 1의 상태의 중첩(superposition) 상태가 가능하다(Fig. 1). 이 덕분에 양자 상태를 병렬로 처리할 수 있어 계산의 효율성이 높아지게 된다. 큐빗의 또다른 특징인 얽힘은 두 개 이상의 큐빗이 상호작용하여 서로 독립적인 상태가 아닌 하나의 결합된 상태로 존재하는 현상을 말한다. 얽혀있는 두 개의 큐빗중 한 개의 상태를 측정하면 다른 큐빗의 상태도 즉시 결정되는데, 이를 이용하여 양자 컴퓨팅의 독특한 양자 알고리즘이 개발되었다.

Figure 1. The quantum state vector Ψ of a qubit represented on the Bloch sphere. The state vector exists as a vector on the unit sphere with a radius of 1. When the state vector is located at the north pole, it corresponds to the state 0, and when located at the south pole, it corresponds to the state 1 [Data from Ref. 13].

몇몇 양자 알고리즘들은 이러한 큐빗의 중첩과 얽힘을 이용하여 고전적 컴퓨터보다 더 빠른 속도로 계산이 가능하다는 것이 알려져 있다. 예를 들어, 고전적 알고리즘은 소인수분해 문제를 해결하는 데 지수 함수의 시간이 소요되지만, 양자 알고리즘 쇼어 (Shor) 알고리즘은 이를 다항 시간(polynomial time) 내에 해결할 수 있다. 이 쇼어 알고리즘은 현대 암호학의 기반이 되는 RSA 암호 체계를 위협하는 핵심 기술로 여겨져 전 세계적으로 연구가 활발하다.

고전적 알고리즘보다 더 빠르게 문제를 해결할 수 있는 잠재력을 가지고 있는 다른 양자 알고리즘으로서 그로버 알고리즘은 비정형 데이터베이스에서 검색 문제를 기존의 방법보다 훨씬 빠르게 해결할 수 있다[1]. 고전적인 방법에 의해 N개의 항목 중에서 하나의 정답을 찾는 데 O(N)의 시간이 걸리지만, 1996년 로브 그로버에 의해 발표된 그로버 양자 알고리즘은 이를 O(N) 시간으로 단축할 수 있다. 이 결과에 의하면 그로버 알고리즘은 비정형 데이터 검색 문제에서 매우 큰 성능 향상을 제공한다.

이러한 양자 알고리즘들은 고전적 컴퓨터가 풀지 못하거나 매우 오랜 시간이 걸리는 문제들을 새로운 방식으로 해결할 수 있다. 예를 들어, 물리학, 화학, 생물학 등에서의 시뮬레이션 문제는 고전적 컴퓨터로는 매우 어려운 계산이지만, 양자 컴퓨터는 양자역학적 특성을 직접 활용해 이러한 시뮬레이션을 효율적으로 수행할 수 있다.

양자 알고리즘은 고전적 머신러닝 알고리즘을 가속화할 수 있는 가능성을 제공한다. 예를 들어, 양자 컴퓨팅을 활용하면 고차원 데이터에서의 최적화, 패턴 인식, 클러스터링 등의 문제를 더 빠르게 해결할 수 있다. 양자 컴퓨팅과 양자 알고리즘의 발전은 계산의 본질을 변화시킬 잠재력이 있다. 양자 컴퓨터가 실용화되면 암호학 및 사이버보안[2-4], 최적화 문제[5], 과학적 시뮬레이션[6, 7], AI와 머신러닝[8, 9], 및 화학[10-12] 등 다양한 분야에서 혁신을 가져올 수 있다. 본 리뷰에서는 가장 응용 잠재력이 높은 양자 알고리즘 중의 하나이며 전 세계적으로 최근 연구가 활발히 진행되고 있는 그로버 알고리즘의 연구 현황을 살펴보고 응용 가능한 분야와 시사점을 다루고자 한다.

1. 비정형 검색 문제의 설명

비정형 검색 문제는 정렬되지 않은 N개의 요소에서 특정 요소를 찾는 문제이다. 이 문제는 데이터에 어떠한 구조나 규칙이 없기 때문에 각 요소를 개별적으로 검사해야 한다. 즉, 모든 요소를 일일이 확인해야 하는 고전적 문제이다. 이렇게 정렬되지 않은 목록에서 특정 값을 찾고자 할 때, 비정형 검색 문제에 직면하게 된다. 목록에 규칙이 없으므로, 고전적인 검색 알고리즘은 각 항목을 하나씩 확인하면서 찾고자 하는 값을 찾게 된다.

2. 고전적 검색 알고리즘 및 그 한계의 개요

비정형 검색 문제에 대해 고전적인 알고리즘은 모든 요소를 하나하나 확인해야만 하며, 이로 인해 시간 복잡도가 선형적으로 증가한다. 즉, N 개의 요소를 확인하려면 O(N) 만큼의 시간이 소요된다. 고전적 알고리즘 사용시 평균적으로는 N/2 개를 검사하여 원하는 결과를 찾을 수 있지만, 최악의 경우에는 N 번의 확인이 필요하다. 이와 같은 고전적 알고리즘은 시간 복잡도가 선형(O(N)) 이기 때문에, 데이터셋의 크기가 커질수록 필요한 계산 시간이 급격히 증가한다. 이는 대규모 데이터셋을 다루는 데 비효율적이다.

3. 양자 속도 향상: 그로버 알고리즘이 제공하는 속도 향상

그로버의 알고리즘은 1996년에 Lov Grover 가 제안한 양자 알고리즘으로, 비정형 검색 문제에서 고전적 알고리즘보다 빠른 속도 향상을 제공한다. 즉, 고전적 검색에서는 O(N) 개의 검사를 요구하지만, 그로버 알고리즘은 오직 O(N) 만큼의 검사로 문제를 해결할 수 있다.

그로버의 알고리즘은 이러한 검색 속도 향상은 중첩과 진폭 증폭이라는 원리를 적극적으로 활용한 결과이다. 양자 상태의 중첩을 이용하여 여러 상태를 동시에 탐색할 수 있으므로 이는 다수의 가능한 해결책을 동시에 탐구하는 결과가 된다. 또한 그로버 알고리즘의 독특한 진폭 증폭(Amplitude Amplification)은 그로버 알고리즘의 탐색 속도 향상을 이뤄내는 가장 중요한 요소라고 할 수 있다. 이 과정은, 일정 알고리즘을 반복하여 올바른 해결책의 확률 진폭이 증폭되고, 최종적으로는 올바른 해결책의 측정 확률이 극대화된다. 고전적 알고리즘은 하나하나 요소를 검사하는 반면, 그로버의 알고리즘은 상태 벡터를 올바른 해결책 쪽으로 회전시키며, 약 O(N) 번의 반복 후 올바른 해결책을 매우 높은 확률로 측정할 수 있다.

4. 그로버 알고리즘의 수학적 전개

그로버 알고리즘은 고차원 힐베르트 공간에서 양자 상태에 대한 일련의 변환으로 수학적으로 설명할 수 있다. 주요 구성 요소는 다음과 같다[13-15]:

초기 상태: 그로버 알고리즘은 모든 가능한 상태의 동일한 중첩 상태로 시스템을 초기화한다.

N=2n 개의 가능한 상태에 대해, 초기 상태는 다음과 같이 표현된다:

이 상태는 N 개의 요소에 대해 동일한 확률 진폭을 가진 모든 상태의 중첩을 나타낸다.

오라클: 오라클은 그로버 알고리즘에서 가장 핵심적인 루틴으로서 문제에 특화된 양자 연산으로, 우리가 찾아내려고 하는 정답 상태의 부호를 반전시킨다. 정답 상태 xs 에 대해, 오라클은 다음과 같은 변환을 수행한다:

이를 통해 정답 상태가 다른 요소들과 구별된다.

diffuser 연산자: 오라클이 목표 상태를 표시한 후, 확산 연산자는 목표 상태의 확률 진폭을 증폭시킨다. 이 연산은 양자 상태의 진폭을 그 평균값에 대해 반전시키는 방식으로 동작한다:

여기서 I는 항등 행렬이고, ψ0는 초기 중첩 상태이다. 이 diffuser 연산자는 정답 상태 xs 의 진폭을 증폭시키고, 나머지 상태들의 진폭을 감소시킨다.

그로버 연산자: 오라클과 확산 연산자의 곱은 그로버 연산자 G 를 형성한다:

이다.

이 그로버 연산자를 반복하여 양자 상태의 진폭이 계속 커지게 된다 (진폭 증폭) (Fig. 2, Fig. 3). 그로버 연산자를 한번 수행할 때 전체 양자 상태의 각도가 일정 각도만큼 커지는데 이러면서 양자 상태가 우리가 원하는 정답 상태에 아주 가깝게 된다.

Figure 2. Diagram showing the amplitude amplification process of Grover algorithm [Data from Ref. 13].

Figure 3. (Color online) Experimental deviation density matrices ρexpx0=123, shown in magnitude with the sign of the real part (all imaginary components were small), after 2 (a) and 28 (b) Grover iterations [Adapted with permission from Ref. 15].

최종 측정: 일정한 횟수만큼 그로버 연산자를 반복 수행한후 계산 기저에서 측정하면 아주 높은 확률로 양자 상태는 정답 상태에 가까워져 있다. 즉 우리가 원하는 정답을 찾은 것이다. 이때 최적의 반복 횟수 T 는 다음과 같이 구해진다.

그로버 알고리즘은 단순한 비정형 검색 문제에서의 최초의 성공 이후, 다양한 문제에 적용할 수 있도록 여러 변형과 일반화가 이루어졌다. 특히 암호학, 최적화 문제, 인공지능, 머신러닝, 계산화학 및 생물학 등의 분야에서 그로버 알고리즘의 다양한 응용 사례가 보고되고 있다.

본 리뷰에서 그로버 알고리즘의 주요 변형과 그 응용, 그리고 최근의 연구 동향에 대해 알아본다.

1. 양자 최소값 찾기 (Quantum Minimum Finding)

그로버 알고리즘의 첫 번째 변형 중 하나는 양자 최소값 찾기 문제에 적용된 것이다. 최소값 찾기 문제에서는 모든 요소 중 가장 작은 값을 찾는 것이 목표이다. 고전적 알고리즘에서 최소값을 찾기 위해서는 모든 값들을 확인해야 하는데, 이는 O(N)의 시간이 소요된다. 그로버 알고리즘은 최소값을 찾기 위한 최적화 문제에도 적용되어 속도 향상을 제공한다.

이를 위해 그로버의 기법을 사용하여 값의 비교를 수행하고, 정답의 확률을 점차 증폭시킨다.

그로버의 알고리즘을 사용하면 최소값을 찾는 문제의 시간 복잡도는 O(N)으로 줄어든다.

Dürr와 Høyer 의 연구는 Grover 알고리즘을 최소값 찾기 문제에 적용한 최초의 연구 중 하나이다[16]. Dürr와 Høyer는 고전적인 컴퓨터에서 N 개의 원소 중 최소값을 찾기 위해서는 N-1 번의 비교가 필요하지만, 양자 알고리즘을 사용하면 O(N) 번의 연산으로 최소값을 찾을 수 있음을 보여주었다. 이 알고리즘은 Grover 알고리즘의 원리를 변형하여, 최소값을 찾기 위해 양자 검색 과정에서 최소값을 가진 인덱스를 탐색하는 방식으로 동작한다. 이 연구는 Grover 알고리즘이 최적화 문제, 특히 최소값 찾기 문제에 효과적으로 적용될 수 있음을 증명한 중요한 연구로 평가된다. 이 논문은 최소값 탐색 문제에 대한 양자 컴퓨팅의 잠재력을 처음으로 제시했다는 점에서 큰 의미를 갖고 있다.

Ambainis는 이 논문에서 다양한 양자 검색 알고리즘의 이론적 기반과 응용 사례를 분석하며, Grover 알고리즘의 변형을 통해 여러 최적화 문제를 해결할 수 있음을 제시한다. 특히, 최소값 찾기 문제를 Grover 알고리즘과 비슷한 방식으로 해결할 수 있는 양자 알고리즘을 설명하고 있다[17].

보다 최근의 연구에서 양자 컴퓨터가 고전적인 컴퓨터와 근본적으로 다른 성능을 보일 수 있는 문제들에서, Aaronson과 Ambainis는 최소값 찾기 문제와 같은 최적화 문제에서, 양자 알고리즘이 고전적 알고리즘에 비해 근본적으로 우월한 성능을 제공할 수 있음을 보여준다. 특히, Grover 알고리즘을 변형하여 최적화 문제에서 양자 우위를 달성하는 방법을 분석한다(Fig. 4)[18].

Figure 4. (Color online) A quantum circuit that can be taken to define the k-fold Forrelation problem [Data from Ref. 18].

2. 양자 카운팅 (Quantum Counting)

양자 카운팅[19-23] 은 그로버 알고리즘의 또 다른 확장으로, 특정한 조건을 만족하는 항목들의 수를 세는 문제를 해결하는 방법이다. 양자 카운팅 알고리즘은 그로버의 알고리즘과 양자 푸리에 변환을 결합하여 특정 상태들이 몇 번 존재하는지를 추정할 수 있다.

그로버 알고리즘을 반복해서 적용함으로써 조건을 만족하는 요소들이 있는지 여부를 알 수 있으며, 이 과정에서 양자 푸리에 변환을 사용하여 정확히 몇 개의 요소가 존재하는지 추정하게 된다. 양자 카운팅의 구체적인 응용을 위해서는 데이터베이스에서 특정 조건을 만족하는 항목의 수를 빠르게 파악하거나, 제약 만족 문제에서 해의 수를 세는 데 사용될 수 있다.

Boyer 등의 1998년 연구는 Grover 알고리즘을 기반으로 양자 검색 및 카운팅 문제에서의 성능을 분석한다. 특히, 양자 검색의 경계 조건(tight bounds)을 분석하고, 이를 통해 양자 카운팅 문제에서 최적의 검색 횟수를 계산하는 방법을 설명한다[24].

1996년의 한 연구에서는 Grover 알고리즘의 확장을 통해 최소값 찾기 및 양자 카운팅 문제를 해결하는 방법을 제시한다[16]. Dürr와 Høyer는 Grover 알고리즘의 진폭 증폭 기법을 응용하여 데이터베이스에서 최소값을 가진 항목을 효율적으로 찾는 방법을 설명한다.

3. 그로버 알고리즘을 통한 근사 매칭 및 제약 만족 문제 해결

그로버 알고리즘은 비정형 검색 문제에서 특정 항목을 찾는 데만 사용되는 것이 아니라, 근사 매칭(approximate matching)이나 제약 만족 문제(constraint satisfaction problem)에도 응용될 수 있다. 예를 들어, 데이터베이스에서 완벽히 일치하는 항목이 아닌, 근사적으로 일치하는 항목을 찾는 문제에 그로버 알고리즘을 변형하여 사용할 수 있다.

근사 매칭(approximate matching)은 정확한 일치가 아닌, 유사한 패턴을 찾는 문제를 해결하는 알고리즘적 접근법이다. 예를 들어, 두 개의 문자열 A와 B, 또는 두 데이터 세트가 있을 때, 문자열 A 내에서 문자열 B와 가장 유사한 부분을 찾는 것이 근사 매칭 문제의 한 예이다.

고전적인 경우에서는 근사 매칭 문제를 해결하는 데 O(N) 시간이 소요되지만, 그로버의 알고리즘을 사용하면 O(N) 시간으로 해결할 수 있다. 이때 목표 상태가 완벽히 일치하지 않더라도 어느 정도 가까운 결과를 찾는 것이 가능하다. 고전적인 방법으로는 편집 거리(edit distance) 를 계산하여 두 문자열 사이의 유사도를 측정할 수 있다. 이 방식은 O(mn) 의 시간 복잡도를 가지며, 여기서 m 과 n 은 각각 문자열 A 와 B 의 길이이다. 이 편집 거리를 기반으로 한 근사 문자열 매칭 알고리즘을 제안되었다[25, 26].

근사 매칭 알고리즘은 DNA 서열 정렬 및 유전자 서열에서 변형된 부분이 존재할 수 있으므로, 완벽하게 일치하는 부분을 찾기보다는 근사하게 일치하는 부분을 찾아야 할 때 유용하게 사용된다[27]. 최근 그로버 알고리즘을 근사 문자열 매칭 문제에 적용한 연구들에서, 양자 알고리즘이 고전적인 근사 매칭 알고리즘보다 효율적임을 보인 바 있다(Fig. 5)[28-30].

Figure 5. (Color online) The parameterized cyclic rotation operator. The Qiskit code useful for building the quantum circuit for a string of length n is shown above. In the middle, the circuit generated by the procedure for a string of length n=8 is shown. Below, the results of 1000 runs of the circuit using the superimposed rotation parameter are shown [Data from Ref. 29].

제약 만족 문제는 주어진 제약 조건을 만족시키는 해를 찾는 문제이다. 제약 만족 문제는 다양한 수학적 최적화, 인공지능, 논리 퍼즐 등에 널리 응용되며, 특히 조합 최적화 문제나 논리적 추론 문제에서 중요한 역할을 한다.

그로버 알고리즘은 이러한 문제에서도 최적의 해를 빠르게 찾는 데 응용될 수 있으며, 이를 통해 매우 복잡한 최적화 문제에서 성능 향상을 이끌어낼 수 있다.

4. 그로버 알고리즘의 변형을 통한 실패율 없는 검색

그로버 알고리즘은 이론적으로 매우 높은 확률로 정답을 찾을 수 있지만, 여전히 약간의 실패 확률이 존재할 수 있다. 이에 대한 변형으로 그로버 알고리즘을 이론적으로 실패율 없이 구현할 수 있는 방법이 연구되었다. Long은 그로버 알고리즘의 실패 확률을 완전히 제거하는 변형을 제안하였다[31]. 이 변형에 의해 그로버 알고리즘에서 위상 반전을 위상 회전으로 대체하여 일정한 반복 후 측정시 정답이 1의 확률로 얻어지게 된다.

5. 암호학에서의 그로버 알고리즘: 암호 분석

그로버 알고리즘의 대표적인 응용 중 하나는 암호 분석이다[32]. 특히, 대칭키 암호를 공격하는 데 매우 유용하다. 고전적 방식에서 무차별 대입 공격은 O(N) 시간이 걸리지만, 그로버 알고리즘은 이를 O(N) 로 단축시킬 수 있다. 즉, 그로버 알고리즘은 대칭키 암호의 보안 강도를 절반 이상으로 줄일 수 있다. AES와 같은 대칭키 암호에서, 키 공간을 무차별 대입 공격으로 검색하는 데 필요한 시간을 그로버 알고리즘으로 줄일 수 있다. 고전적 컴퓨터에서는 128비트 AES 키를 무차별 대입하는 데 2128 의 시간이 걸리지만, 그로버 알고리즘을 사용하면 264의 시간이 소요된다. 또한 그로버 알고리즘의 존재는 대칭키 암호가 더 강력한 키 길이를 사용해야 함 즉 암호 시스템의 보안 강화를 시사한다. 예를 들어, AES-128보다 AES-256이 더 안전한 이유는 그로버 알고리즘이 키 길이에 미치는 영향을 감안해야 하기 때문이다.

6. 최적화 문제에서의 응용

그로버 알고리즘은 최적화 문제에서 매우 유용하다[16]. 고전적인 최적화 문제는 보통 시간이 많이 걸리고, 많은 계산을 필요로 하는 경우가 많다. 그로버 알고리즘을 활용하면 가능한 해를 빠르게 검색할 수 있기 때문에, 복잡한 최적화 문제에서도 성능을 개선할 수 있다.

응용 사례로서, 복잡한 시스템에서 최소 비용을 찾는 최적화 문제, 예를 들어 물류 최적화 문제, 네트워크 최적화 문제 등에 그로버 알고리즘이 적용될 수 있다. 이는 기존의 선형 탐색 대신 그로버 알고리즘을 사용하여 더 빠른 검색을 가능하게 한다.

최소값 찾기: 앞서 언급한 양자 최소값 찾기 문제와도 연관되어 있으며, 그로버 알고리즘을 변형하여 최적화 문제에서 최소값이나 최대값을 더 효율적으로 탐색할 수 있다.

7. 인공지능 및 머신러닝에서의 응용

그로버 알고리즘은 인공지능(AI) 및 머신러닝 문제에 적용되어 학습 알고리즘의 효율성을 높이는 데 사용될 수 있다[33]. 특히, 데이터셋에서 패턴을 찾거나, 최적의 모델 매개변수를 찾는 문제에서 그로버 알고리즘의 속도 향상을 기대할 수 있다. 응용 사례로서 분류 문제나 군집화 문제에서 특정 데이터를 찾기 위한 검색에 그로버 알고리즘을 적용할 수 있다. 예를 들어, 특정한 특징을 가진 데이터 포인트를 대규모 데이터셋에서 찾는 작업에서 그로버 알고리즘을 사용하여 효율을 올릴 수 있다. 그로버 알고리즘은 최근 강화 학습에도 응용되고 있다. 그로버 알고리즘을 사용하면 에이전트가 최적의 행동을 찾는 데 필요한 탐색 시간을 줄일 수 있으며, 이로 인해 강화 학습 알고리즘의 성능을 개선할 수 있다.

8. 계산 화학 및 생물학에서의 응용

그로버 알고리즘은 계산화학 및 생물학 분야에서도 중요한 응용 가능성을 가지고 있다[34]. 특히 분자 구조의 최적화나 약물 디자인에서 특정 분자 구조를 검색하거나 최적의 상태를 찾는 데 적용될 수 있다. 주요한 응용사례 중 하나로서 새로운 약물 후보군을 설계하는 과정에서, 그로버 알고리즘을 통해 효율적으로 특정한 화학적 속성을 가진 분자 구조를 찾는 데 사용될 수 있다. 또한, 단백질 접힘 문제와 같은 복잡한 생물학적 시스템에서 특정 접힘 상태를 빠르게 탐색하는 데 기여할 수 있다. 또한 그로버 알고리즘을 사용하여 분자의 에너지 상태를 최적화하는 문제를 빠르게 해결할 수 있다.

그로버 알고리즘은 다양한 양자 컴퓨팅 플랫폼에서 실험적으로 구현되었다. 여기서는 초전도 큐빗, 이온 트랩, 광자 기반 양자 컴퓨터 등을 이용한 실험적 구현 사례와, 이러한 실험에서 겪는 도전 과제를 설명하겠다.

1. 그로버 알고리즘의 실험적 구현

초전도 큐빗 기반 양자 컴퓨터는 그로버 알고리즘의 구현에 매우 유망한 플랫폼이다. 초전도 큐빗은 긴 코히런스 시간과 비교적 낮은 오류율 덕분에 그로버 알고리즘의 실험적 검증에 적합하다. DiCarlo 등은 초전도 큐빗을 이용해 작은 크기의 데이터베이스에서 그로버 알고리즘을 구현하여 실험적 성공을 거둔 바 있다[35]. 이 실험은 실제 양자 하드웨어에서 그로버 알고리즘이 정상적으로 작동할 수 있음을 입증하였다. 이 연구에서 두 개의 트랜스몬 (transmon) 큐빗에 큐빗 전이 진동수의 마이크로웨이브 펄스를 인가하여 큐빗을 회전시켰다.

이러한 초전도체 기반 양자 컴퓨팅을 이용한 양자 알고리즘 실증 작업에서 주요 도전 과제는 큐트의 오류를 제어하고, 충분히 긴 시간 동안 코히런스 상태를 유지하는 것이다.

또한 그로버 알고리즘은 최근 이온 트랩 기술을 이용하여 실험적으로 구현되었다[36-39]. 이온 트랩 기술은 매우 정밀한 제어가 가능하며, 특히 다른 종류의 큐빗보다 매우 긴 코히어런스 시간을 갖는 것으로 알려져 있다. 예를 들면, 코히어런스 시간대 게이트 시간의 비율이 이온 트랩 기술에 의해 106 까지 가능한데, 이는 초전도체 큐빗의 ∼ 3000 와 비교해 아주 높은 코히어런스 시간이 구현되었다[40]. 이 때문에, 이온 트랩 기술은 그로버 알고리즘의 실험적 구현에 적합하다. 미국 미시간 주립대학 연구진은 트랩된 이온으로 2 큐빗 메모리의 4가지 가능한 양자 상태중 임의의 한 상태를 마킹한 후, 그로버 알고리즘으로 평균 60% 의 확률로 성공적으로 복구해 내었다[33]. 연구진에 의하면 이 그로버 알고리즘의 검색 확률은 고전적인 검색 알고리즘의 50%를 넘어선 것이다. 비록 작은 크기지만 이 연구는 그로버 알고리즘을 성공적으로 구현하였으며, 이는 이온 트랩 기반 양자 컴퓨팅의 가능성을 입증한 중요한 사례라고 할 수 있다. 이온 트랩 시스템에서 가장 큰 과제는 여러 이온들을 장시간 제어하는 문제이다. 많은 이온을 포함한 대규모 시스템에서 그로버 알고리즘을 구현하려면 매우 정밀한 제어가 요구되며, 레이저와 장비의 안정성이 필요하다.

2. 그로버 알고리즘 구현에서의 도전 과제

그로버 알고리즘은 이론적으로는 간단하게 보이지만, 실제 양자 컴퓨터에서 구현하는 과정에는 여러 도전 과제가 존재한다. 이러한 도전 과제는 양자 하드웨어의 한계와 양자 알고리즘의 효율적인 실행을 방해하는 여러 요소들로 인해 발생한다.

실제 양자 컴퓨터에서 그로버 알고리즘을 구현할 때 가장 큰 도전 과제 중 하나는 큐빗 오류율과 디코히런스 (Qubit Error Rates and Decoherence), 그에 따른 게이트 에러율 문제이다[41-43]. 큐빗은 외부 간섭이나 열적 진동으로 인해 불안정해질 수 있으며, 이는 디코히런스(decoherence)로 이어진다. 디코히런스는 큐빗 상태가 양자 초점 상태에서 이탈하는 현상으로, 알고리즘의 정확도를 떨어뜨리고 계산 오류를 유발할 수 있다. 초전도 큐빗나 이온 트랩과 같은 양자 하드웨어에서, 큐빗이 오래 유지되지 못하거나 잘못된 연산이 발생하면 그로버 알고리즘의 정확성이 저하된다. 양자 오류 정정 기술은 큐빗 오류율을 줄이기 위한 해결책 중 하나이다. 이 기술은 추가적인 리소스를 필요로 하며, 대규모 시스템에서 구현하기 어려운 점이 있다.그러나, 최근 양자 오류 정정 기술은 빠른 속도로 진보하고 있으며[44-46], 최근 중국과 미국의 연구진에 의한 binomial 보존 (boson) 논리 큐빗에 의한 에러 정정 기술 실현이 그 예중 하나이다[44].

그로버 알고리즘의 핵심은 여러 반복(iteration)을 통해 정답의 확률을 증폭시키는 것이다. 이를 위해서는 정확한 양자 게이트가 필요하며, 양자 게이트의 피델리티(fidelity)가 중요하다[43, 47, 48] 피델리티는 2개의 밀도 행렬의 유사성(closeness)를 의미하며(Fig. 6)[49, 50], 양자 게이트가 이론적으로 예상되는 연산과 실제 연산 사이의 일치 정도를 나타낸다.

Figure 6. The quantum circuit for Grover’s algorithm. Register α,β and γ contain n, 1 and l qubits respectively [Data from Ref. 47].

피델리티가 낮으면 알고리즘의 성능이 저하되고, 결국 최종 측정 단계에서 올바른 결과를 얻지 못할 수 있다. 다수의 반복(iteration)이 필요한 그로버 알고리즘의 특성상, 각 반복에서 정확한 양자 게이트가 구현되지 않으면 전체 알고리즘이 실패할 가능성이 커진다. 그로버 알고리즘의 실험적 구현에서 잡음과 게이트 피델리티의 중요성은 잘 알려져 있다[47].

마지막으로 고찰할 그로버 알고리즘의 도전과제는 대규모 큐빗 시스템에서의 확장성 (Scalability)이다. 그로버 알고리즘을 큰 데이터베이스에서 실행하려면 대규모 큐빗 시스템이 필요하다. 그러나 현재의 양자 컴퓨터는 수십에서 수백 개의 큐빗으로 제한되어 있으며, 이는 실질적인 문제에 적용하기에는 부족하다.

그로버 알고리즘이 처리하는 데이터베이스의 크기가 커질수록 필요한 큐빗 수가 증가한다. 그러나 현재 양자 컴퓨터의 기술적 한계로 인해 수천 개 이상의 큐빗을 안정적으로 유지하고 제어하는 것이 어렵다. 최근에 양자 컴퓨터의 확장성을 개선하기 위해 모듈형 양자 컴퓨터[50] 가 제안되었다. 모듈화 기술은 다양한 요소들의 분리와 조합을 가능하게 해 컴퓨팅 아키텍쳐에서 중요한 역할을 수행한다. 모듈화 기술은 양자 컴퓨팅에서 결맞은 (coherent) 채널들을 통해 컴퓨팅 요소들을 연결시키며, 최근 CMOS 플랫폼[47], 중성 원자[51]나 스핀 기반 시스템[52, 53]을 이용해 구현되었다. 이와 같은 새로운 기술의 등장에도 불구하고 양자 알고리즘 특히 그로버 알고리즘을 위한 확장성 있는 양자 컴퓨터의 상용화된 시스템은 아직 개발 초기 단계에 머물러 있다.

양자 컴퓨팅 기술이 발전함에 따라, 그로버 알고리즘의 적용 범위와 성능도 점차 확대되고 있다. 최근의 연구는 NISQ (Noisy Intermediate-Scale Quantum) 시대의 기술 발전과 하이브리드 양자-고전 컴퓨팅 시스템에 중점을 두고 있다. 또한 그로버 알고리즘의 변형과 개선을 통해 더 많은 응용 가능성이 연구되고 있다.

현재의 양자 컴퓨터는 완벽하지 않은 NISQ 시스템으로, 수백 개의 큐빗을 가진 컴퓨터에서 잡음이 존재하는 조건 하에서 알고리즘을 실행해야 한다. NISQ 시스템에서 그로버 알고리즘을 효율적으로 구현하기 위해 다양한 최적화가 필요하다. 기존 그로버 알고리즘을 소규모 문제에 적용하기 위해서는 알고리즘을 하드웨어에 맞게 최적화하는 것이 중요하다. 예를 들어, 오류율을 최소화하기 위한 게이트 최적화, 회로 깊이 줄이기 등이 필요하다. 잡음에 민감한 그로버 알고리즘을 NISQ 환경에서 잘 작동하게 하기 위해 잡음 내성 알고리즘이 개발되고 있으며, 이는 향후 상용 양자 컴퓨터에서의 활용 가능성을 높인다.

완전한 양자 컴퓨터가 상용화되기 전까지, 하이브리드 양자-고전 컴퓨팅 모델이 중요한 연구 방향으로 떠오르고 있다. 양자 변분법 계산 기법들이 그 대표적인 예이다. 이 방법은 일부 계산은 양자 컴퓨터가 처리하고, 나머지 계산은 고전적 컴퓨터가 담당하는 방식이다. 그로버 알고리즘도 이러한 하이브리드 시스템에서 응용 가능성이 크다[54]. 그로버 알고리즘을 사용하여 양자 컴퓨터에서 복잡한 검색 작업을 수행한 후, 나머지 계산을 고전적 컴퓨터로 처리하는 방식이 연구되고 있다. 이는 NISQ 시대의 하이브리드 시스템에서 유망한 접근법이다. 하이브리드 시스템은 양자 컴퓨터의 한계를 보완하고, 보다 효율적으로 문제를 해결할 수 있게 하다. 예를 들어, 작은 크기의 문제는 양자 컴퓨터가 처리하고, 나머지 연산을 고전 컴퓨터가 맡는 방식으로 최적화를 이루어낸다. 최근에는 하이브리드 양자-고전 컴퓨팅 모델이 기계학습 (관련 리뷰 논문[55]) 이나 재무 (finance) 문제[56] 에도 적용되고 있다.

현재 그로버 알고리즘은 비정형 검색 문제 외에도 다양한 문제에 맞게 변형되고 있으며, 이에 따라 새로운 응용 분야가 계속해서 탐구되고 있다. 특히 최적화 문제나 암호 해독과 같은 분야에서 그로버 알고리즘의 변형이 중요한 역할을 하고 있다.

최근 연구에서는 그로버 알고리즘을 최적화 문제에 적용하는 다양한 방법이 제시되었다. 이를 통해 복잡한 시스템에서 최소값이나 최대값을 찾는 문제에서 효율성을 극대화할 수 있다.

또한 암호 해독 응용에서 그로버 알고리즘은 대칭키 암호의 해독에서 매우 유용한 도구로, 이를 사용하여 복잡한 암호 체계를 빠르게 공격할 수 있는 방법이 연구되고 있다. 대칭키 암호는 양자 공격에 대비해 더 강력한 암호 체계를 필요로 한다. AES와 같은 대칭키 암호를 대체하거나 강화하기 위해 양자 저항 암호(quantum-resistant cryptography)가 개발되고 있다. 이는 양자 컴퓨터의 공격에 견딜 수 있는 암호화 기법이다[57].

Grassl 등의 한 연구에서 Grover 알고리즘을 AES 암호에 적용하기 위한 양자 리소스 추정을 다룬다. 양자 컴퓨터에서 Grover 알고리즘을 효과적으로 사용하려면 얼마나 많은 큐빗과 양자 게이트가 필요한지, 그리고 얼마나 긴 연산 시간이 소요되는지를 추정한다(Fig. 7)[58].

Figure 7. The reversible implementation of the function Uf is shown in further detail. In this case the key size k=128 is considered for which r=3 invocations of AES suffice in order to make the target key unique [Data from Ref. 58].

그로버 알고리즘의 미래는 양자 하드웨어와 오류 수정 기술의 발전과 밀접하게 연관되어 있다. 양자 컴퓨터가 더욱 견고하고 확장 가능해짐에 따라, 그로버 알고리즘은 암호학, 머신러닝, 최적화와 같은 분야에서 더 널리 실질적인 응용이 이루어질 가능성이 크다.

This work was supported by project # 202311800001. This work was supported by the National Research Foundation of Korea (NRF-2021R1A2C1008272).