一般 いっぱん NOTゲート 以外 いがい 古典 こてん 的 てき 基本 きほん 論理 ろんり 不 ふ 可逆 かぎゃく 演算 えんざん 入力 にゅうりょく 出力 しゅつりょく 情報 じょうほう 失 うしな 入力 にゅうりょく ANDゲート において出力 しゅつりょく 結果 けっか 入力 にゅうりょく 組 く 合 あ 得 え 知 し 不可能 ふかのう
ただし、古典 こてん 的 てき 代表 だいひょう 任意 にんい 長 なが ビット列 びっとれつ 対 たい 可逆 かぎゃく 構成 こうせい 理想 りそう 的 てき 可逆 かぎゃく 情報 じょうほう 損失 そんしつ 物理 ぶつり 学 がく 的 てき エントロピー の増加 ぞうか 伴 ともな 電力 でんりょく 消費 しょうひ 熱 ねつ 損失 そんしつ 問題 もんだい 生 しょう 応用 おうよう 面 めん 関心 かんしん 寄 よ 一般 いっぱん 可逆 かぎゃく ビット列 びっとれつ 入力 にゅうりょく 受 う 取 と 同 おな 長 なが ビット列 びっとれつ 出力 しゅつりょく 可逆 かぎゃく 関数 かんすう 表 あらわ 長 なが n のビット列 びっとれつ 構成 こうせい 文字 もじ 列 れつ x 1 x 2 ... x n n 表現 ひょうげん ビット列 びっとれつ 全部 ぜんぶ n 通 とお 存在 そんざい
より厳密 げんみつ 可逆 かぎゃく ビット列 びっとれつ 集合 しゅうごう n 自身 じしん 全 ぜん 単 たん 射 しゃ 写像 しゃぞう f として表現 ひょうげん 可逆 かぎゃく f の例 れい 入力 にゅうりょく 定 さだ 置換 ちかん 適用 てきよう 写像 しゃぞう 挙 あ 現在 げんざい 置換 ちかん 用 もち 可逆 かぎゃく 古典 こてん 的 てき 論理 ろんり 構成 こうせい 手法 しゅほう 真偽 しんぎ 表 ひょう 用 もち 簡単 かんたん 表現 ひょうげん 範囲 はんい 小 ちい n （例 れい n = 1, 2, 3）についてのみ研究 けんきゅう
量子 りょうし 定義 ていぎ 古典 こてん 的 てき 論理 ろんり 場合 ばあい 同様 どうよう n -量子 りょうし 置換 ちかん 考 かんが 古典 こてん 的 てき ビット列 びっとれつ 空間 くうかん n 量子 りょうし 版 ばん ヒルベルト空間 くうかん である。
H
QB
(
n
)
=
ℓ
2
(
{
0
,
1
}
n
)
.
{\displaystyle H_{\operatorname {QB} (n)}=\ell ^{2}(\{0,1\}^{n}).}
これは定義 ていぎ n 複素 ふくそ 関数 かんすう 空間 くうかん 内積 ないせき 空間 くうかん 空間 くうかん 古典 こてん 的 てき 文字 もじ 列 れつ 線形 せんけい 重 かさ 合 あ 構成 こうせい 見 み H QB（ n ） は、 2n 次元 じげん 複素 ふくそ 空間 くうかん 注意 ちゅうい 空間 くうかん 要素 ようそ 量子 りょうし ビット列 びっとれつ n- 量子 りょうし 呼 よ
古典 こてん 的 てき ビット列 びっとれつ x 1 x 2 ... x n 対 たい ケット 表記 ひょうき 使用 しよう 表記 ひょうき 量子 りょうし ビット列 びっとれつ
|
x
1
,
x
2
,
⋯
,
x
n
⟩
{\displaystyle |x_{1},x_{2},\cdots ,x_{n}\rangle \quad }
を考 かんが 古典 こてん 的 てき ビット列 びっとれつ x 1 x 2 ... x n 他 た 文字 もじ 列 れつ 写 うつ 関数 かんすう 対応 たいおう 特殊 とくしゅ 量子 りょうし ビット列 びっとれつ 古典 こてん 的 てき ビット列 びっとれつ 対応 たいおう 特殊 とくしゅ 量子 りょうし ビット列 びっとれつ 計算 けいさん 基底 きてい 状態 じょうたい 呼 よ 長 ちょう n に対 たい n 個 こ 存在 そんざい 量子 りょうし ビット列 びっとれつ 計算 けいさん 基底 きてい 状態 じょうたい 複素 ふくそ 線形 せんけい 結合 けつごう
古典 こてん 的 てき 論理 ろんり 対照 たいしょう 的 てき 量子 りょうし 論理 ろんり 常 つね 可逆 かぎゃく 特別 とくべつ 種類 しゅるい 可逆 かぎゃく 関数 かんすう ユニタリ 作用素 さようそ エルミート内積 ないせき を保存 ほぞん 複素 ふくそ 内積 ないせき 空間 くうかん 線形 せんけい 変換 へんかん 用 もち 量子 りょうし ビット列 びっとれつ 対 たい 可逆 かぎゃく 量子 りょうし n -量子 りょうし 空間 くうかん H QB(n ） から自己 じこ ユニタリ作用素 さようそ U である。
通常 つうじょう 我々 われわれ nの 小 ちい 値 ね 関心 かんしん
可逆 かぎゃく n- ビットの古典 こてん 的 てき 論理 ろんり 回路 かいろ 次 つぎ 可逆 かぎゃく n- ビット量子 りょうし 生成 せいせい 可逆 かぎゃく n ビット論理 ろんり fに は、次 つぎ 定義 ていぎ 量子 りょうし W f 対応 たいおう
W
f
(
|
x
1
,
x
2
,
⋯
,
x
n
⟩
)
=
|
f
(
x
1
,
x
2
,
⋯
,
x
n
)
⟩
.
{\displaystyle W_{f}(|x_{1},x_{2},\cdots ,x_{n}\rangle )=|f(x_{1},x_{2},\cdots ,x_{n})\rangle .}
W f 計算 けいさん 基底 きてい 状態 じょうたい 置換 ちかん 注意 ちゅうい
中 なか 特 とく 重要 じゅうよう 量子 りょうし 入出力 にゅうしゅつりょく 対 たい 定義 ていぎ 制御 せいぎょ 呼 よ W CNOT である。 古典 こてん 的 てき 論理 ろんり 派生 はせい 量子 りょうし 論理 ろんり 他 ほか 例 れい トフォリゲート とフレドキンゲート が挙 あ
しかし、量子 りょうし 空間 くうかん 構造 こうぞう 古典 こてん 的 てき 表現 ひょうげん 多 おお 量子 りょうし 可能 かのう 以下 いか 相対 そうたい 位相 いそう 行列 ぎょうれつ 乗算 じょうざん 与 あた 量子 りょうし
U
θ しーた
=
[
e
i
θ しーた
0
0
1
]
,
{\displaystyle U_{\theta }={\begin{bmatrix}e^{i\theta }&0\\0&1\end{bmatrix}},}
すなわち、
U
θ しーた
|
0
⟩
=
e
i
θ しーた
|
0
⟩
U
θ しーた
|
1
⟩
=
|
1
⟩
.
{\displaystyle U_{\theta }|0\rangle =e^{i\theta }|0\rangle \quad U_{\theta }|1\rangle =|1\rangle .}
再 ふたた 最初 さいしょ 可逆 かぎゃく 」 古典 こてん 計算 けいさん 考 かんが 概念的 がいねんてき 可逆 かぎゃく n ビット回路 かいろ 可逆 かぎゃく n ビット論理 ろんり 間 あいだ 違 ちが n ビット列 びっとれつ 空間 くうかん 上 じょう 単 たん 可逆 かぎゃく 関数 かんすう 前節 ぜんせつ 述 の 工学 こうがく 的 てき 理由 りゆう 可逆 かぎゃく 回路 かいろ 構成 こうせい 組 く 合 あ 少数 しょうすう 単純 たんじゅん 可逆 かぎゃく 必要 ひつよう
この構成 こうせい 過程 かてい 説明 せつめい 可逆 かぎゃく n- ビットゲートf と、可逆 かぎゃく m- ビットゲートg があるとする。 これらを合成 ごうせい 次 つぎ 図 ず f のk- ビットの出力 しゅつりょく g のk- ビットの入力 にゅうりょく 接続 せつぞく 新 あたら 回路 かいろ 作成 さくせい 意味 いみ 以下 いか 例 れい n = 5, k = 3, m = 7である。 結果 けっか 回路 かいろ 可逆 かぎゃく n +m-k )-ビットで動作 どうさ
この方法 ほうほう 古典 こてん 的 てき 結合 けつごう 呼 よ 概念 がいねん 以下 いか 引用 いんよう 先駆 せんく 的 てき 論文 ろんぶん 技術 ぎじゅつ 的 てき 定義 ていぎ 対応 たいおう 可逆 かぎゃく 機械 きかい 構成 こうせい 中間 ちゅうかん 的 てき 機械 きかい 可逆 かぎゃく 確認 かくにん 重要 じゅうよう 条件 じょうけん 計算 けいさん 途中 とちゅう 生成 せいせい 保証 ほしょう 正味 しょうみ 物理 ぶつり 的 てき 効果 こうか 増加 ぞうか 演習 えんしゅう 行 おこな 動機 どうき
これで、 トフォリゲート が汎用 はんよう 示 しめ 任意 にんい 可逆 かぎゃく 的 てき 古典 こてん 的 てき n ビット回路 かいろ h が与 あた 場合 ばあい 上記 じょうき 方法 ほうほう 古典 こてん 的 てき 結合 けつごう 次 つぎ n + m ）ビット回路 かいろ f を生成 せいせい 意味 いみ
f
(
x
1
,
…
,
x
n
,
0
,
…
,
0
⏟
m
)
=
(
y
1
,
…
,
y
n
,
0
,
…
,
0
⏟
m
)
{\displaystyle f(x_{1},\ldots ,x_{n},\underbrace {0,\dots ,0} _{m})=(y_{1},\ldots ,y_{n},\underbrace {0,\ldots ,0} _{m})}
さらに次 つぎ 式 しき 成立 せいりつ
(
y
1
,
…
,
y
n
)
=
h
(
x
1
,
…
,
x
n
)
{\displaystyle (y_{1},\ldots ,y_{n})=h(x_{1},\ldots ,x_{n})}
この最終 さいしゅう 結果 けっか 常 つね 補助 ほじょ m個 こ ゼロの文字 もじ 列 れつ 注意 ちゅうい 生成 せいせい 計算 けいさん 実際 じっさい 物理 ぶつり 学 がく 的 てき 増加 ぞうか 問題 もんだい 論文 ろんぶん 注意深 ちゅういぶか 説明 せつめい
より一般 いっぱん 任意 にんい 関数 かんすう f は、（全 ぜん 単 たん 射 しゃ 以外 いがい 回路 かいろ 模倣 もほう 知 し 写像 しゃぞう 単 たん 射 い 場合 ばあい 計算 けいさん 途中 とちゅう 最後 さいご 生成 せいせい 明 あき
量子 りょうし 回路 かいろ 量子 りょうし 同様 どうよう 構成 こうせい 定義 ていぎ 上記 じょうき 任意 にんい 古典 こてん 的 てき 結合 けつごう 関連 かんれん fの 代 か n- 量子 りょうし U が、 gの 代 か m -量子 りょうし W がある場合 ばあい 可逆 かぎゃく 量子 りょうし 回路 かいろ 生成 せいせい 以下 いか 図 ず 例 れい 説明 せつめい
この方法 ほうほう 接続 せつぞく n+m-k )-量子 りょうし 空間 くうかん 作用素 さようそ 生成 せいせい 事実 じじつ 簡単 かんたん 確認 かくにん 実際 じっさい 量子 りょうし 間 あいだ 物理 ぶつり 的 てき 接続 せつぞく デコヒーレンス が発生 はっせい 可能 かのう 性 せい 場所 ばしょ 工学 こうがく 上 じょう 課題 かだい
普遍 ふへん 性 せい 少数 しょうすう 種類 しゅるい 組 く 合 あ 任意 にんい 量子 りょうし 回路 かいろ 構成 こうせい 証明 しょうめい 量子 りょうし 回路 かいろ 普遍 ふへん 性 せい 定理 ていり universality theorems )は、たとえばあるθ しーた 対 たい 量子 りょうし 位相 いそう Uθ しーた と、2-量子 りょうし W CNOT の組 くみ 対 たい 知 し
ただし、量子 りょうし 回路 かいろ 普遍 ふへん 性 せい 定理 ていり 古典 こてん 的 てき 回路 かいろ 普遍 ふへん 性 せい 定理 ていり 弱 よわ 主張 しゅちょう 任意 にんい 可逆 かぎゃく n- 量子 りょうし 回路 かいろ 基本 きほん 組 く 立 た 回路 かいろ 任意 にんい 適切 てきせつ 近似 きんじ 主張 しゅちょう 古典 こてん 的 てき 回路 かいろ 異 こと 非 ひ 可算 かさん 角度 かくど θ しーた 対 たい 同 おな 量 りょう 位相 いそう 存在 そんざい 少 すく 有限 ゆうげん U θ しーた W CNOT )}のみでは表現 ひょうげん 注意 ちゅうい 必要 ひつよう
ここまでで、量子 りょうし 回路 かいろ 使用 しよう 計算 けいさん 実行 じっこう 方法 ほうほう 示 しめ 多 おお 重要 じゅうよう 数値 すうち 問題 もんだい 有限 ゆうげん 次元 じげん 空間 くうかん 変換 へんかん U を計算 けいさん 還元 かんげん 有名 ゆうめい 離散 りさん 変換 へんかん 主 おも 例 れい 変換 へんかん U を実行 じっこう 量子 りょうし 回路 かいろ 設計 せっけい 期待 きたい 原理 げんり 的 てき 一方 いっぽう 入力 にゅうりょく 計算 けいさん 基底 きてい 状態 じょうたい 適切 てきせつ 重 かさ 合 あ 、n- 量子 りょうし 状態 じょうたい ψ ぷさい 用意 ようい 出力 しゅつりょく U ψ ぷさい 測定 そくてい 残念 ざんねん 課題 かだい
観測 かんそく 者 しゃ 任意 にんい 計算 けいさん 基底 きてい 状態 じょうたい 位相 いそう ψ ぷさい 測定 そくてい 不可能 ふかのう 正確 せいかく 出力 しゅつりょく 読 よ 取 と 方法 ほうほう 量子力学 りょうしりきがく 測定 そくてい 性質 せいしつ 入力 にゅうりょく 状態 じょうたい 重 かさ 合 あ ψ ぷさい 用意 ようい 効果 こうか 的 てき 方法 ほうほう 今 いま これは、離散 りさん 変換 へんかん 量子 りょうし 回路 かいろ 他 た 量子 りょうし 回路 かいろ 中 なか 間 あいだ 使用 しよう 否定 ひてい 実用 じつよう 化 か 一層 いっそう 困難 こんなん 実際 じっさい 量子 りょうし 計算 けいさん 確 かく 率 りつ 的 てき
以下 いか 量子 りょうし 回路 かいろ 確 かく 率 りつ 的 てき 古典 こてん 的 てき 模倣 もほう 数理 すうり 紹介 しょうかい 空間 くうかん H QB(r ) 上 うえ r- 量子 りょうし 回路 かいろ U、
H
QB
(
r
)
→
H
QB
(
r
)
.
{\displaystyle H_{\operatorname {QB} (r)}\rightarrow H_{\operatorname {QB} (r)}.}
を考 かんが U はユニタリ作用素 さようそ 回路 かいろ ビット列 びっとれつ 古典 こてん 的 てき 写像 しゃぞう 関連付 かんれんづ 次 つぎ 指定 してい
入力 にゅうりょく 古典 こてん 的 てき ビット列 びっとれつ X' = {0,1}m 出力 しゅつりょく 古典 こてん 的 てき ビット列 びっとれつ Y = {0,1}n 入力 にゅうりょく 内容 ないよう x = x 1 .. x m 量子 りょうし 何 なん 方法 ほうほう 初期 しょき 化 か 使用 しよう 理想 りそう 的 てき 以下 いか 計算 けいさん 基底 きてい 状態 じょうたい 与 あた
|
x
→
,
0
⟩
=
|
x
1
,
x
2
,
⋯
,
x
m
,
0
,
…
,
0
⏟
r
−
m
⟩
,
{\displaystyle |{\vec {x}},0\rangle =|x_{1},x_{2},\cdots ,x_{m},\underbrace {0,\dots ,0} _{r-m}\rangle ,}
ただし、前述 ぜんじゅつ 通 とお 理想 りそう 的 てき 初期 しょき 状態 じょうたい 用意 ようい 現実 げんじつ 的 てき 不可能 ふかのう 初期 しょき 状態 じょうたい 適切 てきせつ 近似 きんじ 尺度 しゃくど 理想 りそう 化 か 入力 にゅうりょく 近 ちか 密度 みつど 演算 えんざん 子 こ S によって与 あた 混合 こんごう 状態 じょうたい 仮定 かてい
Tr
(
|
|
x
→
,
0
⟩
⟨
x
→
,
0
|
−
S
|
)
≤
δ でるた .
{\displaystyle \operatorname {Tr} \left({\big |}|{\vec {x}},0\rangle \langle {\vec {x}},0|-S{\big |}\right)\leq \delta .}
同様 どうよう 出力 しゅつりょく 空間 くうかん 観測 かんそく 値 ち Aの Y 値 ね 量子 りょうし 関連付 かんれんづ 量子力学 りょうしりきがく 観測 かんそく 通常 つうじょう 射影 しゃえい 測定 そくてい projection valued measure ) R で定義 ていぎ 変数 へんすう 離散 りさん 的 てき 場合 ばあい 射影 しゃえい 測定 そくてい 可算 かさん 集合 しゅうごう 上 じょう λ らむだ 添字 そえじ 付 づ 族 ぞく λ らむだ 還元 かんげん 同様 どうよう Y 値 ね 観測 かんそく 次 つぎ 性質 せいしつ 満 み Yの 要素 ようそ 付 つ 直交 ちょっこう 投影 とうえい y 族 ぞく 関連付 かんれんづ
I
=
∑
y
∈
Y
E
y
.
{\displaystyle I=\sum _{y\in Y}\operatorname {E} _{y}.}
与 あた 混合 こんごう 状態 じょうたい S に対 たい 次 つぎ 式 しき 与 あた Y 上 うえ 確 かく 率 りつ 測度 そくど 対応 たいおう
Pr
{
y
}
=
Tr
(
S
E
y
)
.
{\displaystyle \operatorname {Pr} \{y\}=\operatorname {Tr} (S\operatorname {E} _{y}).}
長 なが mの すべてのビット文字 もじ 列 れつ x に対 たい 次 つぎ 式 しき 成立 せいりつ 関数 かんすう F ： X → Y は回路 かいろ U ： H QB（ r ） → H QB（ r ） によって誤差 ごさ ε いぷしろん 回路 かいろ 内 ない 計算 けいさん
⟨
x
→
,
0
|
U
∗
E
F
(
x
)
U
|
x
→
,
0
⟩
=
⟨
E
F
(
x
)
U
(
|
x
→
,
0
⟩
)
|
U
(
|
x
→
,
0
⟩
)
⟩
≥
1
−
ϵ
.
{\displaystyle \left\langle {\vec {x}},0{\big |}U^{*}\operatorname {E} _{F(x)}U{\big |}{\vec {x}},0\right\rangle =\left\langle \operatorname {E} _{F(x)}U(|{\vec {x}},0\rangle ){\big |}U(|{\vec {x}},0\rangle )\right\rangle \geq 1-\epsilon .}
ここで、
|
Tr
(
S
U
∗
E
F
(
x
)
U
)
−
⟨
x
→
,
0
|
U
∗
E
F
(
x
)
U
|
x
→
,
0
⟩
|
≤
Tr
(
|
|
x
→
,
0
⟩
⟨
x
→
,
0
|
−
S
|
)
‖
U
∗
E
F
(
x
)
U
‖
≤
δ でるた
{\displaystyle \left|\operatorname {Tr} (SU^{*}\operatorname {E} _{F(x)}U)-\left\langle {\vec {x}},0{\big |}U^{*}\operatorname {E} _{F(x)}U{\big |}{\vec {x}},0\right\rangle \right|\leq \operatorname {Tr} ({\big |}|{\vec {x}},0\rangle \langle {\vec {x}},0|-S{\big |})\|U^{*}\operatorname {E} _{F(x)}U\|\leq \delta }
そのため
Tr
(
S
U
∗
E
F
(
x
)
U
)
≥
1
−
ϵ
−
δ でるた .
{\displaystyle \operatorname {Tr} (SU^{*}\operatorname {E} _{F(x)}U)\geq 1-\epsilon -\delta .}
定理 ていり ε いぷしろん δ でるた Y 上 うえ 確 かく 率 りつ 分布 ぶんぷ
Pr
{
y
}
=
Tr
(
S
U
∗
E
y
U
)
{\displaystyle \operatorname {Pr} \{y\}=\operatorname {Tr} (SU^{*}\operatorname {E} _{y}U)}
は、十分 じゅうぶん 大 おお 対 たい 多数決 たすうけつ 誤差 ごさ 確 かく 率 りつ 任意 にんい 小 ちい F (x )を決定 けってい 具体 ぐたい 的 てき Y 上 うえ の 確 かく 率 りつ 分布 ぶんぷ k個 こ 独立 どくりつ 取得 しゅとく 半分 はんぶん 以上 いじょう 一致 いっち 値 ね 選択 せんたく 値 ね F (x )がk / 2回 かい 以上 いじょう 確 かく 率 りつ 少 すく 次 つぎ 式 しき 表 あらわ
1
−
e
−
2
γ がんま
2
k
,
{\displaystyle 1-e^{-2\gamma ^{2}k},}
ただし、γ がんま ε いぷしろん δ でるた 限界 げんかい 適用 てきよう 得 え
Biham, Eli ; Brassard, Gilles ; Kenigsberg, Dan; Mor, Tal (2004), “Quantum computing without entanglement”, Theoretical Computer Science 320 (1): 15–33, arXiv :quant-ph/0306182 , doi :10.1016/j.tcs.2004.03.041 , MR 2060181 Freedman, Michael H. ; Kitaev, Alexei ; Larsen, Michael J. ; Wang, Zhenghan (2003), “Topological quantum computation”, Bulletin of the American Mathematical Society 40 (1): 31–38, arXiv :quant-ph/0101025 , doi :10.1090/S0273-0979-02-00964-3 , MR 1943131 Hirvensalo, Mika (2001), Quantum Computing , Natural Computing Series, Berlin: Springer-Verlag, ISBN 3-540-66783-0 , MR 1931238 Hirvensalo, Mika (2001), Quantum Computing , Natural Computing Series, Berlin: Springer-Verlag, ISBN 3-540-66783-0 , MR 1931238 Hirvensalo, Mika (2001), Quantum Computing , Natural Computing Series, Berlin: Springer-Verlag, ISBN 3-540-66783-0 , MR 1931238 Kitaev, A. Yu. (1997), “Quantum computations: algorithms and error correction” (Russian), Uspekhi Mat. Nauk 52 (6(318)): 53–112, Bibcode : 1997RuMaS..52.1191K , doi :10.1070/RM1997v052n06ABEH002155 , MR 1611329 Nielsen, Michael A. ; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information , Cambridge: Cambridge University Press, ISBN 0-521-63235-8 , MR 1796805 Nielsen, Michael A. ; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information , Cambridge: Cambridge University Press, ISBN 0-521-63235-8 , MR 1796805 Nielsen, Michael A. ; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information , Cambridge: Cambridge University Press, ISBN 0-521-63235-8 , MR 1796805 
