論文の概要: From Promises to Totality: A Framework for Ruling Out Quantum Speedups

• arxiv url: http://arxiv.org/abs/2603.29256v1
• Date: Tue, 31 Mar 2026 04:29:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-01 15:25:03.151515
• Title: From Promises to Totality: A Framework for Ruling Out Quantum Speedups
• Title（参考訳）: PromisesからTotalityへ - 量子スピードを向上するためのフレームワーク
• Authors: Thomas Huffstutler, Upendra Kapshikar, David Miloschewsky, Supartha Podder,
• Abstract要約: 部分ブール関数がスーパーポリノミカルな量子クエリの高速化を示すことができる(そしてできない)かどうかを考察する。 本稿では,2つのレンズを用いて,このようなスピードアップを排除するための一般的なフレームワークを開発する。
• 参考スコア（独自算出の注目度）: 1.6332728502735252
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study when partial Boolean functions can (and cannot) exhibit superpolynomial quantum query speedups, and develop a general framework for ruling out such speedups via two complementary lenses: promise-aware complexity measures and function completions. First, we introduce promise versions of standard combinatorial measures (including block sensitivity and related variants) and prove that if the relevant promise and completion measures collapse, then deterministic and quantum query complexities are necessarily polynomially related, i.e., $D(f)=poly(Q(f))$. We then analyze structured families of promises, including symmetric partial functions and promises supported on Hamming slices, obtaining sharp (up to polynomial factors) characterizations in terms of a single gap parameter for the symmetric case and refined slice-dependent bounds for $k$-slice domains. Next, we formalize completion complexity as the minimum of a measure over total completions of a partial function, and show that completability of a measure captures the possibility of superpolynomial quantum speedups. Finally, we apply this viewpoint to derive broad non-speedup criteria for some classes of functions admitting well-behaved completions, such as functions with low maximum influence on both the standard and $p$-biased hypercubes and functions with efficiently identifiable domains, and then show some hardness results for general completion techniques.
• Abstract（参考訳）: 部分ブール関数がスーパーポリノミカルな量子クエリ・スピードアップを示すことができる(そしてできない)かどうかを考察し、2つの補完レンズ(promise-aware complexity measures)と関数完備化(Function completions)によってそのようなスピードアップを決定するための一般的なフレームワークを開発する。 まず、標準組合せ測度(ブロック感度および関連する変種を含む)の公約バージョンを導入し、関連する公約と完備化測度が崩壊した場合、決定論的および量子的クエリ複雑度は必ずしも多項式関係である、すなわち$D(f)=poly(Q(f))$であることを示す。 次に、対称部分関数やハミングスライスで支持される約束を含む約束の構造化された族を解析し、対称ケースの1つのギャップパラメータと$k$-スライス領域の洗練されたスライス依存境界の観点から、鋭い(多項式因子まで)特徴付けを得る。 次に、部分関数の完全完備化に対する尺度の最小値として完備化複雑性を定式化し、その尺度の完全性は超多項式量子スピードアップの可能性を捉えることを示す。 最後に、この視点を適用し、例えば、標準および$p$のバイアス付きハイパーキューブと効率的に識別可能なドメインを持つ関数の両方に最も影響の小さい関数や、一般的な補完技法の硬さを示すような、良好な完備化を許容する関数のクラスに対して、幅広い非スピードアップ基準を導出する。

関連論文リスト

• Multi-Property Synthesis [69.79949693440426]
  複数の特性を持つ合成について研究し、全ての特性を満たすことは不可能かもしれない。 プロパティのサブセットを列挙する代わりに、製品ゲーム状態とそれらから実現可能なゴールセットの関係を1つの固定点計算で計算する。
  論文  参考訳（メタデータ） (2026-01-15T18:18:33Z)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  QAMA(Quantum Annealing Multi-Head Attention)は、エネルギーベースのハミルトン最適化問題として注目を集める新しいドロップイン演算子である。 この枠組みでは、トークン相互作用を二項二項項に符号化し、低エネルギー構成の探索に量子アニールを用いる。 経験的に、自然言語と視覚のベンチマークによる評価は、タスク全体にわたって、標準的なマルチヘッドの注意から少なくとも2.7ポイントの精度が低下していることを示している。
  論文  参考訳（メタデータ） (2025-04-15T11:29:09Z)
• Generalized Rényi entropy accumulation theorem and generalized quantum probability estimation [0.0]
  エントロピー蓄積定理は、多くのデバイス依存およびデバイス非依存の暗号プロトコルのセキュリティ解析において強力なツールである。 Affine min-tradeoff関数の構築に依存しており、実際に最適に構築することはしばしば困難である。 新たにエントロピー蓄積境界が導出され,有限サイズ性能が著しく向上した。
  論文  参考訳（メタデータ） (2024-05-09T17:11:00Z)
• Decoupling by local random unitaries without simultaneous smoothing, and applications to multi-user quantum information tasks [0.0]
  単純なテレスコープ和のトリックは、三角形の不等式とランダムチャネルの予測収縮係数のテンソル化特性とともに、局所的な動作によって複数のユーザに対して一般的な同時疎結合を実現することができることを示す。 我々は、スムーズなミンエントロピーの1ショット設定やR'enyiエントロピーの有限ブロック長設定のいずれにおいても、理想デカップリングから期待される偏差の有界を得る。 これは量子シャノン理論におけるいくつかのタスクに対して、1ショット、有限ブロック長、同時達成性をもたらす。
  論文  参考訳（メタデータ） (2023-04-24T14:17:32Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• Efficient Neural Network Analysis with Sum-of-Infeasibilities [64.31536828511021]
  凸最適化における総和係数法に着想を得て,広範な分岐関数を持つネットワーク上での検証クエリを解析するための新しい手法を提案する。 標準ケース分析に基づく完全探索手順の拡張は、各検索状態で実行される凸手順をDeepSoIに置き換えることによって達成できる。
  論文  参考訳（メタデータ） (2022-03-19T15:05:09Z)

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

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