중력으로 NP-완전 문제를 푼다? 물리학이 던진 도발

NP-완전 문제는 외판원 문제처럼 정답 검증은 쉽지만 푸는 데는 지수 시간이 걸린다고 여겨지는 난제다. 이 논문은 '준고전 중력(semiclassical gravity)'을 쓰면 이런 문제를 다항 시간에 풀 수 있다고 주장한다. 핵심은 중력이 양자역학에 미세한 '비선형성'을 도입한다는 점이다. 기존 양자컴퓨터는 선형 양자역학을 따르기에 NP-완전 문제를 효율적으로 못 풀지만, 비선형성이 있으면 지수적으로 많은 후보 해를 한꺼번에 증폭하고 구별할 수 있다는 논리다. 다만 이는 무한한 측정 정밀도와 결잃음(decoherence) 무시 같은 이상적 가정에 기댄 이론적 결과로, 당장 RSA 암호가 깨지거나 실제 하드웨어가 나오는 건 아니다. 그럼에도 '계산의 한계는 결국 우리가 사는 우주의 물리 법칙이 정한다'는 점을 일깨운다. P vs NP를 물리학 관점에서 다시 보게 하는 흥미로운 사고실험이다.