양자 알고리즘 한눈에 보기
양자 컴퓨터 하드웨어는 최근에서야 개발이 가속화되었지만, 이 원리를 이용한 양자 알고리즘은 오래전부터 끊임없이 개발이 되어 왔습니다. 수학자와 물리학자들의 이러한 노력들은 양자 컴퓨터의 잠재적인 파워를 보여줌으로써, 양자 산업에 대한 지속적인 투자와 관심을 이끌어내는 원동력이라고 할 수 있습니다.
그러다 보니 양자 알고리즘 중에서는 지적 호기심을 충족하기는 하지만, 실용성은 떨어지는 알고리즘도 있고, 구현되려면 현재의 기술로는 한참 걸리는 알고리즘도 있습니다.
많은 양자 튜토리얼을 봐 왔지만, 대다수의 컨텐츠에서는 이러한 문제들을 따로 구분하여 소개하지는 않았습니다. 하지만 양자컴퓨터를 상업적으로 사용하고자 하는 저희 KQC 입장에서는 이러한 알고리즘들의 실용성과 구현가능성에 대한 명확한 인식이 필요합니다.
이번 포스팅에서는 1. 양자 알고리즘 초창기에 등장해 관심을 이끌어낸 Iconic 알고리즘, 2. 현재의 양자 컴퓨터에서도 충분히 구현가능하며 어느정도 실용성도 가지고 있는 Ready-to-go 알고리즘 그리고 3. 아직까지는 시기상조이긴 하나, 구현이 된다면 지금까지 인류가 시도조차 하지 못했던 문제들을 풀 수 있는 Yet-to-come 알고리즘을 구분하여 소개하려고 합니다.
구체적인 원리는 다음에 각각 따로 포스팅을 만들어서 알려드릴 예정이며, 이번 포스팅에서는 풀고자 하는 문제, 알고리즘의 의의 그리고 활용 분야에 집중하려고 합니다.
- Iconic 알고리즘
첫번째로 소개해드릴 알고리즘들은 양자 컴퓨팅이라는 아이디어가 처음 나왔을때 양자 컴퓨터가 이론적으로 고전 컴퓨터에 비해서 잘 풀 수 있는 알고리즘이 있다는 것을 입증하는 과정에서 나온 알고리즘입니다.
대표적으로는 도이치 알고리즘이 있습니다.
도이치 알고리즘은 1992년 David Deutsch와 Richard Jozsa가 구상한 알고리즘으로 양자 알고리즘 연구의 초창기에 양자 우위를 입증한 예시로서 자주 언급되고 있습니다.
도이치 알고리즘이 풀고자 하는 문제는 0 혹은 1을 결과로 반환하는 임의의 함수가 Balanced 함수인지 Constant 함수 인지를 판단하고자 하는 것입니다. Constant 함수는 함수가 어떠한 인풋을 넣던 모두 0을 반환하거나 모두 1을 반환하는 함수이며 Balanced 함수는 모든 인풋 중 절반은 0, 절반은 1을 반환하는 함수를 합니다.
고전 컴퓨터를 이용한 방식으로 이 문제를 풀려면 N개의 인풋을 가지는 함수에 대해 대략 N/2번 결과값을 확인해야하지만 도이치 알고리즘을 이용하면 양자회로를 오직 한번만 돌려서 문제를 풀 수 있습니다.
도이치 알고리즘은 실용적인 의의는 거의 없지만 양자 컴퓨터를 이용하여 고전 컴퓨터 보다 훨씬 더 빠르게 풀 수 있는 문제를 찾아냈다는 학술적 의의가 있습니다.
2. Ready-to-go 알고리즘
두번째로 소개해드릴 알고리즘들은 현재의 NISQ 컴퓨터를 이용하고도 구현이 가능하며, 또 풀고자 하는 문제들도 현실적인 알고리즘 들입니다. 이 알고리즘들은 당장은 파워가 그렇게 좋지는 않지만 대략 3~10년 안에 상용화가 되어 각 산업계에 영향을 미칠 것이라고 기대하고 있습니다.
우선 가장 첫번째로 알려드릴 알고리즘은 Quantum Annealing입니다. Quantum Annealing은 조합 최적화 문제의 한 유형인 Quadratic Unconstrained Binary Optimization (QUBO)를 타깃으로 한 알고리즘입니다. QUBO는 일반적인 조합최적화 문제 형태이며 Weighted Maxcut Problem, Travelling Salesmans Problem 그리고 Satisfiablity Problem 등 다양한 형태의 실용적인 문제로 발전 시킬 수 있습니다.
Quantum Annealing은 현재 DWAVE가 주도해서 개발하고 있는 특수 목적용 양자 컴퓨터인 Quantum Annealer를 이용해서 풀 수 있습니다. Quantum Annealer는 일반적인 양자컴퓨터에 비해 범용성이 떨어지는 대신 개발이 용이합니다. 구체적으로 DWAVE는 현재 5000 큐빗 이상의 Quantum Annealer를 개발했으며 이는 IBM이 주도해서 개발하고 있는 가장 최신의 범용 양자컴퓨터가 433 큐빗임을 감안하면 압도적인 수치라고 할 수 있습니다.
현재 Quantum Annealer는 다양한 분야에서 연구가 되고 있으며 대표적으로는 금융계의 포트폴리오 최적화, 유통계의 루트 최적화 그리고 데이터 분석계의 변수선택 문제 등을 풀기 위해 연구되고 있습니다.
두번째로 알려드릴 알고리즘은 Variational Quantum Eigensolver (VQE)입니다. Variational Quantum Eigensolver는 양자컴퓨터와 고전컴퓨터를 모두 사용하는 하이브리드 알고리즘으로 Hamiltonian의 Ground State를 찾아내는데 사용할 수 있는 알고리즘입니다. 물리학을 공부하신적이 없다면 위에서 한 말이 많이 어려우실겁니다. 저도 여기서 정신이 혼미해졌던 기억이 나네요..^^
데이터 분석 관점에서는 대략적으로 Hamiltonian은 행렬로, Ground State는 행렬의 가장 작은 고유값에 대한 고유 벡터로 생각하셔도 별 문제가 없습니다. 따라서 VQE는 행렬의 가장 작은 고유값 및 고유벡터를 찾아내는 문제입니다.
VQE는 용어에서 알 수 있다시피 물리학과 화학에서 다루는 입자 역학 문제를 푸는 것이 목적입니다. 재료 과학, 제약, 생물학 등 많은 자연 과학들의 기저에 물리학과 화학이 있는 만큼, VQE는 이들의 발전에 큰 영향을 줄 수 있는 학문이라고 할 수 있습니다.
마지막으로 알려드릴 알고리즘은 그로버 (Grover) 알고리즘입니다. 그로버 알고리즘은 임의의 인풋에만 반응하는 작동 방식을 알 수 없는 함수에 대해서 그 함수가 어떤 인풋에 반응하는지를 찾아내는 알고리즘입니다.
이때 함수의 작동 원리를 모른다는 점에서 자세한 설명 없이 내려지는 그리스 신화의 신탁(Oracle)과 비슷하여 그로버 알고리즘의 대상이 되는 함수를 오라클(Oracle)이라는 별칭으로 부릅니다.
이 과정에서 그로버 알고리즘은 정답이 나올 확률을 증폭시키는 진폭 증폭 (Amplitude Amplification)의 컨셉을 제안했습니다. 그로버 알고리즘 그 자체 뿐만 아니라 이 Amplitude Amplification의 컨셉은 다양한 양자 알고리즘에서 응용되고 있습니다.
그로버 알고리즘은 금융, 화학, 바이오 등의 다양한 분야의 시뮬레이션과 최적화에 대해서 사용될 수 있는 알고리즘입니다.
3. Yet-to-come 알고리즘
마지막으로 알려드릴 알고리즘들은 현재의 NISQ 컴퓨터에서는 구현이 거의 불가능하지만 먼 미래에 큐빗의 개수가 늘어나고 오류가 안정적이 될 때 이득이 발생할 수 있는 알고리즘들입니다. 굉장히 파워풀하고 핵심적인 문제를 타깃으로 하고 있어서 구현이 된다면 인류의 지성을 진일보 시킬 수 있을 것이라고 기대되고 있습니다.
첫번째는 Quantum Phase Estimation (QPE)입니다. 이는 행렬의 Phase (위상)을 찾아내는 알고리즘입니다. Phase라고 함은 아이젠밸류의 복소수 버전으로 이해하시면 됩니다. VQE와 비교하면 VQE는 가장 낮은 아이젠밸류만 찾을 수 있다면 Quantum Phase Estimtation은 모든 Eigenvalue를 찾아내고자 하는 알고리즘입니다.
아이젠밸류를 모두 찾아낼 수 있는 만큼 QPE는 행렬의 특이값 분해와 역행렬 계산의 기반 알고리즘으로 사용할 수 있습니다. 다양한 문제에서 컴퓨팅 시간이 오래 걸리는 이유가 특이값 분해와 역행렬 계산 때문이라는 것을 감안하면, QPE를 사용함으로써 이들 시간을 압도적으로 줄여줄 수 있을 것이라고 기대하고 있습니다.
따라서 응용 분야 그 자체에 기여를 한다기 보다는 응용 분야들에 사용되는 기초 계산에 영향을 주기에 한번 구현이 된다면 광범위한 영역에서 영향을 미치게 됩니다.
두번째는 Shor’s Algorithm입니다. Shor’s Algorithm은 전세계의 학계가 양자컴퓨터를 진지하게 연구하기 시작한 계기를 준 알고리즘으로 현재 양자 알고리즘에서 가장 중요한 알고리즘 중 하나입니다. 쇼어 알고리즘이 풀고자 하는 문제는 소인수 분해의 문제입니다. 소인수 분해는 NP 문제로 분류되는데, 정답을 찾기는 어렵지만 찾아낸 정답이 진짜 정답인지 확인하기는 굉장히 쉬운 문제입니다. 예를 들어, 1002001라는 숫자를 소인수 분해하기 위해서는 순차적으로 탐색해야 하므로 아주 오랜 시간이 걸리는 반면, 1001이 이 숫자의 인수라는 것을 판단하는 것은 너무 쉽습니다. 소인수분해 문제의 이러한 성질은 컴퓨터 통신 보안의 기초를 이루고 있습니다.
그런데, 이런 천문학적인 시간이 걸리는 소수 두개의 곱으로 만들어진 큰 숫자의 소인수 분해 문제를, 쇼어 알고리즘을 이용하면 놀라울 만큼 짧은 시간내에 풀 수 있습니다. 이는 현재 사용되는 모든 컴퓨터의 보안이 무력화된다는 것을 의미하기에 업계에 큰 충격을 주었습니다.
이외에도 양자 알고리즘은 몇몇 더 존재하지만 우선은 일반적으로 대중(?)에게 알려진 유명한 양자알고리즘은 이정도라고 생각하시면 될 것 같네요. 앞으로 양자 알고리즘 시리즈를 통해, 이들 알고리즘들의 원리와 타깃에 대해서 좀 더 세밀하게 다루어 볼 예정입니다.
KQC는 상용 양자 알고리즘 및 소프트웨어의 연구/개발을 학계와 업계의 협업을 통해 진행하고 있는 회사입니다. 새로운 기술과 영역에 도전하고 싶은 데이터 사이언티스트는 물론 양자 컴퓨팅을 활용하고자 하는 기업들의 연락을 기다립니다.
https://www.kqchub.com/contactus를 방문하셔서 form을 작성하시거나, info@kqchub.com으로 연락주세요.
