Applications of the Quantum Algorithm for st-Connectivity

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 2019
Accession Number
AD1093300

Entities

People

  • Kai Delorenzo
  • R. T. Witter
  • Shelby Kimmel

Organizations

  • Middlebury College

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Capacitance
  • Circuits
  • Coding
  • Computer Programs
  • Computer Science
  • Computers
  • Detection
  • Electrical Circuits
  • Equations
  • Graph Theory
  • Notation
  • Quantum Algorithms
  • Quantum Computing
  • Random Walk
  • Resistance
  • Weighting Functions

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Quantum Computing
  • Space
  • Space - Space Objects