Symmetry-based quantum algorithms for open-shop scheduling with hard constraints

본 논문은 양자 컴퓨팅을 위한 오픈-샵 스케줄링 문제에서 하드 제약 조건을 인코딩하기 위해 대칭성 기반 접근법을 제시하며, 이차 수의 파라미터만 최적화함으로써 확률적으로 최적 해에 도달함을 보장하는 가용성 보존 치환군을 활용하는 새로운 변분 알고리즘을 제안한다.

핵심

다음은 연구 논문에 대한 설명을 창의적인 비유를 곁들여 쉬운 언어로 번역한 것입니다.

큰 그림: 양자 퍼즐 상자

배송 트럭 대대의 일정을 잡으려는 물류 관리자가 되어 상상해 보세요. 당신은 작업 목록 (배송), 기계 세트 (트럭), 그리고 시간표 (시간대) 를 가지고 있습니다. 규칙은 엄격합니다:

1. 모든 작업은 정확히 한 번만 수행되어야 합니다.
2. 어떤 트럭도 한 번에 두 곳에 있을 수 없습니다.
3. 어떤 시간대에도 두 개의 작업이 할당될 수 없습니다.

이것을 **오픈샵 스케줄링 문제 (OSSP)**라고 합니다. 이는 고전적인 "어려운" 퍼즐입니다. 일반 컴퓨터로 해결하려 하면 잘못된 조합이 너무 많아 확인하는 데 영원히 걸릴 수 있습니다.

이 논문의 저자들은 이렇게 질문했습니다: 양자 컴퓨터를 사용하면 이를 더 빠르게 해결할 수 있을까요?

문제는 현재의 양자 컴퓨터가 어설픈 유아와 같다는 점입니다. 그들은 실수를 쉽게 합니다. 단순히 "최고의 일정을 찾아라"라고 요청하면, 그들은 종종 "금지 구역" (한 트럭에 동시에 두 개의 작업을 할당하는 등 규칙을 위반하는 일정) 으로 헤매게 됩니다.

이 팀의 해결책은 안전한 길만 걷는 법을 아는 양자 로봇을 만드는 것입니다. 그들은 컴퓨터가 불법적인 일정을 고려하는 것을 물리적으로 방지하는 새로운 알고리즘을 설계했습니다.

---

핵심 아이디어: "대칭성" 열쇠

그들의 비법을 이해하려면 가능한 일정들로 가득 찬 방을 상상해 보세요.

• 나쁜 일정: 규칙을 위반하는 잘못된 위치에 서 있는 사람들.
• 좋은 일정: 올바른 위치에 서 있는 사람들.

대부분의 양자 알고리즘은 "나쁜" 사람들을 벌금 (과태료) 과 같은 무거운 페널티를 주어 방에서 밀어내려 합니다. 하지만 이는 messy 합니다. 나쁜 사람들이 여전히 머무를 수도 있고, 페널티가 충분히 강력하지 않을 수도 있습니다.

저자들의 접근법:
나쁜 사람들을 처벌하는 대신, 그들은 "좋은 일정"이 숨겨진 대칭성을 가지고 있다는 사실을 깨달았습니다.
작업을 댄서로, 시간대를 춤 파트너로 생각하세요. 완벽한 춤 루틴 (유효한 일정) 이 있다면, 파트너를 특정 방식으로 바꾸어도 여전히 완벽한 루틴을 유지할 수 있습니다.

저자들은 규칙을 깨뜨리지 않고 작업을 어떻게 섞을 수 있는지를 정확히 설명하는 수학적 "군 (group, 규칙의 집합)"을 발견했습니다. 그들은 이를 **가능성 유지 군 (Feasibility-Preserving Group)**이라고 부릅니다.

비유:
루비크의 큐브를 상상해 보세요.

• 표준 접근법: 이미 고친 색상을 망치지 않기를 바라며 무작위로 면을 비틀어 해결하려 합니다.
• 이 논문의 접근법: 큐브를 사전에 승인된 특정 방식 (대칭성) 으로만 비튼다면, 색상이 여전히 정렬된 상태를 유지할 것이 보장된다는 사실을 깨닫습니다. 당신의 움직임이 수학적으로 설계되어 큐브가 풀리지 않도록 하므로, 큐브를 "망가뜨릴" 걱정을 할 필요가 없습니다.

새로운 알고리즘: "셔플" 기계

이 논문은 이러한 대칭성을 사용하는 새로운 유형의 양자 알고리즘 (변분 양자 알고리즘) 을 제안합니다.

1. 안전하게 시작: 하나의 유효한 일정 (시드 솔루션) 으로 컴퓨터를 시작합니다.
2. 믹서: 무작위 잡음 대신 컴퓨터는 특수한 "믹서" 게이트를 적용합니다. 이 게이트는 일정을 수학적으로 유효하게 유지하는 방식으로만 작업을 교환하는 셔플 버튼과 같습니다.
3. 보장: 저자들은 매우 강력한 수학적 사실을 증명했습니다: $J$개의 작업이 있다면, 절대적인 최선의 것을 포함한 모든 가능한 유효한 일정에 도달하기 위해 조정해야 하는 특정하고 관리 가능한 수의 "노브" (매개변수) 만 있으면 됩니다.

"노브" 비유:
조합 잠금이 달린 거대한 금고가 있다고 상상해 보세요.

• 구식 양자 방법: 수십억 개의 무작위 숫자를 시도하며 조합을 추측해야 합니다. 운이 좋을 수도 있지만, 막다른 길에 갇힐 수도 있습니다.
• 이 방법: 저자들은 지도를 찾았습니다. 그들은 $J^3$ (작업 수의 대략적인 세제곱) 개의 특정 노브만 돌리면 금고의 모든 문에 도달할 수 있음을 증명했습니다. 올바른 순서로 올바른 다이얼만 돌리면 모든 문을 열 수 있는 마스터 키를 가진 것과 같습니다.

그들이 실제로 한 일 (증명)

이 논문은 이론만 이야기하는 것이 아니라 실제로 테스트했습니다.

1. 시뮬레이션: 그들은 고전 컴퓨터에서 문제의 작은 버전 (작업 4 개, 기계 2 대) 을 시뮬레이션했습니다.

   • 결과: 나쁜 일정에 "벌금"을 부과하는 기존 방법은 좋은 해결책을 찾지 못했습니다. 그들은 "금지 구역"에 갇혔습니다.
   • 결과: "안전한 길"에 엄격하게 머무는 그들의 새로운 방법은 빠르게 완벽한 해결책을 찾았습니다.

2. 실제 하드웨어 테스트: 그들은 문제의 아주 작은 버전 (작업 3 개, 기계 1 대—본질적으로 외판원 문제) 을 가져와 실제 양자 컴퓨터 (IBM Q System One) 에서 실행했습니다.

   • 결과: 실제 컴퓨터에 잡음 (정지 소음이 있는 라디오와 같은) 이 있었음에도 불구하고, 그들의 알고리즘은 무작위 확률보다 더 자주 최선의 해결책을 찾았습니다. 이는 불완전한 하드웨어에서도 "안전한 길" 논리가 작동함을 보여주었습니다.

결론

이 논문은 양자 컴퓨터를 위한 가드레일을 구축하는 것에 관한 것입니다.

컴퓨터가 도로에 머물기를 바라는 대신, 그들은 차가 도로를 벗어날 수 없도록 재설계했습니다. 스케줄링 문제의 수학적 대칭성을 사용하여 그들은 다음과 같은 알고리즘을 만들었습니다:

• 불가능한 일정을 결코 고려하지 않습니다.
• 특정하고 제한된 수의 노브를 돌림으로써 완벽한 해결책에 도달할 수 있습니다.
• 오늘날의 잡음이 많고 불완전한 양자 기계에서도 기존 방법보다 더 잘 작동합니다.

그들은 아직 전 세계 모든 산업의 문제를 해결한 것은 아니지만, 이 특정 유형의 스케줄링 퍼즐을 해결하기 위한 더 신뢰할 수 있는 새로운 엔진을 구축했습니다.

기술 요약

기술적 요약: 하드 제약 조건을 가진 오픈-샵 스케줄링을 위한 대칭성 기반 양자 알고리즘

문제 정의
본 논문은 $J$개의 작업이 각각 $T$개의 시간 슬롯을 가진 $M$대의 기계에 분배되어야 하는 조합 최적화 문제인 오픈-샵 스케줄링 문제 (OSSP) 를 다룬다. 제약 조건은 모든 작업이 정확히 한 번 수행되어야 하며, 어떤 기계 - 시간 슬롯에도 최대 하나의 작업만 할당되어야 한다는 것이다. 이 문제는 $TSP = OSSP(1, T, T)$인 외판원 문제 (TSP) 의 일반화이다.

핵심적인 어려움은 이러한 "하드 제약 조건"을 변분 양자 알고리즘 (VQA) 에 인코딩하는 데 있다. 제약 조건이 없는 문제 (예: MAX-CUT) 나 "소프트 코딩"된 제약 조건을 가진 문제 (비실현 가능성을 목적 함수에 페널티로 부과) 와 달리, OSSP 는 최적화가 실현 가능 부분 공간 (feasible subspace) 내에 엄격하게 머무르도록 요구한다. 소프트 코딩은 종종 비최적의 최적화 지형이나 실현 가능성 문제를 초래한다. 양자 교대 연산자 Ansatz(QAOA) 는 실현 가능성 보존 믹서를 통해 하드 제약 조건을 위한 프레임워크를 제공하지만, 스케줄링 문제에 대한 기존 구성은 종종 휴리스틱적이어서 문제의 근본적인 대칭성 구조를 완전히 활용하지 못한다.

방법론
저자들은 OSSP 의 실현 가능성 구조를 분석하기 위해 엄밀한 군론적 접근법과 그래프 이론을 결합한다:

1. 제약 조건 그래프 모델: 문제는 잠재적인 작업 할당 (비트) 을 정점으로, 동시 할당을 금지하는 제약 조건을 간선으로 하는 제약 조건 그래프 $G=(V, E)$로 매핑된다. 해는 크기 $J$인 독립 집합 (코클라이크) 에 해당한다.
2. 실현 가능성 보존 군 ($F$): 저자들은 실현 가능한 해를 다른 실현 가능한 해로 매핑하는 비트 값 치환의 군 $F$를 식별한다. 그들은 OSSP 에 대해 이 군이 제약 조건 그래프의 자기동형군 $\text{Aut}(G)$와 동형임을 증명한다.
   • "바쁜" 경우 ($MT = J$) 에는 군 구조가 대칭군을 포함하는 wreath product 이다.
   • 결정적으로, 그들은 $F$가 모든 실현 가능한 해의 집합에 대해 **추이적 (transitively)**으로 작용함을 보인다. 이는 어떤 실현 가능한 해든 $F$ 내의 치환 시퀀스를 통해 다른 어떤 해로든 변환될 수 있음을 의미한다.
3. 알고리즘 설계:
   • QAOA 확장: 그들은 $F$의 생성자로부터 직접 믹서를 구성함으로써 QAOA 프레임워크를 정교화한다. $F$가 추이적으로 작용하므로, 그 요소들에서 유도된 믹서는 전체 실현 가능 부분 공간에 접근할 수 있음을 보장한다.
   • 새로운 VQA (양자 군 최적화): 바쁜 OSSP 인스턴스의 경우, 저자들은 표준 위상 분리기를 우회하는 새로운 알고리즘을 제안한다. 바쁜 OSSP 의 해 공간을 나타내는 대칭군 $S_J$ 내의 치환을 전치 (transpositions) 의 곱으로 분해하여 SWAP 게이트를 사용한 매개변수화 회로를 구성한다.
   • 매개변수화: 알고리즘은 치환을 $J(J-1)/2$개의 전치로 분해하는 특정 방식을 활용한다. 각 전치는 작업 블록 전체에 걸친 불연속 SWAP 게이트의 곱으로 구현된다.

주요 기여

• 이론적 특성화: 본 논문은 OSSP 에 대한 실현 가능성 보존 군에 대한 완전한 특성화를 제공하여, 그것이 제약 조건 그래프의 자기동형군과 동형임을 증명하고 해 집합에 대한 그 추이적 작용을 확립한다.
• 보장된 도달성: 무한한 회로 깊이 ($p \to \infty$) 의 극한에서만 최적해 도달이 보장되는 일반 QAOA 와 달리, 제안된 VQA 는 매개변수에 대한 엄격한 상한을 제공한다. 저자들은 $O(J^3)$(구체적으로 $J(J-1)/2$) 개의 매개변수가 전역 최적해를 포함한 어떤 실현 가능한 해에도 확실히 도달하기에 충분함을 증명한다.
• 하드 제약 조건 구현: 이 연구는 소프트 코딩 제약 조건의 함정을 피하면서 실현 가능 부분 공간을 엄격하게 보존하는 믹서를 체계적으로 구성하는 방법을 보여준다.
• 하드웨어 구현: 저자들은 $OSSP(1, 3, 3)$인스턴스 (3 도시 TSP 와 동등) 에 대해 실제 양자 장치 (IBM Q System One) 에서 알고리즘을 구현하고, $OSSP(2, 2, 4)$인스턴스에 대해 잡음 없는 시뮬레이션을 수행했다.

결과

• 잡음 없는 시뮬레이션 ($OSSP(2, 2, 4)$): 하드코딩된 제약 조건을 가진 제안된 VQA 는 6 회 반복 (12 개 매개변수 최적화) 내에 전역 최소값 (근사 비율 100%) 에 성공적으로 도달했다. 반면, 소프트 코딩된 제약 조건을 가진 표준 QAOA 는 작은 실현 가능 부분 공간에 진폭을 집중시키는 어려움으로 인해 모든 18 개 매개변수에 접근하더라도 근사 비율이 30% 를 초과하지 못했다.
• 실제 하드웨어 ($OSSP(1, 3, 3)$): IBM Q System One 에서 알고리즘은 초기 상태를 벗어나 지역 최적점과의 중첩을 증가시키는 능력을 보였다. 그러나 저자들은 하드웨어 잡음이 전역 최적점으로의 수렴을 크게 흐리게 하여 잡음 배경이 신호를 지배했다고 지적한다. 고전적 잡음 시뮬레이션이 더 나은 수렴을 보였으므로, 알고리즘 설계보다는 현재 하드웨어의 한계 (결맞음 시간, 게이트 충실도) 가 주요 병목 현상임을 시사한다.

의의 및 주장
본 논문은 휴리스틱 믹서 설계를 넘어, VQA 에서 하드코딩된 제약을 위한 체계적이고 대칭성 기반의 프레임워크를 제공한다는 데 주요한 의의가 있다고 주장한다. 문제의 실현 가능성 구조를 그래프 자기동형과 연결함으로써, 저자들은 다항식 개수의 매개변수 ($O(J^3)$) 가 전체 해 공간을 탐색하기에 충분하다는 이론적 보장을 가진 알고리즘을 유도한다.

저자들은 실용적인 확장성에 대해 겸손한 태도를 보인다. 이론적 매개변수 상한이 강력하지만, 이러한 매개변수의 실용적 최적화는 "황량한 고원 (barren plateaus)"과 고차원 공간에서의 지수적으로 많은 지역 최소값으로 인해 방해받음을 인정한다. 또한, 그들은 명시적으로 그들의 접근 방식이 등식 제약 조건 (대칭성) 에 의존하며, 그러한 대칭성이 부재한 부등식 제약 조건 (예: 배낭 문제) 을 가진 문제에는 직접 적용되지 않을 수 있다고 밝힌다. 이 연구는 향후 하드웨어 개선이 잡음과 연결성 문제를 해결한다면, 스케줄링 문제를 위해 더 효율적이고 이론적으로 근거 있는 양자 알고리즘을 설계하기 위해 실현 가능성 보존 군 구조를 활용할 수 있음을 보여주는 원리 증명 (proof of principle) 역할을 한다.