量子コンピュータ 計算能力

量子コンピュータ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/01 22:50 UTC 版)

計算能力

理論

ヴァジラーニらは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。したがって、計算可能性の点では既存のあらゆるコンピュータと量子チューリングマシンは変わらない。つまり、量子チューリングマシンで「計算可能」な問題は古典チューリングマシンでも「計算可能」であるし、古典チューリングマシンで「計算可能」でない問題は量子チューリングマシンでも「計算可能」でない。(なお、ここで「計算可能」というのは、計算理論の専門用語であって、「原理的に解くことができない」というような表現から一般の人がイメージするような素朴な印象はおそらくたいていは正確ではない)

計算可能性の理論に関しては以上のようであるのだが、では、計算複雑性の理論としてはどうだろうか、というのが関心のある所であろう。

量子コンピュータは容易に古典コンピュータをエミュレートすることが可能であるため、古典コンピュータで速く解ける問題(汎用問題)は、量子コンピュータでも同程度以上に速く解くことができる。よって汎用問題について、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。ただし、同程度は可能だとしても、「より大きい」かどうかはよくわかっていない。

量子コンピュータに関係する複雑性クラスBQPがある。BQPとNPの関係は明確ではないが、BQPのほうが大きいだろうと考えられ、2010年代ころより、NPを含むPHにBQPが含まれない、ということを示唆する結果がいくつか示されてきている。

実際

量子ゲートマシンは理論的には古典コンピューターをシミュレート出来るとされるが、現実には古典ゲートによる小規模演算器もシミュレート出来ない。さらに、量子ゲート処理に必要な時間が論理回路より圧倒的に遅いこともあり、古典コンピュータの置き換えは不可能である。そのため、量子ゲートマシンは専用アルゴリズム開発と共に、古典コンピュータに対してある種の問題を高速に解く付加装置として利用するのが現実的である。

Googleは量子ゲートマシンの高速性が2017年末までに実証されると予想した[80]。古典コンピューターよりも実際の量子ゲートマシンの方が高速に解ける問題が存在することを、量子超越性と呼び、このような問題の探索が続けられている。2019年10月23日、Googleは、ランダムに作った量子回路の出力結果を推定すると言う問題で、量子超越性を実証したと発表した[81]

量子ゲートマシン上で素因数分解を行うショアのアルゴリズムは、2001年にIBMが世界で初めて15(=3×5)の分解に成功した[17]。2012年にブリストル大学が21(=3×7)の素因数分解を行い記録を更新したが[82]、21を超えるの数の素因数分解の報告はない(2019年9月時点)。

2017年現在始まっているIBM Q[83]などではごく限られた数の量子ビットしか扱えない。重ね合わせ状態を保ちデータを記憶する量子メモリが実現されていない事、量子複製不可能定理により、計算結果を使いまわすことができない事、複数の量子コンピューターを接続し計算規模を大きくする技術が実現していない事、量子ゲートに起因する誤差が蓄積する事などから、計算大規模化が困難である。従って、現状では、与えられた問題を解くことに使われる状態ではなく、既に提案されている小規模な量子アルゴリズムの実証から始め、量子コンピュータで解ける有用な問題の模索が続いている。

量子コンピュータとしては、量子ゲート型以外に、D-Waveなどの量子アニーリングやその他いくつかのタイプが提案されている、量子イジングマシンはQUBO(制約のない二値二次式の最適化)(英語版)に特化した専用計算機と言える。


  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