(57)【特許請求の範囲】
【請求項１】
２ｎ＋１個の量子ビットＱ１，…，Ｑ２ｎ＋１に対して操作を行うことにより、２つの二進数ａ，ｂの和ａ＋ｂを計算する量子回路であって、
第１量子ビット、第２量子ビット及び第３量子ビットからなる３つの量子ビットにＭＡＪ２を適用する操作を、第２量子ビットを制御ビット、第１量子ビットを目標ビットとするＣＮＯＴを適用し、第１量子ビットを制御ビット、第２量子ビットを目標ビットとしてＣＮＯＴを適用し、第３量子ビットを制御ビット、第２量子ビットを目標ビットとしてＣＮＯＴを適用し、第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＣＮＯＴを適用し、第１量子ビットと第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＴｏｆｆｏｌｉを適用する操作とし、
第１量子ビット、第２量子ビット及び第３量子ビットからなる３つの量子ビットにＵＭＡ２を適用する操作を、第１、第２量子ビットを制御ビットとし、第３量子ビットを目標ビットとしてＴｏｆｆｏｌｉを適用し、第２量子ビットと第３量子ビットにＳＷＡＰを適用し、第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＣＮＯＴを適用し、第１量子ビットと第２量子ビットにＳＷＡＰを適用する操作とし、
第１量子ビット、第２量子ビット、第３量子ビット及び第４量子ビットからなる４つの量子ビットにＳＷＡＰ２を適用する操作を、第２量子ビットと第３量子ビットにＳＷＡＰを適用し、第１量子ビットと第２量子ビットにＳＷＡＰを適用し、第３量子ビットと第４量子ビットにＳＷＡＰを適用し、第２量子ビットと第３量子ビットにＳＷＡＰを適用する操作としたとき、
上記二進数ｂの各桁は小さい方から量子ビットＱ２ｉ＋１（ｉ＝０，…，ｎ−１）の初期状態にそれぞれ対応し、上記二進数ａの各桁は小さい方から量子ビットＱ２ｉ＋２（ｉ＝０，…，ｎ−１）の初期状態にそれぞれ対応し、和ａ＋ｂの各桁は小さい方から量子ビットＱ２ｉ＋１（ｉ＝０，…，ｎ）の操作後の状態にそれぞれ対応し、
量子ビットＱ２ｎ−ｋ＋１を目標ビット、量子ビットＱ２ｎ−ｋを制御ビットとしてＣＮＯＴを適用し、量子ビットＱ２ｎ−ｋ＋１を制御ビット、量子ビットＱ２ｎ−ｋを目標ビットとしてＣＮＯＴを適用する操作をｋ＝０からｋ＝２ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ１，Ｑ２を制御ビット、量子ビットＱ３を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４，Ｑ２ｋ＋５にＭＡＪ２を適用し、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３にＳＷＡＰを適用し、量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４にＳＷＡＰを適用し、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３を制御ビット、量子ビットＱ２ｋ＋４を目標ビットとしてＴｏｆｆｏｌｉを適用する操作をｋ＝０からｋ＝ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１にＭＡＪ２を適用し、
量子ビットＱ２ｎ−２，Ｑ２ｎ−１にＳＷＡＰを適用し、量子ビットＱ２ｎ−１を制御ビット、量子ビットＱ２ｎを目標ビットとしてＣＮＯＴを適用し、量子ビットＱ２ｎ−２，Ｑ２ｎ−１にＳＷＡＰを適用し、
量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２にＵＭＡ２を適用する操作をｋ＝０からｋ＝ｎ−４までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２，Ｑ３を制御ビット、量子ビットＱ４を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ１にＮＯＴを適用し、量子ビットＱ１，Ｑ２にＳＷＡＰを適用し、量子ビットＱ２，Ｑ３にＳＷＡＰを適用し、量子ビットＱ４，Ｑ５にＳＷＡＰを適用し、量子ビットＱ３，Ｑ４にＳＷＡＰを適用し、量子ビットＱ４，Ｑ５を制御ビット、量子ビットＱ６を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ２ｋ＋４，Ｑ２ｋ＋５，Ｑ２ｋ＋６，Ｑ２ｋ＋７にＳＷＡＰ２を適用し、量子ビットＱ２ｋ＋６，Ｑ２ｋ＋７を制御ビット、量子ビットＱ２ｋ＋８目標ビットとしてＴｏｆｆｏｌｉを適用する操作をｋ＝０からｋ＝ｎ−４までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２，Ｑ２ｎ−２ｋ−１にＳＷＡＰ２を適用する操作をｋ＝０からｋ＝ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２にＮＯＴを適用し、量子ビットＱ２，Ｑ３を制御ビット、量子ビットＱ４を対象ビットとしてＴｏｆｆｏｌｉを適用し、量子ビットＱ１，Ｑ２にＳＷＡＰを適用し、量子ビットＱ２，Ｑ３にＳＷＡＰを適用し、
量子ビットＱ２ｋ＋１を目標ビット、量子ビットＱ２ｋ＋２を制御ビットとしてＣＮＯＴを適用する操作をｋ＝０からｋ＝ｎ−１までｋを１ずつ増加させて順次繰り返す、
操作を行う量子回路。
【請求項２】
２ｎ＋１個の量子ビットＱ１，…，Ｑ２ｎ＋１に対して操作を行うことにより、２つの二進数ａ，ｂの和ａ＋ｂを計算する量子演算装置であって、
第１量子ビット、第２量子ビット及び第３量子ビットからなる３つの量子ビットにＭＡＪ２を適用する操作を、第２量子ビットを制御ビット、第１量子ビットを目標ビットとするＣＮＯＴを適用し、第１量子ビットを制御ビット、第２量子ビットを目標ビットとしてＣＮＯＴを適用し、第３量子ビットを制御ビット、第２量子ビットを目標ビットとしてＣＮＯＴを適用し、第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＣＮＯＴを適用し、第１量子ビットと第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＴｏｆｆｏｌｉを適用する操作とし、
第１量子ビット、第２量子ビット及び第３量子ビットからなる３つの量子ビットにＵＭＡ２を適用する操作を、第１、第２量子ビットを制御ビットとし、第３量子ビットを目標ビットとしてＴｏｆｆｏｌｉを適用し、第２量子ビットと第３量子ビットにＳＷＡＰを適用し、第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＣＮＯＴを適用し、第１量子ビットと第２量子ビットにＳＷＡＰを適用する操作とし、
第１量子ビット、第２量子ビット、第３量子ビット及び第４量子ビットからなる４つの量子ビットにＳＷＡＰ２を適用する操作を、第２量子ビットと第３量子ビットにＳＷＡＰを適用し、第１量子ビットと第２量子ビットにＳＷＡＰを適用し、第３量子ビットと第４量子ビットにＳＷＡＰを適用し、第２量子ビットと第３量子ビットにＳＷＡＰを適用する操作としたとき、
上記二進数ｂの各桁は小さい方から量子ビットＱ２ｉ＋１（ｉ＝０，…，ｎ−１）の初期状態にそれぞれ対応し、上記二進数ａの各桁は小さい方から量子ビットＱ２ｉ＋２（ｉ＝０，…，ｎ−１）の初期状態にそれぞれ対応し、和ａ＋ｂの各桁は小さい方から量子ビットＱ２ｉ＋１（ｉ＝０，…，ｎ）の操作後の状態にそれぞれ対応し、
量子ビットＱ２ｎ−ｋ＋１を目標ビット、量子ビットＱ２ｎ−ｋを制御ビットとしてＣＮＯＴを適用し、量子ビットＱ２ｎ−ｋ＋１を制御ビット、量子ビットＱ２ｎ−ｋを目標ビットとしてＣＮＯＴを適用する操作をｋ＝０からｋ＝２ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ１，Ｑ２を制御ビット、量子ビットＱ３を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４，Ｑ２ｋ＋５にＭＡＪ２を適用し、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３にＳＷＡＰを適用し、量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４にＳＷＡＰを適用し、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３を制御ビット、量子ビットＱ２ｋ＋４を目標ビットとしてＴｏｆｆｏｌｉを適用する操作をｋ＝０からｋ＝ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１にＭＡＪ２を適用し、
量子ビットＱ２ｎ−２，Ｑ２ｎ−１にＳＷＡＰを適用し、量子ビットＱ２ｎ−１を制御ビット、量子ビットＱ２ｎを目標ビットとしてＣＮＯＴを適用し、量子ビットＱ２ｎ−２，Ｑ２ｎ−１にＳＷＡＰを適用し、
量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２にＵＭＡ２を適用する操作をｋ＝０からｋ＝ｎ−４までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２，Ｑ３を制御ビット、量子ビットＱ４を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ１にＮＯＴを適用し、量子ビットＱ１，Ｑ２にＳＷＡＰを適用し、量子ビットＱ２，Ｑ３にＳＷＡＰを適用し、量子ビットＱ４，Ｑ５にＳＷＡＰを適用し、量子ビットＱ３，Ｑ４にＳＷＡＰを適用し、量子ビットＱ４，Ｑ５を制御ビット、量子ビットＱ６を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ２ｋ＋４，Ｑ２ｋ＋５，Ｑ２ｋ＋６，Ｑ２ｋ＋７にＳＷＡＰ２を適用し、量子ビットＱ２ｋ＋６，Ｑ２ｋ＋７を制御ビット、量子ビットＱ２ｋ＋８目標ビットとしてＴｏｆｆｏｌｉを適用する操作をｋ＝０からｋ＝ｎ−４までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２，Ｑ２ｎ−２ｋ−１にＳＷＡＰ２を適用する操作をｋ＝０からｋ＝ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２にＮＯＴを適用し、量子ビットＱ２，Ｑ３を制御ビット、量子ビットＱ４を対象ビットとしてＴｏｆｆｏｌｉを適用し、量子ビットＱ１，Ｑ２にＳＷＡＰを適用し、量子ビットＱ２，Ｑ３にＳＷＡＰを適用し、
量子ビットＱ２ｋ＋１を目標ビット、量子ビットＱ２ｋ＋２を制御ビットとしてＣＮＯＴを適用する操作をｋ＝０からｋ＝ｎ−１までｋを１ずつ増加させて順次繰り返す、
操作を行う量子演算装置。
【請求項３】
２ｎ＋１個の量子ビットＱ１，…，Ｑ２ｎ＋１に対して操作を行うことにより、２つの二進数ａ，ｂの和ａ＋ｂを計算する量子演算方法であって、
第１量子ビット、第２量子ビット及び第３量子ビットからなる３つの量子ビットにＭＡＪ２を適用する操作を、第２量子ビットを制御ビット、第１量子ビットを目標ビットとするＣＮＯＴを適用し、第１量子ビットを制御ビット、第２量子ビットを目標ビットとしてＣＮＯＴを適用し、第３量子ビットを制御ビット、第２量子ビットを目標ビットとしてＣＮＯＴを適用し、第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＣＮＯＴを適用し、第１量子ビットと第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＴｏｆｆｏｌｉを適用する操作とし、
第１量子ビット、第２量子ビット及び第３量子ビットからなる３つの量子ビットにＵＭＡ２を適用する操作を、第１、第２量子ビットを制御ビットとし、第３量子ビットを目標ビットとしてＴｏｆｆｏｌｉを適用し、第２量子ビットと第３量子ビットにＳＷＡＰを適用し、第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＣＮＯＴを適用し、第１量子ビットと第２量子ビットにＳＷＡＰを適用する操作とし、
第１量子ビット、第２量子ビット、第３量子ビット及び第４量子ビットからなる４つの量子ビットにＳＷＡＰ２を適用する操作を、第２量子ビットと第３量子ビットにＳＷＡＰを適用し、第１量子ビットと第２量子ビットにＳＷＡＰを適用し、第３量子ビットと第４量子ビットにＳＷＡＰを適用し、第２量子ビットと第３量子ビットにＳＷＡＰを適用する操作としたとき、
上記二進数ｂの各桁は小さい方から量子ビットＱ２ｉ＋１（ｉ＝０，…，ｎ−１）の初期状態にそれぞれ対応し、上記二進数ａの各桁は小さい方から量子ビットＱ２ｉ＋２（ｉ＝０，…，ｎ−１）の初期状態にそれぞれ対応し、和ａ＋ｂの各桁は小さい方から量子ビットＱ２ｉ＋１（ｉ＝０，…，ｎ）の操作後の状態にそれぞれ対応し、
量子ビットＱ２ｎ−ｋ＋１を目標ビット、量子ビットＱ２ｎ−ｋを制御ビットとしてＣＮＯＴを適用し、量子ビットＱ２ｎ−ｋ＋１を制御ビット、量子ビットＱ２ｎ−ｋを目標ビットとしてＣＮＯＴを適用する操作をｋ＝０からｋ＝２ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ１，Ｑ２を制御ビット、量子ビットＱ３を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４，Ｑ２ｋ＋５にＭＡＪ２を適用し、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３にＳＷＡＰを適用し、量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４にＳＷＡＰを適用し、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３を制御ビット、量子ビットＱ２ｋ＋４を目標ビットとしてＴｏｆｆｏｌｉを適用する操作をｋ＝０からｋ＝ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１にＭＡＪ２を適用し、
量子ビットＱ２ｎ−２，Ｑ２ｎ−１にＳＷＡＰを適用し、量子ビットＱ２ｎ−１を制御ビット、量子ビットＱ２ｎを目標ビットとしてＣＮＯＴを適用し、量子ビットＱ２ｎ−２，Ｑ２ｎ−１にＳＷＡＰを適用し、
量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２にＵＭＡ２を適用する操作をｋ＝０からｋ＝ｎ−４までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２，Ｑ３を制御ビット、量子ビットＱ４を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ１にＮＯＴを適用し、量子ビットＱ１，Ｑ２にＳＷＡＰを適用し、量子ビットＱ２，Ｑ３にＳＷＡＰを適用し、量子ビットＱ４，Ｑ５にＳＷＡＰを適用し、量子ビットＱ３，Ｑ４にＳＷＡＰを適用し、量子ビットＱ４，Ｑ５を制御ビット、量子ビットＱ６を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ２ｋ＋４，Ｑ２ｋ＋５，Ｑ２ｋ＋６，Ｑ２ｋ＋７にＳＷＡＰ２を適用し、量子ビットＱ２ｋ＋６，Ｑ２ｋ＋７を制御ビット、量子ビットＱ２ｋ＋８目標ビットとしてＴｏｆｆｏｌｉを適用する操作をｋ＝０からｋ＝ｎ−４までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２，Ｑ２ｎ−２ｋ−１にＳＷＡＰ２を適用する操作をｋ＝０からｋ＝ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２にＮＯＴを適用し、量子ビットＱ２，Ｑ３を制御ビット、量子ビットＱ４を対象ビットとしてＴｏｆｆｏｌｉを適用し、量子ビットＱ１，Ｑ２にＳＷＡＰを適用し、量子ビットＱ２，Ｑ３にＳＷＡＰを適用し、
量子ビットＱ２ｋ＋１を目標ビット、量子ビットＱ２ｋ＋２を制御ビットとしてＣＮＯＴを適用する操作をｋ＝０からｋ＝ｎ−１までｋを１ずつ増加させて順次繰り返す、
操作を行う量子演算方法。 
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、量子回路を用いて量子演算を行う技術に関する。
【背景技術】
【０００２】
近年、従来の情報理論では解決が難しかった問題を、微細な世界に適用される物理法則である量子力学の原理を応用して解決する技術が注目を集めている。例えば、量子コンピュータは、量子力学の世界特有の現象である重ね合わせ状態を利用し、複数の演算を並列的に実行することができる（量子並列性）。そして、この量子並列性及び観測による状態の縮退により、量子コンピュータは、因数分解などの問題に対し、現在のコンピュータよりはるかに高速に計算が可能であることが示唆されている。
【０００３】
例えば、非特許文献１では、量子コンピュータにおいて、２つの二進数ａ＝ａｎ−１…ａ０及びｂ＝ｂｎ−１…ｂ０と、０または１のｚとが入力として与えられたとき、ａ＋ｂ＝ｓｎ…ｓ０を計算し、ｚ（＋）ｓｎとｓｎ−１…ｓ０とａとを出力とする量子回路が開示されている。ただし、ｎは自然数であり、ａｉ∈｛０，１｝（ｉ＝０，…，ｎ−１）、ｂｉ∈｛０，１｝（ｉ＝０，…，ｎ−１）であり、α，β∈｛０，１｝として、α（＋）βはαとβとのｍｏｄ２での加算（排他的論理和）を示す。
【０００４】
図１５は、この非特許文献１に開示された量子回路を示した図である。
【０００５】
この図に示すように、図１５の量子回路は、ＭＡＪ（Majorrity）ゲートと、ＵＭＡ（UnMajorrity and Add）ゲートと、ＣＮＯＴゲートとによって構成される。ここで、量子回路とは、ＣＮＯＴゲート等の量子基本ゲートの組合せを意味する。
【０００６】
ＭＡＪゲートは、３個の量子ビットがそれぞれ示すｘ，ｙ，ｚのマジョリティｘｙ（＋）ｙｚ（＋）ｚｘを計算する量子回路であり、図１０のように定義される。この図に示すように、ＭＡＪゲートは、それぞれ図６、図７で定義されるＣＮＯＴゲートとＴｏｆｆｏｌｉゲートによって構成される。
【０００７】
ＵＭＡゲートは、図１１のように定義される。この図に示すように、ＵＭＡゲートも、ＣＮＯＴゲートとＴｏｆｆｏｌｉゲートによって構成される。なお、図面における
【０００８】
【数１】
0005129646.tif 000002
は、前述した（＋）と同じ排他的論理和を示す。
【０００９】
この非特許文献１の量子回路では、２つの二進数ａ＝ａｎ−１…ａ０及びｂ＝ｂｎ−１…ｂ０を示す２ｎ個の量子ビット｜ａ０＞，…，｜ａｎ−１＞，｜ｂ０＞，…，｜ｂｎ−１＞と、０または１のｚを示す１個の量子ビット｜ｚ＞と、補助量子ビットである１個の量子ビット｜０＞を入力として用いる。なお、図１５は、ａ，ｂがそれぞれ５量子ビット（ｎ＝５）によって表される場合の例であるが、これをｎ量子ビットビット同士の加算回路に拡張することは容易である。
【００１０】
また、この量子回路の場合、演算処理を実行するために必要な基本ゲート（この例ではＣＮＯＴゲートとＴｏｆｆｏｌｉゲート）の3数は、ａ，ｂの桁数に比例して増加する。さらに、演算処理を実行するために必要な計算ステップ数も、ａ，ｂの桁数に比例して増加する。ここで、入力桁数に比例した基本演算数のことを「線形サイズ」といい、入力桁数に比例した計算ステップ数のことを「線形深さ」という。すなわち、非特許文献１の量子回路は、線形サイズ・線形深さで演算を行う量子回路である。
【非特許文献１】S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, “A new quantum ripple-carry addition circuit”，[online], [平成２０年５月１日検索]，インターネット＜http://arxiv.org/abs/quant-ph/0410184v1＞,2004
【発明の開示】
【発明が解決しようとする課題】
【００１１】
多数の量子ビットを実現し、協調的に操作するのは物理的に困難なため、補助量子ビットを用いない方が望ましい。また、量子ビットの制御を容易にするために、近傍量子ビットに対する量子操作のみで量子回路を構成することが望ましい。ここで、近傍量子ビットとは、連続して並ぶ、二進数ａ，ｂの桁数ｎに依存しない定数ｃ個の量子ビットのことである。
【００１２】
しかし、非特許文献１に記載された量子回路は、補助量子ビットが必要であり、近傍量子ビットではない量子ビットに対する量子操作を含むという問題があった。
【００１３】
この発明は、上記問題に鑑み、補助量子ビットを用いないで、近傍量子ビットに対する量子操作のみで、２つの二進数ａ，ｂの和ａ＋ｂを計算する量子回路、量子演算装置及び量子演算方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
この発明の１つの観点によれば、２ｎ＋１個の量子ビットＱ１，…，Ｑ２ｎ＋１に対して操作を行うことにより、２つの二進数ａ，ｂの和ａ＋ｂを計算するために、
第１量子ビット、第２量子ビット及び第３量子ビットからなる３つの量子ビットにＭＡＪ２を適用する操作を、第２量子ビットを制御ビット、第１量子ビットを目標ビットとするＣＮＯＴを適用し、第１量子ビットを制御ビット、第２量子ビットを目標ビットとしてＣＮＯＴを適用し、第３量子ビットを制御ビット、第２量子ビットを目標ビットとしてＣＮＯＴを適用し、第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＣＮＯＴを適用し、第１量子ビットと第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＴｏｆｆｏｌｉを適用する操作とし、
第１量子ビット、第２量子ビット及び第３量子ビットからなる３つの量子ビットにＵＭＡ２を適用する操作を、第１、第２量子ビットを制御ビットとし、第３量子ビットを目標ビットとしてＴｏｆｆｏｌｉを適用し、第２量子ビットと第３量子ビットにＳＷＡＰを適用し、第２量子ビットを制御ビット、第３量子ビットを目標ビットとしてＣＮＯＴを適用し、第１量子ビットと第２量子ビットにＳＷＡＰを適用する操作とし、
第１量子ビット、第２量子ビット、第３量子ビット及び第４量子ビットからなる４つの量子ビットにＳＷＡＰ２を適用する操作を、第２量子ビットと第３量子ビットにＳＷＡＰを適用し、第１量子ビットと第２量子ビットにＳＷＡＰを適用し、第３量子ビットと第４量子ビットにＳＷＡＰを適用し、第２量子ビットと第３量子ビットにＳＷＡＰを適用する操作としたとき、
上記二進数ｂの各桁は小さい方から量子ビットＱ２ｉ＋１（ｉ＝０，…，ｎ−１）の初期状態にそれぞれ対応し、上記二進数ａの各桁は小さい方から量子ビットＱ２ｉ＋２（ｉ＝０，…，ｎ−１）の初期状態にそれぞれ対応し、和ａ＋ｂの各桁は小さい方から量子ビットＱ２ｉ＋１（ｉ＝０，…，ｎ）の操作後の状態にそれぞれ対応し、
量子ビットＱ２ｎ−ｋ＋１を目標ビット、量子ビットＱ２ｎ−ｋを制御ビットとしてＣＮＯＴを適用し、量子ビットＱ２ｎ−ｋ＋１を制御ビット、量子ビットＱ２ｎ−ｋを目標ビットとしてＣＮＯＴを適用する操作をｋ＝０からｋ＝２ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ１，Ｑ２を制御ビット、量子ビットＱ３を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４，Ｑ２ｋ＋５にＭＡＪ２を適用し、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３にＳＷＡＰを適用し、量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４にＳＷＡＰを適用し、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３を制御ビット、量子ビットＱ２ｋ＋４を目標ビットとしてＴｏｆｆｏｌｉを適用する操作をｋ＝０からｋ＝ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１にＭＡＪ２を適用し、
量子ビットＱ２ｎ−２，Ｑ２ｎ−１にＳＷＡＰを適用し、量子ビットＱ２ｎ−１を制御ビット、量子ビットＱ２ｎを目標ビットとしてＣＮＯＴを適用し、量子ビットＱ２ｎ−２，Ｑ２ｎ−１にＳＷＡＰを適用し、
量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２にＵＭＡ２を適用する操作をｋ＝０からｋ＝ｎ−４までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２，Ｑ３を制御ビット、量子ビットＱ４を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ１にＮＯＴを適用し、量子ビットＱ１，Ｑ２にＳＷＡＰを適用し、量子ビットＱ２，Ｑ３にＳＷＡＰを適用し、量子ビットＱ４，Ｑ５にＳＷＡＰを適用し、量子ビットＱ３，Ｑ４にＳＷＡＰを適用し、量子ビットＱ４，Ｑ５を制御ビット、量子ビットＱ６を目標ビットとしてＴｏｆｆｏｌｉを適用し、
量子ビットＱ２ｋ＋４，Ｑ２ｋ＋５，Ｑ２ｋ＋６，Ｑ２ｋ＋７にＳＷＡＰ２を適用し、量子ビットＱ２ｋ＋６，Ｑ２ｋ＋７を制御ビット、量子ビットＱ２ｋ＋８目標ビットとしてＴｏｆｆｏｌｉを適用する操作をｋ＝０からｋ＝ｎ−４までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２，Ｑ２ｎ−２ｋ−１にＳＷＡＰ２を適用する操作をｋ＝０からｋ＝ｎ−３までｋを１ずつ増加させて順次繰り返し、
量子ビットＱ２にＮＯＴを適用し、量子ビットＱ２，Ｑ３を制御ビット、量子ビットＱ４を対象ビットとしてＴｏｆｆｏｌｉを適用し、量子ビットＱ１，Ｑ２にＳＷＡＰを適用し、量子ビットＱ２，Ｑ３にＳＷＡＰを適用し、
量子ビットＱ２ｋ＋１を目標ビット、量子ビットＱ２ｋ＋２を制御ビットとしてＣＮＯＴを適用する操作をｋ＝０からｋ＝ｎ−１までｋを１ずつ増加させて順次繰り返す、
操作を行う。
【発明の効果】
【００１５】
補助量子ビットを用いないで、近傍量子ビットに対する操作のみで、２つの二進数ａ，ｂの和ａ＋ｂを計算することができる。
【発明を実施するための最良の形態】
【００１６】
以下、この発明の量子回路、量子演算装置及び量子演算方法の一実施形態について説明する。同一の部分には、同じ符号を付けて重複説明を略する。
【００１７】
この実施形態による量子回路、量子演算装置及び量子演算方法は、２つのｎ（ｎは自然数）桁の二進数ａ＝ａｎ−１…ａ０と、ｂ＝ｂｎ−１…ｂ０と０又は１であるｚが入力として与えられたとき、和ａ＋ｂ＝ｓｎ…ｓ０を計算し、ｚ（＋）ｓｎとｓｎ−１…ｓ０とａ＝ａｎ−１…ａ０とを出力する。ｉ＝０，…，ｎ−１として、ａｉ∈｛０，１｝，ｂｉ∈｛０，１｝，ｓｉ∈｛０，１｝である。（＋）は、ｍｏｄ２での加算である。
【００１８】
この実施形態による量子回路、量子回路及び量子演算方法は、和ａ＋ｂを計算するために、２ｎ＋１個の量子ビットＱ１，…，Ｑ２ｎ＋１（図２０参照）に対して量子操作を行う。非特許文献１の量子回路とは異なり、補助量子ビットを用いない。ここで、量子ビットに対して量子操作を行うことを、量子ビットに対して操作を行うと略記することがある。
【００１９】
二進数ｂの各桁は小さい方から量子ビットＱ２ｉ＋１（ｉ＝０，…，ｎ−１）の初期状態にそれぞれ対応しており、二進数ａの各桁は小さい方から量子ビットＱ２ｉ＋２（ｉ＝０，…，ｎ−１）の初期状態にそれぞれ対応する。すなわち、ｉ＝０，…，ｎ−１として、ｂｉの桁は量子ビットＱ２ｉ＋１の初期状態に対応し、ａｉの桁は量子ビットＱ２ｉ＋２の初期状態に対応する。
【００２０】
２つのｎ桁の二進数ａ，ｂの和ａ＋ｂは、繰り上がりにより、ｎ＋１桁になる可能性がある。量子ビットＱ２ｎ＋１は、和ａ＋ｂのｎ＋１番目の桁である最上位桁を保存するために用いられる。
【００２１】
この実施形態による量子回路、量子演算装置及び量子演算方法は、近傍量子ビットに対して操作を行う。ここで、近傍量子ビットとは、連続して並ぶ、二進数ａ，ｂの桁数ｎに依存しない定数ｃ個の量子ビットのことである。この実施形態ではｃ＝３である。量子回路及び量子演算方法を、近傍量子ビットに対する操作のみで構成することにより、物理的に実現し易くなり、量子ビットに対する操作の精度が増す。
【００２２】
この実施形態による量子回路、量子演算装置及び量子演算方法は、線形サイズ・線形深さである。線形サイズとは、基本演算数が二進数ａ，ｂの桁数ｎに比例していることを意味する。線形深さとは、計算ステップ数が二進数ａ，ｂの桁数ｎに比例していることを意味する。
【００２３】
この実施形態による量子回路、量子演算装置及び量子演算方法は、図６から図９にそれぞれ示すＣＮＯＴ、Ｔｏｆｆｏｌｉ、ＮＯＴ及びＳＷＡＰを基本演算とする。
【００２４】
以下、ｉ＝０，…，ｎ−１として、量子ビットＱ２ｉ＋１の初期状態が｜ｂｉ＞であり、量子ビットＱ２ｉ＋２の初期状態が｜ａｉ＞であり、量子ビットＱ２ｎ＋１の初期状態が｜ｚ＞である場合を例に挙げて説明をする。
【００２５】
この実施形態による量子回路及び量子演算方法は、図１６から図１９に示す５つのステップから成り、これらのステップの処理が量子演算装置により実現される。量子演算装置の機能ブロック図を図２０に例示する。図１から図５に、ｎ＝５、すなわち二進数ａ，ｂが５桁の場合の量子回路を例示する。
【００２６】
＜ステップＳ１（図１６参照）＞
ＣＮＯＴ操作部１１（図２０参照）が、量子ビットＱ２ｎ−ｋ＋１を目標ビット、量子ビットＱ２ｎ−ｋを制御ビットとしてＣＮＯＴを適用し、量子ビットＱ２ｎ−ｋ＋１を制御ビット、量子ビットＱ２ｎ−ｋを目標ビットとしてＣＮＯＴを適用する操作をｋ＝０からｋ＝２ｎ−３までｋを１ずつ増加させて順次繰り返す（ステップＳ１）。
【００２７】
ステップＳ１は、具体的にはステップＳ１ａ〜ステップｓ１ｅからなる。制御部９は、記憶部１０に格納された変数ｋをｋ＝０とする（ステップＳ１ａ）。ＣＮＯＴ操作部１１が、量子ビットＱ２ｎ−ｋ＋１を目標ビット、量子ビットＱ２ｎ−ｋを制御ビットとして、これらの量子ビットＱ２ｎ−ｋ＋１，Ｑ２ｎ−ｋにＣＮＯＴを適用する（ステップＳ１ｂ）。続いて、ＣＮＯＴ操作部１１が、量子ビットＱ２ｎ−ｋ＋１を制御ビット、量子ビットＱ２ｎ−ｋを目標ビットとして、これらの量子ビットＱ２ｎ−ｋ＋１，Ｑ２ｎ−ｋにＣＮＯＴを適用する（ステップＳ１ｃ）。制御部９は、ｋ＝２ｎ−３であるか判断する（ステップＳ１ｄ）。ｋ＝２ｎ−３でなければ、制御部９はｋを１だけインクリメント（ステップＳ１ｅ）して、ステップＳ１ｂに進む。ｋ＝２ｎ−３であれば、ステップＳ２に進む。
【００２８】
ステップＳ１の操作により、ｚの値が、二進数ａの２番目以降の桁ａｎ…ａ１及び二進数ｂの２番目以降の桁ｂｎ…ｂ１それぞれ分配される。
【００２９】
＜ステップＳ２（図１６参照）＞
ステップＳ２は、ステップＳ２ａ〜ステップＳ２ｃからなる。
【００３０】
まず、Ｔｏｆｆｏｌｉ操作部１３が、量子ビットＱ１，Ｑ２を制御ビット、量子ビットＱ３を目標ビットとしてＴｏｆｆｏｌｉを適用する（ステップＳ２ａ）。
【００３１】
続いて、量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４，Ｑ２ｋ＋５に対してＭＡＪ２を適用し、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３にＳＷＡＰを適用し、量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４に対してＳＷＡＰを適用し、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３を制御ビット、量子ビットＱ２ｋ＋４を目標ビットとしてＴｏｆｆｏｌｉを適用する操作をｋ＝０からｋ＝ｎ−３までｋを１ずつ増加させて順次繰り返す（ステップＳ２ｂ）。
【００３２】
ここで、ＭＡＪ２は、３つの入力値の内で最も多い値を出力する量子回路であり、図１２で定義される。例えば、入力値の２つ以上が｜０＞であれば｜０＞を出力し、入力値の２つ以上が｜１＞であれば｜１＞を出力する。
【００３３】
ステップＳ２ｂは、具体的にはステップＳ２ｂ１〜ステップＳ２ｂ５からなる。制御部９が、記憶部１０に格納された変数ｋをｋ＝０とする（ステップＳ２ｂ１）。ＭＡＪ２操作部１４が、量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４，Ｑ２ｋ＋５に対してＭＡＪ２を適用する（ステップＳ２ｂ２）。ＳＷＡＰ操作部１２が、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３にＳＷＡＰを適用する（ステップＳ２ｂ３）。続いて、ＳＷＡＰ操作部１２が、量子ビットＱ２ｋ＋３，Ｑ２ｋ＋４に対してＳＷＡＰを適用する（ステップＳ２ｂ４）。Ｔｏｆｆｏｌｉ操作部１３が、量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３を制御ビット、量子ビットＱ２ｋ＋４を目標ビットとして、これらの量子ビットＱ２ｋ＋２，Ｑ２ｋ＋３，Ｑ２ｋ＋４にＴｏｆｆｏｌｉを適用する（ステップＳ２ｂ５）。制御部９は、ｋ＝ｎ−３であるか判断する（ステップＳ２ｂ６）。ｋ＝ｎ−３でなければ、制御部９はｋを１だけインクリメント（ステップＳ２ｂ７）して、ステップＳ２ｂ２に進む。ｋ＝ｎ−３であれば、ステップＳ２ｃに進む。
【００３４】
ステップＳ２の最後に、ＭＡＪ２操作部１４が、量子ビットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対してＭＡＪ２を適用する（ステップＳ２ｃ）
ステップＳ２の操作により、各桁の繰り上がり｜ｃｉ＞（ｉ＝１，…，ｎ）が計算され、｜ａｉ（＋）ｃｉ＞という形で表現される。ここで、｜ｃ０＞＝｜０＞であり、｜ｃｉ＋１＞＝｜ａｉｂｉ（＋）ｂｉｃｉ（＋）ｃｉａｉ＞である。
【００３５】
なお、図２の右下に出てくる｜ｚ（＋）ｓ５＞の｜ｓ５＞は、｜ｃ５＞と等しい。｜ａ５＞＝｜ｂ５＞＝０であるためである。
【００３６】
＜ステップＳ３（図１７参照）＞
ステップＳ３は、ステップＳ３ａ〜ステップＳ３ｅからなる。
【００３７】
まず、ＳＷＡＰ操作部１２が、量子ビットＱ２ｎ−２，Ｑ２ｎ−１に対してＳＷＡＰを適用する（ステップＳ３ａ）。ＣＮＯＴ操作部１１が、量子ビットＱ２ｎ−１を制御ビット、量子ビットＱ２ｎを目標ビットとして、これらの量子ビットＱ２ｎ−１，Ｑ２ｎにＣＮＯＴを適用する（ステップＳ３ｂ）。ＳＷＡＰ操作部１２が、量子ビットＱ２ｎ−２，Ｑ２ｎ−１に対してＳＷＡＰを適用する（ステップＳ３ｃ）。
【００３８】
続いて、ＵＭＡ２操作部１５が、量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２に対してＵＭＡ２を適用する操作をｋ＝０からｋ＝ｎ−４までｋを１ずつ増加させて順次繰り返す（ステップＳ３ｄ）。ＵＭＡ２は、図１３で定義される量子ゲートである。
【００３９】
ステップＳ３ｄは、具体的にはステップＳ３ｄ１〜ステップｓ３ｄ４からなる。制御部９が、記憶部１０に格納された変数ｋをｋ＝０とする（ステップＳ３ｄ１）。ＵＭＡ２操作部１５が、量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２に対してＵＭＡ２を適用する（ステップＳ３ｄ２）。制御部９は、ｋ＝ｎ−４であるか判断する（ステップＳ３ｄ３）。ｋ＝ｎ−４でなければ、制御部９はｋを１だけインクリメント（ステップＳ３ｄ４）して、ステップＳ３ｄ２に進む。ｋ＝ｎ−４であれば、ステップＳ３ｅに進む。
【００４０】
ステップＳ３の最後に、Ｔｏｆｆｏｌｉ操作部１３が、量子ビットＱ２，Ｑ３を制御ビット、量子ビットＱ４を目標ビットとして、これらの量子ビットＱ２，Ｑ３，Ｑ４にＴｏｆｆｏｌｉを適用する（ステップＳ３ｅ）。
【００４１】
ステップＳ３の操作により、ｉ＝２，…，ｎとして、｜ａｉ（＋）ｃｉ＞は、｜ａｉ（＋）ｃ１（＋）ｂ０＞という、ｃｉがｉに依存しない形で表現される。
【００４２】
＜ステップＳ４（図１８参照）＞
ステップＳ４は、ステップＳ４ａ〜ステップＳ４ｅからなる。
【００４３】
ＮＯＴ操作部１６が、量子ビットＱ１にＮＯＴを適用する（ステップＳ４ａ）。ＳＷＡＰ操作部１２が、量子ビットＱ２，Ｑ３にＳＷＡＰを適用する（ステップＳ４ｂ）。ＳＷＡＰ操作部１２が、量子ビットＱ４，Ｑ５にＳＷＡＰを適用する（ステップＳ４ｃ）。ＳＷＡＰ操作部１２が、量子ビットＱ３，Ｑ４にＳＷＡＰを適用する。Ｔｏｆｆｏｌｉ操作部１４が、量子ビットＱ５，Ｑ６を制御ビット、量子ビットＱ７を目標ビットとして、これらの量子ビットＱ５，Ｑ６，Ｑ７にＴｏｆｆｏｌｉを適用する（ステップＳ４ｄ）。
【００４４】
続いて、量子ビットＱ２ｋ＋４，Ｑ２ｋ＋５，Ｑ２ｋ＋６，Ｑ２ｋ＋７にＳＷＡＰ２を適用し、量子ビットＱ２ｋ＋６，Ｑ２ｋ＋７，Ｑ２ｋ＋８にＴｏｆｆｏｌｉを適用する操作をｋ＝０からｋ＝ｎ−４までｋを１ずつ増加させて順次繰り返す（ステップＳ４ｅ）。
【００４５】
ＳＷＡＰ２は、図１４により定義される量子回路である。
【００４６】
ステップＳ４ｅは、具体的にはステップＳ４ｅ１〜ステップＳ４ｅ５からなる。制御部９は、記憶部１０に格納された変数ｋをｋ＝０とする（ステップＳ４ｅ１）。ＳＷＡＰ２操作部１７が、量子ビットＱ２ｋ＋４，Ｑ２ｋ＋５，Ｑ２ｋ＋６，Ｑ２ｋ＋７にＳＷＡＰ２を適用する（ステップＳ４ｅ２）。Ｔｏｆｆｏｌｉ操作部１４が、量子ビットＱ２ｋ＋６，Ｑ２ｋ＋７を制御ビット、量子ビットＱ２ｋ＋８を目標ビットとして、これらの量子ビットＱ２ｋ＋６，Ｑ２ｋ＋７，Ｑ２ｋ＋８にＴｏｆｆｏｌｉを適用する（ステップＳ４ｅ３）。制御部９は、ｋ＝ｎ−４であるか判断する（ステップＳ４ｅ４）。ｋ＝ｎ−４でなければ、制御部９はｋを１だけインクリメント（ステップＳ４ｅ５）して、ステップＳ４ｅ２に進む。ｋ＝ｎ−４であれば、ステップ５に進む。
【００４７】
ステップｓ４の操作により、ｉ＝２，…，ｎとして、｜ａｉ（＋）ｃ１（＋）ｂ０＞から、｜ａｉ＞が求められる。
【００４８】
＜ステップＳ５（図１９参照）＞
ステップＳ５は、ステップＳ５ａ〜ステップＳ５ｆからなる。
【００４９】
ＳＷＡＰ２操作部１７は、量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２，Ｑ２ｎ−２ｋ−１に対してＳＷＡＰ２を適用する操作をｋ＝０からｋ＝ｎ−３までｋを１ずつ増加させて順次繰り返す（ステップＳ５ａ）。ＳＷＡＰ２は、図１４で定義される量子ゲートである。
【００５０】
ステップＳ５ａは具体的には、ステップＳ５ａ１〜ステップＳ５ａ４からなる。制御部９が、記憶部１０に格納された変数ｋをｋ＝０とする（ステップＳ５ａ１）。ＳＷＡＰ２操作部１７は、量子ビットＱ２ｎ−２ｋ−４，Ｑ２ｎ−２ｋ−３，Ｑ２ｎ−２ｋ−２，Ｑ２ｎ−２ｋ−１に対してＳＷＡＰ２を適用する（ステップＳ５ａ２）。制御部９は、ｋ＝ｎ−３であるか判断する（ステップＳ５ａ３）。ｋ＝ｎ−３でなければ、制御部９はｋを１だけインクリメント（ステップＳ５ａ４）して、ステップＳ５ａ２に進む。ｋ＝ｎ−３であれば、ステップＳ５ｂに進む。
【００５１】
ＮＯＴ操作部１６が、量子ビットＱ２にＮＯＴを適用する（ステップＳ５ｂ）。Ｔｏｆｆｏｌｉ操作部１３が、量子ビットＱ２，Ｑ３，Ｑ４にＴｏｆｆｏｌｉを適用する（ステップＳ５ｃ）。ＳＷＡＰ操作部１２が、量子ビットＱ１，Ｑ２に対してＳＷＡＰを適用する（ステップＳ５ｄ）。続いて、ＳＷＡＰ操作部１２が、量子ビットＱ２，Ｑ３に対してＳＷＡＰを適用する（ステップＳ５ｅ）。
【００５２】
ＣＮＯＴ操作部１１が、量子ビットＱ２ｋ＋１を目標ビット、量子ビットＱ２ｋ＋２を制御ビットとしてＣＮＯＴを適用する操作をｋ＝０からｋ＝ｎ−１までｋを１ずつ増加させて順次繰り返す（ステップＳ５ｆ）。
【００５３】
ステップＳ５ｆは具体的には、ステップＳ５ｆ１〜ステップＳ５ｆ４からなる。制御部９が、記憶部１０に格納された変数ｋをｋ＝０とする（ステップＳ５ｆ１）。ＣＮＯＴ操作部１１が、量子ビットＱ２ｋ＋１を目標ビット、量子ビットＱ２ｋ＋２を制御ビットとして、これらの量子ビットＱ２ｋ＋１，Ｑ２ｋ＋２にＣＮＯＴを適用する（ステップＳ５ｆ２）。制御部９は、ｋ＝ｎ−１であるか判断する（ステップＳ５ｆ３）。ｋ＝ｎ−１でなければ、制御部９はｋを１だけインクリメント（ステップＳ５ｆ４）して、ステップＳ５ｆ２に進む。ｋ＝ｎ−１であれば、処理を終える。
【００５４】
ステップＳ５の処理により、和ａ＋ｂ＝ｓｎ…ｓ０の各桁は小さい方から、量子ビットＱ２ｉ＋１（ｉ＝０，…，ｎ）の操作後の状態にそれぞれ対応することになる。具体的には図５にｎ＝５の場合を例示するように、ｓｎ−１…ｓ０の各桁については量子ビットＱ２ｉ＋１＝｜ｓｉ＞となり（ｉ＝０，…，ｎ−１）、ｓｎの桁については量子ビットＱ２ｎ＋１＝｜ｚ（＋）Ｓｎ＞となる。
なお、量子ビットＱ２ｉ＋２（ｉ＝０，…，ｎ−１）の操作後の状態は、それぞれ二進数ｂの各桁の小さい方から対応する。
【００５５】
このように、補助量子ビットを用いないで、２つの二進数ａ，ｂの和ａ＋ｂを計算することができる。補助量子ビットを用いないことにより、従来よりも少ない量子ビットで加算を行うことができ、量子ビットの制御が容易になる。
【００５６】
〔量子演算装置〕
次に、本発明の量子回路に則って量子ビットへの操作を行う量子演算装置１について説明する。本発明の量子演算装置１は、図２０に例示するように、制御部９、記憶部１０、ＣＮＯＴ操作部１１、ＳＷＡＰ操作部１２、Ｔｏｆｆｏｌｉ操作部１３、ＭＡＪ２操作部１４、ＵＭＡ２操作部１５、ＮＯＴ操作部１６、ＳＷＡＰ２操作部１７及び量子ビットＱ１，…，Ｑ２ｎ＋１を含む。
【００５７】
量子演算装置１は、量子コンピュータ単体で実現できる。制御部９及び記憶部１０部分は後述するように古典コンピュータにより実現してもよい。量子コンピュータの実現する物理系としては、例えば、イオントラップを用いる方法（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）。
【００６０】
＜ＣＮＯＴ操作部１１＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によってＣＮＯＴを実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光ビームスプリッタ等を用い、「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. 方式によってＣＮＯＴ演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってＣＮＯＴ操作部１１を実現できる。
その他、上記の文献に記載された方法でＣＮＯＴ操作部１１を実現してもよい。
【００６１】
＜ＳＷＡＰ操作部１２，Ｔｏｆｆｏｌｉ操作部１３，ＭＡＪ２操作部，ＵＭＡ２操作部，ＮＯＴ操作部１６，ＳＷＡＰ２操作部１７＞
キュービットとして光子の偏光を用いる場合には、上述のＣＮＯＴの構成や偏光回転素子等を用い、各演算を実現できる。核スピンをキュービットやイオントラップとして用いる場合には、上述の電磁波パルスやレーザービーム照射によって各処理を実現できる。
【００６２】
＜制御部９，記憶部１０＞
制御部９は、例えば公知のコンピュータに所定のプログラムを実行させて実現してもよいし、上述の量子コンピュータによって実現してもよい。また、記憶部１０は、ＤＲＡＭ、ＳＲＡＭ、フラッシュメモリ、ＮＶ（Nonvolatile）ＲＡＭ等の読書き可能な半導体メモリでもよいし、上述の量子メモリでもよい。
【００６３】
＜量子ビット単体操作＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。
【００６４】
［変形例等］
量子ビットＱ１，…，Ｑ２ｎ＋１の全部又は一部が、｜０＞と｜１＞の重ね合わせになっていても良い。｜０＞と｜１＞の重ね合わせになっている量子ビットＱ１，…，Ｑ２ｎ＋１に対してこの発明による量子回路及び量子演算方法を適用することにより、並列処理が可能となる。例えば、ｎ桁の二進数ａ，ｂの各桁にそれぞれ対応する量子ビットＱ１，…，Ｑ２ｎのそれぞれが｜０＞と｜１＞の重ね合わせになっている場合には、２２ｎ個ある、すべての二進数ａ，ｂの組み合わせについての和ａ＋ｂを並列的に計算することができる。
【００６５】
ＭＡＪ２操作部１４がＭＡＪ２操作を量子ビットに対して行う代わりに、ＣＮＯＴ操作部１１が図１２で定義されるＭＡＪ２操作と実質的に等しい操作を行ってもよい。同様に、ＵＭＡ２操作部１５がＵＭＡ２操作を量子ビットに対して行う代わりに、ＣＮＯＴ操作部１１、ＳＷＡＰ操作部１２及びＴｏｆｆｏｌｉ操作部１３が図１３で定義されるＵＭＡ２操作と実質的に等しい操作を行ってもよい。
【００６６】
ここで、実質的に等しい操作とは、出力が同じ操作という意味である。ＵＭＡ２を例に挙げて説明すると、ＵＭＡ２操作部１５が図１３で定義されるＵＭＡ２を１回の量子操作で行う操作と、ＵＭＡ２を構成する各操作を逐次行う操作（すなわち、１番目，２番目及び３番目の量子ビットにＴｏｆｆｏｌｉ操作を行い、２番目と３番目の量子ビットにＳＷＡＰ操作を行い、２番目と３番目の量子ビットにＣＮＯＴ操作を行い、１番目と２番目の量子ビットにＳＷＡＰ操作を行う操作）とは、出力が同じであるため実質的に等しい操作である。
【００６７】
また、図９に定義されたＳＷＡＰは、図２１に示すように３つのＣＮＯＴで構成できることが知られている。換言すれば、図９に定義されたＳＷＡＰ操作は、図２１に示された３つのＣＮＯＴ操作と実質的に等しい。したがって、図１３で定義されるＵＭＡ２操作は、そのＵＭＡ２の内の２番目のＳＷＡＰを、３つのＣＮＯＴに置き換えた図２３のＵＭＡ３操作と実質的に等しい。
【００６８】
また、図２２に示すように、制御ビットと目標ビットを変えずにＣＮＯＴを２回行うと、もとの量子状態に戻ることが知られている。すなわち、制御ビットと目標ビットを変えずにＣＮＯＴを２回行う操作は、何も行わない操作と実質的に等しい。したがって、図２３で定義されるＵＭＡ３操作は、そのＵＭＡ３の内の４番目のＣＮＯＴの操作と５番目のＣＮＯＴの操作を行わない図２４で定義されるＵＭＡ４操作と実質的に等しい。ＵＭＡ２操作と実質的に等しい操作は、ここで例示したＵＭＡ３操作、ＵＭＡ４操作以外にも存在する。
【００６９】
ＵＭＡ２操作と実質的に等しい操作が複数存在したように、この発明の量子回路、量子演算装置及び量子演算方法による操作にも実質的に等しい操作が存在する。上述のステップＳ１からステップＳ５の操作に代えて、この操作と実質的に等しい操作を行ってもよい。
【００７０】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００７１】
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図面の簡単な説明】
【００７２】
【図１】ｎ＝５の場合の量子回路のステップＳ１を例示する図。
【図２】ｎ＝５の場合の量子回路のステップＳ２を例示する図。
【図３】ｎ＝５の場合の量子回路のステップＳ３を例示する図。
【図４】ｎ＝５の場合の量子回路のステップＳ４を例示する図。
【図５】ｎ＝５の場合の量子回路のステップＳ５を例示する図。
【図６】ＣＮＯＴを示す図。
【図７】Ｔｏｆｆｏｌｉを示す図。
【図８】ＮＯＴを示す図。
【図９】ＳＷＡＰを示す図。
【図１０】ＭＡＪを示す図。
【図１１】ＵＭＡを示す図。
【図１２】ＭＡＪ２を示す図。
【図１３】ＵＭＡ２を示す図。
【図１４】ＳＷＡＰ２を示す図。
【図１５】従来技術による２つの二進数の和を演算するための量子回路。
【図１６】ステップＳ１及びステップＳ２の処理を表すフローチャート。
【図１７】ステップＳ３の処理を表すフローチャート。
【図１８】ステップＳ４の処理を表すフローチャート。
【図１９】ステップＳ５の処理を表すフローチャート。
【図２０】量子演算装置の機能ブロックを例示する図
【図２１】ＳＷＡＰ’を示す図。
【図２２】ＣＮＯＴを２回適用する量子回路を示す図。
【図２３】ＵＭＡ３を示す図。
【図２４】ＵＭＡ４を示す図。
【符号の説明】
【００７３】
１     量子演算装置
９     制御部
１０   記憶部
１１   ＣＮＯＴ操作部
１２   ＳＷＡＰ操作部
１３   Ｔｏｆｆｏｌｉ操作部
１４   ＭＡＪ２操作部
１５   ＵＭＡ２操作部
１６   ＮＯＴ操作部
１７   ＳＷＡＰ２操作部
【図１】
0005129646.tif 000003
【図２】
0005129646.tif 000004
【図３】
0005129646.tif 000005
【図４】
0005129646.tif 000006
【図５】
0005129646.tif 000007
【図６】
0005129646.tif 000008
【図７】
0005129646.tif 000009
【図８】
0005129646.tif 000010
【図９】
0005129646.tif 000011
【図１０】
0005129646.tif 000012
【図１１】
0005129646.tif 000013
【図１２】
0005129646.tif 000014
【図１３】
0005129646.tif 000015
【図１４】
0005129646.tif 000016
【図１５】
0005129646.tif 000017
【図１６】
0005129646.tif 000018
【図１７】
0005129646.tif 000019
【図１８】
0005129646.tif 000020
【図１９】
0005129646.tif 000021
【図２０】
0005129646.tif 000022
【図２１】
0005129646.tif 000023
【図２２】
0005129646.tif 000024
【図２３】
0005129646.tif 000025
【図２４】
0005129646.tif 000026