Quantum algorithms and the power of forgetting

dc.contributor.advisorChilds, Andrewen_US
dc.contributor.advisorCoudron, Matthewen_US
dc.contributor.authorGilani, Amin Shirazen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.description.abstractThe so-called Welded Tree Problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm (https://arxiv.org/pdf/quant-ph/0209131.pdf). Given the name of a special ENTRANCE vertex, a quantum walk can find another distinguished EXIT vertex using polynomially many queries, though without finding any particular path from ENTRANCE to EXIT. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT in the Welded Tree Problem. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the ENTRANCE, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is hard to imagine how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, to outperform classical computation, quantum algorithms must necessarily forget the path they take to reach a solution.en_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pquncontrolledClassical Hardnessen_US
dc.subject.pquncontrolledComputational Complexityen_US
dc.subject.pquncontrolledQuantum Algorithmsen_US
dc.subject.pquncontrolledQuantum Hardnessen_US
dc.subject.pquncontrolledWelded Tree Problemen_US
dc.titleQuantum algorithms and the power of forgettingen_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
519.55 KB
Adobe Portable Document Format