DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
AD1093300
Title:
Applications of the Quantum Algorithm for st-Connectivity
Corporate Author:
Middlebury College Middlebury United States
Report Date:
2019-06-01
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.
Descriptive Note:
Journal Article - Open Access
Supplementary Note:
Applications of the Quantum Algorithm for , 6, 01 Jan 0001, 01 Jan 0001,
Pages:
0014
Distribution Statement:
Approved For Public Release;
File Size:
0.48MB
