論文の概要: Planted Cliques and Quantum Symmetry-Adapted Measurements
- arxiv url: http://arxiv.org/abs/2609.40310v3
- Date: Mon, 05 Oct 2026 13:47:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-07 04:43:28.488906
- Title: Planted Cliques and Quantum Symmetry-Adapted Measurements
- Title（参考訳）: 植物傾斜と量子対称性-適応測定-
- Abstract要約: 我々は、量子符号化とヒルベルト適応測定が、ある古典グラフから植えられた斜め検出のための情報を保存する方法を研究する。
コンパクトなバイナリ位相符号化では、定数検出には同じグラフの位相状態のコピー$(n1+2varepsilonlnn)$が必要であることを証明している。
- 参考スコア（独自算出の注目度）: 0.19116784879310025
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For $k=\lfloor n^{1/2-\varepsilon}\rfloor$, with fixed $0<\varepsilon<1/2$, detection is statistically possible but conjectured hard for polynomial-time classical algorithms. For a compact binary phase encoding, we prove that constant-advantage detection requires $Ω(n^{1+2\varepsilon}\ln^2 n)$ copies of the phase state of the same graph, even under arbitrary joint measurements. In the large-copy limit, the optimal decision rule thresholds the total number of $k$-cliques in the graph and its complement, but this characterization provides no efficient detector. We therefore explore measurements guided by the symmetries of the input distributions, starting with the efficient Schur transform on the full graph register. We show that weak Schur sampling, which measures only the representation label, depends only on edge count and has vanishing distinguishing power in this regime. When the label and multiplicity registers are discarded, the remaining quantum states are almost perfectly distinguishable. We show that the support of the planted state occupies only a vanishing fraction of the graph Hilbert space. Any subspace containing it still permits near-perfect detection if its relative dimension also vanishes. This gives us freedom to choose a subspace that is easier to measure. We propose exploring subgroup isotypic measurements to find such subspaces. Whether they can yield an efficient detector remains open. Finally, we show that a single supplied coherent quantum sample permits efficient detection, yielding a conditional computational separation from one classical sample under quantum planted-clique hardness.
- Abstract（参考訳）: 本研究では, 量子符号化と対称性適応測定が, 古典グラフからの植え込み斜め検出のための情報を保存する方法について検討する。
k=\lfloor n^{1/2-\varepsilon}\rfloor$に対して、固定された$0<\varepsilon<1/2$の場合、検出は統計的に可能であるが、多項式時間古典アルゴリズムでは難しい。
コンパクトな二値位相符号化では、任意の関節測定下であっても、定数アドバンテージ検出には同じグラフの位相状態のコピーが$Ω(n^{1+2\varepsilon}\ln^2 n)$必要であることが証明される。
大きなコピーの極限において、最適決定規則はグラフとその補数における$k$-cliquesの総数を閾値とするが、この特徴づけは効率的な検出器を提供しない。
したがって、入力分布の対称性によって導かれる測度を、全グラフレジスタ上の効率的なシュア変換から探索する。
表現ラベルのみを測定する弱いシュアサンプリングは、エッジカウントにのみ依存し、この状態におけるパワーの区別がなくなることを示す。
ラベルと多重度レジスタが破棄されると、残りの量子状態はほぼ完全に区別できる。
植物状態の支持がヒルベルト空間の消滅部分のみを占めることを示す。
この部分空間を含む任意の部分空間は、その相対次元が消えても、ほぼ完全な検出を許す。
これにより、測定が容易な部分空間を選択する自由が得られます。
そこで我々は,そのような部分空間を見つけるために,部分群アイソタイプの測定を提案する。
効率の良い検出器を作れるかどうかはまだ不明だ。
最後に、単一供給されたコヒーレント量子サンプルが効率的な検出を可能にし、量子プランクド・斜め硬度の下で1つの古典的サンプルから条件付き計算的分離が得られることを示す。
関連論文リスト
- Symmetry Constrained Quantum Error Mitigation for the Schwinger Model [39.146761527401424]
偏極雑音下でのゲージ理論のパリティ・フェルミオン数対称性を利用する。
ディジタル量子シミュレーションにおける対称性の検証について検討する。
論文 参考訳（メタデータ） (2026-08-21T13:49:11Z) - Scheme to Detect the Strong-to-weak Symmetry Breaking via Randomized Measurements [11.213906010203264]
最近の進歩は、新しい対称性を破るパターンを強調している。
強弱対称性の破れは、典型的にはR'enyi-2相関器のような多重レプリカ相関関数を用いて検出される。
本稿では,ランダム化計測ツールボックスを用いた実験において,強弱対称性の破れを検出するための実用的なプロトコルを提案する。
論文 参考訳（メタデータ） (2024-12-24T12:41:38Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。
サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。
格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
論文 参考訳（メタデータ） (2022-12-12T15:06:32Z) - Validation tests of GBS quantum computers give evidence for quantum
advantage with a decoherent target [62.997667081978825]
複数モードデータの検証に指紋としてグループカウント確率の正P位相空間シミュレーションを用いる。
偽データを解き放つ方法を示し、これを古典的なカウントアルゴリズムに適用する。
論文 参考訳（メタデータ） (2022-11-07T12:00:45Z) - Lower Bounds for Learning Quantum States with Single-Copy Measurements [2.7869568828212175]
量子トモグラフィーとシャドウトモグラフィーの問題点を,未知の$d$次元状態の個々のコピーを用いて測定した。
特に、この手法は、その複雑さの観点から、フォークロアのパウリ・トモグラフィー(Pauli tomography)アルゴリズムの最適性を厳格に確立する。
論文 参考訳（メタデータ） (2022-07-29T02:26:08Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。