해밀토니안 국소성 테스팅과 인증은 하이젠베르크 한계에 도달하지 못한다
Hamiltonian locality testing and certification do not achieve the Heisenberg limit
한국어 초록
본 연구에서는 시간 진화(time-evolution) 연산자에 접근할 수 있지만 그 역연산자에는 접근할 수 없는 환경에서 해밀토니안(Hamiltonian) 속성 테스팅의 하한(lower bound)을 규명합니다. 각 실험은 시간 진화 연산자를 여러 번 쿼리할 수 있으며, 해밀토니안 간 거리는 정규화된 프로베니우스 노름(normalized Frobenius norm)으로 측정됩니다. 이 모델(model)에서 해밀토니안이 $k$-국소($k$-local)인지 아니면 모든 $k$-국소 해밀토니안과 $\varepsilon$ 이상 떨어져 있는지를 테스트하려면 $Ω(1/\varepsilon^2)$의 총 진화 시간이 필요함을 보이며, 이는 Kallaugher와 Liang(TQC'25)의 상한과 일치합니다. 또한 미지의 해밀토니안이 목표 해밀토니안과 동일한지 아니면 이와 $\varepsilon$ 이상 떨어져 있는지를 테스트하는 데에도 $Ω(1/\varepsilon^2)$의 총 진화 시간이 필요함을 증명하여, Sinha와 Tong(2025)의 상한과 일치함을 보입니다. 이는 해밀토니안 학습 및 테스팅의 자연스러운 문제들에서 $1/\varepsilon$의 하이젠베르크 한계 스케일링(Heisenberg-limited scaling)을 배제하는 최초의 하한 결과입니다. 세 번째 결과로, 정밀도(precision) $\varepsilon$까지의 진폭 추정(amplitude estimation)에는 $Ω(1/\varepsilon^2)$의 총 시간 진화가 필요함을 보여 연속 시간 쿼리 모델에서 Tang과 Wright(QIP'26)의 결과를 재현합니다. 이 세 가지 결과는 모두 영 해밀토니안(zero Hamiltonian)과 적절히 선택된 무작위 해밀토니안 앙상블(ensemble)을 구별하는 난이도에서 비롯됩니다. 본 논문에서는 연속 시간 적대자 방법(continuous-time adversary method)을 순방향 해밀토니안 진화에 맞게 적용함으로써 이러한 난이도를 증명합니다.
원문 초록
We establish lower bounds for Hamiltonian property testing with access to the time-evolution operator but not its inverse. Each experiment may query the time-evolution operator multiple times, and distances between Hamiltonians are measured in the normalized Frobenius norm. In this model, we show that testing whether a Hamiltonian is $k$-local or $\varepsilon$-far from every $k$-local Hamiltonian requires $Ω(1/\varepsilon^2)$ total evolution time, matching the upper bound of Kallaugher and Liang (TQC'25). We also prove that testing whether an unknown Hamiltonian equals a target Hamiltonian or is $\varepsilon$-far from it requires $Ω(1/\varepsilon^2)$ total evolution time, matching the upper bound of Sinha and Tong (2025). These are the first lower bounds for natural problems in Hamiltonian learning and testing that rule out Heisenberg-limited scaling of $1/\varepsilon$. As a third result, we show that amplitude estimation to precision $\varepsilon$ requires $Ω(1/\varepsilon^2)$ total time evolution, recovering the result of Tang and Wright (QIP'26) in the continuous-time query model. All three results follow from the hardness of distinguishing the zero Hamiltonian from a suitably chosen ensemble of random Hamiltonians. We establish this hardness by adapting the continuous-time adversary method to forward Hamiltonian evolution.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
28 pages