Asymptotically Efficient Quantum Karatsuba Multiplication

[gyu-don]

一言でいうと

量子コンピュータ上でのKaratsuba乗算を漸近的に古典と同じオーダーのゲート複雑性、空間複雑性で行う方法を示した。

Karatsuba乗算は、古典ではよく知られた乗算アルゴリズムで、教科書的な乗算では整数のビット長 $n$ の乗算に $O(n^3)$ の演算コストがかかるのに対し、Karatsuba乗算では再帰的な手法により $O(n^{log 3})$ で計算が行える。Karatsuba乗算を可逆計算として実装する際、従来手法では、計算途中で使ったancillaを、都度uncomputeするか、全て保存し最後にuncomputeをしていた。前者ではゲート複雑性のオーダーが大きくなり、また、後者では空間複雑性のオーダーが大きくなる。提案手法では、インライン加算 (+=) を利用することで、ゲート複雑性と空間複雑性のオーダーが古典と同等になる。これは、古典での末尾再帰最適化と類似している。しかし、この手法が教科書的な乗算と比べて効率的になるのは約10,000ビットを超えたときであり、現代のRSA暗号をShorのアルゴリズムで解く際の乗算では、今回示した実装よりも、教科書的な乗算を行った方が効率がいい。ただし、この論文では、漸近的な挙動のみを議論しており、定数倍の効率化は試みていない。

論文リンク

https://arxiv.org/abs/1904.07356

著者/所属機関

Craig Gidney
Google Inc., Santa Barbara, California 93117, USA

投稿日付(yyyy/MM/dd)

2019/04/15