기술 요약: 인력 배정(Personnel Rostering)을 위한 제약 조건 보존형 QAOA

문제 정의

인력 배정은 일일 충원 요구 사항 및 연속 근무 제한과 같은 엄격한 운영 제약 조건을 특징으로 하는 조합 최적화 문제입니다. 고전적인 방법들(정수 계획법, 메타휴리스틱)이 성공을 거두어 왔으나, 시스템 규모에 따른 탐색 공간의 기하급급한 증가는 양자 알고리즘, 특히 양자 근사 최적화 알고리즘(QAOA)의 사용을 촉진합니다.

제약 조건이 있는 문제에 대한 표준 QAOA 정식화는 일반적으로 페널티 기반 접근 방식에 의존합니다. 이 프레임워크에서는 위상 해밀토니안(phase Hamiltonian)에 에너지 페널티 항을 추가하여 하드 제약 조건을 강제합니다. 이 방식은 다음과 같은 상당한 단점이 있습니다:

1. 보정 민감도: 성능이 페널티 계수의 선택에 크게 좌우됩니다.
2. 지형 왜곡: 큰 페널티는 최적화 지형을 왜곡할 수 있습니다.
3. 불가능한 상태로의 접근성: 변분 진화(variational evolution) 과정 중에 불가능한 구성(infeasible configurations)이 동적으로 접근 가능한 상태로 남아 있어, 비록 에너지가 높게 설정되어 있더라도 금지된 영역에 양자 진폭이 축적될 수 있습니다.

본 논문은 하드 제약 조건이 믹서 해밀토니안(mixer Hamiltonian)에 직접 내장되어, 양자 진화가 엄격하게 실행 가능한 부분 공간(feasible subspace) 내에 머물도록 하는 제약 조건 보존형 QAOA 프레임워크의 필요성을 다룹니다.

방법론

1. 수학적 정식화

저자들은 $N$명의 작업자와 $D$일 동안의 이진 인력 배정 문제를 정식화합니다. 상태는 이진 행렬 $q \in \{0,1\}^{N \times D}$로 표현되며, 여기서 $q_{n,d}=1$은 작업자 $n$이 $d$일에 배정되었음을 나타냅니다.
이 문제는 두 가지 하드 제약 조건을 준수하면서 할당 비용 $C(q)$를 최소화하는 것을 목표로 합니다:

• 일일 충원(Daily Coverage): $\sum_{n} q_{n,d} = W_d$ (일별 고정 인력).
• 연속 근무 금지(No-Consecutive-Duty): $q_{n,d} q_{n,d+1} = 0$ (작업자가 이틀 연속 근무할 수 없음).

구성 공간은 계층적으로 구조화됩니다:

• $\mathcal{H}$: 전체 이진 힐베르트 공간.
• $\mathcal{F}_{cov}$: 충원 제약 조건만을 만족하는 부분 공간.
• $\mathcal{F}_{full}$: 두 제약 조건을 모두 만족하는 부분 공간 (완전 실행 가능 매니폴드).

2. 믹서 구성

본 논문은 실행 가능한 섹터에 대응하는 계층적 믹서 해밀토니안을 제안합니다:

• Penalty-X (베이스라인): 표준 가로 방향 자기장 믹서($\sum X_{n,d}$)를 사용하며, 두 제약 조건을 위상 해밀토니안의 에너지 페널티를 통해 강제합니다.
• Coverage-XY: 각 일자별 작업자 수(excitation number)를 보존하는 XY 믹서를 사용합니다. 이는 $\mathcal{F}_{cov}$를 동적으로 보존하지만, 연속 근무 금지 제약 조건을 위해 여전히 페널티 항이 필요합니다.
• Guarded-XY (제안 방식): 두 제약 조건을 믹서에 직접 내장하는 **가드된 전이 연산자(guarded transition operator)**를 도입합니다.
  • 가드 메커니즘: $d$일에 작업자 $u$와 $v$ 사이의 교환이 제안될 때, 연산자는 "가드 프로젝터(guard projector)" $\hat{G}$를 포함합니다. 이 프로젝터는 인접한 날짜($d-1, d+1$)의 상태를 평가하며, 교환이 연속 근무 위반을 생성할 경우 0이 됩니다.
  • 결과: 믹서 $\hat{H}_{M}^{guard}$는 오직 $\mathcal{F}_{full}$ 내에서만 전이를 생성합니다. 결과적으로 위상 해밀토니안은 목적 함수 자체($\hat{H}_C = \hat{H}_{obj}$)로 축소되어, 하드 제약 조건 페널티 보정의 필요성을 제거합니다.

3. 도달 가능성(Reachability) 및 타이트 패턴 확장

저자들은 정확한 실행 가능성 보존이 도달 가능성(실행 가능한 그래프의 연결성)을 보장하지는 않는다는 점을 식별했습니다. "포화된(saturated)" 업무 세그먼트($W_d + W_{d+1} = N$)에서는, 연속 근무 금지 제약 조건이 상호 보완적인 할당을 강제하여 실행 가능한 그래프를 서로 분리된 구성 요소로 파편화할 수 있습니다.

• 해결책: **타이트 패턴 확장(tight-pattern extension)**이 도입됩니다. 이는 포화된 세그먼트 전반에 걸쳐 전체 교대 할당 패턴을 교환하는 집합적 교환 연산자를 추가하여, 제약을 위반하지 않으면서 $\mathcal{F}_{full}$ 내의 연결성을 복구합니다.

4. 시뮬레이션 프로토콜

본 연구는 벤치마크 인스턴스($N=4, D=4$, 작업량 $W=[2,1,2,1]$)에 대해 정밀한 상태 벡터 시뮬레이션을 사용합니다.

• 비교 대상: Penalty-X, Coverage-XY, 그리고 Guarded-XY (타이트 패턴 확장을 적용하거나 적용하지 않은 경우).
• 최적화: 기대값(Expectation-Value) 및 조건부 가치 위험(CVaR, $\alpha=0.2$) 목적 함수 하에서 평가되었습니다.
• 보정: 베이스라인 방법들의 페널티 계수는 공정한 비교를 위해 엄격하게 보정되었으나, Guarded-XY는 보정이 필요하지 않았습니다.
• 초기화: 균등 중첩(uniform superposition) 상태와 국소적 실행 가능 시작 상태를 모두 테스트했습니다.

주요 결과

1. 페널티 보정의 제거

Guarded-XY 방식은 하드 제약 조건 페널티 계수를 튜닝할 필요성을 성공적으로 제거했습니다. 위상 해밀토니안은 할당 비용만을 포함하므로 변분 지형(variational landscape)이 단순해집니다.

2. 우수한 출력 분포 품질

• 실행 가능성: Guarded-XY는 설계상 $P_{full} = 1$ (실행 가능한 상태의 확률 100%)을 유지합니다. 반면, Coverage-XY와 Penalty-X는 최적화된 페널티를 사용하더라도 실행 불가능한 영역으로 누출되는 현상($P_{full} < 1$)을 보입니다.
• 최적 집중도: CVaR 최적화 하에서, Guarded-XY는 다른 방법들에 비해 정확한 최적 스케줄을 샘플링하는 확률($P_{opt}$)이 일관되게 가장 높았습니다.
• 솔루션 품질: Guarded-XY는 가장 높은 평균 근사 비율($\langle r \rangle$)을 달립니다. 본 논문은 부분적으로 제약 조건을 보존하는 방법(Coverage-XY)이 인위적으로 낮은 원시 비용을 가진 불가능한 스케줄에 상당한 확률을 할당함으로써, 진정한 실행 가능한 최적해로부터 최적화를 왜곡하는 경향이 있다고 언급합니다.

3. 구조적 민감도 및 초기화

• 포화된 업무량: 타이트 패턴 확장은 매우 포화된 업무 시나리오에서 연결성을 유지하는 데 필수적임을 보여주며, 이를 통해 실행 가능한 그래프가 파편화되는 것을 방지합니다.
• 초기화: 몇 개의 "확산(spreading)" 믹서 레이어를 적용한다면, 단일 국소 실행 가능 스케줄에서 시작하더라도 이 프레임워크는 효과적으로 작동합니다. 이는 하드웨어 친화적인 초기화 전략을 시사합니다.
• 확장성: 다양한 큐비트 수(12, 16, 20)를 가진 인스턴스 테스트 결과, (더 큰 탐색 공간으로 인해) 원시 최적 확률은 감소할 수 있으나, 최적 상태 농축(optimal-state enrichment, $\eta_{opt}$)은 높게 유지되었습니다. 이는 알고리즘이 균등 샘플링에 비해 최적 솔루션을 일관되게 증폭시킨다는 것을 나타냅니다.

의의 및 주장

본 논문은 두 가지 하드 스케줄링 제약 조건이 믹서 해밀토니안에 직접 내장된, 인력 배정을 위한 최초의 체계적인 제약 조건 보존형 QAOA 정식화를 제시한다고 주장합니다.

주요 기여는 다음과 같습니다:

1. 제약 조건 처리의 전환: 제약 조건 강제를 에너지 위상 해밀토니안에서 동적 믹서로 이동시켜, 진화가 설계에 의해 실행 가능한 매니폴드 내에 머물도록 보장합니다.
2. 설계 원칙의 분리: 실행 가능성 보존(믹서가 실행 가능한 집합 내에 머물도록 보장)과 도달 가능성 설계(실행 가능한 집합이 연결되도록 보장)를 구분합니다. Guarded-XY 믹서는 전자를 담당하고, 타이트 패턴 확장은 후자를 담당합니다.
3. 일반화 가능성: 저자들은 전이 그래프 프레임워크와 가드된 전이 원칙이 실행 가능성을 국소적 전이 규칙으로 특징지을 수 있는 광범위한 제약 조건 최적화 양자 문제(스케줄링, 라우팅, 자원 할당 등)에 적용 가능하다고 주장합니다.

이 연구는 제약 조건 보존형 믹서가 페널티 계수 보정의 민감도 없이도, 페널티 기반 방법보다 더 높은 품질의 출력 분포와 최적 솔루션에 대한 더 강력한 집중도를 제공할 수 있음을 입증합니다.