論文の概要: The state hidden subgroup problem and an efficient algorithm for locating unentanglement

• arxiv url: http://arxiv.org/abs/2410.12706v1
• Date: Wed, 16 Oct 2024 16:12:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-17 13:42:26.661693
• Title: The state hidden subgroup problem and an efficient algorithm for locating unentanglement
• Title（参考訳）: 状態隠れ部分群問題と非絡み合いの探索のための効率的なアルゴリズム
• Authors: Adam Bouland, Tudor Giurgica-Tiron, John Wright,
• Abstract要約: 我々は「隠されたカット問題」と呼ばれる絡み合いテストの一般化について研究する。 本稿では,隠されたカット問題を,慎重に選択されたアベリアグループアクションでステートHSPとして定式化する方法について述べる。 隠蔽状態のサンプリングは、よく知られたシモンの問題の変種として同様の結果をもたらすことを証明している。
• 参考スコア（独自算出の注目度）: 2.8125881524451235
• License:
• Abstract: We study a generalization of entanglement testing which we call the "hidden cut problem." Taking as input copies of an $n$-qubit pure state which is product across an unknown bipartition, the goal is to learn precisely where the state is unentangled, i.e. to determine which of the exponentially many possible cuts separates the state. We give a polynomial-time quantum algorithm which can find the cut using $O(n/\epsilon^2)$ many copies of the state, which is optimal up to logarithmic factors. Our algorithm also generalizes to learn the entanglement structure of arbitrary product states. In the special case of Haar-random states, we further show that our algorithm requires circuits of only constant depth. To develop our algorithm, we introduce a state generalization of the hidden subgroup problem (StateHSP) which might be of independent interest, in which one is given a quantum state invariant under an unknown subgroup action, with the goal of learning the hidden symmetry subgroup. We show how the hidden cut problem can be formulated as a StateHSP with a carefully chosen Abelian group action. We then prove that Fourier sampling on the hidden cut state produces similar outcomes as a variant of the well-known Simon's problem, allowing us to find the hidden cut efficiently. Therefore, our algorithm can be interpreted as an extension of Simon's algorithm to entanglement testing. We discuss possible applications of StateHSP and hidden cut problems to cryptography and pseudorandomness.
• Abstract（参考訳）: 我々は「隠されたカット問題」と呼ばれる絡み合いテストの一般化について研究する。 未知の二分法にまたがる積である$n$-qubit純状態の入力コピーとして、その状態がどこで絡み合っていないかを正確に学習すること、すなわち、指数的に多くの可能なカットのうちどれが状態を分離するかを決定することである。 多項式時間量子アルゴリズムは、$O(n/\epsilon^2)$多くの状態のコピーを用いてカットを見つけることができるが、これは対数係数に最適である。 我々のアルゴリズムは任意の積状態の絡み合い構造を学習するためにも一般化される。 Haar-random状態の特別な場合、我々のアルゴリズムは一定の深さしか持たない回路を必要とすることを示す。 このアルゴリズムを開発するために、隠れ対称性の部分群を学習するために、未知の部分群作用の下で量子状態不変量を与える、独立した関心を持つかもしれない隠れ部分群問題(StateHSP)の状態一般化を導入する。 本稿では,隠されたカット問題を,慎重に選択したアベリアグループアクションでステートHSPとして定式化する方法について述べる。 次に、隠されたカット状態上のフーリエサンプリングが、よく知られたシモン問題の変種として同様の結果をもたらすことを証明し、隠されたカットを効率的に見つけることができる。 したがって、我々のアルゴリズムは、絡み合いテストへのサイモンのアルゴリズムの拡張と解釈できる。 我々は、StateHSPと隠蔽切断問題を暗号や擬似ランダムネスに応用する可能性について論じる。

関連論文リスト

• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates [0.0]
  ガウスゲートの任意の数で用意された$n$フェルミオンモード上での学習状態の効率的なアルゴリズムを提案する。 我々の研究は、ガウス門をほとんど持たない状態の構造に光を当て、回路の複雑さを改良した上界を提供する。
  論文  参考訳（メタデータ） (2024-02-28T19:18:27Z)
• Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
  計算基底の部分集合である$S$に対する部分集合状態は [ frac1sqrt|S|sum_iin S |irangle である。 固定された部分集合サイズ $|S|=s$ に対して、$s = 2n/omega(mathrmpoly(n))$ と $s=omega(mathrmpoly(n))$ が与えられたとき、ランダムな部分集合状態は情報理論上はHaarランダム状態と区別できないことを示す。
  論文  参考訳（メタデータ） (2023-12-23T15:52:46Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• Dissipative ground state preparation and the Dissipative Quantum Eigensolver [0.0]
  H の基底状態部分空間に収束する局所 CPT 写像と停止条件を構築する。 この散逸性量子固有解法には多くの興味深い特徴があり、これは以前の基底状態生成アルゴリズムよりも有利である。
  論文  参考訳（メタデータ） (2023-03-21T15:50:06Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• An entanglement perspective on the quantum approximate optimization algorithm [0.0]
  ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。 また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
  論文  参考訳（メタデータ） (2022-06-14T17:37:44Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Low-Complexity Algorithm for Restless Bandits with Imperfect Observations [1.4542411354617986]
  我々は、強化学習と最適化において幅広い応用分野を見出す、レスレス・バンディット問題の一類を考察する。 我々は,観測誤差を伴う一般的なレスト・バンディット・モデルに容易に適用可能な,高い性能を実現する低複雑性アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-08-09T05:01:19Z)
• Free versus Bound Entanglement: Machine learning tackling a NP-hard problem [0.06091702876917279]
  高次元系の絡み合い検出は、効率的な方法が欠如しているため、NPハード問題である。 魔法のように対称な二分四重項状態の族を見つけ、自由絡み合うには82%$、確実に分離可能な場合は$2%$、有界絡みを持つには10%$がある。
  論文  参考訳（メタデータ） (2021-06-07T21:38:39Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)

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

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