최적화란?
참고
Microsoft QIO 및 1QBit 최적화 솔버가 더 이상 사용되지 않으며 2023년 6월 30일 이후에는 Azure Quantum 서비스에서 더 이상 사용할 수 없습니다.
최적화는 원하는 결과와 제약 조건을 고려하여 가능한 옵션 세트에서 문제에 대한 최상의 솔루션을 찾는 프로세스입니다.
최상의 솔루션이란 여러 가지 의미를 가질 수 있습니다. 비용이 가장 저렴한 옵션일 수도 있고, 런타임이 가장 빠르거나, 환경적 영향을 가장 적게 주는 옵션일 수도 있습니다. 작업을 간단하게 유지하기 위해 가장 좋은 방법은 일반적으로 최소화할 비용 함수 로 정의됩니다. 대신 비용 함수를 최대화하려는 경우(예: 태양 전지에서 에너지 출력을 최대화하려는 경우) 비용을 음수로 곱한 다음 최소화하기만 하면 됩니다.
최적화 문제 및 용어에 대한 자세한 정보는 최적화의 주요 개념을 참조하세요.
최적화란 향후 양자 컴퓨터에서 실행하기 위한 주요 후보인 컴퓨팅 문제의 클래스로, 클래식 솔루션에 비해 양자 이점을 제공합니다. 현재 Azure의 클래식 하드웨어에서 실행되는 Azure Quantum 솔버를 사용하여 다른 많은 클래식 최적화 기술보다 빠르게 최적화 문제를 구현할 수 있습니다.
QIO(양자 유도 최적화)란 무엇인가요?
기존 컴퓨터에서 양자 효과를 시뮬레이션함으로써 새로운 유형의 양자 솔루션이 개발되었습니다. 양자 기반 최적화 알고리즘은 클래식 하드웨어에서 양자 컴퓨팅의 장점 중 일부를 활용하여 기존 접근 방식보다 속도를 높입니다.
양자 기반 알고리즘은 속도 향상을 제공하는 본질적인 양자 현상을 전통적으로 에뮬레이션할 수 있는 고전적 알고리즘입니다. 양자 유도형 알고리즘에는 여러 가지 유형이 있습니다. 일반적으로 사용되는 알고리즘은 다음과 같이 구성된 단열 양자 컴퓨팅이라는 계산 모델을 기반으로 합니다.
먼저 시스템을 준비하고 가장 낮은 에너지 상태로 초기화합니다.
그런 다음, 해결하고자 하는 문제를 설명하는 더 복잡한 시스템으로 천천히 변환합니다. 단열 모델에 따르면 변환이 충분히 느리게 일어나는 한, 시스템은 적응할 시간을 확보하고 최저 에너지 구성을 유지합니다. 변환이 완료되면 문제를 해결할 수 있습니다.
이에 대한 좋은 비유로 한 잔의 물을 생각해 볼 수 있습니다. 물이 담긴 잔을 테이블 위에서 천천히 움직이면 시스템이 새로운 구성에 적응할 시간이 있기 때문에 물이 쏟아지지 않습니다. 하지만 잔을 빠르게 움직이면 시스템에는 변화가 지나치게 빠르게 발생하고 물이 사방에 쏟아지게 됩니다.
양자 기반 최적화는 어디에 적용되나요?
양자 기반 최적화를 실제 문제에 적용하면 비즈니스에 새로운 인사이트를 제공하거나 프로세스의 효율을 높여 비용 절감에 도움이 될 수 있습니다. 양자 기반 최적화에는 다음과 같은 장점이 있습니다.
- 주어진 사용 사례와 솔루션 품질로 다른 최적화 기법에 비해 더 빠르게 솔루션을 찾을 수 있습니다.
- 주어진 문제와 시간으로 다른 최적화 기법에 비해 더 나은 품질의 솔루션을 찾을 수 있습니다.
- 더 많은 변수를 고려하도록 문제를 확장하여 다른 최적화 기법에 비해 더 현실적인 모델을 사용합니다.
참고
양자 기반 최적화 방법은 추론이므로, 최적의 솔루션을 찾는다거나 항상 다른 최적화 기법보다 나은 성과를 낸다고는 보장할 수 없습니다. 실제로는 문제에 따라 다르며, 어떤 상황에서는 양자 기반 최적화의 성과가 다른 방식보다 낫고, 어떤 상황에서는 아닌지를 알아내는 것은 여전히 활발하게 연구되는 분야입니다.
기존의 다른 최적화 알고리즘에 비해 양자 기반 최적화가 제대로 작동하는 데 필요한 조건은 다음과 같습니다.
- 최적화 지형은 들쭉날쭉하되, 구조화되어 있어야 합니다. 해당 지형은 현실 문제에서 빈번하게 발생합니다. 추가 정보는 최적화 지형을 참조하세요.
- 변수 수가 작으면(예: 100 미만) 단순화 알고리즘으로도 충분합니다. 수백 개의 변수가 포함된 문제의 경우, 양자 기반 최적화는 기존에 사용한 방법에 비해 크기 정도에서 개선이 있었습니다.
- 선택한 비용 메트릭에 영향을 주는 문제 매개 변수는 비용 함수의 변수를 통해 표현해야 합니다. PUBO 문제를 가져오기 위해 이진 변수에 대한 다항식으로 비용 함수를 표현합니다.
양자 기반 최적화는 문제를 어떻게 해결하나요?
비용 함수의 글로벌 최솟값을 찾는 데는 몇 가지 방법이 있습니다. 가장 성공적이고 널리 사용되는 추론 중 하나는 시뮬레이션된 강화입니다. 추론은 대략적인 솔루션을 찾는 기법인데, 특히 정확한 솔루션을 찾는 데 너무 오래 걸릴 수 있는 상황에서 그렇습니다. 이 기법을 검색 공간의 임의 탐색이라고 생각할 수 있습니다. 여기에서 각 워커는 최적화 지형을 관통하는 경로를 만듭니다.
시뮬레이션된 강화에서 알고리즘은 이상적으로 항상 하향 이동하는 워커를 시뮬레이션하지만 0이 아닌 어떤 확률로 상향 이동도 가능합니다. 이로 인해 국소 최저점에서 이탈해서 인근의 더 낮은 최저점으로 내려갈 가능성이 생깁니다. 상향 이동을 열 점프라고 합니다. 시뮬레이션된 강화가 천천히 냉각되는 재질의 행태를 모방한 물리학의 알고리즘이기 때문입니다.
양자 기반 최적화는 시뮬레이션된 강화의 복합 문제 해결 방법을 사용하지만 양자 기계적 효과를 적용합니다.
양자 강화는 양자 알고리즘이며, 기본적으로는 시뮬레이션된 강화와 비슷하지만 몇 가지 측면에서 차이가 있습니다. 시뮬레이션된 강화에서는 한 솔루션에서 다른 솔루션으로의 열 점프를 통해 검색 공간을 탐색하지만, 양자 강화는 양자 터널링이라는 양자 효과를 활용하여 워커가 해당 에너지 장벽을 통해 이동할 수 있게 합니다.
이 그래프에서는 기존 및 양자 방법 간의 차이점을 확인할 수 있습니다. 시뮬레이션된 강화에서는 열 변동으로 인해 에너지 장벽을 극복할 수 있고, 양자 터널링에서는 양자 효과를 통해 워커가 에너지 장벽을 통과할 수 있습니다.
Azure Quantum 최적화 기법
최적화 문제를 만든 후에는 Azure Quantum의 양자 기반 최적화 솔버 중 하나에 제출할 수 있습니다. 최적화 작업을 제출하는 방법을 참조하세요.
Azure Quantum에서는 개별적 및 복합적 최적화 문제를 해결하는 광범위한 양자 기반 기법을 사용할 수 있습니다. 그러나 새 최적화 문제를 어떤 솔버가 가장 잘 해결할지 결정하는 것은 불가능합니다. 각 대상의 사양을 탐색하여 전략을 개발할 수 있으며, 어떤 최적화 솔버를 사용해야 하나요?문서에서 벤치마킹을 사용하여 적합한 솔버를 찾는 방법에 대한 지침을 찾을 수 있습니다.
최적화 솔루션의 경우 다음 공급자 중에서 선택할 수 있습니다.
- Microsoft QIO: 수십 년간의 양자 연구에서 영감을 얻은 최적화 문제를 다시 표현하는 여러 대상 집합입니다.
- 1QBit: 검색 기술을 사용하여 QUBO 문제를 해결하는 반복 추론 알고리즘입니다.
- Toshiba SQBM+: Toshiba Simulated Quantum Bifurcation Machine은 빠른 속도로 대규모 조합 최적화 문제를 해결하는 GPU 기반 ISING 머신입니다.
Microsoft QIO 대상
Microsoft QIO 공급자는 모든 Azure Quantum 작업 영역에서 사용하도록 설정됩니다. Microsoft QIO는 각 유형의 최적화 시나리오에 대한 다양한 대상 집합을 제공합니다.
- 병렬 템퍼링: 시스템 복사본이 서로 다른 온도에서 유지되어 템퍼링 접근 방식에서 반복된 가열 및 냉각을 자동화하는 관련 고전적 최적화 접근 방식입니다. 고전적 및 (시뮬레이션된) 양자 강화뿐 아니라 기타 많은 추론을 가속화하는 데 사용할 수 있습니다.
- 시뮬레이션된 강화: 결함을 제거하기 위해 자재의 느린 냉각을 모방(강화)하는 고전적인 확률적 시뮬레이션 방법입니다. 온도는 일정에 따라 감소합니다. 열 홉은 검색 공간에서 로컬 최솟값에서 벗어나는 경우를 지원합니다.
- 모집단 강화: 시뮬레이션된 강화는 이상적으로 항상 아래 방향으로 이동하는 워커를 시뮬레이션하고, 모집단 강화는 메트로폴리스 워커의 모집단을 시뮬레이션하여 양호한 상태에 대하여 검색 작업을 지속적으로 통합합니다.
- 양자 몬테카를로: 양자 몬테카를로 시뮬레이션을 사용하여 양자 강화 방법을 모방하는 양자 기반 최적화입니다. 시뮬레이션된 강화의 온도와 유사하게, 양자 터널링 강도는 시간이 지남에 따라 감소합니다. 양자 터널링 효과는 검색 공간에서 로컬 최솟값에서 벗어나는 경우를 지원합니다.
- 저확률 몬테카를로: 저확률 몬테카를로는 단열 양자 계산에서 영감을 얻은 확산 몬테카를로 알고리즘입니다. 이 알고리즘은 검색 공간에서 워커 모집단의 확산을 시뮬레이션하며, 워커는 비용 함수에 따라 수행하는 방법을 기반으로 제거되거나 중복됩니다.
- Tabu 검색: Tabu 검색은 인접 구성을 찾습니다. 이동성을 개선할 수 없는 경우 악화되는 이동을 허용하고 이전에 방문한 솔루션으로 이동하지 못하게 할 수 있습니다.
이는 사용 가능한 기법 중 하나일 뿐이며 Microsoft는 Azure Quantum 서비스에 대한 새로운 솔버의 개발 및 추가를 계속하고 있습니다. 자세한 내용은 Microsoft QIO 대상 목록을 참조하세요.