(57)【特許請求の範囲】
【請求項１】
ｎが２以上の整数であり、ｗが１≦ｗ≦ｎを満たす整数であり、ｘｗ∈｛０，１｝であり、｜ｘ｜＝ｘ１＋…＋ｘｎであり、ｃｅｉｌ（・）が（・）の天井関数であり、ｍ＝ｃｅｉｌ（ｌｏｇ２（ｎ＋１））であり、ｋが１≦ｋ≦ｍを満たす整数であり、
初期状態が｜ｘ１〉，…，｜ｘｎ〉であるｎ個の入力量子ビットＸ１，…，Ｘｎ、初期状態が｜ｙ〉である１個の出力量子ビットＹ、初期化補助量子ビット、および未初期化補助量子ビットを用い、
【数３２】
0006445487.tif 000033
で表される状態｜φｋ〉を生成する第１量子演算部と、
前記状態｜φ１〉…｜φｍ〉からφ１，…，φｍの論理和を表す状態を生成する第２量子演算部と、
を有する論理和演算装置。
【請求項２】
請求項１の論理和演算装置であって、
ｎが３以上の整数である、論理和演算装置。
【請求項３】
請求項１または２の論理和演算装置であって、
Ｉ（１），…，Ｉ（ｍ）がｍ個の前記初期化補助量子ビットであり、ｎｍ（ｍ＋３）／２個の前記未初期化補助量子ビットからなる集合が部分集合Ａ（１），…，Ａ（ｍ），Ｂ（１），…，Ｂ（ｍ）からなり、前記部分集合Ａ（ｋ）がｎ個の前記未初期化補助量子ビットＡ１（ｋ），…，Ａｎ（ｋ）からなり、前記部分集合Ｂ（ｋ）がｋ個の部分集合Ｂ（ｋ，１），…，Ｂ（ｋ，ｋ）からなり、ｒは１≦ｒ≦ｋを満たす整数であり、前記部分集合Ｂ（ｋ，ｒ）がｎ個の前記未初期化補助量子ビットＢ１（ｋ，ｒ），…，Ｂｎ（ｋ，ｒ）からなり、
前記第１量子演算部は、第１から第１０演算部を含み、ｍ個のステージＳ（１），…，Ｓ（ｍ）を実行し、ｓが１≦ｓ≦ｍを満たす整数であり、ｓ’が２≦ｓ’≦ｍを満たす整数であり、前記ステージＳ（ｓ’）は前記ステージＳ（ｓ’−１）の後に実行され、
前記初期化補助量子ビットＩ（１），…，Ｉ（ｍ）の初期状態が｜０〉，…，｜０〉であり、前記未初期化補助量子ビットＡ１（ｋ），…，Ａｎ（ｋ）の初期状態が｜ａ１（ｋ）〉，…，｜ａｎ（ｋ）〉であり、前記未初期化補助量子ビットＢ１（ｋ，ｒ），…，Ｂｎ（ｋ，ｒ）の初期状態が｜ｂ１（ｋ，ｒ）〉，…，｜ｂｎ（ｋ，ｒ）〉であり、
前記ステージＳ（ｓ）では、
前記第１演算部が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））にアダマール演算を適用し、
前記第２演算部が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））を制御ビットとし、Ｂ１（ｋ（ｓ），ｓ），…，Ｂｎ（ｋ（ｓ），ｓ）を標的ビットとした(n+1)-fanout演算を行い、
前記第３演算部が、ｓ≧２のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を標的ビットとしたs-fanout演算を行い、
前記第４演算部が、
ｓ＝１のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算の逆演算を行い、
ｓ≧２のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））およびＢｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算の逆演算を行い、
前記第５演算部が、１≦ｊ≦ｎについて、Ｘｊを制御ビットとし、Ａｊ（ｓ），Ａｊ（ｓ＋１），…，Ａｊ（ｍ）を標的ビットとした(m-s+2)-fanout演算を行い、
前記第６演算部が、
ｓ＝１のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算を行い、
ｓ≧２のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））およびＢｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算を行い、
前記第７演算部が、１≦ｊ≦ｎについて、Ｘｊを制御ビットとし、Ａｊ（ｓ），Ａｊ（ｓ＋１），…，Ａｊ（ｍ）を標的ビットとした(m-s+2)-fanout演算を行い、
前記第８演算部が、ｓ≧２のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を標的ビットとしたs-fanout演算を行い、
前記第９演算部が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））を制御ビットとし、Ｂ１（ｋ（ｓ），ｓ），…，Ｂｎ（ｋ（ｓ），ｓ）を標的ビットとした(n+1)-fanout演算を行い、
前記第１０演算部が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））にアダマール演算を適用する、論理和演算装置。
【請求項４】
請求項３の論理和演算装置であって、
前記第２量子演算部は、第１１から１４演算部を含み、
前記第１１演算部は、１≦ｋ≦ｍについて、Ｉ（ｋ）にNOT演算を適用し、
前記第１２演算部は、Ｉ（１），…，Ｉ（ｍ）を制御ビットとし、Ｙを標的ビットとした(m+1)-Toffoli演算を適用し、
前記第１３演算部は、１≦ｋ≦ｍについてのＩ（ｋ）およびＹにNOT演算を適用し、
前記第１４演算部は、逆演算ＲＳ（ｍ），…，ＲＳ（１）を行い、
前記逆演算ＲＳ（ｓ）は前記ステージＳ（ｓ）の逆演算であり、前記逆演算ＲＳ（ｓ’−１）は前記逆演算ＲＳ（ｓ’）の後に実行される、論理和演算装置。
【請求項５】
ｎが２以上の整数であり、ｗが１≦ｗ≦ｎを満たす整数であり、ｘｗ∈｛０，１｝であり、｜ｘ｜＝ｘ１＋…＋ｘｎであり、ｃｅｉｌ（・）が（・）の天井関数であり、ｍ＝ｃｅｉｌ（ｌｏｇ２（ｎ＋１））であり、ｋが１≦ｋ≦ｍを満たす整数であり、
第１量子演算部が、初期状態が｜ｘ１〉，…，｜ｘｎ〉であるｎ個の入力量子ビットＸ１，…，Ｘｎ、初期状態が｜ｙ〉である１個の出力量子ビットＹ、初期化補助量子ビット、および未初期化補助量子ビットを用い、
【数３３】
0006445487.tif 000034
で表される状態｜φｋ〉を生成する第１量子演算ステップと、
第２量子演算部が、前記状態｜φ１〉…｜φｍ〉からφ１，…，φｍの論理和を表す状態を生成する第２量子演算ステップと、
を有する論理和演算方法。
【請求項６】
請求項５の論理和演算方法であって、
ｎが３以上の整数である、論理和演算方法。
【請求項７】
請求項５または６の論理和演算方法であって、
Ｉ（１），…，Ｉ（ｍ）がｍ個の前記初期化補助量子ビットであり、ｎｍ（ｍ＋３）／２個の前記未初期化補助量子ビットからなる集合が部分集合Ａ（１），…，Ａ（ｍ），Ｂ（１），…，Ｂ（ｍ）からなり、前記部分集合Ａ（ｋ）がｎ個の前記未初期化補助量子ビットＡ１（ｋ），…，Ａｎ（ｋ）からなり、前記部分集合Ｂ（ｋ）がｋ個の部分集合Ｂ（ｋ，１），…，Ｂ（ｋ，ｋ）からなり、ｒ＝１，…，ｋであり、前記部分集合Ｂ（ｋ，ｒ）がｎ個の前記未初期化補助量子ビットＢ１（ｋ，ｒ），…，Ｂｎ（ｋ，ｒ）からなり、
前記第１量子演算部は、第１から第１０演算部を含み、ｍ個のステージＳ（１），…，Ｓ（ｍ）を実行し、ｓが１≦ｓ≦ｍを満たす整数であり、ｓ’が２≦ｓ’≦ｍを満たす整数であり、前記ステージＳ（ｓ’）は前記ステージＳ（ｓ’−１）の後に実行され、
前記初期化補助量子ビットＩ（１），…，Ｉ（ｍ）の初期状態が｜０〉，…，｜０〉であり、前記未初期化補助量子ビットＡ１（ｋ），…，Ａｎ（ｋ）の初期状態が｜ａ１（ｋ）〉，…，｜ａｎ（ｋ）〉であり、前記未初期化補助量子ビットＢ１（ｋ，ｒ），…，Ｂｎ（ｋ，ｒ）の初期状態が｜ｂ１（ｋ，ｒ）〉，…，｜ｂｎ（ｋ，ｒ）〉であり、
前記ステージＳ（ｓ）では、
前記第１演算部が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））にアダマール演算を適用し、
前記第２演算部が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））を制御ビットとし、Ｂ１（ｋ（ｓ），ｓ），…，Ｂｎ（ｋ（ｓ），ｓ）を標的ビットとした(n+1)-fanout演算を行い、
前記第３演算部が、ｓ≧２のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を標的ビットとしたs-fanout演算を行い、
前記第４演算部が、
ｓ＝１のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算の逆演算を行い、
ｓ≧２のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））およびＢｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算の逆演算を行い、
前記第５演算部が、１≦ｊ≦ｎについて、Ｘｊを制御ビットとし、Ａｊ（ｓ），Ａｊ（ｓ＋１），…，Ａｊ（ｍ）を標的ビットとした(m-s+2)-fanout演算を行い、
前記第６演算部が、
ｓ＝１のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算を行い、
ｓ≧２のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））およびＢｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算を行い、
前記第７演算部が、１≦ｊ≦ｎについて、Ｘｊを制御ビットとし、Ａｊ（ｓ），Ａｊ（ｓ＋１），…，Ａｊ（ｍ）を標的ビットとした(m-s+2)-fanout演算を行い、
前記第８演算部が、ｓ≧２のときに、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を標的ビットとしたs-fanout演算を行い、
前記第９演算部が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））を制御ビットとし、Ｂ１（ｋ（ｓ），ｓ），…，Ｂｎ（ｋ（ｓ），ｓ）を標的ビットとした(n+1)-fanout演算を行い、
前記第１０演算部が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））にアダマール演算を適用する、論理和演算方法。
【請求項８】
請求項７の論理和演算方法であって、
前記第２量子演算部は、第１１から１４演算部を含み、
前記第１１演算部は、１≦ｋ≦ｍについて、Ｉ（ｋ）にNOT演算を適用し、
前記第１２演算部は、Ｉ（１），…，Ｉ（ｍ）を制御ビットとし、Ｙを標的ビットとした(m+1)-Toffoli演算を適用し、
前記第１３演算部は、１≦ｋ≦ｍについてのＩ（ｋ）およびＹにNOT演算を適用し、
前記第１４演算部は、逆演算ＲＳ（ｍ），…，ＲＳ（１）を行い、
前記逆演算ＲＳ（ｓ）は前記ステージＳ（ｓ）の逆演算であり、前記逆演算ＲＳ（ｓ’−１）は前記逆演算ＲＳ（ｓ’）の後に実行される、論理和演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子計算技術に関し、特に論理和関数を計算する技術に関する。
【背景技術】
【０００２】
入力桁数をｎとするとき、初期化補助量子ビットを持たず、１個の未初期化補助量子ビットを持ち、Ｏ（ｎ）個の計算ステップで論理和関数ｘ１∨…∨ｘｎを計算する量子回路の構成方法が知られている（例えば、非特許文献１等参照）。図１７はｎ＝７としたときの例であり、状態（量子状態）｜ｘ１〉，…，｜ｘｎ〉の入力量子ビットおよび状態｜ｙ〉の出力量子ビットの他に、任意の状態｜ａ１〉の未初期化補助量子ビットが用いられる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, “Elementary gates for quantum computation,” Phys. Rev. A, Vol. 52 No. 5, pp. 3457-3467, 1995.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
計算ステップの個数が多いほど量子回路の計算時間が長くなる。また、計算ステップの個数が多いほど物理的実現性が低下する。従って、物理的実現性の高さと短い計算時間を同時に実現するためには、計算ステップの個数を小さくするほうがよい。従来方法ではＯ（ｎ）個の計算ステップで論理和関数を行っており、物理的実現性と計算時間の長さに問題がある。
【０００５】
本発明の課題は、従来よりも少ない計算ステップで論理和関数を計算することである。
【課題を解決するための手段】
【０００６】
ｘ１，…，ｘｎの論理和を計算するために、初期状態が｜ｘ１〉，…，｜ｘｎ〉であるｎ個の入力量子ビットＸ１，…，Ｘｎ、初期状態が｜ｙ〉である１個の出力量子ビットＹ、初期化補助量子ビット、および未初期化補助量子ビットを用い、
【数１】
0006445487.tif 000002
で表される状態｜φｋ〉を生成し、当該状態｜φ１〉…｜φｍ〉からφ１，…，φｍの論理和を表す状態を生成する。ただし、ｎが２以上の整数であり、ｗが１≦ｗ≦ｎを満たす整数であり、ｘｗ∈｛０，１｝であり、｜ｘ｜＝ｘ１＋…＋ｘｎであり、ｃｅｉｌ（・）が（・）の天井関数であり、ｍ＝ｃｅｉｌ（ｌｏｇ２（ｎ＋１））であり、ｋが１≦ｋ≦ｍを満たす整数である。
【発明の効果】
【０００７】
初期化補助量子ビットおよび未初期化補助量子ビットを用い、ｘ１，…，ｘｎの論理和の計算をφ１，…，φｍの論理和の計算に帰着させることで、従来よりも少ない計算ステップで論理和関数を計算できる。
【図面の簡単な説明】
【０００８】
【図１】図１は実施形態の論理和演算装置の機能構成を例示したブロック図である。
【図２】図２Ａおよび図２Ｂは補助量子ビットの構成を例示したブロック図である。
【図３】図３は本形態の論理和演算を行う量子回路の例示である。
【図４】図４は本形態の論理和演算を行う量子回路の例示である。
【図５】図５は本形態の論理和演算を行う量子回路の例示である。
【図６】図６ＡはNOT演算を表し、図６ＢはCNOT演算を表し、図６Ｃはアダマール演算を表し、図６Ｄはz-Toffoli演算を表す。
【図７】図８は5-Toffoli演算を行う量子回路である。
【図８】図７は3-Toffoli演算を行う量子回路である。
【図９】図９Ａは制御Ｖ演算を表し、図９Ｂは制御Ｖ演算の逆演算を表す。
【図１０】図１０はp-fanout演算を表す。
【図１１】図１１は9-fanout演算を行う量子回路の一例である。
【図１２】図１２Ａは(p,q)−位相シフト演算を表し、図１２Ｂは(p,q)−位相シフト演算の逆演算を表す。
【図１３】図１３は(9,q)−位相シフト演算を行う量子回路の一例である。
【図１４】図１４Ａは本形態の処理の全体を説明するためのフローチャートである。図１４Ｂは図１４ＡのステップＳ１の詳細を説明するためのフローチャートである。
【図１５】図１５はステップＳ（ｓ）の詳細を説明するためのフローチャートである。
【図１６】図１６はステップＳ２の詳細を説明するためのフローチャートである。
【図１７】図１７は論理和関数を計算する従来の量子回路の例示である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［定義］
まず実施形態で使用する用語を定義する。
論理和関数とは、長さ１以上の全ての有限ビット列からなる集合を定義域とし、｛０，１｝を値域とする関数であり、入力ビット列ｘがｎ個のビットｘ１，…，ｘｎからなる列のとき、
【数２】
0006445487.tif 000003
を出力する関数を意味する。ただし、ｎが１以上の整数であり、１≦ｗ≦ｎを満たす整数ｗに対し、ｘｗは０または１（ｘｗ∈｛０，１｝）であり、｜ｘ｜＝ｘ１＋…＋ｘｎである。例えばｎは２以上の整数であり、特に本形態ではｎが３以上の整数のときに効果が高い。以下では、論理積関数も扱うが、この関数は入力ビット列ｘがｎ個のビットｘ１，…，ｘｎからなる列のとき、
【数３】
0006445487.tif 000004
を出力する。
【００１０】
【数４】
0006445487.tif 000005
は２を法とする加算（排他的論理和）を表し、記載表記の制約上、本形態ではこれを（＋）と表記することもある。任意のα∈｛０，１｝に対し、α（＋）１（αにNOT演算を適用した値）を
【数５】
0006445487.tif 000006
と記述する。このとき
【数６】
0006445487.tif 000007
という関係が成り立つことは容易に確認できる。
【００１１】
入力桁数をｎとするとき、論理和関数を計算する量子回路とは，ｎ個の入力量子ビットと１個の出力量子ビットを持ち、任意のｘ１，…，ｘｎ，ｙ∈｛０，１｝に対し、入力量子ビットの初期状態を｜ｘ１〉…｜ｘｎ〉、出力量子ビットの初期状態を｜ｙ〉とすると、その量子回路を構成する基本演算を全て適用することにより、入力量子ビットの状態は変化せず、出力量子ビットの状態がｙ（＋）ｘ１∨…∨ｘｎ（２を法とした、ｙにｘ１∨・・・∨ｘｎを加算した値の剰余）となるような量子回路のことである。論理積関数を計算する量子回路も同様に定義される。すなわち、論理積関数を計算する量子回路とは，ｎ個の入力量子ビットと１個の出力量子ビットを持ち、任意のｘ１，…，ｘｎ，ｙ∈｛０，１｝に対し、入力量子ビットの初期状態を｜ｘ１〉…｜ｘｎ〉、出力量子ビットの初期状態を｜ｙ〉とすると、その量子回路を構成する基本演算を全て適用することにより、入力量子ビットの状態は変化せず、出力量子ビットの状態が｜ｙ（＋）ｘ１∧…∧ｘｎ〉となるような量子回路のことである。なお、「状態」とは「量子状態」と同義であり、「初期状態」とは「初期量子状態」と同義である。
【００１２】
量子回路は入力量子ビットと出力量子ビット以外に、補助量子ビットを持つことができ、補助量子ビットは、初期化補助量子ビットと未初期化補助量子ビットに分類される。初期化補助量子ビットとは、初期状態が｜０〉と定められたものであり、未初期化補助量子ビットとは、初期状態が｜０〉と｜１〉のどちらでも許されるものである。論理和関数を計算する量子回路が、ｕ個の初期化補助量子ビットとｑ個の未初期化補助量子ビットを持つとき（ただし、ｕおよびｑは正整数）、初期化量子ビット全体の初期状態は｜０〉…｜０〉であるが、未初期化補助量子ビット全体の初期状態は、任意のａ１，…，ａｑ∈｛０，１｝に対し、｜ａ１〉…｜ａｑ〉であるとし、その量子回路を構成する全ての基本演算を適用した後で、これらの状態は変化しないものとする。すなわち、計算の途中で補助量子ビットはどのような状態になっても良いが、計算終了後には初期状態に戻らなければならないということを要請する。
【００１３】
量子回路において、１個の計算ステップとは、その量子回路の中で並列に実行可能な基本演算のグループのことである。ただし、異なる量子ビット上の基本演算（NOT演算およびアダマール演算などの１量子ビット演算、並びにCNOT演算などの２量子ビット演算）は並列に実行可能であるとする。従って、λ個の計算ステップで論理和関数を計算する量子回路において、その量子回路に含まれる基本演算はλ個のグループに分類され、各グループにおいて、その中の全ての演算は並列に実行可能である。
【００１４】
図６Ａに示すように、NOT演算Ｘは、任意の状態｜χ〉にある１個の量子ビットに対する演算であり、この量子ビットの状態を｜χ（＋）１〉にする（ただし、χ∈｛０，１｝，χ（＋）１＝χ＋１ ｍｏｄ ２）。
【００１５】
図６Ｂに示すように、CNOT演算は、任意の状態｜χ〉にある１個の制御ビットと任意の状態｜γ〉にある１個の標的ビットとに対する演算である。CNOT演算後の当該制御ビットの状態は｜χ〉であり、当該標的ビットの状態は｜χ（＋）γ〉である（ただし、χ，γ∈｛０，１｝，χ（＋）γ＝χ＋γ ｍｏｄ ２）。
【００１６】
図６Ｃに示すように、アダマール（Hadamard）演算（変換）は、任意の状態｜χ〉にある１個の量子ビットに対する演算であり、この量子ビットの状態を
【数７】
0006445487.tif 000008
にする（ただし、χ∈｛０，１｝）。
【００１７】
図６Ｄに示すように、z-Toffoli演算は、任意の状態｜χ１〉，…，｜χｚ−１〉にあるｚ−１個の制御ビット（ただし、ｚは３以上の整数）、および任意の状態｜γ〉にある１個の標的ビットに対する演算である。z-Toffoli演算後の当該ｚ−１個の制御ビットの状態はそれぞれ｜χ１〉，…，｜χｚ−１〉であり、当該標的ビットの状態は｜γ（＋）χ１…χｚ−１〉である（ただし、χ１，…，χｚ−１，γ∈｛０，１｝である。χ１…χｚ−１はχ１，…，χｚ−１の積であり、χ１，…，χｚ−１の論理積を表す）。z-Toffoli演算は、入力桁数がｚ−1の論理積関数χ１∧…∧χｚ−１を計算する量子回路であることに注意する。z-Toffoli演算は３-Toffoli演算からなる量子回路によって計算できる。例えば、５-Toffoli演算は図７に例示する３-Toffoli演算からなる量子回路によって計算できる。任意の状態｜χ１〉，…，｜χ４〉にある４個の制御ビット、任意の状態｜γ〉にある１個の標的ビット、および任意の状態｜ａ１〉，｜ａ２〉にある２個の未初期化補助量子ビットに対し、この量子回路を適用することで、５-Toffoli演算を行うことができる。この演算後の当該４個の制御ビットの状態はそれぞれ｜χ１〉，…，｜χ４〉であり、当該標的ビットの状態は｜γ（＋）χ１…χ４〉であり、当該２個の未初期化補助量子ビットの状態はそれぞれ｜ａ１〉，｜ａ２〉である。図８に例示するように、３-Toffoli演算は、CNOT演算、制御Ｖ演算および制御Ｖ演算の逆演算からなる量子回路によって計算できる。任意の状態｜χ１〉，｜χ２〉にある２個の制御ビット、任意の状態｜γ〉にある１個の標的ビットに対し、この量子回路を適用することで、３-Toffoli演算を行うことができる。この演算後の当該２個の制御ビットの状態はそれぞれ｜χ１〉，｜χ２〉であり、当該標的ビットの状態は｜γ（＋）χ１χ２〉である。
【００１８】
図９Ａに示すように、制御Ｖ演算は、任意の状態｜χ〉にある１個の制御ビットと任意の状態｜γ〉にある１個の標的ビットとに対する演算である（ただし、χ，γ∈｛０，１｝）。制御Ｖ演算後の当該制御ビットの状態は｜χ〉であり、当該標的ビットの状態は以下である。ただし、ｉは虚数単位を表す。
【数８】
0006445487.tif 000009
【００１９】
図９Ｂに示すように、制御Ｖの逆演算は、任意の状態｜χ〉にある１個の制御ビットと任意の状態｜γ〉にある１個の標的ビットとに対する演算である（ただし、χ，γ∈｛０，１｝）。制御Ｖ演算後の当該制御ビットの状態は｜χ〉であり、当該標的ビットの状態は以下である。
【数９】
0006445487.tif 000010
【００２０】
図１０に示すように、p-fanout演算は、任意の状態｜γ〉にある１個の制御ビット、および任意の状態｜χ１〉，…，｜χｐ−１〉にあるｐ−１個（ただし、ｐは２以上の整数）の標的ビットに対する演算である。p-fanout演算後の当該制御ビットの状態は｜γ〉であり、当該ｐ−１個の標的ビットの状態はそれぞれ｜χ１（＋）γ〉，…，｜χｐ−１（＋）γ〉である（ただし、γ，χ１，…，χｐ−１∈｛０，１｝）。
【００２１】
参考文献１（C. Moore, “Quantum circuits: fanout, parity, and counting,” arXiv:quant-ph/9903046, 1999.）で述べられている量子回路から、補助量子ビットを持たず、Ｏ（ｌｏｇｐ）個の計算ステップでp-fanout演算を実行する量子回路は容易に構成できる。一例として、ｐ＝２κ＋１のとき（ただし、κは１以上の整数）のp-fanout演算を実行する量子回路を述べる（なお、κ＝０のとき、p-fanout演算はCNOT演算であるから、１個のCNOT演算だけからなる量子回路で実行できる）。次のような量子ビットを用意する。
・１個の制御ビットΓ
・ｐ−１個の標的ビットΧ１，…，Χｐ−１
Γの初期状態は｜γ〉であり、Χ１，…，Χｐ−１の初期状態はそれぞれ、｜χ１〉，…，｜χｐ−１〉である。ただし、γ，χ１，…，χｐ−１∈｛０，１｝である。この初期状態｜γ〉｜χ１〉，…，｜χｐ−１〉を｜γ〉｜χ１（＋）γ〉，…，｜χｐ−１（＋）γ〉に変換するp-fanout演算を行う量子回路を示す。この量子回路はCNOT演算だけから構成される。この量子回路による処理は以下のようになる。
【００２２】
＜ステップI＞量子回路は、Ｌ＝１，２，３，…，κについて１からκまで昇順に、次の処理を実行する。
【数１０】
0006445487.tif 000011
を制御ビットとし、
【数１１】
0006445487.tif 000012
を標的ビットとしたCNOT演算を適用する。ただし、ｊは０≦ｊ≦２κ−Ｌ−１を満たす整数であり、これら２κ−Ｌ個のCNOT演算は並列に適用される。
＜ステップII＞次に量子回路はΓ制御ビットとし、Χ１を標的ビットとしたCNOT演算を適用する。
＜ステップIII＞次に量子回路はステップIの逆演算を適用する。すなわち量子回路は、Ｌ＝κ，κ−１，κ−２，…，１についてκから１まで降順に、次の処理を実行する。
【数１２】
0006445487.tif 000013
を制御ビットとし、
【数１３】
0006445487.tif 000014
を標的ビットとしたCNOT演算を適用する。ただし、ｊは０≦ｊ≦２κ−Ｌ−１を満たす整数であり、これら２κ−Ｌ個のCNOT演算は並列に適用される。
【００２３】
κ＝３の場合（9-fanout）の量子回路は図１１のようになる。
【００２４】
ｐがｐ＝２κ＋１で表すことができない場合、p-fanout演算を行う量子回路は次のように構成される。まず、ｐ＜ｐ’＝２κ＋１となる最小のｐ’に対し、ｐ＝ｐ’とした上述のステップI〜IIIを実行する量子回路を構成する。ただし、κは１以上の整数である。この量子回路は量子ビットΓ，Χ１，…，Χｐ’−１を持つ。次に、Χｐ，Χｐ＋１，…，Χｐ’−１のいずれかの量子ビットに適用されている演算をすべて削除する。これが求める量子回路である。例えば，ｐ＝８の場合、ｐ’＝９（κ＝３）となり、図１１の回路において，Χ８に適用されている２つのCNOT演算（最初のステップと最後のステップに含まれる）を削除したものが、8-fanout演算を実行する量子回路である。
【００２５】
以上のように、任意のｐに対し、p-fanout演算を実行する量子回路は補助量子ビットを持たない。ｐ’に対応するκはκ≦ｃｅｉｌ（ｌｏｇ２ ｐ）を満たすので、この量子回路の計算ステップの個数はＯ（ｌｏｇ２ ｐ）となる。
【００２６】
また図１２Ａに示すように、(p,q)−位相シフト演算は、任意の状態｜χ１〉，…，｜χｐ−１〉にあるｐ−１個の制御ビット、および任意の状態｜χｐ〉にある１個の標的ビットに対するｐ量子ビット演算である（ただし、χ１，…，χｐ−１，χｐ∈｛０，１｝、ｐは２以上の整数であり、ｑは１以上の整数である）。(p,q)−位相シフト演算後の当該ｐ−１個の制御ビットおよび１個の標的ビットの状態は
【数１４】
0006445487.tif 000015
である。
【００２７】
非特許文献１で述べられている量子回路から、補助量子ビットを持たず、Ｏ（ｐ）個の計算ステップで(p,q)−位相シフト演算を実行する量子回路は、１個の(2,q)−位相シフト演算、２個の(2,q+1)−位相シフト演算の逆演算、および２個の(p-1)-Toffoli演算から構成できることが分かる。例えば、ｐ＝９のときの(p,9)−位相シフト演算を実行する量子回路は図１３のようになる。この8-Toffoli演算は、図１７の量子回路の最初と最後の演算ステップのNOT演算をすべて取り除き、入力量子ビットの状態｜ｘ１〉，…，｜ｘ７〉を｜χ１〉，…，｜χ７〉に置換し、出力量子ビットの状態｜ｙ〉を｜χ９〉に置換し、未初期化補助量子ビットの状態｜ａ１〉を｜χ８〉に置換した量子回路によって計算できる。
【００２８】
図１２Ｂに示すように、(p,q)−位相シフトの逆演算は、任意の状態｜χ１〉，…，｜χｐ−１〉にあるｐ−１個の制御ビット、および任意の状態｜χｐ〉にある１個の標的ビットに対するｐ量子ビット演算である（ただし、χ１，…，χｐ−１，χｐ∈｛０，１｝、ｐは２以上の整数であり、ｑは１以上の整数である）。(p,q)−位相シフトの逆演算後の当該ｐ−１個の制御ビットおよび１個の標的ビットの状態は
【数１５】
0006445487.tif 000016
である。
【００２９】
［実施形態］
次に、図面を参照して実施形態の概要を説明する。
＜構成＞
図１および図２に例示するように、本形態の論理和演算装置１は、演算部１１０１〜１１１０を含む量子演算部１１、演算部１２１１〜１２１４を含む量子演算部１２、ｎ個の入力量子ビットＸ１，…，Ｘｎ、１個の出力量子ビットＹ、ｍ個の初期化補助量子ビットＩ（１），…，Ｉ（ｍ）、ｎｍ（ｍ＋３）／２個の未初期化補助量子ビットを有する。ｎは２以上の整数であるが、ｎが３以上の整数のときに計算ステップの削減効果が顕著である。ｍ＝ｃｅｉｌ（ｌｏｇ２（ｎ＋１））であり、ｃｅｉｌ（・）は（・）の天井関数を表す。未初期化補助量子ビットからなる集合は、部分集合Ａ（１），…，Ａ（ｍ），Ｂ（１），…，Ｂ（ｍ）からなる。部分集合Ａ（ｋ）はｎ個の未初期化補助量子ビットＡ１（ｋ），…，Ａｎ（ｋ）からなる（図２Ａ）。ただし、ｋは１≦ｋ≦ｍを満たす整数（ｋ＝１，…，ｍ）である。部分集合Ｂ（ｋ）はｋ個の部分集合Ｂ（ｋ，１），…，Ｂ（ｋ，ｋ）からなり、部分集合Ｂ（ｋ，ｒ）はｎ個の未初期化補助量子ビットＢ１（ｋ，ｒ），…，Ｂｎ（ｋ，ｒ）からなる（図２Ｂ）。ただし、ｒは１≦ｒ≦ｋを満たす整数（ｒ＝１，…，ｋ）である。すなわち部分集合Ｂ（ｋ）は、ｋｎ個の未初期化補助量子ビットＢ１（ｋ，ｒ），…，Ｂｎ（ｋ，ｒ）（ただし、１≦ｋ≦ｍ，１≦ｒ≦ｋ）からなる。
【００３０】
論理和演算装置１は周知の量子コンピュータを用いて実現できる。例えば、イオントラップ量子コンピュータを用いる場合、イオンの基底状態と励起状態を利用して量子ビットを実現し、イオンを直線上に並べて各演算を行う。アダマール演算を含む１量子ビットユニタリ演算は個々のイオンに狙いを定めたレーザービームによって実現され、２量子ビット演算であるCNOT演算も同様に実現される。一般の２量子ビット演算は、１量子ビット演算とCNOT演算を組み合わせて実現される。
【００３１】
＜処理＞
ｎ個のビットｘ１，…，ｘｎからなる入力ビット列ｘに前述の論理和関数（式（１））を適用し、論理和ｘ１∨…∨ｘｎを得る処理の概要を説明する。ただし、ｘｗ∈｛０，１｝であり、ｗは１≦ｗ≦ｎを満たす整数である。
【００３２】
図１４Ａに例示するように、まず量子演算部１１（第１量子演算部）が、初期状態が｜ｘ１〉，…，｜ｘｎ〉であるｎ個の入力量子ビットＸ１，…，Ｘｎ、初期状態が｜ｙ〉である１個の出力量子ビットＹ、初期化補助量子ビット、および未初期化補助量子ビットを用い、ｋ＝１，…，ｍについて
【数１６】
0006445487.tif 000017
で表される状態｜φｋ〉を生成する。ただし、｜ｘ｜＝ｘ１＋…＋ｘｎである（ステップＳ１）。
【００３３】
次に、量子演算部１２（第２量子演算部）が、状態｜φ１〉…｜φｍ〉からφ１，…，φｍの論理和を表す状態を生成する。言い換えると、状態｜φ１〉…｜φｍ〉に対する量子演算を行ってφ１，…，φｍの論理和を表す状態を生成する（ステップＳ２）。
【００３４】
ここで、ステップＳ１で得られる状態｜φ１〉…｜φｍ〉に対応するφ１，…，φｍの論理和φ１∨…∨φｍを表す状態は、ｘ１，…，ｘｎの論理和ｘ１∨…∨ｘｎを表す状態と等しくなる。例えばｎ＝３のときにはｍ＝２となり、ステップＳ１では次のような２つの１量子ビット状態が生成される。
【数１７】
0006445487.tif 000018
【００３５】
これらが次の性質を持つことは容易に確かめられる（例えば、参考文献２：P. Hoyer and R. Spalek, “Quantum fan-out is powerful,” Theory of Computing, Vol. 1, pp. 81-103, 2005.）。
・ｘ１∨ｘ２∨ｘ３＝１（ｘ１，ｘ２，ｘ３の中の少なくとも１つは１）の場合、上の２つの状態（式（２）（３））の中の少なくとも１つは｜１〉。
・ｘ１∨ｘ２∨ｘ３＝０（ｘ１，ｘ２，ｘ３の全てが０）の場合、上の２つの状態（式（２）（３））は全て｜０〉。
従って、ｘ１∨ｘ２∨ｘ３の計算は、状態｜φ１〉，｜φ２〉の論理和、すなわち論理和φ１∨φ２を表す状態を得る計算に帰着される。そのため、ステップＳ２で状態｜φ１〉…｜φｍ〉からφ１，…，φｍの論理和を表す状態を生成することで、ｘ１∨ｘ２∨ｘ３の演算結果を得ることができる。
【００３６】
本形態では、初期化補助量子ビットおよび未初期化補助量子ビットを用い、ｘ１，…，ｘｎの論理和の計算をφ１，…，φｍの論理和の計算に帰着させることで、従来よりも少ない計算ステップで論理和関数を計算できる。
【００３７】
＜ステップＳ１の詳細＞
ステップ１の詳細を説明する。
次の量子ビットを用いる（図１，図２Ａおよび図２Ｂ）。
・ｎ個の入力量子ビットＸ１，…，Ｘｎ
・１個の出力量子ビットＹ
・ｍ個の初期化補助量子ビットＩ（１），…，Ｉ（ｍ）
・ｎｍ（ｍ＋３）／２個の未初期化補助量子ビット（未初期化補助量子ビットの構成は前述の通り）
【００３８】
初期状態は次の通りである。
Ｘ１，…，Ｘｎの初期状態はそれぞれ｜ｘ１〉，…，｜ｘｎ〉
Ｙの初期状態は｜ｙ〉
Ｉ（１），…，Ｉ（ｍ）の初期状態はそれぞれ｜０〉，…，｜０〉
任意の１≦ｋ≦ｍに対し、Ａ１（ｋ），…，Ａｎ（ｋ）の初期状態はそれぞれ｜ａ１（ｋ）〉，…，｜ａｎ（ｋ）〉
任意の１≦ｋ≦ｍおよび１≦ｒ≦ｋに対し、Ｂ１（ｋ，ｒ），…，Ｂｎ（ｋ，ｒ）の初期状態はそれぞれ｜ｂ１（ｋ，ｒ）〉，…，｜ｂｎ（ｋ，ｒ）〉
【００３９】
回路構成の記述を容易にするため、全量子ビットの状態を図示する場合、Ｘ１，…，Ｘｎの状態を先頭に記述し、その後は、ｋ＝１からｍまで順に、各ｋについてＡ１（ｋ），…，Ａｎ（ｋ）の状態，Ｉ（ｋ）の状態，Ｂ（ｋ，１），…，Ｂ（ｋ，ｋ）の状態という順序で記述し、最後にＹの状態を記述する。また、任意の１≦ｒ≦ｋに対するＢ（ｋ，ｒ）の状態は、Ｂ１（ｋ，ｒ）の状態，…，Ｂｎ（ｋ，ｒ）の状態の順に記述する。ステップＳ１では、Ｉ（ｋ）（ただし、１≦ｋ≦ｍ）の状態が｜φｋ〉となり、他の量子ビットの状態は変化しない。例えば、ｎ＝３の場合、ｍ＝２であり、３個の入力量子ビットＸ１，Ｘ２，Ｘ３，１個の出力量子ビットＹ，２個の初期化補助量子ビットＩ（１），Ｉ（２），１５個の未初期化補助量子ビットＡ１（１），Ａ２（１），Ａ３（１），Ａ１（２），Ａ２（２），Ａ３（２），Ｂ１（１，１），Ｂ２（１，１），Ｂ３（１，１），Ｂ１（２，１），Ｂ２（２，１），Ｂ３（２，１），Ｂ１（２，２），Ｂ２（２，２），Ｂ３（２，２）の状態を上で述べた順序で記述すると、次のようになる。
｜ｘ１〉｜ｘ２〉｜ｘ３〉｜ａ１（１）〉｜ａ２（１）〉｜ａ３（１）〉｜０〉｜ｂ１（１，１）〉｜ｂ２（１，１）〉｜ｂ３（１，１）〉｜ａ１（２）〉｜ａ２（２）〉｜ａ３（２）〉｜０〉｜ｂ１（２，１）〉｜ｂ２（２，１）〉｜ｂ３（２，１）〉｜ｂ１（２，２）〉｜ｂ２（２，２）〉｜ｂ３（２，２）〉｜ｙ〉
【００４０】
ステップＳ１の処理により、この状態が次の状態になる。
｜ｘ１〉｜ｘ２〉｜ｘ３〉｜ａ１（１）〉｜ａ２（１）〉｜ａ３（１）〉｜φ１〉｜ｂ１（１，１）〉｜ｂ２（１，１）〉｜ｂ３（１，１）〉｜ａ１（２）〉｜ａ２（２）〉｜ａ３（２）〉｜φ２〉｜ｂ１（２，１）〉｜ｂ２（２，１）〉｜ｂ３（２，１）〉｜ｂ１（２，２）〉｜ｂ２（２，２）〉｜ｂ３（２，２）〉｜ｙ〉
【００４１】
図１４に例示するように、ステップＳ１はｍ個のステージＳ（１），…，Ｓ（ｍ）（ステップＳ１１−１〜Ｓ１１−ｍ）を、Ｓ（１），…，Ｓ（ｍ）の順に実行する。すなわち、ｓ’を２≦ｓ’≦ｍを満たす整数とすると、ステージＳ（ｓ’）はステージＳ（ｓ’−１）の後に実行される。
【００４２】
≪ステージＳ（ｓ）の詳細≫
図３，図４，図１５を用いてステージＳ（ｓ）の詳細を説明する。ただし、ｓは１≦ｓ≦ｍを満たす整数である。ただし、図３はｎ＝３，ｍ＝２，ｓ＝１の例であり、図４はｎ＝３，ｍ＝２，ｓ＝２の例である。
【００４３】
まず演算部１１０１（第１演算部）が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））にアダマール演算を適用する（ステップＳ１１１−ｓ）。
【００４４】
次に演算部１１０２（第２演算部）が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））を制御ビットとし、Ｂ１（ｋ（ｓ），ｓ），…，Ｂｎ（ｋ（ｓ），ｓ）を標的ビットとした(n+1)-fanout演算を並列に適用する（ステップＳ１１２−ｓ）。
【００４５】
ｓ≧２のときには、次に演算部１１０３（第３演算部）が、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を標的ビットとしたs-fanout演算を並列に適用する。ｓ＝１のときには、演算部１１０３は何の演算も適用しない（ステップＳ１１３−ｓ）。
【００４６】
ｓ＝１のときには、次に演算部１１０４（第４演算部）が、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算の逆演算を並列に適用する。ｓ≧２のときには、演算部１１０４は、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））およびＢｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算の逆演算を並列に適用する（ステップＳ１１４−ｓ）。
【００４７】
次に演算部１１０５（第５演算部）が、１≦ｊ≦ｎについて、Ｘｊを制御ビットとし、Ａｊ（ｓ），Ａｊ（ｓ＋１），…，Ａｊ（ｍ）を標的ビットとした(m-s+2)-fanout演算を並列に適用する（ステップＳ１１５−ｓ）。
【００４８】
ｓ＝１のときには、次に演算部１１０６（第６演算部）が、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算を並列に適用する。ｓ≧２のときには、演算部１１０６は、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））およびＢｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を制御ビットとし、Ｂｊ（ｋ（ｓ），ｓ）を標的ビットとした(s+1,k(s)-s+1)-位相シフト演算を並列に適用する（ステップＳ１１６−ｓ）。
【００４９】
次に演算部１１０７（第７演算部）が、１≦ｊ≦ｎについて、Ｘｊを制御ビットとし、Ａｊ（ｓ），Ａｊ（ｓ＋１），…，Ａｊ（ｍ）を標的ビットとした(m-s+2)-fanout演算を行う（ステップＳ１１７−ｓ：ステップＳ１１５−ｓと同じ）。
【００５０】
ｓ≧２のときには、次に演算部１１０８（第８演算部）が、ｓ≦ｋ（ｓ）≦ｍと１≦ｊ≦ｎについて、Ａｊ（ｋ（ｓ））を制御ビットとし、Ｂｊ（ｋ（ｓ），１），…，Ｂｊ（ｋ（ｓ），ｓ−１）を標的ビットとしたs-fanout演算を並列に適用する。ｓ＝１のときには、演算部１１０８は何の演算も適用しない（ステップＳ１１８−ｓ：ステップＳ１１３−ｓと同じ）。
【００５１】
次に演算部１１０９（第９演算部）が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））を制御ビットとし、Ｂ１（ｋ（ｓ），ｓ），…，Ｂｎ（ｋ（ｓ），ｓ）を標的ビットとした(n+1)-fanout演算を並列に適用する（ステップＳ１１９−ｓ：ステップＳ１１２−ｓと同じ）。
【００５２】
次に演算部１１０１（第１演算部）が、ｓ≦ｋ（ｓ）≦ｍについて、Ｉ（ｋ（ｓ））にアダマール演算を適用する（ステップＳ１２０−ｓ：ステップＳ１１１−ｓと同じ）。
【００５３】
以上により、ｍ個の初期化補助量子ビットＩ（１），…，Ｉ（ｍ）の状態がそれぞれ｜φ１〉，…，｜φｍ〉となる（この理由については後述する）。
【００５４】
＜ステップＳ２の詳細＞
図５，図１６を用いてステップ２の詳細を説明する。ただし、図５はｎ＝３，ｍ＝２の例である。
【００５５】
上述したステップＳ１の後、まず、演算部１２１１（第１１演算部）は、１≦ｋ≦ｍについて、Ｉ（ｋ）にNOT演算Ｘを並列に適用する（ステップＳ２１）。
【００５６】
次に、演算部１２１２（第１２演算部）は、Ｉ（１），…，Ｉ（ｍ）を制御ビットとし、Ｙを標的ビットとした(m+1)-Toffoli演算を並列に適用する。(m+1)-Toffoli演算は、論理和関数ｘ１∨…∨ｘｎ（ただし、ｎ＝ｍ）を計算する量子回路から最初と最後の計算ステップのNOT演算を取り除いた量子回路によって計算できる（例えば、非特許文献１参照）。なお、このような量子回路は１個の未初期化補助量子ビットを使うが、(m+1)-Toffoli演算の制御ビットおよび標的ビット以外の任意の量子ビット（例えば、入力量子ビットＸ１）をこの未初期化補助量子ビットに対応させればよい（ステップＳ２２）。
【００５７】
次に、演算部１２１３（第１３演算部）は、ＹにNOT演算Ｘを適用し、これと並列にステップＳ２１と同じ演算、すなわち１≦ｋ≦ｍについてＩ（ｋ）へのNOT演算Ｘを適用する（ステップＳ２３）。
【００５８】
次に、演算部１２１４（第１４演算部）は、ステージＳ（１），…，Ｓ（ｍ）の逆演算ＲＳ（ｍ），…，ＲＳ（１）を適用する。ただし、逆演算ＲＳ（ｓ）はステージＳ（ｓ）の逆演算であり、２≦ｓ’≦ｍを満たす整数ｓ’について逆演算ＲＳ（ｓ’−１）は逆演算ＲＳ（ｓ’）の後に実行される。すなわち、ステージＳ（ｍ）の逆演算ＲＳ（ｍ）を実行する量子回路から始めて、ステージＳ（１）の逆演算ＲＳ（１）を実行する量子回路まで順に適用する。各ステージＳ（ｓ）の逆演算ＲＳ（ｓ）を実行する量子回路は、各ステージＳ（ｓ）の量子回路において、各ゲートをその逆演算と置換し、適用する順番を逆転させたものである。ＨとＣＮＯＴの逆演算はそれぞれそれ自身である。また、ある演算に対し、その逆演算の逆演算は、元の演算であることに注意する（ステップＳ２４）。
【００５９】
ステップＳ２２までの演算とステップ２３の中のＹに適用するNOT演算Ｘにより、｜φ１〉，…，｜φｍ〉に対する論理和が計算され、Ｙが論理和ｘ１∨…∨ｘｎを表す状態｜ｙ（＋）ｘ１∨…∨ｘｎ〉となる。また、ステップＳ２３の中でステップＳ２１と同じ演算を適用しているのはＩ（ｋ）の状態を｜φｋ〉に戻すためであり、Ｙ以外の量子ビットの状態はステップＳ１の出力状態に戻る。従って、ステップ２４により、Ｙ以外の量子ビットの状態は初期状態に戻る。ステップＳ１はＹに演算を適用しないことに注意する。
【００６０】
＜ステップＳ１で正しく｜φ１〉，…，｜φｍ〉が生成される理由＞
ステップＳ１で正しく｜φ１〉，…，｜φｍ〉が生成される理由を説明する。簡単のため、ｎ＝３（従って、ｍ＝２）の場合について述べる。
【００６１】
≪｜φ１〉について≫
図３に例示したように、｜φ１〉はステージＳ（１）（ステップＳ１１−１）で用意が完了する。簡単のため、Ｉ（１）とＢ１（１，１），Ｂ２（１，１），Ｂ３（１，１）だけの状態変化を記述する。これらの初期状態は｜０〉｜ｂ１（１，１）〉｜ｂ２（１，１）〉｜ｂ３（１，１）〉であり、ステップＳ１１４−ｓ終了後、状態は次のようになる。
【数１８】
0006445487.tif 000019
ただし、α＝−ａ１（１）（１−２ｂ１（１，１））−ａ２（１）（１−２ｂ２（１，１））−ａ３（１）（１−２ｂ３（１，１））である。さらにステップＳ１１６−ｓ終了後、状態は次のようになる。
【数１９】
0006445487.tif 000020
ただし、β＝ｘ１−２（ａ１（１）（＋）ｂ１（１，１））ｘ１＋ｘ２−２（ａ２（１）（＋）ｂ２（１，１））ｘ２＋ｘ３−２（ａ３（１）（＋）ｂ３（１，１））ｘ３である。さらに、ステージＳ（１）（ステップＳ１１−１）終了後、状態は次のようになる。
【数２０】
0006445487.tif 000021
ここで、βの中の２の倍数の項が
【数２１】
0006445487.tif 000022
の値に影響しないことに注意する。実際、
【数２２】
0006445487.tif 000023
であり、βの中の２の倍数である他の項も同様に計算され、
【数２３】
0006445487.tif 000024
となる。従って、式（４）の最終状態は次と等しい。
【数２４】
0006445487.tif 000025
これは所望の量子状態
【数２５】
0006445487.tif 000026
である（式（２））。
【００６２】
≪｜φ２〉について≫
図３および図４に例示したように、｜φ２〉はステージＳ（１）（ステップＳ１１−１）とＳ（２）（ステップＳ１１−２）で用意が完了する。ステージＳ（１）（ステップＳ１１−１）による状態変化は｜φ２〉の場合と同様であり、ステージＳ（１）後のＩ（２）の状態は次のようになる。
【数２６】
0006445487.tif 000027
ただし、η＝ｘ１−２（ａ１（２）（＋）ｂ１（２，１））ｘ１＋ｘ２−２（ａ２（２）（＋）ｂ２（２，１））ｘ２＋ｘ３−２（ａ３（２）（＋）ｂ３（２，１））ｘ３である。｜φ１〉の場合と異なり、ηの中の２の倍数の項が
【数２７】
0006445487.tif 000028
の値に影響しないとは言えないことに注意する。これは、ｅの指数部分の値の分母が２ではなく、２２であるからである。ステージＳ（２）（ステップＳ１１−２）による状態変化は、ステージＳ（１）（ステップＳ１１−１）と同様であり、Ｉ（２）の状態は次のようになる。
【数２８】
0006445487.tif 000029
ただし、δ＝ｘ１−２２（ａ１（２）（＋）ｂ１（２，１））（ａ１（２）（＋）ｂ１（２，２））ｘ１＋ｘ２−２２（ａ２（２）（＋）ｂ２（２，１））（ａ２（２）（＋）ｂ２（２，２））ｘ２＋ｘ３−２２（ａ３（２）（＋）ｂ３（２，１））（ａ３（２）（＋）ｂ３（２，２））ｘ３である。δの中の２２の倍数の項が
【数２９】
0006445487.tif 000030
の値に影響しないことは、｜φ１〉を用意する場合に、βの中の２の倍数の項が
【数３０】
0006445487.tif 000031
の値に影響しなかったことと同様である。従って、この状態は所望の状態
【数３１】
0006445487.tif 000032
と等しい。
【００６３】
＜補助量子ビットと計算ステップの個数＞
前述のように、本形態の論理和関数を計算する量子回路は、ｍ＝ｃｅｉｌ（ｌｏｇ２（ｎ＋１））＝Ｏ（ｌｏｇｎ）個の初期化補助量子ビットを持ち、ｎｍ（ｍ＋３）／２＝Ｏ（ｎ （ｌｏｇ２ｎ）２）個の未初期化補助量子ビットを持つ。
【００６４】
この量子回路の計算ステップの個数を考える。任意の１≦ｓ≦ｍに対し、ステージＳ（ｓ）の計算ステップの個数は以下のようになる。
・ステップＳ１１１−ｓ：１
・ステップＳ１１２−ｓ：Ｏ（ｌｏｇ２（ｎ＋１））
・ステップＳ１１３−ｓ：Ｏ（ｌｏｇ２ ｓ）
・ステップＳ１１４−ｓ：Ｏ（ｓ＋１）
・ステップＳ１１５−ｓ：Ｏ（ｌｏｇ２（ｍ−ｓ＋２））
・ステップＳ１１６−ｓ〜Ｓ１２０−ｓ：ステップＳ１１１−ｓ〜Ｓ１１５−ｓと同じ
ｓ≦ｍ＝Ｏ（ｌｏｇ２ｎ）であるから、ステージＳ（ｓ）のステップの個数はＯ（ｌｏｇ２ ｎ）となり、ステップＳ１のステップの個数はＯ（ｍｌｏｇ２ ｎ）＝Ｏ（（ｌｏｇ２ ｎ）２）となる。
【００６５】
ステップＳ２については次のようになる。
・ステップＳ２１：１
・ステップ２２：Ｏ（ｍ＋１）
・ステップ２３：１
・ステップ２４：ステップＳ１と同じ
従って、ステップＳ２の計算ステップの個数はＯ（（ｌｏｇ２ ｎ）２）となり、本形態の量子回路全体のステップの個数はＯ（（ｌｏｇ２ｎ）２）となる。
【００６６】
＜本形態の特徴＞
多数の初期化補助量子ビットを実現するのは物理的に困難であるが、多数の未初期化補助量子ビットを実現するのは、初期化補助量子ビットと比較して容易である。また、量子回路の計算ステップの個数が多いほど計算時間が長くなる。従って、物理的実現性の高さと短い計算時間を同時に実現するためには、未初期化補助量子ビットを多く使ったとしても、初期化補助量子ビットの個数と計算ステップの個数を同時に小さくするほうがよい。未初期化補助量子ビットを多く使ったとしても、初期化補助量子ビットの個数と計算ステップの個数が同時に対数多項式（Ｏ（（ｌｏｇ２ ｎ）ｃ），ｃは０以上の定数）で表現される程小さい量子回路の構成方法は知られていなかった。
【００６７】
本形態の量子回路では、Ｏ（ｎ （ｌｏｇ２ｎ）２）個の未初期化補助量子ビットおよびＯ（ｌｏｇ２ｎ）個の初期化補助量子ビットを利用し、Ｏ（（ｌｏｇ２ｎ）２）個の計算ステップで論理和関数を計算する。これにより、物理的実現性の高さと短い計算時間を同時に実現できる。
【００６８】
［その他の変形例等］
なお、本発明は上述の実施形態に限定されるものではない。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００６９】
１  論理和演算装置
１１  量子演算部
１２  量子演算部
【図１】
0006445487.tif 000035
【図２】
0006445487.tif 000036
【図３】
0006445487.tif 000037
【図４】
0006445487.tif 000038
【図５】
0006445487.tif 000039
【図６】
0006445487.tif 000040
【図７】
0006445487.tif 000041
【図８】
0006445487.tif 000042
【図９】
0006445487.tif 000043
【図１０】
0006445487.tif 000044
【図１１】
0006445487.tif 000045
【図１２】
0006445487.tif 000046
【図１３】
0006445487.tif 000047
【図１４】
0006445487.tif 000048
【図１５】
0006445487.tif 000049
【図１６】
0006445487.tif 000050
【図１７】
0006445487.tif 000051