양자 최적화

QuEra의 256큐비트 양자 컴퓨터는 다양한 산업과 관련된 특정 최적화 문제를 해결할 수 있습니다. 하드웨어에 자연스럽게 매핑되는 최적화 문제 중 하나는 최대 독립 집합 문제(MIS)입니다. 그래프의 최대 독립 집합은 어떤 정점도 연결되지 않은(예: 가장자리를 공유하는) 정점의 가능한 최대 하위 집합입니다. 이러한 집합을 구하는 것은 NP-어려운 문제입니다. 일반적인 그래프의 경우, 근사 해법조차도 기존 알고리즘으로는 효율적인 분석이 불가능할 수 있습니다. 매장 위치 최적화와 같은 많은 산업 문제를 MIS 문제로 공식화할 수 있습니다( 이 애플리케이션 노트 참조).

다양한 최적화 문제 인코딩

MIS에 대한 솔루션은 여기에 설명된 것처럼 다른 관련 최적화 문제의 해결책을 제시할 수 있습니다. 양자 샘플링, 양자 메모리 인코딩, 양자 머신 러닝, 양자 단열 알고리즘(QAA) 및 양자 근사 최적화 알고리즘(QAOA)과 같은 변형 최적화 등 다양한 알고리즘 기술을 사용하여 다양한 문제를 해결할 수 있습니다:

안테나 배치

최소 버텍스 커버리지

최소 지배 집합

그래프 색상 지정

가중 그래프의 가중 최대 독립 집합은 아날로그 중성 원자 양자 컴퓨터에서도 특정 원자에 대한 에너지를 다른 원자보다 증가시킴으로써 인코딩할 수 있습니다. 여기에 설명된 바와 같이, 이로 인해 다음과 같은 최적화 문제가 추가로 발생합니다.

이차 제약 조건 없는 이진 최적화(QUBO)

정수 인수분해

이러한 문제는 영리한 인코딩을 통해 더 큰 그래프에서 MIS 문제로 변환할 수 있으며, 큐비트 수에 따라 최대 4제곱으로 확장할 수 있습니다.

중성 원자 배열로 양자 컴퓨터 구축하기

최대 독립 집합 찾기

리드버그 봉쇄 효과는 가깝게 위치한 두 개의 중성 원자가 동시에 리드버그 상태로 여기될 때 발생하는 양자 현상입니다. 이 효과는 원자 중 하나만 여기 상태에 도달할 수 있게 하며, 그래프의 최대 독립 집합(MIS)을 찾는 데 활용할 수 있습니다. 이 과정에는 그래프를 중성 원자의 배열로 인코딩하는 작업이 포함됩니다. 인코딩은 그래프에서 가장자리를 공유하는 두 개의 정점이 서로의 리드버그 봉쇄 반경 내에 있는 두 원자에 해당하는 방식으로 이루어집니다. 시스템의 총 에너지를 최대 원자 수를 여기시킬 수 있을 만큼 높은 수준으로 올리면 전체 시스템 상태는 최대 독립 집합에 해당합니다. 그런 다음 여기 여부에 관계없이 원자의 상태를 측정하여 솔루션을 결정합니다. 여기된 원자 그룹은 MIS를 나타냅니다.

이미지 A: 리드버그 봉쇄에 의해 제약을 받는 최대 여기 원자 집합

이미지 B: 빨간색으로 강조 표시된 부분: 그래프의 최대 독립 집합(정점의 최대 하위 집합으로, 어떤 정점도 가장자리를 공유하지 않음).

효율적인 솔루션

중립 원자 프로세서에서 MIS 문제를 해결하는 것은 원자의 자연스러운 동작을 이용하기 때문에 최소한의 오버헤드만 필요합니다. 관심 그래프가 단위 디스크 그래프(UDG)인 경우, 256개의 큐비트에서 256개의 변수를 사용해 MIS 문제를 인코딩할 수 있습니다. 특정 그래프의 경우 아날로그 중립 원자 프로세서는 MIS를 효율적으로 찾을 수 있습니다. 최적화 문제를 푸는 표준 알고리즘인 고전적인 시뮬레이션 어닐링과 비교해보면, 중립 원자 프로세서는 정확하게 정의된 그래프 집합의 경우 문제 크기에 따라 더 유리하게 확장된다는 것을 알 수 있습니다. 성능에 대해 자세히 알아보려면 이 결과 보고서 또는 이 블로그 게시물을 읽어보세요.

MIS의 산업 응용 분야

안테나 배치
(최대 독립 세트)

통신 서비스의 커버리지를 극대화하려면 특정 지역 내에 안테나를 고밀도로 배치해야 합니다. 그러나 신호 간섭으로 인해 커버리지 영역이 겹치지 않아야 하고 안테나 간 최소 거리 규정이 정부 기관에 의해 부과되는 경우가 많기 때문에 이러한 목표를 달성하는 데 어려움이 있습니다. 모든 잠재적 위치 사이트 중에서 최적의 안테나 배치는 두 개의 커버리지 영역이 교차하지 않는 최대 독립 세트에 해당합니다. 이 문제는 각 안테나에 부착된 '가중치'를 최대화함으로써 확장할 수 있는데, 이는 전체 서비스 지역 또는 서비스 대상 고객 수와 같은 변수를 나타낼 수 있습니다. 이러한 원칙은 IoT 애플리케이션을 위한 센서 배치나 매장 또는 유통 센터의 전략적 위치를 위한 설치 공간 최적화 등 관련 문제에도 적용할 수 있습니다.

포트폴리오 최적화(최대 파벌)

In the financial industry, optimizing portfolios of assets, such as stocks or bonds, can enhance returns. Generally, Maximum Independent Sets (MISs) and their complement, maximum cliques, are valuable for deriving nontrivial insights into the correlation properties of large datasets. This information can guide strategies for hedging and diversification. One can construct a 'market graph,' where stocks correspond to vertices and vertices are connected when their correlations, θ_ij, exceed a threshold, Θ. For instance, setting θ_ij<Θ<0 and searching for graph cliques generates collections of mutually anti-correlated assets, maximizing returns while minimizing risk. Conversely, cliques obeying the limit θ_ij>Θ>0 generate portfolios of positively-correlated assets whose prices move in tandem, as might occur for assets within the same market.

5G 네트워크(최소 지배 세트)

5G 아키텍처는 휴대폰 또는 네트워크에 연결된 자동차 간과 같은 디바이스 간(D2D) 통신 네트워크에 점점 더 많이 활용되고 있습니다. 이는 특히 혼잡한 콘서트나 혼잡한 고속도로 교통 상황과 같은 시나리오와 관련이 있습니다. 이러한 네트워크의 노드는 인접한 자율 주행 차량이 정보를 교환할 때처럼 Bluetooth와 같은 단거리 프로토콜을 사용하여 서로 통신할 수 있습니다. 또는 콘서트 참석자들이 사진을 업로드할 때처럼 더 넓은 무선 기지국 네트워크에 연결할 수도 있습니다.
그러나 모든 노드를 더 넓은 기지국 네트워크에 연결하면 잠재적으로 과부하가 발생할 수 있습니다. 이 문제를 완화하기 위해 노드의 하위 집합을 게이트웨이 노드로 선택하고 이 노드만 셀 네트워크에 연결할 수 있습니다. 그러면 해당 지역의 다른 모든 노드는 범위 내 게이트웨이 노드에 직접 연결하여 더 넓은 인터넷에 연결할 수 있으므로 셀 타워 대역폭을 관리 가능한 수준으로 줄일 수 있습니다.