Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs

Details Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs

2003-03-20

arxiv.org/abs/quant-ph/0303131v1

Physics

Quantum Physics

9 pages, to be submitted

Scientific paper

Quantum algorithms for several problems in graph theory are considered. Classical algorithms for finding the lowest weight path between two points in a graph and for finding a minimal weight spanning tree involve searching over some space. Modification of classical algorithms due to Dijkstra and Prim allows quantum search to replace classical search and leads to more efficient algorithms. In the case of highly asymmetric complete bipartite graphs, simply replacing classical search with quantum search leads to a faster quantum algorithm. A fast quantum algorithm for computing the diameter of a complete graph is also given.

Affiliated with

Also associated with

No associations

Rating

Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-205201