論文の概要: Random regular graph states are complex at almost any depth

• arxiv url: http://arxiv.org/abs/2412.07058v1
• Date: Mon, 09 Dec 2024 23:44:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-11 14:35:29.101831
• Title: Random regular graph states are complex at almost any depth
• Title（参考訳）: ランダム正則グラフ状態は、ほぼどんな深さでも複素である
• Authors: Soumik Ghosh, Dominik Hangleiter, Jonas Helsen,
• Abstract要約: グラフ状態は、その単純な古典的記述とリッチな絡み合い構造のために、量子情報理論の基本的な対象である。 私たちにとって、それらは回路接続、絡み合い構造、計算複雑性の関係を理解するためのおもちゃモデルです。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Graph states are fundamental objects in the theory of quantum information due to their simple classical description and rich entanglement structure. They are also intimately related to IQP circuits, which have applications in quantum pseudorandomness and quantum advantage. For us, they are a toy model to understand the relation between circuit connectivity, entanglement structure and computational complexity. In the worst case, a strict dichotomy in the computational universality of such graph states appears as a function of the degree $d$ of a regular graph state [GDH+23]. In this paper, we initiate the study of the average-case complexity of simulating random graph states of varying degree when measured in random product bases and give distinct evidence that a similar complexity-theoretic dichotomy exists in the average case. Specifically, we consider random $d$-regular graph states and prove three distinct results: First, we exhibit two families of IQP circuits of depth $d$ and show that they anticoncentrate for any $2 < d = o(n)$ when measured in a random $X$-$Y$-plane product basis. This implies anticoncentration for random constant-regular graph states. Second, in the regime $d = \Theta(n^c)$ with $c \in (0,1)$, we prove that random $d$-regular graph states contain polynomially large grid graphs as induced subgraphs with high probability. This implies that they are universal resource states for measurement-based computation. Third, in the regime of high degree ($d\sim n/2$), we show that random graph states are not sufficiently entangled to be trivially classically simulable, unlike Haar random states. Proving the three results requires different techniques--the analysis of a classical statistical-mechanics model using Krawtchouck polynomials, graph theoretic analysis using the switching method, and analysis of the ranks of submatrices of random adjacency matrices, respectively.
• Abstract（参考訳）: グラフ状態は、その単純な古典的記述とリッチな絡み合い構造のために、量子情報理論の基本的な対象である。 また、量子擬似ランダム性や量子優位性に応用できるIQP回路にも密接に関係している。 私たちにとって、それらは回路接続、絡み合い構造、計算複雑性の関係を理解するためのおもちゃモデルです。 最悪の場合、そのようなグラフ状態の計算普遍性の厳密な二分法は正規グラフ状態 [GDH+23] の次数$d$の関数として現れる。 本稿では、ランダムな積ベースで測定された場合、ランダムなグラフ状態のシミュレーションを行う平均ケース複雑性の研究を開始し、その平均ケースに同様の複雑性-理論的二分法が存在するという明確な証拠を与える。 具体的には、ランダムな$d$正規グラフ状態を検討し、以下の3つの異なる結果を証明する: まず、深さ$d$のIQP回路の2つの族を示し、ランダムな$X$-Y$平面積ベースで測定した場合、任意の2 < d = o(n)$に対して反集中化を示す。 これはランダムな定数正則グラフ状態に対する反集中を意味する。 第二に、$d = \Theta(n^c)$ with $c \in (0,1)$において、ランダムな$d$正規グラフ状態は、高い確率で誘導された部分グラフとして多項式的に大きな格子グラフを含むことを証明している。 これは、測定に基づく計算の普遍的な資源状態であることを意味する。 第三に、高次(d\sim n/2$)の状態では、ランダムグラフ状態はハール乱状態とは異なり、自明に古典的にシミュレートできるほどに絡み合っていないことを示す。 3つの結果の証明には, クラウチョック多項式を用いた古典的統計力学モデルの解析, 切替法を用いたグラフ理論解析, ランダム隣接行列の下位行列のランク解析など, 様々な手法が必要である。

関連論文リスト

• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  フービニ・スタディ計量に基づく絡み合い尺度は、Cocchiarellaと同僚によって最近導入された。 本稿では,多モードガウス状態に対する幾何絡み合いの一般化であるガウスエンタングルメント尺度(GEM)を提案する。 自由度の高い系に対する計算可能な多部絡み合わせ測度を提供することにより、自由なボゾン場理論の洞察を得るために、我々の定義が利用できることを示す。
  論文  参考訳（メタデータ） (2024-01-31T15:50:50Z)
• Local random quantum circuits form approximate designs on arbitrary architectures [0.1977825609388727]
  エッジが許容される2$-qudit相互作用を決定する任意の連結グラフ上のランダム量子回路(RQC)を考える。 有界次数と高さを持つグラフ上のRQCは、$O(mathrmpoly(k))$ gates の後、$k$-designs となる。 我々は、RQCが回路サイズで近似設計を生成するグラフのより大きなクラスを同定する。
  論文  参考訳（メタデータ） (2023-10-30T08:48:14Z)
• Analysis and Approximate Inference of Large Random Kronecker Graphs [4.417282202068703]
  大規模なランダムクロネッカーグラフの隣接性は分解可能であることを示す。 本稿では,鍵グラフパラメータを推論するデノワーズ・アンド・ソルブの手法を提案する。
  論文  参考訳（メタデータ） (2023-06-14T13:09:38Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。 我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-10-05T09:39:51Z)
• How to Teach a Quantum Computer a Probability Distribution [0.0]
  正規グラフ上の離散時間量子ウォークを確率分布として教える。 また、ハードウェアやソフトウェアに関する懸念や、即時アプリケーション、機械学習へのいくつかの関連についても論じる。
  論文  参考訳（メタデータ） (2021-04-15T02:41:27Z)
• The principle of majorization: application to random quantum circuits [68.8204255655161]
  i) 普遍的、ii) 古典的シミュラブル、iii) 普遍的、古典的シミュラブルの3つのクラスが考慮された。 回路のすべての族が平均的に正規化の原理を満たすことを検証した。 明らかな違いは、状態に関連したローレンツ曲線のゆらぎに現れる。
  論文  参考訳（メタデータ） (2021-02-19T16:07:09Z)
• Bosonic and fermionic Gaussian states from Kähler structures [0.0]
  ボソニックおよびフェルミオンガウス状態は、その線型複素構造$J$によって一意に特徴づけられることを示す。 これらの手法を, 絡み合いと複雑性の研究, (B) 安定系の力学, (C) 駆動系の力学に応用する。
  論文  参考訳（メタデータ） (2020-10-29T12:21:47Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。