論文の概要: A Generalized Quantum Branching Program
- arxiv url: http://arxiv.org/abs/2307.11395v1
- Date: Fri, 21 Jul 2023 07:27:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-24 13:21:51.586695
- Title: A Generalized Quantum Branching Program
- Title(参考訳): 一般化量子分岐プログラム
- Authors: Debajyoti Bera and Tharrmashastha Sapv
- Abstract要約: 本稿では,GQBPと呼ばれる量子分岐プログラムモデルを提案する。
我々は、GQBPとAQBP、GQBPとNQBP、GQBPとクエリ複雑度の間にいくつかの等価性を示す。
- 参考スコア(独自算出の注目度): 0.5584060970507505
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Classical branching programs are studied to understand the space complexity
of computational problems. Prior to this work, Nakanishi and Ablayev had
separately defined two different quantum versions of branching programs that we
refer to as NQBP and AQBP. However, none of them, to our satisfaction, captures
the intuitive idea of being able to query different variables in superposition
in one step of a branching program traversal. Here we propose a quantum
branching program model, referred to as GQBP, with that ability. To motivate
our definition, we explicitly give examples of GQBP for n-bit Deutsch-Jozsa,
n-bit Parity, and 3-bit Majority with optimal lengths. We the show several
equivalences, namely, between GQBP and AQBP, GQBP and NQBP, and GQBP and query
complexities (using either oracle gates and a QRAM to query input bits). In way
this unifies the different results that we have for the two earlier branching
programs, and also connects them to query complexity. We hope that GQBP can be
used to prove space and space-time lower bounds for quantum solutions to
combinatorial problems.
- Abstract(参考訳): 古典分岐プログラムは計算問題の空間複雑性を理解するために研究されている。
この研究に先立ち、中西とアブラエフは、NQBPとAQBPと呼ばれる分岐プログラムの2つの異なる量子バージョンを別々に定義した。
しかし、私たちの満足のいくものはいずれも、分岐プログラムトラバースの一段階において、重ね合わせで異なる変数をクエリできるという直感的なアイデアを捉えていない。
本稿では,gqbpと呼ばれる量子分岐プログラムモデルを提案する。
我々の定義を動機づけるために、最適長を持つ n ビットのDeutsch-Jozsa, n ビットのパリティ, 3 ビットのプライマリティに対する GQBP の例を明示的に提示する。
本稿では,GQBPとAQBP,GQBP,NQBP,GQBP,およびGQBPと問合せ複雑度(オラクルゲートとQRAMを用いて入力ビットを問合せする)の等価性を示す。
このようにして、この2つの以前の分岐プログラムの異なる結果を統一し、それらをクエリの複雑さに結びつける。
我々は、gqbpが組合せ問題に対する量子解の空間と時空下限を証明するのに使えることを望んでいる。
関連論文リスト
- The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳(メタデータ) (2024-02-29T01:35:46Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Complexity and order in approximate quantum error-correcting codes [1.3108652488669732]
量子回路の複雑性と近似量子誤差補正(AQEC)特性の厳密な接続を確立する。
我々の重要な発見は、サブシステムの分散が$O(k/n)$しきい値以下であれば、コード部分空間の任意の状態は、回路の複雑さの低い境界に従わなければならないということである。
AQECのこの理論は、多体量子系の量子複雑性と順序を理解するための汎用的なフレームワークを提供する。
論文 参考訳(メタデータ) (2023-10-07T07:03:46Z) - Space-bounded quantum state testing via space-efficient quantum singular
value transformation [1.5469452301122177]
本稿では、一方の誤差(単位coRQL)と両側の誤差(BQL)の設定を含む空間有界量子計算の完全性について述べる。
この結果から,3つの測度すべてを考慮すると,空間境界状態試験問題は量子状態の生成と同じくらい容易に計算できることがわかった。
論文 参考訳(メタデータ) (2023-08-09T17:16:19Z) - stateQIP = statePSPACE [0.15229257192293197]
本研究では,SDPPSPACEと状態QIPの2つの状態クラスの関係について検討する。
私たちの主な結果は、リバースインクルージョン、stateQIP $subseteq$ statePSPACEです。
また、一般的な量子対話プロトコルの最適証明戦略を量子空間で実装できることも示している。
論文 参考訳(メタデータ) (2023-01-18T19:00:17Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。
これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
論文 参考訳(メタデータ) (2023-01-05T11:05:22Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - Quantum space, ground space traversal, and how to embed multi-prover
interactive proofs into unentanglement [0.0]
サビッチの定理は、NPSPACE計算はPSPACEでシミュレートできると述べている。
SQCMASPACE=NEXP のように、サビッチの定理の量子アナログが成り立たないことを示す。
SQCMASPACE を[Chailloux, Sattath, 2012] のスパース分離ハミルトン問題に組み込む方法を示す (QMA(2)-complete for 1/poly promise gap)。
論文 参考訳(メタデータ) (2022-06-10T17:35:10Z) - BILP-Q: Quantum Coalition Structure Generation [0.0]
我々は、結合構造生成問題(CSGP)を解決するための最初の一般量子アプローチであるBILP-Qを提案する。
実量子アニール(D-Wave)を用いた中規模問題に対するBILP-Qの実行
論文 参考訳(メタデータ) (2022-04-28T22:19:50Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳(メタデータ) (2021-08-03T17:49:09Z) - PBS-Calculus: A Graphical Language for Coherent Control of Quantum
Computations [77.34726150561087]
本稿では,量子演算のコヒーレント制御を含む量子計算を表現・推論するためにPBS計算を導入する。
我々はこの言語に方程式理論を加え、それが健全で完備であることが証明された。
我々は、制御された置換の実装やループのアンロールのようなアプリケーションを考える。
論文 参考訳(メタデータ) (2020-02-21T16:15:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。