(57)【特許請求の範囲】
【請求項１】
整数N, bと生成元aとが与えられたときにat=b mod Nを満たす整数tを求める離散対数問題を解くための量子演算装置であって、
d（d≧2）個の基底を構成するn（n≧1）個の第１量子ビットからなる第１量子レジスタの量子状態を基底状態に初期化し、d個の基底を構成するn個の第２量子ビットからなる第２量子レジスタの量子状態を基底状態に初期化する初期化部と、
上記第１量子レジスタの量子状態を
A1・Σj=0d-1|j>
の量子重ね合わせ状態（ただし、A1≠0）とする量子重ね合わせ状態生成部と、
上記第１量子レジスタと上記第２量子レジスタとの量子状態を
【数１】
0005118461.tif 000039
（ただし、A2≠0、αは０以上の整数）の量子絡み合い状態とする制御演算部と、
上記第１量子レジスタに対し、量子状態
【数２】
0005118461.tif 000040
を量子状態|x>に変換する逆２次位相変換演算（ただし、τ=-exp(π・i/d)であり、iは虚数単位であり、βは有理数）を施す逆２次位相変換演算部と、
少なくとも上記第１量子レジスタの量子状態を観測し、その観測結果を出力する観測部と、
を有することを特徴とする量子演算装置。
【請求項２】
請求項１に記載の量子演算装置であって、
(A)  n≧3及びd=2nを満たし、上記第１量子レジスタをなすn個の第１量子ビットを量子ビットQ1,...,Qnとし、βをｄとの最大公約数が１である１以上の整数とし、nが奇数である場合のεを(n-3)/2とし、nが偶数である場合のεを(n-4)/2とし、wを0≦w≦εの整数とし、τw=-exp(π・i/2(n-2w))とし、
(B)  量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh2|0>+h1|1>に変換する処理をNOT演算Xとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を-i・h2|0>-i・h1|1>に変換する処理を逆複素NOT演算-iXとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>-h2|1>に変換する処理をパウリ変換演算Zとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>+θ・h2|1>に変換する処理を位相変換演算Z(θ)とし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>+i・h2|1>に変換する処理を位相変換演算Sとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1+h2)/√2}|0>+{(h1-h2)/√2}|1>に変換する処理をアダマール変換演算Hとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1+h2(-1+√2))/(2√2)}|0>+{(-h1+h2(1+√2))/(2√2)}|1>に変換する処理を変換演算Θ1とし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1(1+√2)+h2(1-√2))/(2√2)}|0>+{(h1+h2)/(2√2)}|1>に変換する処理を変換演算Θ2とし、量子状態がh1|00>-h2|01>+h3|10>+τw-2/β・h4|11>である２つの量子ビットの量子状態をh1|00>+h2|01>+h3|10>+h4|11>に変換する制御演算を制御演算{Sw(0)}-1とし、
(C)  上記逆２次位相変換演算部は、
量子ビットQ1+wを制御ビットとし、量子ビットQn-wを目標ビットとし、量子ビットQ1+wの量子状態|0>に対して量子ビットQn-wの量子状態を維持し、量子ビットQ1+wの量子状態|1>に対して量子ビットQn-wにパウリ変換演算Zをα回施す制御パウリ変換演算部と、
量子ビットQ1+wに対してアダマール変換演算Hを施す第１アダマール変換部と、
量子ビットQ1+wを制御ビットとし、量子ビットQκ+1+w（κ=1,...,n-2w-2，κは整数）を目標ビットとし、量子ビットQ1+wの量子状態|0>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）の量子状態を維持し、量子ビットQ1+wの量子状態|1>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）に
【数３】
0005118461.tif 000041
の演算を施す第１制御R演算部と、
量子ビットQn-wを制御ビットとし、量子ビットQκ+1+w（κ=1,...,n-2w-2）を目標ビットとし、量子ビットQn-wの量子状態|0>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）の量子状態を維持し、量子ビットQn-wの量子状態|1>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）に
【数４】
0005118461.tif 000042
の逆演算を施す第２制御R演算部と、
量子ビットQn-wに対して位相変換演算Z(i・τwα/β)の逆演算を施す第１位相変換演算部と、
量子ビットQn-w-1に対してパウリ変換演算Zをα回施すパウリ変換演算部と、
量子ビットQ2+w,...,Qn-w-1に対し再帰演算Vw+1を施す再帰的演算制御部と、
量子ビットQn-wを制御ビットとし、量子ビットQκ+1+w（κ=1,...,n-2w-2）を目標ビットとし、量子ビットQn-wの量子状態|0>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）の量子状態を維持し、量子ビットQn-wの量子状態|1>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）にRwの演算を施す第３制御R演算部と、
量子ビットQ1+wに対して位相変換演算Sの逆演算を施す第２位相変換演算部と、
量子ビットQn-wを制御ビットとし、量子ビットQ1+wを目標ビットとし、量子ビットQn-w，Q1+wに対して制御演算{Sw(0)}-1を施す制御逆Sw(0)演算部と、
量子ビットQ1+wを制御ビットとし、量子ビットQn-wを目標ビットとし、量子ビットQ1+wの量子状態|0>に対して量子ビットQn-wの量子状態を維持し、量子ビットQ1+wの量子状態|1>に対して量子ビットQn-wに逆複素NOT演算-iXを施す制御逆複素NOT演算部と、
量子ビットQ1+wに対してアダマール変換演算Hを施す第２アダマール変換部と、
量子ビットQ1+wに対してNOT演算Xを施すNOT演算部と、を含み、
(D)  ０以上ε以下の整数wに対する再帰演算Vwが、
整数wについてなされた上記制御パウリ変換演算部と上記第１アダマール変換部と上記第１制御R演算部と上記第２制御R演算部と上記第１位相変換演算部と上記パウリ変換演算部と上記再帰的演算制御部と上記第３制御R演算部と上記第２位相変換演算部と上記制御逆Sw(0)演算部と上記制御逆複素NOT演算部と上記第２アダマール変換部と上記NOT演算部とによる演算であり、
(E)  nが奇数である場合の再帰演算Vε+1が、
量子ビットQ2+εに対し、α回のパウリ変換演算Zと、μ=α・2ｎ-1／βとした場合の位相変換演算Z(τ0μ) と、変換演算Θ1と、μ=2ｎ／βとした場合の位相変換演算Z(τ0μ) と、変換演算Θ2とを施す演算であり、
(F)  nが偶数である場合の再帰演算Vε+1が、
量子ビットQ2+εを制御ビットとし、量子ビットQ3+εを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQ3+εの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対して量子ビットQ3+εにパウリ変換演算Zをα回施す制御演算と、
量子ビットQ2+εに対するアダマール変換演算Hと位相変換演算Sと、
量子ビットQ3+εに対するμ=α・2ｎ-2／βとした場合の位相変換演算Z(τ0μ) と位相変換演算Sと、
量子ビットQ3+εを制御ビットとし、量子ビットQ2+εを目標ビットとし、量子ビットQ3+εの量子状態|0>に対して量子ビットQ2+εの量子状態を維持し、量子ビットQ3+εの量子状態|1>に対して位相変換演算Z(-τ(n-2)/22/β)を量子ビットQ2+εに施す制御演算と、
量子ビットQ3+εに対するパウリ変換演算Zと、
量子ビットQ2+εを制御ビットとし、量子ビットQ3+εを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQ3+εの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対して量子ビットQ3+εに逆複素NOT演算-iXを施す制御演算と、
量子ビットQ2+εに対するアダマール変換演算HとNOT演算Xと、
を行う演算であり、
(G)  上記逆２次位相変換演算が、w=0における再帰演算V0である、
ことを特徴とする量子演算装置。
【請求項３】
請求項１に記載の量子演算装置であって、
(A)  n≧3及びd=2nを満たし、上記第１量子レジスタをなすn個の第１量子ビットを量子ビットQ1,...,Qnとし、上記第２量子レジスタをなすn個の第２量子ビットを量子ビットQn+1,...,Q2nとし、αを１以上の整数とし、nが奇数である場合のεを(n-3)/2とし、nが偶数である場合のεを(n-4)/2とし、wを0≦w≦εの整数とし、
(B)  量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh2|0>+h1|1>に変換する処理をNOT演算Xとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を-i・h2|0>-i・h1|1>に変換する処理を逆複素NOT演算-iXとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>-h2|1>に変換する処理をパウリ変換演算Zとし、量子状態がh1|0>+ h2|1>である１つの量子ビットの量子状態をh1|0>+ i・h2|1>に変換する処理を位相変換演算Sとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1+h2)/√2}|0>+{(h1-h2)/√2}|1>に変換する処理をアダマール変換演算Hとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1+h2(-1+√2))/(2√2)}|0>+{(-h1+h2(1+√2))/(2√2)}|1>に変換する処理を変換演算Θ1とし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1(1+√2)+h2(1-√2))/(2√2)}|0>+{(h1+h2)/(2√2)}|1>に変換する処理を変換演算Θ2とし、n個の量子ビットの量子状態|y>を量子状態|xρ・y mod N>に変換するユニタリ変換をUx,Nρとし、
(C)  上記逆２次位相変換演算部は、
量子ビットQ1+wを制御ビットとし、量子ビットQn-wを目標ビットとし、量子ビットQ1+wの量子状態|0>に対して量子ビットQn-wの量子状態を維持し、量子ビットQ1+wの量子状態|1>に対して量子ビットQn-wにパウリ変換演算Zをα回施す制御パウリ変換演算部と、
量子ビットQ1+wに対してアダマール変換演算Hを施す第１アダマール変換部と、
各κ=1,...,n-2w-2について、２つの量子ビットQ1+w, Qκ+1+wを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、２つの量子ビットQ1+w, Qκ+1+wの何れかの量子状態が|0>である状態に対して量子ビットQn+1,...,Q2nの量子状態を維持し、２つの量子ビットQ1+w, Qκ+1+wの量子状態がともに|1>である状態に対して量子ビットQn+1,...,Q2nにρ=2(n-2w-κ)としたユニタリ変換Ux,Nρを施す処理を行う第１制御R演算部と、
各κ=1,...,n-2w-2について、２つの量子ビットQn-w, Qκ+1+wを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、２つの量子ビットQn-w, Qκ+1+wの何れか量子状態が|0>である状態に対して量子ビットQn+1,...,Q2nの量子状態を維持し、２つの量子ビットQn-w, Qκ+1+wの量子状態がともに|1>である状態に対して量子ビットQn+1,...,Q2nにρ=-α・2(n-2w-κ)としたユニタリ変換Ux,Nρを施す処理を行う第２制御R演算部と、
量子ビットQn-wを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、量子ビットQn-wの量子状態|0>に対して量子ビットQn+1,...,Q2nの量子状態を維持し、量子ビットQn-wの量子状態|1>に対して量子ビットQn+1,...,Q2nにユニタリ変換Ux,N-αを施す制御演算と、量子ビットQn-wに対するα回のパウリ変換演算Zと、量子ビットQn-wに対する位相変換演算Sとを行う第１位相変換演算部と、
量子ビットQn-w-1に対してパウリ変換演算Zをα回施すパウリ変換演算部と、
量子ビットQ2+w,...,Qn-w-1を制御ビットとし、量子ビットQn+1,...,Q2nを目標ビットとした制御再帰演算U-Vw+1を施す再帰的演算制御部と、
各κ=1,...,n-2w-2について、２つの量子ビットQn-w, Qκ+1+wを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、２つの量子ビットQn-w, Qκ+1+wの何れか量子状態が|0>である状態に対して量子ビットQn+1,...,Q2nの量子状態を維持し、２つの量子ビットQn-w, Qκ+1+wの量子状態がともに|1>である状態に対して量子ビットQn+1,...,Q2nにρ=2(n-2w-κ)としたユニタリ変換Ux,Nρを施す処理を行う第３制御R演算部と、
量子ビットQ1+wに対して位相変換演算Sの逆演算を施す第２位相変換演算部と、
２つの量子ビットQ1+w, Qn-wを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、２つの量子ビットQ1+w, Qn-wの何れか量子状態が|0>である状態に対して量子ビットQn+1,...,Q2nの量子状態を維持し、２つの量子ビットQ1+w, Qn-wの量子状態がともに|1>である状態に対してユニタリ変換Ux,N2を量子ビットQn+1,...,Q2nに施す制御演算と、量子ビットQn-wに対するパウリ変換演算Zとを行う制御逆Sw(0)演算部と、
量子ビットQ1+wを制御ビットとし、量子ビットQn-wを目標ビットとし、量子ビットQ1+wの量子状態|0>に対して量子ビットQn-wの量子状態を維持し、量子ビットQ1+wの量子状態|1>に対して量子ビットQn-wに逆複素NOT演算-iXを施す制御逆複素NOT演算部と、
量子ビットQ1+wに対してアダマール変換演算Hを施す第２アダマール変換部と、
量子ビットQ1+wに対してNOT演算Xを施すNOT演算部と、を含み、
(D)  ０以上ε以下の整数wに対する制御再帰演算U-Vwが、整数wについてなされた上記制御パウリ変換演算部と上記第１アダマール変換部と上記第１制御R演算部と上記第２制御R演算部と上記第１位相変換演算部と上記パウリ変換演算部と上記再帰的演算制御部と上記第３制御R演算部と上記第２位相変換演算部と上記制御逆Sw(0)演算部と上記制御逆複素NOT演算部と上記第２アダマール変換部と上記NOT演算部とによる演算であり、
(E)  nが奇数である場合の制御再帰演算U-Vε+1が、
量子ビットQ2+εに対するα回のパウリ変換演算Zと、
量子ビットQ2+εを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQn+1,...,Q2nの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対してρ=α・2n-1としたユニタリ変換Ux,Nρを量子ビットQn+1,...,Q2nに施す制御演算と、
量子ビットQ2+εに対する変換演算Θ1と、
量子ビットQ2+εを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQn+1,...,Q2nの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対してρ=2nとしたユニタリ変換Ux,Nρを量子ビットQn+1,...,Q2nに施す制御演算と、
量子ビットQ2+εに対する変換演算Θ2と、
を行う演算であり、
(F)  nが偶数である場合の制御再帰演算U-Vε+1が、
量子ビットQ2+εを制御ビットとし、量子ビットQ3+εを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQ3+εの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対して量子ビットQ3+εにパウリ変換演算Zをα回施す制御演算と、
量子ビットQ2+εに対するアダマール変換演算Hと位相変換演算Sと、
量子ビットQ3+εを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、量子ビットQ3+εの量子状態|0>に対して量子ビットQn+1,...,Q2nの量子状態を維持し、量子ビットQ3+εの量子状態|1>に対してρ=α・2n-2としたユニタリ変換Ux,Nρを量子ビットQn+1,...,Q2nに施す制御演算と、
量子ビットQ3+εに対する位相変換演算Sと、
２つの量子ビットQ2+ε, Q3+εを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、２つの量子ビットQ2+ε, Q3+εの何れかの量子状態が|0>である状態に対して量子ビットQn+1,...,Q2nの量子状態を維持し、２つの量子ビットQ2+ε, Q3+εの量子状態がともに|1>である状態に対して量子ビットQn+1,...,Q2nにユニタリ変換Ux,N2を施す制御演算と、
量子ビットQ3+εに対するパウリ変換演算Zと、
量子ビットQ2+εを制御ビットとし、量子ビットQ3+εを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQ3+εの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対して量子ビットQ3+εに逆複素NOT演算-iXを施す制御演算と、
量子ビットQ2+εに対するアダマール変換演算HとNOT演算Xと、
を行う演算であり、
(G)  上記逆２次位相変換演算が、w=0における制御再帰演算U-V0である、
ことを特徴とする量子演算装置。
【請求項４】
請求項１から３の何れかに記載の量子演算装置であって、
上記初期化部は、
上記第１量子レジスタの量子状態を|0>に初期化し、上記第２量子レジスタの量子状態を|1>に初期化し、
上記量子重ね合わせ状態生成部は、
上記第１量子レジスタをなすn個の第１量子ビットのそれぞれに対してアダマール変換を施し、上記量子重ね合わせ状態を生成し、
上記制御演算部は、
上記第１量子ビットを制御ビットとし、上記第２量子ビットを目標ビットとし、上記第１量子レジスタの量子状態A1・Σj=0d-1|j>に応じ、量子状態|y>を量子状態
【数５】
0005118461.tif 000043
を上記第２量子レジスタに施す制御演算を行う第１制御演算部と、
上記第１量子ビットを制御ビットとし、上記第２量子ビットを目標ビットとし、上記第１量子レジスタの量子状態A1・Σj=0d-1|j>に応じ、量子状態|y>を量子状態
【数６】
0005118461.tif 000044
を上記第２量子レジスタに施す制御演算を行う第２制御演算部と、を含む、
ことを特徴とする量子演算装置。
【請求項５】
(A)  nを３以上の整数とし、d=2nとし、iを虚数単位とし、αを０以上の整数とし、βをｄとの最大公約数が１である１以上の整数とし、τ=-exp(π・i/d)とし、nが奇数である場合のεを(n-3)/2とし、nが偶数である場合のεを(n-4)/2とし、wを0≦w≦εの整数とし、τw=-exp(π・i/2(n-2w))とし、
(B)  量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh2|0>+h1|1>に変換する処理をNOT演算Xとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を-i・h2|0>-i・h1|1>に変換する処理を逆複素NOT演算-iXとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>-h2|1>に変換する処理をパウリ変換演算Zとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>+θ・h2|1>に変換する処理を位相変換演算Z(θ)とし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>+i・h2|1>に変換する処理を位相変換演算Sとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1+h2)/√2}|0>+{(h1-h2)/√2}|1>に変換する処理をアダマール変換演算Hとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1+h2(-1+√2))/(2√2)}|0>+{(-h1+h2(1+√2))/(2√2)}|1>に変換する処理を変換演算Θ1とし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1(1+√2)+h2(1-√2))/(2√2)}|0>+{(h1+h2)/(2√2)}|1>に変換する処理を変換演算Θ2とし、量子状態がh1|00>-h2|01>+h3|10>+τw-2/β・h4|11>である２つの量子ビットの量子状態をh1|00>+h2|01>+h3|10>+h4|11>に変換する制御演算を制御演算{Sw(0)}-1とした場合における、
(C)  量子ビットQ1+wを制御ビットとし、量子ビットQn-wを目標ビットとし、量子ビットQ1+wの量子状態|0>に対して量子ビットQn-wの量子状態を維持し、量子ビットQ1+wの量子状態|1>に対して量子ビットQn-wにパウリ変換演算Zをα回施す制御パウリ変換演算部と、
量子ビットQ1+wに対してアダマール変換演算Hを施す第１アダマール変換部と、
量子ビットQ1+wを制御ビットとし、量子ビットQκ+1+w（κ=1,...,n-2w-2）を目標ビットとし、量子ビットQ1+wの量子状態|0>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）の量子状態を維持し、量子ビットQ1+wの量子状態|1>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）に
【数７】
0005118461.tif 000045
の演算を施す第１制御R演算部と、
量子ビットQn-wを制御ビットとし、量子ビットQκ+1+w（κ=1,...,n-2w-2）を目標ビットとし、量子ビットQn-wの量子状態|0>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）の量子状態を維持し、量子ビットQn-wの量子状態|1>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）に
【数８】
0005118461.tif 000046
の逆演算を施す第２制御R演算部と、
量子ビットQn-wに対して位相変換演算Z(i・τwα/β)の逆演算を施す第１位相変換演算部と、
量子ビットQn-w-1に対してパウリ変換演算Zをα回施すパウリ変換演算部と、
量子ビットQ2+w,...,Qn-w-1に対し再帰演算Vw+1を施す再帰的演算制御部と、
量子ビットQn-wを制御ビットとし、量子ビットQκ+1+w（κ=1,...,n-2w-2）を目標ビットとし、量子ビットQn-wの量子状態|0>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）の量子状態を維持し、量子ビットQn-wの量子状態|1>に対して量子ビットQκ+1+w（κ=1,...,n-2w-2）にRwの演算を施す第３制御R演算部と、
量子ビットQ1+wに対して位相変換演算Sの逆演算を施す第２位相変換演算部と、
量子ビットQn-wを制御ビットとし、量子ビットQ1+wを目標ビットとし、量子ビットQn-w，Q1+wに対して制御演算{Sw(0)}-1を施す制御逆Sw(0)演算部と、
量子ビットQ1+wを制御ビットとし、量子ビットQn-wを目標ビットとし、量子ビットQ1+wの量子状態|0>に対して量子ビットQn-wの量子状態を維持し、量子ビットQ1+wの量子状態|1>に対して量子ビットQn-wに逆複素NOT演算-iXを施す制御逆複素NOT演算部と、
量子ビットQ1+wに対してアダマール変換演算Hを施す第２アダマール変換部と、
量子ビットQ1+wに対してNOT演算Xを施すNOT演算部と、を含み、
(D)  ０以上ε以下の整数wに対する再帰演算Vwが、
整数wについてなされた上記制御パウリ変換演算部と上記第１アダマール変換部と上記第１制御R演算部と上記第２制御R演算部と上記第１位相変換演算部と上記パウリ変換演算部と上記再帰的演算制御部と上記第３制御R演算部と上記第２位相変換演算部と上記制御逆Sw(0)演算部と上記制御逆複素NOT演算部と上記第２アダマール変換部と上記NOT演算部とによる演算であり、
(E)  nが奇数である場合の再帰演算Vε+1が、
量子ビットQ2+εに対し、α回のパウリ変換演算Zと、μ=α・2ｎ-1／βとした場合の位相変換演算Z(τ0μ) と、変換演算Θ1と、μ=2ｎ／βとした場合の位相変換演算Z(τ0μ) と、変換演算Θ2とを施す演算であり、
(F)  nが偶数である場合の再帰演算Vε+1が、
量子ビットQ2+εを制御ビットとし、量子ビットQ3+εを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQ3+εの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対して量子ビットQ3+εにパウリ変換演算Zをα回施す制御演算と、
量子ビットQ2+εに対するアダマール変換演算Hと位相変換演算Sと、
量子ビットQ3+εに対するμ=α・2ｎ-2／βとした場合の位相変換演算Z(τwμ) と位相変換演算Sと、
量子ビットQ3+εを制御ビットとし、量子ビットQ2+εを目標ビットとし、量子ビットQ3+εの量子状態|0>に対して量子ビットQ2+εの量子状態を維持し、量子ビットQ3+εの量子状態|1>に対して位相変換演算Z(-τ(n-2)/22/β)を量子ビットQ2+εに施す制御演算と、
量子ビットQ3+εに対するパウリ変換演算Zと、
量子ビットQ2+εを制御ビットとし、量子ビットQ3+εを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQ3+εの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対して量子ビットQ3+εに逆複素NOT演算-iXを施す制御演算と、
量子ビットQ2+εに対するアダマール変換演算HとNOT演算Xと、
を行う演算である、
ことを特徴とする逆２次位相変換演算装置。
【請求項６】
(A)  nを３以上の整数とし、iを虚数単位とし、αを０以上の整数とし、nが奇数である場合のεを(n-3)/2とし、nが偶数である場合のεを(n-4)/2とし、wを0≦w≦εの整数とし、
(B)  量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh2|0>+h1|1>に変換する処理をNOT演算Xとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を-i・h2|0>-i・h1|1>に変換する処理を逆複素NOT演算-iXとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>-h2|1>に変換する処理をパウリ変換演算Zとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>+i・h2|1>に変換する処理を位相変換演算Sとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1+h2)/√2}|0>+{(h1-h2)/√2}|1>に変換する処理をアダマール変換演算Hとし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1+h2(-1+√2))/(2√2)}|0>+{(-h1+h2(1+√2))/(2√2)}|1>に変換する処理を変換演算Θ1とし、量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1(1+√2)+h2(1-√2))/(2√2)}|0>+{(h1+h2)/(2√2)}|1>に変換する処理を変換演算Θ2とし、n個の量子ビットの量子状態|y>を量子状態|xρ・y mod N>に変換するユニタリ変換をUx,Nρとし、
(C)  量子ビットQ1+wを制御ビットとし、量子ビットQn-wを目標ビットとし、量子ビットQ1+wの量子状態|0>に対して量子ビットQn-wの量子状態を維持し、量子ビットQ1+wの量子状態|1>に対して量子ビットQn-wにパウリ変換演算Zをα回施す制御パウリ変換演算部と、
量子ビットQ1+wに対してアダマール変換演算Hを施す第１アダマール変換部と、
各κ=1,...,n-2w-2について、２つの量子ビットQ1+w, Qκ+1+wを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、２つの量子ビットQ1+w, Qκ+1+wの何れか量子状態が|0>である状態に対して量子ビットQn+1,...,Q2nの量子状態を維持し、２つの量子ビットQ1+w, Qκ+1+wの量子状態がともに|1>である状態に対して量子ビットQn+1,...,Q2nにρ=2(n-2w-κ)としたユニタリ変換Ux,Nρを施す処理を行う第１制御R演算部と、
各κ=1,...,n-2w-2について、２つの量子ビットQn-w, Qκ+1+wを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、２つの量子ビットQn-w, Qκ+1+wの何れか量子状態が|0>である状態に対して量子ビットQn+1,...,Q2nの量子状態を維持し、２つの量子ビットQn-w, Qκ+1+wの量子状態がともに|1>である状態に対して量子ビットQn+1,...,Q2nにρ=-α・2(n-2w-κ)としたユニタリ変換Ux,Nρを施す処理を行う第２制御R演算部と、
量子ビットQn-wを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、量子ビットQn-wの量子状態|0>に対して量子ビットQn+1,...,Q2nの量子状態を維持し、量子ビットQn-wの量子状態|1>に対して量子ビットQn+1,...,Q2nにユニタリ変換Ux,N-αを施す制御演算と、量子ビットQn-wに対するα回のパウリ変換演算Zと、量子ビットQn-wに対する位相変換演算Sとを行う第１位相変換演算部と、
量子ビットQn-w-1に対してパウリ変換演算Zをα回施すパウリ変換演算部と、
量子ビットQ2+w,...,Qn-w-1を制御ビットとし、量子ビットQn+1,...,Q2nを目標ビットとした制御再帰演算U-Vw+1を施す再帰的演算制御部と、
各κ=1,...,n-2w-2について、２つの量子ビットQn-w, Qκ+1+wを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、２つの量子ビットQn-w, Qκ+1+wの何れか量子状態が|0>である状態に対して量子ビットQn+1,...,Q2nの量子状態を維持し、２つの量子ビットQn-w, Qκ+1+wの量子状態がともに|1>である状態に対して量子ビットQn+1,...,Q2nにρ=2(n-2w-κ)としたユニタリ変換Ux,Nρを施す処理を行う第３制御R演算部と、
量子ビットQ1+wに対して位相変換演算Sの逆演算を施す第２位相変換演算部と、
２つの量子ビットQ1+w, Qn-wを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、２つの量子ビットQ1+w, Qn-wの何れか量子状態が|0>である状態に対して量子ビットQn+1,...,Q2nの量子状態を維持し、２つの量子ビットQ1+w, Qn-wの量子状態がともに|1>である状態に対してユニタリ変換Ux,N2を量子ビットQn+1,...,Q2nに施す制御演算と、量子ビットQn-wに対するパウリ変換演算Zとを行う制御逆Sw(0)演算部と、
量子ビットQ1+wを制御ビットとし、量子ビットQn-wを目標ビットとし、量子ビットQ1+wの量子状態|0>に対して量子ビットQn-wの量子状態を維持し、量子ビットQ1+wの量子状態|1>に対して量子ビットQn-wに逆複素NOT演算-iXを施す制御逆複素NOT演算部と、
量子ビットQ1+wに対してアダマール変換演算Hを施す第２アダマール変換部と、
量子ビットQ1+wに対してNOT演算Xを施すNOT演算部と、を含み、
(D)  ０以上ε以下の整数wに対する制御再帰演算U-Vwが、
整数wについてなされた上記制御パウリ変換演算部と上記第１アダマール変換部と上記第１制御R演算部と上記第２制御R演算部と上記第１位相変換演算部と上記パウリ変換演算部と上記再帰的演算制御部と上記第３制御R演算部と上記第２位相変換演算部と上記制御逆Sw(0)演算部と上記制御逆複素NOT演算部と上記第２アダマール変換部と上記NOT演算部とによる演算であり、
(E)  nが奇数である場合の制御再帰演算U-Vε+1が、
量子ビットQ2+εに対するα回のパウリ変換演算Zと、
量子ビットQ2+εを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQn+1,...,Q2nの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対してρ=α・2n-1としたユニタリ変換Ux,Nρを量子ビットQn+1,...,Q2nに施す制御演算と、
量子ビットQ2+εに対する変換演算Θ1と、
量子ビットQ2+εを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQn+1,...,Q2nの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対してρ=2nとしたユニタリ変換Ux,Nρを量子ビットQn+1,...,Q2nに施す制御演算と、
量子ビットQ2+εに対する変換演算Θ2と、
を行う演算であり、
(F)  nが偶数である場合の制御再帰演算U-Vε+1が、
量子ビットQ2+εを制御ビットとし、量子ビットQ3+εを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQ3+εの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対して量子ビットQ3+εにパウリ変換演算Zをα回施す制御演算と、
量子ビットQ2+εに対するアダマール変換演算Hと位相変換演算Sと、
量子ビットQ3+εを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、量子ビットQ3+εの量子状態|0>に対して量子ビットQn+1,...,Q2nの量子状態を維持し、量子ビットQ3+εの量子状態|1>に対してρ=α・2n-2としたユニタリ変換Ux,Nρを量子ビットQn+1,...,Q2nに施す制御演算と、
量子ビットQ3+εに対する位相変換演算Sと、
２つの量子ビットQ2+ε, Q3+εを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、２つの量子ビットQ2+ε, Q3+εの何れかの量子状態が|0>である状態に対して量子ビットQn+1,...,Q2nの量子状態を維持し、２つの量子ビットQ2+ε, Q3+εの量子状態がともに|1>である状態に対して量子ビットQn+1,...,Q2nにユニタリ変換Ux,N2を施す制御演算と、
量子ビットQ3+εに対するパウリ変換演算Zと、
量子ビットQ2+εを制御ビットとし、量子ビットQ3+εを目標ビットとし、量子ビットQ2+εの量子状態|0>に対して量子ビットQ3+εの量子状態を維持し、量子ビットQ2+εの量子状態|1>に対して量子ビットQ3+εに逆複素NOT演算-iXを施す制御演算と、
量子ビットQ2+εに対するアダマール変換演算HとNOT演算Xと、
を行う演算である、
ことを特徴とする逆２次位相変換演算装置。
【請求項７】
整数N, bと生成元aとが与えられたときにat=b mod Nを満たす整数tを求める離散対数問題を解くための量子演算方法であって、
初期化部が、d（d≧2）個の基底を構成するn個の第１量子ビットからなる第１量子レジスタの量子状態を基底状態に初期化し、d個の基底を構成するn個の第２量子ビットからなる第２量子レジスタの量子状態を基底状態に初期化する初期化過程と、
量子重ね合わせ状態生成部が、上記第１量子レジスタの量子状態を
A1・Σj=0d-1|j>
の量子重ね合わせ状態（ただし、A1≠0）とする量子重ね合わせ状態生成過程と、
制御演算部が、上記第１量子レジスタと上記第２量子レジスタとの量子状態を
【数９】
0005118461.tif 000047
（ただし、A2≠0、αは０以上の整数）の量子絡み合い状態とする制御演算過程と、
逆２次位相変換演算部が、上記第１量子レジスタに対し、量子状態
【数１０】
0005118461.tif 000048
を量子状態|x>に変換する逆２次位相変換演算（ただし、τ=-exp(π・i/d)であり、iは虚数単位であり、βは有理数）を施す逆２次位相変換演算過程と、
観測部が、少なくとも上記第１量子レジスタの量子状態を観測し、その観測結果を出力する観測過程と、
を有することを特徴とする量子演算方法。
【請求項８】
請求項１から４の何れかに記載の量子演算装置の制御に必要な処理をコンピュータに実行させるためのプログラム。
【請求項９】
請求項５又は６に記載の逆２次位相変換演算装置の制御に必要な処理をコンピュータに実行させるためのプログラム。
【請求項１０】
請求項８又は９に記載のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子演算技術に関し、特に、離散対数問題の解を効率的に求める量子演算技術に関する。
【背景技術】
【０００２】
量子計算の古典計算に対する優位性を示す強い根拠として常に引き合いに出されるのが、ショーアのアルゴリズムである（例えば、非特許文献１参照）。１９９４年に発表されて以来、ショーアのアルゴリズムは量子アルゴリズムの手本として、研究の対象とされてきた。この１０数年間で、ショーアのアルゴリズム以外にも古典計算に対して指数的に速い量子アルゴリズムは見つかっている。にもかかわらずショーアのアルゴリズムが重要な研究対象と位置付けられている理由として、このアルゴリズムが単に古典計算に比べて指数的に高速なだけではなく、このアルゴリズムの応用範囲の広さが挙げられる。ショーアのアルゴリズムが対象とする問題群は「隠れ部分群問題」として定式化でき、可換群と非可換群の一部とに対する隠れ部分群問題は、ショーアのアルゴリズムを用いることによって多項式時間で解けることが知られている。因数分解問題や離散対数問題など、公開鍵暗号を構成する重要な難問が可換群上の隠れ部分群問題に帰着できる。また、重要な基本問題の一つとして知られるグラフ同型問題は、非可換群上の隠れ部分群問題に帰着できる。このように重要問題の多くがショーアのアルゴリズムの対象に含まれ、その適用範囲の広さは研究に対する大きなモチベーションとなっている。
【０００３】
因数分解を解くショーアのアルゴリズムでは、２つの量子レジスタ（第１，２量子レジスタ）を用い、各量子レジスタを構成する量子ビットに対し、アダマール変換〔ウォルシュ−アダマール（Walsh-Hadamard）変換〕と、べき乗剰余演算と、量子フーリエ変換とを行う。なお、量子レジスタとは、複数の量子ビットからなる量子ビット群のことである。このアルゴリズムでアダマール変換を第１量子レジスタの量子ビットに施し、べき乗剰余演算を第２量子レジスタの量子ビットに施すと、第１レジスタの量子ビットの量子状態は周期的になる。因数分解問題を解くためには、この周期に関する情報が必要となる。しかし、これらの量子状態を普通に観測しても、この周期を求めることはできない。ショーアのアルゴリズムでは、さらに第１レジスタの量子ビットに対して量子フーリエ変換を施し、第１レジスタの周期を効率的に求める。
【０００４】
図１（ａ）は、非特許文献１に示された周期計算を行う量子回路を示した図である。
この量子回路ではx (mod n)で示される乗法群の位数r（周期に関する情報）を求める。すなわち、xr≡1(mod n)を満たす最小のrを求める。
【０００５】
まず、n2≦q≦2・n2を満たすq(=2L, Lは整数)を設定する。また、第１，第２量子レジスタの量子ビットの量子状態を｜0＞に初期化し、これらの量子状態を
|0>|0>  …(1)
とする。
【０００６】
次に、第１量子レジスタの量子ビットにアダマール変換を施し、これらの量子ビットの量子状態を重ね合わせ状態にし、第１，２量子レジスタに保存された量子状態を
【数１１】
0005118461.tif 000002
とする。
【０００７】
次に、量子並列性を利用し、第２量子レジスタの量子ビットを用い、すべてのa (mod q)に対するべき乗剰余演算xa (mod n)を１ステップで行い、その演算結果を示す量子状態を第２量子レジスタに保存する。これにより、第１，２量子レジスタに保存された量子状態は、
【数１２】
0005118461.tif 000003
となる。
【０００８】
次に、第１量子レジスタの量子ビットに基底qの量子フーリエ変換を施す。なお、基底qの量子フーリエ変換は、量子状態|a>を量子状態
【数１３】
0005118461.tif 000004
に写像する演算を意味する。なお、iは虚数単位を意味し、exp(i・θ)は、ガウス平面の単位円上の点cosθ+ i・sinθを意味する。また、この量子フーリエ変換を行列表現すると
【数１４】
0005118461.tif 000005
のユニタリ行列となる。なお、ωはω=exp(2・π・i/q)である（１のｑ乗根）。
【０００９】
このような量子フーリエ変換により、第１，２量子レジスタに保存された量子状態は、
【数１５】
0005118461.tif 000006
となる。
【００１０】
その後、第１，２量子レジスタに保存された量子状態を観測する。ここで、観測される量子状態が|c, xk (mod n)>（ただし、0≦k＜q）となる確率は、
【数１６】
0005118461.tif 000007
はxa≡xk(mod n)を満たすa(0≦a＜q)についてのα(a)の総和を意味し、|α|はαの絶対値を意味する。
【００１１】
ここで、xa≡xk(mod n)を満たす場合、位数rに対してxa≡xk+b・r(mod n)（bは整数）を満たすため
a=b・r+k  …(8)
の関係を満たす。式(8)を式(7)に代入すると、
【数１７】
0005118461.tif 000008
【００１２】
ここで、exp(2・π・i・k・c/q)の項はbによらず一定であるため無視すると、式(9)は
【数１８】
0005118461.tif 000009
となる。
【００１３】
この確率がピークになるのは、整数zに対して
r・c/q=z  …(11)
となるときである。一方、式(11)を満たさない場合、量子フーリエ変換の干渉効果により、exp(2・π・i・b・r・c/q)の項は相互に打ち消し合い、式(10)で表される確率は非常に小さくなる。すなわち、上述の観測において観測されやすい量子状態|c, xk (mod n)>は、式(11)の関係を満たす量子状態である。すなわち、
c/q=z/r  …(12)
の関係を満たす量子状態である。ここでもし、整数zと位数rとの最大公約数gcd(z,r)=1であれば、
r=q/gcd(c,q)   …(13)
によって位数rを求めることができる。また、必ずしもgcd(z,r)=1となるとは限らないが、算出された位数rが正しか否かは容易に検証可能である。そのため、算出された位数rが正しくないときに同様な処理を再度行うことによって正しい位数rを算出できる確率をいくらでも１００％に近づけることができる。
【００１４】
また、ショーアは非特許文献１で離散対数問題を解くアルゴリズムも示している。離散対数問題は公開鍵暗号の安全性の根拠となる問題であり、それが効率的に解けることを示したことは、大きなインパクトをもたらした。因数分解問題と異なり、離散対数問題では量子レジスタを３つ使用し、第１量子レジスタと第２量子レジスタで量子フーリエ変換を実行する。
【００１５】
図１（ｂ）は、非特許文献１に示された離散対数問題を効率的に解く量子回路を示した図である。
【００１６】
この量子回路では、素数pと整数x (0＜x＜p)と乗法群の生成元gとが与えられたときに、
gr≡x (mod p)   …(14)
を満たす整数r(0≦r＜p-1)を求める。
【００１７】
まず、第１〜３量子レジスタの量子状態を｜0＞に初期化し、これらの量子状態を
|0>|0>|0>  …(15)
とする。
【００１８】
次に、第１，２量子レジスタの量子ビットにそれぞれアダマール変換を施して重ね合わせ状態とし、さらに、第３量子レジスタの量子ビットに対し、各a,bに対応するga・x-b (mod n)の演算を行い、各量子状態を
【数１９】
0005118461.tif 000010
とする。
【００１９】
次に、第１，第２量子レジスタの量子ビットに対して基底p-1の量子フーリエ変換を施し、各量子状態を
【数２０】
0005118461.tif 000011
とする。
【００２０】
そして、これらの量子状態を観測する。この観測によってy≡gk (mod p)を満たす量子状態|c,d,y>が観測される確率は、a-r・b≡k (mod p-1)を満たす全ての(a,b)に関する総和
【数２１】
0005118461.tif 000012
である。ここで、a=k+r・b+s(p-1)（sは整数）の関係を用いて式(18)を変換すると、
【数２２】
0005118461.tif 000013
となる。この確率が最大となるのは
d≡-r・c (mod p-1)   …(20)
のときであり、その最大値は1/(p-1)2である。その他の場合は、演算の干渉効果により確率０となる。そして、gcd(c, p-1)=1であれば第１，第２量子レジスタの観測結果c, dと式(20)とにより、式(14)を満たす整数rを算出できる。また、必ずしもgcd(c, p-1)=1となるとは限らないが、算出された整数rが正しか否かは容易に検証可能である。そのため、算出された整数rが正しくないときに同様な処理を再度行うことによって正しい整数rを算出できる確率をいくらでも１００％に近づけることができる。
【非特許文献１】Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM J. Sci. Statist. Comput. 26 (1997).
【特許文献１】特開２００６−１９５５８７
【発明の開示】
【発明が解決しようとする課題】
【００２１】
しかし、非特許文献１の離散対数問題を解くアルゴリズムでは３つの量子レジスタを必要とし、必要となる量子レジスタの数が多いという問題点がある。
【００２２】
本発明はこのような点に鑑みてなされたものであり、非特許文献１の離散対数問題を解くアルゴリズムよりも少ない量子レジスタで離散対数問題を解くことが可能な量子演算技術を提供することを目的とする。
【課題を解決するための手段】
【００２３】
本発明では整数N, bと生成元aとが与えられたときにat=b mod Nを満たす整数tを求める離散対数問題を解く。そのために、まず、d（d≧2）個の基底を構成するn（n≧1）個の第１量子ビットからなる第１量子レジスタの量子状態を基底状態に初期化し、d個の基底を構成するn個の第２量子ビットからなる第２量子レジスタの量子状態を基底状態に初期化する。次に、第１量子レジスタの量子状態を
A1・Σj=0d-1|j>  …(21)
の量子重ね合わせ状態（ただし、A1≠0）とする。さらに、第１量子レジスタと第２量子レジスタとの量子状態を
【数２３】
0005118461.tif 000014
（ただし、A2≠0、αは０以上の整数）の量子絡み合い状態とし、第１量子レジスタに対し、量子状態
【数２４】
0005118461.tif 000015
を量子状態|x>に変換する逆２次位相変換演算（ただし、τ=-exp(π・i/d)であり、iは虚数単位であり、βは有理数）を施す。そして、少なくとも第１量子レジスタの量子状態を観測し、その観測結果を出力する。
【００２４】
ここで、後述のように、式（２２）の
【数２５】
0005118461.tif 000016
の部分は、y=j, x=tとした場合の式（２３）で表現できる。よって、βの値が適切であった場合には、式（２２）の量子状態の第１量子レジスタに対して式（２３）の逆２次位相変換演算を行い、第１量子レジスタを観測することにより、離散対数問題at=b mod Nの解tを求めることができる。
【発明の効果】
【００２５】
本発明では、非特許文献１の離散対数問題を解くアルゴリズムよりも少ない量子レジスタで離散対数問題を解くことが可能となる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
【００２７】
〔定義〕
まず、記号・用語を定義する。
量子レジスタ：複数の量子ビットの集合
Q1,...,Qn：第１量子レジスタを構成するn個の第１量子ビット
Qn+1,...,Q2n：第２量子レジスタを構成するn個の第２量子ビット
ｄ：n個の量子ビットが構成する基底の数
ａ：x mod Nからなる乗法群の生成元
ｂ：x mod Nからなる乗法群の元である整数
Ｎ：整数
α：α≧０を満たす整数
τ：τ=-exp(π・i/d)
ｉ：虚数単位
τｗ：τw=-exp(π・i/2(n-2w))
ｗ：0≦w≦εを満たす整数
ε：nが奇数である場合にはε=(n-3)/2、nが偶数である場合にはε=(n-4)/2
Ｘ：量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh2|0>+h1|1>に変換する処理をNOT演算
【００２８】
【数２６】
0005118461.tif 000017
-iX：量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をi・h2|0>-i・h1|1>に変換する処理を逆複素NOT演算
【００２９】
【数２７】
0005118461.tif 000018
Z：量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>-h2|1>に変換する処理をパウリ変換演算Z
【００３０】
【数２８】
0005118461.tif 000019
Z(θ)：量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>+θ・h2|1>に変換する処理を位相変換演算
【００３１】
【数２９】
0005118461.tif 000020
S：量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態をh1|0>+i・h2|1>に変換する処理を位相変換演算
【００３２】
【数３０】
0005118461.tif 000021
H：量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1+h2)/√2}|0>+{(h1-h2)/√2}|1>に変換する処理をアダマール変換演算
【００３３】
【数３１】
0005118461.tif 000022
Θ1：量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1+h2(-1+√2))/(2√2)}|0>+{(-h1+h2(1+√2))/(2√2)}|1>に変換する処理
【００３４】
【数３２】
0005118461.tif 000023
Θ2：量子状態がh1|0>+h2|1>である１つの量子ビットの量子状態を{(h1(1+√2)+h2(1-√2))/(2√2)}|0>+{(h1+h2)/(2√2)}|1>に変換する処理
【００３５】
【数３３】
0005118461.tif 000024
Sw(0)：量子状態がh1|00>+h2|01>+h3|10>+h4|11>である２つの量子ビットの量子状態をh1|00>-h2|01>+h3|10>+τw-2/β・h4|11>に変換する制御演算
【００３６】
【数３４】
0005118461.tif 000025
{Sw(0)}-1：量子状態がh1|00>-h2|01>+h3|10>+τw-2/β・h4|11>である２つの量子ビットの量子状態をh1|00>+h2|01>+h3|10>+h4|11>に変換する制御演算
Ux,Nρ：n個の量子ビットの量子状態|y>を量子状態|xρ・y mod N>に変換するユニタリ変換
【００３７】
〔第１実施形態〕
次に、本発明の第１実施形態を説明する。
本形態では、前述のように、d（d≧2）個の基底を構成するn（n≧1）個の第１量子ビットからなる第１量子レジスタの量子状態を基底状態に初期化し、d個の基底を構成するn個の第２量子ビットからなる第２量子レジスタの量子状態を基底状態に初期化する。次に、第１量子レジスタの量子状態を式（２１）の量子重ね合わせ状態とする。さらに、第１量子レジスタと第２量子レジスタとの量子状態を式（２２）の量子絡み合い状態とし、第１量子レジスタに対し、式（２３）で示される逆２次位相変換演算を施す。そして、少なくとも第１量子レジスタの量子状態を観測し、その観測結果を出力する。これにより、βの値が適切であった場合には、離散対数問題at=b mod Nの解tを求めることができる。
【００３８】
本形態では、ｄとの最大公約数が１である１以上のランダムな整数βを選択し、この処理を行う。このようにβを選択した場合、逆２次位相変換演算はユニタリとなる（D. M. Appleby, "SIC-POVMs AND THE EXTENDED CLIFFORD GROUP", arXiv:quant-ph/0412001v2, 17 Jan 2005等（以下「参考文献１」）参照）。ここで、式（２３）で示される逆２次位相変換演算はこのような条件のβに対して周期的であり、４通りの演算にしかならない（「参考文献１」等参照）。そのため、本形態では、１／４程度の確率で正しい解に近い値が算出される。また、求めた解が正しいか否かはat=b mod Nを満たすか否かを古典的に検証することで容易に検証できるため、同様な処理を繰り返すことによって正しい解が算出される確率を限りなく１００％に近づけることができる。なお、量子ビットの準位数に限定はないが、説明の簡略化のため、本形態では２準位の量子ビットを用いた例を説明する。すなわち、以下ではn≧3及びd=2nを満たす場合を例示する。
【００３９】
＜構成＞
図２は、第１実施形態の量子演算装置１の構成を示したブロック図である。また、図３（ａ）は、制御演算部１５の詳細構成を示したブロック図であり、図３（ｂ）は、逆２次位相変換演算部１６の詳細構成を示したブロック図である。
【００４０】
図２に示すように、本形態の量子演算装置１は、d=2n個の基底を構成するn個の第１量子ビットQ1,...,Qnからなる第１量子レジスタ１１と、d個の基底を構成するn個の第２量子ビットQn+1,...,Q2nからなる第２量子レジスタ１２と、初期化部１３と、量子重ね合わせ状態生成部１４と、制御演算部１５と、逆２次位相変換演算部１６と、観測部１７と、量子演算装置１全体を制御する制御部１８とを有する。
【００４１】
また、図３に示すように、本形態の制御演算部１５は、第１制御演算部１５ａと、第２制御演算部１５ｂとを有し、本形態の逆２次位相変換演算部１６は、制御パウリ変換演算部１６ａと、第１アダマール変換部１６ｂと、第１制御R演算部１６ｃと、第２制御R演算部１６ｄと、第１位相変換演算部１６ｅと、パウリ変換演算部１６ｆと、再帰的演算制御部１６ｇと、第３制御R演算部１６ｈと、第２位相変換演算部１６ｉと、制御逆Sw(0)演算部１６ｊと、制御逆複素NOT演算部１６ｋと、第２アダマール変換部１６ｍと、NOT演算部１６ｎとを有する。
【００４２】
なお、量子演算装置１は、制御部１８の制御のもと各処理を実行する。また、量子演算装置１のハードウェア構成例について後述する。
【００４３】
＜処理＞
次に、本形態の処理について説明する。
【００４４】
図４は、第１実施形態の処理の全体を説明するための図である。また、図５は、図４のステップＳ２〜Ｓ４の処理を説明するための量子回路である。さらに、図６は、図５の再帰演算Vw（０≦w≦ε）を説明するための量子回路であり、図７は、演算Rwを説明するための量子回路であり、図８は、演算Rwαを説明するための量子回路である。さらに図９（ａ）は、nが奇数である場合の再帰演算Vε+1を説明するための量子回路であり、図９（ｂ）は、ｎが偶数である場合の再帰演算Vε+1を説明するための量子回路である。以下、これらの図を用いて、本形態の処理を説明する。
【００４５】
図４に示すように、本形態では、まず、初期化部１３が、n個の第１量子ビットQ1,...,Qnからなる第１量子レジスタ１１の量子状態を基底状態|0>に初期化し、d個の基底を構成するn個の第２量子ビットQn+1,...,Q2nからなる第２量子レジスタ１２の量子状態を基底状態|1>に初期化する（ステップＳ１）。この基底状態では、各量子ビットは、量子重ね合わせ状態にも量子絡み合い状態にもなっていない。これにより、第１量子レジスタ１１と第２量子レジスタ１２との量子状態は
|0>|1>
となる。
【００４６】
次に、量子重ね合わせ状態生成部１４が、第１量子レジスタ１１の量子状態を
(1/√d)・Σj=0d-1|j>  …(24)
の量子重ね合わせ状態とする（ステップＳ２）。この処理は、量子重ね合わせ状態生成部１４が、第１量子レジスタ１１を構成するn個の第１量子ビットQ1,...,Qnに対し、それぞれアダマール変換Hを施すことによって成される（図５参照）。なお、式（２４）の例ではA1=1/√dと正規化して表現されているが他の値A1≠0を用いてこの状態が表現されてもよい。
【００４７】
さらに、制御演算部１５が、第１量子レジスタ１１を構成する第１量子ビットQ1,...,Qnを制御ビットとし、第２量子レジスタ１２を構成する第２量子ビットQn+1,...,Q2nを目標ビットとした制御演算により、第１量子レジスタ１１と第２量子レジスタ１２との量子状態を
【数３５】
0005118461.tif 000026
の量子絡み合い状態とする（ステップＳ３）。この処理では、まず、第１制御演算部１５ａが、第１量子ビットQ1,...,Qnを制御ビットとし、第２量子ビットQn+1,...,Q2nを目標ビットとし、第１量子レジスタ１１の量子状態1/√d・Σj=0d-1|j>に応じ、第２量子ビットQn+1,...,Q2nにρ=α・j2とした場合におけるユニタリ変換Ua,Nρを施す制御演算を行い、次に、第２制御演算部１５ｂが、第１量子ビットQ1,...,Qnを制御ビットとし、第２量子ビットQn+1,...,Q2nを目標ビットとし、第１量子レジスタ１１の量子状態1/√d・Σj=0d-1|j>に応じ、第２量子ビットQn+1,...,Q2nにユニタリ変換U(1/b), N2jを施す制御演算を行う（図５参照）。なお、a, b, Nは、それぞれ離散対数問題at=b mod Nを構成するパラメータであり、事前に量子演算装置１に入力され、制御演算部１５に設定された値である。また、当該制御演算は量子重ね合わせ状態の量子ビットに対して成される制御演算であり、その演算結果も重ね合わせ状態となる。また、式（２５）の例ではA2=1/√dと正規化して表現されているが他の値A2≠0を用いてこの状態が表現されてもよい。
【００４８】
ここで、
【数３６】
0005118461.tif 000027
と定義すると、
【数３７】
0005118461.tif 000028
を満たすことが知られている（例えば、Nielsen and Chuang, "Quantum Computation and Quantum Information", Cambridge University Press（以下「参考文献２」）参照）。そして、at=b mod Nを満たすことからa-2・t・j =b-2・j mod Nとおき、k=α・j2-2・t・jとおいて、式（２７）を式（２５）に代入すると、
【００４９】
【数３８】
0005118461.tif 000029
となり、さらにτ=-exp(π・i/d)とすると、
【数３９】
0005118461.tif 000030
となる。これより、第１量子レジスタ１１に対し、量子状態
【数４０】
0005118461.tif 000031
を量子状態|x>に変換する変換を施すことができれば、第１量子レジスタ１１の量子状態を、at=b mod Nを満たす|t>とすることができる。
【００５０】
しかし、sやrの値を知ることはできない。そのため、本形態では、式（３０）の代わりに、逆２次位相変換演算部１６が、第１量子レジスタ１１に対し、量子状態
【数４１】
0005118461.tif 000032
を量子状態|x>に変換する逆２次位相変換演算を施す（ステップＳ４／図５における再帰演算V0）。この逆２次位相変換演算によって正しい解を得るためにはβ-1=2・d・s/rでなければならない。しかし、前述のようにβを選択した場合、この逆２次位相変換演算は４通りの演算にしかならない。そのため、ステップＳ４の逆２次位相変換演算により、第１量子レジスタ１１の量子状態は１／４程度の確率で正しい解に近い量子状態となる。
【００５１】
その後、観測部１７が、第１量子レジスタ１１の量子状態を観測し、その観測結果を出力する（ステップＳ５）。この観測結果は、１／４程度の確率で正しい解tに近い値となる。そして、ステップＳ１〜Ｓ５の処理を繰り返すことによって正しい解が算出される確率を限りなく１００％に近づけることができる。
【００５２】
＜逆２次位相変換演算（ステップＳ４）の詳細＞
本形態の逆２次位相変換演算は、w=0における再帰演算V0である（図５参照）。以下、この再帰演算V0を再帰的に説明する。
【００５３】
［再帰演算Vw（0≦w≦ε，ε=(n-3)/2（奇数n）又はε=(n-4)/2（偶数n））］
図６に示すように、再帰演算Vwでは、まず、制御パウリ変換演算部１６ａ（図３）が、第１量子ビットQ1+wを制御ビットとし、第１量子ビットQn-wを目標ビットとし、第１量子ビットQ1+wの量子状態|0>に対して第１量子ビットQn-wの量子状態を維持し、第１量子ビットQ1+wの量子状態|1>に対して第１量子ビットQn-wに、パウリ変換演算Zをα回施す制御パウリ変換演算を行う。なお、当該制御演算は量子重ね合わせ状態の量子ビットに対して成される制御演算であり、その演算結果も重ね合わせ状態となる。以下の各制御演算についても同様である。
【００５４】
次に、第１アダマール変換部１６ｂが、第１量子ビットQ1+wに対してアダマール変換演算Hを施す。
【００５５】
次に、第１制御R演算部１６ｃが、第１量子ビットQ1+wを制御ビットとし、第１量子ビットQκ+1+w（κ=1,...,n-2w-2）を目標ビットとし、第１量子ビットQ1+wの量子状態|0>に対して第１量子ビットQκ+1+w（κ=1,...,n-2w-2）の量子状態を維持し、第１量子ビットQ1+wの量子状態|1>に対して第１量子ビットQκ+1+w（κ=1,...,n-2w-2）に
【数４２】
0005118461.tif 000033
の演算を施す制御演算を行う（図７参照）。
【００５６】
次に、第２制御R演算部１６ｄが、第１量子ビットQn-wを制御ビットとし、第１量子ビットQκ+1+w（κ=1,...,n-2w-2）を目標ビットとし、第１量子ビットQn-wの量子状態|0>に対して第１量子ビットQκ+1+w（κ=1,...,n-2w-2）の量子状態を維持し、第１量子ビットQn-wの量子状態|1>に対して第１量子ビットQκ+1+w（κ=1,...,n-2w-2）に
【数４３】
0005118461.tif 000034
（図８参照）の逆演算を施す制御演算を行う。
【００５７】
次に、第１位相変換演算部１６ｅが、第１量子ビットQn-wに対して位相変換演算Z(i・τwα/β)の逆演算{Z(i・τwα/β)}-1を施し、パウリ変換演算部１６ｆが、第１量子ビットQn-w-1に対してパウリ変換演算Zをα回施す。
【００５８】
次に、再帰的演算制御部１６ｇが、第１量子ビットQ2+w,...,Qn-w-1に対し再帰演算Vw+1を施す。
【００５９】
次に、第３制御R演算部１６ｈが、第１量子ビットQn-wを制御ビットとし、第１量子ビットQκ+1+w（κ=1,...,n-2w-2）を目標ビットとし、第１量子ビットQn-wの量子状態|0>に対して第１量子ビットQκ+1+w（κ=1,...,n-2w-2）の量子状態を維持し、第１量子ビットQn-wの量子状態|1>に対して第１量子ビットQκ+1+w（κ=1,...,n-2w-2）に式（３２）のRw演算を施す制御演算を行う（図７参照）。
【００６０】
次に、第２位相変換演算部１６ｉが、第１量子ビットQ1+wに対して位相変換演算Sの逆演算S-1を施し、制御逆Sw(0)演算部１６ｊが、第１量子ビットQn-wを制御ビットとし、第１量子ビットQ1+wを目標ビットとし、第１量子ビットQn-w，Q1+wに対して制御演算{Sw(0)}-1を施す。
【００６１】
さらに、制御逆複素NOT演算部１６ｋが、第１量子ビットQ1+wを制御ビットとし、第１量子ビットQn-wを目標ビットとし、第１量子ビットQ1+wの量子状態|0>に対して第１量子ビットQn-wの量子状態を維持し、第１量子ビットQ1+wの量子状態|1>に対して第１量子ビットQn-wに逆複素NOT演算-iXを施す制御演算を施す。
【００６２】
そして、第２アダマール変換部１６ｍが、第１量子ビットQ1+wに対してアダマール変換演算Hを施し、NOT演算部１６ｎが、第１量子ビットQ1+wに対してNOT演算Xを施す。
【００６３】
［nが奇数である場合の再帰演算Vε+1］
図９（ａ）に示すように、nが奇数である場合の再帰演算Vε+1は、第１量子ビットQ2+εに対し、α回のパウリ変換演算Zと、μ=α・2ｎ-1／βとした場合の位相変換演算Z(τ0μ) と、変換演算Θ1と、μ=2ｎ／βとした場合の位相変換演算Z(τ0μ) と、変換演算Θ2とを施す演算である。
【００６４】
［nが偶数である場合の再帰演算Vε+1］
図９（ｂ）に示すように、nが偶数である場合の再帰演算Vε+1は、第１量子ビットQ2+εを制御ビットとし、第１量子ビットQ3+εを目標ビットとし、第１量子ビットQ2+εの量子状態|0>に対して第１量子ビットQ3+εの量子状態を維持し、第１量子ビットQ2+εの量子状態|1>に対して第１量子ビットQ3+εにパウリ変換演算Zをα回施す制御演算と、第１量子ビットQ2+εに対するアダマール変換演算Hと位相変換演算Sと、第１量子ビットQ3+εに対するμ=α・2ｎ-2／βとした場合の位相変換演算Z(τ0μ) と位相変換演算Sと、第１量子ビットQ3+εを制御ビットとし、第１量子ビットQ2+εを目標ビットとし、第１量子ビットQ3+εの量子状態|0>に対して第１量子ビットQ2+εの量子状態を維持し、第１量子ビットQ3+εの量子状態|1>に対して位相変換演算Z(-τ(n-2)/22/β)を第１量子ビットQ2+εに施す制御演算と、第１量子ビットQ3+εに対するパウリ変換演算Zと、第１量子ビットQ2+εを制御ビットとし、第１量子ビットQ3+εを目標ビットとし、第１量子ビットQ2+εの量子状態|0>に対して第１量子ビットQ3+εの量子状態を維持し、第１量子ビットQ2+εの量子状態|1>に対して第１量子ビットQ3+εに逆複素NOT演算-iXを施す制御演算と、第１量子ビットQ2+εに対するアダマール変換演算HとNOT演算Xと、を行う演算である。
【００６５】
〔第２実施形態〕
本形態は第１実施形態の変形例であり、逆２次位相変換演算を工夫することで、βを設定することなく、確実に離散対数問題の解を算出できる例である。
【００６６】
第１実施形態では、sやrの値を知ることはできないため、式（３０）に示す変換の代わりに式（３１）に示す変換を第１量子レジスタ１１に施して離散対数問題の解を求めていた。しかし、図６〜図９に示すように、実際の演算内でsやrの値に関係するβ-1が表れるのは位相変換演算
【数４４】
0005118461.tif 000035
のみであり、以下のような方法をとれば、sやrの値を知ることなく、このような演算が可能となる。以下、その原理を説明する。
【００６７】
図１０（ａ）（ｂ）は、sやrの値を知ることなく、式（３４）の演算が可能となる原理を説明するための図である。
【００６８】
まず、Uをユニタリ変換演算とし、θを|φ>の固有値とすると、図１０（ａ）に示すように、第１量子ビットに対する位相変換演算Z(θ)の結果と、当該第１量子ビットを制御ビットとし、第２量子ビットを目標ビットとし、第２量子ビットの量子状態|φ>に対する制御ユニタリ変換を行なった際の第１量子ビットの量子状態とが等しくなることが広く知られている（例えば、参考文献２等参照）。
【００６９】
また、
【数４５】
0005118461.tif 000036
と定義すると、
【数４６】
0005118461.tif 000037
を満たし、
【数４７】
0005118461.tif 000038
を満たす。すなわち、exp(π・i・s/r)は、ユニタリ変換Ux,Nの固有ベクトル|us>に対する固有値である。
【００７０】
ここで、図１０（ａ）の関係においてθ=-exp(π・i・s/r)=τw1/β，|φ>=|us>，U=Ux,Nとすると、図１０（ｂ）に示す関係が成り立つことが分かる。すなわち、第１量子ビットに対する位相変換演算Z(-exp(π・i・s/r))の結果と、当該第１量子ビットの反転ビットを制御ビットとし、第２量子ビットを目標ビットとし、第２量子ビットの量子状態|us >に対する制御ユニタリ変換Ux,Nを行なった際の第１量子ビットの量子状態とが等しくなることが分かる。すなわち、sやrの値を知ることなく位相変換演算Z(-exp(π・i・s/r))の計算ができる。その結果、式（３０）に示す逆２次位相変換を行なうことができ、正しい解tを求めることができる。
【００７１】
以下、第１実施形態との相違点を中心に、本形態の説明を行う。なお、本形態でもn≧3及びd=2nを満たす場合を例にとって説明する。
【００７２】
＜構成＞
本形態の量子演算装置は、第１実施形態の量子演算装置１（図２）の逆２次位相変換演算部１６を逆２次位相変換演算部１１６に置換した構成である。
【００７３】
図１１は、逆２次位相変換演算部１１６の詳細構成を示したブロック図である。なお、図１１において、第１実施形態と共通する部分については図３（ｂ）と同じ符号を付した。
【００７４】
図１１に示すように、本形態の逆２次位相変換演算部１１６は、制御パウリ変換演算部１６ａと、第１アダマール変換部１６ｂと、第１制御R演算部１１６ｃと、第２制御R演算部１１６ｄと、第１位相変換演算部１１６ｅと、パウリ変換演算部１６ｆと、再帰的演算制御部１１６ｇと、第３制御R演算部１１６ｈと、第２位相変換演算部１６ｉと、制御逆Sw(0)演算部１１６ｊと、制御逆複素NOT演算部１６ｋと、第２アダマール変換部１６ｍと、NOT演算部１６ｎとを有する。
【００７５】
＜処理＞
本形態の処理は、第１実施形態の逆２次位相変換演算（ステップＳ４）の処理を置換したものである。以下、本形態の逆２次位相変換演算の詳細を説明する。図１２は、図４のステップＳ２〜Ｓ４の処理に相当する量子回路である。また、図１３は、図１２の制御再帰演算U-Vw（０≦w≦ε）を説明するための量子回路であり、図１４（ａ）は、nが奇数である場合の制御再帰演算U-Vε+1を説明するための量子回路であり、図１４（ｂ）は、ｎが偶数である場合の制御再帰演算U-Vε+1を説明するための量子回路である。
【００７６】
＜本形態の逆２次位相変換演算の詳細＞
本形態の逆２次位相変換演算は、w=0における制御再帰演算U-V0である（図１２）。以下、この制御再帰演算U-V0を再帰的に説明する。
【００７７】
［制御再帰演算U-Vw（0≦w≦ε，ε=(n-3)/2（奇数n）又はε=(n-4)/2（偶数n））］
まず、制御パウリ変換演算部１６ａが、第１量子ビットQ1+wを制御ビットとし、第１量子ビットQn-wを目標ビットとし、第１量子ビットQ1+wの量子状態|0>に対して第１量子ビットQn-wの量子状態を維持し、第１量子ビットQ1+wの量子状態|1>に対して第１量子ビットQn-wにパウリ変換演算Zをα回施す制御演算を行う（図１３）。
【００７８】
次に、第１アダマール変換部１６ｂが、第１量子ビットQ1+wに対してアダマール変換演算Hを施す。
【００７９】
次に、第１制御R演算部１１６ｃが、各κ=1,...,n-2w-2（κは整数）について、２つの第１量子ビットQ1+w, Qκ+1+wを制御ビットとし、n個の第２量子ビットQn+1,...,Q2nを目標ビットとし、２つの第１量子ビットQ1+w, Qκ+1+wの何れかの量子状態が|0>である状態に対して第２量子ビットQn+1,...,Q2nの量子状態を維持し、２つの第１量子ビットQ1+w, Qκ+1+wの量子状態がともに|1>である状態に対して第２量子ビットQn+1,...,Q2nにρ=2(n-2w-κ)としたユニタリ変換Ux,Nρを施す処理を行う制御演算を行う。
【００８０】
次に、第２制御R演算部１１６ｄが、各κ=1,...,n-2w-2について、２つの第１量子ビットQn-w, Qκ+1+wを制御ビットとし、n個の第２量子ビットQn+1,...,Q2nを目標ビットとし、２つの第１量子ビットQn-w, Qκ+1+wの何れか量子状態が|0>である状態に対して第２量子ビットQn+1,...,Q2nの量子状態を維持し、２つの第１量子ビットQn-w, Qκ+1+wの量子状態がともに|1>である状態に対して第２量子ビットQn+1,...,Q2nにρ=-α・2(n-2w-κ)としたユニタリ変換Ux,Nρを施す処理を行う制御演算を行う。
【００８１】
次に、第１位相変換演算部１１６ｅが、第１量子ビットQn-wを制御ビットとし、n個の第２量子ビットQn+1,...,Q2nを目標ビットとし、第１量子ビットQn-wの量子状態|0>に対して第２量子ビットQn+1,...,Q2nの量子状態を維持し、第１量子ビットQn-wの量子状態|1>に対して第２量子ビットQn+1,...,Q2nにユニタリ変換Ux,N-αを施す制御演算と、第１量子ビットQn-wに対するα回のパウリ変換演算Zと、第１量子ビットQn-wに対する位相変換演算Sとを行う。
【００８２】
次に、パウリ変換演算部１６ｆが、第１量子ビットQn-w-1に対してパウリ変換演算Zをα回施す。
【００８３】
次に、再帰的演算制御部１１６ｇが、第１量子ビットQ2+w,...,Qn-w-1を制御ビットとし、量子ビットQn+1,...,Q2nを目標ビットとした制御再帰演算U-Vw+1を施す。
【００８４】
次に、第３制御R演算部１１６ｈが、各κ=1,...,n-2w-2について、２つの第１量子ビットQn-w, Qκ+1+wを制御ビットとし、n個の第２量子ビットQn+1,...,Q2nを目標ビットとし、２つの第１量子ビットQn-w, Qκ+1+wの何れか量子状態が|0>である状態に対して第２量子ビットQn+1,...,Q2nの量子状態を維持し、２つの第１量子ビットQn-w, Qκ+1+wの量子状態がともに|1>である状態に対して第２量子ビットQn+1,...,Q2nにρ=2(n-2w-κ)としたユニタリ変換Ux,Nρを施す処理を行う。
【００８５】
また、第２位相変換演算部１６ｉが、量子ビットQ1+wに対して位相変換演算Sの逆演算を施す。
【００８６】
次に、制御逆Sw(0)演算部１１６ｊが、２つの第１量子ビットQ1+w, Qn-wを制御ビットとし、n個の第２量子ビットQn+1,...,Q2nを目標ビットとし、２つの第１量子ビットQ1+w, Qn-wの何れか量子状態が|0>である状態に対して第２量子ビットQn+1,...,Q2nの量子状態を維持し、２つの第１量子ビットQ1+w, Qn-wの量子状態がともに|1>である状態に対してユニタリ変換Ux,N2を第２量子ビットQn+1,...,Q2nに施す制御演算と、第１量子ビットQn-wに対するパウリ変換演算Zとを行う。
【００８７】
次に、制御逆複素NOT演算部１６ｋが、第１量子ビットQ1+wを制御ビットとし、第２量子ビットQn-wを目標ビットとし、第１量子ビットQ1+wの量子状態|0>に対して第２量子ビットQn-wの量子状態を維持し、第１量子ビットQ1+wの量子状態|1>に対して第２量子ビットQn-wに逆複素NOT演算-iXを施す。
【００８８】
そして、第２アダマール変換部１６ｍが、量子ビットQ1+wに対してアダマール変換演算Hを施し、NOT演算部１６ｎが、量子ビットQ1+wに対してNOT演算Xを施す。
【００８９】
［nが奇数である場合の制御再帰演算U-Vε+1］
図１４（ａ）に示す通り、nが奇数である場合の制御再帰演算U-Vε+1は、第１量子ビットQ2+εに対するα回のパウリ変換演算Zと、第１量子ビットQ2+εを制御ビットとし、n個の第２量子ビットQn+1,...,Q2nを目標ビットとし、第１量子ビットQ2+εの量子状態|0>に対して第２量子ビットQn+1,...,Q2nの量子状態を維持し、第１量子ビットQ2+εの量子状態|1>に対してρ=α・2n-1としたユニタリ変換Ux,Nρを第２量子ビットQn+1,...,Q2nに施す制御演算と、第１量子ビットQ2+εに対する変換演算Θ1と、第１量子ビットQ2+εを制御ビットとし、n個の量子ビットQn+1,...,Q2nを目標ビットとし、第１量子ビットQ2+εの量子状態|0>に対して第２量子ビットQn+1,...,Q2nの量子状態を維持し、第１量子ビットQ2+εの量子状態|1>に対してρ=2nとしたユニタリ変換Ux,Nρを第２量子ビットQn+1,...,Q2nに施す制御演算と、第１量子ビットQ2+εに対する変換演算Θ2と、を行う演算である。
【００９０】
［nが偶数である場合の制御再帰演算U-Vε+1］
図１４（ｂ）に示す通り、nが偶数である場合の制御再帰演算U-Vε+1は、第１量子ビットQ2+εを制御ビットとし、第１量子ビットQ3+εを目標ビットとし、第１量子ビットQ2+εの量子状態|0>に対して第１量子ビットQ3+εの量子状態を維持し、第１量子ビットQ2+εの量子状態|1>に対して第１量子ビットQ3+εにパウリ変換演算Zをα回施す制御演算と、第１量子ビットQ2+εに対するアダマール変換演算Hと位相変換演算Sと、第１量子ビットQ3+εを制御ビットとし、n個の第２量子ビットQn+1,...,Q2nを目標ビットとし、第１量子ビットQ3+εの量子状態|0>に対して第２量子ビットQn+1,...,Q2nの量子状態を維持し、第１量子ビットQ3+εの量子状態|1>に対してρ=α・2n-2としたユニタリ変換Ux,Nρを第２量子ビットQn+1,...,Q2nに施す制御演算と、第１量子ビットQ3+εに対する位相変換演算Sと、２つの第１量子ビットQ2+ε, Q3+εを制御ビットとし、n個の第２量子ビットQn+1,...,Q2nを目標ビットとし、２つの第１量子ビットQ2+ε, Q3+εの何れかの量子状態が|0>である状態に対して第２量子ビットQn+1,...,Q2nの量子状態を維持し、２つの第１量子ビットQ2+ε, Q3+εの量子状態がともに|1>である状態に対して第２量子ビットQn+1,...,Q2nにユニタリ変換Ux,N2を施す制御演算と、第１量子ビットQ3+εに対するパウリ変換演算Zと、第１量子ビットQ2+εを制御ビットとし、第１量子ビットQ3+εを目標ビットとし、第１量子ビットQ2+εの量子状態|0>に対して第１量子ビットQ3+εの量子状態を維持し、第１量子ビットQ2+εの量子状態|1>に対して第１量子ビットQ3+εに逆複素NOT演算-iXを施す制御演算と、第１量子ビットQ2+εに対するアダマール変換演算HとNOT演算Xと、を行う演算である。
【００９１】
〔ハードウェア構成〕
次に、各実施形態の量子演算装置のハードウェア構成を例示する。
本形態における量子ビットの生成、初期化、量子重ね合わせ状態の生成、量子絡み合い状態の生成、逆２次位相変換、観測等は、すべて量子コンピュータによって実現できる。量子コンピュータの実現する物理系としては、例えば、液体中の各スピンを用いる方法（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）、イオントラップを用いる方法（J. I. Cirac and P. Zoller, Quantum computations with cold trapped ions, Physical Review Letter 74;4091, 1995）、量子ドット中の電子スピンを用いる方法（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-cooperpair box, Nature 393, 786-788, 1999）、光子を用いる方法（Y. Nakamura, M. Kitagawa, K. Igeta, In 3-rd Proc. Asia-Pacific Phys. Comf., World Scientific, Singapore, 1988）等を例示できる。また、それぞれの物理系に対する量子コンピュータの実現方法については、「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（参考文献３）」に記載された方法によって量子ビットが生成されたＳｉ（１１１）基板等を用いることができる。
また、初期化部１３は、例えば、この量子ビット基板を［ｍＫ（ミリケルビン）］オーダー以下に冷却可能な希釈冷却機等の冷却装置と、量子ビット基板上の任意の位置にレーザ光を照射可能なレーザ光出射装置と、磁場発生装置とを有し、冷却と磁場の制御とレーザ光の出射とによって量子ビット基板上の量子ビットを操作する。
【００９３】
また、量子重ね合わせ状態生成部１４及び制御演算部１５は、例えば、上述の量子ビット基板と、レーザ光出射装置と、磁場発生装置とを有し、磁場の制御とレーザ光の出射とによって量子ビット基板上の量子ビットを操作する。
【００９４】
さらに、観測部１７は、例えば、操作対象の量子ビットと同じ量子状態となる測定用の量子ビット列を量子ビット基板上に数列生成し、それに対して核磁気共鳴プローブ法（MRFM）（例えば、参考文献３参照。）等を適用して量子状態を測定する装置である。
【００９５】
また、制御部１８は、例えば、公知のCPU（Central Processing Unit）を中心に構成される制御素子であり、所定のプログラムが読み込まれることにより、量子演算装置を制御する。
【００９６】
また、このプログラムは、量子演算装置の制御に必要な処理をコンピュータ（古典的計算機）に実行させるためのプログラムである。すなわち、このプログラムがCPUに読み込まれ、このCPUと協同して働くことにより、量子演算装置の制御に必要な処理が実行される。ここで、「量子演算装置の制御に必要な処理」とは、量子演算装置で行われる量子操作の制御に必要な処理を意味する。つまり、このプログラムは、例えば、核スピンがキュービットに用いられる場合には、核スピンに当てる電磁波の周波数や時間の制御をコンピュータに実行させるためのプログラムや、量子演算装置全体の制御処理をコンピュータに実行させるためのプログラムを意味する。また、光子がキュービットに用いられる場合には、量子計算に必要な各光学素子の特性（例えば、ミラーの角度や位相シフタの制御電圧等）の制御をコンピュータに実行させるためのプログラムや、量子演算装置全体の制御処理をコンピュータに実行させるためのプログラムを意味する。
【００９７】
このプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００９８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１００】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【産業上の利用可能性】
【０１０１】
本発明の産業上の利用分野としては、公開鍵暗号方式の安全性確認システム等を例示できる。
【図面の簡単な説明】
【０１０２】
【図１】図１（ａ）は、非特許文献１に示された周期計算を行う量子回路を示した図である。図１（ｂ）は、非特許文献１に示された離散対数問題を効率的に解く量子回路を示した図である。
【図２】図２は、第１実施形態の量子演算装置の構成を示したブロック図である。
【図３】図３（ａ）は、制御演算部の詳細構成を示したブロック図であり、図３（ｂ）は、逆２次位相変換演算部の詳細構成を示したブロック図である。
【図４】図４は、第１実施形態の処理の全体を説明するための図である。
【図５】図５は、図４のステップＳ２〜Ｓ４の処理を説明するための量子回路である。
【図６】図６は、図５の再帰演算Vw（０≦w≦ε）を説明するための量子回路である。
【図７】図７は、演算Rwを説明するための量子回路である。
【図８】図８は、演算Rwαを説明するための量子回路である。
【図９】図９（ａ）は、nが奇数である場合の再帰演算Vε+1を説明するための量子回路であり、図９（ｂ）は、ｎが偶数である場合の再帰演算Vε+1を説明するための量子回路である。
【図１０】図１０（ａ）（ｂ）は、sやrの値を知ることなく、式（３４）の演算が可能となる原理を説明するための図である。
【図１１】図１１は、逆２次位相変換演算部の詳細構成を示したブロック図である。
【図１２】図１２は、図４のステップＳ２〜Ｓ４の処理に相当する量子回路である。
【０１０３】
【図１３】図１３は、図１２の制御再帰演算U-Vw（０≦w≦ε）を説明するための量子回路である。
【図１４】図１４（ａ）は、nが奇数である場合の制御再帰演算U-Vε+1を説明するための量子回路であり、図１４（ｂ）は、ｎが偶数である場合の制御再帰演算U-Vε+1を説明するための量子回路である。
【符号の説明】
【０１０４】
１  量子演算装置
【図１】
0005118461.tif 000049
【図２】
0005118461.tif 000050
【図３】
0005118461.tif 000051
【図４】
0005118461.tif 000052
【図５】
0005118461.tif 000053
【図６】
0005118461.tif 000054
【図７】
0005118461.tif 000055
【図８】
0005118461.tif 000056
【図９】
0005118461.tif 000057
【図１０】
0005118461.tif 000058
【図１１】
0005118461.tif 000059
【図１２】
0005118461.tif 000060
【図１３】
0005118461.tif 000061
【図１４】
0005118461.tif 000062