(x332)00000..と、引数のビット列で指定された通りに立てた状態で重ね合わせたものを作る問題。作り、あとはbits[i]が1のところを順にCNOTして回る。(x273)引数の2つのビット列で指定された通りに立てた2つの状態の重ね合わせを作る問題。ψ0,ψ1どちらも1のところはXで反転して1にして、片方だけ1になってる最初のところをHで0+1にして、あとはCNOTで返していく。いうものを知らなかった。これは+-だとaが-のときqs[i]のほうが反転する。stateなら必ず先頭ビットが1になって終わるはず。stateの識別の時みたいに、2ビット目から最後までを制御ビットとしてCNOTで先頭を改変していく。stateはこれで先頭を1に出来る。stateでは最初が0になって識別可能。ビット数が奇数の場合:どちらも先頭が1になっている。先頭ビット(1)を制御ビットとして他のビットをCNOTでフリップしていくと、Wでは2ビット目以降が「ほぼ」全て1に、GHZでは2ビット目以降が全て0になる。ここまで出来ればあとは計測するだけ。(「ほぼ」なので失敗する可能性もある確率的な方法。qubitから成る状態4種類のどれかが与えられるのでどれかを答える問題。各ビットをHしてMした結果で場合分け。qubitから成る状態4種類のどれかが与えられるのでどれかを答える問題(その2)。今回はH2回+M2回に加え、CNOTを1回使う必要がある。厳密に識別するのは物理的に(量子力学的に)不可能なので1000回のうち80%以上合ってれば良い。}}→WA(2)http://codeforces.com/contest/1002/submission/40080987http://codeforces.com/contest/1002/submission/40081006あ、回転させればいい感じに差がつくんじゃないかな(22.5度回転してみた。(x145)C1と同様だが今回は間違いが許されず、分からない時には-1と答えろという問題。(全体の8割まで-1と答えて良い)POVMによる計測で同じことをする話はネットで読んだ。2のOracleを実装する問題。Oracle分かってなくて古典的に解こうとしてた...→WAhttp://codeforces.com/contest/1002/submission/40038721WarmupのOracle問題のところに解説へのリンクがあったのでそちらを通してから再訪。2のOracleを実装する問題。qubitの多数決をするOracleを実装する問題。3ビットの加算回路を作らないといけないんだけどAND演算をするのに必要なCCNOTを知らなくて困った。2のOracleが与えられるので、b[]を一発で知りたい。Bernstein-Vaziraniアルゴリズムを実装するだけの問題。それ聞いたことある...(Courseraで受けた量子コンピューティングの講師がVazirani先生だった)古典的には2^n回とか(確率的にはもっと少ない回数で)呼び出せば分かるのだけれど量子計算ではこれを1発で調べられるという有難い話。x全ビットに0+1を、yに0-1をセットしてOracleを1回呼び出す。なっているのをHしてMして検出する。2のb[]を一発で調べたい、という問題。E1の要領でやるとbは11111...になる。計測では見分けられない。(計測に他のパウリ基底を使えば行けるのかとか思ったけど行けなかった)これどうすればいい?って辺りで終了。解説読んだなるほど、bを厳密に合わせに行かなくてもよくて、Ufの中のbと、「立っているビットの数」の偶奇さえ一致していれば良い、と。Uf.ってそういう意味だったのね。Contest終わってた。結局最後の問題が一番正解者数少なかったのか。これなんかもう量子コンピューティング関係なくて完全にトンチだった気がするんだが...。2018トンチといえばトンチかな。algorithmの後に置かれてるのは罠。Code)をインストールして臨んだ本選。量子計算の知識は以前CourseraでVazirani教授の講義を受講したのと、池袋でやっていた量子情報勉強会に何度か参加したのが全てで、(Q#を含め)プログラムを書くのは今回が初めてでした。全完はできなかったものの、問題を解く過程で色々思い出したり調べたりでいい勉強になりました。Code(ってほとんどatomだった)でQ#(とC#)を触ってみて割と楽しかったことで、Microsoftチョットキライだった*1のが少し上書きされました。WarmupMSのQ#を使った量子コンピューティングのプログラミングコンテ...2012-08-10Courseraレポート(〜8/9)前回までのあらすじ量子力学&量子計算のクラスのみ受講中。»@naoya_t自然言語処理とか機械学習とか競技プログラミングとか。競プロ精進記録は別ブログ🔒に移しました。yukicoder遅延伝搬セグメント木の復習をしたので、beetさん作問のセグ木コンテスト(2019/9/6開催)の問題を解いてみた。サウスタワー23Fなんで自分に参加権が来たのかよく分からないオンサイトイベントに参加してきた話。146のQ4でN個の点の3次元マンハッタン距離の最大値を求める問題が出たのでメモ。"なお、接尾辞配列を構成するアルゴリズムは他にも多数存在しています。14:00-FORCIAさんで開催されたオンサイトのゆるふわコンテストに参加。過去問コンテスト後に読んだ問題たち。ここで出てくるテクニックもこの機会にぜひ身につけておきたい。