Comment on Temperature change can solve the Deutsch-Jozsa problem: An exploration of thermodynamic query complexity

기술 요약: 온도 변화가 Deutsch–Jozsa 문제를 해결할 수 있다는 주장에 대한 논평: 열역학적 쿼리 복잡도에 관한 탐구

문제 제식 (Problem Statement)
본 논문은 Phys. Rev. A 113, 012420 (2026) (이하 참고문헌 [1])에서 제안된 자원 계수 및 판독(readout) 분석의 결정적인 결함을 다룬다. 참고문헌 [1]은 Deutsch–Jozsa 결정 문제가 단 한 번의 열 쿼리(프로브 큐비트와 열 기계 오라클 사이의 열 교환)와 입력 크기에 독립적인 다수의 통계적으로 유용한 프로브 샘플을 통해 해결될 수 있다고 주장한다. 본 논문의 저자들은 제안된 판독 메커니즘이 단일 쿼리로부터 독립적인 샘플을 생성하지 못하며, 도출된 샘플 하한선이 수학적으로 잘못되었음을 논증한다.

방법론 및 분석 (Methodology and Analysis)
본 논문은 참고문헌 [1]에서 논의된 두 가지 주요 판독 전략과 샘플 복잡도 하한을 도출하는 데 사용된 통계적 부등식을 분석한다.

1. CNOT Fanout 분석: 참고문헌 [1]은 반복 측정을 허용하기 위해 단일 포스트-쿼리 프로브 상태 $\rho_h$ (여기서 $h \in \{B, C\}$는 balanced 또는 constant 가설을 나타냄)를 $M$개의 순수 안실라 큐비트로 "유니터리 재구성"하기 위해 CNOT 게이트를 사용하는 것을 제안한다.

   • 저자들은 대각 성분 프로브 상태(diagonal probe state)로부터 CNOT 게이트를 적용하면 $M$개의 안실라에 대해 결합 상태 $\sigma^{(M)}_h = p_h|0^{M+1}\rangle\langle 0^{M+1}| + (1-p_h)|1^{M+1}\rangle\langle 1^{M+1}|$가 생성됨을 보여준다.
   • 각 레지스터는 주변 상태(marginal state) $\rho_h$를 유지하지만, 결합 상태는 완벽하게 상관된(correlated) 레지스터들(모두 0이거나 모두 1인 상태)로 구성된다.
   • 결과적으로, $M+1$개의 기록된 비트는 $M$번 복제된 단일 베르누이 시행(Bernoulli draw)이지, $M+1$개의 독립적인 시행이 아니다. 따라서 경험적 빈도는 $M$이 증가함에 따라 진정한 확률 $p_h$로 수렴하지 않는다.
   • 저자들은 이 fanout 상태에 대한 balanced 가설과 constant 가설 사이의 트레이스 거리(trace distance)와 상대 엔트로피(relative entropy)를 계산하였으며, 이들이 단일 복사본의 값과 동일함($T(\sigma^{(M)}_B, \sigma^{(M)}_C) = T(\rho_B, \rho_C)$ 및 $D(\sigma^{(M)}_B \| \sigma^{(M)}_C) = D(\rho_B \| \rho_C)$)을 보여준다. 따라서 fanout은 구별 가능성(distinguishability)을 증폭시키지 못한다.

2. Reset-and-Repeat 분석: 대안적인 전략은 프로브를 측정하고, 시스템을 리셋한 후 실험을 반복하는 것이다.

   • 저자들은 "쿼리"가 프로브와 오라클 사이의 열 교환으로 정의되는 참고문헌 [1]의 정의에 따라, 이 절차가 $M$개의 독립적인 샘플을 생성하기 위해서는 $M$번의 별도 열 쿼리가 필요하다고 주장한다.
   • 따라서 "하나의 쿼리 후 다수의 샘플"이라는 주장은 운영상 유효하지 않다. 즉, 독립적인 샘플을 위해서는 반복적인 열 교환이 필수적이다.

3. 통계적 부등식 비판: 본 논문은 $n^* > \ln(1/\delta) / D(\rho_B \| \rho_C)$라고 명시된 참고문헌 [1]의 식 (7)에 기술된 샘플 하한 $n^*$을 검토하며, 이를 트레이스 거리 임계값 $t$와 연결하기 위해 핀스커 부등식(Pinsker's inequality)을 활용한다.

   • 저자들은 핀스커 부등식($D \geq 2T^2$)이 상대 엔트로피의 역수에 대한 *상한(upper bound)*을 의미하며, 하한이 아님을 보여준다.
   • 구체적으로, 부등식을 대입하면 $\frac{\ln(1/\delta)}{D} < \frac{\ln(1/\delta)}{2t^2}$가 된다. 식 (7)에서 $n^*$의 하한을 왼쪽 항으로부터 도출하는 것은 참고문헌 [1]에 기술된 $n^* > \frac{\ln(1/\delta)}{2t^2}$라는 부등식을 논리적으로 함의할 수 없다.
   • 또한, 저자들은 체르노프-스타인 정리(Chernoff–Stein lemma)가 점근적 오류 지수를 규정하기는 하지만, 추가적인 분석 없이는 참고문헌 [1]에서 사용된 것과 같은 정확한 유한 샘플 부등식을 제공하지 않는다는 점을 지적한다.

주요 기여 및 결과 (Key Contributions and Results)

• 자원 계수의 교정: 본 논문은 CNOT fanout이 대각 성분 포스트-쿼리 프로브를 생성할 때 독립적인 복사본이 아닌 완벽하게 상관된 레지스터들을 생성함을 입증한다. 따라서 이 안실라들을 반복 측정하는 것은 단 하나의 베르누이 관측만을 제공할 뿐, $M$개의 독립적인 관측을 제공하지 않는다.
• 쿼리 복잡도의 명확화: 분석 결과, "reset-and-repeat" 방법을 통해 $M$개의 독립적인 샘플을 생성하려면 $M$번의 열 쿼리가 필요함을 확인하였으며, 이는 단 한 번의 쿼리로 입력 크기에 독립적인 다수의 샘플을 얻을 수 있다는 주장에 반한다.
• 샘플 하한의 수학적 반박: 저자들은 $\delta = t = 0.1$일 때 약 116개의 샘플이 필요하다는 식 (7)의 구체적인 수치적 주장이 핀스커 부등식으로부터 도출되지 않음을 보여준다. 해당 부등식은 실제로는 해당 식에 대한 상한 추정치를 제공하는 것이지, 필요한 하한이 아니다.
• 구별 가능성 보존: CNOT fanout은 가설 간의 트레이스 거리와 상대 엔트로피를 증폭시키는 것이 아니라 보존하는 등거리 임베딩(isometric embedding)임을 보여준다.

의의 및 주장 (Significance and Claims)
저자들은 이러한 관찰이 근본적인 인구 이동(population-transfer) 계산이나 "열적 킥백(thermal kickback)"이 프로브 온도에 결정 정보를 인코딩할 가능성을 무효화하는 것은 아니라고 밝힌다. 또한, 인구 분리(population separation)가 0에서 멀리 떨어져 있는 한, 고정된 목표 오차에 대해 상수 쿼리 복잡도가 가능할 가능성도 배제하지 않는다.

그러나 본 논문은 운영적 결론(operational conclusions)이 참고문헌 [1]과 같이 수정되어야 한다고 주장한다. 구체적으로:

1. 단일 쿼리된 혼합 프로브가 여러 개의 독립적인 관측을 생성한다는 주장은 거짓이다.
2. 온도 추정에 필요한 독립적인 관측을 생성하려면 열 교환 오라클을 반복적으로 사용해야 한다.
3. "하나의 쿼리" 대 "다수의 샘플"을 기준으로 한 비교는 결함이 있다.
4. 식 (7)에서 도출된 "최소 116개의 샘플"이라는 구체적인 수치적 주장은 인용된 부등식들에 의해 뒷받침되지 않는다.

본 논문은 단일 쿼리 판독 주장과 그에 따른 참고문헌 [1]의 자원 계수가 열역학적 쿼리 복잡도를 정확하게 반영하기 위해서는 수정이 필요하다고 결론짓는다.