Better bounds on finite-order Grothendieck constants

기술 요약: 유한 차수 그로텐디크 상수(Grothendieck constants)에 대한 더 나은 경계값

문제 정의
본 논문은 유한 차수 그로텐디크 상수 $KG(d)$의 계산 문제를 다룬다. 이 상수들은 특정 텐서 노름(tensor norms)이 포함된 최적화 작업에서 $d$차원 전략이 1차원 전략에 비해 갖는 이득을 정량화한다. 무한 차수 상수 $KG$와$d=2$인 경우는 잘 연구되어 있으나,$d \geq 3$인 경우의 값은 여전히 거의 알려져 있지 않다. 주요 과제는$d$차원 반정부정계획법(SDP) 값인 $SDP_d(M)$과 1차원 값인 $SDP_1(M)$(이는 NP-난해 문제인 MaxCut 문제와 동일함) 사이의 비율을 최대화하는 행렬 $M$을 찾는 것이다. 기존의 $d \in \{3, \dots, 9\}$에 대한 경계값들은 느슨하며, 고차원 안사테제(ansatze)를 찾는 것은 차원의 저주로 인해 방해를 받고 있다.

방법론
저자들은 프랭크-월프(Frank-Wolfe, FW) 알고리즘에 기반한 최근의 투영 기법과 강력한 이진 이차 최적화 솔버를 결합하였다. 방법론은 두 가지 주요 접근 방식으로 나뉜다:

1. 대칭적 인스턴스 (휴리스틱 및 분석적 접근):

   • 저자들은 매우 대칭적인 라인 패킹(line packings, 예: $E_7, E_8$과 같은 루트 시스템 및 600-cell, 120-cell과 같은 다포체)을 사용하여 그램 행렬(Gram matrices) $P$를 구성한다.
   • 저자들은 $P$를 대칭 상관 폴리토프(symmetrized correlation polytope) $SDP_1$ 위로 투영하기 위해 BPCG(Blended Pairwise Conditional Gradient) 알고리즘을 사용한다. 이 과정은 하이퍼플레인(하이퍼플레인의 면 $A$)을 통해 $P$를 $SDP_1$으로부터 분리하는 것을 목표로 한다.
   • 대칭 구조의 경우, 주변 공간의 차원이 축소되어 "추정된(putative)" 면(facet)을 도출할 수 있다. 그러나 이러한 거대하고 대칭적인 인스턴스에 대해 정확한 $SDP_1(A)$를 계산하는 것은 정확한 솔버로는 종종 불가능하다. 따라서 저자들은 $SDP_1(A)$를 추정하기 위해 휴리스틱 방법(교대 최소화/seesaw 최적화)을 사용하며, 이는 엄밀하게 인증되지는 않지만 매우 시사적인 하한값을 제공한다.

2. 비대칭적 인스턴스 (정확한 인증):

   • 엄밀하게 인증된 경계값을 얻기 위해, 저자들은 행의 수($m_1$)는 적고 열의 수($m_2$)는 많은 직사각형 행렬 $M$을 구성한다. 이는 $SDP_1(M)$ 계산의 복잡도를 줄여준다($m_1$에 대해서는 지수적이지만 $m_2$에 대해서는 선형적임).
   • 저자들은 분리 하이퍼플레인 $M$을 찾기 위해 프랭크-월프 알고리즘을 사용한 후, 브랜치 앤 바운드(branch-and-bound) 솔버인 [13]과 QuBowl 솔버인 [39]를 사용하여 결과적인 이진 이차 최적화 문제(MaxCut)를 정확하게 해결한다.
   • $d=3$의 경우, 기존의 양자 전략을 라세르 계층(Lasserre hierarchy)의 첫 번째 레벨로 정교화하여 하한값을 약간 개선한다.

주요 기여 및 결과

• $d \in \{3, 4, 5\}$에 대한 인증된 하한값:
  본 논문은 $d=3, 4, 5$에 대해 기존의 기술 수준(SoA)을 개선하는 엄밀하게 인증된 하한값을 제공한다. $KG(d)$의 단조성에 의해, 이러한 개선은 모든$d \leq 9$로 확장된다.

  • $KG(3) \geq 1.43670$ (기존 $1.43665$ 대비 개선).
  • $KG(4) \geq 1.48579$ (기존 $1.48217$ 대비 개선).
  • $KG(5) \geq 1.49339$ (기존 $1.48217$ 대비 개선).
    이 결과들은 $d=9$까지의 알려진 $KG(d)$ 최선치들을 능가한다.

• 고차원을 위한 휴리스틱 경계값:
  매우 대칭적인 구조(구체적으로 $E_7$ 루트 시스템 및 120-cell)를 사용하여, 저자들은 현재의 SoA 값보다 상당히 높은 휴리스틱 하한값을 도출한다.

  • $KG(7)$의 경우,$E_7$루트 시스템은$KG(5)$의 인증된 하한값보다 높은 약$1.4997$의 휴리스틱 경계값을 생성한다.
  • $KG(8)$의 경우, 120-cell은 약 $1.5138$의 휴리스틱 경계값을 생성한다.
  • 저자들은 해당 $SDP_1$ 인스턴스를 정확하게 풀 수 없기 때문에 이 경계값들이 현재는 휴리스틱 상태임을 명시하지만, 밑바탕이 되는 대칭적 인스턴스들은 향후 이를 인증할 수 있도록 제공된다.

• 일반화된 상수 $KG(d \to 2)$:
  저자들은 복소수 $d$차원 양자 역학이 실수 큐비트 양자 역학에 비해 갖는 이득과 관련된 일반화된 그로텐디크 상수 $KG(d \to 2)$에 대한 분석을 확장한다.

  • 하한값: 저자들은 $SDP_2(M)$를 상한으로 하기 위해 라세르 계층(레벨 2)을 사용하여 $KG(d \to 2)$에 대한 수치적 하한값을 제공한다. 이 경계값들은 여러 차원(예: $d=3, 4, 5$)에서 기존의 기술 수준을 개선한다.
  • 상한값: 저자들은 [14]에서 변형된 분해 방법을 사용하여 $KG(3 \to 2) \leq 1.1233\dots$라는 엄밀한 해석적 상한값을 도출한다. 이는 이 특정 상수에 대한 최초의 비자명한 상한값이다.

의의 및 주장
본 논문은 프랭크-월프 투영 기법과 고급 이진 최적화 솔버를 결합함으로써 $3 \leq d \leq 9$ 범위의 유한 차수 그로텐디크 상수에 대한 알려진 하한값을 성공적으로 좁혔다고 주장한다. 이 연구는 $KG(d \to 2)$를 복소수 양자 역학이 실수 양자 역학에 비해 갖는 정량적 이득으로 해석하며, 양자 비국소성과의 연결성을 강조한다. $KG(3 \to 2)$에 대한 엄밀한 상한값은 이 이득에 대한 구체적인 한계를 제공한다. 결론적으로, 제공된 인스턴스와 방법론은 대칭성을 활용하여 남은 이차 최적화 문제들을 해결하고, 결과적으로 무한 차수 그로텐디크 상수의 최선 하한값($\approx 1.6769$)과 경쟁할 수 있는 경계값을 찾는 경로를 제시한다.