Feedback-based quantum optimization and its classical counterpart: quantum advantage and the power of classical algorithms

본 논문은 피드백 기반 양자 최적화 (FALQON) 의 고전적 대응책을 소개하여, 양자 알고리즘이 더 우수한 해의 품질을 제공할 수 있지만, 고전적 대응책은 종종 더 빠른 수렴을 달성하고 고차원 비제약 이진 최적화 문제에 대해 상당한 확장성을 보임을 입증한다.

핵심

거대한 안개 낀 산악 지형에서 절대적인 최저점을 찾으려 한다고 상상해 보세요. 이것이 컴퓨터가 '조합 최적화' 문제를 해결할 때 수행하는 작업입니다. 예를 들어, 화물 운송 회사의 가장 효율적인 배송 경로를 찾거나 새로운 배터리의 재료를 최적으로 배치하는 방법을 찾는 것이 그렇습니다. 목표는 에너지 (또는 비용) 가 가장 낮은 '바닥 상태', 즉 가장 깊은 골짜기를 찾는 것입니다.

이 논문은 그 골짜기를 찾으려 노력하는 두 팀의 탐험가를 비교하는 새로운 방식을 소개합니다: 양자 탐험가들(기이한 양자 물리 법칙을 사용하는) 과 고전 탐험가들(표준 수학 및 물리학을 사용하는) 입니다.

다음은 간단한 비유를 통해 그들의 발견 사항을 정리한 것입니다:

1. 두 팀의 탐험가

이 논문은 피드백 기반 최적화라는 특정 방법에 초점을 맞춥니다. 이는 미리 작성된 지도를 따르는 것이 아니라, 현재 서 있는 지형에 기반하여 나침반을 계속 확인하고 경로를 조정하는 등산객과 같습니다.

• 양자 팀 (FALQON): 이 탐험가들은 양자 역학을 사용합니다. 양자적 기이함 (한 번에 여러 곳에 있는 것과 같은) 으로 인해 그들은 한 번에 전체 지형을 '느낄' 수 있습니다.
• 고전 팀 (CC-FALQON, CACAO 등): 이 탐험가들은 표준 물리학을 사용합니다. 그들은 국소적인 단서를 기반으로 위치를 업데이트하며 한 걸음씩 이동합니다.

2. 큰 발견: 속도 대 품질

연구자들은 누가 승리하는지 시뮬레이션을 실행했습니다. 결과는 스포츠카와 중량 트럭 사이에서 선택하는 것과 같은 고전적인 트레이드오프를 드러냈습니다.

• 양자 '스포츠카' (FALQON):

  • 장점: 절대적으로 최적인 해결책 (가장 깊은 골짜기) 을 찾는 데 탁월합니다. 일부 테스트에서는 고전 팀보다 더 나은 답을 찾았습니다.
  • 단점: 느립니다. 경로를 계속 측정하고 조정해야 하므로 계산 비용이 많이 들고 시간이 오래 걸립니다.
  • 비유: 전체 지도를 볼 수 있지만 많은 배터리를 소모하고 정밀하게 이동하기 위해 천천히 움직이는 하이테크 드론과 같습니다.

• 고전 '트럭' (CACAO 및 그 업그레이드):

  • 장점: 놀라울 정도로 빠릅니다. 양자 팀보다 훨씬 빠르게 좋은 해결책에 수렴합니다.
  • 단점: 때로는 절대적으로 가장 깊은 골짜기 대신 '충분히 좋은' 골짜기에 만족합니다.
  • 비유: 곧고 빠르게 주행하는 중량 트럭과 같습니다. 완벽한 장소를 찾지는 못할지라도 기록적인 시간 안에 그곳에 도달합니다.

3. '슈퍼 트럭' (HOT-CACAO)

저자들은 기본 고전 트럭에서 멈추지 않았습니다. HOT-CACAO(그리고 더 진보된 버전인 HOT-CACAO+) 라는 '슈퍼 트럭'을 개발했습니다.

• 작동 원리: 트럭에 '고차' 도구를 추가했습니다. 트럭에 조향 장치뿐만 아니라 바퀴가 도로에 닿기 전에 도로의 모양에 맞춰 조정할 수 있는 서스펜션 시스템을 준다고 상상해 보세요.
• 결과: 이 슈퍼 트럭은 크고 복잡한 문제에서 승리자입니다. 빠르면서도 매우 깊은 골짜기를 찾습니다.
• 확장성: 문제가 거대해졌을 때 (예: 10,000 개의 도시가 있는 지도), 기본 트럭들과 양자 드론은 어려움을 겪거나 그대로 유지되었습니다. 반면 슈퍼 트럭은 지도가 커질수록 저에너지 해결책을 찾는 능력이 실제로 향상되었습니다.

4. '균질성 vs 비균질성' 반전

가장 흥미로운 발견 중 하나는 두 팀이 '노이즈'나 고르지 않은 지형 (비균질성이라고 함) 에 어떻게 반응했는지였습니다.

• 양자 팀: 지형이 매끄럽고 균일할 때 (균질성) 가장 잘 작동했습니다. 지형을 고르지 않게 만들면 혼란을 겪고 성능이 떨어졌습니다.
• 고전 팀: 그들은 오히려 고르지 않은 지형 (비균질성) 을 좋아했습니다. 문제의 각 부분을 다르게 처리함으로써 혼란을 더 잘 헤쳐나갈 수 있었습니다.
• 비유: 양자 팀은 동기화된 댄스 트roupe 과 같습니다. 모두 완벽한 조화를 이루어 움직여야 작동합니다. 고전 팀은 개별 등산객들의 그룹과 같습니다. 길이 거칠어지면 각자 그 주위를 우회할 수 있는 자신만의 독특한 단계를 취할 수 있습니다.

5. 이것이 중요한 이유 (논문에 따르면)

이 논문은 양자 컴퓨터를 모든 것을 대체할 '미래'로만 보지 말아야 한다고 결론 내립니다.

• 양자 우위: 양자 알고리즘 (FALQON 등) 은 전 지형을 전역적으로 탐색할 수 있는 능력 덕분에 고전 컴퓨터가 놓칠 수 있는 더 높은 품질의 해결책을 찾을 잠재력을 보여줍니다.
• 고전적 힘: 그러나 고전 알고리즘 (특히 새로운 HOT-CACAO 버전) 은 현재 더 실용적입니다. 이들은 더 빠르고, 값비싼 양자 하드웨어가 필요하지 않으며, 먼저 단순화할 필요 없이 직접 거대하고 복잡한 문제 (예: '고차' 문제) 를 처리할 수 있습니다.

요약하자면: 이 논문은 양자 컴퓨터가 결국 완벽한 답을 찾을 수 있는 정밀 도구와 같지만, 고전 컴퓨터는 현재 현실 세계의 최적화 문제를 해결하는 데 매우 효과적인 강력하고 빠르며 확장 가능한 도구로 진화했다고 주장합니다. '슈퍼 트럭' (HOT-CACAO+) 은 현재 대규모 복잡한 작업의 챔피언입니다.

기술 요약

기술 요약: 피드백 기반 양자 최적화 및 그 고전적 대응

문제 제기
물류, 재료 과학, 금융 등에 광범위하게 존재하는 조합 최적화 문제는 일반적으로 NP-hard 로 분류되어, 정확한 해를 구하는 데 지수적인 계산 비용이 필요합니다. 양자 어닐러와 변분 양자 알고리즘을 포함한 다양한 양자 및 고전 솔버가 존재하지만, 양자 우위의 가능성을 평가하기 위해 양자 접근법과 그 고전적 대응을 엄격하게 비교할 필요가 있습니다. 구체적으로, Feedback-based Algorithm for Quantum Optimization(FALQON) 은 고전적 최적화 루프 없이 리아푸노프 제어 이론을 활용하여 비용 함수를 반복적으로 감소시킵니다. 그러나 양자 시스템에서 반복적 피드백의 계산 비용은 상당합니다. 반면, FALQON 에서 영감을 받은 CACAO(Counterdiabaticity-assisted Classical Algorithm for Optimization) 와 같은 고전 알고리즘은 더 빠른 수렴을 제공하지만 해의 품질이 부족할 수 있습니다. 또한, Higher-order Unconstrained Binary Optimization(HUBO) 문제는 종종 2 차 Unconstrained Binary Optimization(QUBO) 형태로 축소하여 해결되는데, 이는 문제 크기를 증가시켜 비효율적입니다. 피드백 기반 양자 알고리즘의 정확한 고전적 대응과 HUBO 문제를 직접 처리하는 능력에 대한 이해에는 격차가 존재합니다.

방법론
저자들은 스핀 시스템의 양자 - 고전 대응에 기반한 이론적 프레임워크를 수립했습니다. 파울리 행렬 $\{\hat{X}_i, \hat{Y}_i, \hat{Z}_i\}$를 고전 단위 스핀 벡터 $\{m^X_i, m^Y_i, m^Z_i\}$로 대체하고 정준 운동 방정식을 활용함으로써, 피드백 기반 양자 최적화에 대한 정확한 고전적 대응을 유도했습니다.

1. 이론적 유도:

   • 양자 측면: 논문은 문제 해밀토니안과 구동 항 사이의 교환자의 기댓값으로 제어 매개변수가 결정되는 FALQON 과 그 비균질 변형 (iFALQON) 을 검토합니다.
   • 고전 측면: 저자들은 CC-FALQON과 CC-iFALQON을 정확한 고전적 대응으로 유도합니다. 양자 버전과 달리, 이러한 고전 알고리즘은 반복적 피드백 루프를 요구하지 않으며, 제어 매개변수는 고전 스핀의 순간 상태로부터 직접 계산됩니다.
   • 고차 확장: 프레임워크는 2 차 카운터대아바틱 항을 도입하는 HOT-CACAO(Higher-Order CACAO) 와 문제 해밀토니안 및 논의된 모든 카운터대아바틱 항 (1 차 및 2 차) 을 포함하는 **HOT-CACAO+**를 개발하기 위해 확장됩니다.

2. 벤치마킹:

   • 소규모: 저자들은 양자 알고리즘 (FALQON, iFALQON) 과 그 고전적 대응 (CC-FALQON, CC-iFALQON) 및 기타 고전 변형 (CACAO, HOT-CACAO, HOT-CACAO+) 간의 해 품질과 수렴 속도를 비교하기 위해 QUBO 로 공식화된 2-SAT 문제의 $N=12$개 인스턴스에 대해 벤치마크 테스트를 수행합니다.
   • 대규모: 연구는 HUBO 로 직접 공식화된 3-SAT 문제의 $N=10,000$개 인스턴스에서 고전 알고리즘의 확장성을 평가합니다. 테스트된 알고리즘에는 CC-iFALQON, CACAO, HOT-CACAO, HOT-CACAO+가 포함됩니다.
   • 동역학 분석: 논문은 수렴 거동과 비국소성 대 국소성의 역할을 이해하기 위해 제어 매개변수 강도와 에너지 동역학을 분석합니다.

주요 기여

• 정확한 고전적 대응: 논문은 스핀 시스템 대응에서 유도된 피드백 기반 양자 최적화 알고리즘에 대한 최초의 정확한 고전적 공식인 CC-FALQON 과 CC-iFALQON 을 소개합니다.
• 고차 고전 이론: 이는 문제 해밀토니안의 명시적 포함과 함께 고차 카운터대아바틱 항으로 CACAO 알고리즘을 확장하는 HOT-CACAO 와 HOT-CACAO+를 개발합니다.
• 직접 HUBO 해결: 제안된 고전 알고리즘은 보조 변수를 도입하고 성능을 저하시키는 일반적인 차수 축소 방법 없이 HUBO 문제를 직접 해결하는 것으로 입증되었습니다.
• 양자 대 고전 동역학: 이 연구는 비균질 구동에 대한 양자 및 고전 동역학의 대조적 거동을 명확히 하여, 그 차이를 양자 동역학의 전역적 성격 대 고전 업데이트의 국소적 성격에 기인합니다.

결과

• 해 품질 대 수렴 속도:
  • 품질에서의 양자 우위: 소규모 인스턴스에서 FALQON 은 그 고전적 대응인 CC-FALQON 과 기타 고전 알고리즘보다 우수한 해 품질 (더 낮은 최종 에너지 밀도) 을 보여주어, 전역 최적화 지형을 탐색하는 데 잠재적인 양자 우위가 있음을 시사합니다.
  • 속도에서의 고전 우위: 고전 알고리즘은 일반적으로 양자 알고리즘보다 훨씬 빠른 수렴을 보입니다. 특히 CC-FALQON 은 매우 느린 수렴을 보이는 반면, HOT-CACAO 와 HOT-CACAO+는 빠르게 수렴합니다.
• 비균질성 효과:
  • 양자 설정에서는 균질 구동 (FALQON) 이 비균질 구동 (iFALQON) 보다 우수합니다.
  • 고전 설정에서는 경향이 반전됩니다: 비균질 구동 (CC-iFALQON) 이 균질 구동 (CC-FALQON) 보다 낮은 에너지를 달성합니다. 이는 전역 양자 동역학과 국소 매개변수 간의 불일치 대 비균질 구동과 국소 고전 업데이트 간의 호환성에 기인합니다.
• 확장성 및 HUBO 성능:
  • 대규모 3-SAT 인스턴스 ($N=10,000$) 에서 **HOT-CACAO+**는 테스트된 모든 방법 중 가장 낮은 최종 에너지 밀도를 달성합니다.
  • HOT-CACAO+는 HOT-CACAO 보다 느리게 수렴하지만 더 낮은 에너지 상태에 도달하여 수렴 속도와 해 품질 간의 트레이드오프를 나타냅니다.
  • 확장성 분석은 HOT-CACAO+가 시스템 크기가 증가함에 따라 일관되게 에너지 밀도를 개선하는 유일한 방법임을 보여줍니다. 반면 다른 방법들은 정체됩니다. 이는 대규모 고차 최적화를 위해 문제 해밀토니안과 고차 카운터대아바틱 항을 결합할 필요성을 강조합니다.

의의 및 주장
이 논문은 "양자성"과 고전적 접근법의 뚜렷한 역할을 부각시킨다는 주장을 합니다. 피드백 기반 양자 최적화 (FALQON) 는 전역 상관관계를 활용하여 더 높은 품질의 해를 달성할 잠재력을 보이는 반면, 특히 고차 카운터대아바틱 항으로 강화된 고전 알고리즘 (HOT-CACAO+) 은 HUBO 문제에 대해 빠른 수렴과 우수한 확장성을 제공합니다.

저자들은 고전 알고리즘이 양자 구현과 관련된 반복적 오버헤드와 중간 상태 측정 비용을 피하기 때문에 조합 최적화에 매우 유망하다고 주장합니다. 또한, 차수 축소 없이 고차 상호작용을 직접 처리할 수 있는 능력은 이러한 고전적 접근법을 HUBO 공식에 특히 효율적으로 만듭니다. 논문은 양자 알고리즘이 해 품질 측면에서 이점을 제공할 수 있지만, 고전 알고리즘은 강력하고 확장 가능한 대안을 제공하며, 동등한 계산 예산 하에서의 체계적인 비교가 향후 연구의 필수적인 방향이라고 결론지었습니다.