자파타 컴퓨팅 홀딩스
자파타 컴퓨팅 홀딩스는 주식 상장전 자파타 AI라는 이름으로 설립되었으며, WNNR과 병합하면서 나스닥에 우회 상장하였습니다.
자파타 컴퓨팅 홀딩스는 5차 산업 혁명이 아니냐는 이야기가 나올 정도로 차세대 산업에서 중요한 부분을 차지하고 있는 생성형 AI와 관련된 S/W 회사이며, 본사만의 양자 컴퓨팅 기술을 통해 창의가 필요한 IT 기업 외에도 제조업, 서비스 업 등 AI 분석이 필요한 회사에 도움을 주는 일을 통해서 매출을 올리고 있습니다.
자파타 컴퓨팅 홀딩스 급등
2024년 4월1일, 나스닥에 우회 상장한 자파타 컴퓨팅 홀딩스는 5달러로 평가되었으며, 상장전 WNNR은 15달러까지 급등했고, 자파타 컴퓨팅 홀딩스는 정규장이 열리기 전인 프리 마켓에서 50달러까지도 상승하며 급등세가 예측되었습니다.
하지만 상장 직후 15달러에서 시작된 주가는 종가 5달러까지 하락하였고, 이후 2주간 2.23달러까지 하락하였습니다.
그러나 2024년 4월12일 네이쳐지에 자파타와 밀접한 관려이 있는 AI 주제 논문이 기고되며 2.5달러에서 머물던 주가는 프리마켓에서 3.6달러까지 상승하며 급등 추세를 보여주었습니다.
자파타 컴퓨팅 홀딩스 관련 네이쳐 AI 연구 내용 번역
양자 컴퓨터 AI 논문 요약
검색 공간에 대한 효율적인 탐색을 고안하는 것은 조합 최적화 알고리즘 설계의 핵심 과제 중 하나입니다. 여기서는 최적화 문제를 해결하기 위해 모든 생성 모델(클래식, 양자 또는 양자에서 영감을 받은)을 활용하는 프레임워크인 GEO(Generator-Enhanced Optimization) 전략을 소개합니다.
저희는 텐서 네트워크 Born 기계에 의존하는 양자에서 영감을 받은 버전의 GEO(이하 TN-GEO)에 중점을 둡니다.
결과를 설명하기 위해 S&P 500 및 기타 여러 금융 주가 지수에서 인스턴스를 구성하여 표준 카디널리티 제약 포트폴리오 최적화 문제의 맥락에서 이러한 벤치마크를 실행하고 이러한 양자에서 영감을 받은 생성 모델의 일반화 기능이 산업 애플리케이션의 맥락에서 어떻게 실제 가치를 제공할 수 있는지 보여줍니다.
또한 최첨단 알고리즘을 포괄적으로 비교하고 TN-GEO가 최고임을 보여주며, 이는 비교에 사용된 솔버를 고려할 때 수십 년 동안 이 실제 산업 애플리케이션에서 미세 조정된 놀라운 결과입니다. 또한 양자에서 영감을 받은 모델과 그에 따른 양자 생성 모델을 통해 실용적인 이점을 향한 유망한 단계입니다.
양자 컴퓨터 기반 AI 논문 소개
합 최적화는 기계 학습 및 재료 시뮬레이션과 함께 실질적인 양자 이점을 위한 최고의 후보 중 하나입니다.
즉, 양자 지원 알고리즘이 상업적 또는 과학적 가치가 있는 실제 응용 분야에서 최고의 고전 알고리즘을 능가하는 순간입니다. 양자 어닐러(예: 1,2)에 맞게 조정된 알고리즘부터 게이트 기반 양자 컴퓨터(예: 3,4) 및 텐서 네트워크에 기반한 양자 영감(QI) 모델에 이르기까지 양자 서브루틴으로 최적화 문제를 해결하기 위한 기술 포트폴리오가 계속 진행 중입니다.
현재까지 제안된 양자 최적화 접근 방식에 관계없이 실세계 문제를 변수 수 측면에서 오버헤드를 초래하는 작업인 다항식 제약 없는 이진 최적화(PUBO) 식으로 변환할 필요가 있습니다. 이러한 PUBO 매핑을 보여주는 구체적인 실세계 사용 사례는 참고문헌 6과 7에 나와 있습니다. 따라서 여기서 제기된 변환 및 오버헤드 한계를 건너뛰고 임의의 목적 함수에서 작동할 수 있는 양자 최적화 전략을 찾는 것이 단기적으로 이상적일 것입니다.
저희 연구에서는 (양자 또는 고전) 생성 모델의 힘을 활용하는 발전기 강화 최적화(GEO) 프레임워크를 제안하여 이러한 문제에 대한 해결책을 제공합니다. 이 솔버 제품군은 조합 문제가 실제 환경에서 다루기 어려워지는 대규모 문제로 확장할 수 있습니다. 베이지안 최적화와 같은 대체 솔버 및 시뮬레이션 어닐링과 같은 일반 솔버와 비교하여 GEO의 다양한 기능을 강조하는 주요 결과를 제시합니다. 포트폴리오 최적화의 특정 실제 대규모 응용 프로그램의 경우 최첨단(SOTA) 최적화와 비교하여 접근 방식의 경쟁력을 보여줍니다.
양자 컴퓨터 기반 AI 논문 서두
다음은 제안된 접근 방식이 다른 사용 가능한 솔버에 비해 유리하도록 만드는 더 중요한 하이라이트입니다:
생성 모델의 힘을 활용합니다. 솔버의 본질은 데이터에서 명확하지 않은 구조를 밝히는 것을 목표로 한다는 것이며, 이러한 상관 관계를 포착하면 해당 반복 단계까지 볼 수 있는 상위 기능과 유사한 기능을 가진 새로운 후보를 제안합니다(그림 1 참조).
그림1 설명
GEO 프레임워크는 생성 모델을 활용하여 모든 양자 또는 고전적 솔버의 이전 샘플을 활용합니다. 훈련된 양자 또는 고전적 생성기는 기존 솔버가 도달할 수 없는 후보 솔루션을 제안하는 역할을 합니다. 이 시드 데이터 세트(단계 0)는 관찰 비트 문자열로 구성됩니다.
그리고 각각의 비용, 저렴한 비용으로 샘플에 더 많은 가중치를 부여하기 위해 시드 샘플과 그 비용은 비용 함수의 대리 역할을 하지만 확률론적 영역에서 하는 소프트맥스 함수를 구성하는 데 사용됩니다. 이 소프트맥스 대리점은 생성 모델(1-3단계)을 훈련하기 위해 훈련 세트 샘플을 회수하는 사전 분포 역할도 합니다. 1단계와 2단계 사이의 그림에서 볼 수 있듯이 소프트맥스 대리점의 훈련 샘플은 비용 가치가 낮은 샘플을 선호하는 편향이 있습니다. 여기에 제시된 작업을 위해 텐서 네트워크(TN) 기반 생성 모델을 구현했습니다.
따라서 저희는 양자에서 영감을 받은 GEO의 인스턴스화를 TN-GEO라고 부릅니다. 고전, 양자 또는 하이브리드 양자 고전의 다른 생성 모델 제품군은 본문에 설명된 대로 탐색할 수 있습니다. 양자에서 영감을 받은 생성기는 훈련 데이터의 주요 기능을 캡처하고 비용 이전에 사후 선택되는 새로운 솔루션 후보를 제안하는 데 사용되는 텐서 네트워크 본 머신(TNBM) 모델에 해당합니다.
평가됩니다(단계 4-6). 새로운 세트는 시드 데이터 세트(단계 7)와 병합되어 알고리즘의 다음 반복에서 사용될 업데이트된 시드 데이터 세트(단계 8)를 형성합니다. 여기서 부스터 또는 독립형 솔버로서 제안된 두 가지 TN-GEO 전략에 대한 더 많은 알고리즘 세부 사항은 본문과 보충 노트 1.F 및 1.G에서 확인할 수 있습니다.
서두 복귀
전체 접근 방식은 데이터 중심입니다. 즉, 문제를 해결하려는 이전 시도에서 얻은 데이터든 다른 최첨단 솔버에서 얻은 데이터든 더 많은 데이터의 가용성이 성능을 향상시킬 것으로 예상됩니다. GEO의 부스터 예에서는 SA(Simulated Annealing)에서 탐색한 데이터를 사용했지만, 다른 솔버에서 이전에 관찰한 데이터가 있다면 이를 결합하여 GEO의 시작점으로 제공할 수 있습니다.
이 모델은 비용 함수에 구애받지 않으며, 즉 블랙박스 솔버입니다. 우리의 접근 방식으로 모든 비용 함수를 해결할 수 있기 때문에 이것은 가장 중요합니다. 양자 또는 양자에서 영감을 얻은 최적화를 위한 제안의 대부분은 문제의 비용 함수를 2차 또는 다항식으로 매핑해야 합니다. 이는 비용 함수를 계산하는 것이 얼마나 복잡하거나 비용이 많이 드는지에 관계없이 모든 이산 최적화 문제를 해결할 수 있는 가능성을 열어줍니다. 이것은 생성 모델에 전달된 정보가 탐색된 비트열과 각각의 비용 값뿐이기 때문에 가능합니다.
포트폴리오 최적화에 대한 다재다능함과 전략적 초점: 위의 항목에서 따랐습니다. 우리 연구의 NP-하드 문제로 카디널리티 제약 포트폴리오 최적화를 선택한 주요 동기는 지난 수십 년 동안 미세 조정된 구체적인 벤치마크와 해결사의 광범위한 문헌의 가용성이었습니다. 새로운 메타 휴리스틱이 제안될 때마다 포트폴리오 최적화가 벤치마크에 사용될 가능성이 높습니다. 다른 최근 독립적인 작업은 GEO8,9의 다른 실제 응용 프로그램을 고려했습니다. 예를 들어, 참고 문헌 8의 저자는 평면 계획 NP-하드 문제와 관련된 산업 사례를 고려했습니다. 이 블랙박스 기능은 이진 변수 측면에서 다항식이 되도록 비용 함수에 의존하는 양자 근사 최적화 알고리즘(QAOA)3,4와 같은 다른 양자 휴리스틱에 비해 우리의 접근 방식을 유리하게 만드는 가장 중요한 기능 중 하나입니다.
최적화기 내에서 생성 모델을 서브루틴으로 활용하는 다른 제안(예: GFlowNets10 및 변형 신경 어닐링 11 알고리즘 참조)이 최근에 등장했지만, 저희 프레임워크는 임의의 비용 함수(즉, 블랙박스 솔버)를 처리하는 기능과 생성기를 양자 또는 양자에서 영감을 얻은 구현으로 교체할 수 있는 기능을 모두 제공합니다. 또한 GEO에는 더 많은 데이터를 사용할 수 있을수록 더 많은 정보를 전달하고 (양자) 생성기를 훈련하는 데 사용할 수 있다는 향상된 기능이 있습니다.
그림 1과 같이 GEO 세부 사항에 따라 생성 모델링 코어가 고전, QI 또는 양자 회로(QC) 향상 또는 하이브리드 양자 고전 모델에 이르는 전체 솔버 제품군을 구성할 수 있습니다. 이러한 옵션은 각각 볼츠만 머신12 또는 GAN(Generative Adversarial Networks)13, TNBM(Tensor-Network Born Machines)14, QCBM(Quantum Circuit Born Machines)15 또는 QC-AAN(Quantum-Circuit Associative Adversarial Networks)16을 활용하여 실현할 수 있습니다.
QI 알고리즘은 효율적인 텐서 네트워크(TN) 표현을 사용하여 더 큰 규모의 양자 시스템을 시뮬레이션 할 수 있기 때문에 흥미로운 대안이 됩니다. 양자 생성 모델을 구축하는 데 사용되는 TN의 복잡성에 따라 수천 개의 문제 변수에서 수십 개까지 시뮬레이션 할 수 있으며, 후자는 보편적인 게이트 기반 양자 컴퓨팅 모델을 시뮬레이션하는 한계입니다. 이는 QI 모델을 선택하여 양자 생성 모델에서 사용할 수 있는 양자 자원의 양을 제어 할 수 있습니다.
따라서 모든 양자 생성 모델 옵션에서 우리는 TN을 기반으로 한 QI 생성 모델을 사용하여 GEO 전략을 테스트하고 산업 규모 시나리오에서 발견되는 것에 상응하는 여러 변수가 있는 인스턴스로 확장하기로 결정했습니다. 저희는 이후 저희의 해결사를 TN-GEO라고 부릅니다. TN-GEO 모델의 훈련을 위해 Han 등의 작업을 따랐고, 그들은 MPS(Matrix Product States)를 사용하여 비지도 생성 모델을 구축할 것을 제안했습니다. 후자는 감독 ML18,19,20,21의 맥락에서 양자에서 영감을 얻은 모델의 초기 성공에서 범위를 확장합니다.
이 작업에서는 양자 강화 솔버 제품군에 대한 두 가지 작동 모드에 대해 논의할 것입니다.
"부스터"로서 TN-GEO에서 고전(또는 양자) 솔버의 과거 관측치를 활용합니다. 이 모드를 설명하기 위해 시뮬레이션 어닐링(SA) 실행의 관측치를 사용합니다. 이 섹션에는 결과가 제시되어 있으며 시뮬레이션 세부 정보는 보충 노트 1.F에 제공됩니다. 독립형 솔버로서 TN-GEO의 모든 초기 비용 함수 평가는 양자에서 영감을 얻은 생성 모델에 의해 전적으로 결정되며, MPS 모델이 캡처하려는 목표 확률 분포를 지원하기 위해 무작위 사전이 구성됩니다.
결과는 이 섹션에 제시되어 있으며 시뮬레이션 세부 정보는 보충 노트 1.G에 제공됩니다. 이 두 전략 모두는 그림 1의 알고리즘 워크플로우 다이어그램에 캡처되어 있으며 보충 노트 1에 더 자세히 설명되어 있습니다. 이 두 설정 모두에 대한 구현을 설명하기 위해 카디널리티 제약이 있는 포트폴리오 최적화 문제의 NP 하드 버전에서 성능을 테스트했습니다. 특정 자산 세트 또는 포트폴리오에 대한 최적의 투자를 선택하는 것은 정량적 금융 분야에서 매우 중요한 문제입니다. 이 문제는 일부 투자 제한을 준수하면서 자산 간에 자본을 최적으로 할당하는 것이 목표인 투자자에게 실질적으로 중요합니다.
Markowitz22에서 도입한 이 최적화 작업의 목표는 정의된 수준의 위험에 대해 가장 높은 기대 수익(이익)을 제공하거나 주어진 수준의 기대 수익에 대해 가장 낮은 위험을 제공하는 포트폴리오 세트를 생성하는 것입니다. 이 작업에서는 이 카디널리티 제약 최적화 문제의 두 가지 변형에 초점을 맞춥니다. 첫 번째 시나리오는 특정 목표 수익률이 주어지면 변동성이나 위험을 최소화하는 포트폴리오를 선택하는 것을 목표로 합니다(더 자세한 내용은 보충 노트 1.A에 제공됨).
가장 성능이 좋은 SOTA 알고리즘에서 보고된 결과와 비교하기 위해 고정된 수준의 위험 회피가 주어지면 가장 좋은 포트폴리오를 선택하는 것이 목표인 두 번째 시나리오에서 TN-GEO를 실행했습니다. 이는 문헌에서 SOTA 솔버 간의 비교와 관련하여 가장 일반적으로 사용되는 이 최적화 문제의 버전입니다(자세한 내용은 부록 1.B에 나와 있습니다).
다른 조합 최적화 솔버의 부스터로서의 TN-GEO
그림 2에서 저희는 실험 설계와 TN-GEO를 부스터로 사용하여 얻은 결과를 제시합니다. 이 실험에서 저희는 시뮬레이션 어닐링(SA)의 중간 결과를 사용하여 TN-GEO 알고리즘의 시드 데이터로 어떻게 사용할 수 있는지 설명합니다.
그림 2A에 설명된 바와 같이 TN-GEO 전략(전략 4)과 비교하기 위해 탐색한 두 가지 전략(전략 1 및 2)이 있습니다. 각 전략을 공정하게 비교하기 위해, 저희는 각 전략에 거의 동일한 계산 시간을 제공합니다. 전략 2의 경우, 이는 TN-GEO에 할당된 시간으로 SA를 추가로 재시작하는 것으로 해석됩니다. 전략 2에 사용된 설정과 비교하여 처음부터 SA에 대한 다른 설정을 탐색한 전략 1의 경우, 이는 전략 2에서 SA에 할당된 것과 동일한 총 비용 함수 평가 수를 사용하는 것과 같습니다.
실험의 경우 이 수는 전략 1 및 2에 대해 20,000개의 비용 함수 평가로 설정되었습니다. 전략 4에서 TN-GEO는 전략 2에서 나온 처음 10,000개의 관측치 중 가장 좋은 1,000개로 구성된 사전에 초기화되었습니다(자세한 내용은 보충 참고 1.F 참조). TN-GEO 전략에서 얻은 성능 향상을 평가하기 위해 상대적인 TN-GEO 향상인 η를 계산하고 이를 다음과 같이 정의합니다.
A 개략적인 표현을 보여줍니다. 전략 1-3은 시뮬레이션 어닐링(SA), 병렬 템퍼링(PT), 일반 알고리즘(GA) 등과 같은 고전적인 최적화 도구 모음을 사용하여 조합 최적화 문제를 해결할 때 사용자가 탐색할 수 있는 현재 옵션에 해당합니다.
전략 1에서 사용자는 선호하는 해결사와 함께 계산 예산을 사용합니다. 전략 2-4에서 사용자는 중간 결과를 검사하고 동일한 해결사(strategy 2)로 계속 시도할지, 중간 결과를 얻기 위해 사용되는 새로운 해결사 또는 동일한 해결사의 새로운 설정을 사용할지, 또는 여기서 제안한 대로 획득한 데이터를 사용하여 TN-GEO(strategy 4)와 같은 GEO 프레임워크 내에서 양자 또는 양자에서 영감을 얻은 생성 모델을 훈련할지 여부를 결정합니다. B 결과는 전략 1 또는 전략 2에 비해 TN-GEO의 상대적인 TN-GEO 향상을 보여줍니다. 양의 값은 TN-GEO가 각각의 고전적인 전략을 능가하는 런을 나타냅니다(κ (1) 참조).
데이터는 실험의 20개의 독립적인 런에서 부트스트랩된 중위수를 나타내고 오차 막대는 95% 신뢰 구간에 해당합니다. 여기에 제시된 두 개의 인스턴스는 두 가지 다른 카디널리티 제약 조건(κ = 30 및 strategy = 50)에서 S&P 500 시장 지수에 포함된 모든 자산(N = 500)이 포트폴리오 최적화 인스턴스에 해당합니다. 이 카디널리티 제약 조건은 유효한 포트폴리오에 한 번에 포함될 수 있는 자산의 수를 나타내며, 검색 공간을 산출합니다. M ~ 1069개의 포트폴리오로 κ = 50을 지원합니다.
여기서는 고전적인 전략(예: 전략 1-3)에 의해 발견되는 가장 낮은 최소값입니다.
양자 강화 접근 방식(예: TN-GEO)에서 발견된 가장 낮은 값에 해당합니다. 따라서 양의 값은 고전적인 접근 방식에 비해 개선된 것을 반영하는 반면, 음의 값은 고전적인 솔버가 양자 강화 제안을 능가하는 경우를 나타냅니다.
도 2B에 도시된 바와 같이, 우리는 TN-GEO가 구현된 고전적 전용 전략 모두에서 평균적으로 성능이 우수하다는 것을 관찰했습니다. 여기서 관찰된 양자에서 영감을 얻은 향상과 변수(assets)의 수가 증가함에 따라 더 큰 향상 경향은 N = 30에서 N = 100 사이의 여러 변수를 가진 다른 많은 투자 우주에서 확인되었습니다(자세한 내용은 보충 노트 3 참조). SA와 비교하여 향상을 보여주지만, 우리의 접근 방식은 해결사가 찾은 솔루션을 기반으로 하고 검색 시작부터 경쟁하지 않기 때문에 다른 해결사를 사용할 때도 유사한 결과를 기대할 수 있습니다. 또한 사용 가능한 데이터가 많을수록 TN-GEO의 기대 성능이 향상됩니다. 부스터로서의 TN-GEO의 중요한 하이라이트는 이러한 이전 관찰이 순수한 양자 또는 고전적 또는 하이브리드처럼 다른 해결사 조합에서 나올 수 있다는 것입니다.
고전적인 전용 전략과 비교하여 관찰된 성능 향상은 관련 검색 공간, 즉 지정된 기대 투자 수익에 대해 낮은 위험 값을 산출할 수 있는 포트폴리오를 나타내는 비트열 구성 x의 공간에 대한 더 나은 탐색에서 비롯되어야 합니다. 이것이 TN-GEO 구성의 직관입니다. 생성 모델의 목표는 이전에 관찰된 데이터에서 중요한 상관 관계를 포착하고 생성 기능을 사용하여 유사한 새로운 후보를 제안하는 것입니다.
새로운 후보를 생성하는 것은 ML에서 결코 사소한 작업이 아니며 모델의 일반화 능력을 측정하기 때문에 모델의 유용성과 파워를 결정합니다. 이 QI 생성 모델 설정에서 TN-GEO의 핵심에 있는 MPS 기반 생성 모델은 단순히 훈련 세트의 일부로 제공된 관찰을 기억하는 것이 아니라 새로운 보이지 않는 후보를 제공할 것으로 예상됩니다. 이는 최근 합성 데이터 세트(예: 24,25,26 참조)에서 어느 정도 테스트되고 입증된 아이디어입니다. 그림 3에서 저희는 양자에서 영감을 얻은 생성 모델이 새로운 샘플로 일반화되고 있으며 이러한 모델이 최적화 검색에 실제 가치를 추가한다는 것을 보여줍니다. 이는 산업 규모 환경에서 실제 응용의 맥락에서 양자 생성 모델의 일반화 능력을 보여주며, 이는 저희 논문의 주요 결과 중 하나에 해당합니다.
파란색 히스토그램은 N = 50 및 N = 100 자산을 가진 투자 우주에 해당하는 고전적인 솔버(종자 데이터 세트)에서 얻은 관측치 또는 포트폴리오의 수를 나타냅니다. 주황색은 TN-GEO의 핵심에 있는 양자 생성 모델에서 얻은 샘플을 나타냅니다.
녹색 대시 선은 종자 데이터에서 발견되는 최상의 위험 값에 위치합니다. 이 표시는 양자 생성 모델로 얻은 모든 새로운 샘플을 강조하며 고전적인 솔버 자체에서 얻은 샘플보다 낮은 포트폴리오 위험 값(최소값 향상)에 해당합니다. N = 50의 경우 샘플 수는 31이고 N = 100의 경우 MPS 생성 모델에서 349개의 샘플을 얻었습니다.
우리의 TN 기반 생성 모델은 고전적인 시드 데이터보다 더 나은 최소값을 생성할 뿐만 아니라 저비용 스펙트럼에서 풍부한 양의 샘플을 생성합니다. 이 편향은 TN-GEO의 설계에 각인되어 있으며 그림 1에 표시된 소프트맥스 대리 사전 분포의 목적입니다. 새로운 샘플의 이러한 풍부함은 알고리즘의 다음 반복에 유용할 뿐만 아니라 응용 프로그램을 해결하는 사용자에게 쉽게 가치가 있을 수 있습니다.
일부 응용 프로그램에서는 준우승자에 대한 정보를 갖는 데에도 가치가 있습니다. 궁극적으로 비용 함수는 검색을 안내하는 시스템의 모델일 뿐이며 가장 낮은 비용은 실제 투자 전략에서 최상의 성능으로 이어지지 않습니다.
독립형 솔버로서의 발전기 강화 최적화
다음으로, 저희는 독립형 솔버로서 TN-GEO 프레임워크의 성능을 살펴봅니다. 초점은 비용 함수를 평가하는 데 비용이 많이 들고 이 함수에 대한 최소 호출 횟수 내에서 최선의 최소값을 찾는 것이 필요한 조합 문제에 있습니다.
그림 4에서 저희는 네 가지 고전적인 최적화 전략과의 비교를 제시합니다. 첫 번째 솔버로 저희는 가능한 모든 포트폴리오의 2N 비트열에 대한 완전 무작위 검색 전략에 해당하는 무작위 솔버를 사용하고, 여기서 N은 투자 세계의 자산 수입니다. 두 번째 솔버로 저희는 완전 무작위 검색에 비해 더 정교한 무작위 전략인 조건부 무작위 솔버를 사용합니다. 조건부 무작위 전략은 검색이 고정된 수의 κ 자산을 포함하는 비트열로 제한된다는 선험적 정보를 사용합니다. 따라서 조합 가능성의 수는 이는 2N보다 훨씬 작습니다.
예상대로, 이 정보를 사용하지 않는 경우 전체 2N 검색 공간에 대한 무작위 솔버의 성능은 더 좋지 않습니다. 여기서 고려된 다른 두 가지 경쟁 전략은 SA와 베이지안 최적화 라이브러리 GPyOpt23입니다. 이 두 고전 솔버 모두에서 고정된 κ로 이 카디널리티 제약을 부과하도록 검색 전략을 조정했습니다(보충주 1.E의 자세한 내용). 이는 성능을 높이기 위해 해당 선험적 정보를 사용하지 않는 TN-GEO의 기준을 훨씬 더 높입니다.
MPS 생성 모델의 특정 적응은 양자 상태의 입자 수에 MPS 보존을 부과할 수 있는 응축 물질 물리학의 아이디어를 차용하여 구축에 의한 자산 수를 보존하기 위해 구현될 수 있습니다. 보충주 1.G에 설명된 바와 같이, 우리는 알고리즘을 초기화하는 인공 시드 데이터 세트를 구축하는 동안에만 간접적으로 이 정보를 사용하지만(단계 0, 그림 1), QI 생성 모델 구축 중에 강력한 제약 조건이 되거나(단계 3, 그림 1), 여기서 나오는 새로운 후보 샘플을 생성하기 위해 부과되지 않습니다(단계 4, 그림 1).
네 가지 고전적 경쟁 전략에 대한 TN-GEO의 비교에서 투자 우주는 N = 30에서 N = 100 범위의 자산 수(문제 변수)의 다양성을 가진 S&P 500의 하위 집합으로 구성됩니다.
목표는 여기에서 다루는 조합 문제의 사양 중 하나인 기대 수익이 주어지면 위험을 최소화하는 것입니다. 오차 막대와 95% 신뢰 구간은 각 문제에 대한 각 솔버에 대해 100개 이상의 독립적인 무작위 초기화를 부트스트래핑하여 계산됩니다. 각 솔버의 주요 줄은 이러한 100번의 반복에 걸쳐 부트스트래핑된 중위수에 해당하며, 이는 여기에서 고려하는 고전적 솔버에 비해 TN-GEO의 우수한 성능을 보여줍니다.
본문에 명시된 바와 같이 TN-GEO를 제외하고 고전적 솔버는 유효한 포트폴리오 선택에 부과된 카디널리티 제약 조건에서 오는 선험적 정보를 유리하게 사용합니다.
그림 4에서 우리는 널리 사용되는 솔버와 비교하여 TN-GEO 독립형 전략의 장점을 보여줍니다. 특히, TN-GEO와 다른 솔버 사이의 간격은 더 많은 수의 변수에서 더 큰 것으로 보인다는 점이 흥미롭습니다.
최첨단 알고리즘과의 비교
마지막으로, 우리는 TN-GEO를 이 특정 조합 문제에 대한 광범위한 알고리즘 전략을 다루는 9개의 다른 선도적인 SOTA 최적화기와 비교하고 다음과 같이 언급합니다.
(1) 유전 알고리즘, 타부 검색 및 시뮬레이션 어닐링인 GTS27; (2) 개선된 입자 군집 최적화 알고리즘인 IPSO28; (3) 입자 군집 최적화와 시뮬레이션 어닐링을 결합한 하이브리드 알고리즘인 IPSO-SA29; (4) 인구 기반 증분 학습 및 차등 진화 알고리즘인 PBILD30; (5) 탐욕 무작위 적응 솔루션 절차인 GRASP31; (6) 실행 가능성 실행 및 실행 불가능성 절차를 갖춘 인공 꿀벌 군집 알고리즘인 (7) 개미 군집 최적화, 인공 꿀벌 군집 및 유전 알고리즘을 통합한 하이브리드 알고리즘인 AAG33; (8) 2차 프로그래밍과 결합된 가변 이웃 검색 알고리즘인 VNSQP34; 그리고 (9) 빠르게 수렴하는 인공 꿀벌 군집 알고리즘인 ABC-HP35. (10) 또한, 우리는 생성기로 신경 자기회귀 밀도 추정(NADE)36 모델을 기반으로 하는 고전적인 버전의 GEO를 포함했습니다. 우리는 이 구현을 NADE-GEO라고 부릅니다.
카디널리티 제약 포트폴리오 최적화 문제를 다룬 문헌의 대다수 연구자들이 사용하는 테스트 데이터는 OR-Library37에서 나온 것으로 1992년 3월부터 1997년 9월까지의 주간 가격에 해당하는 홍콩 항셍(31개 자산), 독일 DAX 100(85개 자산), 영국 FTSE 100(89개 자산), 미국 S&P 100(98개 자산), 일본 닛케이 225(225개 자산)입니다.
중요한 점은 NADE-GEO와 TN-GEO를 제외한 9개의 솔버는 각각의 참고 문헌에서 저자에 의해 미세 조정되었다는 것입니다. 각각의 저자는 이 표준 벤치마크 문제에서 성공하기 위한 최선의 결과를 보고했으며, 이는 우리가 여기에 구현된 두 버전의 GEO와 비교하여 보고한 값입니다. TN-GEO와 NADE-GEO의 하이퍼파라미터 미세 조정에 대한 자세한 내용은 부록 노트 1.H에서 확인할 수 있습니다.
전체 비교에는 위에서 언급한 10개의 알고리즘이 포함되지만, 이 섹션에서는 2000년대 초반의 메타 휴리스틱을 제외하고 NADE-GEO를 포함하여 현재의 최첨단 옵티마이저에만 초점을 맞추고 전체 결과의 축소 버전을 제시하는 데 중점을 둘 것입니다. 특히 이 섹션에서 결과가 제시된 선택된 알고리즘은 GRASP, ABCFEIT, AAG, VNSQP, ABC-HP 및 NADE-GEO입니다. 전체 결과는 보충 노트 3에 나와 있습니다.
따라서 여기서는 TN-GEO로 얻은 결과와 NADE-GEO 및 위에서 언급한 5개의 다른 SOTA 메타휴리스틱 알고리즘과의 비교 결과를 문헌에서 공개적으로 사용할 수 있습니다.
최종 해석
다른 양자 최적화 전략에 비해 TN-GEO의 중요한 특징은 알고리즘의 유연성입니다. 여기에 표시된 바와 같이, 다른 제안과 달리 당사의 GEO 프레임워크는 임의의 비용 함수에 적용될 수 있으며, 이는 다항식 제약 없는 이진 최적화(PUBO) 문제에 대한 명시적 매핑으로 쉽게 해결할 수 없는 새로운 응용 프로그램의 가능성을 열어줍니다.
저희의 접근 방식은 또한 모든 해결사, 아마도 더 효율적이거나 심지어 응용 프로그램별 최적화기에서 나올 수 있기 때문에 종자 샘플의 출처와 관련하여 유연합니다. 핵심을 형성하는 생성 모델의 입증된 일반화 기능은 TN-GEO가 다른 최첨단 해결사를 사용한 이전 실험의 진행 상황을 기반으로 구축하는 데 도움이 되며, 고전적인 최적화기만으로는 달성할 수 없을 수 있는 새로운 후보를 제공합니다. 저희는 이 유연한 접근 방식이 산업 규모의 실제 조합 최적화 문제에 대한 양자 및 양자에서 영감을 얻은 생성 모델의 광범위한 적용 가능성을 열어줄 것이라고 낙관합니다.
이 작업의 범위를 텐서 네트워크 기반 생성 양자 모델로 제한했지만, 다른 생성 양자 모델도 고려하는 것은 자연스러운 확장입니다. 예를 들어, 양자 회로 연관 적대 네트워크(QC-AAN) 16과 같은 하이브리드 고전 양자 모델을 쉽게 탐색하여 소위 노이즈가 많은 중간 규모 양자(NISQ) 장치 40과 함께 생성 양자 모델의 힘을 활용할 수 있습니다. 특히, QC-AAN 프레임워크는 더 많은 수의 변수를 사용하고 이산 값을 넘어서는 작업, 예를 들어 혼합 정수 프로그래밍(MIP) 최적화 문제 41 또는 42에서 볼 수 있는 연속 값을 가진 변수를 수행할 수 있는 가능성을 열어줍니다.
양자 기반 및 하이브리드 양자 고전 알고리즘은 모두 이 NP-하드 버전의 포트폴리오 최적화 문제 또는 기타 조합 최적화 문제의 훨씬 더 큰 문제 크기에서 이 GEO 프레임워크에서 테스트할 수 있습니다. NISQ 장치의 큐비트 수가 증가함에 따라 양자 회로 본 머신(QCBM) 15: 게이트 기반 양자 컴퓨터로 임의의 확률 분포를 모델링하고 생성 모델링 작업을 수행하는 일반적인 프레임워크와 같은 더 많은 양자 자원을 활용할 수 있는 생성 모델을 탐색하는 것도 흥미로울 것입니다.
양자 장치를 사용하여 GEO에서 상당한 이점을 얻을 수 있는지에 대한 질문은 현재 활발히 연구되고 있는 주제입니다. 양자에서 영감을 받은 최고의 솔루션에서 향상된 양자 하드웨어 구현으로 보다 체계적이고 점진적인 향상에 도달하기 위한 한 가지 제안이 최근 참고문헌 43에서 제안되었습니다. 거기에서 사용 가능한 최고의 양자에서 영감을 받은 텐서 네트워크 솔루션에서 시작하여 양자 회로에 매핑합니다. 이는 양자에서 영감을 받은 텐서 네트워크 기반 솔루션으로 접근할 수 있는 것 이상으로 그럴듯한 상관 관계를 높이기 위해 분해된 것 이상으로 게이트를 추가하여 후속적으로 수정할 수 있습니다.
