論文の概要: Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies
- arxiv url: http://arxiv.org/abs/2204.10671v1
- Date: Fri, 22 Apr 2022 12:37:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-16 01:09:13.995112
- Title: Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies
- Title（参考訳）: 量子と古典的順序付き二項決定図の指数分離, 順序付け法と階層
- Authors: Kamil Khadiev, Aliya Khadieva and Alexander Knop
- Abstract要約: 量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
- 参考スコア（独自算出の注目度）: 68.93512627479197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study quantum Ordered Binary Decision Diagrams($OBDD$)
model; it is a restricted version of read-once quantum branching programs, with
respect to "width" complexity. It is known that the maximal gap between
deterministic and quantum complexities is exponential. But there are few
examples of functions with such a gap. We present a new technique
("reordering") for proving lower bounds and upper bounds for OBDD with an
arbitrary order of input variables if we have similar bounds for the natural
order. Using this transformation, we construct a total function $REQ$ such that
the deterministic $OBDD$ complexity of it is at least $2^{\Omega(n / \log n)}$,
and the quantum $OBDD$ complexity of it is at most $O(n^2/\log n)$. It is the
biggest known gap for explicit functions not representable by $OBDD$s of a
linear width. Another function(shifted equality function) allows us to obtain a
gap $2^{\Omega(n)}$ vs $O(n^2)$.
Moreover, we prove the bounded error quantum and probabilistic $OBDD$ width
hierarchies for complexity classes of Boolean functions. Additionally, using
"reordering" method we extend a hierarchy for read-$k$-times Ordered Binary
Decision Diagrams ($k$-$OBDD$) of polynomial width, for $k = o(n / \log^3 n)$.
We prove a similar hierarchy for bounded error probabilistic $k$-$OBDD$s of
polynomial, superpolynomial and subexponential width.
The extended abstract of this work was presented on International
Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June
8 -- 12, 2017
- Abstract（参考訳）: 本稿では,量子順序付き二分決定ダイアグラム($obdd$)モデルについて検討する。
決定論と量子複雑性の間の最大ギャップは指数的であることが知られている。
しかし、そのようなギャップを持つ関数の例はほとんどない。
自然順序に対する同様の境界がある場合、入力変数の任意の順序で obdd の下限と上限を証明できる新しい手法("reordering")を提案する。
この変換を用いて、決定論的$OBDD$複雑性が少なくとも$2^{\Omega(n / \log n)}$であり、量子$OBDD$複雑さが少なくとも$O(n^2/\log n)$であるような総関数$REQ$を構築する。
これは、線形幅の$OBDD$sで表現できない明示的な関数の最大のギャップである。
別の関数(シフト等式関数)は、ギャップ 2^{\Omega(n)}$ と $O(n^2)$ を得られる。
さらに,ブール関数の複雑性クラスに対する有界誤差量子および確率的$obdd$ width階層を証明した。
さらに、"順序付け"メソッドを使用して、$k = o(n / \log^3 n)$に対して、多項式幅の$k$Times Ordered Binary Decision Diagrams$k$-$OBDD$)の階層を拡張する。
有界誤差確率的k$-$obdd$s of polynomial, superpolynomial and subexponential width に対する同様の階層を証明した。
この研究の要約は、ロシアの国際コンピュータ科学シンポジウム、CSR 2017、カザン、ロシア、2017年6月8日 - 12日に発表された。
関連論文リスト
- Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳（メタデータ） (2023-06-02T17:49:35Z) - Pauli-based model of quantum computation with higher-dimensional systems [0.0]
パウリベースの計算(英: Pauli-based calculation、PBC)は、量子ビットを用いた量子計算の普遍モデルである。
奇数原始次元系のPBCを一般化し、その普遍性を実証する。
論文 参考訳（メタデータ） (2023-02-27T12:05:13Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - 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) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - 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) - Exact Quantum Query Algorithms Outperforming Parity -- Beyond The
Symmetric functions [3.652509571098291]
まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。
Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
論文 参考訳（メタデータ） (2020-08-14T12:17:48Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。