JP4847914B2

JP4847914B2 - 量子加算演算方法及び量子加算演算装置

Info

Publication number: JP4847914B2
Application number: JP2007107238A
Authority: JP
Inventors: 康博高橋; 豪加藤; 泰人河野
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: Nippon Telegraph and Telephone Corp
Priority date: 2007-04-16
Filing date: 2007-04-16
Publication date: 2011-12-28
Anticipated expiration: 2027-04-16
Also published as: JP2008269012A

Description

本発明は、量子コンピュータにおいて加算演算を行う技術に関し、特に、効率的な加算演算を行うための技術に関する。

Ｏ（ｎ）個の基本演算とＯ（ｌｏｇ_２ｎ）個の計算ステップとＯ（ｎ）個の補助ビットとを用い、加算演算を行う量子回路が知られている（例えば、非特許文献１参照）。なおＯ（α）は十分大きなαに対してαの定数倍以下となる値を意味する（Ｏ記法）。また、「量子回路」とは、量子ビットに対する操作内容の時系列表現を意味する。

非特許文献１の量子回路は、２つの２進数ａ＝ａ_ｎ−１…ａ_０〔ａ_ｐ∈｛０，１｝，ｐ∈｛０，…，ｎ−１｝〕及びｂ＝ｂ_ｎ−１…ｂ_０〔ｂ_ｐ∈｛０，１｝〕が入力として与えられたとき、ａ＋ｂ＝ｓ_ｎ…ｓ_０〔ｓ_ｑ∈｛０，１｝，ｑ∈｛０，…，ｎ｝〕を算出し、ｓ_ｎ…ｓ_０とａとを出力する量子回路である。すなわち、初期量子状態がそれぞれ｜ａ_０＞，…，｜ａ_ｎ−１＞であるｎ個の量子ビットＱｘ_０，…，Ｑｘ_ｎ−１と、初期量子状態がそれぞれ｜ｂ_０＞，…，｜ｂ_ｎ−１＞であるｎ個の量子ビットＱｙ_０，…，Ｑｙ_ｎ−１と、初期量子状態がそれぞれ｜０＞であるＯ（ｎ）個の補助量子ビットとに対し、NOT演算，CNOT演算及びToffoli演算を基本演算とした量子操作を施し、量子状態がそれぞれ｜ａ_０＞，…，｜ａ_ｎ−１＞であるｎ個の量子ビットＱｘ_０，…，Ｑｘ_ｎ−１と、量子状態がそれぞれ｜ｓ_０＞，…，｜ｓ_ｎ−１＞であるｎ個の量子ビットＱｙ_０，…，Ｑｙ_ｎ−１と、量子状態が｜ｓ_ｎ＞である１個の補助量子ビットと、量子状態が｜０＞である複数の補助量子ビットとを出力する。なお、補助量子ビットとは、補助ビットとして利用する量子ビットを意味する。

図１７，１８は、非特許文献１に記載された加算演算用の量子回路の例示である。なお、図１７は演算の前段の量子操作を示す量子回路であり、図１８は図１７の量子操作の後に行われる後段の量子操作を示す量子回路である。また、図１７，１８は、８ビット同士（ｎ＝８）の加算演算を行う場合の例である。さらに、図１７，１８中のｃ_ｉ（１≦ｉ≦ｎ）は、

である。また、

が成り立つことが知られている。

図１７に示すように、非特許文献１の量子回路の前段では、初期量子状態がそれぞれ｜ａ_０＞，…，｜ａ_ｎ−１＞であるｎ個の量子ビットＱｘ_０，…，Ｑｘ_ｎ−１と、初期量子状態がそれぞれ｜ｂ_０＞，…，｜ｂ_ｎ−１＞であるｎ個の量子ビットＱｙ_０，…，Ｑｙ_ｎ−１とに対し、CNOT演算によって１ビット毎の加算処理を行い、補助量子ビットを用いたToffoli演算及びCNOT演算によって１ビット毎の繰上げ処理を行っている。また、図１８に示すように、非特許文献１の量子回路の後段では、前段で行った演算の一部の逆演算とNOT演算とによって、補助量子ビットの量子状態を｜０＞に戻す処理を行っている。なお、図１７，１８の量子回路は、容易にｎビット同士の加算用の量子回路に拡張できる。
T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore, A logarithmic-depth quantum carry-lookahead adder, Quantum Infomation and Computation, Vol. 6 No. 4&5, pp. 351-369, 2006

非特許文献１の量子回路では、Ｏ（ｎ）個の基本演算による操作をＯ（ｌｏｇ_２ｎ）個の計算ステップで実行し、その際Ｏ（ｎ）個の補助量子ビットを利用している。しかし、演算に必要となる量子ビットの数が多くなればなるほど、それらを実現し、協調的に操作することが物理的に困難となる。よって、出来るだけ少ない数の補助量子ビットによって量子回路を構成することが望ましい。
本発明はこのような点に鑑みてなされたものであり、従来よりも少ない数の補助量子ビットで量子加算演算が可能な技術を提供することを目的とする。

本発明では上記課題を解決するために、複数の量子ビット単位（加算処理ブロック単位）で加算処理及び繰上げ処理を行う。

すなわち、本発明では、２つの２進数ａ＝ａ_ｎ−１…ａ_０〔ａ_ｐ∈｛０，１｝，ｐ∈｛０，…，ｎ−１｝，ｎ≧４〕及びｂ＝ｂ_ｎ−１…ｂ_０〔ｂ_ｐ∈｛０，１｝〕に対し、ａ＋ｂ＝ｓ_ｎ…ｓ_０〔ｓ_ｑ∈｛０，１｝，ｑ∈｛０，…，ｎ｝〕を算出するために、初期量子状態がそれぞれ｜ａ_０＞，…，｜ａ_ｎ−１＞であるｎ個の量子ビットＱｘ_０，…，Ｑｘ_ｎ−１と、初期量子状態がそれぞれ｜ｂ_０＞，…，｜ｂ_ｎ−１＞であるｎ個の量子ビットＱｙ_０，…，Ｑｙ_ｎ−１と、初期量子状態が｜０＞である１個の補助量子ビットＱｚ_０，１と、初期量子状態がそれぞれ｜０＞である２・｛（ｎ／ｋ）−１｝〔ｋはｎを割り切る２以上ｎ未満の整数の定数である〕個の補助量子ビットＱｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−１，１}，Ｑｚ_{（ｎ／ｋ）−１，２}と、初期量子状態がそれぞれ｜０＞である

個の補助量子ビットＱｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}と、が少なくとも存在し、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋと量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋとをｉ番目〔０≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕の加算処理ブロックＡ_ｉとし、当該加算処理ブロックＡ_ｉに属する初期量子状態の量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋ及び量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと、初期量子状態の補助量子ビットＱｚ_ｉ，１とに対してHIGHBIT演算を施し、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋの量子状態をそれぞれ｜ａ_{（ｉ＋１）・ｋ−１}＞，…，｜ａ_ｉ・ｋ＞とし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋの量子状態をそれぞれ｜ｂ_{（ｉ＋１）・ｋ−１}＞，…，｜ｂ_ｉ・ｋ＞とし、補助量子ビットＱｚ_ｉ，１の量子状態を｜ｃ_ｉ＞〔ｃ_ｉは、２つの２進数ａ_{（ｉ＋１）・ｋ−１}…ａ_ｉ・ｋとｂ_{（ｉ＋１）・ｋ−１}…ｂ_ｉ・ｋの和を２進表記した場合の最上位ビット値〕とする処理を、各加算処理ブロックＡ_ｉについてそれぞれ実行するHIGHBIT演算過程と、補助量子ビットＱｚ_０，１，Ｑｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−１，１}，Ｑｚ_{（ｎ／ｋ）−１，２}，Ｑｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}を用い、補助量子ビットＱｚ_ｗ，１の量子状態を｜ｄ_ｗ＞〔ｄ_ｗ∈｛０，１｝は、加算処理ブロックＡ_ｗから加算処理ブロックＡ_ｗ＋１への繰上げ値〕とする処理を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに補助量子ビットＱｚ_{（ｎ／ｋ）−１，１}の量子状態を｜ｓ_ｎ＞とする処理を実行する繰上げ値演算過程と、加算処理ブロックＡ_０に属する量子ビットＱｘ_ｋ−１，…，Ｑｘ_０と量子ビットＱｙ_ｋ−１，…，Ｑｙ_０とに対してSUM演算を施し、量子ビットＱｘ_ｋ−１，…，Ｑｘ_０の量子状態をそれぞれ｜ａ_ｋ−１＞，…，｜ａ_０＞とし、量子ビットＱｙ_ｋ−１，…，Ｑｙ_０の量子状態をそれぞれ｜ｓ_ｋ−１＞，…，｜ｓ_０＞とする第１のSUM演算過程と、加算処理ブロックＡ_ｉに属する量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋ及び量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと、補助量子ビットＱｚ_{ｉ−１，１}とに対して繰上げSUM演算を施し、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋの量子状態をそれぞれ｜ａ_{（ｉ＋１）・ｋ−１}＞，…，｜ａ_ｉ・ｋ＞とし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋの量子状態をそれぞれ｜ｓ_{（ｉ＋１）・ｋ−１}＞，…，｜ｓ_ｉ・ｋ＞とし、補助量子ビットＱｚ_{ｉ−１，１}の量子状態を維持する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のSUM演算過程と、を実行する。

このように、本発明では、加算処理ブロック単位で繰上げ値を求め（HIGHBIT演算過程）、補助量子ビットを用いて当該加算処理ブロック単位の繰上げ処理及び加算値の最上位ビット値の算出を行い（繰上げ値演算過程）、加算処理ブロック単位で加算処理を行う。これにより、量子ビット単位で加算処理を行い、補助量子ビットを用いて量子ビット単位で繰上げ処理を行う場合に比べ、処理に必要な補助量子ビット数を削減できる。なお、本発明において「量子ビット（又は補助量子ビット）の量子状態を｜α＞とする」とは、量子ビット（又は補助量子ビット）の量子状態を、｜α＞と他の量子状態との重ね合わせ状態とすることをも含む概念である。

また、本発明における上記繰上げ値演算過程は、例えば、量子ビットＱｘ_{ｉ・ｋ+ｊ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ+ｊ}を目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のCNOT演算過程と、上記第１のCNOT演算過程による処理がなされたｋ個の量子ビットＱｙ_ｉ・ｋ，…，Ｑｙ_{ｉ・ｋ＋ｋ−１}を制御ビットとし、補助量子ビットＱｚ_ｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のk-Toffoli演算過程と、第１のk-Toffoli演算過程によるk-Toffoli演算が施された補助量子ビットＱｚ_ｉ，２を補助量子ビットＱｐ_Ｌ−１（ｉ）と表現した場合における、補助量子ビットＱｐ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}うちの１つの補助量子ビットである補助量子ビットＱｐ_ｔ（ｉ）を目標ビットとしたToffoli演算を、目標ビットを重複させることなく、ｉ＝１からｉを１ずつ増加させながら

まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら

まで実行する第１のToffoli演算過程と、

HIGHBIT演算過程による処理が施された補助量子ビットＱｚ_ｉ，１を補助量子ビットＱｇ_Ｌ−１（ｉ）と表現した場合における、補助量子ビットＱｇ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｇ_ｔ−１（２ｉ＋１）を目標ビットとしたToffoli演算〔当該Toffoli演算後の補助量子ビットＱｇ_ｔ−１（２ｉ＋１）を補助量子ビットＱｇ_ｔ（ｉ）と表現〕を、ｉ＝０からｉを１ずつ増加させながら

まで実行する第２のToffoli演算過程と、ｕ＝２^ｔ・ｉ／ｋ−１とした場合における補助量子ビットＱｚ_ｕ，１，Ｑｐ_ｔ−１（２ｉ）を制御ビットとし、補助量子ビットＱｇ_ｔ−１（２ｉ）を目標ビットとしたToffoli演算を、ｉ＝１からｉを１ずつ増加させながら

まで実行する処理を、

からｔを１ずつ減少させながらｔ＝Ｌまで実行する第３のToffoli演算過程と、補助量子ビットＱｐ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｐ_ｔ（ｉ）を目標ビットとしたToffoli演算を、

からｉを１ずつ減少させながらｉ＝１まで実行する処理を、

からｔを１ずつ減少させながらｔ＝Ｌまで実行する第４のToffoli演算過程と、第４のToffoli演算過程による処理の後、ｋ個の量子ビットＱｙ_ｉ・ｋ，…，Ｑｙ_{ｉ・ｋ＋ｋ−１}を制御ビットとし、補助量子ビットＱｚ_ｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のk-Toffoli演算過程と、第２のk-Toffoli演算過程による処理の後、量子ビットＱｘ_{ｉ・ｋ+ｊ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ+ｊ}を目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のCNOT演算過程と、を有する。

また、本発明において好ましくは、第１のSUM演算過程及び第２のSUM演算過程による処理の後、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋに対してNOT演算を施す処理を0≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第１のNOT演算過程と、上記繰上げ値演算過程が具備する、補助量子ビットＱｚ_ｗ，１の量子状態を｜ｄ_ｗ＞とする処理の逆演算を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに、量子ビットＱｘ_{（ｗ＋１）・ｋ−１}，…，Ｑｘ_ｗ・ｋと量子ビットＱｙ_{（ｗ＋１）・ｋ−１}，…，Ｑｙ_ｗ・ｋと補助量子ビットＱｚ_ｗ，１とに対する上記HIGHBIT演算の逆演算であるHIGHBIT-REV演算を０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行する逆演算過程と、逆演算過程による処理の後、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋに対してNOT演算を施す処理を０≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第２のNOT演算過程と、をさらに実行する。なお、αをβに変換する処理の逆演算とは、βをαに変換する処理の意味である。

これにより、補助量子ビットの量子状態を初期化でき、補助量子ビットの再利用が可能となる。

また、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋと量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと補助量子ビットＱｚ_ｉ，１とに対する上記HIGHBIT演算は、例えば、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、補助量子ビットＱｚ_ｉ，１を目標ビットとするToffoli演算を行う過程と、ｋ≧３である場合にのみ行われる、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を第１量子ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を第２量子ビットとし、補助量子ビットＱｚ_ｉ，１を第３量子ビットとしたMAJ演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ}，Ｑｙ_{ｉ・ｋ＋ｗ}を制御ビットとし、量子ビットＱｘ_ｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝１から１ずつ増加させてｗ＝ｋ−２まで実行する過程と、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}を第１量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を第２量子ビットとし、補助量子ビットＱｚ_ｉ，１を第３量子ビットとしたMAJ演算を実行する過程と、ｋ≧３である場合にのみ行われる、量子ビットＱｘ_ｉ・ｋを制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｘ_ｉ・ｋを制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ−１}，Ｑｙ_{ｉ・ｋ＋ｗ−１}を制御ビットとし、量子ビットＱｘ_ｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−１から１ずつ減少させてｗ＝２まで実行する過程と、量子ビットＱｙ_ｉ・ｋにNOT演算を施す過程と、ｋ≧３である場合にのみ行われる、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたToffoli演算と、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたToffoli演算とを、それぞれ、２≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、量子ビットＱｙ_ｉ・ｋにNOT演算を施す過程と、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋１}を目標ビットとしたToffoli演算と、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋１}を目標ビットとしたToffoli演算とを、それぞれ実行する過程と、を実行する演算であり、上記MAJ演算は、第３量子ビットを制御ビットとし、第２量子ビットを目標ビットとしたCNOT演算を行う第１過程と、第３量子ビットを制御ビットとし、第１量子ビットを目標ビットとしたCNOT演算を行う第２過程と、上記第１過程及び上記第２過程の後に行われる、第１量子ビット及び第２量子ビットを制御ビットとし、第３量子ビットを目標ビットとしたToffoli演算を行うMAJ第３過程と、を実行する演算である。

また、量子ビットＱｘ_ｋ−１，…，Ｑｘ_０と量子ビットＱｙ_ｋ−１，…，Ｑｙ_０とに対する上記SUM演算は、例えば、量子ビットＱｙ_ｋ−１を制御ビットとし、量子ビットＱｘ_ｗを目標ビットとしたCNOT演算と、量子ビットＱｙ_ｋ−１を制御ビットとし、量子ビットＱｙ_ｗを目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する過程と、量子ビットＱｘ_ｗを第１量子ビットとし、量子ビットＱｙ_ｗを第２量子ビットとし、量子ビットＱｙ_ｋ−１を第３量子ビットとしたMAJ演算を、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−２まで実行する過程と、量子ビットＱｘ_ｗを制御ビットとし、量子ビットＱｙ_ｗを目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、を実行する演算である。また、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋと量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと補助量子ビットＱｚ_{ｉ−１，１}とに対する上記繰上げSUM演算〔１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕は、例えば、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する過程と、補助量子ビットＱｚ_{ｉ−１，１}を制御ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を目標ビットとしてCNOT演算を実行する過程と、ｋ≧３である場合にのみ行われる、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を第１量子ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を第２量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を第３量子ビットとしたMAJ演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ}，Ｑｙ_{ｉ・ｋ＋ｗ}を制御ビットとし、補助量子ビットＱｚ_{ｉ−１，１}を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−３まで実行する過程と、量子ビットＱｘ_{（ｉ＋１）・ｋ−２}を第１量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−２}を第２量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を第３量子ビットとしたMAJ演算を実行する過程と、ｋ≧３である場合にのみ行われる、補助量子ビットＱｚ_{ｉ−１，１}を制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ−１}，Ｑｙ_{ｉ・ｋ＋ｗ−１}を制御ビットとし、補助量子ビットＱｚ_{ｉ−１，１}を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−２から１ずつ減少させてｗ＝１まで実行する過程と、
補助量子ビットＱｚ_{ｉ−１，１}を制御ビットとし、量子ビットＱｘ_ｉ・ｋを目標ビットとしたCNOT演算を実行する過程と、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、を実行する演算を実行する過程と、を実行する演算である。

また、本発明において好ましくは、定数ｋは、ｌｏｇ_２（ｌｏｇ_２ｎ）以下の最大の整数である。

この場合、本発明の演算に必要となる補助量子ビットの数はＯ（ｎ／ｌｏｇ_２ｎ）となる。なお、定数ｋ＝Ｏ（ｌｏｇ_２ｎ）である限り、本発明の演算に必要となる補助量子ビットの数はＯ（ｎ／ｌｏｇ_２ｎ）となることがいえる。

以上のように、本発明では、加算処理ブロック単位で繰上げ値を求め、補助量子ビットを用いて当該加算処理ブロック単位の繰上げ処理及び加算値の最上位ビット値の算出を行い、加算処理ブロック単位で加算処理を行うとした。そのため、１ビット毎に加算処理及び繰上げ処理を行う従来方法に比べ、繰上げ処理に必要な補助量子ビット数を削減できる。その結果、従来よりも少ない数の補助量子ビットで量子加算演算が可能となる。

以下、本発明を実施するための最良の形態を図面を参照して説明する。

＜構成＞
図１は、本形態の量子加算演算装置１の構成を例示した図である。

本発明の量子加算演算装置は、２つの２進数ａ＝ａ_ｎ−１…ａ_０〔ａ_ｐ∈｛０，１｝，ｐ∈｛０，…，ｎ−１｝，ｎ≧４〕及びｂ＝ｂ_ｎ−１…ｂ_０〔ｂ_ｐ∈｛０，１｝〕に対し、ａ＋ｂ＝ｓ_ｎ…ｓ_０〔ｓ_ｑ∈｛０，１｝，ｑ∈｛０，…，ｎ｝〕を算出する。図１では、その一例としてｎ＝８の場合の量子加算演算装置１の構成を例示する。

図１に例示するように、量子加算演算装置１は、非演算子及び演算結果の情報を保持させる量子ビット１０と、補助ビットとして使用される量子ビットである複数の補助量子ビット２０と、量子ビット１０及び補助量子ビット２０にHIGHBIT演算を施すHIGHBIT演算部３０と、HIGHBIT演算部３０の逆演算を行うHIGHBIT-REV演算部４０と、量子ビット１０及び補助量子ビット２０にCNOT演算を施すCNOT演算部５０と、量子ビット１０にNOT演算を施すNOT演算部６０と、量子ビット１０及び補助量子ビット２０にk-Toffoli演算を施すk-Toffoli演算部７０と、2-Toffoli演算を施すToffoli演算部8０と、量子ビット１０にSUM演算を施すSUM演算部９０と、量子ビット１０及び補助量子ビット２０に繰上げSUM演算を施す繰上げSUM演算部１００と、制御部１１０とを具備する。

ここで、量子ビット１０は、初期量子状態がそれぞれ｜ａ_０＞，…，｜ａ_ｎ−１＞であるｎ個の量子ビットＱｘ_０，…，Ｑｘ_ｎ−１と、初期量子状態がそれぞれ｜ｂ_０＞，…，｜ｂ_ｎ−１＞であるｎ個の量子ビットＱｙ_０，…，Ｑｙ_ｎ−１とによって構成される（図１の例では、ｎ＝８）。また、量子ビット１０は加算処理単位である加算処理単位ブロック１１毎に分類される。本形態の場合、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋと量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋとをｉ番目〔０≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕の加算処理ブロックＡ_ｉとする。なお、この例のｋはｎを割り切る２以上ｎ未満の整数の定数であり、ｋ＝Ｏ（ｌｏｇ_２ｎ）を満たす。一例として、ｌｏｇ_２（ｌｏｇ_２ｎ）以下の最大の整数を定数ｋとする。図１の例はｋ＝２とした場合の例である。

また、補助量子ビット２０は、初期量子状態が｜０＞である１個の補助量子ビットＱｚ_０，１と、初期量子状態がそれぞれ｜０＞である２・｛（ｎ／ｋ）−１｝個の補助量子ビットＱｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−１，１}，Ｑｚ_{（ｎ／ｋ）−１，２}と、初期量子状態がそれぞれ｜０＞である

個の補助量子ビットＱｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}とを有する（図１の例では、ｎ＝８）。また、これら以外にもk-Toffoli演算を行う場合等に補助量子ビットが必要となるが、本形態の量子回路全体として使用する補助量子ビットの数はＯ（ｎ／ｌｏｇ_２ｎ）となる（詳細は後述する）。

また、本形態の量子回路はNOT演算とCNOT演算とToffoli演算とを基本演算とし、各演算は、これらの組み合わせによって実現される。なお、これらの基本演算、HIGHBIT演算、k-Toffoli演算、SUM演算及び繰上げSUM演算の詳細については後述する。また、量子加算演算装置１のハードウェア構成例については後述する。

＜処理＞
次に、本形態の量子加算演算装置１の処理について説明する。

図２〜９は、本形態の量子加算演算装置１の処理内容を示す量子回路の例示である。

ここで、図２は本形態の演算の前段の量子操作を示す量子回路であり、図３は図２の量子操作の後に行われる後段の量子操作を示す量子回路である。また、図２，３は、８ビット同士（ｎ＝８）の加算演算を行う場合の例である。

また、図４，５は、本形態のHIGHBIT演算を例示した量子回路である。ここで、図４（ａ）はHIGHBIT演算のステージ１を示し、図４（ｂ）はHIGHBIT演算のステージ２を示し、図５はHIGHBIT演算のステージ３を示す。すなわち、図４（ａ），図４（ｂ），図５という順序で量子操作が行われる。なお、図４，５はｋ＝５，ｉ＝０の場合のHIGHBIT演算を例示している。

また、図６は、本形態のSUM演算を例示した量子回路である。ここで、図６（ａ）はSUM演算のステージ１を示し、図４（ｂ）はSUM演算のステージ２を示す。すなわち、図６（ａ），図６（ｂ）という順序で量子操作が行われる。なお、図６はｋ＝５の場合のSUM演算を例示している。

また、図７，８は、本形態の繰上げSUM演算を例示した量子回路である。ここで、図７（ａ）は繰上げSUM演算のステージ１を示し、図７（ｂ）は繰上げSUM演算のステージ２を示し、図８は繰上げSUM演算のステージ３を示す。すなわち、図７（ａ），図７（ｂ），図８という順序で量子操作が行われる。なお、図７，８はｋ＝５，ｉ＝１の場合の繰上げSUM演算を例示している。

また、図９（ａ）はNOT演算を示す量子回路であり、図９（ｂ）はCNOT演算を示す量子回路であり、図９（ｃ）はToffoli演算（2-Toffoli演算）を示す量子回路であり、図９（ｄ）はMAJ演算を示す量子回路である。

また、図１０〜１６は、本形態の量子加算演算装置１の処理内容を示すフローチャートの例示である。ここで、図１０，１１は、本形態の演算の前段の量子操作を説明するためのフローチャートであり、図１２は、本形態の演算の後段の量子操作（補助量子ビット初期化）を説明するためのフローチャートである。また、図１３，１４は、本形態のHIGHBIT演算の詳細を説明するためのフローチャートであり、図１５は、本形態のSUM演算の詳細を説明するためのフローチャートであり、図１６は、本形態の繰上げSUM演算の詳細を説明するためのフローチャートである。

なお、図２，１０，１１に例示する前段の量子操作のみで加算結果は得られる。よって、図３，１２に例示する後段の量子操作は必須ではない。しかし、図３，１２に例示する後段の量子操作を行うことにより、演算結果と無関係な補助量子ビット２０（Ｑｚ_０，１，Ｑｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−１，２}，Ｑｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}）を初期量子状態｜０＞に戻すことができる。その結果、当該演算結果と無関係な補助量子ビット２０を別の演算の補助ビットとして再利用できる。本形態では、当該後段の量子操作をも行う処理を説明する。

［処理の全体（図２，３，１０〜１２）］
まず、本形態の処理の全体を説明する。なお、本形態の各処理は、制御部１１０の制御のもと実行される。

まず、HIGHBIT演算部３０が、加算処理ブロックＡ_ｉに属する初期量子状態の量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋ及び量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと、初期量子状態の補助量子ビットＱｚ_ｉ，１とに対してHIGHBIT演算を施し、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋの量子状態をそれぞれ｜ａ_{（ｉ＋１）・ｋ−１}＞，…，｜ａ_ｉ・ｋ＞とし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋの量子状態をそれぞれ｜ｂ_{（ｉ＋１）・ｋ−１}＞，…，｜ｂ_ｉ・ｋ＞とし、補助量子ビットＱｚ_ｉ，１の量子状態を｜ｃ_ｉ＞〔ｃ_ｉは、２つの２進数ａ_{（ｉ＋１）・ｋ−１}…ａ_ｉ・ｋとｂ_{（ｉ＋１）・ｋ−１}…ｂ_ｉ・ｋの和を２進表記した場合の最上位ビット値〕とする処理を、各加算処理ブロックＡ_ｉ〔０≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕についてそれぞれ実行する（ステップＳ１／HIGHBIT演算過程）。なお、ステップＳ１内の処理の順序には限定はない。すなわち、ステップＳ１の処理は、０≦ｉ≦（ｎ／ｋ）−１の各ｉについてｉを１ずつ増加又は減少させながら順次実行されてもよいし、０≦ｉ≦（ｎ／ｋ）−１の各ｉについて同時（並列）に実行されてもよい。

次に、CNOT演算部５０、k-Toffoli演算部７０及びToffoli演算部８０（「繰上げ値演算部」を構成）が、補助量子ビットＱｚ_０，１，Ｑｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−１，１}，Ｑｚ_{（ｎ／ｋ）−１，２}，Ｑｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}を用い、補助量子ビットＱｚ_ｗ，１の量子状態を｜ｄ_ｗ＞〔ｄ_ｗ∈｛０，１｝は、加算処理ブロックＡ_ｗから加算処理ブロックＡ_ｗ＋１への繰上げ値〕とする処理を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに補助量子ビットＱｚ_{（ｎ／ｋ）−１，１}の量子状態を｜ｓ_ｎ＞とする処理を実行する（ステップＳ２〜９／繰上げ値演算過程）。

繰上げ値演算過程では、まず、CNOT演算部５０が、量子ビットＱｘ_{ｉ・ｋ+ｊ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ+ｊ}を目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する（ステップＳ２／第１のCNOT演算過程）。なお、ステップＳ２内の処理の順序には限定はない。すなわち、ステップＳ２の処理は、０≦ｊ≦ｋ−１（ｊは整数）及び１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）を満たす全てのｉ，ｊの組み合わせについて同時（並列）に実行されもよいし、各ｉ，ｊの組み合わせ毎に順次実行されてもよい。一例として、ｊをｊ＝０から１ずつ増加させながらｊ＝ｋ−１までステップＳ２のCNOT演算を施す処理を、ｉをｉ＝１から１ずつ増加させながらｉ＝（ｎ／ｋ）−１まで実行する方法を例示できる。

次に、k-Toffoli演算部７０が、ｋ個の量子ビットＱｙ_ｉ・ｋ，…，Ｑｙ_{ｉ・ｋ＋ｋ−１}を制御ビットとし、補助量子ビットＱｚ_ｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する（ステップＳ３／第１のk-Toffoli演算過程）。なお、ステップＳ３内の処理の順序に限定はなく、各ｉについて同時（並列）に実行されてもよいし、各ｉについて順次実行されてもよい。一例として、ステップＳ３のk-Toffoli演算を施す処理を、ｉをｉ＝１から１ずつ増加させながらｉ＝（ｎ／ｋ）−１まで実行する方法を例示できる。

次に、Toffoli演算部８０が、ステップＳ３によるk-Toffoli演算が施された補助量子ビットＱｚ_ｉ，２を補助量子ビットＱｐ_Ｌ−１（ｉ）と表現した場合における、補助量子ビットＱｐ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}うちの１つの補助量子ビットである補助量子ビットＱｐ_ｔ（ｉ）を目標ビットとしたToffoli演算を、目標ビットを重複させることなく、ｉ＝１からｉを１ずつ増加させながら

まで実行する（ステップＳ４／第１のToffoli演算過程）。

次に、Toffoli演算部８０が、ステップＳ１による処理が施された補助量子ビットＱｚ_ｉ，１を補助量子ビットＱｇ_Ｌ−１（ｉ）と表現した場合における、補助量子ビットＱｇ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｇ_ｔ−１（２ｉ＋１）を目標ビットとしたToffoli演算〔当該Toffoli演算後の補助量子ビットＱｇ_ｔ−１（２ｉ＋１）を補助量子ビットＱｇ_ｔ（ｉ）と表現〕を、ｉ＝０からｉを１ずつ増加させながら

まで実行する（ステップＳ５／第２のToffoli演算過程）。

次に、Toffoli演算部８０が、ｕ＝２^ｔ・ｉ／ｋ−１とした場合における補助量子ビットＱｚ_ｕ，１，Ｑｐ_ｔ−１（２ｉ）を制御ビットとし、補助量子ビットＱｇ_ｔ−１（２ｉ）を目標ビットとしたToffoli演算を、ｉ＝１からｉを１ずつ増加させながら

まで実行する処理を、

からｔを１ずつ減少させながらｔ＝Ｌまで実行する（ステップＳ６／第３のToffoli演算過程）。

次に、Toffoli演算部８０がステップＳ４の処理を逆の順序で実行する（ステップＳ４の処理の逆演算を実行する）。すなわち、Toffoli演算部８０が、補助量子ビットＱｐ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｐ_ｔ（ｉ）を目標ビットとしたToffoli演算を、

からｔを１ずつ減少させながらｔ＝Ｌまで実行する（ステップＳ７／第４のToffoli演算過程）。

次に、ステップＳ２，３の処理を逆の順序で実行する（ステップＳ２，３によってなされる演算の逆演算を実行する）。すなわち、まず、k-Toffoli演算部７０が、ｋ個の量子ビットＱｙ_ｉ・ｋ，…，Ｑｙ_{ｉ・ｋ＋ｋ−１}を制御ビットとし、補助量子ビットＱｚ_ｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する（ステップＳ８／第２のk-Toffoli演算過程）。次に、CNOT演算部５０が、量子ビットＱｘ_{ｉ・ｋ+ｊ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ+ｊ}を目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する（ステップＳ９／第２のCNOT演算過程／繰上げ値演算過程終了）。

次に、SUM演算部９０が、加算処理ブロックＡ_０に属する量子ビットＱｘ_ｋ−１，…，Ｑｘ_０と量子ビットＱｙ_ｋ−１，…，Ｑｙ_０とに対してSUM演算を施し、量子ビットＱｘ_ｋ−１，…，Ｑｘ_０の量子状態をそれぞれ｜ａ_ｋ−１＞，…，｜ａ_０＞とし、量子ビットＱｙ_ｋ−１，…，Ｑｙ_０の量子状態をそれぞれ｜ｓ_ｋ−１＞，…，｜ｓ_０＞とする（ステップＳ１０／第１のSUM演算過程）。

また、繰上げSUM演算部１００が、加算処理ブロックＡ_ｉに属する量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋ及び量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと、補助量子ビットＱｚ_{ｉ−１，１}とに対して繰上げSUM演算を施し、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋの量子状態をそれぞれ｜ａ_{（ｉ＋１）・ｋ−１}＞，…，｜ａ_ｉ・ｋ＞とし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋの量子状態をそれぞれ｜ｓ_{（ｉ＋１）・ｋ−１}＞，…，｜ｓ_ｉ・ｋ＞とし、補助量子ビットＱｚ_{ｉ−１，１}の量子状態を維持する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する（ステップＳ１１／第２のSUM演算過程）。

ここまでが前段の処理である。ここまでの処理によって、ｎ個の量子ビットＱｘ_０，…，Ｑｘ_ｎ−１の量子状態がそれぞれ｜ａ_０＞，…，｜ａ_ｎ−１＞となり、量子ビットＱｙ_０，…，Ｑｙ_ｎ−１の量子状態がそれぞれ｜ｓ_０＞，…，｜ｓ_ｎ−１＞となり、補助量子ビットＱｚ_{（ｎ／ｋ）−１，１}の量子状態が｜ｓ_ｎ＞となる。すなわち、量子ビットＱｘ_０，…，Ｑｘ_ｎ−１と補助量子ビットＱｚ_{（ｎ／ｋ）−１，１}を観測することによって加算演算結果ａ＋ｂ＝ｓ_ｎ…ｓ_０を得ることができる。

この後、後段の処理によって、この演算結果と無関係な補助量子ビットＱｚ_０，１，Ｑｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−１，２}，Ｑｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}の量子状態を初期量子状態｜０＞に戻す。

まず、NOT演算部６０が、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋに対してNOT演算を施す処理を0≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する（ステップＳ２１／第１のNOT演算過程）。なお、ステップＳ２１内の処理の順序に限定はない。すなわち、ステップＳ２１の処理は、0≦ｉ≦（ｎ／ｋ）−２に属するｉについて同時（並列）に実行されてもよく、ｉ毎に順次実行されてもよい（例えばｉを０から１ずつ増加させながらｉ＝（ｎ／ｋ）−２まで順次実行）。

次に、CNOT演算部５０とk-Toffoli演算部７０とToffoli演算部８０と（「逆演算部」を構成）が、上記繰上げ値演算過程が具備する、補助量子ビットＱｚ_ｗ，１の量子状態を｜ｄ_ｗ＞とする処理の逆演算を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに、HIGHBIT-REV演算部４０（「逆演算部」を構成）が、量子ビットＱｘ_{（ｗ＋１）・ｋ−１}，…，Ｑｘ_ｗ・ｋと量子ビットＱｙ_{（ｗ＋１）・ｋ−１}，…，Ｑｙ_ｗ・ｋと補助量子ビットＱｚ_ｗ，１とに対する上記HIGHBIT演算の逆演算であるHIGHBIT-REV演算を０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行する（逆演算過程）。

すなわち、ｎをｎ−ｋとおいた場合における、上記のHIGHBIT演算過程（ステップＳ１）、第１のCNOT演算過程（ステップＳ２）、第１のk-Toffoli演算過程（ステップＳ３）、第１のToffoli演算過程（ステップＳ４）、第２のToffoli演算過程（ステップＳ５）、第３のToffoli演算過程（ステップＳ６）、第４のToffoli演算過程（ステップＳ７）、第２のk-Toffoli演算過程（ステップＳ８）及び第２のCNOT演算過程（ステップＳ９）によって順次行われる処理からなる演算の逆演算を実行し（ステップＳ２２）、量子ビットＱｘ_０，…，Ｑｘ_{ｎ−ｋ−１}の量子状態をそれぞれ｜ａ_０＞，…，｜ａ_{ｎ−ｋ−１}＞とし、量子ビットＱｙ_０，…，Ｑｙ_{ｎ−ｋ−１}の量子状態をそれぞれ｜ｓ_０＞，…，｜ｓ_{ｎ−ｋ−１}＞の反転状態とし、補助量子ビットＱｚ_０，１の量子状態を｜０＞とし、補助量子ビットＱｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−２，１}，Ｑｚ_{（ｎ／ｋ）−２，２}の量子状態をそれぞれ｜０＞にする。つまり、ステップＳ２２では、ｎをｎ−ｋとおいた場合における、第２のCNOT演算過程（ステップＳ９）を逆の順序で実行し、第２のk-Toffoli演算過程（ステップＳ８）を逆の順序で実行し、第４のToffoli演算過程（ステップＳ７）を逆の順序で実行し、・・・、HIGHBIT演算過程（ステップＳ１）を逆の順序で実行する処理を行う。なお、量子状態｜α＞の反転状態とは、量子状態｜α(+)1＞を意味する。なお、(+)は排他的論理和演算子

を示す。

次に、CNOT演算部５０が、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋに対してNOT演算を施す処理を０≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する（ステップＳ２３／第２のNOT演算過程）。なお、ステップＳ２３内の処理の順序に限定はない。

＜演算内容の詳細＞
次に、本形態で用いた各演算内容の詳細について説明する。

［基本演算］
まず、NOT演算、CNOT演算、Toffoli演算及びMAJ演算について説明する。

図９（ａ）に示すように、NOT演算は、量子状態｜ｘ＞の量子ビットＱ_αを、量子状態｜ｘ(+)1＞の量子ビットＱ_αにする操作である。

また、図９（ｂ）に示すように、量子状態｜ｘ＞の量子ビットＱ_αを制御ビットとし、量子状態｜ｙ＞の量子ビットＱ_βを目標ビットビットとするCNOT演算は、量子状態｜ｘ＞の量子ビットＱ_α及び量子状態｜ｙ＞の量子ビットＱ_βを、量子状態｜ｘ＞の量子ビットＱ_α及び量子状態｜x(+)ｙ＞の量子ビットＱ_βにする操作である。

また、図９（ｃ）に示すように、量子状態｜ｘ＞の量子ビットＱ_αと量子状態｜ｙ＞の量子ビットＱ_βとを制御ビットとし、量子状態｜ｚ＞の量子ビットＱ_γを目標ビットビットとするToffoli演算は、量子状態｜ｘ＞の量子ビットＱ_αと量子状態｜ｙ＞の量子ビットＱ_βと量子状態｜ｚ＞の量子ビットＱ_γとを、量子状態｜ｘ＞の量子ビットＱ_αと量子状態｜ｙ＞の量子ビットＱ_βと量子状態｜ｚ(+)xy＞の量子ビットＱ_γにする操作である。なお、量子状態｜ｘ_１＞の量子ビットＱ_α（１），...，量子状態｜ｘ_ｋ＞の量子ビットＱ_α（ｋ）を制御ビットとし、量子状態｜ｚ＞の量子ビットＱ_γを目標ビットビットとするk-Toffoli演算は、量子状態｜ｘ_１＞の量子ビットＱ_α（１），...，量子状態｜ｘ_ｋ＞の量子ビットＱ_α（ｋ）と量子状態｜ｚ＞の量子ビットＱ_γとを、量子状態｜ｘ_１＞の量子ビットＱ_α（１），...，量子状態｜ｘ_ｋ＞の量子ビットＱ_α（ｋ）と量子状態｜ｚ(+)ｘ_１・... ・ｘ_ｋ＞の量子ビットＱ_γにする操作である。

また、図９（ｄ）に示すように、MAJ演算は、第３量子ビットＱ_γを制御ビットとし、第２量子ビットＱ_βを目標ビットとしたCNOT演算を行う第１過程と、第３量子ビットＱ_γを制御ビットとし、第１量子ビットＱ_αを目標ビットとしたCNOT演算を行う第２過程と、上記第１過程及び上記第２過程の後に行われる、第１量子ビットＱ_α及び第２量子ビットＱ_βを制御ビットとし、第３量子ビットＱ_γを目標ビットとしたToffoli演算を行うMAJ第３過程と、を実行する演算である。これにより、量子状態｜ｘ＞の第１量子ビットＱ_αと量子状態｜ｙ＞の第２量子ビットＱ_βと量子状態｜ｚ＞の第３量子ビットＱ_γとを、量子状態｜ｘ(+)ｚ＞の第１量子ビットＱ_αと量子状態｜ｙ(+)ｚ＞の第２量子ビットＱ_βと量子状態｜xy(+)yz(+)zx＞の第３量子ビットＱ_γにする。

［HIGHBIT演算（図４（ａ）（ｂ），５，１３，１４）］
次に、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋと量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと補助量子ビットＱｚ_ｉ，１とに対するHIGHBIT演算について説明する。

HIGHBIT演算では、まず、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、補助量子ビットＱｚ_ｉ，１を目標ビットとするToffoli演算を行う（ステップＳ３１）。

次に、ｋ≧３である場合にのみ（ステップＳ３２）、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を第１量子ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を第２量子ビットとし、補助量子ビットＱｚ_ｉ，１を第３量子ビットとしたMAJ演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ}，Ｑｙ_{ｉ・ｋ＋ｗ}を制御ビットとし、量子ビットＱｘ_ｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝１から１ずつ増加させてｗ＝ｋ−２まで実行し（ステップＳ３３）、ステップＳ３４に進む。なお、ｋ＜３の場合には、ステップＳ３３を実行することなくステップＳ３４に進む。

ステップＳ３４では、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}を第１量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を第２量子ビットとし、補助量子ビットＱｚ_ｉ，１を第３量子ビットとしたMAJ演算を実行する（ステップＳ３４）。

次に、ｋ≧３である場合にのみ（ステップＳ３５）、量子ビットＱｘ_ｉ・ｋを制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｘ_ｉ・ｋを制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ−１}，Ｑｙ_{ｉ・ｋ＋ｗ−１}を制御ビットとし、量子ビットＱｘ_ｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−１から１ずつ減少させてｗ＝２まで実行し（ステップＳ３６）、ステップＳ３７に進む。なお、ｋ＜３の場合には、ステップＳ３６を実行することなくステップＳ３７に進む。

ステップＳ３７では、量子ビットＱｙ_ｉ・ｋにNOT演算を施す（ステップＳ３７）。

次に、ｋ≧３である場合にのみ（ステップＳ３８）、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたToffoli演算と、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたToffoli演算とを、それぞれ、２≦ｗ≦ｋ−１（ｗは整数）について実行する（ステップＳ３９）。なお、ｋ＜３の場合には、ステップＳ３９を実行することなくステップＳ４０に進む。

ステップＳ４０では、量子ビットＱｙ_ｉ・ｋにNOT演算を施す（ステップＳ４０）。

次に、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋１}を目標ビットとしたToffoli演算と、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋１}を目標ビットとしたToffoli演算とを、それぞれ実行する過程と、を実行する（ステップＳ４１）。

［SUM演算（図６（ａ）（ｂ），１５）］
次に、量子ビットＱｘ_ｋ−１，…，Ｑｘ_０と量子ビットＱｙ_ｋ−１，…，Ｑｙ_０とに対するSUM演算について説明する。

SUM演算では、まず、量子ビットＱｙ_ｋ−１を制御ビットとし、量子ビットＱｘ_ｗを目標ビットとしたCNOT演算と、量子ビットＱｙ_ｋ−１を制御ビットとし、量子ビットＱｙ_ｗを目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する（ステップＳ５１）。次に、量子ビットＱｘ_ｗを第１量子ビットとし、量子ビットＱｙ_ｗを第２量子ビットとし、量子ビットＱｙ_ｋ−１を第３量子ビットとしたMAJ演算を、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−２まで実行する（ステップＳ５２）。次に、量子ビットＱｘ_ｗを制御ビットとし、量子ビットＱｙ_ｗを目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する（ステップＳ５３）。

なお、ｋの値によっては、ステップＳ５１〜Ｓ５３の処理の一部が互いに相殺する場合がある。このような場合には相殺し合う処理を実行しなくてもよい。例えば、図２のｋ＝２の例では、MAJ演算が有する２つのCNOT演算とステップＳ５１のCNOT演算とが相殺されている。

［繰上げSUM演算（図７（ａ）（ｂ），８，１６）］
次に、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋと量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと補助量子ビットＱｚ_{ｉ−１，１}とに対する繰上げSUM演算〔１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕について説明する。

繰上げSUM演算では、まず、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する（ステップＳ６１）。

次に、補助量子ビットＱｚ_{ｉ−１，１}を制御ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を目標ビットとしてCNOT演算を実行する（ステップＳ６２）。

次に、ｋ≧３である場合にのみ（ステップＳ６３）、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を第１量子ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を第２量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を第３量子ビットとしたMAJ演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ}，Ｑｙ_{ｉ・ｋ＋ｗ}を制御ビットとし、補助量子ビットＱｚ_{ｉ−１，１}を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−３まで実行し（ステップＳ６４）、ステップＳ６５に進む。なお、ｋ＜３の場合には、ステップＳ６４を実行することなくステップＳ６５に進む。

ステップＳ６５では、量子ビットＱｘ_{（ｉ＋１）・ｋ−２}を第１量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−２}を第２量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を第３量子ビットとしたMAJ演算を実行する（ステップＳ６５）。

次に、ｋ≧３である場合にのみ（ステップＳ６６）、補助量子ビットＱｚ_{ｉ−１，１}を制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ−１}，Ｑｙ_{ｉ・ｋ＋ｗ−１}を制御ビットとし、補助量子ビットＱｚ_{ｉ−１，１}を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−２から１ずつ減少させてｗ＝１まで実行し（ステップＳ６７）、ステップＳ６８に進む。なお、ｋ＜３の場合には、ステップＳ６７を実行することなくステップＳ６８に進む。

ステップＳ６８では、補助量子ビットＱｚ_{ｉ−１，１}を制御ビットとし、量子ビットＱｘ_ｉ・ｋを目標ビットとしたCNOT演算を実行する（ステップＳ６８）。次に、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する（ステップＳ６９）。

＜ハードウェア構成＞
次に本形態の量子加算演算装置１のハードウェア構成を例示する。

本形態の量子加算演算装置１は、量子コンピュータ或いは量子コンピュータと古典コンユータとの組合せで実現できる。量子コンピュータを実現する物理系としては、例えば、イオントラップを用いる方法（J. I. Cirac and P. Zoller, Quantum computations with cold trapped ions, Physical Review Letter 74;4091, 1995）、量子ビットとして光子の偏光や光路を用いる方法（Y. Nakamura, M. Kitagawa, K. Igeta, In 3-rd Proc. Asia-Pacific Phys. Comf., World Scientific, Singapore, 1988）、液体中の各スピンを用いる方法（Gershenfield, Chuang, Bulk spin resonance quantum computation, Science, 275;350, 1997）、シリコン結晶中の核スピンを用いる方法（B. E. Kane, A silicon-based nuclear spin quantum computer, Nature 393, 133, 1998）、量子ドット中の電子スピンを用いる方法（D. Loss and D. P. DiVincenzo, Quantum computation with quantum dots, Physical Review A 57, 120-126, 1998）、超伝導素子を用いる方法（Y. Nakamura, Yu. A. Pashkin and J. S. Tsai, Coherent control of macroscopic quantum states in a single-cooper pair box, Nature 393, 786-788, 1999）等を例示できる。また、それぞれの物理系に対する量子コンピュータの実現方法については、「http://www.ipa.go.jp/security/fy11/report/contents/crypto/crypto/report/QuantumComputers/contents/doc/qc_survey.pdf」や「M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Chapter 7 Physical Realization」に詳しい。

以下に、量子加算演算装置１を実現するための具体的なハードウェア構成を例示する。

［量子ビット］
イオントラップ量子コンピュータでは、例えば、イオンの基底状態と励起状態を利用して量子ビットを実現し、イオンを直線上に並べて演算処理を行う。また、核スピンを量子ビットとして用いる場合には、例えば、「T. D. Ladd, et al., "All-Silicon quantum computer," Phys. Rev. Lett., vol. 89, no. 1, 017901-1‐017901-4, July 1, 2002.」に記載されているようにＳｉ（１１１）基板等に各量子ビットを生成して演算処理を行う。

なお、量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いてもよいし、各量子ビットが生成された基板をｍＫ（ミリケルビン）オーダー以下に冷却してスピンの向きを揃えた後、所定の電磁波パルスを印加して生成してもよい。また、量子ビットとして光子の偏光を用いる場合には、例えば、パラメトリックダウンコンバージョン（ＰＤＣ：parametric down conversion）（例えば、「P. G. Kwiat, K. Mattle, H. Weinfurter, A. Zeilinger, A. V. Sergienko, and Y. Shih, “New high-intensity source of polarization-entangled photon pairs,” Phys. Rev. Lett. ,75:4337-4341, 1995.」「P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A, 60:R773-R776, 1999.」等参照。）により生成された複数個の単一光子を用いる。この場合、各量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いる。また、パラメトリックダウンコンバージョン等により生成された単一光子に、ビームスプリッタや偏光回転素子等によって実現されるウォルシューアダマール変換、ＣＮＯＴ、回転等の操作を行い、上述の初期量子状態を生成することとしてもよい。

その他、上記の文献に記載された方法で量子ビットを用意することとしてもよい。

また、演算前後や演算途中において量子ビットの量子状態を保存する必要がある場合には、例えば、量子ドット内の電子準位、核スピン、あるいは超伝導体内部の電荷（クーパー対）量を量子ビットとして用いてデータを保存する量子メモリ等を用いてもよい（A.Barenco, D.Deutsch, and A.Ekert, Phys. Rev. Lett.74,4083(1995)、松枝秀明電子情報通信学会誌 A Vol.J81-A No.12(1998)1978、T.H.Oosterkamp et.al., Nature 395,873(1998)、D.Loss and D.P. DiVincenzo, Phys. Rev. A57(1998) 120. T.Oshima, quant-ph/0002004, http://arxiv.org/abs/quant-ph/0002004、B.E.Kane, A silicon-based nuclear spin quantum computer, Nature, 393, 133(1998)、http://www.snf.unsw.edu.au/、Y.Nakamura, Yu. A. Pashkin and J.S.Tsai, Nature 398(1999)768）。

［CNOT演算］
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によってCNOT演算を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光ビームスプリッタ等を用い、「T.B. Pittman, M.J. Fitch, B.C. Jacobs, J.D. Franson: “Experimental Controlled-NOT Logic Gate for Single Photons in the Coincidence Basis,” quant-ph/0303095, http://arxiv.org/abs/quant-ph/0303095」記載のPittman et al. 方式によってCNOT演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってCNOT演算を実現できる。

その他、上記の文献に記載された方法でCNOT演算を実現してもよい。

［Toffoli演算］
Toffoli演算は、CNOT演算と量子ビット単体へのユニタリ変換との組み合わせによって実現できる。なお、この演算にも補助ビットとなる量子ビットが必要となる。k-Toffoli演算についても同様である。

［量子ビット単体の操作（NOT演算，ユニタリ変換）］
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。

＜本形態の特徴＞
以上のように、本形態では、量子ビット毎に加算処置と繰上げ処理とを行うのではなく、複数の量子ビットからなる加算処理ブロック単位で加算処理と繰上げ処理とを行う。その結果、繰上げ処理に必要となる補助量子ビット数を削減できる。具体的には、Ｏ（ｎ／ｌｏｇ_２ｎ）個の補助量子ビットを用い、Ｏ（ｎ）個の基本演算をＯ（ｌｏｇ_２ｎ）個の計算ステップで実行することにより、２進ｎ桁の加算演算を行うことができる。以下に、本形態の処理でＯ（ｎ／ｌｏｇ_２ｎ）個の補助量子ビットしか使用されないことを示す。

まず、図１１，１２のフローチャートの各ステップで必要な補助量子ビットの数をオーダーで示す（すなわち、補助量子ビットの数を表現する多項式の係数部分までは言及しない）。

［ステップＳ１］
各ｉのHIGHBIT演算において補助量子ビットを１個ずつ使用するため、全体としてＯ（ｎ／ｋ）個の補助量子ビットを用いる。

［ステップＳ２，３］
各k-Toffoli演算がそれぞれ１個の補助量子ビットを使用するため、全体としてＯ（ｎ／ｋ）個の補助量子ビットを用いる（なお、正確には、各k-Toffoli演算は基本演算と１つの補助量子ビットによって実現されるため、全体としてk-Toffoli演算数の２倍の補助量子ビットを用いることになるが、オーダーの評価ではＯ（ｎ／ｋ）個と示して問題ない）。

［ステップＳ４］
各Toffoli演算が１個の補助量子ビットを用いるため、全体として

個の補助量子ビットを用いる。

［ステップＳ５以降］
新たに補助量子ビットを必要としない。
ここで、ｋ＝Ｏ（ｌｏｇ_２ｎ）であるから、Ｏ（ｎ／ｋ）＝Ｏ（ｎ／ｌｏｇ_２ｎ）である。また、Ｌの定め方からＬ＝Ｏ｛ｌｏｇ_２（ｌｏｇ_２ｎ）｝である。これを用いて式（１）を展開するとＯ（ｎ／ｌｏｇ_２ｎ）となる。したがって、上記の各ステップで必要となる補助量子ビットの数の合計はＯ（ｎ／ｌｏｇ_２ｎ）個となる。

なお、本発明は上述の実施の形態に限定されるものではない。例えば、各量子ビットの初期量子状態が、複数の量子状態が重ね合わされたものであってもよい。また、SUM演算の説明で例示したように、相殺し合う処理を省略してもよい。また、前述のようにステップＳ２１〜Ｓ２３の処理を実行しない構成であってもよい。さらに、上述の各種の処理は、上述した記載に従って実行されるのみならず、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。

本発明の産業上の利用分野としては、例えば、量子コンピュータ等を例示できる。

図１は、本形態の量子加算演算装置の構成を例示した図である。図２は本形態の演算の前段の量子操作を示す量子回路である。図３は図２の量子操作の後に行われる後段の量子操作を示す量子回路である。図４は、本形態のHIGHBIT演算を例示した量子回路である。図５は、本形態のHIGHBIT演算を例示した量子回路である。図６は、本形態のSUM演算を例示した量子回路である。図７は、本形態の繰上げSUM演算を例示した量子回路である。図８は、本形態の繰上げSUM演算を例示した量子回路である。図９（ａ）はNOT演算を示す量子回路であり、図９（ｂ）はCNOT演算を示す量子回路であり、図９（ｃ）はToffoli演算（2-Toffoli演算）を示す量子回路であり、図９（ｄ）はMAJ演算を示す量子回路である。図１０は、本形態の演算の前段の量子操作を説明するためのフローチャートである。図１１は、本形態の演算の前段の量子操作を説明するためのフローチャートである。図１２は、本形態の演算の後段の量子操作（補助量子ビット初期化）を説明するためのフローチャートである。図１３は、本形態のHIGHBIT演算の詳細を説明するためのフローチャートである。図１４は、本形態のHIGHBIT演算の詳細を説明するためのフローチャートである。図１５は、本形態のSUM演算の詳細を説明するためのフローチャートである。図１６は、本形態の繰上げSUM演算の詳細を説明するためのフローチャートである。図１７は、非特許文献１に記載された加算演算用の量子回路の例示である。図１８は、非特許文献１に記載された加算演算用の量子回路の例示である。

符号の説明

１量子加算演算装置
１０量子ビット
２０補助量子ビット

Claims

２つの２進数ａ＝ａ_ｎ−１…ａ_０〔ａ_ｐ∈｛０，１｝，ｐ∈｛０，…，ｎ−１｝，ｎ≧４〕及びｂ＝ｂ_ｎ−１…ｂ_０〔ｂ_ｐ∈｛０，１｝〕に対し、ａ＋ｂ＝ｓ_ｎ…ｓ_０〔ｓ_ｑ∈｛０，１｝，ｑ∈｛０，…，ｎ｝〕を算出する量子加算演算方法であって、
初期量子状態がそれぞれ｜ａ_０＞，…，｜ａ_ｎ−１＞であるｎ個の量子ビットＱｘ_０，…，Ｑｘ_ｎ−１と、初期量子状態がそれぞれ｜ｂ_０＞，…，｜ｂ_ｎ−１＞であるｎ個の量子ビットＱｙ_０，…，Ｑｙ_ｎ−１と、初期量子状態が｜０＞である１個の補助量子ビットＱｚ_０，１と、初期量子状態がそれぞれ｜０＞である２・｛（ｎ／ｋ）−１｝〔ｋはｎを割り切る２以上ｎ未満の整数の定数である〕個の補助量子ビットＱｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−１，１}，Ｑｚ_{（ｎ／ｋ）−１，２}と、初期量子状態がそれぞれ｜０＞である

個〔Ｌはｎ／２^Ｌ−１以下の最大の整数をｎ／ｋとする整数である〕の補助量子ビットＱｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}と、が少なくとも存在し、
量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋと量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋとをｉ番目〔０≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕の加算処理ブロックＡ_ｉとし、当該加算処理ブロックＡ_ｉに属する初期量子状態の量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋ及び量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと、初期量子状態の補助量子ビットＱｚ_ｉ，１とに対してHIGHBIT演算を施し、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋの量子状態をそれぞれ｜ａ_{（ｉ＋１）・ｋ−１}＞，…，｜ａ_ｉ・ｋ＞とし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋの量子状態をそれぞれ｜ｂ_{（ｉ＋１）・ｋ−１}＞，…，｜ｂ_ｉ・ｋ＞とし、補助量子ビットＱｚ_ｉ，１の量子状態を｜ｃ_ｉ＞〔ｃ_ｉは、２つの２進数ａ_{（ｉ＋１）・ｋ−１}…ａ_ｉ・ｋとｂ_{（ｉ＋１）・ｋ−１}…ｂ_ｉ・ｋの和を２進表記した場合の最上位ビット値〕とする処理を、各加算処理ブロックＡ_ｉについてそれぞれ実行するHIGHBIT演算過程と、
補助量子ビットＱｚ_０，１，Ｑｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−１，１}，Ｑｚ_{（ｎ／ｋ）−１，２}，Ｑｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}を用い、補助量子ビットＱｚ_ｗ，１の量子状態を｜ｄ_ｗ＞〔ｄ_ｗ∈｛０，１｝は、加算処理ブロックＡ_ｗから加算処理ブロックＡ_ｗ＋１への繰上げ値〕とする処理を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに補助量子ビットＱｚ_{（ｎ／ｋ）−１，１}の量子状態を｜ｓ_ｎ＞とする処理を実行する繰上げ値演算過程と、
加算処理ブロックＡ_０に属する量子ビットＱｘ_ｋ−１，…，Ｑｘ_０と量子ビットＱｙ_ｋ−１，…，Ｑｙ_０とに対してSUM演算を施し、量子ビットＱｘ_ｋ−１，…，Ｑｘ_０の量子状態をそれぞれ｜ａ_ｋ−１＞，…，｜ａ_０＞とし、量子ビットＱｙ_ｋ−１，…，Ｑｙ_０の量子状態をそれぞれ｜ｓ_ｋ−１＞，…，｜ｓ_０＞とする第１のSUM演算過程と、
加算処理ブロックＡ_ｉに属する量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋ及び量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと、補助量子ビットＱｚ_{ｉ−１，１}とに対して繰上げSUM演算を施し、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋの量子状態をそれぞれ｜ａ_{（ｉ＋１）・ｋ−１}＞，…，｜ａ_ｉ・ｋ＞とし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋの量子状態をそれぞれ｜ｓ_{（ｉ＋１）・ｋ−１}＞，…，｜ｓ_ｉ・ｋ＞とし、補助量子ビットＱｚ_{ｉ−１，１}の量子状態を維持する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のSUM演算過程と、
を実行することを特徴とする量子加算演算方法。
請求項１に記載の量子加算演算方法であって、
上記繰上げ値演算過程は、
量子ビットＱｘ_{ｉ・ｋ+ｊ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ+ｊ}を目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のCNOT演算過程と、
上記第１のCNOT演算過程による処理がなされたｋ個の量子ビットＱｙ_ｉ・ｋ，…，Ｑｙ_{ｉ・ｋ＋ｋ−１}を制御ビットとし、補助量子ビットＱｚ_ｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のk-Toffoli演算過程と、
第１のk-Toffoli演算過程によるk-Toffoli演算が施された補助量子ビットＱｚ_ｉ，２を補助量子ビットＱｐ_Ｌ−１（ｉ）と表現した場合における、補助量子ビットＱｐ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}うちの１つの補助量子ビットである補助量子ビットＱｐ_ｔ（ｉ）を目標ビットとしたToffoli演算を、目標ビットを重複させることなく、ｉ＝１からｉを１ずつ増加させながら

まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら

まで実行する第１のToffoli演算過程と、
HIGHBIT演算過程による処理が施された補助量子ビットＱｚ_ｉ，１を補助量子ビットＱｇ_Ｌ−１（ｉ）と表現した場合における、補助量子ビットＱｇ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｇ_ｔ−１（２ｉ＋１）を目標ビットとしたToffoli演算〔当該Toffoli演算後の補助量子ビットＱｇ_ｔ−１（２ｉ＋１）を補助量子ビットＱｇ_ｔ（ｉ）と表現〕を、ｉ＝０からｉを１ずつ増加させながら

まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら

まで実行する第２のToffoli演算過程と、
ｕ＝２^ｔ・ｉ／ｋ−１とした場合における補助量子ビットＱｚ_ｕ，１，Ｑｐ_ｔ−１（２ｉ）を制御ビットとし、補助量子ビットＱｇ_ｔ−１（２ｉ）を目標ビットとしたToffoli演算を、ｉ＝１からｉを１ずつ増加させながら

まで実行する処理を、

からｔを１ずつ減少させながらｔ＝Ｌまで実行する第３のToffoli演算過程と、
補助量子ビットＱｐ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｐ_ｔ（ｉ）を目標ビットとしたToffoli演算を、

からｉを１ずつ減少させながらｉ＝１まで実行する処理を、

からｔを１ずつ減少させながらｔ＝Ｌまで実行する第４のToffoli演算過程と、
第４のToffoli演算過程による処理の後、ｋ個の量子ビットＱｙ_ｉ・ｋ，…，Ｑｙ_{ｉ・ｋ＋ｋ−１}を制御ビットとし、補助量子ビットＱｚ_ｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のk-Toffoli演算過程と、
第２のk-Toffoli演算過程による処理の後、量子ビットＱｘ_{ｉ・ｋ+ｊ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ+ｊ}を目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のCNOT演算過程と、を有する、
ことを特徴とする量子加算演算方法。
請求項１に記載の量子加算演算方法であって、
第１のSUM演算過程及び第２のSUM演算過程による処理の後、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋに対してNOT演算を施す処理を0≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第１のNOT演算過程と、
上記繰上げ値演算過程が具備する、補助量子ビットＱｚ_ｗ，１の量子状態を｜ｄ_ｗ＞とする処理の逆演算を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに、量子ビットＱｘ_{（ｗ＋１）・ｋ−１}，…，Ｑｘ_ｗ・ｋと量子ビットＱｙ_{（ｗ＋１）・ｋ−１}，…，Ｑｙ_ｗ・ｋと補助量子ビットＱｚ_ｗ，１とに対する上記HIGHBIT演算の逆演算であるHIGHBIT-REV演算を０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行する逆演算過程と、
逆演算過程による処理の後、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋに対してNOT演算を施す処理を０≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第２のNOT演算過程と、
をさらに実行することを特徴とする量子加算演算方法。
請求項２に記載の量子加算演算方法であって、
第１のSUM演算過程及び第２のSUM演算過程による処理の後、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋに対してNOT演算を施す処理を0≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第１のNOT演算過程と、
第１のNOT演算過程による処理の後、ｎをｎ−ｋとおいた場合における、上記のHIGHBIT演算過程、第１のCNOT演算過程、第１のk-Toffoli演算過程、第１のToffoli演算過程、第２のToffoli演算過程、第３のToffoli演算過程、第４のToffoli演算過程、第２のk-Toffoli演算過程及び第２のCNOT演算過程によって順次行われる処理からなる演算の逆演算を実行し、
量子ビットＱｘ_０，…，Ｑｘ_{ｎ−ｋ−１}の量子状態をそれぞれ｜ａ_０＞，…，｜ａ_{ｎ−ｋ−１}＞とし、量子ビットＱｙ_０，…，Ｑｙ_{ｎ−ｋ−１}の量子状態をそれぞれ｜ｓ_０＞，…，｜ｓ_{ｎ−ｋ−１}＞の反転状態とし、補助量子ビットＱｚ_０，１の量子状態を｜０＞とし、補助量子ビットＱｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−２，１}，Ｑｚ_{（ｎ／ｋ）−２，２}の量子状態をそれぞれ｜０＞にする逆演算過程と、
逆演算過程による処理の後、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋに対してNOT演算を施す処理を０≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第２のNOT演算過程と、
をさらに実行することを特徴とする量子加算演算方法。
請求項１又は４に記載の量子加算演算方法であって、
量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋと量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと補助量子ビットＱｚ_ｉ，１とに対する上記HIGHBIT演算は、
量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、補助量子ビットＱｚ_ｉ，１を目標ビットとするToffoli演算を行う過程と、
ｋ≧３である場合にのみ行われる、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を第１量子ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を第２量子ビットとし、補助量子ビットＱｚ_ｉ，１を第３量子ビットとしたMAJ演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ}，Ｑｙ_{ｉ・ｋ＋ｗ}を制御ビットとし、量子ビットＱｘ_ｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝１から１ずつ増加させてｗ＝ｋ−２まで実行する過程と、
量子ビットＱｘ_{（ｉ＋１）・ｋ−１}を第１量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を第２量子ビットとし、補助量子ビットＱｚ_ｉ，１を第３量子ビットとしたMAJ演算を実行する過程と、
ｋ≧３である場合にのみ行われる、量子ビットＱｘ_ｉ・ｋを制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｘ_ｉ・ｋを制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ−１}，Ｑｙ_{ｉ・ｋ＋ｗ−１}を制御ビットとし、量子ビットＱｘ_ｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−１から１ずつ減少させてｗ＝２まで実行する過程と、
量子ビットＱｙ_ｉ・ｋにNOT演算を施す過程と、
ｋ≧３である場合にのみ行われる、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたToffoli演算と、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたToffoli演算とを、それぞれ、２≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、
量子ビットＱｙ_ｉ・ｋにNOT演算を施す過程と、
量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋１}を目標ビットとしたToffoli演算と、量子ビットＱｘ_ｉ・ｋ，Ｑｙ_ｉ・ｋを制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋１}を目標ビットとしたToffoli演算とを、それぞれ実行する過程と、を実行する演算であり、
上記MAJ演算は、
第３量子ビットを制御ビットとし、第２量子ビットを目標ビットとしたCNOT演算を行う第１過程と、
第３量子ビットを制御ビットとし、第１量子ビットを目標ビットとしたCNOT演算を行う第２過程と、
上記第１過程及び上記第２過程の後に行われる、第１量子ビット及び第２量子ビットを制御ビットとし、第３量子ビットを目標ビットとしたToffoli演算を行うMAJ第３過程と、を実行する演算である、
ことを特徴とする量子加算演算方法。
請求項１から４の何れかに記載の量子加算演算方法であって、
量子ビットＱｘ_ｋ−１，…，Ｑｘ_０と量子ビットＱｙ_ｋ−１，…，Ｑｙ_０とに対する上記SUM演算は、
量子ビットＱｙ_ｋ−１を制御ビットとし、量子ビットＱｘ_ｗを目標ビットとしたCNOT演算と、量子ビットＱｙ_ｋ−１を制御ビットとし、量子ビットＱｙ_ｗを目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する過程と、
量子ビットＱｘ_ｗを第１量子ビットとし、量子ビットＱｙ_ｗを第２量子ビットとし、量子ビットＱｙ_ｋ−１を第３量子ビットとしたMAJ演算を、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−２まで実行する過程と、
量子ビットＱｘ_ｗを制御ビットとし、量子ビットＱｙ_ｗを目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、を実行する演算であり、
量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋと量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと補助量子ビットＱｚ_{ｉ−１，１}とに対する上記繰上げSUM演算〔１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕は、
量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する過程と、
補助量子ビットＱｚ_{ｉ−１，１}を制御ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を目標ビットとしてCNOT演算を実行する過程と、
ｋ≧３である場合にのみ行われる、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を第１量子ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を第２量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を第３量子ビットとしたMAJ演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ}，Ｑｙ_{ｉ・ｋ＋ｗ}を制御ビットとし、補助量子ビットＱｚ_{ｉ−１，１}を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−３まで実行する過程と、
量子ビットＱｘ_{（ｉ＋１）・ｋ−２}を第１量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−２}を第２量子ビットとし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}を第３量子ビットとしたMAJ演算を実行する過程と、
ｋ≧３である場合にのみ行われる、補助量子ビットＱｚ_{ｉ−１，１}を制御ビットとし、量子ビットＱｘ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算と、量子ビットＱｘ_{ｉ・ｋ＋ｗ−１}，Ｑｙ_{ｉ・ｋ＋ｗ−１}を制御ビットとし、補助量子ビットＱｚ_{ｉ−１，１}を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−２から１ずつ減少させてｗ＝１まで実行する過程と、
補助量子ビットＱｚ_{ｉ−１，１}を制御ビットとし、量子ビットＱｘ_ｉ・ｋを目標ビットとしたCNOT演算を実行する過程と、
量子ビットＱｘ_{ｉ・ｋ＋ｗ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ＋ｗ}を目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、を実行する演算を実行する過程と、を実行する演算であり、
上記MAJ演算は、
第３量子ビットを制御ビットとし、第２量子ビットを目標ビットとしたCNOT演算を行う第１過程と、
第３量子ビットを制御ビットとし、第１量子ビットを目標ビットとしたCNOT演算を行う第２過程と、
上記第１過程及び上記第２過程の後に行われる、第１量子ビット及び第２量子ビットを制御ビットとし、第３量子ビットを目標ビットとしたToffoli演算を行うMAJ第３過程と、を実行する演算である、
ことを特徴とする量子加算演算方法。
請求項１から６の何れかに記載の量子加算演算方法であって、
定数ｋは、ｌｏｇ_２（ｌｏｇ_２ｎ）以下の最大の整数である、
ことを特徴とする量子加算演算方法。
２つの２進数ａ＝ａ_ｎ−１…ａ_０〔ａ_ｐ∈｛０，１｝，ｐ∈｛０，…，ｎ−１｝，ｎ≧４〕及びｂ＝ｂ_ｎ−１…ｂ_０〔ｂ_ｐ∈｛０，１｝〕に対し、ａ＋ｂ＝ｓ_ｎ…ｓ_０〔ｓ_ｑ∈｛０，１｝，ｑ∈｛０，…，ｎ｝〕を算出する量子加算演算装置であって、
初期量子状態がそれぞれ｜ａ_０＞，…，｜ａ_ｎ−１＞であるｎ個の量子ビットＱｘ_０，…，Ｑｘ_ｎ−１と、
初期量子状態がそれぞれ｜ｂ_０＞，…，｜ｂ_ｎ−１＞であるｎ個の量子ビットＱｙ_０，…，Ｑｙ_ｎ−１と、
初期量子状態が｜０＞である１個の補助量子ビットＱｚ_０，１と、初期量子状態がそれぞれ｜０＞である２・｛（ｎ／ｋ）−１｝〔ｋはｎを割り切る２以上ｎ未満の整数の定数である〕個の補助量子ビットＱｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−１，１}，Ｑｚ_{（ｎ／ｋ）−１，２}と、
初期量子状態がそれぞれ｜０＞である

個〔Ｌはｎ／２^Ｌ−１以下の最大の整数をｎ／ｋとする整数である〕の補助量子ビットＱｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}と、
量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋと量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋとをｉ番目〔０≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕の加算処理ブロックＡ_ｉとし、当該加算処理ブロックＡ_ｉに属する初期量子状態の量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋ及び量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと、初期量子状態の補助量子ビットＱｚ_ｉ，１とに対してHIGHBIT演算を施し、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋの量子状態をそれぞれ｜ａ_{（ｉ＋１）・ｋ−１}＞，…，｜ａ_ｉ・ｋ＞とし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋの量子状態をそれぞれ｜ｂ_{（ｉ＋１）・ｋ−１}＞，…，｜ｂ_ｉ・ｋ＞とし、補助量子ビットＱｚ_ｉ，１の量子状態を｜ｃ_ｉ＞〔ｃ_ｉは、２つの２進数ａ_{（ｉ＋１）・ｋ−１}…ａ_ｉ・ｋとｂ_{（ｉ＋１）・ｋ−１}…ｂ_ｉ・ｋの和を２進表記した場合の最上位ビット値〕とする処理を、各加算処理ブロックＡ_ｉについてそれぞれ実行するHIGHBIT演算部と、
補助量子ビットＱｚ_０，１，Ｑｚ_１，１，Ｑｚ_１，２，Ｑｚ_２，１，Ｑｚ_２，２，…，Ｑｚ_{（ｎ／ｋ）−１，１}，Ｑｚ_{（ｎ／ｋ）−１，２}，Ｑｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}を用い、補助量子ビットＱｚ_ｗ，１の量子状態を｜ｄ_ｗ＞〔ｄ_ｗ∈｛０，１｝は、加算処理ブロックＡ_ｗから加算処理ブロックＡ_ｗ＋１への繰上げ値〕とする処理を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに補助量子ビットＱｚ_{（ｎ／ｋ）−１，１}の量子状態を｜ｓ_ｎ＞とする処理を実行する繰上げ値演算部と、
加算処理ブロックＡ_０に属する量子ビットＱｘ_ｋ−１，…，Ｑｘ_０と量子ビットＱｙ_ｋ−１，…，Ｑｙ_０とに対してSUM演算を施し、量子ビットＱｘ_ｋ−１，…，Ｑｘ_０の量子状態をそれぞれ｜ａ_ｋ−１＞，…，｜ａ_０＞とし、量子ビットＱｙ_ｋ−１，…，Ｑｙ_０の量子状態をそれぞれ｜ｓ_ｋ−１＞，…，｜ｓ_０＞とする第１のSUM演算部と、
加算処理ブロックＡ_ｉに属する量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋ及び量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと、補助量子ビットＱｚ_{ｉ−１，１}とに対して繰上げSUM演算を施し、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋの量子状態をそれぞれ｜ａ_{（ｉ＋１）・ｋ−１}＞，…，｜ａ_ｉ・ｋ＞とし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋの量子状態をそれぞれ｜ｓ_{（ｉ＋１）・ｋ−１}＞，…，｜ｓ_ｉ・ｋ＞とし、補助量子ビットＱｚ_{ｉ−１，１}の量子状態を維持する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のSUM演算部と、
を有することを特徴とする量子加算演算装置。
請求項８に記載の量子加算演算装置であって、
上記繰上げ値演算部は、
量子ビットＱｘ_{ｉ・ｋ+ｊ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ+ｊ}を目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のCNOT演算部と、
上記第１のCNOT演算部による処理がなされたｋ個の量子ビットＱｙ_ｉ・ｋ，…，Ｑｙ_{ｉ・ｋ＋ｋ−１}を制御ビットとし、補助量子ビットＱｚ_ｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のk-Toffoli演算部と、
第１のk-Toffoli演算部によるk-Toffoli演算が施された補助量子ビットＱｚ_ｉ，２を補助量子ビットＱｐ_Ｌ−１（ｉ）と表現した場合における、補助量子ビットＱｐ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｚ_{（ｎ／ｋ）}，…，Ｑｚ_{（ｎ／ｋ）＋ｍ−１}うちの１つの補助量子ビットである補助量子ビットＱｐ_ｔ（ｉ）を目標ビットとしたToffoli演算を、目標ビットを重複させることなく、ｉ＝１からｉを１ずつ増加させながら

まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら

まで実行する第１のToffoli演算部と、
HIGHBIT演算部による処理が施された補助量子ビットＱｚ_ｉ，１を補助量子ビットＱｇ_Ｌ−１（ｉ）と表現した場合における、補助量子ビットＱｇ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｇ_ｔ−１（２ｉ＋１）を目標ビットとしたToffoli演算〔当該Toffoli演算後の補助量子ビットＱｇ_ｔ−１（２ｉ＋１）を補助量子ビットＱｇ_ｔ（ｉ）と表現〕を、ｉ＝０からｉを１ずつ増加させながら

まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら

まで実行する第２のToffoli演算部と、
ｕ＝２^ｔ・ｉ／ｋ−１とした場合における補助量子ビットＱｚ_ｕ，１，Ｑｐ_ｔ−１（２ｉ）を制御ビットとし、補助量子ビットＱｇ_ｔ−１（２ｉ）を目標ビットとしたToffoli演算を、ｉ＝１からｉを１ずつ増加させながら

まで実行する処理を、

からｔを１ずつ減少させながらｔ＝Ｌまで実行する第３のToffoli演算部と、
補助量子ビットＱｐ_ｔ−１（２ｉ），Ｑｐ_ｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｐ_ｔ（ｉ）を目標ビットとしたToffoli演算を、

からｉを１ずつ減少させながらｉ＝１まで実行する処理を、

からｔを１ずつ減少させながらｔ＝Ｌまで実行する第４のToffoli演算部と、
第４のToffoli演算部による処理の後、ｋ個の量子ビットＱｙ_ｉ・ｋ，…，Ｑｙ_{ｉ・ｋ＋ｋ−１}を制御ビットとし、補助量子ビットＱｚ_ｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のk-Toffoli演算部と、
第２のk-Toffoli演算部による処理の後、量子ビットＱｘ_{ｉ・ｋ+ｊ}を制御ビットとし、量子ビットＱｙ_{ｉ・ｋ+ｊ}を目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のCNOT演算部と、
HIGHBIT演算部による処理の後、加算処理ブロックＡ_０に属する量子ビットＱｘ_ｋ−１，…，Ｑｘ_０及び量子ビットＱｙ_ｋ−１，…，Ｑｙ_０とに対してSUM演算を施し、量子ビットＱｘ_ｋ−１，…，Ｑｘ_０の量子状態をそれぞれ｜ａ_ｋ−１＞，…，｜ａ_０＞とし、量子ビットＱｙ_ｋ−１，…，Ｑｙ_０の量子状態をそれぞれ｜ｓ_ｋ−１＞，…，｜ｓ_０＞とする第１のSUM演算部と、
第２のCNOT演算部による処理の後、加算処理ブロックＡ_ｉに属する量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋ及び量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋと、補助量子ビットＱｚ_{ｉ−１，１}とに対してSUM演算を施し、量子ビットＱｘ_{（ｉ＋１）・ｋ−１}，…，Ｑｘ_ｉ・ｋの量子状態をそれぞれ｜ａ_{（ｉ＋１）・ｋ−１}＞，…，｜ａ_ｉ・ｋ＞とし、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋの量子状態をそれぞれ｜ｓ_{（ｉ＋１）・ｋ−１}＞，…，｜ｓ_ｉ・ｋ＞とし、補助量子ビットＱｚ_{ｉ−１，１}の量子状態を維持する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のSUM演算部と、
を有することを特徴とする量子加算演算装置。
請求項８に記載の量子加算演算装置であって、
第１のSUM演算部及び第２のSUM演算部による処理の後、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋに対してNOT演算を施す処理を0≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第１のNOT演算部と、
上記繰上げ値演算部による補助量子ビットＱｚ_ｗ，１の量子状態を｜ｄ_ｗ＞とする処理の逆演算を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに、量子ビットＱｘ_{（ｗ＋１）・ｋ−１}，…，Ｑｘ_ｗ・ｋと量子ビットＱｙ_{（ｗ＋１）・ｋ−１}，…，Ｑｙ_ｗ・ｋと補助量子ビットＱｚ_ｗ，１とに対する上記HIGHBIT演算の逆演算であるHIGHBIT-REV演算を０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行する逆演算部と、
逆演算部による処理の後、量子ビットＱｙ_{（ｉ＋１）・ｋ−１}，…，Ｑｙ_ｉ・ｋに対してNOT演算を施す処理を０≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第２のNOT演算部と、
をさらに実行することを特徴とする量子加算演算装置。