効率的量子アルゴリズムの設計手法

• Item type: Trans(1)
• 公開日: 2002-09-15
• タイトル: 効率的量子アルゴリズムの設計手法
• タイトル / 言語: en
• タイトル: How to Design Efficient Quantum Algorithms
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 量子計算特集
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 電気通信大学
• 著者所属(英): en
• 著者所属(英): The University of Electro - Communications
• 著者名: 西野, 哲朗
• 著者名(英): Tetsuro, Nishino
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 1985年にDavid Deutschは，量子並列計算が実行できるuring 機械として，量子uring機械（以下QTM と略す）を導入した．QTM上で実行されるアルゴリズムを量子アルゴリズムという．1994年にPeter Shorが，整数の因数分解に対する多項式時間量子アルゴリズムを設計したことはよく知られている．本論では，ShorのアルゴリズムとGroverのアルゴリズムを具体例として，効率的量子アルゴリズムを設計するための2つの主要な手法を説明する．さらに，これらの手法は，種々の効率的量子アルゴリズムの設計に幅広く用いられていることも示す．一方，近年多くの研究者が量子コンピュータの物理的実現法について研究を行っている．なかでも，NMR（核磁気共鳴）が，いくつかの理由により，量子コンピュータの実現方法として有望視されている．しかし，NMR上で実行される量子計算は，通常のQTM 上の量子計算とは若干異なる．たとえば，NMR量子コンピュータ上では，Shorのアルゴリズムはそのままでは動作しない．本論では，NMR量子コンピュータ上で実行される効率的なアルゴリズムの設計法も示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In 1985, David Deutsch introduced quantum uring machines (QTMs for short)as uring machines which can perform so called quantum parallel computations. Algorithms executed on QTMs are called quantum algorithms. It is well known that Peter Shor designed a polynomial time quantum algorithm for integer factoring in 1994. In this paper, we first illustrate two major methods of designing efficient quantum algorithms with Shor ’s algorithm and Grover’s algorithm as examples. Furthermore, we show that these methods are widely used to design various efficient quantum algorithms. On the other hand, many researchers are studying how to physically implement quantum computers based on the QTM these days. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computations performed on NMR is slightly different from those performed on QTMs. For example, Shor’s algorithm cannot be executed on an NMR quantum computer as it is. In this paper, we also show how to design efficient algorithms executed on NMR quantum computers.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 43, 号 SIG07(TOM6), p. 1-9, 発行日 2002-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会