論文の概要: A 1.5-Query Lower Bound for the Unitary Synthesis Problem

• arxiv url: http://arxiv.org/abs/2508.13215v1
• Date: Sun, 17 Aug 2025 03:21:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-20 15:36:31.661349
• Title: A 1.5-Query Lower Bound for the Unitary Synthesis Problem
• Title（参考訳）: 単項合成問題に対する1.5クエリ下界
• Authors: Eric Huang,
• Abstract要約: 1.5クエリ設定と呼ばれる単位問題に対する新しい合成の下限を証明した。 疑似ランダム量子状態は1.5クエリに制限された敵に対して安全であることを示す。
• 参考スコア（独自算出の注目度）: 2.8554857235549753
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove a new lower bound for the unitary synthesis problem in the so-called 1.5-query setting. Our analysis establishes that any attempt to implement arbitrary n-qubit unitaries via limited oracle access requires resources that exceed the fractional query threshold. This result extends the one-query lower bound of Lombardi, Ma, and Wright (2023) to the fractional query regime, and introduces a conservative and chaining-based approach to handle intermediate query complexities. As a consequence, we derive cryptographic implications, showing that pseudorandom quantum states remain secure against adversaries restricted to 1.5 queries. Our work provides both conceptual clarification of fractional-query complexity and practical insights into the design of quantum cryptographic protocols.
• Abstract（参考訳）: 我々は、1.5-query と呼ばれる設定において、ユニタリ合成問題に対する新しい下界を証明した。 我々の分析は、限定的なオラクルアクセスによる任意のn-qubitユニタリの実装には、分数クエリしきい値を超えるリソースが必要であることを証明している。 この結果は、Lombardi, Ma, and Wright (2023) の1クエリ下界を分数的なクエリ構造に拡張し、中間的なクエリの複雑さを扱うための保守的で連鎖的なアプローチを導入している。 その結果、疑似ランダム量子状態は1.5クエリに制限された敵に対して安全であることを示し、暗号的含意を導出する。 我々の研究は、分数クエリの複雑さの概念的解明と量子暗号プロトコルの設計に関する実践的な洞察の両方を提供する。

関連論文リスト

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Quantile Multi-Armed Bandits with 1-bit Feedback [40.22079522118723]
  リスク感度と通信制約の要素を含むベストアーム識別のバリエーションについて検討する。 本研究では,雑音の多い二分探索をサブルーチンとして利用し,学習者が1ビットフィードバックによって定量報酬を推定できるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-10T17:03:33Z)
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.9208007322096533]
  一般高次量子計算におけるブール関数の問合せ複雑性について検討する。 最近導入された因果順序の量子制御を持つ量子回路のクラスは、クエリの複雑さを減らすことは不可能である。 因果不確定なスーパーマップを利用する場合、2つのクエリで計算できる最小誤差が厳密に低い関数がいくつか見つかる。
  論文  参考訳（メタデータ） (2023-07-18T13:12:55Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• Commitment capacity of classical-quantum channels [70.51146080031752]
  古典的量子チャネルに対するコミットメント能力の様々な概念を定義する。 条件エントロピーの観点から上界と下界のマッチングを証明した。
  論文  参考訳（メタデータ） (2022-01-17T10:41:50Z)
• Geometry of Banach spaces: a new route towards Position Based Cryptography [65.51757376525798]
  我々は幾何学的機能解析の観点から位置ベース量子暗号(PBQC)について検討し,その量子ゲームとの関係について考察した。 私たちが関心を持っている主な質問は、PBQCプロトコルのセキュリティを損なうために、攻撃者の連合が共有しなければならない、最適な絡み合いの量を求めることです。 より複雑なバナッハ空間の型プロパティの理解は、仮定を捨て、我々のプロトコルを攻撃するのに使用されるリソースに条件のない低い境界をもたらすことを示します。
  論文  参考訳（メタデータ） (2021-03-30T13:55:11Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Computing conditional entropies for quantum correlations [10.549307055348596]
  特に、デバイス非依存の量子鍵分布を実行するのに必要な、最小限の大域的検出効率について、新たな上限を求める。 正の整数に対するパラメータ $alpha_k = 1+frac12k-1$ を持つ反復平均量子 R'enyi の族を導入する。 この条件付きエントロピーは、デバイス非依存の最適化の文脈において、半定値プログラミング問題に緩和できる、特によい形式であることを示す。
  論文  参考訳（メタデータ） (2020-07-24T15:27:51Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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