集中講義／量子コンピュータ概論

量子コンピュータは，現代物理学の基礎をなす量子力学の原理に従って（最大限に活用して）動作するコンピュータである．近年のめざましい実験的進展に支え られ，量子コンピュータのための理論的な枠組みも発展をみせている．本講義では，量子コンピュータの仕組みを理解することを目標とし，量子コンピュータを 記述するために欠かせない量子力学・量子情報の基礎の導入，量子コンピュータによって可能になる量子アルゴリズムの紹介，そして，量子コンピュータの実装 において欠かせない量子誤り訂正とそれを用 いた誤り耐性量子コンピュータについて解説する．特に，M. A. Nielsen と I. L. Chuang による量子情報科学の代表的な著書 “Quantum Computation and Quantum Information” 以降に登場した重要なテーマ，トポロジカル量子符号とそれを用いたトポロジカル量子計算の理解を最終目標とする．

講義計画

• はじめに：[スライド]

• 量子情報基礎：
  量子ビット、量子演算、多量子ビット系、多量子ビット演算、量子状態の測定、密度演算子
  [講義ノート][レポート] （授業で省略した、部分系の測定と部分トレース、混合状態のBloch球表示も含まれています。 ）

• 量子計算基礎：
  万能量子計算、Solovay-Kitaevアルゴリズム、量子アルゴリズム（Hadamardテスト、Kitaev位相推定アルゴリズム、Shorの素因数分解アルゴリズム、Aharonov-Jones-LandauのJones多項式近似アルゴリズム*）
  [講義ノート:万能性、ゲート分解、Solovay-Kitaevアルゴリズム] 
  (講義中にご指摘頂きました間違いを修正しました．)
  [講義ノート:Kitaevの位相推定、素因数分解] 
  [講義ノート:Jones多項式の近似] 
  (補足：4step encodingでは組紐群B_8の表現を考えましたが、1からスタートし8ステップ後に1に戻るパスは合計14個あるので、14次元表現になっています。これがSU(14)で稠密になっていることからその部分群であるSU(4)=4step encoding上での2量子ビット演算においても稠密であることが示せます。 詳しくは、[6]の bridging補題と decoupling補題を参照下さい。）
  [レポート] (Hadamardテストの精度と測定回数の関係=Chernoff-Hoeffding限界を書いておきました．)

• スタビライザー形式と応用：
  スタビライザー形式、Gottesman-Knillの定理、量子誤り訂正符号、マジック状態蒸留*、誤り耐性量子計算、測定型量子計算*

[講義ノート:スタビライザ形式、Gottesman-Knillの定理]

[講義ノート:量子誤り訂正]

[補足:測定型量子計算]（時間の都合上省略しました。）

[レポート]

（マジック状態とClifford回路による量子テレポーテーションでnonClifford演算が”deterministic”に実行できることが理解できるようになっています。）

• トポロジカル符号とトポロジカル誤り耐性量子計算*
  トポロジカル表面符号、トポロジカル符号とトロポジカル秩序、トポロジカル量子誤り訂正、誤り訂正とスピングラス模型、トポロジカル誤り耐性量子計算、defect qubitの基本操作、BraidingによるCNOT、マジック状態注入、トポロジカル誤り耐性量子計算
  [講義ノート:トポロジカル表面符号、トポロジカル秩序、誤り訂正とスピングラス]
  [講義ノート:トポロジカル誤り耐性量子計算]

進捗状況によって内容を変更・省略する可能性があります。講義ノートはスキャンして 公開する予定です。

参考文献等
[1] M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information”, Cambridge university press.”（和訳あり、*が付いている項目以外はカバーしています）
[2] スライド「量子計算超入門」（一部を除きだいたい講義内容がカバーされています） [pdf,18.1MB]
[3] スライド「量子計算の基礎」（量子計算基礎のごく一部が含まれています） [pdf,6.7MB]
[4] C.M. Dawson, and M. A. Nielsen, “The Solovay-Kitaev algorithm”, arXiv preprint quant-ph/0505030 (2005). （Solovay-Kitaevアルゴリズムの最も分かりやすい解説）
[5] D. Aharonov, V. Jones, and Z. Landau, “A polynomial quantum algorithm for approximating the Jones polynomial.” Algorithmica 55.3 (2009): 395-421. arXiv:0511096 （AJLアルゴリズム）
[6] D. Aharonov, and I. Arad, “The BQP-hardness of approximating the Jones polynomial.” New Journal of Physics 13.3 (2011): 035019. arXiv:0605181 （Jones多項式近似のBQP完全性）
[7] E. Knill, R. Laflamme, and W. H. Zurek. “Resilient quantum computation: error models and thresholds.” Proc. of the Royal Society of London. A: Math., Phys. and Eng. Sci. 454.1969 (1998): 365-384. arXiv:quant-ph/9702058 (マジック状態蒸留 Hadamard演算子の間接測定)
[8] S. Bravyi, and A. Kitaev. “Universal quantum computation with ideal Clifford gates and noisy ancillas.” Physical Review A 71.2 (2005): 022316. arXiv:quant-ph/0403025 （マジック状態蒸留 15qubit Reed-Mullar code, 実は[7]と等価）
R. Raussendorf, and H. J. Briegel. “A one-way quantum computer.” Physical Review Letters 86.22 (2001): 5188.（MBQC提案論文）
[10] R. Raussendorf, D. E. Browne, and H. J. Briegel, “Measurement-based quantum computation on cluster states.” Physical review A 68 (2003): 022312. arXiv:quant-ph/0301052 （[9]の詳細版。この講義では説明しないが、MBQCの演算子的な説明があり、これが [13]のトポロジカル量子計算へと繋がった。）
[11] M. A. Nielsen, “CLUSTER-STATE QUANTUM COMPUTATION”, Rep. on Math. Phys. 57, 147 (2006) arXiv:quant-ph/0504097 （テレポーテーション回路を用いたMBQCの理解。初学者にはわかりやすい。）
[12] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, “Topological quantum memory”, Journal of Mathematical Physics, 43(9) (2002): 4452-4505. arXiv:quant-ph/0110143 （表面符号を用いたトポロジカル誤り訂正。誤り訂正とスピングラス模型との対応につても解説されている。）
[13] R. Raussendorf, J. Harrington, and K. Goyal, “A fault-tolerant one-way quantum computer.” Annals of physics 321.9 (2006): 2242-2270. arXiv:quant-ph/0510135 （表面符号を用いたトポロジカル量子計算、3次元リソース上のMBQCとして提案された。）
[14] R. Raussendorf, J. Harrington, and K. Goyal, “Topological fault-tolerance in cluster state quantum computation”, New Journal of Physics 9.6 (2007): 199.（[13]の改良版。）
[15] A. G. Fowler, A. M. Stephens, and P. Groszkowski. “High-threshold universal quantum computation on the surface code.”Physical Review A 80.5 (2009): 052312. arXiv:0803.0272 （[12]を、２次元の回路モデルとして解説）

さらに勉強したい人へ
(講義内容をさらに深く理解するための文献です)

• Simulating Physics with Computers by R. P. Feynman presented by Pinchas Birnbaum and Eran Tromer, Weizmann Institute of Science（計算と物理、量子コンピュータの背景）
• 量子コンピュータ授業#8 「量子コンピュータの歴史」 by 古田彩（日経サイエンス）
  二人の悪魔と多数の宇宙 : 量子コンピュータの起源 by 古田彩（日経サイエンス）日本物理学会誌59(8), 512-519, 2004-08-05
• Lecture notes by John Preskill（全般）
• Lecture notes by Umesh Vazirani（全般）
• D. Aharonov, I. Arad, E. Eban, and Z. Landau, “Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane”, arXiv quant-ph/0702008. （AJLアルゴリズムのTutte多項式への拡張）
• M. Van den Nest, W. Dür, and H. J. Briegel, “Classical spin models and the quantum-stabilizer formalism.” Physical review letters 98.11 (2007): 117207; “Completeness of the classical 2D Ising model and universal quantum computation.” Physical review letters 100.11 (2008): 110501. （MBQC=スタビライザ状態と直積状態の内積と分配関数の対応）
• A. Matsuo, K. Fujii, and N. Imoto, “Quantum algorithm for an additive approximation of Ising partition functions”, Phys. Rev. A 90, 022304 (2014) arXiv:1405.2749 （MBQCと分配関数の対応を利用して構成したイジング分配関数近似量子アルゴリズム）
• E. Gibney, “Quantum Computer Quest”, Nature 516 24-26 (2014).

（雑誌を見れない人はarXiv版をご覧下さい）
随時更新中．．．