論文の概要: Polynomial representation of general partial Boolean functions with a single quantum query

• arxiv url: http://arxiv.org/abs/2112.12416v2
• Date: Tue, 10 Oct 2023 03:09:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-13 17:12:15.867136
• Title: Polynomial representation of general partial Boolean functions with a single quantum query
• Title（参考訳）: 単一量子クエリを用いた一般部分ブール関数の多項式表現
• Authors: Xu Guoliang, Qiu Daowen
• Abstract要約: 1992年初頭、Deutsch-Jozsaアルゴリズムは1つの量子クエリを持つ対称部分ブール関数を計算した。 本稿では,3つの新たな結果の証明と発見を行う。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query, and thus achieved the best separation between classical deterministic and exact quantum query complexity. Until recent years, it was clarified that all symmetric partial Boolean functions with a single quantum query can be computed exactly by Deutsch-Jozsa algorithm. For the general partial Boolean functions with a single quantum query, the latest characterizations is complex and not very satisfactory. Based on this, this paper proves and discovers three new results: (1) Establishing a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one; (2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query; (3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm. Essentially, the first discovery represent a step forward for a fundamental conclusion that the polynomial degree of partial Boolean functions with a single quantum query is one or two, and the last two results contribute a way for searching more nontrival partial Boolean functions that have quantum advantages.
• Abstract（参考訳）: 1992年初頭、deutsch-jozsaアルゴリズムは1つの量子クエリを持つ対称部分ブール関数を計算し、古典的決定論と厳密な量子クエリの複雑性の間の最良の分離を達成した。 近年まで、単一の量子クエリを持つすべての対称部分ブール関数は、deutsch-jozsaアルゴリズムによって正確に計算できることが明らかになった。 単一の量子クエリを持つ一般部分ブール関数の場合、最新の特徴付けは複雑であり、あまり満足できない。 Based on this, this paper proves and discovers three new results: (1) Establishing a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one; (2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query; (3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm. 本質的には、最初の発見は、単一の量子クエリを持つ部分ブール関数の多項式次数が1つか2であるという基本的な結論への一歩であり、最後の2つの結果は、量子的な利点を持つより三価でない部分ブール関数の探索に寄与する。

関連論文リスト

• Quantum advantage and lower bounds in parallel query complexity [0.0]
  本稿では,全関数に対する量子・ランダム化・決定論的(逐次的)問合せ複雑性について検討する。 これらの測度の平行一般化の間には、はるかに大きな分離が可能であることが分かる。 逐次上界から並列量子下界を導出する新しい手法を開発した。
  論文  参考訳（メタデータ） (2024-10-03T16:50:00Z)
• Quantum and Classical Communication Complexity of Permutation-Invariant Functions [4.410515368583671]
  置換不変ブール関数の量子的およびランダムな通信複雑性は(対数係数まで)2次同値であることを示す。 本研究は,通信複雑性に対するクエリ複雑性に関する最近の研究を拡張したものである。
  論文  参考訳（メタデータ） (2023-12-31T11:07:49Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• On the Fine-Grained Query Complexity of Symmetric Functions [4.956977275061968]
  本稿では、Watrous予想のきめ細かいバージョンについて考察する。 確率が任意に1/2ドルに近いランダム化および量子化アルゴリズムを含む。
  論文  参考訳（メタデータ） (2023-09-20T13:04:45Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• The power of qutrits for non-adaptive measurement-based quantum computing [0.0]
  量子相関は、一般化された四重項グリーンベルガー・ホーネ・ザイリンガー状態(GHZ)を資源とし、最低でも3n-1$の四重項関数の計算を可能にすることを証明している。 これにより、LHVが計算できない任意の三次函数に対して対応する一般化されたGHZ型パラドックスが得られる。
  論文  参考訳（メタデータ） (2022-03-23T13:41:22Z)
• Characterization of exact one-query quantum algorithms (ii): for partial functions [0.2741266294612775]
  クエリモデル(またはブラックボックスモデル)は、古典コンピューティングと量子コンピューティングの両方のコミュニティから多くの注目を集めている。 通常、量子の利点は、古典的なアルゴリズムよりもクエリの複雑さが高い量子アルゴリズムを提示することで明らかにされる。 例えば、Deutsch-Jozsaアルゴリズム、Simonアルゴリズム、Groverアルゴリズムといったよく知られた量子アルゴリズムは、クエリ複雑性の観点から量子コンピューティングのかなりの利点を示している。
  論文  参考訳（メタデータ） (2020-08-27T09:06:34Z)

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

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