# 量子計算の基礎
- 喋ってる人
- 東大数理科学研究科 => NTT で量子コンピュータやってる
- 主にアルゴリズム開発
- いまいまの目標
- 100ビット
- 誤り訂正がイイカンジに行ける

## 量子計算とはどんな分野か？
1. 物理的構成で最も一般的な計算とはなにか？
- 物理法則が許容する物理現象の限界 = 我々が可能な情報処理の限界
1. どこまで効率的に物理現象を模様可能か?
- エンジニアリングの話も含む
3. 情報処理の限界から物理法則の理解を深められないか？
- ex) P=NPでない ⇒ 起きてはいけない物理法則がある！

- 計算機 = 制御された大規模量子物理系
- いままでの計算機
- 量子性を削ぎ落としたスケール(=アナログ回路)で回路を制御
- 量子性を削ぎ落とすような制約を入れることで、逆にイイカンジの最適化が図れている(後述)
- 量子計算機
- 量子性そのまんまで回路を構築する = "量子回路"

## 量子力学の公理と記法
### 記号
- d次元ヒルベルト空間 H
- ブラ記号/ケット記号 = 縦ベクトル/横ベクトル
- 正規直交基底 {|x>} xはだいたい整数 |0> |1>
- ベクトルのテンソル積 |a> ✕ |b> => |ab>
- 随伴 = 天地の複素共益 †
- 内積 <a|b>
- 線形演算子 L(H) 行列表現があるよ
- 密度演算子 D(H) ρ

#### 公理１
- 量子系の任意の状態はD(H)の元ρと1対１に対応する

#### 公理2 閉じた系の時間発展
- ρ(t) ∈ D(H) の時間微分をハミルトニアンで表現した微分方程式があるよという話

#### 公理3 測定
- 測定とは
- 得られる記号の集合S
- それぞれに紐付いた線形演算子の集合
- 測定は原理的に確率的である
- 測定の結果、密度演算子(=物理状態)は状態遷移する
- 初期状態は理論上は既知として扱う
- 実装上はノイズとかあるんで未知としてなんかする

※ 測定にかかる時間を考慮する場合は、何らかの測定系を用意する

#### 公理4 物理系の合成
- 2つの量子系H1, H2をあわせて考えるときどうなるの？
- テンソル積 H = H1✕H2 と表される
- 密度演算子も それぞれのテンソル積を考える
- ハミルトニアンはちょっとむずい
- 相互作用があるときと無いときで違う
- H1にたいする測定{Ms}はHに対する{Ms✕I} に対応

### 量子ビットを用いた表現
- 2次元量子系をn個組み合わせてd=2^n次元の系を考えるのが最近の主流
- ex.) 3ビット = 2^3=8次元 |001> みたいに書く
- 2次元系の回路を作ってそれを合成するのが今いまイケてる

#### なぜ 2次元系の合成系とするの？
1. 身近な計算機との対応付をわかりやすくするため
2. テンソル積で分解されるベクトル空間を、物理空間と対応付けるため
3. 技術的に、2~3次元が限界
- 制御可能なエネルギーや自由度の問題
---
- 理論上は光でもイオンでも行けるけど、イイカンジの2次元系をとりだせるか？が問題

## 量子状態への写像
- 「あるハミルトニアンでの時間発展」 を 密度演算子に対する線形写像として定義する

### 理論上はこんな仮定をおく
1. ダイナミクスと測定の厳密な制御
2. 孤立した物理系を取り出せる
- 実態としては「ある２次元系のハミルトニアンだけが変わった」というような相互作用を起こすことが可能
4. 初期状態は計算規程の0状態から始まる　ρ0 = |0><0|

### 計算過程とはなにか
- ハミルトニアンの時間発展(密度演算子の微分方程式) <=> 測定
- を行ったり来たり
- 微分方程式いちいちとくのは辛いから、↓

### ユニタリ写像をつかう
- 定理:閉じた系の時間非依存ハミルトニアンによる時間発展はユニタリ写像と対応している
- 任意のユニタリ写像について、それを時間発展結果として実現するハミルトニアンは存在する
- ユニタリ写像の合成はユニタリ写像

### 純粋状態を用いた表現
- ρがrank(ρ)=1のとき、ρは純粋状態という
- それ以外は混合状態という
- rank(ρ)=1のとき ρ=|a><a|という分解が一意に定まる

つまり、密度行列と状態ベクトルは行ったり来たりできる
手計算なら状態ベクトルで計算したほうが楽

---
- 初期状態はなんらかの純粋状態
- ユニタリ写像と測定は、純粋状態を純粋状態に写像する
- 理論上は純粋状態だけを考える

### 測定系を用いた射影測定
- 任意の測定は、計算機を拡張した系での時間発展と射影測定にできる
- 射影演算子の集合でまとめて測定を行う
- 興味のある系だけ

### 遅延測定
- 測定した結果に基づいて定まる次の時間発展は、時間発展のあとの測定としてかける

### 一般化
射影測定と遅延測定を組み合わせることで、一つのユニタリ演算子と一つの射影測定だけで計算を一般化することをできる

ただし、任意のハミルトニアンや測定が実現できてしまうと、「すべての計算が一瞬で終わる」のでそれはおかしい

## 量子計算の効率
### 現実的なハミルトニアンと測定の制約
- 現実には任意の自己随伴なハミルトニアンを構成することはできないと信じられている

#### 局所ハミルトニアン
- ハミルトニアンを局所的な相互作用(n-localなハミルトニアン)の和として表す

### 現実的な実験の要請
1. 実質的にはハミルトニアンは定数-local (とくに2-local)
- 定数: アルゴリズムを考えるときに問題のサイズが大きくなっても変えられない
2. ハミルトニアンの和を構成する演算子の固有値の絶対値の最大値はたかだか定数
3. 射影測定

ハミルトニアン
- 理想: 任意の自己随伴演算子
- 現実: 局所的な相互作用の和
- 量子計算で扱うやつ: 作用する空間が共通部分を持たない

### 量子計算で用いるハミルトニアン
- ユニタリのテンソル積として表現できる

### 量子回路の表現
- 量子ゲート
- 1-qubit, 2-qubitのゲートには慣用的に名前がついているものがいくつかある




### 古典との計算量の比較
- 任意の定数-localハミルトニアンは2-qubitゲートの多項式個で近似可能
- 任意のユニタリ演算子は2-qubitゲートで近似するには2^nのオーダー個数必要

### まとめ
- 任意の量子計算は1ステップで行ける
- 任意の定数-localなハミルトニアンは2-qubitゲートの多項式時間で近似可能
- けど、任意のユニタリ演算子の近似には指数関数時間かかる

### 計算量クラスの定義
- 決定問題
- BQPクラス 量子計算専用のクラス
- 問題サイズnに対して多項式的な数のconst-qubitゲートで構成可能
- Shoreの素因数分解はBQP
- 量子シミュレート　BQP完全
- 要するに任意の量子系がシミュレートできる計算はBQPであるということを言っている


- Pクラス
- BPPクラス
- BQPのゲートの種類を限定したものといえる
- 指数時間かければBQPの問題は溶ける
- つまり、指数時間かけてしまえば古典計算機でも量子計算はシミュレートできる
- PSPACEクラス
- NPクラス
- 検算はかんたんだけど計算は大変
- BQPとは排他な領域があるっぽい

NANDがつくれれば、任意の論理回路が作れる
- 2qubitのNANDはユニタリじゃない(非可逆)

### 量子計算機が「早い」とはなにか？
- 古典計算機は
- 量子ゲートを「計算基底から計算基底へのマップ=論理ゲート」に限定している
- 未知の純粋状態はコピーができない
- 計算基底への射影測定は非破壊
- これらを仮定することで最適化が図られている

- 量子計算機は
- ゲート数はめっちゃ減らせる
- エラー率がやばい
- BQP -> P にできても、ゲート数が急増する問題は「それほど多くない」ので、ゲートを減らせることの利点が活きない

## 量子計算のいま
- 最近の変化
- 規模
- むかし 技術的に2,3ビットの制御しかできなかった
- いま 超電導量子ビット集積化の技術が発達した
- ノイズ
- むかし 1%~10%で下げ止まっていた
- いま 0.1%~1%くらいになってきた
- いま 1%くらいで誤り訂正ができるようになってきた
- 応用
- 有用なアルゴリズムが大きく発展した
- 環境
- 汎用半導体計算機の発展が頭打ちになってきた

### Googleのはなし
- 配線やばい
- お金と根性を感じる
- 量子超越性を示した
- 量子計算のほうが計算能力が高いということ
- ただ、なんか微妙な仮定が置かれているので業界的には微妙

- スパコンとの比較
- IBMが別にスパコンでもめっちゃ早くできるつってた
- 10000年 => 2.5日