2017-07-16

C++20 進捗

C++

先日、ISO C++委員会は、カナダのトロントで次の国際標準であるC++20の作業を開始し、技術仕様の開発が続かれた。C++ 20ドラフトには、以下の機能が追加された。

Concepts
Explicit generic lambdas
＿VA_OPT＿
Default bit-field initializers
Fixed const-qualified pointers to members
Allow［=, this］ as a lambda capture
Designated Initializers
More deduction guides for the standard library
Endian
Fixing string conversion fixes
Improve class template argument deduction in the stdlib
Arrays for make_shared
THREE Technical Specifications
- Coroutines v1
- Ranges v1
- Networking v1

その他、reddit ページと内容が被るところがあるが、参考書執筆の際のリファレンスにするために、主に話題に上がっている提案書のリンクをリビジョン含めてまとめたので、もし提案の経緯など追いたければどうぞ。
github.com

2017-07-10

最近 srook/cxx17/mpl/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$ への収束を避ける事が当アルゴリズムのポイントである。

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