論文の概要: Partial Boolean functions computed by exact quantum 1-query algorithms

• arxiv url: http://arxiv.org/abs/2112.12416v1
• Date: Thu, 23 Dec 2021 08:45:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-03 18:08:30.217085
• Title: Partial Boolean functions computed by exact quantum 1-query algorithms
• Title（参考訳）: 完全量子1-クエリアルゴリズムによる部分ブール関数の計算
• Authors: Guoliang Xu, Daowen Qiu
• Abstract要約: 正確な量子1-クエリアルゴリズムによって計算された全ての部分ブール関数は、単純な形式に還元できることを示す。 最大4ビットまでの小さな部分ブール函数に対しては、新たに10個の非自明な簡約部分ブール函数が存在することが示される。 これらの結果は、量子的に有利な問題を見つけるための道を開いた。
• 参考スコア（独自算出の注目度）: 2.3097706741644686
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deutsch's algorithm and Deutsch-Jozsa algorithm are exact quantum 1-query algorithms, and in recent years, it has proved that all symmetric partial Boolean functions and total Boolean functions by exact quantum 1-query algorithms can be computed exactly by Deutsch-Jozsa algorithm. Considering the most general case (i.e., all partial Boolean functions), in this paper we obtain four new results: (1) We prove that all partial Boolean functions computed by exact quantum 1-query algorithms can be reduced to a simple form; (2) We discover that all reduced partial Boolean functions computed by exact quantum 1-query algorithms can be represented by degree-1 multilinear polynomials; (3) For small partial Boolean functions up to four bits, we show that there are only 10 new non-trivial reduced partial Boolean functions computed by exact quantum 1-query algorithms; (4) We propose a construction method for finding out all partial Boolean functions computed by a given exact quantum 1-query algorithm. These results break through a basic conclusion that the polynomial degree of all partial Boolean functions computed by exact quantum 1-query algorithms is one or two and pave a way for finding out more problems that have quantum advantages.
• Abstract（参考訳）: DeutschのアルゴリズムとDeutsch-Jozsaアルゴリズムは正確な量子1-クエリアルゴリズムであり、近年では全ての対称部分ブール関数と完全量子1-クエリアルゴリズムによる総ブール関数がDeutsch-Jozsaアルゴリズムによって正確に計算できることが証明されている。 Considering the most general case (i.e., all partial Boolean functions), in this paper we obtain four new results: (1) We prove that all partial Boolean functions computed by exact quantum 1-query algorithms can be reduced to a simple form; (2) We discover that all reduced partial Boolean functions computed by exact quantum 1-query algorithms can be represented by degree-1 multilinear polynomials; (3) For small partial Boolean functions up to four bits, we show that there are only 10 new non-trivial reduced partial Boolean functions computed by exact quantum 1-query algorithms; (4) We propose a construction method for finding out all partial Boolean functions computed by a given exact quantum 1-query algorithm. これらの結果は、厳密な量子1-クエリアルゴリズムによって計算されるすべての部分ブール関数の多項式次数は 1 か 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)

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

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