Quantum circuit evolutionary framework applied on set partitioning problem

본 논문은 수렴 정체성을 극복하고 고전적 최적화기의 필요성을 제거하여 집합 분할 문제를 효과적으로 해결하기 위해 가변 위상과 유사-반대단열 진화 항을 활용하는 양자 회로 진화 프레임워크를 제안한다.

핵심

거대한 복잡한 퍼즐을 풀려고 한다고 상상해 보세요. 목표는 항공기 승무원과 같은 사람 그룹을 팀으로 나누어 모든 항공편이 정확히 한 번씩만 커버되도록 하고, 중복이나 누락된 근무 시간이 없으면서 비용을 최소화하는 것입니다. 수학의 세계에서는 이를 **집합 분할 문제 (Set Partitioning Problem)**라고 부릅니다. 이는 사람과 항공편이 늘어날수록 기하급수적으로 더 어려워지는 악명 높은 난제입니다.

이 논문은 양자 컴퓨터가 이 퍼즐을 해결할 새로운 방법을 제시합니다. 대부분의 양자 알고리즘이 따르는 표준적인 '레시피' 대신, 저자들은 컴퓨터가 작업하는 동안 스스로 레시피를 진화시킬 수 있는 프레임워크를 구축했습니다.

간단한 비유를 사용하여 그들의 접근 방식을 살펴보면 다음과 같습니다:

1. 구식 방법: '고정된 설계도' (VQE)

현재의 대부분의 양자 알고리즘인 변분 양자 고유값 솔버 (VQE) 와 같은 것들은 엄격하고 변경 불가능한 레시피 책을 따르는 요리사와 비슷하게 작동합니다.

• 설정: '회로'(컴퓨터가 취하는 단계) 의 구조는 고정되어 있습니다. 재료를 추가하거나 제거할 수 없으며, 양 (매개변수) 만 조정할 수 있습니다.
• 문제: 퍼즐이 커질수록 요리사는 종종 '평평한 골짜기'에 갇히게 됩니다. 안개가 자욱한 평평한 지대에서 걷는 상황을 상상해 보세요. 어느 방향으로 걸어도 위로도 아래로도 가지 않습니다. 해법에 더 가까워지고 있는지 알 수 없습니다. 양자 물리학에서는 이를 **황무지 (Barren Plateau)**라고 부릅니다. 컴퓨터가 개선할 방향을 찾을 수 없기 때문에 학습이 멈추게 됩니다.

2. 신식 방법: '진화하는 조각가' (QCE)

저자들은 **양자 회로 진화 (Quantum Circuit Evolution, QCE)**라는 프레임워크를 제안합니다. 고정된 레시피 대신, 작은 점토 덩어리로 시작하여 매 단계마다 점토를 추가, 제거, 또는 재형성할 수 있는 조각가를 상상해 보세요.

• 작동 방식: 컴퓨터는 매우 간단한 회로 (아마도 게이트 하나) 로 시작합니다. 그런 다음 구조를 무작위로 변이시킴으로써 (새로운 단계 추가, 기존 단계 삭제, 연결 변경) 스스로의 약간 다른 버전들인 '가족'을 생성합니다.
• 선택: 컴퓨터는 이 모든 버전을 테스트합니다. 퍼즐을 가장 잘 해결하는 버전이 다음 라운드의 '부모'로 살아남고, 나머지는 폐기됩니다.
• 장점: 구조 자체가 변하기 때문에 컴퓨터는 평평한 골짜기에 갇히지 않습니다. 안개 속에서 길을 찾을 수 있도록 전체적인 접근 방식을 재형성할 수 있습니다.

3. 테스트된 두 가지 전략

논문은 이 '진화하는 조각가' 접근법의 두 가지 구체적인 변형을 테스트했습니다:

• 전략 A: 순진화론자 (Ansatz-Free)
  이 버전은 거의 아무것도 없이 시작하여 자연선택과 마찬가지로 시행착오를 통해 컴퓨터가 구조를 완전히 파악하도록 합니다. 해법이 어떻게 보여야 할지 추측하지 않고, 작동할 때까지 진화할 뿐입니다.

• 전략 B: 물리학에서 영감을 받은 진화론자 (Pseudo-Counterdiabatic)
  이것이 논문의 '스타'입니다. 저자들은 문제의 물리학에 기반한 힌트를 컴퓨터에 제공했습니다. 회로에 특별한 '밀어주기 (nudge)'인 **의사-반대단열항 (pseudo-counterdiabatic term)**을 추가했습니다.

  • 비유: 무거운 상자를 언덕 위로 밀어 올리려 한다고 상상해 보세요. '순진화론자'는 길을 찾을 때까지 무작위로 밀어 올립니다. 반면 '물리학에서 영감을 받은' 버전은 언덕의 모양을 알고 있어 상자가 평평한 곳에 갇히지 않고 부드럽게 움직이도록 유지하는 특정 반대 힘을 가합니다.
  • 결과: 이 전략이 가장 잘 수행되었습니다. 다른 방법들보다 훨씬 더 '갇힌' 느낌 (수렴 정지) 을 피했으며, 퍼즐이 매우 커졌을 때도 마찬가지였습니다.

4. 결과

저자들은 항공기 스케줄링 퍼즐의 35 가지 다른 버전을 사용하여 시뮬레이터 (양자 컴퓨터처럼 작동하는 컴퓨터 프로그램) 에서 이 방법들을 테스트했습니다.

• 승자: 물리학에서 영감을 받은 진화 방법 (APCD-QCE) 은 일관되게 표준적인 '고정된 설계도' 방법 (VQE) 보다 더 나은 해법을 찾았습니다.
• 걸림돌: 새로운 방법들이 훨씬 더 좋았지만, 퍼즐이 극도로 커질 때 (약 20 큐비트) 여전히 어려움을 겪었습니다. 진화하는 조각가조차 완벽한 해법을 찾는 데 시간이나 복잡성이 부족할 때가 있었습니다.
• 노이즈: 컴퓨터가 실수를 할 때 (실제 세계의 '노이즈'를 시뮬레이션) 어떤 일이 일어나는지도 테스트했습니다. 새로운 방법들은 성능이 떨어졌지만 이는 예상된 일이었음에도 불구하고 reasonably 잘 견뎌냈습니다.

결론

이 논문은 양자 회로가 단순히 설정을 조정하는 대신 자신의 모양을 변경하게 함으로써 현재 알고리즘을 가두는 '막다른 길'을 피할 수 있다고 주장합니다. 구체적으로, 이 진화 과정에 물리학 기반의 '밀어주기'를 추가하면 컴퓨터가 더 나은 해법을 더 빠르게 찾을 수 있습니다.

이것이 아직 모든 문제 (특히 가장 거대한 문제들) 를 해결하는 것은 아니지만, 스케줄링 및 자원 관리와 같은 복잡한 최적화 문제를 해결하기 위해 양자 컴퓨터를 사용하는 유망한 새로운 길을 제시하며, 최적화의 중추적인 작업을 고전 컴퓨터가 수행할 필요성을 우회할 가능성을 열어줍니다.

기술 요약

기술 요약: 양자 회로 진화 프레임워크를 집합 분할 문제에 적용한 연구

문제 정의
본 논문은 잘 알려진 NP-완전 조합 최적화 문제인 집합 분할 문제 (SPP) 를 다룹니다. SPP 는 모든 요소가 정확히 하나의 부분집합에 속하도록 보장하면서 총 가중치를 최소화하기 위해 요소 집합을 상호 배타적이고 완전한 부분집합으로 분할하는 것을 포함합니다. 실제 응용 사례에는 항공기 승무원 스케줄링이 포함됩니다. 양자 하드웨어에서 이를 해결하기 위해 저자들은 SPP 를 2 차 무제약 이진 최적화 (QUBO) 문제로 공식화했으며, 이는 이후 아이징 해밀토니안 (Ising Hamiltonian) 으로 매핑됩니다. 본 연구는 특히 양자 비트 수가 증가함에 따라 기울기가 지수적으로 소멸하여 수렴 정체를 초래하는 '황량한 평야 (barren plateaus)' 현상으로 종종 고통받는 변분 양자 알고리즘 (VQA), 예를 들어 변분 양자 고유 솔버 (VQE) 의 한계를 대상으로 합니다.

방법론
저자들은 표준 VQE 접근법과 구별되는 양자 회로 진화 (QCE) 프레임워크를 제안합니다. 가변 파라미터를 고전 최적화 알고리즘으로 최적화하는 고정된 회로 토폴로지 (안사츠) 를 사용하는 VQE 와 달리, QCE 프레임워크는 회로 토폴로지 자체를 진화시킵니다. 본 연구는 이 프레임워크 내에서 두 가지 서로 다른 전략을 평가합니다:

1. 안사츠 없는 양자 회로 진화 (AF-QCE):

   • 이전 문헌 [13] 에서 영감을 받은 이 접근법은 최소 회로 (단일 무작위 게이트) 로 시작하여 사전 정의된 안사츠 없이 반복적으로 진화합니다.
   • 진화는 INSERT(게이트 추가), DELETE(게이트 제거), SWAP(게이트 교체), MODIFY(게이트 파라미터 조정) 와 같은 돌연변이 연산에 의존합니다.
   • 회로 군집이 생성되고 측정된 후, 가장 성능이 좋은 회로가 다음 세대의 부모로 선택되어 비용 함수의 단조 감소를 보장합니다.

2. 의사-반대 단열 진화 항이 포함된 안사츠 (APCD-QCE):

   • 이 접근법은 수렴성을 개선하기 위해 물리학에서 영감을 받은 구조를 안사츠에 통합합니다. 이는 $H_T(\lambda) = H_{ad}(\lambda) + H_{pcd}(\lambda)$ 형태의 해밀토니안을 사용하는데, 여기서 $H_{ad}$는 단열 시간 진화 해밀토니안을 나타내고 $H_{pcd}$는 의사-반대 단열 진화 항입니다.
   • 유니타리 연산자는 $U = U_{ad}U_{pcd}$로 정의됩니다. $U_{ad}$ 성분은 고정되어 있습니다 (하나의 트로터 단계). 반면 $U_{pcd}$는 AF-QCE 와 동일한 진화 돌연변이 전략을 사용하여 진화됩니다.
   • 초기 상태 준비는 $|+\rangle^{\otimes n}$을 사용하며, 힐베르트 공간의 탐색을 용이하게 하기 위해 특정 파라미터 설정 ($\beta=0, \delta=0.5$) 이 적용됩니다.

실험 설정
실험은 Qiskit 라이브러리를 사용하여 두 가지 시나리오 하에서 고성능 시뮬레이터 (KUATOMU) 에서 수행되었습니다:

• 무잡음: 6 개에서 20 개 양자 비트까지 범위를 갖는 SPP 의 35 개 인스턴스가 테스트되었습니다.
• 잡음: NISQ 장치의 한계를 모방하기 위해 특정 양자 비트에 탈분극 오류 채널 ($\epsilon = 0.01$) 이 포함된 시뮬레이션이 수행되었습니다.
• 비교: QCE 전략은 표준 VQE(2 국소 선형 얽힘 안사츠 및 COBYLA 최적화기를 사용) 에 대해 벤치마크되었습니다.
• 지표: 성능은 고전적 참조 값 (Gurobi 솔버) 과 양자 알고리즘이 찾은 최소 기대값의 비율로 정의된 **근사 비율 ($R$)**을 사용하여 측정되었습니다.

주요 결과

• VQE 대비 우위: 무잡음 시나리오에서 AF-QCE 와 APCD-QCE 모두 VQE 를 크게 능가했습니다. VQE 는 양자 비트 수가 증가함에 따라 성능이 급격히 저하되어 (보통 10 개 이상의 양자 비트 인스턴스에서 수렴에 실패함) 진화 접근법들이 더 나은 성능을 유지한 반면, VQE 는 성능이 떨어졌습니다.
• APCD-QCE 성능: APCD-QCE 전략은 가장 견고한 결과를 보여주었으며, 35 개 인스턴스 중 25 개에서 1.00(최적) 의 근사 비율을 달성했습니다. 이는 VQE 와 AF-QCE 가 어려움을 겪었던 대부분의 경우에서 수렴 정체를 효과적으로 피했습니다.
• 확장성 한계: 개선에도 불구하고 확장성 과제는 지속되었습니다. 20 개 양자 비트 인스턴스 (특히 20.1, 20.6, 20.7) 의 경우 APCD-QCE 를 포함한 모든 방법이 수렴 정체의 징후를 보였으며, 근사 비율이 크게 하락했습니다.
• 잡음 영향: 잡음 시뮬레이션에서는 모든 알고리즘의 성능이 저하되었으며, 특히 작은 인스턴스에서 두드러졌습니다. 그러나 QCE 프레임워크는 일반적으로 VQE 대비 동등하거나 더 나은 성능을 유지했습니다.

의의 및 주장
본 논문은 제안된 QCE 프레임워크가 정수 최적화 문제에 대한 고정 안사츠 변분 알고리즘에 대한 유망한 대안을 제공한다고 주장합니다. 주요 기여점은 다음과 같습니다:

• 정체 완화: 프레임워크, 특히 APCD-QCE 변형은 표준 VQA 의 황량한 평야와 관련된 수렴 정체를 피하는 놀라운 능력을 보여줍니다.
• 고전 최적화기의 제거: 회로 토폴로지를 직접 진화시킴으로써 파라미터를 조정하기 위한 COBYLA 와 같은 고전 최적화기의 필요성을 우회하여 현재 VQA 워크플로우의 병목 현상을 해결합니다.
• 확장성으로의 길: 20 개 양자 비트 정체에 대한 완전한 해결책은 아니지만, 결과는 가변 토폴로지 회로가 대규모 최적화 문제를 해결하기 위한 "흥미로운 경로"를 제공함을 시사합니다. 저자들은 APCD-QCE 전략이 충분한 수의 세대가 주어지면 수렴 정체 효과에 "거무 면역"이라고 언급하지만, 돌연변이 공간에서의 국소 최소값 탈출은 여전히 과제로 남아 있습니다.

저자들은 양자 비트 수가 증가함에 따라 확장성 장애물에 직면하고 있지만, 물리학에서 영감을 받은 항 (의사-반대 단열) 을 진화 회로 검색에 통합하는 것이 NISQ 장치에서 조합 문제를 해결하기 위해 고무적인 결과를 낳았다고 결론지었습니다.