양자 컴퓨팅을 통해 '여행하는 외판원 문제' 해결

TSP(Traveling Salesman Problem)로 알려진 컴퓨터 과학 분야의 고전적인 알고리즘 문제는 조합 최적화 문제의 대표적인 예입니다.

TSP란 정확히 무엇인가요? 이 수학 고전은 원래 도시로 돌아오기 전에 정확히 한 번 N개의 도시를 방문할 수 있는 최단 경로를 찾는 것과 관련됩니다. 그러나 도시 수가 증가함에 따라 최적의 솔루션을 찾는 데 가능한 경로와 계산 시간도 늘어납니다. 이 문제는 근사 방법을 사용하여 해결할 수 있지만 양자 컴퓨터는 훨씬 더 나은 솔루션을 훨씬 더 빠르게 제공할 수 있습니다. 

이것이 바로 이론물리학자의 말이다. Jens Eisert 교수 팀은 다음을 시연했습니다.: 양자컴퓨터를 이용하면 이러한 문제를 더 잘, 더 빠르게 해결할 수 있다는 것입니다.

양자 컴퓨팅은 양자역학을 활용하는 하드웨어와 알고리즘을 활용하여 슈퍼컴퓨터를 비롯한 기존의 접근 범위를 넘어서는 복잡한 문제를 해결합니다. 수천 개의 CPU 및 GPU 코어를 갖춘 대규모 클래식 컴퓨터인 슈퍼컴퓨터는 강력한 성능에도 불구하고 고도로 복잡한 문제를 해결할 때 20세기 트랜지스터 기술에 의존한다는 한계가 있습니다. 

여기서 양자 물리학이 등장합니다. 정보를 이진 비트(0과 1)로 인코딩하는 기존 컴퓨터와 달리 양자 컴퓨터는 양자 비트 또는 큐비트를 사용하여 다차원 양자 알고리즘을 실행합니다. 

또한 냉각을 위해 팬을 사용하는 기존 컴퓨터와 달리 양자 컴퓨터는 양자 상태를 유지하기 위해 양자 프로세서를 극도로 낮은 온도에서 유지해야 합니다. 이는 과냉각된 초유체를 통해 달성됩니다. 

초전도체는 전자가 저항 없이 이동할 수 있도록 하는 중요한 양자 역학 효과를 나타내는 물질입니다. 전자가 통과하면서 쌍을 이루어 장벽을 넘어 전하를 운반합니다. 두 개의 초전도체가 절연체의 양쪽에 배치되면 초전도 큐비트를 전도하는 데 사용되는 조셉슨 접합이 형성됩니다.  

큐비트는 양자 정보를 중첩 상태로 만드는 중요한 작업에 유용합니다. 중첩 상태란 큐비트의 가능한 구성 요소들의 조합을 의미합니다. 중첩된 큐비트 그룹은 복잡한 문제를 표현할 수 있는 복잡하고 다차원적인 계산 공간을 생성할 수 있습니다.

여기에서 두 큐비트의 얽힘으로 인해 하나의 변경 사항이 다른 큐비트에 직접 영향을 미칠 수 있는 반면, 이러한 얽힌 큐비트가 중첩 상태에 놓이게 되면 우리는 매우 많은 확률을 얻게 됩니다. 양자 컴퓨터의 계산은 가능한 모든 계산 상태의 중첩을 준비하여 작동하며 간섭을 통해 솔루션을 찾습니다.

물론, 많은 큐비트로 양자 컴퓨터를 구축하는 것은 매우 복잡한 절차이지만, 이러한 컴퓨터가 무엇을 수행할 수 있는지에 대한 여러 가지 방법이 연구되고 있습니다. 

에너지 재료 연구 연구 센터인 HZB(Helmholtz-Zentrum Berlin)와 공립 연구 대학인 베를린 자유 대학교(Freie Universität Berlin)에서 공동 연구 그룹을 이끌고 있는 Eisert에 따르면:

“그것에 관한 많은 신화가 있고 때로는 어느 정도 뜨거운 공기와 과대 광고가 있습니다. 그러나 우리는 수학적 방법을 사용하여 이 문제에 엄격하게 접근했으며 해당 주제에 대해 확실한 결과를 제공했습니다. 무엇보다도 우리는 어떤 의미에서 이점이 있을 수 있는지 명확히 했습니다.” 

중요한 여행 세일즈맨 문제

최적화 문제인 TSP는 물류 및 공급망 산업에서 경제적으로 매우 중요합니다. 이는 작업 일정 관리, 자원 할당, 포트폴리오 최적화, 심지어 단백질 접힘까지 포함하는 광범위한 조합 최적화 문제 범주에 속하며 모두 다양한 분야에 중요합니다.

이러한 문제의 사회적, 경제적 중요성을 고려할 때, 이 문제는 집중적인 연구의 주제가 되어 왔습니다. 이처럼 가장 효율적인 공급망, 가장 저렴한 배송 경로 등의 문제에 대한 답을 찾는 것은 우리 일상생활에 긍정적인 영향을 미칩니다.

그러나 교통 혼잡, 운영 비용 상승, 갑작스러운 경로 변경, 막바지 업무 약속, 고객 요청 등 다양한 제약 조건을 고려하면서 여러 목적지에 대한 배송 경로를 최적화하는 것은 TSP의 해결을 더욱 어렵게 만듭니다. 이러한 과제에도 불구하고 TSP를 해결하는 것은 상품의 효율적인 배송을 위해 매우 중요하며, 이는 실행 가능한 비즈니스 모델을 보장합니다. 

이 문제를 해결하면 이동 거리와 시간이 줄어들고 연료 사용량이 절약되는 등 많은 이점이 있습니다. 이동 거리를 최소화하면 탄소 배출량을 크게 줄이는 데 도움이 될 수 있으며, 이는 대기 질 향상, 기후 변화 둔화 및 경제 성장으로 이어집니다. 또한, TSP 문제를 해결하면 상품의 적시 배송과 고객과의 적시 미팅이 가능해지며, 이는 고객 경험과 현장 서비스 비즈니스를 향상시킬 수 있습니다.

앞서 살펴보았듯이 문제를 해결하면 비즈니스에 도움이 될 뿐만 아니라 이러한 이점이 고객에게도 전달되어 관련된 모든 사람의 경험이 풍부해집니다.

TSP 문제를 푸는 데는 여러 가지 방법이 있습니다. 그중 하나는 '무차별 대입(Brute-Force)' 방식으로, 최단 경로를 찾기 위해 가능한 모든 순열을 계산합니다. 분기 한정 방식에서는 문제가 여러 개의 하위 문제로 나뉘며, 각 단계의 해는 이후 단계에서 구해지는 해에 영향을 미칩니다.

동적 프로그래밍에서는 중복 계산을 피하는 데 중점을 둡니다. 한편, Nearest Neighbor는 시작 위치에서 시작한 다음 가장 가까운 위치에서 중지하는 근사 알고리즘입니다. 모든 도시를 둘러보고 나면 출발지로 돌아갑니다. 실용적이고 상대적으로 빠르지만, 이 방법이 항상 효율적인 경로를 제공하는 것은 아닙니다.

기술이 발전함에 따라 경로 계획 및 최적화가 훨씬 더 효과적으로 수행될 수 있습니다. 특히 인공지능(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), 뮌헨 Quantum Valley 및 DFG의 자금 지원을 받았습니다. 독일 연방교육연구부도 재정적 지원을 제공했다.

양자 컴퓨팅의 잠재력 탐구 

위대한 업적이기는 하지만, 양자 컴퓨팅이 순회 세일즈맨 문제를 해결하는 데 사용된 것은 이번이 처음은 아니었습니다. 양자 컴퓨팅을 활용하여 이 문제를 해결하려는 많은 연구자와 애호가들이 있었습니다. 

2022년 XNUMX월에는 종이 GAS(Grover Adaptive Search) 기반의 TSP용 양자 알고리즘을 제안했습니다. GAS 프레임워크에는 최소한 두 가지 근본적인 어려움이 있습니다. 즉, 솔루션이 실현 가능하지 않을 수 있다는 점, 현재 양자 컴퓨터의 큐비트 수가 매우 제한되어 최소 요구 사항을 충족할 수 없어 조합 최적화 문제에 대한 양자 알고리즘 적용이 제한된다는 점입니다. 

따라서 이 논문은 알고리즘 실행 중에 비실용적인 솔루션을 자동으로 제거할 수 있는 해밀턴 사이클 감지(HCD) 오라클을 다듬었습니다. 그들은 또한 양자 컴퓨팅의 가역성 요구 사항을 충분히 고려하고 사용된 큐비트가 단순히 덮어쓰거나 해제되지 않는 어려움을 극복하여 큐비트 사용량을 절약하기 위한 "앵커 레지스터" 전략을 설계했습니다. 이를 통해 연구에는 31큐비트만 필요했고 솔루션의 성공률은 86.71%였습니다.

2019년에는 자칭 물리학 감정가인 Joseph Cammidge가 쓴 어닐링 양자 프로세서를 사용하여 7개 도시의 외판원 문제를 해결할 수 있었고, 기술적 한계가 제거되면 9개 도시의 문제를 해결할 수 있는 이론적 잠재력을 가지고 있다는 것입니다. 

새로운 컴퓨팅 방법인 양자 어닐링(Quantum annealing)은 기존 기술보다 더 빠르게 최적화 문제를 해결할 수 있는 잠재력을 보여주었습니다. 그 이론은 큐비트가 과냉각될 때 최적의 저에너지 상태를 달성한다는 것을 의미합니다. 

그러나 2021년에는 공부 공급망 디지털 및 데이터 과학의 자금 지원을 받은 Johnson & Johnson은 양자 어닐러가 8개 이하의 노드 문제 크기만 처리할 수 있으며 성능이 기존 솔버에 비해 시간과 정확성 측면에서 모두 낮음을 발견했습니다.

TSP 문제를 해결하기 위해 양자 컴퓨팅을 사용하는 것은 한동안 진행되어 왔습니다. 2001여년 전인 XNUMX년에 한 연구가 시작되었습니다. 수색 문제를 해결하기 위한 양자 알고리즘

앨라배마 대학교의 버클리 호퍼는 논문에서 그로버와 쇼어의 양자 컴퓨터 알고리즘을 살펴보았습니다. 그는 그로버의 알고리즘은 제곱근 개선 정도만 제공하기 때문에 고전적으로 난해한 문제를 양자 컴퓨터에서는 난해하게 만들 수 없다고 지적했습니다. 쇼어의 알고리즘에 대해 호퍼는 난해할 것으로 예상되는 소인수분해 문제를 양자 컴퓨터에서는 난해한 문제로 변환할 수는 있지만, 매우 특정한 유형의 문제에만 적합하다고 지적했습니다. 

전반적으로, 호퍼는 "여행하는 외판원 문제에 대한 대략적인 해를 계산하기 위한 알고리즘에 대해 만족스러운 결과를 찾지 못했습니다."

그로부터 몇 년 후, 전기전자공학회(IEEE) 제시 유전자 알고리즘과 양자 컴퓨팅에서 영감을 받아 문제를 해결하기 위한 새로운 알고리즘입니다. IEEE는 여행하는 외판원 문제의 일부 사례에 제안된 알고리즘을 적용한 결과가 표준 유전자 알고리즘에서 제공하는 결과보다 훨씬 더 우수하다는 사실을 발견했습니다.

양자 컴퓨팅의 현재 상태를 알아보려면 여기를 클릭하세요.

양자 컴퓨팅을 활용하는 기업 

이제 양자 컴퓨팅 연구 및 개발을 담당하고 있는 몇몇 이름을 살펴보겠습니다.

# 1. IBM

IBM(IBM)은 AI, 클라우드 서비스, IT, 고객 금융, 기업 금융 등 다양한 분야에 진출해 있습니다. 이 기술 대기업은 IBM 퀀텀 플랫폼을 통해 양자 컴퓨팅에도 참여하고 있으며, 이 플랫폼은 클라우드 기반 양자 컴퓨팅 서비스에 대한 일반 및 프리미엄 액세스를 제공합니다. 여기에는 IBM의 프로토타입 양자 프로세서 세트, 양자 컴퓨팅 튜토리얼, 그리고 인터랙티브 교재가 포함됩니다.

가장 최근에는 IBM 과학자들이 정해진 양자 컴퓨터의 판도를 바꾸는 잠재력을 여는 장애물을 극복하는 데 한 걸음 더 가까워졌습니다. 이를 위해 그들은 이전 방법보다 약 10배 더 효율적인 새로운 양자 오류 정정 코드를 도입했습니다. 

지난해 말 이 회사는 1,121개의 초전도 큐비트가 벌집 패턴으로 배열된 콘도르(Condor)라는 양자 컴퓨터도 출시했습니다. IBM은 또한 자사 최초의 모듈형 양자 컴퓨터이자 양자 중심 슈퍼컴퓨팅 아키텍처인 IBM Quantum System Two를 공개했습니다. 이 아키텍처는 확장 가능하므로 향후 XNUMX년 내에 출시될 칩으로 업그레이드할 수 있습니다.

시가총액 175억 달러인 IBM의 주가는 연초 대비 190.86% 상승한 16.66달러에 거래되고 있습니다. IBM은 61.86억 8.03천만 달러의 매출(TTM)을 기록했으며, 주당순이익(TTM)은 23.76, 주가수익비율(TTM)은 33.36, 자기자본이익률(TTM)은 3.48%입니다. 배당수익률은 XNUMX%입니다.

# 2. D-웨이브 시스템

이 양자 컴퓨팅 회사는 관련 시스템, 소프트웨어 및 서비스를 개발하고 제공합니다. 해당 제품에는 The Leap 및 The Advantage가 포함되어 있으며 일정 관리, 물류, 약물 발견, 제조 프로세스 등에 대한 양자 애플리케이션을 제공합니다. 

이달 초 D-Wave는 양자 기계가 이제 일반 컴퓨터보다 더 빠르게 실제 응용 프로그램의 문제를 해결할 수 있다고 말했습니다. 올해 초 이 회사는 1,200큐비트, 10,000커플러, 어려운 최적화 문제에 대한 해결 시간이 20배 더 빠른 양자 컴퓨터를 발표했습니다.

이 회사의 주가는 현재 주당 1.86달러에 거래되고 있으며, 연초 대비 138.6% 상승했습니다. 시가총액은 267억 8.247만 달러입니다. 매출은 0.66만 3.19천 달러(TTM), 주당순이익(TTM)은 -20, 주가수익비율(TTM)은 -4를 기록했으며, 2023년 34분기와 연말 실적 모두 매출이 89% 이상 증가했고, 예약은 각각 XNUMX%와 XNUMX% 증가했습니다. 

흥미로운 점은 이 회사의 CEO인 앨런 바라츠 박사가 Zapata AI와의 수년간의 전략적 파트너십, 1,200개 이상의 큐비트 Advantage2 프로토타입 출시, NEC Australia와 Deloitte Canada와의 합작 투자, 전 국토안보부 장관인 크리스틴 닐슨의 이사회 임명 등을 언급하며 이 회사의 추진력을 선언했다는 것입니다.

맺음말

양자 컴퓨팅 시장은 다음과 같이 예상됩니다. 6.5 억 달러에 도달 2028년에는 순회 판매원 문제(TSP)를 해결할 수 있는 잠재력이 제조, 물류, 공급망 관리, 전자 상거래, 운송, 연구 등 여러 산업에 파급력을 미칠 것입니다. 결국, 이는 생산성 향상, 비용 절감, 다양한 부문 전반의 혁신 촉진 등 상당한 이점을 가져올 수 있습니다.

최고의 5개 양자 컴퓨팅 회사 목록을 보려면 여기를 클릭하십시오.