Succinct QUBO formulations for permutation problems by sorting networks

이 논문은 비교-교환 네트워크를 활용하여 $O(n \log^2 n)$ 개의 이진 변수만으로 치환 문제를 표현하는 새로운 QUBO 형식을 제안함으로써, 기존 치환 행렬 인코딩보다 변수 수와 상호작용 밀도가 크게 감소된 효율적인 모델을 제시합니다.

핵심

1. 문제: "숫자 섞기"를 어떻게 표현할까?

우리가 1 번부터 100 번까지 번호가 붙은 카드를 섞어서 특정 순서로 나열한다고 상상해 보세요. 이를 수학적으로 표현할 때, 기존에는 **'큰 격자 (Permutation Matrix)'**를 사용했습니다.

• 기존 방식 (큰 격자): 100 개의 카드를 섞으려면 100x100 의 거대한 격자 (10,000 칸) 를 그려야 합니다. 각 칸에 "있음/없음"을 표시해야 하므로, 양자 컴퓨터가 계산해야 할 변수가 너무 많고, 서로 얽혀 있는 관계 (상호작용) 가 너무 복잡합니다. 마치 10,000 개의 전구를 동시에 켜고 끄며 조합을 찾는 것과 같습니다.

2. 해결책: "자동 정렬기 (Sorting Network)"를 이용하다

저자들은 이 문제를 해결하기 위해 **'정렬 회로 (Sorting Network)'**라는 아이디어를 차용했습니다.

• 정렬 회로란? 숫자들을 입력하면, 어떤 입력이 들어오든 상관없이 미리 정해진 규칙대로 숫자를 오름차순으로 정렬해 주는 기계입니다. 마치 공장에서 컨베이어 벨트를 타고 지나가는 물건을 자동으로 분류하는 기계와 같습니다.
• 핵심 아이디어: "순열"을 직접 표현하는 대신, **"이 순열을 정렬하면 1, 2, 3... 순서가 나오는가?"**를 검증하는 방식으로 접근했습니다.

3. 새로운 방법의 장점: "스마트한 레고"

이 논문이 제안한 새로운 방식 (QUBO) 은 다음과 같은 장점이 있습니다.

1. 변수 수의 대폭 감소 (O(n log²n)):

   • 기존 방식이 10,000 개의 변수가 필요했다면, 이 방식은 훨씬 적은 수 (약 1,000 개 수준) 만으로도 같은 일을 해냅니다.
   • 비유: 10,000 개의 레고 블록으로 성을 짓는 대신, 1,000 개의 블록으로 똑같은 성을 짓는 압축 기술을 개발한 것입니다.

2. 균일한 샘플링 (Unbiased Sampling):

   • 양자 컴퓨터는 무작위로 해답을 찾아냅니다. 기존 방식은 특정 해답이 나올 확률이 다른 해답보다 높을 수 있어 편향될 수 있었습니다.
   • 하지만 이 새로운 방식은 모든 가능한 섞임 (순열) 이 나올 확률을 정확히 동일하게 만들어줍니다. 마치 공정한 주사위를 던지는 것과 같습니다.

3. 다양한 제약 조건 추가 가능:

   • "1 번 카드는 제자리 (Fixed point) 에 있어야 한다", "짝수 순열만 고르라", "특정 카드 A 와 B 가 서로 교환되어 있으면 안 된다" 같은 복잡한 규칙도 쉽게 추가할 수 있습니다.
   • 비유: 공장에서 물건을 분류할 때, "빨간색 물건은 왼쪽으로 보내고, 파란색은 오른쪽으로 보내되, 3 번 컨베이어는 멈추게 해라" 같은 복잡한 지시도 기계가 알아듣게 프로그래밍할 수 있는 것입니다.

4. 왜 이것이 중요할까?

이 기술은 양자 컴퓨팅과 암호학, 조합 설계 분야에서 큰 의미를 가집니다.

• 암호학: 암호를 만들거나 깨는 데는 무작위성이 매우 중요합니다. 이 방법은 암호학적으로 중요한 특정 조건을 만족하는 '완벽한 무작위 섞임'을 양자 컴퓨터로 효율적으로 생성할 수 있게 해줍니다.
• 일정 계획: 스포츠 대회 일정이나 물류 배송 경로처럼 복잡한 순서 문제를 풀 때, 기존보다 훨씬 빠르고 정확하게 최적의 해답을 찾을 수 있는 길을 열어줍니다.

요약

이 논문은 **"숫자를 섞는 문제"**를 해결하기 위해, 거대한 격자 (기존 방식) 대신 **미리 설계된 정렬 기계 (Sorting Network)**를 이용해 문제를 풀었습니다. 그 결과, 양자 컴퓨터가 계산해야 할 데이터 양을 획기적으로 줄이면서도 공정한 무작위성을 보장하는 새로운 방법을 제시했습니다.

마치 **"수천 개의 전구를 끄고 켜며 조합을 찾는 대신, 몇 개의 스위치만 조작하면 원하는 모든 조합을 공평하게 얻을 수 있는 스마트한 제어판"**을 만든 것과 같습니다.

기술 요약

논문 요약: 정렬 네트워크를 이용한 치환 (Permutation) 문제의 간결한 QUBO 공식화

1. 문제 정의 (Problem)

이 논문은 이차 무제약 이진 최적화 (Quadratic Unconstrained Binary Optimization, QUBO) 문제에서 치환 (Permutation) 을 효율적으로 인코딩하는 방법을 다룹니다.

• 기존 방식의 한계: 치환을 표현하는 표준적인 방법은 '치환 행렬 (Permutation Matrix)' 인코딩 (One-hot encoding) 입니다. 이 방식은 $n$ 개의 원소에 대해 $n^2$ 개의 이진 변수 (큐비트) 가 필요하며, 각 변수가 $O(n)$ 개의 다른 변수와 상호작용하여 매우 밀집된 (dense) 상호작용 그래프를 형성합니다. 이는 양자 어닐링 장치나 QUBO 솔버에서 계산 자원을 과도하게 소모하고 확장성을 떨어뜨립니다.
• 목표: 변수의 수를 $O(n \log^2 n)$ 수준으로 줄이고, 상호작용의 밀도를 낮추며, 균일한 샘플링 (Uniform Sampling) 이 가능한 QUBO 공식을 개발하는 것입니다.

2. 방법론 (Methodology)

저자들은 무시관성 비교 - 교환 네트워크 (Oblivious Compare-Exchange Networks), 즉 정렬 네트워크 (Sorting Networks) 를 QUBO 공식화에 적용했습니다.

• 핵심 아이디어:
  • 정렬 네트워크는 입력 값에 관계없이 고정된 순서로 연산 (비교 및 교환) 을 수행하는 알고리즘입니다.
  • 이 네트워크의 각 게이트 (Gate) 의 동작을 이차 다항식 (Quadratic Polynomial) 으로 표현하고, 이를 전체 네트워크에 적용하여 치환의 관계를 정의합니다.
  • 비교 - 교환 (Compare-Exchange, CE) 게이트: 두 입력을 비교하여 큰 값을 아래로, 작은 값을 위로 정렬하는 게이트입니다. 이는 '크기 비교 (Greater Than)' 게이트와 '조건부 교환 (Controlled Swap)' 게이트의 조합으로 구현됩니다.
• 수학적 구성:
  • 게이트 표현: 각 게이트의 입력/출력 관계와 제어 비트를 만족하는 조건을 이차 다항식 (Penalty term) 으로 정의합니다. 예를 들어, $x > y$일 때만 교환이 일어나도록 하는 조건을 다항식 $g(x, y, c)$로 표현하고, 이를 0 이 되도록 최소화하는 방식으로 QUBO 를 구성합니다.
  • 균일성 (Uniformity) 보장: 각 치환은 네트워크의 제어 비트에 대한 유일한 (Unique) 변수 할당에 대응되도록 설계되었습니다. 이는 솔버가 해를 찾을 때 특정 치환이 다른 치환보다 더 높은 확률로 선택되는 편향 (Bias) 을 방지하여 균일한 샘플링을 가능하게 합니다.
  • 변수 수: $n$개의 $k$-비트 숫자를 정렬하는 네트워크 ($k \approx \log n$) 를 사용할 때, 필요한 변수의 총 수는 $O(n \log^2 n)$이며, 각 변수당 상호작용 수는 $O(\log n)$으로 매우 희소 (Sparse) 합니다.

3. 주요 기여 (Key Contributions)

1. 변수 수의 획기적 감소: 기존 $O(n^2)$에서 $O(n \log^2 n)$으로 변수 수를 줄여 대규모 치환 문제를 QUBO 로 풀 수 있는 가능성을 열었습니다.
2. 균일 샘플링 (Uniform Sampling): 각 치환이 고유한 제어 비트 설정에 대응되므로, 제약 조건이 있는 치환 집합에서 균일하게 무작위 표본을 추출할 수 있습니다.
3. 다양한 제약 조건 지원: 정렬 네트워크 프레임워크를 기반으로 다음과 같은 복잡한 제약 조건을 쉽게 추가할 수 있음을 보였습니다.
   • 고정점 (Fixed points) 및 부동점 (Derangements)
   • 치환의 순서 (Order) 및 홀짝성 (Parity)
   • 특정 치환과의 교환 가능성 (Commutativity) 및 켤레 (Conjugacy)
   • 치환의 곱셈 및 역원 연산
4. 치환 패턴 매칭 (Permutation Pattern Matching): 주어진 패턴과 일치하는 부분 수열을 찾는 NP-완전 문제를 정렬 네트워크를 통해 QUBO 로 해결하는 방법을 제시했습니다.

4. 결과 및 성능 (Results)

• 효율성: 제안된 방법은 치환 행렬 인코딩보다 변수 수와 상호작용 밀도 면에서 훨씬 효율적입니다.
• 범용성: 암호학 (S-box 설계), 조합 설계 (라틴 사각형 완성, 스포츠 토너먼트 일정), 그리고 특정 순서를 가진 치환 생성 등 다양한 분야에서 활용 가능합니다.
• 제한 사항: 그래프 이론적 문제 (예: 외판원 문제, TSP) 의 경우 정점들을 이진 문자열로 표현하면 간선 검증이 복잡해져 본 프레임워크 적용이 어렵다는 점을 인정했습니다.

5. 의의 및 중요성 (Significance)

• 양자 컴퓨팅과의 연계: QUBO 는 양자 어닐링 (Ising 모델) 과 직접적으로 연결되므로, 이 연구는 양자 컴퓨터를 사용하여 대규모 치환 문제를 효율적으로 해결할 수 있는 길을 마련했습니다.
• 편향 없는 샘플링: 기존 방법론에서는 특정 해가 더 자주 발견되거나 샘플링 편향이 발생할 수 있었으나, 이 연구는 편향 없는 (Unbiased) 샘플링을 보장하여 통계적 신뢰도를 높였습니다.
• 알고리즘과 최적화의 융합: '무시관성 알고리즘 (Oblivious Algorithms)'을 수학적 프로그래밍 (QUBO) 형식으로 변환하는 새로운 패러다임을 제시했습니다. 이는 향후 다른 알고리즘적 구조를 QUBO 로 매핑하는 데 중요한 기초가 될 것입니다.

결론적으로, 이 논문은 정렬 네트워크의 구조적 특성을 활용하여 치환 문제를 QUBO 로 변환하는 새로운 표준을 제시하며, 양자 최적화 분야에서 치환 기반 문제 해결의 실용성과 확장성을 크게 향상시켰습니다.