Matrix-Free GPU Semidefinite Programming for Quantum Ordered Search at the k=6 Frontier

Motivation

• Known: Childs et al. (2007)는 k-query 양자 순서 탐색 알고리즘의 존재성이 특정 구조화된 SDP의 feasibility와 동치임을 보였고, k=4에서 N=605를 완전히 해결했으며, Carolan et al. (2025)는 LP relaxation으로 k=5에서 N=7265, c≈0.390을 달성했다. 또한 cuLoRADS 등 low-rank factorization 기반 GPU SDP solver가 k≤5까지는 효과적으로 작동함이 알려져 있다.
• Gap: k=6로 넘어가면 예상되는 N*가 10^5 규모여서, low-rank factorization으로 변수 수는 줄일 수 있어도 SDP 제약 행렬 A를 명시적으로(희소 형태라도) 구성·저장하는 기존 solver들은 GPU 메모리 한계에 부딪혀 memory wall에 도달하므로, k=6 문제는 기존 CPU/GPU solver로는 계산적으로 불가능하다.
• Why: 양자 알고리즘의 constant-factor speedup을 정량화하는 query coefficient c의 상한을 실제로 개선하는 것은 양자 질의 복잡도 이론의 핵심 미해결 문제이며, 이 논문은 이론적 한계를 실제로 갱신함과 동시에 대규모 구조화 SDP를 GPU에서 matrix-free로 푸는 일반적 방법론을 제시해 과학계산 전반의 SDP 응용으로 확장 가능성을 연다.
• Approach: OSP SDP의 고도로 구조화된(Toeplitz/Laurent polynomial 기반) 제약을 활용해, 제약 연산자를 커스텀 CUDA 커널로 즉석 평가하는 domain-aware matrix-free Augmented Lagrangian Method(ALM)를 설계함으로써, 메모리 복잡도를 quadratic에서 linear로 낮추고 병목을 메모리에서 연산량으로 전환했다.

Achievement

Figure 5. Empirical Phase Transition (k ≤5). The green curves (N ⋆) show rapid convergence to high precision, while the

1. k=6 프론티어 해결: 단일 GPU 상에서 k=6의 OSP SDP를 풀어 최적 리스트 크기를 90,000 ≤ N* < 94,000로 좁혔다.
2. query coefficient 개선: 경험적 하한 증거를 바탕으로 query complexity 상한 계수를 기존 0.390에서 0.365로 개선했다.
3. 엄밀한 dual infeasibility 인증: N=94,000에서의 infeasibility를 spectral shifting을 통한 matrix-free 최소 고유값 추정으로 dual infeasibility certificate를 구성해, floating-point 연산에도 불구하고 수학적으로 엄밀하게 증명했다.
4. 범용 matrix-free GPU SDP 프레임워크: 제약 행렬을 전혀 명시적으로 저장하지 않는 GPU 가속 ALM solver를 제시하여, 계산 병목을 메모리 대역폭에서 연산 처리량으로 이동시켰다.

How

Figure 1. Structure-Aware Parallel Mapping. Top: The operator

• OSP SDP의 제약(Toeplitz 구조의 Tt 연산자)을 명시적 행렬 A 없이 구조 인지(structure-aware) 방식으로 병렬 매핑하여 GPU 상에서 평가
• 제약 연산의 dense matrix 곱을 구조적 합성(structural synthesis)으로 분해해 메모리 사용량을 quadratic에서 linear로 축소
• 병렬 평가(parallel evaluation) 커널을 통해 T*와 관련된 곱 연산을 on-the-fly로 계산, 메모리 대신 연산이 병목이 되도록 재설계
• Augmented Lagrangian Method 기반 1차 최적화로 대규모 문제를 처리하고, 저정밀 수치해로부터 dual infeasibility 인증을 위해 spectral shifting 기반 matrix-free 최소 고유값 추정 수행

Originality

• SDP 제약 행렬을 전혀 구체화하지 않는 matrix-free 접근을 특정 문제(OSP)의 고유한 Toeplitz/Laurent polynomial 구조에 특화된 CUDA 커널로 구현한 점이 기존 범용 저랭크(low-rank) GPU SDP solver(cuLoRADS 등)와 차별화됨
• 단순 수치적 상한 개선에 그치지 않고 floating-point 연산 기반 결과를 dual infeasibility certificate로 엄밀하게 증명 가능하도록 spectral shifting 기법을 결합한 점
• 양자 알고리즘 이론(quantum query complexity)과 대규모 최적화(GPU 가속 conic solver)를 실질적으로 연결해 30년 가까이 정체된 OSP 상한 개선 문제에 실질적 진전을 이룸

Limitation & Further Study

• k=6에서의 결과가 여전히 하한(N ≥ 90,000)은 수치적 증거에 의존하며, 완전한 엄밀 증명은 상한(N < 94,000)에 대해서만 제공되어 정확한 N*는 미확정으로 남음
• 특정 문제(OSP)의 구조에 맞춰 CUDA 커널을 설계했기 때문에, 다른 SDP 응용(양자 상태 판별, 얽힘 이론 등)에 일반화하려면 추가적인 커널 재설계가 필요할 수 있음
• k=7 이상으로 확장 시 문제 규모가 더욱 커질 것으로 예상되는데, 논문에서 제안한 matrix-free 접근의 확장성 한계(연산 시간, 정밀도 문제)에 대한 논의가 제한적임
• 후속 연구로 더 일반적인 matrix-free 프레임워크의 표준화, 다른 구조화 SDP 클래스(quantum metrology, sum-of-squares 등)로의 적용 확대가 기대됨

Evaluation

총평: 양자 순서 탐색이라는 오랜 이론적 문제에 GPU matrix-free 최적화라는 실용적 도구를 접목해 실질적인 수치적 진전과 엄밀한 증명을 동시에 제공한, 이론과 대규모 계산의 결합이 돋보이는 우수한 연구이다.