論文の概要: Verifiable quantum advantage based on polynomials with planted structures

• arxiv url: http://arxiv.org/abs/2609.39918v1
• Date: Wed, 30 Sep 2026 15:08:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.95925
• Title: Verifiable quantum advantage based on polynomials with planted structures
• Title（参考訳）: 植込み構造を持つ多項式に基づく検証可能な量子優位性
• Abstract要約: 検証可能なシミュレーションシークレットのアイデアを,検証可能な優位性のために開発する。 検証者はシミュレーション秘密を使って、クロスエントロピーテストを評価することができる。
• 参考スコア（独自算出の注目度）: 13.376362080307027
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also verifiable just from the classical outputs of the quantum computation. Here, we develop the idea of simulation secrets for verifiable advantage. A verifier can use a simulation secret to evaluate a cross-entropy test faster than it would take a classical adversary to pass the test. We instantiate this idea using IQP circuits described by cubic polynomials with planted independent spaces. These correspond to the largest independent set in the orbit of a polynomial under the general linear group and yield a low-rank stabilizer decomposition of the corresponding state. We conjecture that large independent spaces are invisible to a computationally bounded adversary, and therefore they cannot exploit them to pass the protocol. A second conjecture regards the fine-grained complexity of producing samples that pass the cross-entropy test for uniformly random polynomials. Under these conjectures, our scheme results in a polynomial gap between the verification time and the time a classical adversary would need to pass the protocol---both are exponential. It has a potential application to generating classically certifiable randomness, since the output distributions have high min-entropy. We estimate that the planted polynomial scheme is implementable using 100 logical qubits at logical error rates around $10^{-6}$.
• Abstract（参考訳）: 量子優位理論における中心的な問題は、量子計算の古典的な出力からのみ検証可能なランダム回路サンプリングと同様のリソース要求を持つ量子優位プロトコルが存在するかどうかである。 本稿では,シミュレーションシークレットのアイデアを検証可能な優位性のために開発する。 検証者はシミュレーション秘密を使って、クロスエントロピーテストを評価することができる。 我々は、このアイデアを、植込み独立空間を持つ立方体多項式によって記述されたIQP回路を用いてインスタンス化する。 これらは一般線型群の下で多項式の軌道上の最大の独立集合に対応し、対応する状態の低ランク安定化器分解をもたらす。 我々は、大きな独立空間は計算的に有界な敵に見えず、それを利用してプロトコルを通過させることはできないと推測する。 第2の予想は、一様ランダム多項式のクロスエントロピーテストに合格するサンプルの生成のきめ細かい複雑さを考慮したものである。 これらの予想の下で、我々のスキームは検証時間と古典的敵がプロトコルを通過しなければならない時間との間に多項式ギャップをもたらす。 出力分布がminエントロピーが高いため、古典的に証明可能なランダム性を生成する可能性がある。 植込み多項式スキームは,100個の論理量子ビットを用いて,論理誤差率10^{-6}$で実装可能であると推定する。

関連論文リスト

• Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity [0.30458514384586394]
  量子暗号の時間境界メタ複雑化プログラムを開始する。 最近の研究は、ワンウェイ関数を持たない量子暗号の最小探索プリミティブであるワンウェイパズルを特徴づけている。
  論文  参考訳（メタデータ） (2026-09-02T14:54:44Z)
• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。 浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
  論文  参考訳（メタデータ） (2026-09-01T15:54:34Z)
• Peaked quantum advantage using error correction [0.0]
  現在の量子優位実験の重要な問題は、それらの検証が理想的な計算の完全なシミュレーションを必要とすることである。 これは、実験を正確に検証できる体制を、それらがシミュラブルである体制に制限する。 我々は、新しい量子優位性-隠れコードサンプリング--を条件付きピークとする提案により、この問題を進展させる。
  論文  参考訳（メタデータ） (2025-10-06T18:31:10Z)
• The hardness of quantum spin dynamics [1.1999555634662633]
  量子スピンハミルトニアンの幅広いクラスが生成する出力分布からのサンプリングは、古典コンピュータにとって難しい問題であることを示す。 約200スピンのインスタンスは、古典的なデバイスでは難しいが、フォールトトレラント量子ビットを持つ中間スケールの量子コンピュータでは実現可能であると推定する。
  論文  参考訳（メタデータ） (2023-12-12T19:00:03Z)
• 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)
• A game of quantum advantage: linking verification and simulation [0.0]
  本稿では,二つのエージェント間の相互作用ゲームとして,懐疑論に対する量子優位性を証明したフォーマリズムを提案する。 もう一人のプレイヤーである懐疑的なアリスは、ボブのデバイスの統計を再現する模擬分布を提案することができる。
  論文  参考訳（メタデータ） (2020-11-24T15:51:33Z)
• Post-Quantum Multi-Party Computation [32.75732860329838]
  我々は、悪質な時間量子敵に対するセキュリティを備えた古典的機能(平易なモデル)のマルチパーティ計算について研究する。 誤差付き学習における超ポリノミカル量子硬度(LWE)とLWEに基づく円形セキュリティ仮定の量子硬度を仮定する。 その過程で、私たちは独立した関心を持つ可能性のある暗号プリミティブを開発します。
  論文  参考訳（メタデータ） (2020-05-23T00:42:52Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  ランダム量子回路は古典的にシミュレートするのは難しいと見なされる。 典型例の近似シミュレーションは, 正確なシミュレーションとほぼ同程度に困難であることを示す。 また、十分に浅いランダム回路はより一般的に効率的にシミュレーション可能であると推測する。
  論文  参考訳（メタデータ） (2019-12-31T19:00:00Z)

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

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