論文の概要: Approximate degree lower bounds for oracle identification problems

• arxiv url: http://arxiv.org/abs/2303.03921v2
• Date: Mon, 22 May 2023 16:22:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-24 03:52:05.256836
• Title: Approximate degree lower bounds for oracle identification problems
• Title（参考訳）: oracle の識別問題に対する近似次数下限
• Authors: Mark Bun, Nadezhda Voronova
• Abstract要約: 本稿では,特定のオラクル識別問題に対する近似次数下界を証明するためのフレームワークを提案する。 我々の下界は、大域関数と等値関数に対するランダムな通信上界によって駆動される。
• 参考スコア（独自算出の注目度）: 19.001036556917818
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string $x \in \{0, 1\}^n$ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of $x$. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of $\Omega(n/\log^2 n)$ for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.
• Abstract（参考訳）: ブール関数の近似次数は、それを点的に近似する実多項式の最小次数である。 どんなブール関数に対しても、その近似次数は量子クエリの複雑性の下限として役立ち、関連する関数に対する量子通信の下限まで一般的に持ち上げる。 我々は、特定のoracle識別問題に対して、近似次数下限を証明するためのフレームワークを導入し、隠れたバイナリ文字列 $x \in \{0, 1\}^n$ を回復することを目的としています。 我々の下位境界はこれらの問題の決定バージョンに適用され、そこでは$x$のパリティを計算することがゴールです。 順序付き探索と隠れ文字列問題に我々のフレームワークを適用し、それぞれ$\Omega(n/\log^2 n)$のほぼ密接な近似次下界を証明した。 これらの下位境界は弱非有界なエラー設定に一般化され、この状態における隠れ文字列問題に対する新しい量子クエリローバウンドを与える。 我々の下限は、大域および等値関数のランダム化通信上限によって駆動される。

関連論文リスト

• Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
  量子古典的階層 QCPH について検討する。これは、交互古典的量子化器の定数数で解ける言語のクラスである。 我々は、量子アルゴリズムに新しい切り換え補題を与えるが、これは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2024-10-24T18:12:03Z)
• Quantum Query-Space Lower Bounds Using Branching Programs [0.18416014644193066]
  GQBPの制限されたバージョンに対する、最初の明示的なクエリ空間の低いバウンダリを示す。 次に、問題を一般化して、ハミング距離が一定である2つの弦の間を決定するために、同じ境界が成り立つことを示す。 我々の結果は、任意の非コンスタント対称ブール関数の問合せ複雑性に基づく$Omega(sqrtn)$-lower境界の代替証明を生成する。
  論文  参考訳（メタデータ） (2024-07-09T13:58:53Z)
• Rank lower bounds on non-local quantum computation [0.0]
  非局所量子計算(NLQC)は、2つの量子システム間の相互作用を1ラウンドの通信と共有絡みによって置き換える。 NLQCの2つのクラス、$f$-routingと$f$-BB84を研究し、これは古典的な情報理論の暗号と量子位置の検証に関係している。
  論文  参考訳（メタデータ） (2024-02-28T19:00:09Z)
• A one-query lower bound for unitary synthesis and breaking quantum cryptography [7.705803563459633]
  ユニタリ合成問題では、任意の$n$qubitのユニタリ$U$を、任意のブール関数$f$を計算するオラクルで拡張された効率的な量子$A$で実装できるかどうかを問う。 本研究は, 対向する$Af$の最大成功確率を解析することにより, 下位境界の証明を可能にする, 効率的なチャレンジャーアドゲームとしてのユニタリ合成を証明する。
  論文  参考訳（メタデータ） (2023-10-13T05:39:42Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• 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)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。 我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
  論文  参考訳（メタデータ） (2022-02-10T18:59:52Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
  ゼロオーダーのオラクルを用いてサドルポイント問題を解くアルゴリズムをいくつか提案する。 解析により、この項の収束率は、一階法よりも$log n$因子の方が悪いことが示されている。 また、混合構成を考慮し、その部分に対してゼロ階のオラクルを使用する1/2階法を開発する。
  論文  参考訳（メタデータ） (2020-09-21T14:26:48Z)

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

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