License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2023.5
URN: urn:nbn:de:0030-drops-183151
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18315/
Go to the corresponding LIPIcs Volume Portal

Jeffery, Stacey ; Kimmel, Shelby ; Piedrafita, Alvaro

Quantum Algorithm for Path-Edge Sampling

pdf-format:
LIPIcs-TQC-2023-5.pdf (1 MB)

Abstract

We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix, and show that this can be done in query complexity that is asymptotically the same, up to log factors, as the query complexity of detecting a path between s and t. We use this path sampling algorithm as a subroutine for st-path finding and st-cut-set finding algorithms in some specific cases. Our main technical contribution is an algorithm for generating a quantum state that is proportional to the positive witness vector of a span program.

BibTeX - Entry

@InProceedings{jeffery_et_al:LIPIcs.TQC.2023.5,
  author =	{Jeffery, Stacey and Kimmel, Shelby and Piedrafita, Alvaro},
  title =	{{Quantum Algorithm for Path-Edge Sampling}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{5:1--5:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18315},
  URN =		{urn:nbn:de:0030-drops-183151},
  doi =		{10.4230/LIPIcs.TQC.2023.5},
  annote =	{Keywords: Algorithm design and analysis, Query complexity, Graph algorithms, Span program algorithm, Path finding, Path detection}
}

Keywords: Algorithm design and analysis, Query complexity, Graph algorithms, Span program algorithm, Path finding, Path detection
Collection: 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Issue Date: 2023
Date of publication: 18.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI