ステップが必要である。1996年にロブ・グローバー(英語版)が発表した[12][32]。広範な種類の確率的アルゴリズムや量子アルゴリズムと組み合わせて、計算時間をその平方根まで落とすことができる。ショアのアルゴリズムほどその効果は劇的ではないが、広い応用をもつことが特徴である。検索条件や検索対象について改良されている。量子ウォーク[編集]詳細は「量子ウォーク」を参照ランダムウォークを量子コンピュータ上で実行する。いくつかのアルゴリズムがこれを利用して作られている。離散フーリエ変換[編集]振幅に対して離散フーリエ変換を行うが、振幅は直接は観測できないことに注意が必要。ショアのアルゴリズムで使われている。QCLでのソースコードは以下の通り。離散フーリエ変換している。はアダマール変換である。i]);}flip(q);プログラミング言語[編集]量子コンピュータ用のプログラミング言語とその処理系の実装方法が多数提案されており、QCL[33]などがある。シミュレーター[編集]量子コンピュータのアルゴリズムをシミュレーションにより実行するためのシミュレーターが多数作られている。simulators[34]を参照。(NMR)や電子スピン共鳴を用いた量子コンピュータの研究開発が行われている[17][35][36][37][38]。2001年、7量子ビット量子コンピュータによる素因数分解が実装された[17][35]。より、1998年に2量子ビット、1999年に3量子ビット、2000年に5量子ビット、2001年に7量子ビット[36]、2005年に8量子ビットqubit[37]、2006年に12量子ビット[38]が実現した。1量子ビット増えるごとに並列度は2倍になる。[40]が主な研究拠点であり、核スピン・電子スピンを用いた量子情報処理の実験が行われている。シリコン中の核スピンを用いた量子情報処理実験が行われている。国内では理化学研究所[44]、東京大学[45]が主な研究拠点であり、量子コンピュータの実現に向けた取り組みがなされている。光子を用いているものは光子コンピュータ、光量子コンピュータとも呼ばれる。2001年、非線形光学を使わずに、量子コンピュータを作成する方法が考案された[46]。呼ばれ、その後の光量子コンピュータの主流となる。2007年、光子を使い、4qubit量子コンピュータによる素因数分解が実装された[18]。2009年、光集積回路(シリコンフォトニクス)上で、4qubit量子コンピュータによる素因数分解が実装された[19]。工学系研究科の古澤明教授と武田俊太郎助教のグループは、大規模光量子コンピュータ実現法を発明と告知[47]。超伝導素子を用いた量子コンピュータの量子ビットは、ジョセフソン・ジャンクションを用いた超伝導回路によって構成されている[48][49][50][51]。超伝導回路中の電荷(クーパー対)の自由度を用いた量子ビットを、電荷量子ビット、またはクーパー対箱と呼ぶ。1999年、日本電気において中村、Pashkin、蔡らにより実現された[48]。当時の量子ビットのコヒーレンス時間は約1ナノ秒であった。超伝導量子ビットは回路量子電磁力学(英語版)の研究とともに発展し、2004年にはコプラナ導波路により実装された超伝導共振器と電荷量子ビットとの強結合が観測されている[52]。共振器や導波路を組み合わせた回路量子電磁力学は、超伝導量子ビット間の相互作用や、量子非破壊測定を行うとても良いツールとなっている。SQUIDを含み、磁束量子の重ね合わせ状態を用いた量子ビットを磁束量子ビット(英語版)と呼ぶ。2003年、デルフト工科大においてChiorescu、中村、Harmans、Mooijらにより実現された[49]。これらはDWAVE社が開発した量子焼きなまし法による最適化手法[20][21]に採用されている。2007年に電荷量子ビットにおける電荷揺らぎ雑音を回避する量子ビットが提案され、トランズモン型量子ビット(英語版)と呼ばれる[53]。比較的シンプルな構成で長コヒーレンス時間が実現され、米国を中心に盛んに研究が進められている。2011年、量子計算や量子誤り訂正に必須となる単一試行の量子非破壊測定(英語版)が実現し、トランズモン型超伝導量子ビットの量子跳躍が観測されている[54]。これらの技術の背景には、標準量子限界に近い雑音指数を達成する低雑音増幅器(ジョセフソンパラメトリック増幅器)の実現がある[55][56]。2013年、上記の基礎技術とFPGAによる高速フィードバック処理により量子テレポーテーション[57]の実験が行われ、空間的に離れた量子ビット間の状態転送が実現した。2014年には160マイクロ秒のコヒーレンス時間が実現し[58]、1999年の発見から15年の間に約10万倍という飛躍的な改善がなされている。Martinis[59]らのグループは、誤り耐性符号の一つである表面符号(英語版)の誤りしきい値を下回る、高い忠実度の基本量子ゲートを実現した[60]。これにより誤り耐性量子計算が現実化し、超伝導量子ビットを用いた量子計算機の開発が一層加速することになる。2015年、9量子ビットによるビット反転エラー訂正(英語版)を実行し、論理量子ビットのエラー確率を物理量子ビットに比べ約1/8まで小さくすることに成功した[61]。同年には、新しい機能性材料の開発を飛躍的に加速する、フェルミ粒子のディジタル量子シミュレーションが、小さな系にて実装されている[62]。大規模化に向けた取り組みが始まり、2016年には三次元集積技術による実装が議論されている[63]。[67]が量子物理の研究を行っており、主な研究拠点である。海外ではGoogle[59]、IBM[68]、デルフト工科大学(インテル・マイクロソフトが支援)[69]、マサチューセッツ工科大学[70]、チューリッヒ工科大学[71]が主な研究拠点である。イオントラップ[編集]詳細は「イオン・トラップ型量子コンピュータ(英語版)」を参照イオントラップを用いる量子コンピュータでは、レーザー冷却によってイオンの捕捉とマニピュレーションを行なう。国内では阪大[72]にて量子シミュレータ・量子コンピュータに向けた研究がなされている。古典コンピュータでの計算は、ブール論理にもとづいた論理ゲートによる論理演算をベースとして行われる。これに対し、量子コンピュータの量子回路では、量子演算の演算子に対応する演算を行うゲートは量子ゲートと呼ばれ、ユニタリー行列でなくてはならない。任意の1量子ビットに対するユニタリー行列は以下の形式で表現できる。可逆計算であることも特徴である。この式を見ると分かる通り、量子ゲートは本質的にアナログ信号処理であり、アナログ処理に伴う誤差が問題となる点で、論理演算とは全く異なる。この事が量子コンピュータ実現上の最大の問題である。\end{pmatrix}}}1量子ビットに対する任意のユニタリー変換とCNOTゲートの組合せによって、n量子ビットの場合も任意のユニタリ変換を構成出来ることが知られている。NOT[編集]NOTはパウリ行列の1つでもある。}制御NOT[編集]CNOTと呼ばれる。はアダマール行列である。Phase[編集]CPhaseと呼ばれる。&{\mbox{otherwise}}\end{cases}}}1量子ビットの場合は、以下の通り。ヴァジラーニらは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。したがって、計算可能性の点では既存のあらゆるコンピュータと量子チューリングマシンは変わらない。量子チューリングマシンで「計算可能」な問題は古典チューリングマシンでも「計算可能」であるし、古典チューリングマシンで「計算可能」でない問題は量子チューリングマシンでも「計算可能」でない。(なお、ここで「計算可能」というのは、計算理論の専門用語であって、「原理的に解くことができない」というような表現から一般の人がイメージするような素朴な印象はおそらくたいていは正確ではない)計算可能性の理論に関しては以上のようであるのだが、では、計算複雑性の理論としてはどうだろうか、というのが関心のある所であろう。量子コンピュータは容易に古典コンピュータをエミュレートすることが可能であるため、古典コンピュータで速く解ける問題(汎用問題)は、量子コンピュータでも同程度以上に速く解くことができる。よって汎用問題について、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。同程度は可能だとしても、「より大きい」かどうかはよくわかっていない。量子コンピュータに関係する複雑性クラスにBQPがある。BQPとNPの関係は明確ではないが、BQPのほうが大きいだろうと考えられ、2010年代ころより、NPを含むPHにBQPが含まれない、ということを示唆する結果がいくつか示されてきている。実際[編集]量子ゲートマシンは理論的には古典コンピューターをシミュレート出来るとされるが、現実には古典ゲートによる小規模演算器もシミュレート出来ない。そのため、量子ゲートマシンの利用には専用アルゴリズム開発が必ず伴う。Googleは量子ゲートマシンの高速性が2017年末までに実証されると予想した[73]。supremacy)と呼び、このような問題の探索が続けられている。2019年10月23日、Googleは、ランダムに作った量子回路の出力結果を推定すると言う問題で、量子超越性を実証したと発表した[74]。量子ゲートマシン上で素因数分解を行うショアのアルゴリズムは、2001年にIBMが世界で初めて15(=3×5)の分解に成功した[17]。2012年にブリストル大学が21(=3×7)の素因数分解を行い記録を更新したが[75]、22以上の数の素因数分解の報告はない(2019年9月時点)。Q[76]などではごく限られた数の量子ビットしか扱えない。より、計算結果を使いまわすことができない事、複数の量子コンピューターを接続し計算規模を大きくする技術が実現していない事、量子ゲートに起因する誤差が蓄積する事などから、計算大規模化が困難である。従って、現状では、与えられた問題を解くことに使われる状態ではなく、既に提案されている小規模な量子アルゴリズムの実証から始め、量子コンピュータで解ける有用な問題の模索が続いている。量子コンピュータとしては、量子ゲート型以外に、D-Waveなどの量子アニーリングやその他いくつかのタイプが提案されている、量子イジングマシンはQUBO(制約のない二値二次式の最適化)(英語版)に特化した専用計算機と言える。一般的でない例としては、数は少ないが3状態の素子で動作するコンピュータや、多値論理の応用などとして研究されている。NANDフラッシュのように実用例も一部にはある。2017年4月1日閲覧。2017年4月1日閲覧。2017年4月1日閲覧。2017年4月1日閲覧。2017年4月1日閲覧。2017年4月1日閲覧。2017年4月1日閲覧。2017年4月1日閲覧。2017年4月1日閲覧。2017年4月1日閲覧。2017年4月1日閲覧。2016年6月17日閲覧。