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

IPSJ Web Site 8 References

Bibliographic Information

Other Title
  • コウリツテキ リョウシ アルゴリズム ノ セッケイ シュホウ
  • How to Design Efficient Quantum Algorithms

Search this article

Abstract

1985年にDavid Deutschは，量子並列計算が実行できるuring 機械として，量子uring機械（以下QTM と略す）を導入した．QTM上で実行されるアルゴリズムを量子アルゴリズムという．1994年にPeter Shorが，整数の因数分解に対する多項式時間量子アルゴリズムを設計したことはよく知られている．本論では，ShorのアルゴリズムとGroverのアルゴリズムを具体例として，効率的量子アルゴリズムを設計するための2つの主要な手法を説明する．さらに，これらの手法は，種々の効率的量子アルゴリズムの設計に幅広く用いられていることも示す．一方，近年多くの研究者が量子コンピュータの物理的実現法について研究を行っている．なかでも，NMR（核磁気共鳴）が，いくつかの理由により，量子コンピュータの実現方法として有望視されている．しかし，NMR上で実行される量子計算は，通常のQTM 上の量子計算とは若干異なる．たとえば，NMR量子コンピュータ上では，Shorのアルゴリズムはそのままでは動作しない．本論では，NMR量子コンピュータ上で実行される効率的なアルゴリズムの設計法も示す．

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.

Journal

References(8)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top