Accession Number:

AD1093300

Title:

Applications of the Quantum Algorithm for st-Connectivity

Descriptive Note:

Journal Article - Open Access

Corporate Author:

Middlebury College Middlebury United States

Personal Author(s):

• DeLorenzo,Kai
• Kimmel,Shelby
• Witter,R. T.

Report Date:

2019-06-01

Pagination or Media Count:

14.0

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.

Descriptors:

• algorithms
• quantum theory
• graphs
• computations

Subject Categories:

• Quantum Theory and Relativity

Distribution Statement:

APPROVED FOR PUBLIC RELEASE