論文の概要: Planted Cliques and Quantum Symmetry-Adapted Measurements

• arxiv url: http://arxiv.org/abs/2609.40310v2
• Date: Thu, 01 Oct 2026 17:18:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:23.57324
• Title: Planted Cliques and Quantum Symmetry-Adapted Measurements
• Title（参考訳）: 植物傾斜と量子対称性-適応測定-
• Abstract要約: 本研究では,古典標本の量子符号化,自然二相状態符号化,対称性適応測定の2つについて検討する。 二相状態の符号化には、任意の関節測定の下でも$(n1+2varepsilonlnn)$コピーが必要である。 フルグラフレジスタ上の対称性適応測定は、自然にシュル変換から生じる。
• 参考スコア（独自算出の注目度）: 0.19116784879310025
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The planted clique problem is a promising candidate for quantum advantage with a wide computational-statistical gap and substantial evidence for classical hardness. We study two quantum encodings of classical samples, a natural binary phase state encoding and symmetry-adapted measurements, and determine if they preserve enough information for planted-clique detection, as well as discuss their potential towards algorithmic efficiency. For the binary phase state encoding, we show that constant-advantage detection requires $Ω(n^{1+2\varepsilon}\ln^2 n)$ copies, even under arbitrary joint measurements. Repeated measurements on $O(n^2)$ copies suffice statistically above the logarithmic clique threshold. The symmetry-adapted measurements on the full graph register arise naturally from the Schur transform. We show that the outcome distribution of weak Schur sampling depends on the sampled graph only through its edge count and fails to distinguish the distributions; whereas retaining the representation label and Specht register after discarding multiplicity preserves distance $1-o(1)$. Near-perfect distinguishability survives even if the label is also discarded. We calculate the retained states, providing concrete targets for efficient measurement. Finally, we show that one supplied coherent quantum sample enables an efficient quantum distinguisher, which yields a conditional computational separation from one classical sample under quantum planted-clique hardness. Our results are structural and information-theoretic; efficient detection from one classical graph in the conjectured hard regime remains open.
• Abstract（参考訳）: プランテッド・クリッド問題(英語版)は、計算統計的ギャップが広く、古典的硬さの実質的な証拠を持つ量子的優位性の候補である。 本研究では,古典的サンプルの量子符号化,自然二相状態符号化,対称性適応測定の2つについて検討し,それらが植込み斜め検出に十分な情報を保持するかどうかを判断し,アルゴリズム効率に対するその可能性について考察する。 二相状態符号化では、任意の関節測定下であっても、定数アドバンテージ検出には$Ω(n^{1+2\varepsilon}\ln^2 n)$コピーが必要であることを示す。 O(n^2)$コピーの繰り返し測定は対数傾き閾値以上で統計的に十分である。 フルグラフレジスタ上の対称性適応測定は、自然にシュル変換から生じる。 弱いシュアサンプリングの結果の分布は、そのエッジ数を通してのみサンプリングされたグラフに依存し、分布の区別に失敗することを示し、一方、多重度を捨てた後に表現ラベルとSpechtレジスタは1-o(1)$で保存されることを示した。 ラベルも捨てられたとしても、ほぼ完全な識別性は残る。 留置状態の計算を行い, 効率的な測定を行うための具体的目標について検討した。 最後に, 供給されたコヒーレントな量子サンプルは, 量子プランド・斜め硬度下での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)

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

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