컴퓨팅
量子 컴퓨팅을 통해 ‘여행하는 판매원 문제’ 해결
컴퓨터 과학 분야에서 알고리즘 문제로 잘 알려진 여행하는 판매원 문제(Traveling Salesman Problem, TSP)는 조합 최적화 문제의 대표적인 예입니다.
TSP는 무엇일까요? 이 수학의 고전은 N개의 도시를 정확히 한 번 방문하여 원래 도시로 돌아오는 가장 짧은 경로를 찾는 문제입니다. 그러나 도시의 수가 증가할수록 가능한 경로와 최적의 해를 찾기 위한 계산 시간도 증가합니다.이 문제는 근사 방법을 사용하여 해결할 수 있지만, 양자 컴퓨터는 훨씬 더 좋은 해결책을 제공할 수 있으며, 훨씬 더 빠르게 제공할 수 있습니다.
이것은 이론 물리학자 Prof. Dr. Jens Eisert의 팀이 증명한 바와 같이, 양자 컴퓨터가 이러한 문제를 더 잘이고 더 빠르게 해결할 수 있음을 보여줍니다.
양자 컴퓨팅은 양자 역학을 활용하여 전통적인 컴퓨터, 심지어 슈퍼 컴퓨터를 넘어서는 복잡한 문제를 해결하는 하드웨어와 알고리즘을 사용합니다. 그러나 이러한 강력한 컴퓨터는 20세기 트랜지스터 기술에 의존하여 높은 복잡도의 문제를 해결할 때 제한됩니다.
이것이 양자 물리학이 등장하는 곳입니다. 클래식 컴퓨터와는 달리, 양자 컴퓨터는 0과 1의 이진 비트로 정보를 인코딩하는 대신 양자 비트(qubit)를 사용하여 다차원 양자 알고리즘을 실행합니다.
또한, 전통적인 컴퓨터와는 달리, 양자 컴퓨터는 팬을 사용하여冷却하는 대신, 양자 프로세서를 극저온으로 유지하여 양자 상태를 유지해야 합니다. 이것은 초 냉각 초유체를 통해 달성됩니다.
초전도체는 저항 없이 전자를 통과시키는 임계 양자 역학적 효과를 나타내는 물질입니다. 전자가 통과할 때, 전하를 장벽으로 운반하기 위해 쌍을 이룹니다. 두 개의 초전도체를 절연체의 양쪽에 배치하면, 조셉슨 접합이 형성되어 초전도 qubit을 구동하는 데 사용됩니다.
qubit은 양자 정보를 초위 상태로 배치하는 중요한 작업에 유용합니다. 초위 상태에 있는 qubit 그룹은 복잡한 다차원 계산 공간을 생성하여 복잡한 문제를 나타낼 수 있습니다.
여기서, 두 개의 qubit을 얽힐 경우, 하나의 변경이 다른 하나에 직접적으로 영향을 미칩니다. 이러한 얽힌 qubit을 초위 상태로 배치하면, 많은 확률을 얻을 수 있습니다. 양자 컴퓨터에서 계산은 모든 가능한 계산 상태의 초위 상태를 준비하고, 간섭을 통해 해를 찾는 방식으로 작동합니다.
물론, 많은 qubit을 가진 양자 컴퓨터를 구축하는 것은 매우 복잡한 절차입니다. 그러나 여러 방법이 이러한 컴퓨터가 수행할 수 있는 작업을 탐색하는 데 사용되고 있습니다.
에이저트는 헬름홀츠 센터 베를린(HZB)과 공공 연구 대학 프리드리히 빌헬름 베를린 대학교의 공동 연구 그룹을 이끄는 에이저트에 따르면:
“여기에는 많은 신화와 때때로 뜨거운 공기와 과장된 이야기가 있습니다. 그러나 우리는 엄격하게 접근하여 수학적 방법을 사용하고, 주제에 대한 견고한 결과를 제공했습니다. 무엇보다도, 어떤 의미에서든 이점이 있을 수 있는지澄明했습니다.”
중요한 여행하는 판매원 문제
최적화 문제인 TSP는 물류 및 공급망 산업에서 매우 중요한 경제적 중요성을 가지고 있습니다. 이는 작업 스케줄링, 자원 할당, 포트폴리오 최적화, 단백질 접히기 등 다양한 부문에서 중요한 조합 최적화 문제를 포함하는 더广い 범주의 일부입니다.
이러한 문제의 사회적 및 경제적 중요성으로 인해, 이러한 문제는 집요한 연구의 대상이 되었습니다. 따라서, 가장 효율적인 공급망과 가장 저렴한 배달 경로를 찾는 것과 같은 문제의 해답을 찾는 것은 우리의 일상 생활에 긍정적인 영향을 미칩니다.
그러나, 여러 목적지에 대한 배달 경로를 최적화하는 것은, 교통 정체, 운영 비용 증가,突然한 경로 변경, 마지막 순간의 비즈니스 약속, 고객 요청 등 다양한 제약 조건을 고려해야 하므로, TSP를 해결하는 것은 더욱 어려워집니다. 이러한 도전에도 불구하고, TSP를 해결하는 것은 효율적인 물류를 보장하기 위해 매우 중요합니다.
이 문제를 해결하는 데에는 여러 가지 이점이 있습니다. 예를 들어, 거리와 시간을 줄이고, 연료 사용을 절약할 수 있습니다. 이동 거리를 최소화하면 탄소 발자국을 크게 줄일 수 있으며, 이는 더 깨끗한 공기, 더 느린 기후 변화, 경제 성장과 같은 이점을 제공합니다. 또한, TSP를 해결하면 물건을 제시간에 배달하고, 고객과 약속을 지킬 수 있으며, 고객 경험과 현장 서비스 비즈니스를 향상시킬 수 있습니다.
우리가 본 것처럼, 이 문제를 해결하는 것은 비즈니스에만 도움이 되지 않으며, 이러한 이점은 고객에게도 확대됩니다. 따라서, 모든 관련자가 εμπλουishment된 경험을 할 수 있습니다.
TSP 문제를 해결하는 데에는 여러 가지 방법이 있습니다. 하나의 방법은 ‘무차별적’ 접근법으로, 모든 가능한 순열을 계산하여 가장 짧은 경로를 찾는 것입니다. 분기 및 경계 방법에서는 문제를 여러 하위 문제로 나누고, 각 단계의 해가 이후 단계에서 찾은 해에 영향을 미칩니다.
다이나믹 프로그래밍에서는 중복 계산을 피하는 데 중점을 둡니다. 가장 가까운 이웃은 근사 알고리즘으로, 시작 위치에서 시작하여 가장 가까운 위치에 정지합니다. 모든 도시를 다 방문한 후, 시작 위치로 돌아갑니다. 실제적이고 비교적 빠르지만, 항상 효율적인 경로를 제공하지는 않습니다.
기술이 발전함에 따라, 경로 계획과 최적화가 훨씬 더 효과적으로 수행될 수 있습니다. 특히, 인공 지능(AI)은 대량의 데이터를 빠르게 분석하여 많은 현대 기업이 운영 및 전략적 결정을 내리는데 도움이 될 수 있습니다.
양자 컴퓨터도 이 문제를 해결하기 위해 조사되고 있습니다. 양자 컴퓨터는 고전적인 컴퓨터보다 상당한 계산 속도 향상을 제공하므로, 이러한 문제에 대한 근사값을 개선하는 데 도움이 될 수 있습니다.
양자 컴퓨팅 기술을 사용하여 TSP 해결
양자 컴퓨팅은 엄청난 관심을 끌고 있으며, 특정 문제에 대한 약속된 결과를 제공하고 있습니다. 그러나, 양자 우위의 범위는 대부분 탐索되지 않았습니다.
따라서, 연구는 전통적인 컴퓨터를 능가하는 양자 컴퓨터의 능력을 입증했습니다. 조합 최적화 문제에 대한 근사값을 찾는 데에서, 양자 컴퓨터가 더 나은 해를 찾을 수 있음을 보여주었습니다.
최근 연구는 Eisert와 그의 동료 Jean-Pierre Seifert가 수행했으며, 분석적 방법만을 사용하여 qubit을 가진 양자 컴퓨터가 TSP 문제를 어떻게 해결할 수 있는지 평가했습니다.
“우리는 단지, 물리적인 구현에 관계없이, 충분한 qubit이 있다고 가정하고, 그들과 함께 컴퓨팅 작업을 수행할 수 있는 가능성을 살펴봅니다.”라고 Vincent Ulitzsch, 테크니컬 대학교 베를린의 박사 과정 학생이 설명했습니다.
그런 다음, 팀은 Shor 알고리즘, 즉 양자 알고리즘을 사용하여 정수의 소인수를 찾고, 이러한 최적화 문제의 하위 클래스를 해결했습니다. 이를 통해, 도시의 수가 증가할수록 계산 시간이 폭발적으로 증가하지 않습니다. 계산 시간은 다항식으로 증가합니다. 즉, Nx로 증가합니다. 여기서 x는 상수입니다. 이렇게 얻은 해는 전통적인 알고리즘을 사용하여 얻은 근사 해보다 훨씬 더 좋습니다.
암호학적 개념과 계산 학습 이론을 사용하여, 연구는 “양자 컴퓨터가 조합 최적화 문제의 근사에 대해 고전적인 컴퓨터보다 초 다항식 우위를 갖는다는 완전한 구성적 증거를 제공합니다.”
연구는 또한, 조합 최적화 문제의 근사 해를 찾는 데 양자 컴퓨터가 제공할 수 있는 잠재적인 이점에 대한 중요한 질문에 대한重大한 진전을 이루었다고 언급했습니다. 이러한 문제는重大한 사회적 및 경제적 영향을 미칩니다.
이 연구는 아인슈타인 연구 유닛, 베를린 수학 연구 센터(MATH+ Cluster of Excellence), BMBF(Hybrid), BMWK(EniQmA), 뮌헨 양자 밸리, DFG에 의해 자금을 지원받았습니다. 독일의 연방 교육 및 연구부도 재정적 지원을 제공했습니다.
양자 컴퓨팅의 잠재력 탐색
이것은 양자 컴퓨팅을 사용하여 TSP 문제를 해결하는 첫 번째 시도는 아니었습니다. 많은 사람들과 연구자들이 이미 이 문제를 해결하기 위해 양자 컴퓨팅을 사용하고 있습니다.
2022년 12월, 한 논문은 TSP를 위한 양자 알고리즘을 제안했습니다. 이 알고리즘은 Grover Adaptive Search(GAS) 프레임워크를 기반으로 합니다. GAS 프레임워크에서, 두 가지 기본적인 어려움이 있습니다. 해가 실현 가능하지 않을 수 있으며, 현재 양자 컴퓨터의 qubit 수는 매우 제한적이며, 조합 최적화 문제를 위한 양자 알고리즘의 최소 요구 사항을 충족할 수 없습니다.
따라서, 논문은 Hamiltonian Cycle Detection(HCD) 오라클을 다듬었으며, 알고리즘 실행 중에 비실용적인 해를 자동으로 제거할 수 있습니다. 또한, 양자 컴퓨팅의可逆性 요구 사항을 고려하여 qubit 사용을 절약하는 “錨登録” 전략을 설계했습니다. 이를 통해, 연구는 31개의 qubit만을 필요로 하며, 해의 성공률은 86.71%였습니다.
2019년, 자칭 물리학 전문가 Joseph Cammidge는 양자 컴퓨팅을 사용하여 TSP 문제를 해결하는 방법에 대해 썼습니다. 그는 양자 어닝 프로세서를 사용하여 7개의 도시를 위한 TSP 문제를 해결할 수 있었으며, 기술적 제한이 제거되면 9개의 도시를 해결할 수 있는 이론적 잠재력을 가지고 있습니다.
새로운 컴퓨팅 방법인 양자 어닝은 최적화 문제를 클래식 기술보다 빠르게 해결할 수 있는 잠재력을 보여주었습니다. 이론적으로, qubit은 극저온으로 냉각되면 최적의 저에너지 상태에 도달할 것입니다.
그러나, 2021년, 한 연구는 양자 어니어가 8개 이하의 노드를 처리할 수 있으며, 시간과 정확도 모두에서 클래식 솔버보다 성능이 낮습니다.
TSP 문제를 해결하기 위해 양자 컴퓨팅을 사용하는 것은 이미 오래전부터 진행되어 왔습니다. 20년 전, 2001년에 한 연구는 TSP 문제를 해결하기 위한 양자 알고리즘을 찾기 시작했습니다.
이 논문에서, 앨라배마 대학교의 Buckley Hopper는 Grover와 Shor의 양자 컴퓨터 알고리즘을 살펴보았습니다. 그는 Grover의 알고리즘이 단지 제곱근 개선을 제공한다는 것을 관찰했으며, 이는 클래스적으로 불가한 문제를 양자 컴퓨터에서 가역적으로 만들 수 없음을 의미합니다. Shor의 알고리즘에 대해서는, 특정 유형의 문제에만 적합하다는 것을 관찰했습니다.
전반적으로, Hopper는 “TSP의 근사 해를 계산하는 알고리즘에 대한 만족스러운 결과를 찾지 못했습니다.”
몇 년 후, 전기 및 전자 기술자 협회(IEEE)는 새로운 알고리즘을 제시했습니다. 이 알고리즘은 유전 알고리즘과 양자 컴퓨팅에서 영감을 받았습니다. IEEE는 이 알고리즘을 TSP의 일부 인스턴스에 적용한 결과가 표준 유전 알고리즘보다 훨씬 더 좋다는 것을 발견했습니다.
양자 컴퓨팅을 사용하는 회사
이제, 양자 컴퓨팅의 연구 및 개발에 참여하는 몇 가지 회사들을 살펴보겠습니다.
#1. IBM
국제 비즈니스 머신즈 코퍼레이션은 인공 지능, 클라우드 서비스, IT, 클라이언트 금융, 상업 금융 등 다양한 부문에서 활동하고 있습니다. 이 기술 대기업은 또한 양자 컴퓨팅에 참여하고 있으며, IBM Quantum Platform을 통해 공공 및 프리미엄 액세스를 제공하고 있습니다. 이는 IBM의 프로토 타입 양자 프로세서, 양자 계산에 대한 튜토리얼, 상호 작용 텍스트북을 포함합니다.
최근에, IBM 과학자들은 양자 컴퓨터의 게임 변경 잠재력을 해방하는 장벽을 극복하는 또 하나의 단계에 있다고 말했습니다. 이를 위해, 약 10배 더 효율적인 새로운 양자 오류 수정 코드를 도입했습니다.
작년 말, 회사는 1,121개의 초전도 qubit을 가진 양자 컴퓨터 Condor를 출시했습니다. IBM은 또한 모듈러 양자 컴퓨터인 IBM Quantum System Two와 양자 중심 슈퍼 컴퓨팅 아키텍처를 공개했습니다. 이는 확장 가능하며, 향후 5년 동안 출시될 칩으로 업그레이드할 수 있습니다.
(IBM )
시장 자본화가 175억 달러인 IBM의 주가는 190.86달러로 거래되고 있으며, 연중 실적은 16.66% 증가했습니다. IBM은 매출(TTM)이 618.6억 달러, 주당 순이익(EPS)이 8.03, 가격 대 수익비(P/E)가 23.76, 자기 자본 수익률(ROE)이 33.36%입니다. 회사는 3.48%의 배당 수익을 제공합니다.
#2. D-Wave Systems
이 양자 컴퓨팅 회사는 관련 시스템, 소프트웨어, 서비스를 개발 및 제공합니다. 제품으로는 The Leap과 The Advantage가 있으며, 스케줄링, 물류, 약물 발견, 제조 공정 등에 대한 양자 애플리케이션을 제공합니다.
이번 달 초, D-Wave는 양자 기계가 실제 적용 가능한 문제를 일반 컴퓨터보다 빠르게 해결할 수 있다고 말했습니다. 이 회사는 또한 1,200개의 qubit, 10,000개의 커플러, 어려운 최적화 문제에 대한 시간당 해결 속도가 20배 더 빠른 양자 컴퓨터를 발표했습니다.
(QBTS )
회사의 주가는 현재 1.86달러로 거래되고 있으며, 연중 실적은 138.6% 증가했습니다. 시가 총액은 2.67억 달러입니다. 회사는 매출(TTM)이 824.7만 달러, 주당 순이익(EPS)이 -0.66, 가격 대 수익비(P/E)가 -3.19입니다. 회사는 4분기 및 연간 실적에서 20% 이상의 매출 증가를 발표했으며, 주문은 각각 34% 및 89% 증가했습니다.
회사의 CEO인 Dr. Alan Baratz는 회사의 모멘텀을 선언하며, Zapata AI와의 다년간의 전략적 제휴, 1,200개 이상의 qubit Advantage2 프로토 타입의 도입, NEC Australia와의 공동 사업, Deloitte Canada와의 공동 사업, 그리고 전 국토 안보 장관인 Kirstjen Nielsen의 이사회의 임명을 언급했습니다.
결론
양자 컴퓨팅 시장은 2028년에 65억 달러에 이를 것으로 예상되며, TSP를 해결하는 데의 잠재력은 제조, 물류, 공급망 관리, 전자 상거래, 운송, 연구 등 다양한 산업에 영향을 미칩니다. 이는 생산성 향상, 비용 절감, 다양한 부문에서 혁신을 촉진할 수 있습니다.
