컴퓨팅
양자 컴퓨팅을 통한 ‘여행하는 세일즈맨 문제’ 해결
컴퓨터 과학 분야에서 고전적인 알고리즘 문제인 여행하는 세일즈맨 문제(TSP)는 조합 최적화 문제의 대표적인 예시입니다.
TSP가 정확히 무엇일까요? 이 수학 고전은 N개의 도시를 각각 한 번씩 방문하고 원점 도시로 돌아오는 가장 짧은 경로를 찾는 것을 포함합니다. 그러나 도시 수가 늘어남에 따라 가능한 경로와 최적 해를 찾는 계산 시간이 증가합니다. 이 문제는 근사 방법으로 해결할 수 있지만, 양자 컴퓨터는 훨씬 더 나은 해결책을 훨씬 빠르게 제공할 수 있습니다.
Prof. Dr. Jens Eisert 팀이 입증한: 이러한 문제들을 양자 컴퓨터로 더 좋고 빠르게 해결할 수 있습니다.
양자 컴퓨팅은 양자 역학을 활용하는 하드웨어와 알고리즘을 이용해 기존 컴퓨터, 특히 슈퍼컴퓨터가 해결할 수 없는 복잡한 문제를 해결합니다. 그럼에도 불구하고, 수천 개의 CPU와 GPU 코어를 가진 대규모 고전 컴퓨터인 슈퍼컴퓨터는 20세기 트랜지스터 기술에 의존하기 때문에 높은 복잡도의 문제를 해결하는 데 한계가 있습니다.
여기서 양자 물리학이 등장합니다. 고전 컴퓨터가 정보를 이진 비트(0과 1)로 인코딩하는 것과 달리, 양자 컴퓨터는 양자 비트 또는 큐비트를 사용해 다차원 양자 알고리즘을 실행합니다.
게다가, 냉각을 위해 팬을 사용하는 기존 컴퓨터와 달리, 양자 컴퓨터는 양자 상태를 유지하기 위해 양자 프로세서를 극도로 낮은 온도에서 유지해야 합니다. 이는 초냉각 초유체를 통해 달성됩니다.
초전도체는 중요한 양자역학적 효과를 나타내는 물질로, 전자가 저항 없이 통과할 수 있게 합니다. 전자가 통과하면서 전하를 전달하기 위해 쌍을 이루며, 두 초전도체가 절연체 양쪽에 배치되면 조셉슨 접합이 형성되어 초전도 큐비트를 구동하는 데 사용됩니다.
큐비트는 양자 정보를 중첩 상태에 놓는 중요한 작업에 유용합니다. 이는 큐비트가 가질 수 있는 여러 구성의 조합입니다. 중첩된 큐비트 그룹은 복잡한 문제를 표현할 수 있는 복잡하고 다차원적인 계산 공간을 만들 수 있습니다.
여기서 두 큐비트의 얽힘을 통해 하나의 변화가 다른 큐비트에 직접 영향을 미치며, 이러한 얽힌 큐비트가 중첩 상태에 놓이면 수많은 확률이 발생합니다. 양자 컴퓨터의 계산은 모든 가능한 계산 상태의 중첩을 준비하고, 간섭을 통해 해를 찾는 방식으로 작동합니다.
물론, 많은 큐비트를 가진 양자 컴퓨터를 구축하는 것은 매우 복잡한 절차이며, 이러한 컴퓨터가 무엇을 할 수 있는지에 대한 여러 방법이 탐구되고 있습니다.
“이에 대해 많은 오해가 존재하고 때때로 과장된 이야기가 있습니다. 그러나 우리는 수학적 방법을 사용해 문제에 엄격히 접근했고, 주제에 대한 확실한 결과를 제시했습니다. 무엇보다도, 어떤 의미에서든 이점이 있을 수 있음을 명확히 밝혔습니다.”
핵심적인 여행하는 세일즈맨 문제
최적화 문제인 TSP는 물류 및 공급망 산업에서 큰 경제적 중요성을 가지고 있습니다. 이는 작업 스케줄링, 자원 할당, 포트폴리오 최적화, 심지어 단백질 접힘과 같은 다양한 분야의 조합 최적화 문제에 포함됩니다.
이러한 문제들의 사회적·경제적 중요성을 고려할 때, 이들은 집중적인 연구 대상이 되어 왔습니다. 따라서 가장 효율적인 공급망 및 가장 저렴한 배송 경로와 같은 문제의 해답을 찾는 것은 우리의 일상에 긍정적인 영향을 미칩니다.
하지만 여러 목적지에 대한 배송 경로를 최적화하면서 교통 혼잡, 상승하는 운영 비용, 갑작스러운 경로 변경, 마지막 순간 비즈니스 약속 및 고객 요청과 같은 다양한 제약을 고려하는 것은 TSP를 해결하기 더욱 어렵게 만듭니다. 이러한 어려움에도 불구하고, TSP를 해결하는 것은 효율적인 물류 배송을 위해 필수적이며, 이는 지속 가능한 비즈니스 모델을 보장합니다.
이 문제를 해결하면 이동 거리와 소요 시간을 줄이고 연료 사용을 절감하는 등 많은 이점이 있습니다. 이동 거리를 최소화하면 탄소 발자국을 크게 줄일 수 있어 대기 질 개선, 기후 변화 완화 및 경제 성장에 기여합니다. 또한, TSP를 해결하면 물품의 정시 배송 및 고객과의 회의를 제때 진행할 수 있어 고객 경험과 현장 서비스 비즈니스를 향상시킵니다.
우리가 보았듯이, 이 문제를 해결하는 것은 기업에만 도움이 되는 것이 아니라 이러한 혜택이 고객에게도 전달되어 모든 관련자의 경험을 풍부하게 합니다.
TSP 문제를 해결하기 위해 여러 방법이 사용될 수 있습니다. 그 중 하나는 모든 가능한 순열을 계산해 최단 경로를 찾는 ‘브루트 포스’ 접근법입니다. 분기 한정 방법에서는 문제를 여러 하위 문제 시리즈로 나누고, 각 단계의 해가 이후 단계의 해에 영향을 미칩니다.
동적 프로그래밍에서는 중복 계산을 피하는 데 초점을 맞춥니다. 한편, 최근접 이웃 알고리즘은 시작 위치에서 시작해 가장 가까운 도시를 차례로 방문하는 근사 알고리즘입니다. 모든 도시를 방문한 뒤 시작점으로 돌아갑니다. 실용적이고 비교적 빠르지만, 항상 효율적인 경로를 제공하지는 않을 수 있습니다.
기술이 발전함에 따라 경로 계획 및 최적화는 훨씬 더 효과적으로 수행될 수 있습니다. 특히 인공지능(AI)은 방대한 데이터를 빠르게 분석해 많은 현대 기업이 운영 및 전략적 결정을 내리는 데 도움을 줄 수 있습니다.
양자 컴퓨터도 이 문제를 해결하기 위해 연구되고 있습니다; 결국 양자 컴퓨터는 고전 컴퓨터에 비해 상당한 계산 속도 향상을 제공하기 때문입니다. 오래전부터 이러한 컴퓨터가 문제의 근사치를 개선하는 데 도움이 될 수 있다고 제안되어 왔습니다.
양자 컴퓨팅 기술을 활용한 TSP 해결
양자 컴퓨팅은 엄청난 관심을 끌고 있으며 특정 문제에 대해 유망한 결과를 제공하고 있지만, 이러한 양자 우위의 범위는 아직 크게 탐구되지 않았습니다.
따라서 이 연구는 양자 컴퓨터가 조합 최적화 문제의 근사 해를 찾는 데 고전 컴퓨터보다 실제로 뛰어나다는 완전한 구성 증명을 제공했습니다.
최근 연구는 Eisert와 그의 동료 Jean-Pierre Seifert가 주도했으며, 분석적 방법만을 사용해 큐비트를 가진 양자 컴퓨터가 TSP 문제를 어떻게 해결할 수 있는지를 평가했습니다.
“우리는 물리적 구현과 관계없이 충분한 큐비트가 있다고 가정하고, 이를 사용해 계산 작업을 수행할 가능성을 살펴봅니다,” 라고 베를린 공과대학 박사과정 학생 Vincent Ulitzsch가 설명했으며, 이는 데이터 암호화와 같은 일반적인 암호학 문제와 유사함을 보여줍니다.
그 후 팀은 소수 인수분해를 찾고 이러한 최적화 문제의 하위 클래스를 해결하기 위해 양자 알고리즘인 쇼어 알고리즘을 사용했습니다. 이를 통해 도시 수가 증가해도 계산 시간이 폭발적으로 증가하지 않고, 다항식적으로만 증가합니다(Nx, 여기서 x는 상수). 이렇게 얻은 해는 기존 알고리즘을 사용한 근사 해보다 질적으로 훨씬 우수합니다.
암호학 개념과 계산 학습 이론을 활용함으로써, 연구는 ‘양자 컴퓨터가 조합 최적화 문제를 근사하는 데 고전 컴퓨터에 비해 초다항식적인 이점을 갖는다’는 완전한 구성 증명을 제공합니다.
연구는 또한 양자 컴퓨터가 조합 최적화 문제의 근사 해에 어떤 잠재적 가치를 제공할 수 있는지에 대한 중요한 질문에 대해 상당한 진전을 이루었다고 언급했습니다. 이러한 문제들은 사회적·경제적 영향을 크게 미칩니다.
이 연구는 Einstein Research Unit, Berlin Mathematics Research Center (MATH+ Cluster of Excellence), BMBF (Hybrid), BMWK (EniQmA), Munich Quantum Valley, 그리고 DFG의 지원을 받았습니다. 독일 연방 교육 및 연구부도 재정 지원을 제공했습니다.
양자 컴퓨팅 잠재력 탐구
큰 성과이지만, 양자 컴퓨팅이 여행하는 세일즈맨 문제를 해결하는 데 사용된 것은 이번이 처음이 아닙니다. 양자 컴퓨팅을 활용해 이 문제를 해결하려는 열정가와 연구자들의 사례가 많이 있었습니다.
2022년 12월, 논문은 Grover Adaptive Search(GAS)를 기반으로 한 TSP용 양자 알고리즘을 제안했습니다. GAS 프레임워크에서는 최소 두 가지 근본적인 어려움이 있습니다—해가 실현 가능하지 않을 수 있고, 현재 양자 컴퓨터의 큐비트 수가 매우 제한적이며 최소 요구 사항을 충족하지 못해 조합 최적화 문제에 대한 양자 알고리즘 적용이 제한됩니다.
따라서 논문은 Hamiltonian Cycle Detection(HCD) 오라클을 다듬어 알고리즘 실행 중 비실현 가능한 해를 자동으로 제거했습니다. 또한 ‘anchor register’ 전략을 설계해 큐비트 사용량을 절감했으며, 양자 컴퓨팅의 가역성 요구사항을 완전히 고려하고 사용된 큐비트가 단순히 덮어쓰이거나 해제되지 않는 문제를 극복했습니다. 이를 통해 연구는 31개의 큐비트만 필요했으며, 해결 성공률은 86.71%였습니다.
2019년에 자체 정의 물리학 애호가 Joseph Cammidge 작성은 7개의 도시를 해결할 수 있는 양자 어닐링 프로세서를 사용했으며, 기술적 제한이 해소되면 9개의 도시까지 해결할 이론적 잠재력이 있다고 밝혔습니다.
새로운 계산 방법인 양자 어닐링은 고전 기술보다 최적화 문제를 더 빠르게 해결할 잠재력을 보여주었습니다. 그 이론에 따르면 큐비트는 초냉각될 때 최적의 저에너지 상태에 도달합니다.
하지만 2021년에 연구는 Supply Chain Digital & Data Science, Johnson & Johnson이 자금을 지원했으며, 양자 어닐러가 8개 이하의 노드 문제만 처리할 수 있고, 시간 및 정확도 측면에서 고전 솔버에 비해 성능이 열악하다고 밝혔습니다.
양자 컴퓨팅을 이용한 TSP 문제 해결은 오래전부터 진행되어 왔습니다. 2001년에 시작된 연구가 검색을 통해 양자 알고리즘을 찾고 있었습니다.
논문에서 앨라배마 대학교의 Buckley Hopper는 Grover와 Shor의 양자 컴퓨터 알고리즘을 살펴보았습니다. 그는 Grover 알고리즘이 제곱근 정도의 개선만 제공하므로 고전적으로 해결 불가능한 문제를 양자 컴퓨터에서 해결 가능하게 만들지는 못한다고 언급했습니다. Shor 알고리즘에 대해서는, 이 알고리즘이 본질적으로 해결 불가능한 소인수 문제를 양자 기계에서 해결 가능하게 만들 수는 있지만, 매우 특정한 유형의 문제에만 적합하다고 관찰했습니다.
전반적으로 Hopper는 “여행하는 세일즈맨 문제에 대한 근사 해를 계산하는 알고리즘에 만족스러운 결과를 찾지 못했다”고 말했습니다.
그 몇 년 후, 전기전자공학회(IEEE) 제시한 새로운 알고리즘은 유전 알고리즘과 양자 컴퓨팅을 모두 영감으로 삼았습니다. IEEE는 제안된 알고리즘을 일부 TSP 사례에 적용한 결과가 표준 유전 알고리즘보다 현저히 우수하다고 밝혔습니다.
양자 컴퓨팅의 현재 상태에 대해 알아보려면 여기를 클릭하십시오.
양자 컴퓨팅을 활용하는 기업
이제 양자 컴퓨팅 연구 및 개발에 참여하고 있는 몇몇 기업을 살펴보겠습니다:
#1. IBM
International Business Machines Corporation은 AI, 클라우드 서비스, IT, 클라이언트 파이낸싱 및 상업 파이낸싱을 포함한 다양한 분야에 참여하고 있습니다. 이 기술 대기업은 IBM Quantum Platform을 통해 양자 컴퓨팅에도 참여하고 있으며, 여기서는 클라우드 기반 양자 컴퓨팅 서비스에 대한 공개 및 프리미엄 액세스를 제공합니다. 여기에는 IBM의 프로토타입 양자 프로세서 세트, 양자 계산 튜토리얼, 인터랙티브 교재가 포함됩니다.
최근 IBM 과학자들은 언급했으며, 양자 컴퓨터의 게임 체인징 잠재력을 열어주는 장애물을 극복하는 데 한 걸음 더 다가섰다고 밝혔습니다. 이를 위해 그들은 기존 방법보다 약 10배 더 효율적인 새로운 양자 오류 정정 코드를 도입했습니다.
지난해 말, 이 회사는 1,121개의 초전도 큐비트를 벌집 형태로 배열한 Condor라는 양자 컴퓨터를 출시했습니다. IBM은 또한 첫 번째 모듈식 양자 컴퓨터이자 양자 중심 슈퍼컴퓨팅 아키텍처인 IBM Quantum System Two를 공개했으며, 이는 확장 가능하고 향후 5년 내에 출시될 칩으로 업그레이드할 수 있습니다.
(IBM )
시가총액 1,750억 달러인 IBM의 주가는 현재 $190.86이며, 연초 대비 16.66% 상승했습니다(YTD). IBM은 연간 매출(TTM) 618.6억 달러, 주당순이익(EPS, TTM) 8.03, 주가수익비율(P/E, TTM) 23.76, 자기자본이익률(ROE, TTM) 33.36%를 기록했습니다. 이 회사는 배당 수익률 3.48%를 지급합니다.
#2. D-Wave Systems
이 양자 컴퓨팅 기업은 관련 시스템, 소프트웨어 및 서비스를 개발 및 제공합니다. 제품에는 The Leap와 The Advantage가 포함되며, 일정 관리, 물류, 신약 개발, 제조 공정 등 다양한 분야에 양자 애플리케이션을 제공합니다.
이번 달 초, D-Wave는 양자 기계가 이제 실제 응용 문제를 기존 컴퓨터보다 빠르게 해결할 수 있다고 밝혔습니다. 올해 초, 이 회사는 1,200개의 큐비트와 10,000개의 커플러를 갖춘 양자 컴퓨터를 발표했으며, 어려운 최적화 문제에 대한 해결 시간은 기존보다 20배 빨라졌습니다.
(QBTS )
이 회사의 주가는 현재 $1.86이며, 연초 대비 138.6% 상승(YTD)했고, 시가총액은 2억 6,700만 달러입니다. 매출(TTM)은 824만 7천 달러, EPS(TTM)는 -0.66, P/E(TTM)는 -3.19를 기록했으며, 2023년 4분기 및 연말 실적 모두 매출이 20% 이상 성장했으며, 예약량은 각각 34%와 89% 증가했습니다.
흥미롭게도, 회사의 CEO인 Dr. Alan Baratz는 Zapata AI와의 다년간 전략적 파트너십, 1,200+ 큐비트 Advantage2 프로토타입 도입, NEC Australia 및 Deloitte Canada와의 합작 투자, 그리고 전 국토안보부 장관 Kirstjen Nielsen을 이사회에 임명한 것을 근거로 회사의 모멘텀을 선언했습니다.
결론
양자 컴퓨팅 시장은 2028년에 $6.5 billion에 도달할 것으로 예상되며, 여행하는 세일즈맨 문제(TSP)를 해결할 잠재력은 제조, 물류, 공급망 관리, 전자상거래, 운송 및 연구 등 여러 산업에 영향을 미칩니다. 결국 이는 생산성을 크게 향상하고 비용을 절감하며 다양한 분야에서 혁신을 촉진하는 등 상당한 이점을 가져올 수 있습니다.
