Robust Fitting on a Gate Quantum Computer

Overview

• Robust fitting은 noisy data에서 inlier를 최대화하는 모델 추정 문제로 computer vision에서 핵심 문제
• 기존 방법은 NP-hard 최적화 문제로 계산 비용이 크거나 RANSAC처럼 비결정적 방법에 의존
• influence 기반 접근은 각 데이터가 모델에 미치는 영향을 측정하여 outlier를 구분
• 본 연구는 gate-based quantum computing을 활용해 influence를 효율적으로 계산하는 방법 제안

Key Takeaways

Problem Setting

• 목표는 noisy data에서 inlier 개수를 최대화하는 모델 추정
• consensus maximization 문제는 NP-hard로 exact solution이 어려움
• 기존 방법
  • RANSAC은 빠르지만 non-deterministic
  • deterministic 방법은 계산 비용이 큼
• influence 계산은 leave-one-out 기반으로 O(N²) 이상의 비용 발생

Main Idea

• quantum computing을 활용하여 influence를 병렬적으로 계산하는 방법 제안
• Influence 기반 Outlier 측정
  • 데이터가 모델 결과에 미치는 영향으로 inlier/outlier 구분
  • influence가 낮으면 inlier, 높으면 outlier
• Boolean Influence
  • 특정 데이터의 포함 여부가 전체 모델 성립 여부를 바꾸는 확률
  • feasibility test를 기반으로 정의
• Quantum Circuit 설계
  • 데이터 subset을 입력으로 받아 residual 계산 후 threshold와 비교
  • 결과를 phase에 encoding하는 oracle 구성
• Bernstein–Vazirani Algorithm
  • superposition을 활용해 여러 subset을 동시에 평가
  • phase kickback과 간섭을 통해 한 번의 실행으로 influence 추출
• 1D Decomposition
  • 고차원 문제를 1차원 residual 문제로 분해
  • 여러 결과를 누적하여 최종 모델 추정

Result

• 시뮬레이터와 실제 양자 하드웨어에서 influence 계산 가능성 검증
• 작은 데이터에서는 실제 quantum device에서도 유의미한 결과 확인
• CV benchmark에서 RANSAC 대비 경쟁력 있는 성능 달성
• outlier 비율이 높은 데이터에서 더 높은 recall 성능 확보
• 양자 서브루틴이 classical robust fitting을 대체할 가능성 확인
• 현재는 noise와 qubit 제한으로 인해 hybrid 방식이 현실적인 접근