2017-07-10

any_pack に加えた機能

C++

テンプレートパラメータにautoを使える喜びを噛み締めて遊ぶ - Rokiのチラ裏にて取り上げてから、いくつかの機能を追加したのでその紹介をしてみる。

cos table

[追記: any_pack によるコンパイル時コサインテーブルの構築。これは、srook/cxx17/mpl/any_pack/math/make_costable.hpp を使うと一発で生成できる。生成されたコサインテーブルは、今の所std::tupleで吐くようにしている。パラメータには x * y のように指定する。8 * 8 のコサインテーブルの生成は以下のようになる。

#include<srook/cxx17/mpl/any_pack/any_pack.hpp> #include<srook/cxx17/mpl/any_pack/math/make_costable.hpp> #include<srook/algorithm/for_each.hpp> #include<iostream> int main() { constexpr auto t = srook::math::cos_table<8,8>; // コンパイル時にコサインテーブルを生成 srook::for_each(t,[](const auto& x){std::cout << x << " ";}); std::cout << std::endl; }

この方法は非推奨とした。次の記述で同様のコンパイル時コサインテーブルが得られ、従来よりもオーバーフローなどの観点からみた時の安全性の向上が見込めるようになった。

constexpr std::array<const double, block * block> cos_table = srook::constant_sequence::math::unwrap_costable::array<srook::constant_sequence::math::make_costable_t<8,8>>::value;

– 追記終わり]
output:

1 1 1 1 1 1 1 1 0.980785 0.83147 0.55557 0.19509 -0.19509 -0.55557 -0.83147 -0.980785 0.92388 0.382683 -0.382683 -0.92388 -0.92388 -0.382683 0.382683 0.92388 0.83147 -0.19509 -0.980785 -0.55557 0.55557 0.980785 0.19509 -0.83147 0.707107 -0.707107 -0.707107 0.707107 0.707107 -0.707107 -0.707107 0.707107 0.55557 -0.980785 0.19509 0.83147 -0.83147 -0.19509 0.980785 -0.55557 0.382683 -0.92388 0.92388 -0.382683 -0.382683 0.92388 -0.92388 0.382683 0.19509 -0.55557 0.83147 -0.980785 0.980785 -0.83147 0.55557 -0.19509

costant_range

コンパイル時範囲変換。以前のエントリでは動的範囲への変換しか機能を提供していなかったので、コンパイル時に適用できる範囲(例えばタプルとか)への変換も用意した。

constexpr auto t = srook::any_pack<1,2,3>::constant_range<std::tuple>; // コンパイル時にタプルへ変換
static_assert( std::get<0>(t) == 1 and std::get<1>(t) == 2 and std::get<2>(t) == 3 );

また、単に範囲に変換するだけではなく、any_pack が保持している値に何らかの処理をしてから範囲へ変換するといったような操作もできる。無論、この時渡す関数オブジェクトは、constexprでなければならない。

struct Twice{
        explicit constexpr Twice()=default;
        template<class T>
        constexpr T operator()(T&& v)const
        {
                return v * 2;
        }
};

constexpr auto t = srook::any_pack<1,2,3>::constant_range<std::tuple,Twice>; // コンパイル時に any_pack が保持している各値を2倍してタプルに変換
static_assert( std::get<0>(t) == 2 and std::get<1>(t) == 4 and std::get<2>(t) == 6 );

make_any_pack

これは、指定サイズの any_pack の生成を行う。STL コンテナのコンストラクタのような感じでサイズと初期化値を指定する。パックに事前に値が含まれていた場合は、その後ろに値を付与する。

#include<srook/cxx17/mpl/any_pack/any_pack.hpp>
#include<boost/type_index.hpp>
#include<iostream>

int main()
{
        std::cout << boost::typeindex::type_id< srook::any_pack<>::make_any_pack<10,0> >().pretty_name() << std::endl; // 10 個の要素を 0 で初期化
        std::cout << boost::typeindex::type_id< srook::any_pack<1,2,3>::make_any_pack<10,0> >().pretty_name() << std::endl; // 1,2,3 の後ろに 10 個の 0 で初期化
}

output:

srook::mpl::v1::any_pack<0, 0, 0, 0, 0, 0, 0, 0, 0, 0>
srook::mpl::v1::any_pack<1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>

for_to, for_until, for_cut_to, for_cut_until

any_pack での for。Scala の for 文にインスパイアされて、to と until を採用している。これは機能が比較的多めなので指定できるパラメータ等を明記しておく。

srook::any_pack<>::for_(to | until | cut_to | cut_until)<begin, end, value を持つメタ関数, any_pack で包んだ任意の値, pack で包んだ任意の型, Invokable (constexpr)>

begin: ループで扱われる最初の値。Scala でのfor(i <- h until t) ...のhに値する(begin は to であろうが until であろうが関係ない)。
end: ループで扱われる末尾、もしくは最後の値。for_toであれば Scala でのfor(i <- h to t)...のtに値し、for_untilであれば Scala での for(i <- h until t)...のtに値する。
value を持つメタ関数: valueを持つメタ関数を渡す。このvalueの値が any_pack に適用される。value を持つメタ関数は、以下のようなシグネチャでなければならない。

// 1st parameter std::size_t: begin ~ end 間の値
// 2nd parameter class: 呼び出し元の保持している any_pack
// 3rd parameter class: 呼び出し時に指定する任意の値の any_pack. 未指定の場合空の any_packが渡ってくる
// 4th parameter class: 呼び出し時に指定する any_pack で包んだ任意の型. 未指定の場合空の pack が渡ってくる
template<std::size_t,class,class,class>
struct Application;

any_pack で包んだ任意の値: any_pack で包んで任意の値を渡すことができる。渡すと、ループ中にその値を用いることができる。設定しなくても良い。
pack で包んだ任意の型: pack で包んで任意の型を渡す事ができる。渡すと、ループ中にその型を用いる事ができる。設定しなくても良い。
Invokable (constexpr): ループで扱われる値の増加、減少の幅をカスタマイズできる。constexprでの呼び出しが可能であり、かつconstexpr default constructibleが可能な関数オブジェクト型を指定する。設定しなくても良い。

例として以下に、この機能を用いたコンパイル時 fizzbuzz を示す。

#include<srook/cxx17/mpl/any_pack/any_pack.hpp>
#include<srook/algorithm/for_each.hpp>
#include<boost/type_index.hpp>
#include<iostream>
#include<tuple>

template<std::size_t,class,class,class> struct applyer;
template<std::size_t i,std::size_t... v>
struct applyer<i,srook::any_pack<v...>,srook::any_pack<>,srook::pack<>>
        : std::integral_constant<
                char,
                (srook::any_pack<v...>::template at<i>() % 15 == 0) ? 'F' :
                (srook::any_pack<v...>::template at<i>() % 5 == 0) ? 'b' :
                (srook::any_pack<v...>::template at<i>() % 3 == 0) ? 'f' : 'V'
        >{};

int main()
{
        using index = srook::any_pack<>::make_index_sequence<50>; // 0 ~ 49 の数列
        constexpr auto fizzbuzz = index::for_until<0,index::size(),applyer>::constant_range<std::tuple>; // fizzbuzz してタプルに変換
        srook::for_each(fizzbuzz,[](const auto& x){std::cout << x << " ";});
        std::cout << std::endl;
}

output:

F V V f V b f V V f b V f V V F V V f V b f V V f b V f V V F V V f V b f V V f b V f V V F V V f V

尚、指定された数値間での数値の増加/減少は、ユーザーが独自にカスタマイズできる。カスタマイズするには、constexpr で実行が可能な関数オブジェクトを渡す。

template<std::size_t i,class,class,class>
struct applyer : std::integral_constant<std::size_t,i>{}; // ループで増加する値をそのまま適用する

struct Increment{
        explicit constexpr Increment() = default;
        constexpr std::size_t operator()(std::size_t v)const noexcept{return v + 2;} // 2ずつ増加
};

using index = srook::any_pack<>::make_any_pack<4,0>;

constexpr auto t = index::for_until<0,4,applyer,srook::any_pack<>,Increment>::constant_range<std::tuple>;
static_assert( std::get<0>(t) == 0 and std::get<1>(t) == 2 and std::get<2>(t) == 0 and std::get<3>(t) == 0 and std::tuple_size<decltype(t)>::value == 4); // 2ずつ増加したため全ての範囲に行き渡らず途中で終わる。

この場合、2ずつ増加する。最後の数値を超えた場合、そこから先は処理されない。処理されなかった部分がいらなければ、for_cut_to、もしくはfor_cut_untilを使う。for_to、for_untilとの違いはここにある。

// applyer, Increment, index ....

 constexpr auto t = index::for_cut_until<0,4,applyer,srook::any_pack<>,srook::pack<>,Increment>::constant_range<std::tuple>;
 static_assert( std::get<0>(t) == 0 and std::get<1>(t) == 2 and std::tuple_size<decltype(t)>::value == 2); // 2ずつ増加したため全ての範囲に行き渡らず途中で終わり、行き渡らない範囲は切り捨てられる。

尚、この数値は増加だけでなく、減少も可能である。単純に、頭 > 最後の関係であれば、数値は減少していく。

constexpr auto t = index::for_until<4,0,applyer,srook::pack<>>::constant_range<std::tuple>; // 4 to 0
static_assert( std::get<0>(t) == 4 and std::get<1>(t) == 3 and std::get<2>(t) == 2 and std::get<3>(t) == 1 );

減少に対しても、増加と同じようにカスタマイズが可能である。

template<std::size_t i,class,class,class>
struct applyer : std::integral_constant<std::size_t,i>{}; // ループで減少する値をそのまま適用する

struct Decrement{
        explicit constexpr Decrement() = default;
        constexpr std::size_t operator()(std::size_t v)const noexcept{return v - 2;} // 2ずつ減少
};

using index = srook::any_pack<>::make_any_pack<4,0>;

constexpr auto t1 = index::for_until<4,0,applyer,srook::any_pack<>,srook::pack<>,Decrement>::constant_range<std::tuple>;
static_assert( std::get<0>(t1) == 4 and std::get<1>(t1) == 2 and std::get<2>(t1) == 0 and std::get<3>(t1) == 0 and std::tuple_size<decltype(t1)>::value == 4); // 2ずつ減少したため全ての範囲に行き渡らず途中で終わる。

constexpr auto t2 = index::for_cut_to<4,0,applyer,srook::any_pack<>,srook::pack<>,Decrement>::constant_range<std::tuple>;
static_assert( std::get<0>(t2) == 4 and std::get<1>(t2) == 2 and std::tuple_size<decltype(t2)>::value == 2); // 2ずつ減少したため全ての範囲に行き渡らず途中で終わり、行き渡らない範囲は切り捨てられる。

また、任意の値を渡すことができる。

template<std::size_t,class,class Value,class>
struct applyer : std::integral_constant<decltype(Value::first),Value::first>{}; // 全ての要素を渡ってきた任意の値にする

using index = srook::any_pack<>::make_any_pack<4,0>;

constexpr auto t = index::for_until<0,index::size(),applyer,srook::any_pack<42>,srook::pack<>>::constant_range<std::tuple>; // 任意の値 42 を渡す
static_assert( std::get<0>(t) == 42 and std::get<1>(t) == 42 and std::get<2>(t) == 42 and std::get<3>(t) == 42);

任意の型を渡す事もできる。

#include<iostream>
#include<srook/cxx17/mpl/any_pack/any_pack.hpp>
#include<srook/algorithm/for_each.hpp>

struct Twicer{
        explicit constexpr Twicer() = default;
        template<class T>
        constexpr T operator()(T v)
        {
                return v * 2;
        }
};

template<std::size_t,class,class,class> struct applyer;
template<std::size_t i,auto... v,class... Ts>
struct applyer<i,srook::any_pack<v...>,srook::any_pack<>,srook::pack<Ts...>>
        : std::integral_constant<decltype(i),srook::First_t<srook::pack<Ts...>>()(i)>{};

int main()
{
        constexpr auto t = srook::any_pack<>::for_until<0,4,applyer,srook::any_pack<>,srook::pack<Twicer>>::constant_range<std::tuple>;
        srook::for_each(t,[](const auto& x){std::cout << x << " ";});
        std::cout << std::endl;
}

output:

0 2 4 6

for_type_to, for_type_until, for_type_cut_to, for_type_cut_until

これは、上記の for と殆ど変わらないが、適用する値が value ではなく type 、つまり型をどんどん連結した any_pack を構築する for となっている。よって、適用するメタ関数には type という型が定義されていなければならない。

output:

f i z z b u z z 1 2 f i z z 4 b u z z f i z z 7 8 f i z z b u z z 11 f i z z 13 14 f i z z b u z z 16 17 f i z z 19 b u z z f i z z 22 23 f i z z b u z z 26 f i z z 28 29 f i z z b u z z 31 32 f i z z 34 b u z z f i z z 37 38 f i z z b u z z 41 f i z z 43 44 f i z z b u z z 46 47 f i z z 49

2017-07-06

stack overflow からの小ネタメモ #2

C++

前回。

stackoverflow.com 質問者は、void_t detection idiom によるSFINAEを試行している。void_t には、確かにテンプレート型に依存するパラメータが渡されているが、C++14 N3936 [temp.alias] を参照すると、テンプレートパラメータのエイリアステンプレートに対して型を指定した時、それが未使用だった場合、テンプレート引数の置換が保証されるような文面がないのである。

template<class...> // 無名のテンプレートパラメータ
using void_t = void;

// value_type を持つ事を要求する
// C++14 では template-idが例え依存していたとしてもテンプレート引数の置換は義務ではない
template<class T,void_t<T::value_type>* = nullptr>
void f(T){}

解決法としては、使用すれば良いわけなので、以下のように make_voidなどを用意してやる。

template<typename...> struct make_void { typedef void type;};
template<typename... Ts> using void_t = typename make_void<Ts...>::type;

しかしこのような動作は、直感的ではないという事で、CWG Issue 1980として取り上げられている。これによれば、14.5.7 [temp.alias] に対して drafting されているとの事で、執筆時現在では、[temp.alias] にて確認できる。内容を引用。

However, if the template-id is dependent, subsequent template argument substitution still > applies to the template-id. [ Example: template<typename…> using void_t = void; template void_t f(); f(); // error, int does not have a nested type foo — end example ]

template-id が依存している場合は、それ以降のテンプレート引数の置換は引き続き template-id に適用される。つまり、これは先ほど述べた内容を保証するといった文面であるから、質問者のコードは、間違いなく C++1z 以降の処理系では正しく動作するべきである。そして、 C++14 では、void_t の内部実装を上記のような void_make などのようなやり方にして、C++1z と同じように動くべきである。

stackoverflow.com GCC と Clang で、それぞれstd::arrayのサイズを0として宣言する際に、default-constructible を要求するかが異なるといった質問だ。これは、[array.zero] にその動作が定義されている。ただ、その文面には、0サイズのstd::arrayをどのように実装すべきかについて執筆時現在言及されていない。つまり IDB なので、実装が default-constructible を要求したとしても、規格違反とはならないのである。しかし、これは規定すべきだという事で LWG issue 2157 として取り上げられている。LWG 2157 では、配列の不特定の内部構造は0サイズのstd::arrayの初期化を許可し、任意の型Tが default-constructible でない場合でも、有効でなければならないといった文面が提示されている。

stackoverflow.com 質問内容は、ローカルクラスがテンプレートメンバーを持つことができない明確な理由とは？といったもの。
回答内容から一部引用する。

template <typename T>
class X {
    template <typename>
    void foo() {
        T t;
    }
};

このクラス X に対して void を指定しても foo を呼び出さなければそれは ill-formed ではない。何故ならば、呼び出されなければ、あるいは明示的インスタンス化がされなければ*1、インスタンス化されないからだ。続いて、さらに回答内容から一部引用。

template <typename T>
auto bar() {
    return [] (auto) {T t;};
};

このコードは ill-formed であるが、これを機能としてサポートする場合を考える。この場合、ローカルコンテキスト*2に依存しないように、ローカルのテンプレートを十分にインスタンス化する必要があるため、generic lambda の body 部分をテンプレート関数 bar のテンプレート引数 T を使って部分的にインスタンス化しなければならない。
テンプレート関数は先ほども述べた通りインスタンス化の遅延が施されるが、ジェネリックラムダも所謂テンプレート版関数オブジェクト、つまりローカルテンプレートクラスである。しかし、回答でも触れられている通り、特にテンプレートメンバ関数がテンプレート関数のローカルクラスの内部にある場合コンパイラ側の対応がとても困難である*3ため、このような部分的インスタンス化を行うような機能が導入されなかったのだとのこと。…しかし、ラムダの body 部分にテンプレートパラメータの型を書くという事は、割と自然にやってしまいそうなものだ。一応、CWG issue 728として取り上げられたようだが、extention となったようだ。CWG issue 728 で問いている内容に対する答えは、上記の通り処理系側の実装困難な問題であるというのが最も妥当だろう。実際、GCC はこのこの extention をサポートしている？ようだが当然 IDB なので、やはり推奨されるものでは決してないだろう。

stackoverflow.com C++にはデフォルト引数を再定義する機能がある([dcl.fct.default]/4)。この機能を有効的に使うシーンは何かあるだろうか？という内容。これに対して、既存のコードやライブラリを変更できず、実際に正しい引数を入力することができない場合、一部のスコープのデフォルト引数を変更することが、いくつかのレガシーツールで生成されたC++コードを扱うときに役立つハックのようなものとして利用できるとのアンサーが1つ付いている。例えば、生成されたコードがデフォルトの引数を使用して何百もの外部ライブラリに何百もの呼び出しを持っていたが、デフォルトの引数がもう正しくない場合など。確かに、そういう用途では検討しても良いのかもしれないが、混沌を更に深めるような気もしてくる。正直、デフォルト引数そのものがそこまで良いものとも思えないので、わざわざ積極的に利用するものでもないだろう。

*1:コンパイラオプション等による明示的インスタンス化を含む

*2:それを含む関数テンプレートのテンプレートパラメータを含む

*3:処理系の実装として、関数定義の処理中に使用される語彙スコープが基本的に一時的であることが知られているとのこと。

2017-07-02

JPEG エンコーダ書いた

jpeg algorithm C++

以前、JPEGに関する画像圧縮技術やデータ構造などついて学んだので、折角だし自分で作ってみようと思い、フルスクラッチで書いて見た。といっても、性能自体はそんなに良いものではないと思うし、簡単のために色々と制限を設けているので実用的ではないと思うが。言語はC++1z。Structured bindings とか Class templates deduction とか普通に使っているので、C++1z に対応しないコンパイラではコンパイルできない。

github.com

仕様と諸々の説明は以下の通り。

出力された lena 氏の画像*1。左はカラーモード、右はグレースケールモードで出力した。グレースケール画像は、簡単のために、Cb値とCr値を 0 としてそのまま持たせている。

f:id:Rok1:20170702130810j:plain:medium f:id:Rok1:20170702131116j:plain:medium

JPEG エンコーダをフルスクラッチで実装した事で、JPEG バイナリが読めるようになった。そしてデータ圧縮のロマンをより一層感じた。今後も時間があれば、機能拡張したりエフェクト付け加えたり、~~はたまたデコーダとかを書ければなと思う~~。

※追記

その後、JPEG デコーダもフルスクラッチで実装した。

*1:ブログに載せる上で画像の表示を小さくしている。

2017-06-20

量子力学と量子コンピューターについての学習メモ #3

Quantum mechanics reading

前回の続き。

データベース検索

データベースの例として電話帳を取り上げる。電話帳は、名前の五十音順に番号が付けられている。これは昇順ソートされたリストであると解釈できるので、バイナリーサーチの手法によって比較的高速かつ簡単にアクセスできる。次に、この電話帳に対して電話番号を入力して、誰のものなのかを問い合わせたいとしたい場合を考えると、この場合線形探索が必要となってしまい、とても効率が悪い。しかし量子コンピュータでは、この種のデータ探索をデータ数が $N \in \mathbb{N}$ とした場合 $\sqrt{N}$ 回で確実に完了するのである。これは、グローバーのアルゴリズムといわれている。まず、以下のようなデータベース回路を用意する。

f:id:Rok1:20170611190244p:plain:w400

全ての量子ビットをアドレスビットとし、入力の値がデータベースと合致した場合、アドレスビット列の位相が反転する。この場合、 $|0101\rangle$ がデータベースに登録されている事となる。もしその入力が得られた場合、位相が反転する。これをDBゲートとする。このゲートの通過結果に折り返し量子回路をかける。この折り返し量子回路は、各量子ビットに対するアダマールゲートとアドレスビット列が全て $|0\rangle$ の状態のときのみその位相を反転するゲートによって容易に実現できるようだ(実装を調査したが、詳しい実装を見つける事ができなかった。もし詳細に関わるドキュメントなどをこのエントリを読んでいる方の中でご存知の方がいたら、是非ご教授願いたい)。
[ ※追記独自に実装した。

中身が |11> なデータベースに対するグローバーのアルゴリズム,多分できた. pic.twitter.com/4j6U6shcIc
— roκi (@530506) 2017年6月19日

これは、データベースの中身が $|11\rangle$ である場合の回路である。数式で流れを追うと明快である*1。

まず初期状態として2量子ビットとも $|0\rangle$ にしておく。
アダマールゲートによって、2量子ビットとも重ね合わせ状態 $(\frac{|0\rangle+|1\rangle}{\sqrt{2}})^{2}$ となる。それぞれの確率振幅は $\frac{1}{2}$ なので、2量子ビットにおける全てのパターンそれぞれの確率振幅は $(\frac{1}{2})^{2} = \frac{1}{4}$ である。
次にターゲットである $|11\rangle$ の位相のみ反転するために制御Zゲートを通過させると、次の数式の通りとなる。 $\frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle) \rightarrow (CZ) \rightarrow \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$ となる。
拡散変換D(折り返し回路)を通過する。アダマール変換、ビット変換、制御Zゲートにより構成される。これらを通過すると、次の式の通りとなる。

$\frac{1}{2}(|0\rangle |0\rangle + |0\rangle |1\rangle + |1\rangle |0\rangle + |1\rangle |1\rangle) \rightarrow (H \otimes H) \rightarrow \\ \frac{1}{2}\left\{ (\frac{|0\rangle + |1\rangle}{\sqrt{2}})^{2} + (\frac{|0\rangle + |1\rangle}{\sqrt{2}} + \frac{|0\rangle - |1\rangle}{\sqrt{2}}) + (\frac{|0\rangle - |1\rangle}{\sqrt{2}} + \frac{|0\rangle + |1\rangle}{\sqrt{2}}) - (\frac{|0\rangle - |1\rangle}{\sqrt{2}})^{2} \right\} = \frac{1}{2}(|0\rangle |0\rangle + |0\rangle |1\rangle + |1\rangle |0\rangle - |1\rangle |1\rangle) \rightarrow (X \otimes X) \rightarrow \\ \frac{1}{2}(|1\rangle |1\rangle + |1\rangle |0\rangle + |0\rangle |1\rangle - |0\rangle |0\rangle) \rightarrow (CZ) \rightarrow \frac{1}{2}(-|1\rangle |1\rangle + |1\rangle |0\rangle + |0\rangle |1\rangle - |0\rangle |0\rangle) \rightarrow (X \otimes X) \rightarrow \\ \frac{1}{2}(-|0\rangle |0\rangle + |0\rangle |1\rangle + |1\rangle |0\rangle - |1\rangle |1\rangle) \rightarrow (H \otimes H) \rightarrow -|1\rangle |1\rangle \rightarrow -|11\rangle$

━━ 追記ここまで ]
この操作を何度か繰り返すことで、特定のビット列の発生する確率が高くなり、判定結果に対する信頼性が高まる。尚、これを繰り返すたびに、判定結果の量子ビット列の確率振り幅は $\frac{5}{\sqrt{N}}$ 、 $\frac{7}{\sqrt{N}}$ …と大きくなる。判定時に、そのビット列を入力してみて、正しく反転するか確認し、間違っていた場合はこれを繰り返す事で、ほぼ確実に内包するデータを取り出せる。

*1:Reference: https://quantumexperience.ng.bluemix.net/qx/tutorial?sectionId=8443c4f713521c10b1a56a533958286b&pageIndex=2

2017-06-18

stack overflow からの小ネタメモ

C++

stack overflow で得たちょっとした小ネタをメモがてら羅列してみる。

stackoverflow.com

質問は、ざっくり書くと、ラムダを関数ポインタに変換する明示的な記述なしでそのような事ができる方法はあるか？であるが、これに対して operator+ を適用すると、変換されると回答されている。これは何が起きているかと言うと回答にもある通り、built-in の unary operator + がラムダの持つ関数ポインタへの変換関数を呼び出すトリガーとなり、その結果関数へ渡せているのである。built-in の unary operator + については、[over.built]の通りである。以下はこの擬似コードである。

template<class T>
T call(T(*func)()){func();}

void(*built_in_plus(void(*f)()))() {return f;}

int main()
{
    call( built_in_plus([]{}) );
}

built-in unary operator+ のこういう使い方は思いつかなかった。ただ個人的には、関数ポインタに変換している旨をキャストによって明示した方が良いとは思う。

stackoverflow.com

initializer_list を使って range-based forを使う事で、より簡潔に記述できるが、意図した通りに動かないのでどうすれば良いかという質問であるが、これは勿論、 initializer_list に渡しているのがその対象のコピーであるため、まず意図したようには動かない。ここでは二つの回答があり、それぞれアドレスを渡すものと、reference_wrapper を渡すものである。個人的にはreference_wrapperを渡す方が好みだが、std::refを全てに書くのも微妙なので、Boost.Fusion が使えれば使いたい…

template<class... Ts>
constexpr boost::fusion::vector<Ts&...> refs(Ts&... ts)
{
    return boost::fusion::vector<Ts&...>{ts...};
}

boost::fusion::for_each(refs(foo,bar,baz),[](std::list<int>& x){x.push_back(42);});

stackoverflow.com 2つの質問が挙げられている。1つは、[class.member.lookup] に反したclang++とclが間違っているという内容。これはまぁ良い(良くはないのだが)。2つ目は、質問文中にあるように2つのクロージャ型を継承し、クロージャの持つ関数を Using-declaration を行ったものと、一切行わなかったもので、それぞれ全てのコンパイラが通す、GCCだけ通さないという結果になった。さらに面白い事に、Using-declaration を片方だけにしたら、今度はclang++とGCCだけが通した。これは一体何が正しいのだろうかという内容。結論から言えば、GCCの挙動が正しい。質問文中の最後に焦点を当てる。以下のような場合を考える。

#include <cstdio>

auto print_int = [](int x) {
    std::printf("int %d\n", x);
};
typedef decltype(print_int) foo_int;

auto print_str = [](const char* x) {
    std::printf("str %s\n", x);
};
typedef decltype(print_str) foo_str;

struct foo : foo_int, foo_str {
    using foo_int::operator();
    //using foo_str::operator();
    foo(): foo_int(print_int), foo_str(print_str) {}
};

int main() {
    foo f;
    f(123);
    f("foo");
}

まずf(123)によって Using-declaration で導出された operator()(int) による呼び出しが行われる。これは普通の動作だ。次に、f("foo")によって、これまた operator() から呼び出そうと試みるが、その引数型はconst char*なので、どれも該当しない。しかし、これは、[over.call.object] に該当する。foo はクロージャ型が持つ、関数ポインタへの implicit conversion function を継承しており、かつその implicit conversion function の operator() は当然ながらその関数ポインタと互換性のあるシグネチャとなるので、fooを関数へのポインタに変換し、これを呼び出す事ができるのだ。そして勿論の事、非 captureless nongeneric lambda は、function pointer への implicit conversion function を持たないため、コンパイルエラーとなるのである。

うむ期待通り. https://t.co/9AvrJZhFNw
— roκi (@530506) 2017年6月13日

これは、[over.call.object] のExampleが意味を明快に示している(簡単のため筆者によって若干改変されている)。

int f1(int){return 42;}
float f2(float){return 4.2f;}

typedef int (*fp1)(int);
typedef float (*fp2)(float);

struct A {
  operator fp1() { return f1; }
  operator fp2() { return f2; }
} a;

#include<iostream>

int main()
{
    int i = a(1); // calls f1 via pointer returned from conversion function
    std::cout << i << std::endl; // 42
    
    float f = a(4.2f); // calls f2 via pointer returned from conversion function
    std::cout << f << std::endl; // 4.2f
}

もうちょっと何個か良いネタがあれば羅列したいところだったが、現時点では特別見つからないので、良いネタを見つけ次第追記するかもしれない。

2017-06-11

量子力学と量子コンピューターについての学習メモ #2

Quantum mechanics algorithm reading

前回の続き。

ドイチュ-ジョサのブラックボックス

ジョサのアルゴリズムとは、ブラックボックスが蓄えているビット列が均一か等分かどちらなのかを判定するアルゴリズムである。よって、このアルゴリズムが有効であるのは、ブラックボックスが蓄えているビット列は、均一か等分かのどちらかに限定されている場合である(そうでない場合、その結果としてある程度の切り捨てが発生する)。

まず従来の方法では、一つ一つ順次検査していく。例えば $N \in \mathbb{N}$ としてブラックボックスが $\mathrm{2}^{N}$ 個のビット列を持っていた場合、これを与えると最大で $\mathrm{2}^{N-1}+1$ 回の検査が必要となるが、ドイチュ-ジョサの考案した量子コンピュータによるアルゴリズムでは、この操作を $2N+3$ 回で行える。自然数 $N$ を具体的な大きな数値にするとこの計算量の少なさは明らかだ。例えば $N = 50$ 、つまり $\mathrm{2}^{50}$ のビット列の場合、古典的な方法では560兆あまりのステップが必要となるが、当アルゴリズムでは103ステップで完了するのである。当然ながら、量子アルゴリズムでは重ね合わせを利用するために、ブラックボックスの入出力は量子ビットで行われる。入力用に3つの量子ビット、結果の出力用に1つの量子ビット、合計4つの量子ビットを使う。先頭ビットに対する答えが知りたければ $|000\rangle$ 、2つ目であれば $|001\rangle$ 、3つ目であれば $|010\rangle$ をセットする。例えば $|010\rangle$ をセットしたとした場合、3つ目のビットが0の場合は、出力用ビットの値がそのまま出力される(出力用量子ビットは予め決められた初期値が設定されなければならない)が、1の場合には出力量量子ビットが反転されて出力される。
例えば、ブラックボックスの中身が $|1,1,1,1,1,1,1,1\rangle$ という均一であった場合、そのブラックボックスは量子回路によって以下のように実装できる。

f:id:Rok1:20170610200046p:plain:medium

どんな入力を受け付けても、全て出力を反転してしまえば良い。これを、BBAとする。

例えば、ブラックボックスの中身が $|1,1,1,1,0,0,0,0\rangle$ という等分であった場合、そのブラックボックスは量子回路によって以下のように実装できる。

f:id:Rok1:20170610202354p:plain:medium

入力が $|100\rangle$ 以降となった場合に反転させなければ良い。これをBBBとする。ドイチュ-ジョサの量子アルゴリズムはこのような量子ブラックボックスに対して、等分が均一かを確実に超高速で判別することができるアルゴリズムである。まず、そのアルゴリズムを実装した量子回路を以下に示す。

f:id:Rok1:20170610204727p:plain:w250 f:id:Rok1:20170610204736p:plain:w250

まず量子ビットは全て $|0\rangle$ にセットされ、アダマールゲートによって $|a_n\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$ となる。中身を具体的に書くと、 $\frac{|0,0,0,0\rangle + |0,0,1,0\rangle + |0,1,0,0\rangle + |0,1,1,0\rangle + |1,0,0,0\rangle + |1,0,1,0\rangle + |1,1,0,0\rangle + |1,1,1,0\rangle}{2\sqrt{2}}$ という具合だ。
次のステップで、量子ブラックボックス回路に入る。この時、量子ブラックボックスBBAを通過した段階では、 $\frac{|0,0,0,1\rangle + |0,0,1,1\rangle + |0,1,0,1\rangle + |0,1,1,1\rangle + |1,0,0,1\rangle + |1,0,1,1\rangle + |1,1,0,1\rangle + |1,1,1,1\rangle}{2\sqrt{2}}$ であり、量子ブラックボックスBBBを通過した段階では、 $\frac{|0,0,0,1\rangle + |0,0,1,1\rangle + |0,1,0,1\rangle + |0,1,1,1\rangle + |1,0,0,0\rangle + |1,0,1,0\rangle + |1,1,0,0\rangle + |1,1,1,0\rangle}{2\sqrt{2}}$ である。この段階で特徴として挙げられるのが、それぞれの項のレジスタビット $|b\rangle$ が、ブラックボックスに蓄えられていたビット列と完全に一致することである。これはつまり、一度の操作でブラックボックスの中身を読み出せたことを意味する。
ここからさらに、レジスタビット $|b\rangle$ に、制御位相シフトを行う。制御位相シフトは、対象とする量子ビットが $|1\rangle$ である場合のみ、その位相をプラスからマイナスへと変化させるので、当操作によってそれぞれ $\frac{-|0,0,0,1\rangle - |0,0,1,1\rangle - |0,1,0,1\rangle - |0,1,1,1\rangle - |1,0,0,1\rangle - |1,0,1,1\rangle - |1,1,0,1\rangle - |1,1,1,1\rangle}{2\sqrt{2}}$ 、 $\frac{-|0,0,0,1\rangle -|0,0,1,1\rangle -|0,1,0,1\rangle -|0,1,1,1\rangle + |1,0,0,0\rangle + |1,0,1,0\rangle + |1,1,0,0\rangle + |1,1,1,0\rangle}{2\sqrt{2}}$ となる。
さらに、量子ブラックボックスを通過し、それぞれ、 $\frac{-|0,0,0,0\rangle - |0,0,1,0\rangle - |0,1,0,0\rangle - |0,1,1,0\rangle - |1,0,0,0\rangle - |1,0,1,0\rangle - |1,1,0,0\rangle - |1,1,1,0\rangle}{2\sqrt{2}}$ 、 $\frac{-|0,0,0,0\rangle -|0,0,1,0\rangle -|0,1,0,0\rangle -|0,1,1,0\rangle + |1,0,0,0\rangle + |1,0,1,0\rangle + |1,1,0,0\rangle + |1,1,1,0\rangle}{2\sqrt{2}}$ となる。簡単のため、アドレスビットとレジスタビットを分けて、 $\frac{(-|0,0,0\rangle - |0,0,1\rangle - |0,1,0\rangle - |0,1,1\rangle - |1,0,0\rangle - |1,0,1\rangle - |1,1,0\rangle - |1,1,1\rangle)|0\rangle}{2\sqrt{2}}$ 、 $\frac{(-|0,0,0\rangle -|0,0,1\rangle -|0,1,0\rangle -|0,1,1\rangle + |1,0,0\rangle + |1,0,1\rangle + |1,1,0\rangle + |1,1,1\rangle)|0\rangle}{2\sqrt{2}}$ とする。
最後にアダマールゲートを作用させる。 $|0\rangle$ に作用させると $\frac{(|0\rangle + |1\rangle)}{\sqrt{2}}$ に、 $|1\rangle$ に作用させると $\frac{(|0\rangle - |1\rangle)}{\sqrt{2}}$ となるため、例えば $|0,0,0\rangle$ の状態に焦点を当てると、まず $\frac{(|0,0,0\rangle + |1,0,0\rangle)}{\sqrt{2}}$ となり、真ん中のビットに作用させると $\frac{(|0,0,0\rangle + |0,1,0\rangle + |1,0,0\rangle + |1,1,0\rangle)}{2}$ となり、同じく右側のビットに作用させ、 $\frac{(|0,0,0\rangle + |0,0,1\rangle + |0,1,0\rangle + |0,1,1\rangle + |1,0,0\rangle + |1,0,1\rangle + |1,1,0\rangle + |1,1,1\rangle)}{2\sqrt{2}}$ となる。この具合に、全ての項をアダマール変換すると、BBA側の変換結果は、1回目のアダマール変換によって全ての量子ビットに位相シフトが起きた事から、 $|a_0\rangle,a_1\rangle,a_2\rangle = (|0\rangle-|1\rangle)\sqrt{2},|b\rangle = |0\rangle$ である事が言えるため、これらに対し再度アダマール変換を施すと、それぞれの量子ビットは $|0,0,0\rangle$ となり、BBB側の変換結果は $\frac{(|0,0,1\rangle + |0,1,1\rangle - |1,0,0\rangle + |1,1,0\rangle)}{2}$ となる。

結果、ブラックボックスBBAは全て状態 $|0\rangle$ である事から、観測すると必ず状態 $|0\rangle$ が得られるため均一である事が言え、ブラックボックスBBBはそうではなく、どれを観測しても全て状態 $|0\rangle$ が得られるわけではない事から、等分であることを当アルゴリズムによって立証することができる。等分の場合に部分的に位相が反転するようにする事で、プラスマイナスによる打ち消しを妨害し、 $|0\rangle$ への収束を避ける事が当アルゴリズムのポイントである。

次回はデーターベース検索のアルゴリズムに続く。

2017-06-09

量子力学と量子コンピューターについての学習メモ #1

algorithm Quantum mechanics reading

量子力学、量子コンピュータについての個人的な学習メモ。学習を促すものでも入門記事でもなくあくまで個人的な学習過程でのメモである事に注意。

量子コンピュータ―超並列計算のからくり (ブルーバックス)

作者: 竹内繁樹
出版社/メーカー: 講談社
発売日: 2005/02/18
メディア: 新書
購入: 7人クリック: 64回
この商品を含むブログ (20件) を見る

量子コンピュータのメカニズムについて理解を深めるためには、量子力学について理解しなければならない。量子力学について理解するには、量子の代表例であり実験例としても最も多彩に業績の残る”光”についてまずは理解せねばならない。

光

光を巡る様々な仮説

光を理解するためには簡単に歴史的経緯を振り返ると理解しやすい。

かつて光に関して、二つの説が立説されていた。一つは「光は粒子」、もう一つは「光は波」。それぞれニュートンとホイヘンスが立説したもの。
前者は、光の直進性に目をつけ光をとても軽い「粒子」であると考えた。一方後者は、ある実験から「光は粒子」という説を真向から否定して立説した。ある実験とは、小さな丸い穴に向けて光を照射して、穴の後ろに配置されたスクリーンでその光を結像させるという実験であり、もし光が直進する粒子だとするならば、その穴がどんなに小さくても、その穴の通りにスクリーンに結像されるはずであるが、実際には波のような縞模様を描いた。これを光の波動説と言う。
しかし光を波とした場合、光の直進性の説明が難しくなる。媒質中を伝わる波（または波動）に対し障害物が存在する時、波がその障害物の背後など、つまり一見すると幾何学的には到達できない領域に回り込んで伝わっていく*1のである。これを回折という。
光の波動説が立説されてから暫くは、光は波であると決着がついていたがそれから約20年後、光電効果という現象が波動説での説明を困難にした。光電効果とは、金属に光を当てると、光を当てられた金属から電子が飛び出すという現象の事を示す。光の波動説に則ってこの現象を捉えると、大きな電気と電磁場の波がやってきたために、金属の中の電子が強く揺さぶられるので、もはや金属の中に留まれなくなって飛び出すと考えられる。しかし、実際の実験結果は、光の強さではなく、光の波長によって*2電子が飛び出すかが変化した。光を強くすると、それに応じて飛び出す電子の数は増加したが、どれだけ光を強くしても波長の長い光では電子は飛び出さず、波長の短い光において飛び出す電子の数が増加した。この実験結果を光の波動説で説明することは困難である。
この光電効果の実験結果を、うまく説明するに至った説が、アインシュタインによる光量子仮説であり、これは光のエネルギーの基本単位を仮定した。
基本単位は、光の振動数に比例し、光の波長に反比例するというもので、比例定数はプランク定数と呼ばれ、 $6 \cdot 10^{-34}$ である。光のエネルギーは連続的な値を取らず、光量子エネルギーの整数倍である、離散的な値しか持たないと考え、さらに、光が当たった時に電子が呼び出すという現象には、1つの光量子が1つの電子に吸収されてそのエネルギーを得た電子が飛び出すというように考える。まれに2つの光量子が1つの電子に吸収されるかもしれないが、プランク定数に則って計算すると、光が非常に強い場合を除いて、低確率でしか起こり得ずその挙動を無視できる。こう仮定すると、周波数を上げていく過程で電子の飛び出す量が増えることに説明がつき、高周波中に電子の飛び出す量が増えたという結果に対しても、単純に光量子の数が増えるためにあると説明することができる。*3 *4
光量子は、現在光子と呼ばれることが多いため、後の記述では「光子」を使う。

結局光とは何なのか

もっとも重要なのは「スリットを通った光は干渉縞を示す」という結果と光電効果に見られた結果を事実として捉えることであり、つまり、断定して言えることは光は波や粒子といったものではないと言うこと。更に、光は基本的には波だが、それぞれの波長の光に対してエネルギーの基本単位があり、その基本単位を分割することはできない、二重性のものであるということ。

波の性質を持つ粒子

光は波であると同時に粒子的な性質を持つ二重性のものであるが、以前まで粒子であると考えられていた電子や原子なども波としての性質を持つことがわかっている。*5 *6。

量子力学

二重性のものに対する知見を得て、量子力学について入門する前に、少し用語とこれまでの概要を簡潔にまとめる。

先の実験によって、光は光子からできており、また、電気は電子からできている事が示された。このようなある基本的な単位量のことを、量子と呼ぶ。
先の実験のように、量子による現象や作用は、我々が日常的に体感するスケールでの物理現象における理論、つまり古典力学によって、辻褄の合うよう説明する事ができない。よって、量子スケールの微視的な物理現象を、古典力学と切り分けて定める力学が新たに設けられた。これを、量子力学という。
つまり古典力学は、量子の集合体としての姿(物質や光などは量子から成り立っているため)における物理現象にのみ正しい理論である。よって量子力学から古典力学を導く事が可能であると考えられると同時に、世の中の全てを量子力学によって解明できるのではないかとの考察をするに値する。

光の偏光

古典論的解釈では、光は電磁波の一種であり、通常その進む方向と直角に電場と磁場が振動する。電場および磁場が特定の（振動方向が規則的な）方向にのみ振動する光のことを偏光という。電磁波の場合は偏波と呼ぶ。光波の偏光に規則性がなく、直交している電界成分の位相関係がでたらめな場合を非偏光あるいは自然光と呼ぶ*7。
偏光には電場（および磁場）の振動方向が一定である直線偏光、電場（および磁場）の振動が伝播に伴って円を描く円偏光(回転方向によって、右円偏光と左円偏光がある。角運動量を持つ。)、電場（および磁場）の振動が時間に関して楕円を描く、楕円偏光(右楕円偏光と左楕円偏光がある。)がある。以下にその図を示す。左からそれぞれ直線偏光、円偏光、楕円偏光を示している。

By Superborsuk - Transferred from pl.wikipedia, パブリック・ドメイン, Link
Copyrighted free use, Link
By from [1], Copyrighted free use, Link

上図のように、特に直線偏光における進む方向と直角な向きは様々である。電場が水平方向に振動する光を水平偏光、垂直な方向に振動する光を垂直偏光という*8。
この偏光の性質を工学的に利用したものの代表例として、ある特定の偏光だけを通す性質を持つ、偏光フィルタというものがある。これは、ある特定の方向の偏光だけを通す性質を持つ。例えば垂直偏光だけを通し水平偏光を全く通さない偏光フィルタの場合、当然水平偏光がそのフィルタを通過して到達する事はない。水平と垂直の中間の偏光がこの偏光フィルタに入った場合、その角度に応じて垂直偏光が出てくる。例えば角度45度で入射した場合は、入射した丁度半分のエネルギーを持った垂直偏光が出てくるのである。

パブリック・ドメイン, Link

二枚の偏光フィルタがあり、それぞれの透過する変更の方向が互いに垂直である場合(例：片方が垂直偏光を遮断する偏光フィルタ、片方が水平方向を遮断する平行フィルタ)、その二枚の偏光フィルタを重ねた部分は光が一切透過できないため真っ黒になる。この場合、1枚目の偏光フィルタによって水平方向の偏光を透過するが、2枚目の偏光フィルタによって水平方向の偏光を遮断するため、当然の原理である。
偏光フィルタと似たような昨日を持つ光学素子として、偏光ビームスプリッタというものがある。偏光フィルタでは、透過する偏光の垂直方向にある偏光を遮断するが、偏光ビームスプリッタは、その偏光を丁度90度直角方向に反射する。
この偏光ビームスプリッタに対して45度偏光を入射すると、水平偏光と垂直偏光の2つの偏光に均等なエネルギーで分解されて出てくる。つまり、例えば仮にある光がどのような偏光なのかを調べたいとした時に、偏光ビームスプリッタへ入射して、二つの出射面から出てくる光の強度を検出器で調べれば、その光がどのような偏光なのか分かるのである。水平偏光、または垂直偏光の場合は、どちらか一方だけの検出器で光が検出されるため、それもすぐに断定する事ができるのである。

光子の偏光

光子 1 つに偏光を持たせて偏光ビームスプリッタへ入射した場合、つまり、垂直方向、水平方向の光子を入射すると、それぞれ透過あるいは直角に反射される。しかし、ここに45度偏光の光子を入射するとすると、光子は量子であり、エネルギーの最小単位であるため二つに分割される事はないはずである。もしこれが仮に分割されてしまえば、アインシュタインによる光量子の考え方に反することとなるためである。実際の実験結果は、透過した側で検出される場合と90度反射された側で検出された場合がでたらめに現れる事となる。
この実験を幾度も繰り返すと、偏光ビームスプリッタによって透過する光子と反射する光子の割合がほぼ厳密に等しく収束する。この実験を幾度も繰り返すという事は、たくさんの光子、つまり通常の光を用いて実験する事に等しく、この結果は45度偏光を入射した場合の結果と対応している。
1つ1つの光子が偏光ビームスプリッタを通過しようとする際、透過側に出るのか、反射側に出るのかを完全に予想する手段はない。これを不確定性定理という。

45度偏光の光子1つ1つを打ち込んで割合が均等になっていく様子を観測してみたい。
— roκi (@530506) 2017年6月5日

重ね合わせ

量子力学、量子コンピュータ実用化における核心である重ね合わせについて理解する。重ね合わせの理解には、先ほどの偏光ビームスプリッタの代わりに半透鏡という道具を用いて、実験を元に考察する。

半透鏡

半透鏡とは、入射した光の丁度半分の光だけが透過し、半分の光が反射する性質を持つ鏡である。実用例としては、マジックミラーなどが挙げられる。明るい空間とくらい空間をマジックミラーで仕切ると、暗い空間にいる人は自分のいる空間からの光が鏡を反射してくるのよりも、明るい空間からの光が鏡を通過してくる方が強いため、明るい空間の様子が分かるが、明るい空間にいる人から見ると、自分のいる空間の光がか鏡で反射する方が暗い空間からの光よりも強いため、一見ただの鏡のように見える。これが、マジックミラーの原理である。

干渉計

半透鏡に単一の光子と比較して強い光を入射すると、偏光ビームスプリッタのように、半分は透過し、半分は反射される。半分になった光をそれぞれ鏡で更に反射させて、戻ってきた交点にまた半透鏡を置くと、その鏡の位置によって、半透鏡から出る光の一方が強まったり、両方同じ強さで出たりする。これを干渉計という*9 *10。このような干渉計などで2つの光が重なり、その2つの光の山谷がぴったり重なり合う状態を、位相差が0の状態、位相が一致した状態という。またそうでない場合を、位相がずれた状態という。
半透鏡に1つの光子を入射したとしても、光子は2つに分割される事はない。よって、光子は2つの出口からでたらめに検出される。これは、半透鏡は光子をでたらめに反射しているように思える。
次に、干渉計に光子を入射する。この場合、干渉計の一方の出力から光子が射出される確率は経路の長さに応じて変化する。つまり、2つの経路が全く同じ長さであれば単一の光子ではない強い光を入射した時と同じように、必ず射出される出口とそうでない出口が確定し、経路の長さが波長の半分だけ異なる場合は、必ず射出される出口とそうでない出口が入れ替わり、確実にそのように射出される。
つまり、半透鏡は、光子をでたらめに反射しているのではない。光子が1粒になったとしても、それは波としての性質を持つ事がここでも伺える。しかし、半透鏡はたった1 粒の光子から、どのように両方の経路の差を知る事ができているのか。これは、確率波という概念で説明される。半透鏡に光子を入射した時の光子は、粒ではなく、ある振幅を持った2つの経路の確率波であるという*11。この概念は、干渉計の中で光子が、単純にどちらかの経路にのみ存在するというわけではないし、更に、光子が二つに分割されてそれぞれの経路へ進行したわけでもない事を示す、今まで通りの量子力学らしい正に辻褄合わせのような概念である*12。
このような確率波の概念でしか説明する事のできない、つまり、ある振り幅を持った2つの確率波として表される状態にあるとしか言えない状態を、重ね合わせ状態という。
重ね合わせ状態は、どちらの状態にあるかを知る、つまり観測しようとすると、重ね合わせ状態が崩壊してしまう。つまり、でたらめにどちらかの経路に存在するという状態になる。これを重ね合わせ状態の破壊、デコヒーレンスという。ちょうど、先の偏光ビームスプリッタの実験は、重ね合わせ状態を破壊しているといえる。

物理学とコンピュータ

量子力学の理論をコンピューターの演算処理の原理として応用しようというものが、量子力学とコンピュータの関係性であり、これを量子コンピュータという。この確率波と重ね合わせ状態を駆使して膨大な並列計算を一気に行おうというアイデアが量子コンピュータの根本にある。そもそも、今私もこのエントリを執筆しているのに用いるコンピュータは、古典力学的な物理法則に則って動作している。しかし、その根本を構成するにあたる現代的な物理学、量子力学の物理法則に則ってコンピュータが動作すれば、この世界の最大限の能力を引き出して演算処理を実行する事ができるのである。

量子ビット

量子ビットは、従来のビットの概念とは異なり、0と1の二つの状態だけでなく、その重ね合わせ状態をとる。これはまず、0と1の中間の状態を持っている、もしくは確率的に0または1の状態であるというようなものではない。先の実験の考察から、重ね合わせ状態を説明するには、確率波という概念が必要であった。つまり量子ビットは、0または1の二つの状態をとる確率波そのものである。量子ビットの状態を知るには、0または1である確率に関する情報の他に、位相という情報が必要になる。0または1である確率を、重みという。
量子ビットは、ブロッホ球といわれる、三次元球体で表現する事ができ、その状態は、球面状の1点で表される。

By Smite-Meister - 投稿者自身による作品, CC 表示-継承 3.0, Link

以下に要点をまとめる。

ブロッホ球は、ブラ-ケット記法という記法によって、式にする事ができる。ブラ-ケット記法は、量子の状態を $| 0 \rangle,| 1 \rangle$ で表す。この時例えば、 $a | 0\rangle$ は、 $|0\rangle$ の振り幅が $a$ 、 $b | 1\rangle$ は、 $|1\rangle$ の振り幅が $b$ である事を示す。
ブロッホ球の緯度と経度それぞれの軸は、緯度が $|0\rangle$ か $|1\rangle$ かの重さを、経度が重ね合わせ状態の位相の違いを表している。
尚、上図のように示される状態は、次の式 $| \psi \rangle = \cos ( \frac{\theta}{2})| 0 \rangle+\exp(\iota\alpha) \sin (\frac{\theta}{2}) | 1 \rangle$ に対応している。
0の状態の量子ビットは北緯90度の北極に対応し、式では、 $| \psi \rangle = | 0\rangle$ と表される。
1の状態の量子ビットは、南緯90度の南極に対応し、式では、 $| \psi \rangle = | 1\rangle$ と表される。
$a | 0\rangle$ と $b | 1\rangle$ が成り立つ時、2.にて上掲された式から、次の式 $|\psi\rangle = a|0\rangle+b|1\rangle$ が成り立つ。例えばこの状態でこの量子ビットを観測、つまり、量子ビットの $|0\rangle$ または $|1\rangle$ の確率を知りたい場合、それぞれの係数を2乗したもので得る事ができる。つまり、4で前掲された条件の場合、 $\mathrm{|a|}^2$ が $|0\rangle$ である確率、 $\mathrm{|b|}^2$ が、 $|1\rangle$ である確率を表す事となり、 $\mathrm{|a|}^2 + \mathrm{|b|}^2 = 1$ が成り立つ。よって例えば $a = 1,b = 0$ であれば、量子ビットは $|0\rangle$ の状態であり、 $a = 0, b = 1$ であれば、量子ビットは $|1\rangle$ の状態である事がいえる。
例えば、赤道上の1点であった場合、丁度0と1が同じ割合だけ重なり合ったような状態の量子ビットに対応する。式では、 $| + \rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$ または $| - \rangle = \frac{1}{\sqrt{2}}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle$ と表される。それぞれブロッホ球上の裏表の関係に値する。

量子ビットから成るコンピューターの構成

このような量子ビットをビットの代わりに用いる時、当然ながら従来のコンピューターでビットが扱われるパーツが取って代わる事になる。つまり、メモリとレジスタが、量子ビットによって構成された量子メモリと量子レジスタに代わる。2ビットの従来型メモリで考えた場合、そのメモリには、00、01、10、11のいずれかの値が乗る事になるが、2つの量子ビットである場合は $|00\rangle$ 、 $|01\rangle$ 、 $|10\rangle$ 、 $|11\rangle$ のどれか1つではなく、これらの重ね合わせ状態となる事ができる(式で表すならば、2つの量子ビットをそれぞれ $a,b$ として、全ての状態が同じ重さである場合は、 $a = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle,b = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$ という関係にある。)ので、量子ビット数の増加による一度に扱える重ね合わせ状態の数は、従来のビットとは比べ物にならないほど爆発的に飛躍する。これが、大規模な並列計算を支援するのである。

量子ゲート

古典的な計算では、演算に論理回路を使う事で演算するが、量子ビットでは量子論理回路を使う。量子論理回路は、量子ビットを入出力に持ち、量子ビットに対して量子ゲートを作用させる。量子ゲートには様々な種類があるが、量子ゲートにおける万能ゲートは回転ゲートと制御ノットゲートの二つである。

回転ゲート

1つの量子ビットに対してのみ作用するゲートで、三次元で表された量子ビットをある与えられた角度だけ回転させる。

$\psi = |0\rangle$ を $y$ 軸方向に180度回転させた場合、 $\psi = |1\rangle$ となる。これを更に $y$ 軸方向に180度回転させれば、 $\psi = |0\rangle$ となる。これは、古典ゲートのNOTゲートに相当し、これを $\pi$ ゲートと言う。
$\psi = |0\rangle$ を $y$ 軸方向に90度回転させた場合、 $\psi = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$ となる。更に90度回転させた場合、 $\psi = |1\rangle$ となり、これを更に2回90度回転させていくと $\psi = \frac{1}{\sqrt{2}}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle$ 、 $\psi = |0\rangle$ というように戻ってくる。

アダマールゲート

回転ゲートの一種で、ブロッホ球上のz軸とx軸方向に45度傾いた方の軸周りに180度回転させるゲートである。 $\psi = |0\rangle$ にアダマールゲートを作用させると、 $\psi = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$ に、再び作用させると $\psi = |0\rangle$ に戻る。 $\psi = |1\rangle$ にアダマールゲートを作用させると $\psi = \frac{1}{\sqrt{2}}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle$ に、再び作用させると $\psi = |1\rangle$ に戻る。アダマールゲートを $H$ とした時、 $H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$ 、 $H|0\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$ が成り立つ。