1 Search Results for "DeLorenzo, Kai"

Document
DOI: 10.4230/LIPIcs.TQC.2019.6
Applications of the Quantum Algorithm for st-Connectivity

Authors: Kai DeLorenzo, Shelby Kimmel, and R. Teal Witter

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
We present quantum algorithms for various problems related to graph connectivity. We give simple and query-optimal algorithms for cycle detection and odd-length cycle detection (bipartiteness) using a reduction to st-connectivity. Furthermore, we show that our algorithm for cycle detection has improved performance under the promise of large circuit rank or a small number of edges. We also provide algorithms for detecting even-length cycles and for estimating the circuit rank of a graph. All of our algorithms have logarithmic space complexity.
Cite as

Kai DeLorenzo, Shelby Kimmel, and R. Teal Witter. Applications of the Quantum Algorithm for st-Connectivity. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{delorenzo_et_al:LIPIcs.TQC.2019.6,
  author =	{DeLorenzo, Kai and Kimmel, Shelby and Witter, R. Teal},
  title =	{{Applications of the Quantum Algorithm for st-Connectivity}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.6},
  URN =		{urn:nbn:de:0030-drops-103984},
  doi =		{10.4230/LIPIcs.TQC.2019.6},
  annote =	{Keywords: graphs, algorithms, query complexity, quantum algorithms, span programs}
}
  • Refine by Author
  • 1 DeLorenzo, Kai
  • 1 Kimmel, Shelby
  • 1 Witter, R. Teal

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Quantum query complexity

  • Refine by Keyword
  • 1 algorithms
  • 1 graphs
  • 1 quantum algorithms
  • 1 query complexity
  • 1 span programs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact