1 Search Results for "Gilani, Amin Shiraz"

Document

DOI: 10.4230/LIPIcs.ITCS.2023.37

Quantum Algorithms and the Power of Forgetting

Authors: Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

The 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 [Andrew M. Childs et al., 2003]. 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. 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 unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation.

Cite as

Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani. Quantum Algorithms and the Power of Forgetting. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 37:1-37:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{childs_et_al:LIPIcs.ITCS.2023.37,
  author =	{Childs, Andrew M. and Coudron, Matthew and Gilani, Amin Shiraz},
  title =	{{Quantum Algorithms and the Power of Forgetting}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{37:1--37:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.37},
  URN =		{urn:nbn:de:0030-drops-175408},
  doi =		{10.4230/LIPIcs.ITCS.2023.37},
  annote =	{Keywords: Quantum algorithms, quantum query complexity}
}

Refine by Author
1 Childs, Andrew M.
1 Coudron, Matthew
1 Gilani, Amin Shiraz

Refine by Classification
1 Theory of computation → Quantum computation theory

Refine by Keyword
1 Quantum algorithms
1 quantum query complexity

Refine by Type
1 document

Refine by Publication Year
1 2023

1 Search Results for "Gilani, Amin Shiraz"

Quantum Algorithms and the Power of Forgetting

Abstract

Cite as

Thanks for your feedback!

Could not send message