論文の概要: Quantum Query-Space Lower Bounds Using Branching Programs

• arxiv url: http://arxiv.org/abs/2407.06872v1
• Date: Tue, 9 Jul 2024 13:58:53 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-10 17:47:35.270909
• Title: Quantum Query-Space Lower Bounds Using Branching Programs
• Title（参考訳）: 分岐プログラムを用いた量子クエリ空間下界境界
• Authors: Debajyoti Bera, Tharrmashastha SAPV,
• Abstract要約: GQBPの制限されたバージョンに対する、最初の明示的なクエリ空間の低いバウンダリを示す。 次に、問題を一般化して、ハミング距離が一定である2つの弦の間を決定するために、同じ境界が成り立つことを示す。 我々の結果は、任意の非コンスタント対称ブール関数の問合せ複雑性に基づく$Omega(sqrtn)$-lower境界の代替証明を生成する。
• 参考スコア（独自算出の注目度）: 0.18416014644193066
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Branching programs are quite popular for studying time-space lower bounds. Bera et al. recently introduced the model of generalized quantum branching program aka. GQBP that generalized two earlier models of quantum branching programs. In this work we study a restricted version of GQBP with the motivation of proving bounds on the query-space requirement of quantum-query circuits. We show the first explicit query-space lower bound for our restricted version. We prove that the well-studied OR$_n$ decision problem, given a promise that at most one position of an $n$-sized Boolean array is a 1, satisfies the bound $Q^2 s = \Omega(n^2)$, where $Q$ denotes the number of queries and $s$ denotes the width of the GQBP. We then generalize the problem to show that the same bound holds for deciding between two strings with a constant Hamming distance; this gives us query-space lower bounds on problems such as Parity and Majority. Our results produce an alternative proof of the $\Omega(\sqrt{n})$-lower bound on the query complexity of any non-constant symmetric Boolean function.
• Abstract（参考訳）: 分岐プログラムは時間空間の低い境界を研究するのに非常に人気がある。 Bera らは最近、一般化量子分岐プログラム aka のモデルを導入した。 量子分岐プログラムの以前の2つのモデルを一般化したGQBP。 本研究では,GQBPの制限バージョンについて検討し,量子クエリ回路のクエリ空間要求に対する限界を証明した。 制限されたバージョンに対する最初の明示的なクエリスペースの低いバウンドを示す。 良く研究されたOR$_n$決定問題(英語版)は、$n$サイズのブールアレイの少なくとも1つの位置が 1 であることから、有界な$Q^2 s = \Omega(n^2)$ を満たすことを証明し、$Q$ はクエリの数を表し、$s$ は GQBP の幅を表す。 次に、この問題を一般化して、ハミング距離が一定である2つの弦間の決定において、同じ境界が成り立つことを示す。 我々の結果は、任意の非コンスタント対称ブール関数の問合せ複雑性に基づく$\Omega(\sqrt{n})$-lowerの代替証明を生成する。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Space-bounded quantum state testing via space-efficient quantum singular value transformation [2.647089498084052]
  空間有界量子計算のための新しい完全特徴付けを提案する。 片側エラー(単位coRQL)と片側エラー(BQL)の設定について検討する。 この結果から,空間境界状態試験問題はすべて同じクラスに対応することが明らかとなった。
  論文  参考訳（メタデータ） (2023-08-09T17:16:19Z)
• A Generalized Quantum Branching Program [0.5584060970507505]
  本稿では,GQBPと呼ばれる量子分岐プログラムモデルを提案する。 我々は、GQBPとAQBP、GQBPとNQBP、GQBPとクエリ複雑度の間にいくつかの等価性を示す。
  論文  参考訳（メタデータ） (2023-07-21T07:27:51Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Approximate degree lower bounds for oracle identification problems [19.001036556917818]
  本稿では,特定のオラクル識別問題に対する近似次数下界を証明するためのフレームワークを提案する。 我々の下界は、大域関数と等値関数に対するランダムな通信上界によって駆動される。
  論文  参考訳（メタデータ） (2023-03-07T14:30:28Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Towards Optimal Separations between Quantum and Randomized Query Complexities [0.30458514384586394]
  入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。 任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
  論文  参考訳（メタデータ） (2019-12-29T01:42:31Z)

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

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