量子コンピュータ Quantum Computers

提供: フリー百科事典『ウィキペディア（Wikipedia）』 Provided: material may be challenged Wikipedia encyclopedia (Wikipedia) 』

移動: ナビゲーション , 検索 Jump to: navigation, search

量子コンピュータ （りょうし-）は、量子力学的な重ね合わせを用いて並列性を実現する次世代のコンピュータ。 Quantum computer (hunter -) is a computer in the next generation to achieve parallelism using a total of layers of quantum mechanics. 2009年現在、実用的なレベルでのハードウェアの実現には至っていない。 Current year 2009, the realization of a practical hardware level is not reached. 量子計算機とも言う。 Also known as quantum computing.

目次 Contents

[ 編集 ] 概要 Summary

従来の計算機（量子計算機に対して、古典計算機という）は1 ビットにつき、0か1の何らかの値しか持ち得ないのに対して、量子計算機では量子ビット（qubit）により、1ビットにつき0と1の値を任意の割合で重ね合わせて保持することが可能である。 Conventional computer (for the quantum computer, calculator called classical) is one per bit, 0 or 1 only have some value for the impossible, and a calculator quantum quantum bit (qubit) by 0 and 1 bits per It is possible to hold any percentage of overlapping values.

n量子ビットあれば、 $2 n$ の状態を同時に計算できる。 If n qubits, $2 n$ states can be computed simultaneously. もし、数千qubitのハードウェアが実現したら、この量子ビットを複数利用して、量子計算機は古典計算機では実現し得ない超並列処理が実現する。 If the hardware that would be thousands of qubit, using multiple qubits, the quantum computer is a classical computer is a massively parallel processing to achieve the impossible a reality. 理論上、現在の最速スーパーコンピュータ (並列度が $220$ 以下)で数千年かかっても解けないような計算でも、例えば数十秒といった短い時間でこなすことができる。 Theoretically, the fastest supercomputer in the current (the degree of parallelism $220$ or less) in the calculation if it takes thousands of years to solve, and you can have done in such a short time of 10 seconds, for example.

従来型のノイマン型コンピュータはプログラムによってどのような計算でも実行できる汎用計算機であるのに対し、現時点での量子コンピュータは、特定のアルゴリズムを超高速に処理する専用計算機や、古典計算機を補助するコプロセッサとして考察されている。 Von Neumann computer, while traditional general-purpose computer that can run on any calculation by the program at this point the quantum computer, calculator and a dedicated high-speed processing algorithms in particular, co-calculator to assist classic are under review as the processor. 多くの量子計算機用のプログラミング言語はコプロセッサ方式を前提としている。 Quantum computer programming language for many system assumes that coprocessor.

[ 編集 ] 歴史 History

[ 編集 ] 1980年代 1980s

量子計算機の歴史は、 1980年にベニオフが量子系においてエネルギーを消費せず計算が行えることを示した^[1]ことに端を発し、 1982年、ファインマンも量子計算が古典計算に対し指数関数的に有効ではないかと推測している^[2] 。 History of quantum computing, 1980 showed that energy can not be calculated in the ^system quantum Benioff years [1] possibly stemmed from 1982, calculated against the exponential Feynman classical and quantum computation I guess that is not effective ^[2]. これらに続き、 1985年、ドイッチュによって、量子計算機の原モデルである量子チューリングマシン ^[3]を定義し、 1989年に量子回路^[4]を考案した。 Following these, in 1985, by Deutsch, quantum Turing machine model of the original ^machine quantum computation [3] to define the 1989 Integrated ^Quantum year [4] was devised.

[ 編集 ] 1990年代 1990s

1992年に、DeutschとJozsaにより、量子コンピュータが古典コンピュータよりも速く解ける問題が考案された^[5] 。 1992 years, Deutsch and Jozsa by, was designed to solve problems faster than classical computers Quantum computers ^[5]. 1993年に、BernsteinとVaziraniにより、万能量子チューリングマシンが記述され、翌年のShorのアルゴリズムで重要な役割を果たすフーリエ変換のアルゴリズムが考案された^[6] 。 1993 year, Bernstein and Vazirani by universal quantum Turing machine is described by the next year, Shor's algorithm was designed to play an important role in the Fourier transform algorithm ^[6].

初めて実用的なアルゴリズムを構築し、量子コンピュータの研究に火をつけたのは、 1994年にショアによって考案されたいわゆる、Shorのアルゴリズム^[7]である。 To build the first practical algorithm, set fire to the study of quantum computers, the 1994 so-called year was designed by Shore, Shor's algorithm ^[7] is. これは、同年のSimonの研究^[8]を基礎に置いている。 This is the year of Simon's ^[8] on the basis of that place. Shorのアルゴリズムは量子計算機特有のアルゴリズムであり、古典計算機では現実的な時間で解くことができないと予想されている素因数分解を、量子計算において極めて短い時間で解決することが出来ることが示されている。 Shor algorithm for machine-specific algorithms and quantum computation in classical computer is a factorization is not expected to be solved in real time, have been shown to be able to be resolved in a very short time in quantum computation that. このため、実用的な量子計算機が実現されれば、素因数分解の困難性を利用したRSA暗号の安全性が崩れることになる。 This is realized if a practical quantum computer, using the difficulty of factoring RSA that can break the encryption security.

1995年に、Andrew Steane ^[9]やPeter Shor ^[10]により、量子誤り訂正のアルゴリズムが考案された。 1995 years, Andrew Steane ^[9] and Peter Shor ^[10] by the invention of quantum error correction algorithms. 1996年に、Lov K. Groverにより、その後、様々なアルゴリズムに応用されるGroverのアルゴリズム^[11]が考案された。 1996 years, Lov K. Grover by, and then applied to various algorithms Grover's algorithm ^[11] was designed. 1997年に、FarhiとGutmannにより、量子ウォーク^[12]が考案された。 1997 years, Farhi and Gutmann by quantum walk ^{[12] was} designed to. 1998年に、量子コンピュータ用のプログラミング言語である、QCL(Quantum Computation Language)の実装が公開された。 In 1998, a programming language for quantum computers, QCL (Quantum Computation Language) implementation of the public.

[ 編集 ] 2000年代 2000s

ハードウェアに進展があった。 There was progress in the hardware. Shorのアルゴリズムは、 2001年に核磁気共鳴 ^[13]により、 2007年に量子光学 ^[14]により、 2009年に光集積回路 ^[15]により15の素因数分解 (=3*5)が実装された。 Shor's algorithm, the 2001 resonance magnetic nuclear weapons a year ^[13] by 2007 Satoru Akira Quantum year ^[14] by the 2009 Integrated Optical Circuits years ^[15] by the degradation 15 prime factors (= 3 * 5) was implemented .

[ 編集 ] 計算能力 computational capacity

AD バーンスタインとU. ヴァジラニは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。 AD Bernstein and U. Vajirani showed that the equivalent of the Turing machine could compute the classical and quantum Turing machine. したがって、古典チューリングマシンで原理的に解くことができない問題は量子チューリングマシンにも解くことはできない。 Therefore, the problem can be solved in principle in the classical Turing machine is a quantum Turing machine can also be solved.

量子コンピュータは古典コンピュータを容易にシミュレートすることが可能であるため、古典的なコンピュータで速く解ける問題は、量子コンピュータにも速く解くことができる。 Because of the quantum computer can easily simulate a classical computer, the problem is solved quickly in a classical computer can be faster on a quantum computer to solve. よって、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。 Thus, quantum computers classic computer "or" a powerful computational speed. ただし、「より大きい」計算速度を持つのかどうか（量子コンピュータにしか速く解けない問題が存在するのかどうか）は、 P≠NP予想という、現在のところ証明されていない予想に依存する。 However, "greater than" whether with the speed of calculation (whether the problem exists only to quickly solve computer quantum) is, P ≠ NP expect that depends on the forecast is not currently certified. Shorのアルゴリズムにより、 NP問題（検算はすぐにできるが、解くのに時間がかかる問題）である素因数分解を素早く解くことができるため、例えば素因数分解問題が古典コンピュータに多項式時間で解けないということを示せば量子コンピュータは古典コンピュータより強力であることになる。 Shor's algorithm, NP problem (recalculation is now available, take time to solve problems) can be solved quickly because the factorization, solvable in polynomial time on the computer that the classical problems such factorization示Se a quantum computer would be more powerful than a classical computer.

[ 編集 ] アルゴリズム Algorithm

量子計算機特有のアルゴリズムがいくつか知られており、古典的に有名なものを示す。 Several known quantum algorithms for specific computer, which shows the famous classic. 他の物は、 Quantum Algorithm Zooなどを参照。 Other things, Quantum Algorithm Zoo and see.

[ 編集 ] Shorのアルゴリズム Shor's algorithm

素因数分解問題を高速に（多項式時間で）解くことができるアルゴリズム。 Fast decomposition problem prime factor (in time polynomial) algorithm can be solved. 古典計算機では非現実的な時間（準指数時間）で解くアルゴリズムしか知られていない。 In classical computer unrealistic time (time subexponential) algorithms to solve not only the known. 1994年にShorによって発見された^[7] ^[16] 。 1994 was discovered by Shor ^[7] ^[16]. Shorは本件で、ネヴァンリンナ賞とゲーデル賞を受賞した。 Shor is the case, was awarded the Gödel Prize Nevanlinna.

2001年12月にIBMアルマデン研究所にて7qubitの量子計算機で15(=3*5)の素因数分解に成功した（Nature,12月20日発行号^[13] ）。 2001 In December IBM Almaden Research Center in quantum computing 7qubit at 15 (= 3 * 5) a successful factorization of (Nature, 12月No. 20, issued on ^[13]).

少し改造することで離散対数問題（DLP, ElGamal暗号や楕円曲線暗号の安全性の根拠）も多項式時間で解くことができる。 Discrete logarithm problem can be modified slightly (DLP, ElGamal grounds of safety of the encryption and elliptic curve cryptography) can also be solved in polynomial time. このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。 An extension of the basic idea of this algorithm, quantum algorithms for noncommutative hidden subgroup problem. 現在は、これをさらに非可換隠れ部分群問題に拡張する研究が進展している。 Currently, research is progressing to extend the noncommutative hidden subgroup problem this further.

[ 編集 ] 詳細 Details

Shorのアルゴリズムは、量子コンピュータが離散フーリエ変換を高速に実行できることによる。 Shor's algorithm is due to be executed quickly transform discrete Fourier quantum computer. また、アルゴリズム全体は確率的( BQP )であり、正しい答えが得られるまで、何度も試行する。 The entire algorithm is probabilistic (BQP) is, until you get the correct answer, try many times.

N を因数分解するにあたり、a は N に対して素な数とし、a の mod N に関する位数、 $min{x | a x = 1(mod N)}$ を求める。 Factoring a Niatari N, a is N and the number of iodine for, a place for the number of mod N, $min (x | a x = 1 (mod N))$ ask. つまり、 $a x$ の周期を求める。 In other words, $a x$ seek a period of. 位数が高速に求められれば、因数分解は高速に行える。 When asked to place the number of high-speed, high-speed factored into the can.

手順の概略は以下の2つ。 Two procedures are outlined below.

全ての x に対して、均等な確率となるように初期化する。 For all x, so that initialize equal probability. そして、それを And it $a ^ x ~ \ bmod N$ のみ確率を持ち、それらは均等になるように変換する。 Only have a chance, they will be converted to be equal. この計算は量子コンピュータ的であるものの、基本的な考えは古典コンピュータと変わらない。 Although this calculation is a quantum computer, the basic idea is no different from classical computers. そのために、2進数の足し算・引き算や、ビットによる条件分岐などを用意する。 Therefore, two of decimal addition and subtraction, and to provide a bit of a conditional branch.
$a ^ x ~ \ bmod N$ は周期 r を持つ。 R with the period. この周期が求める位数である。 Number of cycles required by this position. なので、1で得られた結果を離散フーリエ変換する。 So, one to the results obtained in the discrete Fourier transform. すると、周波数 1 / r のところの確率が大きくなるので、観測すると、高い確率で r が得られる。 Then the frequency 1 / r chance of it just grows, and to observe, with high probability r can be obtained. 失敗した場合は、成功するまで繰り返す。 If it fails, repeat until it succeeds.

[ 編集 ] Groverのアルゴリズム Grover's algorithm

詳細は「グローバーのアルゴリズム」を参照 See "algorithm Glover" section

$n$ 個のデータの中から、ある特定のデータを $n$ pieces of data from the data to a certain $\ sqrt n$ ステップで取得することができるアルゴリズム。 Algorithm can be obtained in one step. 正確には、1〜Nのある一つの値で、オラクル関数f(z)が1になり、それ以外はf(z) = 0となる、オラクル関数fにおいて、f(z) = 1となるzを求める問題。 Precisely, one in the value of 1 to N, the Oracle function f (z) is 1, and otherwise f (z) = 0 and the function f in Oracle, f (z) = 1 and z seeking problem. オラクル関数とは計算量が0の関数である。 Oracle functions and the amount of computation is a function of 0. 古典計算機ではおよそ $n / 2$ ステップが必要である。 In classical computer is about $n / 2$ steps is required. 1996年にグローバーが発表した^[11] ^[17] 。 1996 announced that Grover was ^[11] ^[17]. きわめて広範な種類の確率的アルゴリズムや量子アルゴリズムと組み合わせて、計算時間をその平方根まで落とすことができる。 In conjunction with the algorithm of quantum algorithms and an extremely wide variety of probability can be calculated down to the square root of time. Shorのアルゴリズムほどその効果は劇的ではないが、広い応用をもつことが特徴である。 Shor's algorithm is more dramatic effect, but it is characterized with a wide application. 検索条件や検索対象について改良されている。 Has been improved and the search for your search criteria.

このアルゴリズムはデータ数に見合うだけ十分なqubit数があることを前提としているが、古典コンピュータにおいてデータに見合うだけの十分な並列度がある場合、f(z) = 1 を探すのはO(1)であり、関数の最小値を探す問題は、O(log log n) である。 This algorithm is sufficient to justify the number of data qubit is assumed that there are few, if there is sufficient parallelism to meet the data in a classical computer, f (z) = 1 to find the O (1 ), and the problem of finding the minimum of the function, O (log log n) is.

[ 編集 ] 量子ウォーク Quantum Walk

ランダムウォークを量子コンピュータ上で実行する。 To perform a random walk on a quantum computer. いくつかのアルゴリズムがこれを利用して作られている。 Are made using some of this algorithm. 詳細は、 en:Quantum walkを参照。 For more information, en: Quantum walk information.

[ 編集 ] 離散フーリエ変換 Discrete Fourier Transform

振幅に対して離散フーリエ変換を行うが、振幅は直接は観測できないことに注意が必要。 To the discrete Fourier transform of the amplitude, the amplitude is necessary to note that you can not directly observable. Shorのアルゴリズムで使われている。 Shor's algorithm is used. QCLでのソースコードは以下の通り。 QCL source code is as follows. 変数 q を離散フーリエ変換している。 Q variables are the discrete Fourier transform. V は conditional phase、H はアダマール変換である。 V is a conditional phase, H is the Hadamard transform.

for i = 1 to #q { for i = 1 to # q (
  for j = 1 to i - 1 { for j = 1 to i - 1 (
    V ( pi / 2^ ( i - j ) , q [ #q - i ] & q [ #q - j ] ) ; V (pi / 2 ^ (i - j), q [# q - i] & q [# q - j]);
  } )
  H ( q [ #q - i ] ) ; H (q [# q - i]);
} )
flip ( q ) ; flip (q);

[ 編集 ] ハードウェア Hardware

実験的には、核磁気共鳴、量子光学、量子ドット、超伝導素子、レーザー冷却などによる実現法が研究されている。 Experimentally, the resonance magnetic nuclear, optics, quantum dot quantum, superconducting devices has been achieved by methods such as laser cooling research.

qubit数を増やすことは、課題を抱えている。 increase the number of qubit is challenged. 核磁気共鳴(NMR)により、1998年に2qubit、1999年に3qubit、2000年に5qubit、2001年に7qubit ^[18] 、2005年に8qubit ^[19] 、2006年に12qubit ^[20]が実現した。 Nuclear magnetic resonance (NMR) by 1998, 2qubit, 1999 was 3qubit, 2000 was 5qubit, 2001 was 7Qubit ^[18], 8Qubit year 2005 ^[19], 12Qubit year 2006 ^[20] was realized. 1qubit増えるごとに並列度は2倍になる。 1qubit parallelism is two-fold increase for each. ちなみに、古典コンピュータでは、集積度(並列度)を2倍にするのに約2年かかっていて、ムーアの法則と呼ばれる。 Incidentally, the classical computer, the density (degree of parallelism) to 2-fold to about two years they took, called the Law of Moore.

[ 編集 ] 核磁気共鳴 Nuclear Magnetic Resonance

2001年、7qubit量子コンピュータによる素因数分解が実装された^[13] ^[21] 。 2001, 7qubit factorization was implemented by a quantum computer ^[13] ^[21].

近年、核磁気共鳴（NMR; 例： [1] ）を用いた量子コンピュータの研究開発が行われている[2] 。 Recently, the resonance magnetic nuclear (NMR; example: [1]) is based on the research and development of quantum computers [2]. 関西では、京都大学、大阪市立大学や、近畿大学に設立された量子コンピューター研究センターなどで盛んに研究が行われている。 In Kansai, Kyoto University and Osaka City University, has been studied actively in the Research Center for Computer Kinki University was founded in Quantum.

[ 編集 ] 量子光学 Quantum Optics

2001年、非線形光学を使わずに、量子コンピュータを作成する方法が考案された^[22] 。 In 2001, the optics without using non-linear method was devised to create a quantum computer ^[22]. 線形光量子コンピュータ(Linear optical quantum computer; LOQC)と呼ばれ、その後の光量子コンピュータの主流となる。 Kazuko Akira computer linear (Linear optical quantum computer; LOQC) is called, then enter the mainstream of computer Kazuko Hikaru.

2007年、光子を使い、4qubit量子コンピュータによる素因数分解が実装された^[14] 。 2007, using a photon, 4qubit factorization was implemented by a quantum computer ^[14]. さらに、 2009年、光集積回路(シリコンフォトニクス)上で、4qubit量子コンピュータによる素因数分解が実装された^[15] 。 In addition, in 2009, photonic integrated circuits (silicon photonics) on, 4qubit factorization was implemented by a quantum computer ^[15].

[ 編集 ] 量子回路 Quantum Circuits

[ 編集 ] 量子ゲート Quantum gates

古典コンピュータには、ANDやORやNOTやXORなど、基本的な論理演算がある。 Classical computer, AND and OR and NOT and XOR, etc., there is a basic logical operations. それらは量子コンピュータでは量子ゲートに相当する。 They are equivalent to the quantum computer quantum gates. 量子ゲートはユニタリー行列でなくてはならない。 Quantum gates is not a matrix is not unitary.

任意の1量子ビットに対するユニタリー行列は以下の形式で表現できる。 Unitary matrix for any single qubit can be expressed in the form below.

$e ^ (i \ psi) \ begin (pmatrix) e ^ (i (- \ alpha - \ beta)) \ cos \ theta &-e ^ (i (- \ alpha + \ beta)) \ sin \ theta \ \ e ^ (i (\ alpha - \ beta)) \ sin \ theta & e ^ (i (\ alpha + \ beta)) \ cos \ theta \ end (pmatrix)$

[ 編集 ] NOT NOT

NOTはパウリ行列の1つでもある。 NOT is also one of the three Pauli matrices.

$X = NOT = \ begin (pmatrix) 0 & 1 \ \ 1 & 0 \ end (pmatrix)$

$X | x \ rangle = | \ tilde (x) \ rangle$

[ 編集 ] スワップ Swap

$S_ (10) = \ begin (pmatrix) 1 & 0 & 0 & 0 \ \ 0 & 0 & 1 & 0 \ \ 0 & 1 & 0 & 0 \ \ 0 & 0 & 0 & 1 \ end (pmatrix)$

$S_ (10) | x \ rangle | y \ rangle = | y \ rangle | x \ rangle$

[ 編集 ] 制御NOT controlled-NOT

CNOTと呼ばれる。 Called CNOT. XORに相当する。 Equivalent to XOR.

$C_ (10) = \ begin (pmatrix) 1 & 0 & 0 & 0 \ \ 0 & 1 & 0 & 0 \ \ 0 & 0 & 0 & 1 \ \ 0 & 0 & 1 & 0 \ end (pmatrix)$

$C_ (10) | x \ rangle | y \ rangle = | x \ rangle | y \ oplus x \ rangle$

[ 編集 ] パウリ行列 Pauli matrices

パウリ行列を参照。 See matrix Pauli.

$X = NOT = \ begin (pmatrix) 0 & 1 \ \ 1 & 0 \ end (pmatrix)$

$Y = \ begin (pmatrix) 0 &-i \ \ i & 0 \ end (pmatrix)$

$Z = \ begin (pmatrix) 1 & 0 \ \ 0 & -1 \ end (pmatrix)$

$\ sqrt (X) = \ sqrt (NOT) = H \ sqrt (Z) H = \ frac (1) (2) \ begin (pmatrix) 1 + i & 1-i \ \ 1-i & 1 + i \ end (pmatrix)$

$\ sqrt (Z) = \ begin (pmatrix) 1 & 0 \ \ 0 & i \ end (pmatrix)$

[ 編集 ] アダマール変換 Hadamard transform

アダマール行列である。 Matrix Hadamard.

$H = \ sqrt (\ frac (1) (2)) (X + Z) = \ sqrt (\ frac (1) (2)) \ begin (pmatrix) 1 & 1 \ \ 1 & -1 \ end (pmatrix)$

[ 編集 ] Conditional Phase Conditional Phase

CPhaseと呼ばれる。 CPhase called.

$V (\ phi): | x \ rangle \ to \ begin (cases) e ^ (i \ phi) | x \ rangle & \ mbox (if) x = 111 \ cdots \ \ | x \ rangle & \ mbox (otherwise ) \ end (cases)$

1量子ビットの場合は、以下の通り。 If one quantum bit is as follows.

$V (\ phi) = \ begin (pmatrix) 1 & 0 \ \ 0 & e ^ (i \ phi) \ end (pmatrix)$

[ 編集 ] 回転 Rotating

$U (\ theta) = \ begin (pmatrix) \ cos \ theta & - \ sin \ theta \ \ \ sin \ theta & \ cos \ theta \ end (pmatrix)$

[ 編集 ] トフォリゲート Toforigeto

Toffoliゲート。 Toffoli gate. 制御-制御NOTゲート(ccNOTゲート）ともいわれる。 Control - controlled-NOT gate (ccNOT gate) is also considered.

[ 編集 ] プログラミング言語 Programming languages

量子コンピュータ用のプログラミング言語とその処理系の実装が多数提案されており、 QCLなどがある。 Has been proposed to implement a number of systems that process and programming languages for quantum computers, QCL, among others. 詳細は、 en:Quantum programmingを参照。 For more information, en: Quantum Programming for more information.

[ 編集 ] シミュレーター Simulators

古典コンピュータ上で量子コンピュータのアルゴリズムを実行するためのシミュレーターが多数作られている。 Simulator is designed to perform many quantum computer algorithms on classical computers. 一覧については、 List of QC simulatorsを参照。 For a list, List of QC Simulators information.

[ 編集 ] 参考文献 References

[ 編集 ] 関連項目 See also

ビデオジャパンは、最大でランク。