美術館をGroverのアルゴリズムで解く

量子コンピュータ

数独を一応解けるようになったので、今度は美術館(Akari/Light Up)を解く。 4x4サイズの例題。美術館のルールはこちらから。盤面のいくつかの白マスに白丸（照明）を書き込みます盤面の数字は、その数字の入っているマスにタテヨコに隣り合うマスのうち、…

2024-11-08

4x4より大きいサイズの数独をGroverのアルゴリズムで解く

量子コンピュータ

前にやったものでは量子ビット数の制限で(シミュレータ上で)解ける問題が少なかったので、オラクルの補助量子ビットを減らすようにマルチAND制御ゲートを使って改造した。また、初期状態を構成するゲートを一般化して、 4x4より大きいものについても(一…

2024-11-06

nビット整数の任意の組み合わせに対応する初期状態を作る

量子コンピュータ

Groverのアルゴリズムの初期化用に、nビット整数の任意の組み合わせに対応する初期状態を作る。例えば、3量子ビットに対して{001,011,100,101,110}などの組み合わせを与えたときに、その状態(この場合5状態)の同じ重みで同位相の重ね合わせ状態を作る。と…

2024-11-01

グレイコードを使ったマルチ制御ゲートなどのメモその2

量子コンピュータ

$ m $個の条件のANDが成立する場合に標的ビットに作用させるようなゲートを、 1つの補助ビットを使って構成する方法をまとめる。単純には、条件の数だけ補助量子ビットを用意して、最後にすべての補助量子ビットのANDを取るようなマルチ制御ゲートを適用さ…

2024-10-30

グレイコードを使ったマルチ制御ゲートなどのメモ

量子コンピュータ

制御ビットが$ n $個ある場合のマルチ制御ゲートを(制御ビットが1個の制御ゲートを使って)構成する方法をまとめる。制御ビット$ x _ 1,x _ 2,\cdots,x _ n $が$ x _ i=0,1 $の値をとるとき、 $$ \require{physics} \begin{align*} 2^{n-1} x_1 x_2 \cdots x…

2024-10-28

制御U3ゲートなどのメモ

量子コンピュータ

1ビット量子状態はブロッホ球の球面上の点で表される。なので、一般の1ビット量子ゲート$ U _ 3 $は、ブロッホ球上のEuler回転であらわされる。ということで、x,y,z軸周りの回転ゲート $$ %\require{physics} \begin{align*} R_x \qty(\theta) &= \exp \qt…

2024-10-25

4x4数独をGroverのアルゴリズムで解く

量子コンピュータ

数独については、下記を参照。 9x9サイズの数独は大変なので、4x4サイズの数独を対象にする。基本的には、前にやったものと同じ流れで解く*1。例題以下の問題を例題として解く。方針空きマスにそれぞれ2ビットの量子レジスタを割り当て、各マスの数字…

2024-10-23

和が条件を満たす2数の組をGroverのアルゴリズムで探す

量子コンピュータ

目的：Groverのアルゴリズムで遊ぶ。 Groverのアルゴリズムは、$ N $個の状態のうちから条件を満たすものを探索するアルゴリズム。これを使って、和が条件「4以上の奇数」を満たす2数の組を検索する。条件は、オラクルが簡単に作れそうなものを選んだ。 Gr…

2024-10-18

2変数が等しい場合に標的ビットを反転させるゲートを作るその2

量子コンピュータ

前回、2変数が等しい場合に標的ビットを反転させるゲートを作ってはみたけど、「トランスパイル時に最適化とかされるのだろうか？」「最適化されると、(入力ビットの全部に制御ビットを立てても、それを半分にしても)結局同じような回路になるのでは？」 …

2024-10-11

2変数が等しい場合に標的ビットを反転させるゲートを作る

量子コンピュータ

下記などを参考にして、$ n $ビットに一般化したいな、と思ってまとめた。 $ n $ビットの変数2つ($ a ^ {(n)}, b ^ {(n)} $)を比較して、両者が等しい場合に標的ビットを反転させるゲートを作る。標的ビットを$ \ket{-} $とすると、位相キックバックで位相…