論文メモ
興味の赴くままに読んだ論文に関するメモを、備忘録として残していきます。（ホームページにこれを公開しておくのは、単純に書き残すモチベーションを維持するためです。）
コメントやご指摘等がありましたら、お気軽にtwitter(@kjroooo)にリプ、DM、又はryotaro.suzuki(at)fu-berlin.deにメールを頂けると幸いです。
10/15
by Fernando G.S.L. Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill
個人的に好きな論文の一つ。来週、博士学生の同僚とこれに関して議論するので、読み返していた。
さて、「サイズT*ランダム量子回路の複雑性が、ある指数時間までTに比例する」というブラウン(Brown)-サスキンド(Susskind)予想がある。（この予想はAdS/CFT対応の文脈で出てきた。）その解決に向けて書かれたのがこちらの論文である。著者らは、「強い複雑性」という指標を定義し、強い複雑性がTの1/11乗に比例することを示した。ここで、ある状態が強い複雑性 r を持つとは、どんなサイズ r の量子測定（つまり、サイズ r の量子回路＋計算基底での測定）をその状態に行っても、ある許された誤差以内で完全混合状態と識別されないことを言う。直感的に言えば、r 程度の解像度では純粋状態か混合状態かが見分けがつかない状態である。ユニタリ演算子に対しても、完全脱分極チャンネル(completely deporlarizing channel)との識別を用いて同様に定義される。
名前から想像できる通り、 状態（又は、ユニタリ）が強い複雑性 r を持つならば、それは回路複雑性 r を持つ**。ここで、逆は必ずしも成り立たない。もし状態が|ψ>と|0>の直積状態であれば、|ψ>がどんなに大きな回路複雑性を持っていても、2つめの部分系に対して計算基底で測定すればいいからである。
証明には、ランダム量子回路が効率よく近似ユニタリデザインを成すことを用いている。（それを初めに示したこの論文もとても面白い。また、近似ユニタリデザインと回路複雑性の関係については、こちらの面白い先行研究がある。）
具体的には、ランダム回路が近似 t-デザインを成すならば、その強い複雑性が t 以上になることが示された。強い複雑性がTの1/11乗に比例するのは、t-デザインを成すために必要なゲート数が t の11乗に比例することに由来する。（ちなみに最近の同僚の研究で、これが約5乗に改善された。）
複雑性を状態識別の観点から定義するのは面白いと思う。状態識別の概念は物理の色々なところに顔を出す***ので、それら物理現象と複雑性を状態識別を通して結びつけるような研究は楽しそうだ。
*：ある量子回路のサイズとは、局所ゲートの数のことである。通常は、ランダム量子回路は2-quditゲートから構成されている。
**：状態が回路複雑性 r をもつとは、あるサイズ r の量子回路ではその状態が生成されるが、サイズが r 未満のどんな量子回路でもそれが生成されないことである。
***：例えば、孤立系の熱平衡化はある純粋状態とギブス状態の識別可能性で定義できる。
10/12
by John S. Van Dyke, George S. Barron, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou
量子コンピュータを用いてベーテ仮説固有状態（BAE）を生成するアルゴリズムを提案した論文。具体的に、厳密可解模型であるXXZ模型の固有状態を効率よく生成する手法が書かれている。ここで、可解とは言っても高次相関関数を古典的に求めることは現状難しいらしい。量子コンピュータ上ではそれを簡単に測定できるので、中規模量子コンピュータの応用先の一つとして有益そうだ。
また、この論文の趣旨とは異なるが、BAEを用いて（例えば一体相関関数などが）古典シミュレート可能な量子回路をつくれないか考えてみるのは面白そうだ。例えばクリフォード回路に対応付けると、スタビライザー状態がBAEに、クリフォード演算子はBAEをBAEに写す演算子に対応する、といった感じである（上手くいくか全くわからないが）。
10/10
Entanglement dynamics of random quantum channels
by Zhi Li, Shengqi Sang, and Timothy H. Hsieh
量子ダイナミクスの下で、エンタングルメントなどの量子相関がどのように時間発展するかを特徴づけることは面白い問題である。近年、エンタングルメントエントロピーの時間発展が解析的に求められるトイモデルとして、ランダムユニタリ回路が研究されている（その発端となった論文）。ランダム回路のRenyiエントロピーなどの情報量は、ある古典統計力学モデルの分配関数にマップされることが知られており、それを用いた解析研究もある。
この論文では、その古典統計力学モデル対応を用いて、ランダム量子通信路（ランダムユニタリ回路＋deporlarizingノイズ）における相互情報量のダイナミクスを計算している。ランダムユニタリ回路の場合は、情報量の計算は3体相互作用ポッツモデルのdomain wallの数え上げ問題に帰着されるが、今回の場合も同様にdomain wallを数え上げて計算している。開放系のランダム回路でなにか情報量を計算するというのは、まだまだ研究できることがありそう。（ただノイズを入れると、一点だけ他の状態と異なるようなとても小さいdomain wallがleading termとして効いてきそうなのに、どうしてこれが入っていないのかが分からなかった。）
10/8
On the sampling complexity of open quantum systems
by Isobel A. Aloisio, Gregory A. L. White, Charles D. Hill, and Kavan Modi
量子多体系がどのような場合に効率よく古典計算機によってシミュレートされないか（又は、されるか）は量子計算における重要なテーマである。この論文では、量子開放系の古典シミュレート困難性をsampling complexityの観点から調べている。新しい点として、これまでのボソンサンプリングやランダム量子回路のサンプリングでは、終状態に対して一斉に1-qubit測定をするが、今回は各時刻ごとにある1-qubitを測定している。つまり、同一時間での測定だったものを同一空間での測定に置き換えている（著者らは、多重時間過程と読んでいる。また、測定していないqubitsを環境系とみなしている。）。この問題設定は、Aaronsonの隠れた変数理論と計算複雑性に関する論文から着想を得ているらしい。また想像通り、そのサンプリング問題は、通常の（同一時間上の）サンプリング問題と同程度に難しいことが示されている。
ただ開放系であると言っても、hardnessを示すためには対象系と環境系のユニタリをコントロールしないといけないので、注意が必要である。新規性は、開放系を考えたというよりは同一空間でのサンプリングを定義したことにあると思う。空間方向と時間方向を置き換える手法は、個人的に興味をもって研究しているdual-unitaryと相性が良さそうだ。例えば、定数サイズqubitsで時間をスケールさせた場合のランダムdual-unitary回路のサンプリング困難性が示せれたら面白そう。
10/7
Thermalization without eigenstate thermalization
by Aram W. Harrow and Yichen Huang
量子アルゴリズムやランダムネスで有名なHarrowの新作ということで気になったので読んでみた。
孤立量子系（純粋状態）の熱平衡化を説明する一つのメカニズムとして、すべての固有状態が局所的に見て熱的であるという仮説（ETH）がある。この論文では、ETHを満たさないが熱平衡化する反例として、可積分系に近いSYK模型があることが示された。（この反例には、森さんと白石さんの先行研究がある。）SYK模型とは、全結合ランダム相互作用のフェルミオン系であり、その相互作用が弱い場合を調べている。
全系をみると純粋状態なので、どのくらい局所的に見るか（何個のフェルミオンのみを見るか）が重要である。論文によると、フェルミオンN個の系では、√N以上でかつN/logNより小さい数L個のフェルミオンのみを見れば（ほかはトレースアウトする）、ETHを満たさないが熱平衡化するようだ。ちなみに、√N以下では、ETHを満たしている。
手法として、各固有状態がランダムなガウシアン状態で近似できることを用いている。ガウシアン状態は直積でかけるので、忠実度が簡単に計算されている。ETHを満たさないことの証明は大丈夫だが、なぜ平衡化するかがよくわからなかった。次に出る同じ著者らの論文で詳しく説明されそうなので、そちらもまた読もう。
2022/10/6
Quantum chaos and the complexity of spread of states
by Vijay Balasubramanian, Pawel Caputa, Javier Magan, and Qingyue Wu.
量子系において”複雑性”がどのように時間発展によって増大するかは、量子情報・物性・重力の境界領域にある、とても興味深いテーマである。量子状態の複雑性の指標には、circuit complexity、Nielsen's complexity、（その状態を用いた計算の）計算複雑性など様々あるが、この論文では新しい指標として"spread complexity"を提案している。これは、ある基底（Krylov基底から作ったもの）で固定したときに、時間発展する量子状態がどのようにその基底の上に広がっていくかを測った値である。そして、その基底で固定したときの広がり具合値は、すべての基底の中で最小値を取ることが示されている。（定義で各基底ベクトルに異なる重みをつけている（式3）が効いていそう。）
この複雑性は、circuit complexityやNielsen's complexityと違って何かを最小化をする必要がないので、計算が比較的簡単にできるメリットがある。（例えば、circuit complexityではある状態を生成する量子回路のサイズを最適化しなければいけない。）実際、いくつかの例でこの量を計算していて、具体的にランダムハミルトニアンダイナミクスでは、TFD状態のspread complexityが線形増大してピークに達したあと、少し線形に減少して定常値に落ち着いている。著者らいわく、このピークからの減少度合いは、ランダム行列理論のspectral rigidityというものにに起因するらしい（ランダム行列理論ちゃんと勉強しなくては）。complexityの振る舞いにランダム行列理論の普遍性が絡んでくるのは面白い。
広がり具合といえば、ボソンサンプリングなどのsampling complexityで重要なanti-concentrationも似た量（こちらはKrylov基底ではなく計算基底）を考えているが、何か繋がらないだろうか。