Physics and computation: An insight from non-Hermitian quantum computing

이 논문은 비유니터리 게이트를 도입한 비허미트 양자 컴퓨터 (NQC) 모델이 NP 와 $\text{P}^{\sharp\text{P}}$ 계급의 모든 문제를 다항 시간 내에 해결할 수 있는 막대한 연산 능력을 지니고 있으나, 이는 지수적으로 큰 물리적 자원을 필요로 한다는 점을 규명합니다.

핵심

1. 핵심 아이디어: "규칙을 깨는 컴퓨터 (비유: 마법 지팡이)"

일반적인 양자 컴퓨터는 **'유니터리 (Unitary)'**라는 엄격한 물리 법칙을 따릅니다. 이는 마치 **"무언가를 만들면 반드시 같은 양만큼 사라져야 한다"**는 법칙과 같습니다. 에너지나 확률이 보존되어야 한다는 거죠. 이 규칙 때문에 양자 컴퓨터는 기존 컴퓨터보다 훨씬 빠르지만, 여전히 'NP-완전 문제' (복잡한 퍼즐, 여행 판매원 문제 등) 를 해결하는 데는 한계가 있습니다.

이 논문은 **"그 규칙을 깨자"**고 제안합니다.

• 비유: 일반적인 양자 컴퓨터가 '공평한 저울'이라면, 이 논문이 제안하는 비유미안 (Non-Hermitian) 양자 컴퓨터는 **'마법 지팡이'**입니다.
• 이 마법 지팡이 (게이트 G) 를 사용하면, 확률이 사라지거나 (손실) 갑자기 불어날 (이득) 수 있습니다.
• 이 '마법 지팡이'를 사용하면, 어떤 NP 문제든 다항 시간 (매우 짧은 시간) 안에 해결할 수 있다는 것을 수학적으로 증명했습니다. 즉, 이 컴퓨터는 'P♯P'라는 매우 높은 수준의 복잡도 클래스를 다룰 수 있어, 현재 우리가 상상하는 그 어떤 문제도 순식간에 풀 수 있습니다.

2. 왜 아직 실현되지 않았을까? (비유: 거대한 물자 소모)

그렇다면 왜 우리는 이런 '초능력의 컴퓨터'를 아직 못 만들었을까요? 논문은 물리학적 현실을 지적하며 답을 줍니다.

• 핵심 결론: "이 컴퓨터의 놀라운 능력은 엄청난 물리적 자원을 태워서 얻어지는 것입니다."
• 비유:
  • 이 컴퓨터가 문제를 풀기 위해 '마법 지팡이'를 휘두를 때, 실제로는 지구에 있는 모든 모래알을 다 쓸어모아야 할 정도로 엄청난 입자 (원자) 가 필요합니다.
  • 문제를 입력하는 길이가 조금만 늘어나도 (예: 10 자리 -> 20 자리), 필요한 입자의 수는 지수 함수적으로 폭발합니다.
  • 마치 "한 번의 계산으로 전 세계의 전기를 다 써버리는" 것과 같습니다. 이론적으로는 가능하지만, 실제로는 그 엄청난 에너지를 공급할 수 없기 때문에 불가능합니다.

3. 어떻게 구현하려 했나? (두 가지 시나리오)

저자들은 이 '마법 지팡이 (게이트 G)'를 실제로 만들기 위해 두 가지 방법을 고안했습니다.

시나리오 A: 입자 수를 조절하는 냉각 원자 (비유: 물통의 수위 조절)

• 방법: 두 개의 우물 (Double-well) 사이에 원자들을 넣고, 한쪽 우물에는 원자를 계속 채워 넣고 (이득), 다른 쪽에서는 원자를 빼냅니다 (손실).
• 현실: 이렇게 하려면 **수많은 원자 (보손)**가 필요합니다. 계산이 복잡해질수록 필요한 원자의 수가 기하급수적으로 늘어납니다.
• 문제: 원자가 너무 많으면 주변 환경과 부딪혀서 **결맞음 (Decoherence)**이 깨집니다. 즉, 컴퓨터가 '망가져서' 계산이 끝나기도 전에 정보가 사라져버립니다.

시나리오 B: 포스트셀렉션 (Postselection, 비유: 운 좋은 도박)

• 방법: 계산을 하고 나서, 원하는 결과가 나올 때만 '성공'으로 간주하고 나머지는 버리는 방법입니다.
• 현실: 원하는 결과가 나올 확률이 계산할수록 기하급수적으로 낮아집니다.
• 문제: 성공 확률이 1 억 분의 1 이라면, 1 억 대의 컴퓨터를 동시에 돌려야 한 번 성공할 수 있습니다. 이는 다시 말해 엄청난 물리적 자원이 필요하다는 뜻입니다.

4. 결론: 물리학과 계산의 교훈

이 논문은 우리에게 다음과 같은 깊은 메시지를 줍니다.

1. 이론적 가능성: 물리 법칙을 조금만 수정하거나 (비유미안 시스템), 새로운 원리를 적용하면, 우리는 신과 같은 계산 능력을 가질 수 있습니다.
2. 현실적 장벽: 하지만 그 능력을 얻기 위해 치러야 할 대가는 상상할 수 없을 만큼 거대한 물리적 자원입니다.
3. 통찰: "아직 새로운 물리 법칙이 발견되지 않은 한, 기존 양자 컴퓨터의 한계를 넘어서는 것은 현실적으로 불가능하다."

한 줄 요약:

"이론상으로는 '마법 지팡이'를 휘두르면 모든 문제를 순식간에 풀 수 있지만, 그 마법을 부리기 위해 전 우주에 있는 모든 에너지를 다 써야 한다면, 결국 그 마법은 쓸모가 없는 것입니다. 계산의 힘은 결국 물리적 자원의 한계에 묶여 있다는 것이 이 논문의 결론입니다."

이 논문은 우리가 "더 빠른 컴퓨터"를 꿈꾸며 물리 법칙을 넘어서려 할 때, **자연이 우리에게 부과하는 숨겨진 '가격표'**가 얼마나 비싼지를 보여줍니다.

기술 요약

논문 요약: 비유니터리 양자 컴퓨팅 (NQC) 을 통한 물리학과 계산의 연결

1. 연구 배경 및 문제 제기 (Problem)

• 현재 양자 컴퓨팅의 한계: 기존 양자 컴퓨터 (BQP 복잡도 클래스) 는 쇼어 (Shor) 알고리즘이나 그로버 (Grover) 알고리즘과 같은 특정 문제에서는 고전 컴퓨터보다 우수하지만, NP-완전 문제나 P♯P(계수 문제) 클래스의 문제를 다항식 시간 내에 해결하는 데에는 한계가 있습니다.
• 기존 이론적 접근의 문제점: NP-완전 문제를 다항식 시간에 해결하기 위해 제안된 여러 이론적 모델 (닫힌 시간꼴 곡선, 비선형 게이트, 포스트셀렉션, 로렌츠 양자 컴퓨터 등) 은 물리적으로 구현하기 어렵거나 가상의 능력을 가정하는 경우가 많습니다.
• 핵심 질문: 물리적으로 실현 가능한 시스템을 사용하여 기존 양자 컴퓨팅을 능가하는 계산 능력을 가질 수 있는가? 만약 가능하다면, 그 계산 능력의 물리적 근원은 무엇인가?

2. 연구 방법론 (Methodology)

저자들은 **비유니터리 양자 컴퓨터 (Non-Hermitian Quantum Computer, NQC)**라는 새로운 계산 모델을 제안하고 분석했습니다.

• 모델 정의 (NQC):
  • 기존 양자 게이트 (Hadamard, Phase, CNOT) 에 비유니터리 게이트 $G$를 추가합니다.
  • 게이트 $G$는 대각 행렬 $G = \text{diag}(g^{-1}, g)$ ($g > 0, g \neq 1$) 로 정의되며, 상태의 노름 (norm) 을 변경합니다.
  • 이 모델에서 계산 복잡도 클래스를 **BNQP (Bounded-error Non-Hermitian Quantum Polynomial time)**로 정의합니다.
• 알고리즘 설계:
  • 최대 독립 집합 (Maximum Independent Set, MIS) 문제를 해결하는 알고리즘을 설계했습니다. MIS 는 NP-hard 문제입니다.
  • $n$개의 작업 큐비트와 비유니터리 변환을 받는 추가 큐비트 (oracle qubit) 를 사용하여, 독립 집합 (IS) 인 상태들의 진폭을 지수적으로 증폭시키는 방식을 채택했습니다.
• 물리적 구현 방안 분석:
  • 게이트 $G$를 물리적으로 구현하기 위해 두 가지 구체적인 방식을 제안하고 분석했습니다.
    1. 입자 수 조절을 통한 구현: 이중 우물 (double-well) 구조를 가진 다중 보손 (boson) 시스템 (예: 냉각 원자) 을 사용하여, 한 상태의 입자 수는 증가시키고 다른 상태의 입자 수는 감소시키는 '이득 (gain) 과 손실 (loss)' 메커니즘을 적용합니다.
    2. 포스트셀렉션 (Postselection) 기반 구현: 보조 큐비트를 도입하고 특정 측정 결과를 선택함으로써 비유니터리 효과를 모사하는 방식입니다.
• 복잡도 및 자원 분석:
  • 제안된 알고리즘이 어떤 복잡도 클래스에 해당하는지 증명하고, 물리적 구현에 필요한 자원 (입자 수, 시간, 결맞음 시간 등) 을 정량적으로 분석했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

• 계산 복잡도 이론적 결과:

  • BNQP = P♯P 증명: NQC 모델이 다항식 시간 내에 해결할 수 있는 문제의 클래스 (BNQP) 가 P♯P와 동일함을 증명했습니다. 이는 NP-완전 문제뿐만 아니라 NP-hard 문제와 계수 문제 (counting problems) 도 다항식 시간에 해결할 수 있음을 의미합니다.
  • 로렌츠 양자 컴퓨터 (LQC) 와의 동등성: LQC 와 NQC 는 물리적 구현 방식은 다르지만, '지수적 진폭 증폭 (exponential amplitude amplification)'이라는 핵심 메커니즘을 공유하므로 계산 능력이 동등함을 보였습니다.

• 물리적 구현의 한계 (핵심 통찰):

  • 지수적 자원 요구: NQC 의 놀라운 계산 능력은 지수적으로 큰 물리적 자원이 필요하기 때문에 발생합니다.
    • 입자 수: 알고리즘이 성공하려면 초기 상태의 진폭이 매우 작은 경우에도 이를 구별해야 하므로, 시스템에 존재해야 하는 입자 수가 입력 크기 $n$에 대해 지수적으로 ($2^n$ 이상) 커야 합니다.
    • 포스트셀렉션: 포스트셀렉션 방식을 사용할 경우, 성공 확률이 입력 크기에 대해 지수적으로 감소하므로, 성공을 보장하기 위해 지수적으로 많은 병렬 컴퓨터가 필요합니다.
  • 결맞음 시간 (Decoherence) 문제: 다중 입자 시스템에서 결맞음 시간은 입자 수 $N$에 반비례하여 ($T_2' \approx T_2/N$) 급격히 짧아집니다. NQC 는 입자 수가 지수적으로 증가해야 하므로, 결맞음 시간이 알고리즘 실행 시간보다 훨씬 짧아져 물리적 구현이 사실상 불가능해집니다.

• 게이트 구현 메커니즘:

  • 비유니터리 게이트 $G$는 PT-대칭 시스템이나 예외적 위상 (exceptional topology) 을 가진 시스템에서 얻어지는 **허수 기하학적 위상 (purely imaginary geometric phase)**을 이용하여 구현할 수 있음을 보였습니다.

4. 의의 및 결론 (Significance)

• 물리학과 계산의 관계에 대한 통찰: 이 논문은 "계산 능력의 향상이 물리적 자원의 지수적 증가를 요구한다"는 근본적인 관계를 규명했습니다. 즉, 물리 법칙을 위반하지 않고 (비유니터리 시스템을 물리적 시스템으로 구현하더라도) 기존 양자 컴퓨팅을 능가하는 계산 능력을 얻으려면, 지수적으로 거대한 물리적 자원을 투입해야만 합니다.
• 실현 가능성에 대한 경고: 이론적으로는 NP-완전 문제를 다항식 시간에 풀 수 있는 모델이 존재하지만, 물리적으로 구현하기 위해서는 현실적으로 불가능한 수준의 자원 (지수적인 입자 수, 극도로 낮은 결맞음 시간 등) 이 필요하므로, 현재 물리 법칙의 범위 내에서는 고전 컴퓨터나 기존 양자 컴퓨터를 능가하는 실용적인 컴퓨터를 만드는 것은 불가능할 가능성이 높습니다.
• 미래 연구 방향: 계산 복잡도 클래스 (P, NP, P♯P 등) 와 물리 법칙 (유니터리, 비유니터리, 비선형 등) 사이의 매핑 관계를 더 깊이 연구할 필요성을 제기했습니다.

요약하자면, 이 논문은 비유니터리 양자 컴퓨팅 (NQC) 이 이론적으로는 P♯P 클래스의 문제를 해결할 수 있는 강력한 계산 능력을 가지지만, 그 구현에 필요한 물리적 자원 (입자 수, 결맞음 유지) 이 지수적으로 증가해야 하므로 실제 구현은 불가능에 가깝다는 것을 증명하여, 계산 능력과 물리적 제약 사이의 균형을 명확히 보여줍니다.