論文の概要: Characterization of exact one-query quantum algorithms (ii): for partial functions

• arxiv url: http://arxiv.org/abs/2008.11998v3
• Date: Fri, 11 Dec 2020 12:59:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-04 19:37:12.882141
• Title: Characterization of exact one-query quantum algorithms (ii): for partial functions
• Title（参考訳）: 完全1問量子アルゴリズムのキャラクタリゼーション(ii) : 部分関数について
• Authors: Zekun Ye, Lvzhou Li
• Abstract要約: クエリモデル(またはブラックボックスモデル)は、古典コンピューティングと量子コンピューティングの両方のコミュニティから多くの注目を集めている。 通常、量子の利点は、古典的なアルゴリズムよりもクエリの複雑さが高い量子アルゴリズムを提示することで明らかにされる。 例えば、Deutsch-Jozsaアルゴリズム、Simonアルゴリズム、Groverアルゴリズムといったよく知られた量子アルゴリズムは、クエリ複雑性の観点から量子コンピューティングのかなりの利点を示している。
• 参考スコア（独自算出の注目度）: 0.2741266294612775
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.
• Abstract（参考訳）: クエリモデル(あるいはブラックボックスモデル)は、古典コンピューティングと量子コンピューティングの両方のコミュニティから注目を集めている。 通常、量子の利点は、古典的なアルゴリズムよりもクエリの複雑さが高い量子アルゴリズムを提示することで明らかにされる。 例えば、Deutsch-Jozsaアルゴリズム、Simonアルゴリズム、Groverアルゴリズムといったよく知られた量子アルゴリズムは、クエリ複雑性の観点から量子コンピューティングのかなりの利点を示している。 最近、我々は考察した(Phys)。 rev. a. {\bf 101}, 02232 (2020) 問題: 正確な1クエリ量子アルゴリズムで計算できる関数は何か? この問題は全体ブール関数に対しては解決されているが、部分ブール関数に対しては依然として開である。 そこで本論文では,いくつかの必要十分条件を与えることで,部分ブール関数に対する完全1問量子アルゴリズムの計算能力を特徴付ける。 これらの条件により、我々は1つの量子アルゴリズムによって正確に計算できるが、既に知られている関数と本質的な違いを持つ関数をいくつか構築する。 我々の研究の前には、正確に1クエリの量子アルゴリズムで計算できる既知の関数はすべて対称関数であり、この論文で構築された関数は一般に非対称である。

関連論文リスト

• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Integer Factorization by Quantum Measurements [0.0]
  量子アルゴリズムは、古典的コンピュータでは解けない計算問題を解くために量子力学を使うことが進行中の努力の中心である。 既知の量子アルゴリズムの中で、特別な役割はShorアルゴリズム、すなわち整数分解のための量子時間アルゴリズムによって演じられる。 ここでは、別の真の量子特性(量子計測)に基づく整数分解の異なるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-19T17:00:01Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• 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)
• Polynomial representation of general partial Boolean functions with a single quantum query [0.0]
  1992年初頭、Deutsch-Jozsaアルゴリズムは1つの量子クエリを持つ対称部分ブール関数を計算した。 本稿では,3つの新たな結果の証明と発見を行う。
  論文  参考訳（メタデータ） (2021-12-23T08:45:06Z)
• Revisiting dequantization and quantum advantage in learning tasks [3.265773263570237]
  サンプルとクエリ(SQ)アクセスを持つ古典的アルゴリズムは量子状態入力を持つ量子アルゴリズムよりも指数関数的に高速に学習タスクを実現できることを示す。 これらの結果から,SQアクセスが量子状態入力に対して強すぎるため,指数的量子優位性が欠如していることが示唆された。
  論文  参考訳（メタデータ） (2021-12-01T20:05:56Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。 本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
  論文  参考訳（メタデータ） (2021-11-19T12:35:26Z)
• Quantum algorithmic differentiation [0.0]
  本稿では,量子コンピューティングの文脈でアルゴリズムの微分を行うアルゴリズムを提案する。 アルゴリズムの2つのバージョンを提示する。1つは完全量子であり、もう1つは古典的なステップを雇用する。
  論文  参考訳（メタデータ） (2020-06-23T22:52:22Z)

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

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