情報処理学会第 85 回全国大会

1B-02

NISQ 計算の分割統治による検証
竹内勇貴†

高橋康博‡

NTT コミュニケーション科学基礎研究所†

森前智行§

谷誠一郎†

群馬大学情報学部‡

京都大学基礎物理学研究所§



1. はじめに
量子計算機は、古典計算機にとって解くのが困     
難な問題のいくつかを効率良く解けると期待されている。しかし、量子計算機の能力を最大限      
引き出すためには、量子エラー訂正が不可欠である。量子エラー訂正は正確な状態準備、量子      
操作、測定を必要とするため、現在の技術で実
現するのは困難である。そこで、近年、量子エ    
ラー訂正の機能が無い量子計算機の能力が精力的に研究されている。そのような量子計算機は、
図1.
IBMの53
量子ビットチップNISQ(noisy intermediate-scale quantum、ノイズ耐性が無い小・中規模の量子)[1]計算機と呼れらは全てエラー耐性が有る万能量子計算を想ばれており、様々な専用の量子アルゴリズム定したものであった。𝑛量子ビット入力の NISQ 計[2,3]が提案され、実験的評価[4]も行われてい算を、𝑛より少ない量子ビットに対する測定だける。
で効率良く検証出来るかは極めて非自明な問題である。
これまで様々なエラー抑制手法[5,6]が提案されているが、NISQ 計算にはエラー訂正機能が無いため、問題サイズ𝑛に対して𝑂(log 𝑛)時間で計算が完了するべきである。さらに、現在実現しているいくつかの量子チップは疎である、つまり、2 量子ビット間の接続を少数取り除くだけでチップを二分割することが出来る。例えば、IBM の 53量子ビットチップ[7](図 1)は、2 つの接続を取り除くだけで二分割出来る。まとめると、様々なNISQ 計算は、疎な量子チップ上の浅層量子回路だと考えることが出来る。本発表では、そのような NISQ 計算のみに着目することとする。
NISQ 計算の性能はノイズの影響を強く受けるため、与えられた NISQ 計算機が想定通りに動作しているかを効率良くチェックするのは必要不可欠である。このタスクは、量子計算の検証と呼ばれている。これまで効率的な検証手法(e.g.,[8,9,10,11,12])が複数提案されてきたが、こ

2. 本発表で提案する検証手法|𝜓! ⟩を任意のターゲット状態、つまり、疎な量子チップ上の理想的な浅層量子回路から生成された𝑛量子ビットの純粋状態だとする。本発表では、|𝜓! ⟩と実際の NISQ 計算機から生成された量子状態𝜌"#$ 間の忠実度を推定するための効率的な手法を提案する[13]。忠実度は量子状態間の近さを表す量であるため、我々の手法は NISQ 計算の検証手法として用いることが出来る。我々の手法は、𝑛⁄2 + 1 ≤ 𝑚 + 1 < 𝑛に対して、(𝑚 + 1)量子ビット測定しか必要としない。また、忠実度を推定しているため、我々の検証手法は、決定問題以外の問題に対しても適用することが出来る。

我々の手法の構成は以下の通りである：まず初めに、理想的な(𝑚 + 1)量子ビット測定器が行う量子操作と実際の操作の間のダイヤモンドノル
Divide-and-conquer verification method for noisy intermediate- ムの上限を求める。我々の手法は、(𝑚 + 1)量子scale quantum computation
ビット測定器がノイジー、つまり、上限が 0 でYuki Takeuchi† Yasuhiro Takahashi‡は無いが十分小さい時でも適用することが出来
Tomoyuki Morimae§ Seiichiro Tani†
る。次に、𝜌"#$ の𝑚量子ビットと一つの補助量子
NTT Communication Science Laboratories, NTT Corporation†
ビット|0⟩をノイジーな(𝑚 + 1)量子ビット測定器‡Faculty of Informatics, Gunma University§で測定する。𝜌"#$ の残りの(𝑛 − 𝑚)量子ビットに
Yukawa Institute for Theoretical Physics, Kyoto University

1-183

Copyright 2023 Information Processing Society of Japan.
All Rights Reserved.

情報処理学会第 85 回全国大会

関しても、一つの補助量子ビット|0⟩と一緒にノイジーな(𝑚 + 1)量子ビット測定器で測定する
𝜌"#$ のコピーを多項式個生成することで、これらの手続きを繰り返す。最後に、全ての測定結果を古典事後処理することで、|𝜓! ⟩と𝜌"#$ 間の忠実度を推定する。𝜌"#$ を二分割し、それぞれを個別に測定しているため、我々の手法は分割統治法の一種だと考えることが出来る。
3. 既存手法との比較
我々が知る限り、本提案以前には、NISQ 計算用の効率的な検証手法は二種類しか提案されていなかった[14,15,16,17]。[14,16]で提案されている手法が実際の出力確率分布と理想的な分布の全変動距離を推定しているのに対して、我々の手法は忠実度を推定している。この意味で、
我々の手法は既存手法[14, 16]より優れていると言える。ただし、彼らの手法はターゲット量子回路がエラーの影響を受ける確率の下限、上限を推定するためにも使用することが出来る。さらに、上限を用いることで、忠実度の下限を得ることが出来る。しかし、この方法で得た忠実度の下限はタイトではない可能性がある。
[15,17]で提案された手法は検証可能性と同時に安全性も達成している。つまり、彼女らの手法を用いることで、サーバの量子計算機がノイジーな場合でも、遠隔地のサーバに量子計算を安全かつ検証可能な形で委託することが出来る。
このエラー耐性は前途有望である。しかし、彼
女らの手法は測定型量子計算を利用しており、測定型量子計算は大量の量子ビットを必要とするため、NISQ 計算機には不向きである。一方で、我々の手法は測定型量子計算ではなく、量子回路モデルを利用している。
我々の手法は、サンプル複雑性、つまり、必要なコピー数の観点でも、既存手法に対して優位性がある。|𝜓! ⟩の密度を𝐷と書くことにする。この時、我々の手法のサンプル複雑性は𝑂(𝐷% 2&'( )となり、これは NISQ 計算の場合、𝑛の多項式となる。何故ならば、NISQ 計算の場合、密度は𝐷 =𝑂(log 𝑛)となるからである。一方で、既存の忠実度推定手法として、𝜌"#$ の行列表現を再構成することで忠実度を推定する量子状態トモグラフィ[18]がある。任意の𝑛量子ビット状態は𝑂(4) )個の複素数によって一意に特定出来るために、量子状態トモグラフィは少なくとも同数の𝜌"#$ のコピーを必要とする。効率性を改善するため、
Flammia と Liu は、行列表現を再構成することなく忠実度を推定する直接忠実度推定[19]を提案した。彼らの手法は、平均Ω(2) )個の𝜌"#$ のコピーを必要とする。サンプル複雑性の観点で、彼らの手法は量子状態トモグラフィより優れているが、必要なコピー数は依然、𝑛の指数のままである。その一方、上記でも述べた通り、我々の手法は最悪の場合でも多項式個のコピーしか必要としない。
参考文献[1] J. Preskill, Quantum 2, 79 (2018).
[2] A. Peruzzo, J. McClean, P. Shadbolt, M.H. Yung, X.-Q. Zhou, P. J. Love, A. AspuruGuzik, and J. L. O’Brien, Nat. Commun. 5,4213 (2014).
[3] E. Farhi, J. Goldstone, and S. Gutmann,arXiv:1411.4028.
[4] A. Kandala, A. Mezzacapo, K. Temme, M.
Takita, M. Brink, J. M. Chow, and J. M.
Gambetta, Nature (London) 549, 242 (2017).
[5] Y. Li and S. C. Benjamin, Phys. Rev. X 7,021050 (2017).
[6] S. Endo, S. C. Benjamin, and Y. Li, Phys.
Rev. X 8, 031027 (2018).
[7] A. Kondratyev, SSRN 3569226 (2020).
[8] M. Hayashi and T. Morimae, Phys. Rev.
Lett. 115, 220502 (2015).
[9] J. F. Fitzsimons and E. Kashefi, Phys.
Rev. A 96, 012303 (2017).
[10] J. F. Fitzsimons, M. Hajdus:ek, and T.
Morimae, Phys. Rev. Lett. 120, 040501 (2018).
[11] Y. Takeuchi and T. Morimae, Phys. Rev.
X 8, 021060 (2018).
[12] U. Mahadev, in Proc. of the 59th Annual

Symposium on Foundations of Computer Science(IEEE, Paris, 2018), p. 259.
[13] Y. Takeuchi, Y. Takahashi, T. Morimae,and S. Tani, Quantum 6, 758 (2022).
[14] S. Ferracin, T. Kapourniotis, and A.
Datta, New J. Phys. 21, 113038 (2019).
[15] E. Kashefi, D. Leichtle, L. Music, and
H. Ollivier, arXiv:2011.10005.
[16] S. Ferracin, S. T. Merkel, D. McKay, and
A. Datta, arXiv:2103.06603.
[17] D. Leichtle, L. Music, E. Kashefi, and
H. Ollivier, arXiv:2109.04042.
[18] D. T. Smithey, M. Beck, M. G. Raymer,
and A. Faridani, Phys. Rev. Lett. 70, 1244
(1993).
[19] S. T. Flammia and Y.-K. Liu, Phys. Rev.
Lett. 106, 230501 (2011).

1-184

Copyright 2023 Information Processing Society of Japan.
All Rights Reserved.