A Quantum Algorithm for Minimum Steiner Tree Problem
| 言語 | 英語 |
|---|---|
| 種類 | 国際会議等の予稿 |
| 著者 | Masayuki Miyamoto，Masakazu Iwamura，Koichi Kise |
| 論文名 | A Quantum Algorithm for Minimum Steiner Tree Problem |
| 論文誌名 | Proc. 19th Asian Quantum Information Science Conference (AQIS2019) |
| ページ数 | 2 |
| 発表場所 | Seoul, Korea |
| 査読の有無 | 有 |
| 発表の種類 | ポスター発表 |
| 年月 | 2019年8月 |
| 分野 | 量子コンピューティング |
| キー | Miyamoto2019_AQISa (id=1680) |
要約
Minimum Steiner tree problem is a well-known NP-hard problem. For the minimum Steiner tree problem in graphs with $n$ vertices and $k$ terminals, there are many classical algorithms that take exponential time in $k$. In this paper, to the best of our knowledge, we propose the first quantum algorithm for the minimum Steiner tree problem. The complexity of our algorithm is $\mathcal{O}^*(1.812^k)$. A key to realize the proposed method is how to reduce the computational time of dynamic programming by using a quantum algorithm because existing classical (non-quantum) algorithms in the problem rely on dynamic programming. Fortunately, dynamic programming is realized by a quantum algorithm for the travelling salesman problem, in which Grover's quantum search algorithm is introduced. However, due to difference between their problem and our problem to be solved, recursions are different. Hence, we cannot apply their technique to the minimum Steiner tree problem in that shape. We solve this issue by introducing a decomposition of a graph proposed by Fuchs et al.
注記
関連ファイル
- …
この文献を出力
書式の定義
書式の定義の書き方
{authors} のように波括弧でフィールドを挿入します．[ ... ] で囲んだ部分は，その中のフィールドが空のとき丸ごと省略されます．使えるフィールド：
{authors}{authors_and}{authors_ja}{authors_ja_tight}{authors_en}{authors_en_and}{authors_tight}{first_author}{title}{title_ja}{title_en}{journal}{journal_ja}{journal_en}{book_title}{volume}{number}{series}{presen_id}{pages}{pp}{num_pages}{year}{month}{month_en}{month_short}{ym}{date}{date_ja}{date_en}{publisher}{address}{location}{review}{review_ja}{review_en}{reviewed_mark}{presen_type}{type}{type_label}{doi}{url}{key}{awards}