Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard

이 논문은 양자 워크(quantum walk)가 고전적 알고리즘보다 용접된 트리(welded trees)를 지수적으로 빠르게 횡단할 수 있는 반면, 루트 사이의 경로를 명시적으로 기록하려는 모든 양자 알고리즘은 지수적으로 많은 쿼리($\tilde{\Theta}(2^{n/3})$)를 필요로 한다는 점을 증명함으로써, 간섭이 효율적인 탐색을 가능하게 하지만 경로 재구성은 여전히 어렵다는 "알고리즘적 파동-입자 이중성"을 확립한다.

원저자: Joseph Carolan, Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani, David Miloschewsky, Supartha Podder