量子コンピュータ ソフトウェア

量子コンピュータ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/19 00:40 UTC 版)

ソフトウェア

アルゴリズム

量子コンピュータ特有のアルゴリズムがいくつか知られており、伝統的に有名なものを示す。他の物は、Quantum Algorithm Zoo[34]などを参照。

ショアのアルゴリズム

ショアのアルゴリズム英語版: Shor's factorizationとも)とは、素因数分解問題を高速に(多項式時間で)解くことができるアルゴリズムのことである。古典コンピュータでは非現実的な時間(準指数時間)で解くアルゴリズムしか知られていない。1994年にピーター・ショアによって発見された[8][35]。ショアは本件で、ネヴァンリンナ賞ゲーデル賞を受賞した。

2001年12月にIBMアルマデン研究所にて7量子ビットの量子コンピュータで15 (= 3×5) の素因数分解に成功した(Nature, 12月20日発行号[17])。

少し改造することで離散対数問題(DLP, ElGamal暗号楕円曲線暗号の安全性の根拠)も多項式時間で解くことができる。このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。現在は、これをさらに非可換隠れ部分群問題に拡張する研究が進展している。

ショアのアルゴリズムは、量子コンピュータが離散フーリエ変換を高速に実行できることによる。また、アルゴリズム全体は確率的 (BQP) であり、正しい答えが得られるまで、何度も試行する。

N を素因数分解するにあたり、aN に対してな数とし、a の mod N に関する位数、min{x > 0|ax = 1 (mod N)} を求める。つまり、ax の周期 r を求める。位数が高速に求められれば、因数分解は高速に行える。

例えば、N = 15, a = 7 とする。

70 = 1 (mod 15)
71 = 7 (mod 15)
72 = 4 (mod 15)
73 = 13 (mod 15)
74 = 1 (mod 15)
75 = 7 (mod 15)
76 = 4 (mod 15)
77 = 13 (mod 15)
78 = 1 (mod 15)
79 = 7 (mod 15)

1,7,4,13,1,7,4,13,1,7,…という周期 4 の数列が生成される。

よって、周期 r = min{x > 0|7x = 1 (mod 15)} = 4

手順の概略は以下の2つ。

  1. 全ての x に対して、均等な確率となるように初期化する。そして、それを ax mod N のみ確率を持ち、それらは均等になるように変換する。この計算は量子コンピュータ的であるものの、基本的な考えは古典コンピュータと変わらない。そのために、2進数の足し算・引き算や、ビットによる条件分岐などを用意する。
  2. ax mod N は周期 r を持つ。この周期が求める位数である。従って、1で得られた結果を離散フーリエ変換する。すると、周波数 1/r のところの確率が大きくなるので、観測すると、高い確率で r が得られる。失敗した場合は、成功するまで繰り返す。

グローバーのアルゴリズム

n 個のデータの中から、ある特定のデータを n ステップで取得することができるアルゴリズム。正確には、1 から N のある一つの値で、オラクル関数 f(z) が 1 になり、それ以外は f(z) = 0 となる、オラクル関数 f において、f(z) = 1 となる z を求める問題。オラクル関数とは計算量が 0 の関数である。古典コンピュータではおよそ n/2 ステップが必要である。1996年にロブ・グローバー英語版が発表した[12][36]。きわめて広範な種類の確率的アルゴリズムや量子アルゴリズムと組み合わせて、計算時間をその平方根まで落とすことができる。ショアのアルゴリズムほどその効果は劇的ではないが、広い応用をもつことが特徴である。検索条件や検索対象について改良されている。

このアルゴリズムはデータ数に見合うだけ十分な量子ビット数があることを前提としているが、古典コンピュータにおいてデータに見合うだけの十分な並列度がある場合、f(z) = 1 を探すのは O(1) であり、関数の最小値を探す問題は、O(log log n) である。

ドイッチュ・ジョサのアルゴリズム

量子ウォーク

ランダムウォークを量子コンピュータ上で実行する。いくつかのアルゴリズムがこれを利用して作られている。

離散フーリエ変換

振幅に対して離散フーリエ変換を行うが、振幅は直接は観測できないことに注意が必要。ショアのアルゴリズムで使われている。QCLでのソースコードは以下の通り。変数 q を離散フーリエ変換している。V は conditional phase、H はアダマール変換である。

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

プログラミング言語

量子コンピュータ用のプログラミング言語とその処理系の実装方法が多数提案されており、QCL[37]などがある。詳細は、量子プログラミング言語 を参照。

シミュレーター

量子コンピュータのアルゴリズムをシミュレーションにより実行するためのシミュレーターが多数作られている。一覧については、List of QC simulators[38]を参照。


  1. ^ 一般的でない例としては、数は少ないが3状態の素子で動作するコンピュータや、多値論理の応用などとして研究されている。MLC NANDフラッシュのように実用例も一部にはある。
  2. ^ Paul Benioff (1980年5月). “The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines” (English). J. Stat. Phys.英語版. doi:10.1007/BF01011339. 2017年4月1日閲覧。
  3. ^ Richard Feynman , Peter W. Shor (1982年). “Simulating Physics with Computers” (English). SIAMコンピュータジャーナル英語版. 2017年4月1日閲覧。
  4. ^ David Deutsch (1985年). “Quantum theory, the Church-Turing principle and the universal quantum computer” (English). ペンシルベニア州立大学. 2017年4月1日閲覧。
  5. ^ Royal Society (1989年9月8日). “Quantum computational networks”. JSTOR. 2017年4月1日閲覧。
  6. ^ Deutsch, David; Jozsa, Richard (1992年12月). “Rapid Solution of Problems by Quantum Computation” (English). Astrophysics Data System. doi:10.1098/rspa.1992.0167. 2017年4月1日閲覧。
  7. ^ Ethan Bernstein , Umesh Vazirani (1993年). “Quantum complexity theory” (English). ペンシルベニア州立大学. doi:10.1.1.144.7852. 2017年4月1日閲覧。
  8. ^ a b Peter W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", In Proceeding of 35th IEEE FOCS, pp.124-134, Santa Fe, NM, Nov 20-22, 1994. (ショアのアルゴリズムの論文)
  9. ^ Daniel R. Simon (1994年). “On the Power of Quantum Computation”. ペンシルベニア州立大学. doi:10.1.1.51.5477. 2017年4月1日閲覧。
  10. ^ Andrew Steane (1996年5月13日). “Multiple Particle Interference and Quantum Error Correction” (English). コーネル大学図書館英語版. コーネル大学. doi:10.1098 / rspa.1996.0136. 2017年4月1日閲覧。
  11. ^ A. R. Calderbank, Peter W. Shor (1996年4月16日). “Good Quantum Error-Correcting Codes Exist” (English). コーネル大学図書館. コーネル大学. doi:10.1103/PhysRevA.54.1098. 2017年4月1日閲覧。
  12. ^ a b Lov K. Grover, "A fast quantum mechanical algorithm for database search", STOC'96, pp. 212–219, Philadelphia, Pennsylvania, United States, May 22-24, 1996. (グローバーのアルゴリズムの論文)
  13. ^ Serge Haroche, Jean-Michel Raimond & Michel Brune ; Le chat de Schrödinger se prête à l'expérience - Voir en direct le passage du monde quantique au monde classique, La Recherche 301 (Septembre 1997) 50 (disponible en ligne)
  14. ^ Serge Haroche ; Une exploration au cœur du monde quantique, dans : Qu'est-ce que l'Univers ?, Vol. 4 de l'Université de Tous les Savoirs (sous la direction d'Yves Michaux), Odile Jacob (2001) 571.
  15. ^ Edward Farhi (MIT), Sam Gutmann (Northeastern) (1998年3月20日). “Quantum Computation and Decision Trees” (English). コーネル大学図書館. コーネル大学. doi:10.1103/PhysRevA.58.915. 2017年4月1日閲覧。
  16. ^ Christopher R. Monroe en David J. Wineland. (2008年8月11日). “Quantum Computing with Ions” (English). サイエンティフィック・アメリカン. 2017年4月1日閲覧。
  17. ^ a b c d e Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance”. 2016年6月17日閲覧。
  18. ^ a b Demonstration of Shor's quantum factoring algorithm using photonic qubits
  19. ^ a b Shor's Quantum Factoring Algorithm on a Photonic Chip
  20. ^ a b Learning to program the D-Wave One”. 2013年6月閲覧。
  21. ^ a b Sergio Boixo, Tameem Albash, Federico M. Spedalieri, Nicholas Chancellor & Daniel A. Lidar. “Experimental signature of programmable quantum annealing” (English). ネイチャー. doi:10.1038/ncomms3067. 2013年6月閲覧。
  22. ^ Steven Rich; Barton Gellman (2014年1月3日). “NSA seeks to build quantum computer that could crack most types of encryption” (English). The Washington Post. http://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_story.html?hpid=z1 2014年1月9日閲覧。 
  23. ^ 中田 敦(日経コンピュータ) (2014年9月3日). “米グーグル、量子コンピュータの独自開発に乗り出す”. ITpro (日経BP). オリジナルの2014年9月3日時点におけるアーカイブ。. https://web.archive.org/web/20140903103138/http://itpro.nikkeibp.co.jp/atcl/news/14/090300706/ 2017年4月1日閲覧。 
  24. ^ ニューヨーク州ヨークタウンハイツの研究所に存在する。
  25. ^ “「誰でも使える量子コンピューター」IBMが公開する意味”. WIRED (コンデナスト・パブリケーションズ). (2016年5月9日). オリジナルの2016年5月9日時点におけるアーカイブ。. https://web.archive.org/web/20160509002016/http://wired.jp/2016/05/09/ibm-letting-anyone-play-quantum-computer/ 2017年4月1日閲覧。 
  26. ^ IBM Builds Its Most Powerful Universal Quantum Computing Processors IBM News Release 2017年5月17日
  27. ^ IBM unveils world's first commercial quantum computer The Telegraph 2019年1月8日
  28. ^ The Morning After: Google claims 'quantum supremacy'”. engadget (2019年10月24日). 2019年10月25日閲覧。
  29. ^ 米グーグル、「量子超越性」達成と発表 スパコン超える”. ロイター (2019年10月23日). 2019年10月25日閲覧。
  30. ^ [1]
  31. ^ 株式会社インプレス (2021年11月18日). “東大、万能な「光量子プロセッサ」を開発” (日本語). PC Watch. 2021年11月18日閲覧。
  32. ^ 大規模光量子コンピューターに現実味 NTTが新光源モジュール(2021年12月23日)”. 2021年12月26日閲覧。
  33. ^ 世界初、ラックサイズで大規模光量子コンピュータを実現する基幹技術開発に成功(2021年12月22日)”. 理化学研究所. 2021年12月26日閲覧。
  34. ^ https://quantumalgorithmzoo.org/
  35. ^ Peter W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing, Vol.26, No.5, pp.1484-1509, Oct 1997. (ジャーナル版)
  36. ^ Lov K. Grover, "Rapid sampling though quantum computing", STOC'00, pp. 618–626, Portland, Oregon, United States, May 21-23, 2000. (グローバーの新アルゴリズム)
  37. ^ http://tph.tuwien.ac.at/~oemer/qcl.html
  38. ^ http://www.quantiki.org/wiki/index.php/List_of_QC_simulators
  39. ^ a b IBM's Test-Tube Quantum Computer Makes History”. 2016年6月17日閲覧。
  40. ^ a b 【レポート】量子コンピュータとは(2) - 鉄腕アトムの時代に向けて”. 2016年6月17日閲覧。
  41. ^ a b 量子バイトを実現――量子コンピューティングへの大きな一歩”. 2016年6月17日閲覧。
  42. ^ a b “Benchmarking quantum control methods on a 12-Qubit system”. Phys. Rev. Lett. 96: 170501. (2006). doi:10.1103/PhysRevLett.96.170501. http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.96.170501. 
  43. ^ 大阪大学 基礎工学研究科 システム創成専攻 量子情報デバイス研究室”. 2016年5月13日閲覧。
  44. ^ 沖縄科学技術大学院大学 量子ダイナミクスユニット”. 2016年5月14日閲覧。
  45. ^ 横浜国立大学 大学院 工学研究院 物理情報工学専攻”. 2016年5月13日閲覧。
  46. ^ 京都大学 化学研究所”. 2016年5月13日閲覧。
  47. ^ 慶應義塾大学理工学部物理情報工学科”. 2016年5月13日閲覧。
  48. ^ 量子機能システム研究グループ”. 2016年5月13日閲覧。
  49. ^ 東京大学大学院 工学系研究科 物理工学専攻”. 2016年5月13日閲覧。
  50. ^ A scheme for efficient quantum computation with linear optics
  51. ^ [2] 東京大学 科学技術振興機構(JST)平成29年9月22日
  52. ^ The new light-based quantum computer Jiuzhang has achieved quantum supremacy”. 2020年10月3日閲覧。
  53. ^ 東京大学大学院工学系研究科物理工学専攻 古澤研究室”. 2020年8月21日閲覧。
  54. ^ 東京理科大学理学部物理学科 佐中研究室”. 2020年8月21日閲覧。
  55. ^ a b Nakamura, Yasunobu; Pashkin, Yu. A.; Tsai, J. S. (April 29, 1999). “Coherent control of macroscopic quantum states in a single-Cooper-pair box”. Nature 398: 786-788. doi:10.1038/19718. http://www.nature.com/nature/journal/v398/n6730/full/398786a0.html. 
  56. ^ a b Chiorescu, I.; Nakamura, Y.; Harmans, C. J. P. M.; Mooij, J. E. (Mar 21, 2003). “Coherent Quantum Dynamics of a Superconducting Flux Qubit”. Science 299: 1869-1871. doi:10.1126/science.1081045. http://science.sciencemag.org/content/299/5614/1869. 
  57. ^ Clarke, John; Wilhelm, Frank (June 19, 2008). “Superconducting quantum bits”. Nature 453: 1031-1042. doi:10.1038/nature07128. http://www.nature.com/nature/journal/v453/n7198/full/nature07128.html. 
  58. ^ Kaminsky, William M (2004). "Scalable Superconducting Architecture for Adiabatic Quantum Computation". arXiv:quant-ph/0403090
  59. ^ “Strong coupling of a single photon to a superconducting qubit using circuit quantum electrodynamics”. Nature 431: 162-167. (2004). doi:10.1038/nature02851. http://www.nature.com/nature/journal/v431/n7005/full/nature02851.html. 
  60. ^ “Charge-insensitive qubit design derived from the Cooper pair box”. Phys. Rev. A 76: 042319. (2007). doi:10.1103/PhysRevA.76.042319. http://journals.aps.org/pra/abstract/10.1103/PhysRevA.76.042319. 
  61. ^ “Observation of Quantum Jumps in a Superconducting Artificial Atom”. Phys. Rev. Lett. 106: 110502. (2011). doi:10.1103/PhysRevLett.106.110502. http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.106.110502. 
  62. ^ “Nonlinearities and parametric amplification in superconducting coplanar waveguide resonators”. Appl. Phys. Lett. 90: 253509. (2007). http://scitation.aip.org/content/aip/journal/apl/90/25/10.1063/1.2750520. 
  63. ^ “Flux-driven Josephson parametric amplifier”. Appl. Phys. Lett. 93: 042510. (2008). http://scitation.aip.org/content/aip/journal/apl/93/4/10.1063/1.2964182. 
  64. ^ “Deterministic quantum teleportation with feed-forward in a solid state system”. Nature 500: 319-322. (2013). doi:10.1038/nature12422. http://www.nature.com/nature/journal/v500/n7462/full/nature12422.html?WT_ec_id=NATURE-20130815. 
  65. ^ Excited state population of a 3D transmon in thermal equilibrium”. 2016年5月13日閲覧。
  66. ^ a b Martinis Group”. 2018年7月28日閲覧。
  67. ^ “Superconducting quantum circuits at the surface code threshold for fault tolerance”. Nature 508: 500-503. (2014). doi:10.1038/nature13171. http://www.nature.com/nature/journal/v508/n7497/abs/nature13171.html. 
  68. ^ Kelly, J.; Barends, R.; Fowler, A. G.; Martinis, John M; et, al. (2015). “State preservation by repetitive error detection in a superconducting quantum circuit”. Nature 519: 66-69. doi:10.1038/nature14270. http://www.nature.com/nature/journal/v519/n7541/abs/nature14270.html. 
  69. ^ “Digital quantum simulation of fermionic models with a superconducting circuit”. Nature Communications 6: 7654. (2015). doi:10.1038/ncomms8654. http://www.nature.com/ncomms/2015/150708/ncomms8654/full/ncomms8654.html. 
  70. ^ 3D Integration for Superconducting Qubits”. 2016年5月13日閲覧。
  71. ^ 東京大学 先端科学技術研究センター 量子情報物理工学分野”. 2016年5月13日閲覧。
  72. ^ 理化学研究所 創発物性科学研究センター 超伝導量子エレクトロニクス研究チーム”. 2018年7月28日閲覧。
  73. ^ NTT物性科学基礎研究所”. 2018年7月28日閲覧。
  74. ^ 情報通信研究機構 未来ICT研究所 フロンティア創造総合研究室”. 2016年5月13日閲覧。
  75. ^ IBM Quantum Computing”. 2018年7月28日閲覧。
  76. ^ デルフト工科大学 Superconducting quantum circuits”. 2018年7月28日閲覧。
  77. ^ マサチューセッツ工科大学 Superconducting Circuits and Quantum Computation group”. 2018年7月28日閲覧。
  78. ^ チューリッヒ工科大学 Quantum Device Lab”. 2018年7月28日閲覧。
  79. ^ 大阪大学 大学院基礎工学研究科 電子光科学領域 量子エレクトロニクスグループ”. 2016年5月14日閲覧。
  80. ^ Google Plans to Demonstrate the Supremacy of Quantum Computing” (英語). IEEE Spectrum: Technology, Engineering, and Science News. 2019年8月31日閲覧。
  81. ^ Quantum Supremacy Using a Programmable Superconducting Processor” (英語). Google AI Blog. 2019年10月24日閲覧。
  82. ^ O'Brien, Jeremy L.; Zhou, Xiao-Qi; Roberto Alvarez; Lawson, Thomas; Laing, Anthony; Martín-López, Enrique (2012-11). “Experimental realization of Shor's quantum factoring algorithm using qubit recycling” (英語). Nature Photonics 6 (11): 773–776. doi:10.1038/nphoton.2012.259. ISSN 1749-4893. https://www.nature.com/articles/nphoton.2012.259. 
  83. ^ https://www.research.ibm.com/ibm-q/






量子コンピュータと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

量子コンピュータのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



量子コンピュータのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの量子コンピュータ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2022 GRAS Group, Inc.RSS