QuantumÊAlgorithmÊforÊDirectedÊGraphÊConnectivity
Abstract
As quantum computers approach large scale implementation, it is important to develop and understand fast quantum algorithms for real world problems. We propose to design and analyze a quantum algorithm for directed graph connectivity. This is a problem which is both useful in its own right, but which also has implications for understanding the nature of quantum speed-ups in a wide range of applications. This project will attempt to extend the existing quantum algorithm for undirected st-connectivity (Belovs and Reichardt, 2012) to the problem of directed st-connectivity. Undirected st-connectivity is the problem of deciding whether or not two points in an undirected graph are connected. Not only is st-connectivity one of the most fundamental problems in graph theory, but the quantum algorithm for undirected st-connectivity has proven to be an important building block for the understanding and design of many new quantum algorithms. It is our hope that finding an algorithm for the more general case of directed st-connectivity (that is, deciding whether two points are connected in a directed graph) will both provide new insight into the existing applications for st-connectivity and also broaden the scope of possible applications.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2019
- Source ID
- W911NF1810286
Entities
People
- Shelby Kimmel
Organizations
- Army Contracting Command
- Middlebury College
- United States Army