Eq. 1phase estimation cost model
\[\mathrm{Cost}=O\!\left(\frac{f\,g(\epsilon)}{\epsilon\,\|W'(H)\|}\right).\]
1. 論文の全体像
この論文は、相関電子系の固有値スペクトルを量子回路に埋め込み、量子位相推定で読み出すための、fault-tolerant 実行を強く意識したアルゴリズム設計論文である。中心的な成果は、電子構造 Hamiltonian と Fermi-Hubbard model に対して、1 回の qubitized quantum walk oracle を 基底サイズに線形な T complexity で実装する明示的回路を与えた点にある。
Core object
\(W\)
時間発展 \(e^{-iH\tau}\) ではなく、\(W\) の位相が \(\pm\arccos(E/\lambda)\) になる walk operator を位相推定する。
Oracle cost
\(O(N+\log(1/\epsilon))\)
SELECT と PREPARE の T complexity を、Hubbard と diagonal-Coulomb basis の電子構造で線形化する。
Fault tolerance
\(\sim10^6\)
表面符号、物理 gate error \(10^{-3}\) 程度の仮定で、古典的に難しい規模を百万 qubit オーダー・数時間で見積もる。
論文の一文要約: LCU で \(H=\sum_l w_lH_l\) と書き、\(|\mathcal L\rangle\) と SELECT によって \(H/\lambda\) を射影として埋め込む。そこから作った Szegedy walk \(W=R_{\mathcal L}\mathrm{SELECT}\) を位相推定すれば、Hamiltonian 固有値 \(E\) は \(E=\lambda\cos\phi\) として回収できる。この \(W\) を実装する oracle を、unary iteration, Majorana selection, QROM, alias-style state preparation で T 数を落として構成する。
この論文が従来法から変えた視点
多くの Hamiltonian simulation は \(e^{-iH\tau}\) を高精度に近似して、その eigenphase から固有値を得る。ここでは、時間発展を作ること自体を主目的にしない。LCU oracle から 厳密に 作れる quantum walk の固有位相が \(\arccos(E/\lambda)\) になることを利用し、近似誤差を回転合成と係数準備に押し込む。これにより、query complexity は \(O(\lambda/\epsilon)\)、1 query の T complexity は対象 Hamiltonian の構造を使って線形にできる。
Hamiltonian \(H\)→LCU \(\sum w_lH_l\)→PREPARE + SELECT→Walk \(W\)→PEA→\(E=\lambda\cos\phi\)
2. 中核主張・定理
Theorem 1: diagonal-Coulomb basis の電子構造
対象は \(N\) 個の spin orbital をもつ、Coulomb operator を対角化する基底での電子構造 Hamiltonian:
\[H=\sum_{p,q}T(p-q)a_p^\dagger a_q+\sum_pU(p)n_p+\sum_{p\ne q}V(p-q)n_pn_q.\]
\(\lambda=\sum_{p,q}|T(p-q)|+\sum_p|U(p)|+\sum_{p\ne q}|V(p-q)|\) と定義すると、固有基底サンプリングと固有値推定の additive error \(\epsilon\) は、概ね
\[T\text{-gates}=24\sqrt2\pi\,\frac{N\lambda}{\epsilon}+O\!\left(\frac{\lambda\log(N/\epsilon)}{\epsilon}\right),\qquad \text{ancilla}=\log(\lambda^3N^5/\epsilon^3)+O(1).\]
重要なのは、従来の second-quantized quantum chemistry の T complexity 表で、この論文の plane-wave qubitization が総 T 数 \(O((N^3+N^2\log(1/\epsilon))/\epsilon)\) に到達すること。
Theorem 2: 周期境界付き平面 Hubbard model
対象は \(N\) spin orbital の square planar Hubbard model:
\[H=-t\sum_{\langle p,q\rangle,\sigma}a_{p,\sigma}^\dagger a_{q,\sigma}+\frac{u}{2}\sum_{p,\alpha\ne\beta}n_{p,\alpha}n_{p,\beta},\qquad \lambda=2Nt+Nu/2.\]
固有値 additive error \(\epsilon\) での phase estimation は、概ね
\[T\text{-gates}=10\sqrt2\pi\,\frac{N\lambda}{\epsilon}+O\!\left(\frac{\lambda\log(N/\epsilon)}{\epsilon}\right).\]
正確には本文の Eq. 61 を使うと、\(S\approx10N\), \(P\) は小さいため、\(\sqrt2\pi\lambda(S+2P)/\epsilon\approx(20\sqrt2\pi t+5\sqrt2\pi u)N^2/\epsilon\)。
\[\text{ancilla}=\log\!\left(\frac{\sqrt2\pi\lambda N^3}{2\epsilon}\right)+O(1).\]
注意: 論文の theorem statement では Hubbard の T gates を \(10\sqrt2\pi N\lambda/\epsilon+O(\lambda\log(N/\epsilon)/\epsilon)\) とまとめているが、本文 Eq. 61 では \(S=10N\) を代入して \(\sqrt2\pi\lambda(S+2P)/\Delta E\) として導出している。
この定理を可能にする 4 つの発明的構成
Unary iteration
選択 index を one-hot 的に一つずつ生成し、\(L\) 個の候補操作を \(4L-4\) T で走査する。
Majorana selection
Jordan-Wigner の \(Y_lZ_{l-1}\cdots Z_0\) を unary iteration で選択的に適用する。
QROM
古典データ \(d_l\) の読み出しを語長非依存の \(4L-4\) T で行う。
Alias-style PREPARE
\(\mathrm{alt}_l,\mathrm{keep}_l\) テーブルで係数準備を \(4L+O(\log(1/\epsilon))\) T にする。
3. 背景とコストモデル
なぜ相関電子系か
分子反応、材料物性、高温超伝導の候補機構などは、多電子波動関数の entanglement が強いと古典近似が難しくなる。Feynman 型の「量子系を量子計算機でシミュレートする」動機に直結する。論文は特に、Fermi-Hubbard model と molecular electronic structure Hamiltonian を対象にする。
なぜ T gate が主コストか
表面符号の Clifford gate は比較的安いが、非 Clifford の T gate は magic-state distillation を必要とし、時間と物理 qubit 数の主要なボトルネックになる。したがってこの論文は gate complexity ではなく、fault-tolerant 実装で実効的に支配的な T complexity に焦点を置く。
位相推定に必要なもの
Hamiltonian \(H\) の固有値 \(E_k\) を知りたい場合、\(H\) と固有基底を共有し、その固有位相が \(E_k\) の既知関数になる unitary \(W(H)\) を作る。従来は \(e^{-iH\tau}\) が中心だったが、本論文は \(e^{i\arccos(H/\lambda)}\) 型の walk operator を直接使う。
式で見る「時間発展」と「walk」の違い
時間発展型
\[W(H)\approx e^{-iH\tau},\qquad \|W'(H)\|^{-1}=1/\tau.\]
小さな \(\tau\) を使うと位相からエネルギーへ戻す感度が悪くなる。
walk 型
\[W(H)=e^{i\arccos(H/\lambda)},\qquad \|W'(H)\|^{-1}\le\lambda.\]
query complexity は \(O(\lambda/\epsilon)\)。\(W\) を厳密な oracle circuit として組み立てる。
4. LCU / qubitization の核
論文の抽象フレームワークは LCU、すなわち Hamiltonian を unitary の非負重み付き和として書くところから始まる。
\[H=\sum_{l=0}^{L-1}w_lH_l,
\qquad w_l\ge0,\quad H_l^2=\mathbf1,
\qquad \lambda=\sum_lw_l.\]
係数の符号や複素位相は \(H_l\) 側に吸収し、\(w_l\) は非負に揃える。必要な oracle は次の 2 つ。
PREPARE
\[|0\rangle\mapsto|\mathcal L\rangle=\sum_l\sqrt{w_l/\lambda}|l\rangle.\]
係数の平方根を amplitude として選択 register に準備する。
SELECT
\[|l\rangle|\psi\rangle\mapsto|l\rangle H_l|\psi\rangle.\]
選択 register の値に対応する Pauli/Jordan-Wigner string を system register に適用する。
これにより、SELECT を \(|\mathcal L\rangle\) で挟むと \(H/\lambda\) が出る:
\[(\langle\mathcal L|\otimes\mathbf1)\mathrm{SELECT}(|\mathcal L\rangle\otimes\mathbf1)=H/\lambda.\]
Szegedy walk の固有位相
反射 \(R_{\mathcal L}=2|\mathcal L\rangle\langle\mathcal L|\otimes\mathbf1-\mathbf1\) を定義し、
\[W=R_{\mathcal L}\mathrm{SELECT}\]
とする。\(H|k\rangle=E_k|k\rangle\) なら、\(|\mathcal L\rangle|k\rangle\) と、それに直交する \(|\phi_k\rangle\) の 2 次元部分空間で \(W\) は
\[\begin{pmatrix}E_k/\lambda&\sqrt{1-(E_k/\lambda)^2}\\-\sqrt{1-(E_k/\lambda)^2}&E_k/\lambda\end{pmatrix}\]
として作用する。したがって eigenphase は \(\pm\arccos(E_k/\lambda)\)。位相推定の出力 \(\phi\) から、
\[E_k=\lambda\cos\phi\]
でエネルギーを復元する。
5. Heisenberg-limited 位相推定と誤差管理
制御 inverse の trick
通常の位相推定では、制御 qubit が 0 のとき identity、1 のとき \(W^n\) を適用する。論文は、0 のとき \((W^\dagger)^n\)、1 のとき \(W^n\) になるようにして、実効的な位相差を 2 倍にする。ただし \(\pi\) の曖昧さが出るため、最初に通常の制御 \(W\) を入れて disambiguation する。
\[R_{\mathcal L}W^nR_{\mathcal L}=(W^\dagger)^n.\]
最適な位相推定資源状態
m 個の制御 qubit は一様重ね合わせではなく、sine 型の状態に準備する。
\[\chi_m|0\rangle^{\otimes m}\mapsto\sqrt{\frac{2}{2^m+1}}\sum_{n=0}^{2^m-1}\sin\!\left(\frac{\pi(n+1)}{2^m+1}\right)|n\rangle.\]
この状態は Holevo variance を最適化し、必要な \(W\) query 数は \(2^m\) 程度になる。論文では \(\chi_m\) と semiclassical inverse QFT のコストは \(O(\tilde m)\) で、全体の \(O(2^m)\) に比べて無視できると扱う。
誤差の 3 要素
\(\epsilon_{\rm PEA}\)
有限 m の位相推定に由来。主要項は \(\pi/2^{m+1}\)。
\(\epsilon_{\rm PREP}\)
係数準備・回転合成による Hamiltonian coefficient の誤差。
\(\epsilon_{\rm QFT}\)
semiclassical inverse QFT の回転合成誤差。
\[\Delta E\le \lambda\sqrt{\left(\frac{\pi}{2^{m+1}}\right)^2+(\epsilon_{\rm PREP}+\pi\epsilon_{\rm QFT})^2}.\]
ここから、
\[m=\left\lceil\log\!\left(\frac{\sqrt2\pi\lambda}{2\Delta E}\right)\right\rceil,
\quad \epsilon_{\rm PREP}\le\frac{\sqrt2\Delta E}{4\lambda},
\quad \epsilon_{\rm QFT}\le\frac{\sqrt2\Delta E}{4\pi\lambda}
\]
が導かれる。SELECT query 数は \(2^m<\sqrt2\pi\lambda/\Delta E\)。SELECT の T cost を \(S\)、PREPARE の T cost を \(P\) とすると、主要コストは
\[\frac{\sqrt2\pi\lambda(S+2P)}{\Delta E}.\]
6. 低 T complexity の基本部品
Unary iteration
選択 register \(|l\rangle\) が \(0\le l AND を計算すると 4 T、AND の uncompute は測定と Clifford feedforward で 0 T。これが \(4L-4\) の定数の出所。\[|c\rangle|l\rangle|\psi\rangle\mapsto |c\rangle|l\rangle(X_l)^c|\psi\rangle.\]
Selective Majorana fermion operator
Jordan-Wigner 変換では、fermion operator は長い \(Z\) string を伴う。論文で必要なのは、
\[|l\rangle|\psi\rangle\mapsto |l\rangle Y_lZ_{l-1}\cdots Z_0|\psi\rangle.
\]
unary iteration に accumulator を組み合わせると、\(l\) より下の範囲に \(Z\) をかけ、ちょうど \(l\) に \(Y\) をかける範囲演算が 1 pass で実現できる。T count は \(4L-4\)。
QROM
QROM は classical read-only table \(d_0,\ldots,d_{L-1}\) を量子 index で読む。
\[\mathrm{QROM}_{\vec d}\sum_l\alpha_l|l\rangle|0\rangle=\sum_l\alpha_l|l\rangle|d_l\rangle.\]
この論文の実装は data word 長に T count が依存しない。T は unary iteration の \(4L-4\) のみ。QRAM とは違い、計算中に書き込むことはできないが、oracle 係数テーブルを読む用途には十分。
Subsampling coefficient oracle / alias-style PREPARE
任意の \(L\) 個の係数を持つ状態を、直接精密回転で全部作ると \(O(L\log(L/\epsilon))\) になりがちである。論文は classical alias sampling の量子版を使う。uniform に \(l\) を選び、QROM で \(\mathrm{alt}_l\) と \(\mathrm{keep}_l\) を読む。さらに uniform な \(\sigma\) と比較し、条件付きで \(l\) と \(\mathrm{alt}_l\) を swap する。
\[\frac{\mathrm{keep}_l+\sum_{k:\mathrm{alt}_k=l}(2^\mu-\mathrm{keep}_k)}{2^\mu L}=\tilde\rho_l.\]
これにより、\(\lambda\) を人工的に増やさず、T complexity は \(4L+O(\log(1/\epsilon))\) 型になる。
7. 電子構造 Hamiltonian の構成
対象 Hamiltonian
論文は、Coulomb 項を対角化する second-quantized basis を想定する。この形式には plane-wave dual basis、finite difference / finite element 的な表現、Gausslet basis などが含まれる。
\[H=\sum_{p,q,\sigma}T(p-q)a_{p,\sigma}^\dagger a_{q,\sigma}+\sum_{p,\sigma}U(p)n_{p,\sigma}+\sum_{(p,\alpha)\ne(q,\beta)}V(p-q)n_{p,\alpha}n_{q,\beta}.\]
Jordan-Wigner 後は \(X\vec ZX\), \(Y\vec ZY\), \(ZZ\), \(Z\), identity の組み合わせになる。論文が利用する構造は、項の数は \(O(N^2)\) でも、係数の unique values は \(O(N)\) 程度である点。
SELECTCHEM
index register は \(|\theta\rangle,|U\rangle,|V\rangle,|p\rangle,|\alpha\rangle,|q\rangle,|\beta\rangle\)。\(U,V\) bits がどのタイプの項かを示し、\(\theta\) が符号を示す。SELECTCHEM は次を実装する。
\[\begin{cases}Z_{p,\alpha},& U=1,V=0,(p,\alpha)=(q,\beta),\\Z_{p,\alpha}Z_{q,\beta},&U=0,V=1,(p,\alpha)\ne(q,\beta),\\X_{p,\alpha}\vec Z X_{q,\alpha},&U=0,V=0,pq,\alpha=\beta.
\end{cases}\]
Fig. 14 の回路で、Majorana selector が 3 回程度使われる。T count は \(12N+8\log N+O(1)\)、ancilla は \(N+3\log N+O(1)\) qubits 程度。
PREPARECHEM
PREPARECHEM は、\(U,T,V\) 型の係数振幅をまとめて作る。まず SUBPREPARE が \(d=p-q\) の係数を読む。QROM による data-loading が支配的で、T count は \(6N+O(\mu+\log N)\)。その後、\(q\) の uniform superposition、spin bit の条件付き準備、\(d+q\to p\) 変換で目的状態にする。
\[P=6N+O(\log(N/\epsilon)),\qquad S=12N+O(\log N).\]
電子構造の資源式
\[\lambda=\sum_{p,q}|T(p-q)|+\sum_p|U(p)|+\sum_{p\ne q}|V(p-q)|.
\]
plane-wave dual basis では、固定密度 \(N\propto\Omega\) の成長で \(\lambda\in O(N^2)\)。したがって総 T complexity は厳密上界として \(O(N^3/\Delta E)\)。有限サイズ推定では jellium で \(\lambda\sim N^{5/3}\) 程度に見えるため、実効的にはより軽い。
\[T_{\rm total}\approx\frac{24\sqrt2\pi\lambda N}{\Delta E},\qquad A_{\rm total}=\log\!\left(\frac{4\sqrt2\pi\lambda^3N^5}{\Delta E^3}\right)+O(1).\]
8. Fermi-Hubbard model の構成
対象 Hamiltonian
\[H=-t\sum_{\langle p,q\rangle,\sigma}a_{p,\sigma}^\dagger a_{q,\sigma}+\frac{u}{2}\sum_{p,\alpha\ne\beta}n_{p,\alpha}n_{p,\beta}.\]
Jordan-Wigner 後は、最近接 hopping 由来の \(-X\vec ZX/2\), \(-Y\vec ZY/2\)、onsite interaction 由来の \(ZZ\)、local \(-Z\)、constant になる。
SELECTHUB
index は \(|U\rangle,|V\rangle,|p_x\rangle,|p_y\rangle,|\alpha\rangle,|q_x\rangle,|q_y\rangle,|\beta\rangle\)。周期境界と平面格子の並進対称性を使うため、電子構造一般の場合より少し軽い。
\[S_{\rm HUB}=10N+O(\log N).\]
PREPAREHUB
Hubbard では係数が実質 3 種類だけである: \(-XZX\) / \(-YZY\) の \(t/2\)、\(ZZ\) の \(u/8\)、local \(-Z\) の \(u/4\)。したがって PREPARE は数個の controlled rotation と uniform register の組み合わせで済む。
\[P_{\rm HUB}=O(\log(N/\epsilon)),\qquad \lambda=2Nt+Nu/2.\]
主要コストは SELECT 側が支配し、
\[T_{\rm total}\approx\frac{20\sqrt2\pi t+5\sqrt2\pi u}{\Delta E}N^2.
\]
中間相互作用 \(u/t=4\) かつ \(\Delta E=t/100\) なら、
\[T_{\rm total}<1.8\times10^4N^2,\qquad A<12+3\log N.\]
9. 局所 Hamiltonian と Lieb-Robinson bound の利用
論文の Sec. V D は、Hubbard model の局所性をさらに使えば、Haah et al. の Lieb-Robinson 型シミュレーションと組み合わせて \(\tilde O(N/\epsilon)\) 型のスケーリングも狙えると述べる。これは本論文の fault-tolerant 数値評価の主対象ではないが、漸近的には重要な拡張である。
\[\left\|e^{-iH_{ABC}t}-e^{-iH_{AB}t}e^{iH_Bt}e^{-iH_{BC}t}\right\|\in O\!\left(\sum_X\|h_X\|e^{vt-\mu\mathrm{dist}(A,C)}\right).
\]
直観は、局所相互作用の情報伝播が有限速度であるため、大きい lattice を patch に分割し、境界誤差を指数的に小さくできること。patch ごとの時間発展を qubitization で実装し、本論文の oracle をその中で使う。
10. Fault-tolerant 実装と表面符号資源
T gate と magic state
表面符号では T gate のために magic state
\[|T\rangle=\frac{|0\rangle+e^{i\pi/4}|1\rangle}{\sqrt2}\]
を蒸留し消費する。Clifford 操作は比較的安いため、物理 qubit 数と時間は T-state factory と T count が支配する。
plumbing piece による見積もり
論文は、Majorana circuit と QROM circuit が全体 overhead の 90% 以上を占めると見なし、AND compute/uncompute、naked CNOT、active subcircuit に分解する。さらに surface-code braid diagram に落とし込み、手計算と自動ツールの両方で見積もった。
手計算見積り
Table VII。例えば electronic structure \(N=128\) で \(p=10^{-3}\) なら \(2.4\times10^6\) physical qubits、約 9.9 h。
自動生成見積り
Table IX。手計算より 10–20% 程度大きいが、実行時間はほぼ一致。これは資源見積りの頑健性を補強する。
論文の実践的結論: 古典的に難しい jellium や Hubbard のいくつかの instance は、物理 error rate \(10^{-3}\)、表面符号 cycle 1 μs の仮定で、百万 qubit オーダー・数時間から数十時間の範囲に入る。
11. 図表ガイド: どのページの図が何を示すか
原論文の図は、単なる挿絵ではなく、oracle の T complexity を支える回路等式そのものを示している。以下はページ番号付きの読み解き一覧。
| 場所 | 対象 | 何を読むべきか |
|---|---|---|
| Fig. 1 / p.6 | controlled walk operator | 制御付き \(W=R_{\mathcal L}\mathrm{SELECT}\) の構成。PREPARE, SELECT, 反射 \(R_{\mathcal L}\) がどの順に使われるかを示す。 |
| Fig. 2 / p.7 | Heisenberg-limited PEA | 最適な位相推定資源状態 \(\chi_m\) を使い、制御 \(R_{\mathcal L}\) を挿入して \(W^n\) と \((W^\dagger)^n\) を効率よく実現する回路。 |
| Fig. 3 / p.9 | naive total-control circuit | 選択レジスタの全ビットで制御して \(X_l\) をかける素朴な方法。ここから冗長な制御を除去して unary iteration に変形する。 |
| Fig. 4 / p.10 | AND computation/uncomputation | Toffoli 的な AND の Clifford+T 実装。計算は 4 T、非計算は 0 T で済むという後続回路の基礎。 |
| Fig. 5-7 / p.10-11 | sawtooth to unary iteration | sawtooth 回路を隣接 AND の併合で圧縮し、\(4L-4\) T の indexed operation を得る流れ。 |
| Fig. 8-9 / p.12 | ranged operation and Majorana | accumulator を使って範囲演算を作り、\(Y_lZ_{l-1}\cdots Z_0\) という Majorana 選択を \(4L-4\) T で実装。 |
| Fig. 10 / p.13 | QROM | 古典データベース \(d_l\) を量子添字 \(|l angle\) で読み出す QROM。語長に依存せず \(4L-4\) T。 |
| Fig. 11-13 / p.14-15 | SUBPREPARE / alias sampling | alt/keep テーブルと uniform register を使い、振幅準備の合成コストを加法的にする。Fig.13 は確率質量の再配分を可視化。 |
| Fig. 14-16 / p.17-20 | electronic-structure oracles | SELECTCHEM, SUBPREPARE, PREPARECHEM の具体回路。T ボトルネックは Majorana と QROM。 |
| Fig. 17 / p.21 | jellium lambda scaling | rs=10 Bohr 半径、half filling の jellium で \(\lambda\) が経験的に \(\sim N^{5/3}\) と見えるプロット。 |
| Fig. 18 / p.22 | materials lambda scaling | Li, diamond, Si, LiH, graphite などの \(\lambda\) スケーリング。固定セル、固定 qubit 数、固定点密度の 3 種を比較。 |
| Fig. 19-20 / p.24 | Hubbard oracles | 周期境界付き平面 Hubbard の SELECT/PREPARE。係数が 3 種だけなので PREPARE が特に軽い。 |
| Fig. 21-24 / p.27-28 | surface-code primitives | AND, uncompute AND, Majorana inner loop, T-state distillation を plumbing piece として可視化。 |
| Tables VI-IX / p.29-31 | fault-tolerant estimates | 対象問題ごとの W query 数、Majorana/QROM 呼び出し数、手計算・自動生成の物理 qubit 数と実行時間。 |
ページ別の完全ウォークスルー
本文・図・表・付録・参考文献まで、ページ単位で何が行われているかを整理する。
| Page | 内容 |
|---|---|
| 1 | タイトル、著者、abstract、introduction。問題設定は「相関電子スペクトルを fault-tolerant 量子回路で効率的に符号化する」。Eq. (1) の位相推定コストモデルが始まる。 |
| 2 | Eq. (1)–(4) により、時間発展型と walk 型のコスト感度を比較。T gate と表面符号を主要コストにする理由を説明。 |
| 3 | Table I と Table II。電子構造と Hubbard model の過去手法に対する T complexity の進展を一覧化し、本論文の位置付けを明確化。 |
| 4 | Theorem 1 と Theorem 2、および論文構成。電子構造・Hubbard の最終 T count と ancilla scaling を提示。 |
| 5 | Sec. II: LCU oracle の定義。Eq. (5)–(11) で PREPARE, SELECT, \(H/\lambda\) projection, walk operator, invariant subspace を導入。 |
| 6 | Eq. (12)–(16) と Fig. 1。Szegedy walk の 2 次元作用を導き、\(rccos(E/\lambda)\) の固有位相を示す。 |
| 7 | Fig. 2 と Eq. (17)–(20)。Heisenberg-limited phase estimation と sine-shaped optimal resource state の準備。 |
| 8 | Eq. (21)–(28)。phase error、PREPARE error、QFT error の合成、query count、係数誤差 bound。Sec. III の primitive 導入。 |
| 9 | Eq. (29) と Fig. 3。indexed operation の素朴な total-control 実装から unary iteration へ向かう動機。 |
| 10 | Fig. 4–5。AND compute/uncompute の T count と sawtooth circuit の形成。 |
| 11 | Fig. 6–7、Eq. (30)–(31)。隣接 AND の併合、unary iteration の完成、Majorana selector と QROM の導入。 |
| 12 | Fig. 8–9。accumulator を使う range operation と、\(Y_lZ_{l-1}\cdots Z_0\) の Majorana 選択回路。 |
| 13 | Fig. 10、Eq. (31)–(34)。QROM の具体回路、read-only と QRAM の違い、junk register を許す PREPARE の一般化。 |
| 14 | Eq. (35)–(40) と Fig. 11。\(\mu\)-bit 係数近似、alt/keep QROM、alias sampling 型準備条件。 |
| 15 | Fig. 12–13 と Sec. IV の開始。uniform superposition の振幅増幅回路と alias table の可視例、電子構造 Hamiltonian へ移行。 |
| 16 | Eq. (41)–(43)。second-quantized 電子構造、Jordan-Wigner 後の Pauli 形式、plane-wave dual coefficients。 |
| 17 | Eq. (44)–(45) と Fig. 14。SELECTCHEM の case definition と spin-orbital から qubit への mapping。 |
| 18 | Eq. (46)–(48) と Fig. 15。PREPARECHEM と SUBPREPARE の target state、係数振幅・符号 bit。 |
| 19 | Eq. (49)–(52)。\(q\) と spin の条件付き準備、\(d+q o p\) 変換、電子構造の \(\lambda\) 定義。 |
| 20 | Fig. 16 と Eq. (53)–(55)。PREPARECHEM 全体回路、電子構造の T count と ancilla count。 |
| 21 | Fig. 17 と Table III。jellium での \(\lambda\) empirical scaling と具体的な logical T/qubit/ancilla 見積り。 |
| 22 | Fig. 18 と Sec. V 開始。実材料での \(\lambda\) scaling、Hubbard model の物理的背景。 |
| 23 | Eq. (56)–(58)。Hubbard Hamiltonian、Jordan-Wigner 形式、SELECTHUB case definition。 |
| 24 | Fig. 19–20 と Eq. (59)–(60)。Hubbard SELECT/PREPARE 回路と \(\lambda=2Nt+Nu/2\)。 |
| 25 | Eq. (61)–(66)。Hubbard の T count / ancilla、\(u/t=4\) benchmark、Lieb-Robinson patching lemma。 |
| 26 | Theorem 4 と Sec. VI 開始、Table V。局所 Hamiltonian simulation と fault-tolerant overhead 分解。 |
| 27 | Fig. 21–22。surface-code AND compute/uncompute の braid diagram と plumbing piece 深さ。 |
| 28 | Fig. 23–24。Majorana inner loop の surface-code 実装、T-state distillation factory。 |
| 29 | Table VI–VII。対象 instance ごとの W query/Majorana/QROM 回数、手計算の物理 qubit 数と時間。 |
| 30 | Table VIII。自動ツールによる Majorana/QROM circuit の plumbing-piece volume 見積り。 |
| 31 | Table IX と conclusion 開始。自動ツールの物理 qubit/time 見積りと、全体の達成点のまとめ。 |
| 32 | Conclusion 続きと Appendix 開始。将来課題: Gausslet、first quantization、物理 qubit 数削減。係数誤差解析へ。 |
| 33 | Appendix Eq. (A1)–(A10) と references 開始。\( ilde H\) 係数誤差から walk phase error への bound を導出。 |
| 34 | References。LCU、qubitization、Trotter、quantum chemistry、surface code などの先行研究。 |
| 35 | References 続き。OpenFermion、Jordan-Wigner、jellium、DFT、Hubbard benchmark など。 |
| 36 | References 終了。Lieb-Robinson、surface-code correction、lattice surgery など。 |
12. 全主要表の再整理
Table I: 電子構造 Hamiltonian の T complexity 進展
| Year | Reference | Basis | Algorithm | Oracle T gates | PEA queries | Total T gates |
|---|---|---|---|---|---|---|
| 2005 | Aspuru-Guzik et al. [7] | Gaussians | Trotterization | \(O(\mathrm{poly}(N/\epsilon))\) | \(O(\mathrm{poly}(N/\epsilon))\) | \(O(\mathrm{poly}(N/\epsilon))\) |
| 2010 | Whitfield et al. [44] | Gaussians | Trotterization | \(O(N^4\log(1/\epsilon))\) | \(O(\mathrm{poly}(N/\epsilon))\) | \(O(\mathrm{poly}(N/\epsilon))\) |
| 2013 | Wecker et al. [45] | Gaussians | Trotterization | \(O(N^4\log(1/\epsilon))\) | \(O(N^6/\epsilon^{3/2})\) | \(O(N^{10}\log(1/\epsilon)/\epsilon^{3/2})\) |
| 2014 | McClean et al. [46] | Gaussians | Trotterization | \(O(\sim N^2\log(1/\epsilon))\) | \(O(N^6/\epsilon^{3/2})\) | \(O(\sim N^8\log(1/\epsilon)/\epsilon^{3/2})\) |
| 2014 | Poulin et al. [47] | Gaussians | Trotterization | \(O(N^4\log(1/\epsilon))\) | \(O(\sim N^2/\epsilon^{3/2})\) | \(O(\sim N^6\log(1/\epsilon)/\epsilon^{3/2})\) |
| 2014 | Babbush et al. [48] | Gaussians | Trotterization | \(O(N^4\log(1/\epsilon))\) | \(O(\sim N/\epsilon^{3/2})\) | \(O(\sim N^5\log(1/\epsilon)/\epsilon^{3/2})\) |
| 2015 | Babbush et al. [42] | Gaussians | Taylorization | \(\tilde O(N)\) | \(O(N^4\log(N/\epsilon)/(\epsilon\log\log(N/\epsilon)))\) | \(\tilde O(N^5/\epsilon)\) |
| 2016 | Low et al. [25] | Gaussians | Qubitization | \(\tilde O(N)\) | \(O(N^4/\epsilon+\log(N/\epsilon)/(\epsilon\log\log(N/\epsilon)))\) | \(\tilde O(N^5/\epsilon)\) |
| 2017 | Babbush et al. [39] | Plane waves | Taylorization | \(\tilde O(N)\) | \(O(N^{8/3}\log(N/\epsilon)/(\epsilon\log\log(N/\epsilon)))\) | \(\tilde O(N^{11/3}/\epsilon)\) |
| 2017 | Berry et al. [26] | Plane waves | Qubitization | \(\tilde O(N)\) | \(O(N^{8/3}/\epsilon)\) | \(\tilde O(N^{11/3}/\epsilon)\) |
| 2018 | Kivlichan et al. [40] | Plane waves | Trotterization | \(O(N^2+N\log N\log(1/\epsilon))\) | \(O(\sim N^{3/2}/\epsilon^{3/2})\) | \(O(\sim N^{7/2}/\epsilon^{3/2})\) |
| 2018 | This paper | Plane waves | Qubitization | \(O(N+\log(1/\epsilon))\) | \(O(N^2/\epsilon)\) | \(O((N^3+N^2\log(1/\epsilon))/\epsilon)\) |
Table II: Hubbard model の T complexity 進展
| Year | Reference | Algorithm | Ancillae | Oracle T gates | PEA queries | Total T gates |
|---|---|---|---|---|---|---|
| 1997 | Abrams et al. [4] | Trotterization | \(O(1)\) | \(O(N\log(1/\epsilon))\) | \(O(\mathrm{poly}(N/\epsilon))\) | \(O(\mathrm{poly}(N/\epsilon))\) |
| 2015 | Wecker et al. [50] | Trotterization | \(O(1)\) | \(O(N\log(1/\epsilon))\) | \(O(N^2/\epsilon^{3/2})\) | \(O(N^3\log(1/\epsilon)/\epsilon^{3/2})\) |
| 2015 | Babbush et al. [42] | Taylorization | \(O(\log(N/\epsilon)/\log\log(N/\epsilon))\) | \(O(N\log(1/\epsilon))\) | \(O(N\log(N/\epsilon)/(\epsilon\log\log(N/\epsilon)))\) | \(O(N^2\log(N/\epsilon)\log(1/\epsilon)/(\epsilon\log\log(N/\epsilon)))\) |
| 2016 | Low et al. [25] | Qubitization | \(O(\log N)\) | \(O(N\log(N/\epsilon))\) | \(O(N/\epsilon+\log(N/\epsilon)/(\epsilon\log\log(N/\epsilon)))\) | \(O(N^2\log(N/\epsilon)/\epsilon)\) |
| 2017 | Berry et al. [26] | Qubitization | \(O(\log N)\) | \(O(N\log(N/\epsilon))\) | \(O(N/\epsilon)\) | \(O(N^2\log(N/\epsilon)/\epsilon)\) |
| 2017 | Poulin et al. [27] | Qubitization | \(O(N)\) | \(O(N+\log(1/\epsilon))\) | \(O(N/\epsilon)\) | \(O((N^2+N\log(1/\epsilon))/\epsilon)\) |
| 2018 | Haah et al. [49] | Qubitization | \(O(\log N)\) | \(O(N\log(N/\epsilon))\) | \(\tilde O(1/\epsilon)\) | \(\tilde O(N/\epsilon)\) |
| 2018 | Kivlichan et al. [40] | Trotterization | \(O(\log N)\) | \(O(N+\log N\log(1/\epsilon))\) | \(O(\sim 1/\epsilon^{3/2})\) | \(O(\sim N/\epsilon^{3/2})\) |
| 2018 | This paper | Qubitization | \(O(\log N)\) | \(O(N+\log(1/\epsilon))\) | \(\tilde O(1/\epsilon)\) | \(\tilde O(N/\epsilon)\) |
Table III: jellium 資源見積もり
| Spin orbitals | lambda value | Logical ancilla | Total logical qubits | Total logical T count |
|---|---|---|---|---|
| 54 | 5 | 69 | 123 | \(1.8\times 10^7\) |
| 128 | 23 | 82 | 210 | \(1.9\times 10^8\) |
| 250 | 64 | 91 | 341 | \(1.1\times 10^9\) |
| 1024 | 640 | 112 | 1136 | \(4.3\times 10^{10}\) |
Table IV: Hubbard 資源見積もり
| Dimension | Spin orbitals | Logical ancilla | Total logical qubits | Total logical T count |
|---|---|---|---|---|
| \(6\times6\) | 72 | 33 | 105 | \(9.3\times10^7\) |
| \(8\times8\) | 128 | 33 | 161 | \(2.9\times10^8\) |
| \(10\times10\) | 200 | 36 | 236 | \(7.1\times10^8\) |
| \(20\times20\) | 800 | 42 | 842 | \(1.2\times10^{10}\) |
Table V: Majorana/QROM circuit breakdown
| Circuit | Compute ANDs | Uncompute ANDs | Naked CNOTs | Subcircuits |
|---|---|---|---|---|
| Fig. 9 Majorana | \(N-1\) | \(N-1\) | \(0.5N\) | \(0.5N\) |
| Fig. 10 QROM | \(1.5N-1\) | \(1.5N-1\) | \(0.75N\) | \(0.75N\) |
Table VI: fault-tolerant 入力パラメータ
| System | Spin orbitals N | W queries | Majorana_N | Majorana_N/2 | QROM_3N/2 | Max data qubits |
|---|---|---|---|---|---|---|
| Hubbard | 72 | \(1.3\times10^5\) | \(2.5\times10^5\) | \(1.3\times10^5\) | 0 | 105 |
| Hubbard | 128 | \(2.3\times10^5\) | \(4.6\times10^5\) | \(2.3\times10^5\) | 0 | 161 |
| Hubbard | 200 | \(3.6\times10^5\) | \(7.2\times10^5\) | \(3.6\times10^5\) | 0 | 236 |
| Hubbard | 800 | \(1.4\times10^6\) | \(2.8\times10^6\) | \(1.4\times10^6\) | 0 | 842 |
| Electronic structure | 54 | \(1.4\times10^4\) | \(4.2\times10^4\) | 0 | \(2.8\times10^4\) | 123 |
| Electronic structure | 128 | \(6.3\times10^4\) | \(1.9\times10^5\) | 0 | \(1.3\times10^5\) | 210 |
| Electronic structure | 250 | \(1.7\times10^5\) | \(5.3\times10^5\) | 0 | \(3.5\times10^5\) | 341 |
| Electronic structure | 1024 | \(1.8\times10^6\) | \(5.3\times10^6\) | 0 | \(3.5\times10^6\) | 1136 |
Table VII: 手計算による physical qubit / time overhead
| System | N | Physical qubits p=1e-3 | Physical qubits p=1e-4 | Execution h p=1e-3 | Execution h p=1e-4 |
|---|---|---|---|---|---|
| Hubbard | 72 | \(1.4\times10^6\) | \(4.4\times10^5\) | 4.6 | 2.6 |
| Hubbard | 128 | \(2.1\times10^6\) | \(6.6\times10^5\) | 15 | 8.4 |
| Hubbard | 200 | \(3.2\times10^6\) | \(8.9\times10^5\) | 40 | 21 |
| Hubbard | 800 | \(1.4\times10^7\) | \(3.6\times10^6\) | \(6.7\times10^2\) | \(3.7\times10^2\) |
| Electronic structure | 54 | \(1.4\times10^6\) | \(3.9\times10^5\) | 0.82 | 0.43 |
| Electronic structure | 128 | \(2.4\times10^6\) | \(8.1\times10^5\) | 9.9 | 5.6 |
| Electronic structure | 250 | \(4.4\times10^6\) | \(1.2\times10^6\) | 58 | 30 |
| Electronic structure | 1024 | \(2.0\times10^7\) | \(4.8\times10^6\) | \(2.7\times10^3\) | \(1.4\times10^3\) |
Table VIII: 自動生成による plumbing-piece 見積り
| System | Circuit | T count | Area PP^2 | Time PP | Volume PP^3 | Braided volume PP^3 |
|---|---|---|---|---|---|---|
| Hubbard | Majorana\(_{72}\) | 284 | \(17\times16\) | 1840 | 500480 | 429624 |
| Hubbard | Majorana\(_{128}\) | 508 | \(25\times16\) | 3252 | 1300800 | 1155817 |
| Hubbard | Majorana\(_{200}\) | 796 | \(36\times16\) | 5080 | 2926080 | 2637504 |
| Hubbard | Majorana\(_{800}\) | 3196 | \(123\times16\) | 20262 | 39875616 | 37451032 |
| Electronic | Majorana\(_{54}\) | 212 | \(20\times16\) | 1382 | 442240 | 365717 |
| Electronic | Majorana\(_{128}\) | 508 | \(32\times16\) | 3252 | 1665024 | 1473563 |
| Electronic | Majorana\(_{250}\) | 996 | \(51\times16\) | 6342 | 5175072 | 4685164 |
| Electronic | Majorana\(_{1024}\) | 4092 | \(165\times16\) | 25932 | 68460480 | 64114531 |
| Electronic | QROM\(_{3N/2}, N=54\) | 320 | \(20\times16\) | 2068 | 661760 | 558098 |
| Electronic | QROM\(_{3N/2}, N=128\) | 764 | \(32\times16\) | 4872 | 2494464 | 2273711 |
| Electronic | QROM\(_{3N/2}, N=250\) | 1496 | \(51\times16\) | 9508 | 7758528 | 7272549 |
| Electronic | QROM\(_{3N/2}, N=1024\) | 6140 | \(165\times16\) | 38892 | 102674880 | 100399903 |
Table IX: 自動生成による physical qubit / time overhead
| System | N | Physical qubits p=1e-3 | Physical qubits p=1e-4 | Execution h p=1e-3 | Execution h p=1e-4 |
|---|---|---|---|---|---|
| Hubbard | 72 | \(1.7\times10^6\) | \(5.3\times10^5\) | 4.6 | 2.6 |
| Hubbard | 128 | \(2.4\times10^6\) | \(7.8\times10^5\) | 15 | 8.4 |
| Hubbard | 200 | \(3.8\times10^6\) | \(1.0\times10^6\) | 40 | 21 |
| Hubbard | 800 | \(1.5\times10^7\) | \(4.2\times10^6\) | \(6.7\times10^2\) | \(3.7\times10^2\) |
| Electronic structure | 54 | \(1.7\times10^6\) | \(4.7\times10^5\) | 0.85 | 0.44 |
| Electronic structure | 128 | \(2.9\times10^6\) | \(9.5\times10^5\) | 10 | 5.7 |
| Electronic structure | 250 | \(5.1\times10^6\) | \(1.4\times10^6\) | 58 | 30 |
| Electronic structure | 1024 | \(2.3\times10^7\) | \(5.6\times10^6\) | \(2.8\times10^3\) | \(1.4\times10^3\) |
13. 式インデックス
主要式を番号順に整理した。論文の本文 Eq. (1)–(67) と付録 Eq. (A1)–(A10) を、MathJax で読める形にしている。
Eq. 2time-evolution encoding derivative
\[W(H)\approx e^{-iH\tau},\qquad \|W'(H)\|^{-1}=\|-i\tau e^{-iH\tau}\|^{-1}=\frac{1}{\tau}.\]
Eq. 3modern simulation query scaling
\[O\!\left(\lambda\tau+\frac{\log(1/\epsilon)}{\log\log(1/\epsilon)}\right).\]
Eq. 4walk encoding derivative bound
\[W(H)=e^{i\arccos(H/\lambda)},\qquad \|W'(H)\|^{-1}=\left\|\frac{-i e^{i\arccos(H/\lambda)}}{\sqrt{\lambda^2-H^2}}\right\|^{-1}\le \lambda.\]
Eq. 5LCU decomposition
\[H=\sum_{l=0}^{L-1} w_l H_l,\qquad w_l\ge 0,\quad H_l^2=\mathbf{1}.\]
Eq. 6PREPARE oracle
\[\mathrm{PREPARE}\equiv\sum_{l=0}^{L-1}\sqrt{\frac{w_l}{\lambda}}\,|l\rangle\langle 0|,\qquad |0\rangle^{\otimes \log L}\mapsto |\mathcal L\rangle=\sum_l\sqrt{\frac{w_l}{\lambda}}|l\rangle,\quad \lambda=\sum_l w_l.\]
Eq. 7SELECT oracle
\[\mathrm{SELECT}\equiv\sum_{l=0}^{L-1}|l\rangle\langle l|\otimes H_l,\qquad |l\rangle|\psi\rangle\mapsto |l\rangle H_l|\psi\rangle.\]
Eq. 8Hamiltonian as projection
\[(\langle\mathcal L|\otimes \mathbf 1)\,\mathrm{SELECT}\,(|\mathcal L\rangle\otimes\mathbf 1)=\frac{1}{\lambda}\sum_l w_lH_l=\frac{H}{\lambda}.\]
Eq. 9Szegedy walk
\[W\equiv R_{\mathcal L}\,\mathrm{SELECT},\qquad R_{\mathcal L}\equiv 2|\mathcal L\rangle\langle\mathcal L|\otimes\mathbf 1-\mathbf 1.\]
Eq. 10SELECT is a reflection
\[\mathrm{SELECT}^2=\left(\sum_l |l\rangle\langle l|\otimes H_l\right)^2=\sum_l |l\rangle\langle l|\otimes H_l^2=\mathbf 1.\]
Eq. 11orthogonal state in invariant subspace
\[|\phi_k\rangle=\frac{(\mathrm{SELECT}-E_k/\lambda\,\mathbf 1)|\mathcal L\rangle|k\rangle}{\sqrt{1-(E_k/\lambda)^2}}.\]
Eq. 12first matrix element
\[\langle k|\langle\mathcal L|W|\mathcal L\rangle|k\rangle=\langle k|\langle\mathcal L|\mathrm{SELECT}|\mathcal L\rangle|k\rangle=\frac{E_k}{\lambda}.\]
Eq. 13transition matrix element
\[\langle k|\langle\mathcal L|W|\phi_k\rangle=\sqrt{1-(E_k/\lambda)^2}.\]
Eq. 14two-dimensional walk block
\[W\equiv\begin{pmatrix}E_k/\lambda & \sqrt{1-(E_k/\lambda)^2}\\-\sqrt{1-(E_k/\lambda)^2}&E_k/\lambda\end{pmatrix}=e^{i\arccos(E_k/\lambda)Y}.\]
Eq. 15recovering the Hamiltonian spectrum
\[\mathrm{spectrum}(H)=\lambda\cos\{\arg[\mathrm{spectrum}(W)]\}.\]
Eq. 16controlled inverse trick
\[R_{\mathcal L} W^n R_{\mathcal L}=R_{\mathcal L}^2(\mathrm{SELECT}\,R_{\mathcal L})^n=(\mathrm{SELECT}\,R_{\mathcal L})^n=(W^\dagger)^n.\]
Eq. 17optimal phase-estimation input state
\[\chi_m|0\rangle^{\otimes m}\mapsto \sqrt{\frac{2}{2^m+1}}\sum_{n=0}^{2^m-1}\sin\!\left(\frac{\pi(n+1)}{2^m+1}\right)|n\rangle.\]
Eq. 18Hadamard starting state
\[\sqrt{\frac{1}{2^{m+1}}}\sum_{n=0}^{2^m-1}|n\rangle\otimes(|0\rangle+|1\rangle).\]
Eq. 19state after controlled rotations
\[\sqrt{\frac{1}{2^{m+1}}}\sum_{n=0}^{2^m-1}\left(e^{i\pi(n+1)/(2^m+1)}|n\rangle|0\rangle+e^{-i\pi(n+1)/(2^m+1)}|n\rangle|1\rangle\right).\]
Eq. 20postselected sine state
\[i\sqrt{\frac{1}{2^m}}\sum_{n=0}^{2^m-1}\sin\!\left(\frac{\pi(n+1)}{2^m+1}\right)|n\rangle.\]
Eq. 21phase RMSE
\[\Delta\phi\equiv\sqrt{\mathbb E[\mathrm{dist}(\phi_{\rm est},\phi_{\rm true})^2]}.\]
Eq. 22phase-error budget
\[\Delta\phi\approx\sqrt{V_H(\phi)+(\epsilon_{\rm PREP}+\pi\epsilon_{\rm QFT})^2}\approx\sqrt{\left(\frac{\pi}{2^{m+1}}\right)^2+(\epsilon_{\rm PREP}+\pi\epsilon_{\rm QFT})^2}.\]
Eq. 23energy error from phase error
\[\Delta E=\lambda\Delta\cos(\phi)\le \lambda\Delta\phi\approx \lambda\sqrt{\left(\frac{\pi}{2^{m+1}}\right)^2+(\epsilon_{\rm PREP}+\pi\epsilon_{\rm QFT})^2}.\]
Eq. 24phase bits
\[m=\left\lceil\log\!\left(\frac{\sqrt 2\pi\lambda}{2\Delta E}\right)\right\rceil<\log\!\left(\frac{\sqrt 2\pi\lambda}{\Delta E}\right).\]
Eq. 25PREPARE/QFT target errors
\[\epsilon_{\rm PREP}\le \frac{\sqrt2\Delta E}{4\lambda},\qquad \epsilon_{\rm QFT}\le\frac{\sqrt2\Delta E}{4\pi\lambda}.\]
Eq. 26SELECT query bound
\[2^m<\frac{\sqrt2\pi\lambda}{\Delta E}.\]
Eq. 27overall oracle-gate upper bound
\[\frac{\sqrt2\pi\lambda(S+2P)}{\Delta E}.\]
Eq. 28coefficient-precision requirement
\[|\tilde w_l-w_l|\le \delta=\frac{\sqrt2\Delta E}{4L\left(1+\Delta E^2/(8\lambda^2)\right)}\left(1-\frac{\|H\|^2}{\lambda^2}\right).\]
Eq. 29indexed NOT
\[|c\rangle|l\rangle|\psi\rangle\mapsto |c\rangle|l\rangle (X_l)^c|\psi\rangle.\]
Eq. 30selective Majorana operator
\[|l\rangle|\psi\rangle\mapsto |l\rangle\left(\frac{a_l^\dagger-a_l}{i}\right)|\psi\rangle=|l\rangle Y_lZ_{l-1}\cdots Z_0|\psi\rangle.\]
Eq. 31QROM
\[\mathrm{QROM}_{\vec d}\sum_{l=0}^{L-1}\alpha_l|l\rangle|0\rangle=\sum_{l=0}^{L-1}\alpha_l|l\rangle|d_l\rangle.\]
Eq. 32PREPARE with junk register
\[|\mathcal L\rangle\equiv\sum_{l=0}^{L-1}\sqrt{\frac{w_l}{\lambda}}|l\rangle|\mathrm{temp}_l\rangle.\]
Eq. 33sufficient marginal condition
\[\langle\mathcal L|(|l\rangle\langle l|\otimes\mathbf1)|\mathcal L\rangle=\frac{w_l}{\lambda},\qquad \forall l\in[0,L).\]
Eq. 34approximate target state
\[|0\rangle^{\otimes(1+2\mu+2\log L)}\mapsto \sum_{l=0}^{L-1}\sqrt{\tilde\rho_l}\,|l\rangle|\mathrm{temp}_l\rangle.\]
Eq. 35probability discretization error
\[|\rho_l-\tilde\rho_l|=\frac{|w_l-\tilde w_l|}{\lambda}\le \frac{1}{2^\mu L}\le\frac{\delta}{\lambda}.\]
Eq. 36number of coefficient bits
\[\mu=\left\lceil\log\!\left(\frac{2\sqrt2\lambda}{\Delta E}\right)+\log\!\left(1+\frac{\Delta E^2}{8\lambda^2}\right)-\log\!\left(1-\frac{\|H\|^2}{\lambda^2}\right)\right\rceil.\]
Eq. 37after uniform index and QROM
\[\sum_{l=0}^{L-1}\sqrt{\frac{1}{L}}|l\rangle|\mathrm{alt}_l\rangle|\mathrm{keep}_l\rangle.\]
Eq. 38junk state after alias-style swap
\[|\mathrm{temp}_l\rangle=\frac{1}{\sqrt{2^\mu L\tilde\rho_l}}\left(|\mathrm{alt}_l\rangle|\mathrm{keep}_l\rangle\sum_{\sigma=0}^{\mathrm{keep}_l-1}|\sigma\rangle|0\rangle+\sum_{k: \mathrm{alt}_k=l}|k\rangle|\mathrm{keep}_k\rangle\sum_{\sigma=\mathrm{keep}_k}^{2^\mu-1}|\sigma\rangle|1\rangle\right).\]
Eq. 39alias-table normalization condition
\[\frac{\mathrm{keep}_l+\sum_{k:\mathrm{alt}_k=l}(2^\mu-\mathrm{keep}_k)}{2^\mu L}=\tilde\rho_l=\frac{\tilde w_l}{\lambda}.\]
Eq. 40recursive residual probability
\[\frac{\mathrm{keep}_l+\sum_{k\notin\mathcal L:\mathrm{alt}_k=l}(2^\mu-\mathrm{keep}_k)}{2^\mu L}=\tilde\rho_l-\frac{\sum_{k\in\mathcal L:\mathrm{alt}_k=l}(2^\mu-\mathrm{keep}_k)}{2^\mu L}=\tilde\rho'_l.\]
Eq. 41electronic-structure Hamiltonian
\[H=\sum_{p,q,\sigma}T(p-q)a_{p,\sigma}^\dagger a_{q,\sigma}+\sum_{p,\sigma}U(p)n_{p,\sigma}+\sum_{(p,\alpha)\ne(q,\beta)}V(p-q)n_{p,\alpha}n_{q,\beta}.\]
Eq. 42Jordan-Wigner form for electronic structure
\[\begin{aligned}H={}&\sum_{p\ne q,\sigma}\frac{T(p-q)}{2}\bigl(X_{p,\sigma}\vec Z X_{q,\sigma}+Y_{p,\sigma}\vec Z Y_{q,\sigma}\bigr)+\sum_{(p,\alpha)\ne(q,\beta)}\frac{V(p-q)}{4}Z_{p,\alpha}Z_{q,\beta}\\&-\sum_{p,\sigma}\frac{T(0)+U(p)+\sum_q V(p-q)}{2}Z_{p,\sigma}+\sum_p\left(T(0)+U(p)+\sum_q\frac{V(p-q)}{2}\right)\mathbf1.\end{aligned}\]
Eq. 43plane-wave-dual coefficients
\[T(p)=\sum_\nu \frac{k_\nu^2\cos(k_\nu\cdot r_p)}{2N},\quad U(p)=-\sum_{j,\nu\ne0}\frac{4\pi\zeta_j\cos(k_\nu\cdot R_j-k_\nu\cdot r_p)}{\Omega k_\nu^2},\quad V(p)=\sum_{\nu\ne0}\frac{2\pi\cos(k_\nu\cdot r_p)}{\Omega k_\nu^2}.\]
Eq. 44SELECTCHEM cases
\[\mathrm{SELECT}_{\rm CHEM}|\theta,U,V,p,\alpha,q,\beta\rangle|\psi\rangle=(-1)^\theta|\theta,U,V,p,\alpha,q,\beta\rangle\otimes\begin{cases}Z_{p,\alpha}|\psi\rangle,&U\wedge\neg V\wedge((p,\alpha)=(q,\beta)),\\Z_{p,\alpha}Z_{q,\beta}|\psi\rangle,&\neg U\wedge V\wedge((p,\alpha)\ne(q,\beta)),\\X_{p,\alpha}\vec Z X_{q,\alpha}|\psi\rangle,&\neg U\wedge\neg V\wedge(pq)\wedge(\alpha=\beta),\\\mathrm{undefined},&\mathrm{otherwise.}\end{cases}\]
Eq. 45spin-orbital to qubit mapping
\[M\equiv(N/2)^{1/D},\qquad f(p,\sigma)=\delta_{\sigma,\downarrow}M^D+\sum_{j=0}^{D-1}p_jM^j.\]
Eq. 46PREPARECHEM target
\[\begin{aligned}\mathrm{PREPARE}_{\rm CHEM}|0\rangle^{\otimes(3+2\log N)}\mapsto{}&\sum_{p,\sigma}\tilde U(p)|\theta_p\rangle|1\rangle_U|0\rangle_V|p,\sigma;p,\sigma\rangle\\&+\sum_{p\ne q,\sigma}\tilde T(p-q)|\theta^{(0)}_{p-q}\rangle|0\rangle_U|0\rangle_V|p,\sigma;q,\sigma\rangle\\&+\sum_{(p,\alpha)\ne(q,\beta)}\tilde V(p-q)|\theta^{(1)}_{p-q}\rangle|0\rangle_U|1\rangle_V|p,\alpha;q,\beta\rangle.\end{aligned}\]
Eq. 47PREPARECHEM amplitudes and signs
\[\tilde U(p)=\sqrt{\frac{|T(0)+U(p)+\sum_qV(p-q)|}{2\lambda}},\quad \tilde T(p)=\sqrt{\frac{|T(p)|}{\lambda}},\quad \tilde V(p)=\sqrt{\frac{|V(p)|}{4\lambda}},\quad \theta_p=\frac{1-\mathrm{sign}(-T(0)-U(p)-\sum_qV(p-q))}{2},\quad \theta_p^{(0)}=\frac{1-\mathrm{sign}(T(p))}{2},\quad \theta_p^{(1)}=\frac{1-\mathrm{sign}(V(p))}{2}.\]
Eq. 48SUBPREPARE
\[\mathrm{SUBPREPARE}|0\rangle^{\otimes(2+\log N)}\mapsto\sum_{d=0}^{N-1}\bigl(\tilde U(d)|\theta_d\rangle|1\rangle_U|0\rangle_V+\tilde T(d)|\theta^{(0)}_d\rangle|0\rangle_U|0\rangle_V+\tilde V(d)|\theta^{(1)}_d\rangle|0\rangle_U|1\rangle_V\bigr)|d\rangle.\]
Eq. 49state after q/alpha initialization
\[\begin{aligned}\mathrm{Eq.}(48)\mapsto{}&\sum_{d=0}^{N/2-1}\tilde U(d)|\theta_d\rangle|1\rangle_U|0\rangle_V|d\rangle|+\rangle_\alpha|0\rangle^{\otimes\log N}\\&+\sum_{d=0}^{N/2-1}\sum_{q=0}^{N/2-1}\left(\tilde T(d)|\theta_d^{(0)}\rangle|0\rangle_U|0\rangle_V+\tilde V(d)|\theta_d^{(1)}\rangle|0\rangle_U|1\rangle_V\right)|d\rangle|+\rangle_\alpha|q\rangle|0\rangle.\end{aligned}\]
Eq. 50state after beta logic
\[\begin{aligned}\mathrm{Eq.}(49)\mapsto{}&\sum_{d=0}^{N/2-1}\sum_\sigma\left(\tilde U(d)|\theta_d\rangle|1\rangle_U|0\rangle_V|d,\sigma;0,\sigma\rangle+\sum_{q=0}^{N/2-1}\tilde T(d)|\theta_d^{(0)}\rangle|0\rangle_U|0\rangle_V|d,\sigma;q,\sigma\rangle\right)\\&+\sum_\alpha\left(\tilde V(0)|\theta_0^{(1)}\rangle|0\rangle_U|1\rangle_V|0,\alpha;q,\neg\alpha\rangle+\sum_\beta\sum_{d=1}^{N/2-1}\sum_{q=0}^{N/2-1}\tilde V(d)|\theta_d^{(1)}\rangle|0\rangle_U|1\rangle_V|d,\alpha;q,\beta\rangle\right).\end{aligned}\]
Eq. 51state after converting d to p
\[\begin{aligned}\mathrm{Eq.}(50)\mapsto{}&\sum_{d=0}^{N/2-1}\sum_\sigma\left(\tilde U(d)|\theta_d\rangle|1\rangle_U|0\rangle_V|d,\sigma;d,\sigma\rangle+\sum_{q=0}^{N/2-1}\tilde T(d)|\theta_d^{(0)}\rangle|0\rangle_U|0\rangle_V|d+q,\sigma;q,\sigma\rangle\right)\\&+\sum_\alpha\left(\tilde V(0)|\theta_0^{(1)}\rangle|0\rangle_U|1\rangle_V|q,\alpha;q,\neg\alpha\rangle+\sum_\beta\sum_{d=1}^{N/2-1}\sum_{q=0}^{N/2-1}\tilde V(d)|\theta_d^{(1)}\rangle|0\rangle_U|1\rangle_V|d+q,\alpha;q,\beta\rangle\right).\end{aligned}\]
Eq. 52lambda for electronic structure
\[\lambda=\sum_{p,q}|T(p-q)|+\sum_p|U(p)|+\sum_{p\ne q}|V(p-q)|.\]
Eq. 53dual-basis lambda bound
\[\lambda\in O\!\left(\frac{N^{7/3}}{\Omega^{1/3}}+\frac{N^{5/3}}{\Omega^{2/3}}\right)\in O(N^2)\quad(N\propto\Omega).\]
Eq. 54electronic-structure total T estimate
\[\frac{\sqrt2\pi\lambda(S+2P)}{\Delta E}\approx \frac{24\sqrt2\pi\lambda N}{\Delta E}.\]
Eq. 55electronic-structure ancilla estimate
\[\log\!\left(\frac{\sqrt2\pi\lambda}{2\Delta E}\right)+2\log\!\left(\frac{2\sqrt2\lambda}{\Delta E}\right)+5\log N+O(1)=\log\!\left(\frac{4\sqrt2\pi\lambda^3N^5}{\Delta E^3}\right)+O(1).\]
Eq. 56Hubbard Hamiltonian
\[H=-t\sum_{\langle p,q\rangle,\sigma}a^\dagger_{p,\sigma}a_{q,\sigma}+\frac{u}{2}\sum_{p,\alpha\ne\beta}n_{p,\alpha}n_{p,\beta}.\]
Eq. 57Jordan-Wigner Hubbard Hamiltonian
\[H=-\frac{t}{2}\sum_{\langle p,q\rangle,\sigma}\left(X_{p,\sigma}\vec Z X_{q,\sigma}+Y_{p,\sigma}\vec ZY_{q,\sigma}\right)+\frac{u}{8}\sum_{p,\alpha\ne\beta}Z_{p,\alpha}Z_{p,\beta}-\frac{u}{4}\sum_{p,\sigma}Z_{p,\sigma}+\frac{uN}{4}\mathbf1.\]
Eq. 58SELECTHUB cases
\[\mathrm{SELECT}_{\rm HUB}|U,V,p,\alpha,q,\beta\rangle|\psi\rangle=|U,V,p,\alpha,q,\beta\rangle\otimes\begin{cases}-Z_{p,\alpha}|\psi\rangle,&U\wedge\neg V\wedge((p,\alpha)=(q,\beta)),\\Z_{p,\alpha}Z_{q,\beta}|\psi\rangle,&\neg U\wedge V\wedge(p=q)\wedge(\alpha=0)\wedge(\beta=1),\\-X_{p,\alpha}\vec ZX_{q,\alpha}|\psi\rangle,&\neg U\wedge\neg V\wedge(pq)\wedge(\alpha=\beta),\\\mathrm{undefined},&\mathrm{otherwise.}\end{cases}\]
Eq. 59PREPAREHUB target state
\[\begin{aligned}\mathrm{PREPARE}_{\rm HUB}|0\rangle^{\otimes(2+2\log N)}\mapsto \sum_{p_x,p_y}\bigg[&\sqrt{\frac{u}{8\lambda}}|0\rangle_U|1\rangle_V|p_x,p_y,0;p_x,p_y,1\rangle\\&+\sqrt{\frac{u}{4\lambda}}\sum_{\sigma}|1\rangle_U|0\rangle_V|p_x,p_y,\sigma;p_x,p_y,\sigma\rangle\\&+\sqrt{\frac{t}{2\lambda}}\sum_{\sigma}\bigl(|0\rangle_U|0\rangle_V|p_x,p_y,\sigma;p_x+1,p_y,\sigma\rangle+|0\rangle_U|0\rangle_V|p_x,p_y,\sigma;p_x,p_y+1,\sigma\rangle\\&\qquad+|0\rangle_U|0\rangle_V|p_x,p_y,\sigma;p_x-1,p_y,\sigma\rangle+|0\rangle_U|0\rangle_V|p_x,p_y,\sigma;p_x,p_y-1,\sigma\rangle\bigr)\bigg].\end{aligned}\]
Eq. 60lambda for Hubbard
\[\lambda=2Nt+\frac{Nu}{2}\in O(N).\]
Eq. 61Hubbard total T estimate
\[\frac{\sqrt2\pi\lambda(S+2P)}{\Delta E}=\frac{\sqrt2\pi(2t+u/2)N(S+2P)}{\Delta E}\approx\frac{20\sqrt2\pi t+5\sqrt2\pi u}{\Delta E}N^2.\]
Eq. 62Hubbard ancilla estimate
\[\log\!\left(\frac{\sqrt2\pi\lambda}{2\Delta E}\right)+3\log N+O(1)=\log\!\left(\frac{\sqrt2\pi\lambda N^3}{2\Delta E}\right)+O(1).\]
Eq. 63Hubbard benchmark T estimate at u/t=4
\[\frac{40\sqrt2\pi t}{t/100}N^2<1.8\times10^4N^2.\]
Eq. 64Hubbard benchmark ancilla estimate at u/t=4
\[\log\!\left(\frac{8\sqrt2\pi tN^3}{t/100}\right)<12+3\log N.\]
Eq. 65patching lemma bound
\[\left\|e^{-iH_{ABC}t}-e^{-iH_{AB}t}e^{iH_Bt}e^{-iH_{BC}t}\right\|\in O\!\left(\sum_{X\subseteq(A\cup B\cup C)\setminus(A\cup B)\setminus C}\|h_X\|e^{vt-\mu\,\mathrm{dist}(A,C)}\right).\]
Eq. 66patching example
\[e^{-iH_{ABCD}t}\approx e^{-iH_{AB}t}e^{iH_Bt}e^{-iH_{BCD}t}\approx e^{-iH_{AB}t}e^{iH_Bt}e^{-iH_{BC}t}e^{iH_Ct}e^{-iH_{CD}t}.\]
Eq. 67magic T state
\[|T\rangle\equiv T|+\rangle=\frac{|0\rangle+e^{i\pi/4}|1\rangle}{\sqrt2}.\]
Eq. A1approximate Hamiltonian
\[\tilde H\equiv\sum_{l=0}^{L-1}\tilde w_lH_l.\]
Eq. A2lambda preserved
\[\lambda=\sum_{l=0}^{L-1}\tilde w_l.\]
Eq. A3coefficient error cap
\[\delta\ge |\tilde w_l-w_l|.\]
Eq. A4phase error expansion
\[\epsilon_{\rm PREP}\le\|e^{i\arccos(H/\lambda)}-e^{i\arccos(\tilde H/\lambda)}\|\le\sum_{p=0}^{\infty}\frac{(2p-1)!!}{\lambda^{2p+1}(2p+1)(2p)!!}\|H^{2p+1}-\tilde H^{2p+1}\|.\]
Eq. A5power-difference bound
\[\|H^{2p+1}-\tilde H^{2p+1}\|\le(2p+1)(\max\{\|H\|,\|\tilde H\|\})^{2p}\|H-\tilde H\|.\]
Eq. A6operator-norm coefficient bound
\[\|H-\tilde H\|\le\sum_{l=0}^{L-1}|w_l-\tilde w_l|\le L\delta.\]
Eq. A7norm max bound
\[\max\{\|H\|,\|\tilde H\|\}\le\|H\|+L\delta.\]
Eq. A8summed PREPARE error bound
\[\epsilon_{\rm PREP}\le\frac{L\delta}{\lambda}\left[1-\left(\frac{\|H\|+L\delta}{\lambda}\right)^2\right]^{-1/2}.\]
Eq. A9solving for delta
\[\delta\ge\frac{\epsilon_{\rm PREP}}{(1+\epsilon_{\rm PREP}^2)L}\left(\sqrt{\lambda^2(1+\epsilon_{\rm PREP}^2)-\|H\|^2}-\epsilon_{\rm PREP}\|H\|\right)\ge\frac{\epsilon_{\rm PREP}\lambda}{(1+\epsilon_{\rm PREP}^2)L}\left(1-\frac{\|H\|^2}{\lambda^2}\right).\]
Eq. A10final coefficient precision
\[\delta=\frac{\sqrt2\Delta E}{4L(1+\Delta E^2/(8\lambda^2))}\left(1-\frac{\|H\|^2}{\lambda^2}\right).\]
14. 対話型ツール
14.1 \(E/\lambda\) と walk phase の対応
スライダーで \(x=E/\lambda\) を動かすと、\(\phi=\arccos(x)\) と unit circle 上の \(e^{\pm i\phi}\) が変化する。
読み方
位相推定が返すのは直接 \(E\) ではなく \(\phi\)。walk operator の固有値は \(e^{\pm i\phi}\)、対応は \(E=\lambda\cos\phi\)。\(|E|\) が \(\lambda\) に近いと \(\arccos\) の傾きが大きくなり、係数誤差の扱いが繊細になる。付録の \(\delta\) bound はこの点を制御する。
14.2 資源計算機
式: \(T\approx24\sqrt2\pi\lambda N/\Delta E\), \(A\approx\log_2(4\sqrt2\pi\lambda^3N^5/\Delta E^3)\)。
式: \(\lambda=2Nt+Nu/2\), \(T\approx\sqrt2\pi\lambda(10N)/\Delta E\), \(A\approx\log_2(\sqrt2\pi\lambda N^3/(2\Delta E))\)。
14.3 Alias PREPARE のミニ実験
ランダムな離散確率 \(\rho_l\) に対して、alias table の \(\mathrm{keep}_l\) と \(\mathrm{alt}_l\) を作る。
14.4 Jellium table の \(\lambda\) プロット
15. 付録: 係数誤差が位相誤差へ伝わる bound の意味
付録の目的は、PREPARE oracle で準備する係数 \(w_l\) を近似値 \(\tilde w_l\) にしたとき、walk phase の誤差をどう抑えるかを定量化すること。単純な Hamiltonian norm 誤差だけでなく、\(\arccos\) の非線形性、特に \(|H|/\lambda\) が 1 に近いときの特異的挙動を考慮する。
近似 Hamiltonian を \(\tilde H=\sum_l\tilde w_lH_l\) とし、\(\sum_l\tilde w_l=\lambda\) を保つ。各係数誤差が \(\delta\) 以下なら、
\[\|H-\tilde H\|\le L\delta,\qquad \max\{\|H\|,\|\tilde H\|\}\le\|H\|+L\delta.
\]
\(\arccos\) の級数展開と power-difference bound を使うと、
\[\epsilon_{\rm PREP}\le\frac{L\delta}{\lambda}\left[1-\left(\frac{\|H\|+L\delta}{\lambda}\right)^2\right]^{-1/2}.
\]
これを \(\delta\) について解き、本文の誤差割当 \(\epsilon_{\rm PREP}\le\sqrt2\Delta E/(4\lambda)\) を入れると、本文 Eq. (28) と同じ
\[\delta=\frac{\sqrt2\Delta E}{4L(1+\Delta E^2/(8\lambda^2))}\left(1-\frac{\|H\|^2}{\lambda^2}\right)
\]
が得られる。\((1-\|H\|^2/\lambda^2)\) の因子は、walk phase が \(0\) または \(\pi\) に近づくと係数精度要求が厳しくなることを反映している。
結論と今後の方向
論文は、T count の桁を大きく下げるためには、抽象アルゴリズムだけでなく、係数読み出し、Pauli string 選択、反射、surface-code braid まで統合して設計する必要があることを示した。今後の方向として、Gausslet basis で単一分子へ拡張すること、first quantization と組み合わせて basis error を抑えること、lattice surgery などで physical qubit 数をさらに下げることが挙げられる。
出典: Babbush et al., “Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity,” Phys. Rev. X 8, 041015 (2018), DOI 10.1103/PhysRevX.8.041015. 原論文は Creative Commons Attribution 4.0 International license として公開。