Quantum Speedup in Minimum Steiner Tree Problem
Explore the quantum speedup effects in the Minimum Steiner Tree Problem, a fundamental NP-hard problem in graph theory. Discover how quantum search algorithms and dynamic programming enhance the efficiency of finding minimum values in complex graphs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
QUANTUM SPEEDUP FOR THE MINIMUM STEINER TREE PROBLEM Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise, Fran ois Le Gall
The Minimum Steiner Tree Problem Input : undirected weighted graph ? = ?,?,? , weight function ?:? +, terminal set ? ?, where n = |?| and ? = |?|. Definition of ??? The weight of a minimum Steiner tree for ? (i.e., the minimum weight among all trees that contain ? .) Output : the weight ??? . One of the most fundamental NP-hard problems in the graph theory Many exponential time classical algorithms with respect to ? = |?| 1 1 3.5 3.5 4 4 4 4 3 3 2 2 Minimum Steiner Tree with weight ??? = 17 1.11 1.11 2 2 4 4 1 1 0.5 0.5 2 2 3 3 8 8 ? = ? = 4
Quantum Search Consider a function ?:? 0,1given as a black box. Black box ? ? ? ? 0,1 ?|?| ?? ?? ?? ? ? ? ? Find an element ? ? such that ? ? = 1 Classical : ?(|?|) calls to the black box Quantum : ?( |?|) calls to the black box [Grover 96] (Quantum Search)
Quantum Search for finding the minimum value Consider a function ?:? given as a black box. Black box ? ? ?(?) ?|?| ?? ?? ?? ??? ??.? ? ?.?? Find the minimum value min? ?? ? Classical : ?(|?|) calls to the black box Quantum : ?( |?|) calls to the black box [Durr and Hoyer 96] (using Quantum Search)
Quantum Search + Dynamic Programming [Ambainis+ 2018]: Combine classical dynamic programming alg. with quantum search. Quantum search using the information by classical dynamic programming TSP, Set Cover classical (best known): ? 2?poly ? quantum: ?(1.728?poly(?)) [Ambainis+ 2018] Graph Bandwidth classical (best known): ? 4.383?poly ? quantum: ?(2.946?poly(?)) [Ambainis+ 2018] Our Result: Time Complexity of The Minimum Steiner Tree Problem classical (best known): ?( 2 + ??poly(?)) for any ? > 0 [Fuchs+ 07] quantum: ?(1.812?poly(?))
?-split [Fuchs, Kern and Wang 07] ?-split of a tree ?: subtrees ?1,?2, ,?? that cover ?. (i.e., ? = ?1 ??) ?1 ?? is connected for all ? {1, ,?} ?1 ? ?2 ?3 3-split is used to construct ?(2.684?poly(?))-time algorithm [Fuchs, Kern and Wang 07]
?-split Recursion using 2-split: We use 2-split of a tree ?: subtrees ?1= ? ?1,? ?1 we call ? = ? ?1 ?(?2) the set of split nodes ?1 ? ?1 ?? ,?2= (? ?2,?(?2)) that cover ? min {???1 ? + ??/??2 ??} ? ? ? = ?(1) ??? = min Let ? be a minimum Steiner tree for the terminal set ? with ? = ?. For any ? (0,1/2) and ? (0,1), there exists a 2-split ?1,?2 of ? such that ? ?1 ? ?? and ? = ?(1). In the graph ?, ?1 is a minimum Steiner tree for ? ?1 ?. In the graph ?/?, ?2 is a minimum Steiner tree for ? ?2 ?. ?? Let ? be a minimum Steiner tree for the terminal set ? and ?1,?2 be a 2-split of ?. ? poly(?) accesses to the value Classical : Computing ??? : ?/? : (Graph contraction) Remove all edges in ? and replace all vertices in ? with a new vertex ?? ?? ? ?/? ? Quantum : accesses to the value A ?? poly(?) ? ?1 ? ?? means ? ? ? ? ?1 ? ? + ? ? for some small constant ?.
Outline of Our Algorithm I. Compute ???1 ? and ??/??1 ??for all ?1 ? and ? ? such that ?1 ?? (? 0.283 is a constant) 4, ? ?(1) using classical dynamic programming algorithm. Dreyfus-Wagner algorithm II. Compute ??(?) using quantum search on the recursion by 2-split, three times recursively. we have the database of all the values ???1 for all ?1 s.t. ?1 ?? 4
II. recursively. Compute ??(?) using quantum search on the recursion by 2-split, three times Minimum Steiner Tree for ? 2-split Subtree Subtree (terminal size ?/2) (terminal size ?/2) 2-split 2-split ?/4 ?/4 ?/4 ?/4 1 ? ? 4 1 ? ? 4 1 ? ? 4 1 ? ? 4 ??/4 ??/4 ??/4 ??/4 Computed in step 1.
Outline of Our Algorithm I. Compute ???1 ? and ??/??1 ??for all ?1 ? and ? ? such that ?1 ?? (? 0.283 is a constant) 4, ? ?(1) using classical dynamic programming algorithm. II. Compute ??(?) using quantum search on the recursion by 2-split, three times recursively. ?1 ? +1 ? ?poly ? 4 4 ? 2 = ?(1.812?poly ? )
Outline of Our Algorithm I. Compute ???1 ? and ??/??1 ??for all ?1 ? and ? ? such that ?1 ?? (? 0.283 is a constant) 4, ? ?(1) using classical dynamic programming algorithm. II. Compute ??(?) using quantum search on the recursion by 2-split, three times recursively. ? ?/2 ?/4 ?/4 ??/4 ?1 ? +1 ? ? poly ? + ?poly ? 4 4 ? 2 = ?(1.812?poly ? ) ?/2 = ?(1.812?poly ? )
Outline of Our Algorithm I. Compute ???1 ? and ??/??1 ??for all ?1 ? and ? ? such that ?1 ?? (? 0.283 is a constant) 4, ? ?(1) using classical dynamic programming algorithm. II. Compute ??(?) using quantum search on the recursion by 2-split, three times recursively. If we use ?-split where ? 2, the complexity becomes worse. If we use more recursive quantum search, the complexity becomes worse.
Conclusion We constructed ?(1.812?poly(?)) algorithm for the minimum Steiner tree problem using quantum search. (Faster than the best known classical algorithm) Open problem Further speeding up of the minimum Steiner tree Speeding up other NP-hard problems using quantum search
