論文の概要: 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が組合せ問題に対する量子解の空間と時空下限を証明するのに使えることを望んでいる。

関連論文リスト

• Extending Quantum Perceptrons: Rydberg Devices, Multi-Class Classification, and Error Tolerance [67.77677387243135]
  量子ニューロモーフィックコンピューティング(QNC)は、量子計算とニューラルネットワークを融合して、量子機械学習(QML)のためのスケーラブルで耐雑音性のあるアルゴリズムを作成する QNCの中核は量子パーセプトロン(QP)であり、相互作用する量子ビットのアナログダイナミクスを利用して普遍的な量子計算を可能にする。
  論文  参考訳（メタデータ） (2024-11-13T23:56:20Z)
• Bosonic Quantum Computational Complexity [0.0]
  私たちはそのような研究計画の基礎をつくった。 本稿では,BQPのボゾン一般化に基づく自然複雑性クラスと問題を紹介する。 ボソニックハミルトニアンのスペクトルの有界性を決定する問題はコ-NPハードであることを示す。
  論文  参考訳（メタデータ） (2024-10-05T19:43:41Z)
• Quantum Query-Space Lower Bounds Using Branching Programs [0.18416014644193066]
  GQBPの制限されたバージョンに対する、最初の明示的なクエリ空間の低いバウンダリを示す。 次に、問題を一般化して、ハミング距離が一定である2つの弦の間を決定するために、同じ境界が成り立つことを示す。 我々の結果は、任意の非コンスタント対称ブール関数の問合せ複雑性に基づく$Omega(sqrtn)$-lower境界の代替証明を生成する。
  論文  参考訳（メタデータ） (2024-07-09T13:58:53Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• 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)

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

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