論文の概要: Distributed exact quantum algorithms for Deutsch-Jozsa problem
- arxiv url: http://arxiv.org/abs/2303.10663v1
- Date: Sun, 19 Mar 2023 14:01:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-21 18:04:44.086029
- Title: Distributed exact quantum algorithms for Deutsch-Jozsa problem
- Title（参考訳）: Deutsch-Jozsa問題に対する分散完全量子アルゴリズム
- Authors: Hao Li, Daowen Qiu, Le Luo
- Abstract要約: Deutsch-Jozsa問題(DJ)は、量子アルゴリズムのパワーを示す最も重要な問題の1つである。
DJアルゴリズムは1つのクエリでそれを正確に解くことができる。
- 参考スコア（独自算出の注目度）: 9.060388957107602
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Deutsch-Jozsa (DJ) problem is one of the most important problems
demonstrating the power of quantum algorithm. DJ problem can be described as a
Boolean function $f$: $\{0,1\}^n\rightarrow \{0,1\}$ with promising it is
either constant or balanced, and the purpose is to determine which type it is.
DJ algorithm can solve it exactly with one query. In this paper, we first
discover the inherent structure of DJ problem in distributed scenario by giving
a number of equivalence characterizations between $f$ being constant (balanced)
and some properties of $f$'s subfunctions, and then we propose three
distributed exact quantum algorithms for solving DJ problem. Our algorithms
have essential acceleration over distributed classical deterministic algorithm,
and can be extended to the case of multiple computing nodes. Compared with DJ
algorithm, our algorithms can reduce the number of qubits and the depth of
circuit implementing a single query operator. Therefore, we find that the
structure of problem should be clarified for designing distributed quantum
algorithm to solve it.
- Abstract（参考訳）: Deutsch-Jozsa問題(DJ)は、量子アルゴリズムのパワーを示す最も重要な問題の1つである。
DJ問題は Boolean 関数 $f$: $\{0,1\}^n\rightarrow \{0,1\}$ と記述できる。
djアルゴリズムは1つのクエリで正確に解くことができる。
本稿では、まず、分散シナリオにおけるDJ問題の固有構造を、$f$が定数であること(平衡)と、$f$のサブファンクションのいくつかの特性の間の同値な特徴を与え、次に、DJ問題を解決するために3つの分散完全量子アルゴリズムを提案する。
我々のアルゴリズムは分散古典的決定論的アルゴリズムよりも重要な加速度を持ち、複数の計算ノードに拡張することができる。
DJアルゴリズムと比較して、我々のアルゴリズムは単一のクエリ演算子を実装する回路の深さとキュービット数を削減できる。
したがって, 分散量子アルゴリズムを設計するためには, 問題の構造を明らかにする必要がある。
関連論文リスト
- Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Experimentally demonstrating indefinite causal order algorithms to solve
the generalized Deutsch's problem [4.555392897705548]
Deutschのアルゴリズムは、古典的アルゴリズムよりも優位性を示す最初の量子アルゴリズムである。
この問題を解決するために、不明確な因果順序を持つ新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-05-09T13:04:28Z) - Distributed exact quantum algorithms for Bernstein-Vazirani and search
problems [9.146620606615889]
我々は、$t$の計算ノードを持つ分散Bernstein-Vaziraniアルゴリズム(DBVA)と、未順序データベースの1つのターゲット項目で探索問題を解決する分散型Grover'sアルゴリズム(DEGA)を提供する。
我々は、MindQuantum(量子ソフトウェア)上でDBVAとDEGAの状況を提供し、我々の手法の正確性と実践性を検証する。
論文 参考訳（メタデータ） (2023-03-19T14:18:49Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Optimal exact quantum algorithm for the promised element distinctness
problem [0.2741266294612775]
要素差分問題は、文字列$x=(x_1,ldots,x_N)$の$N$要素が同じ値の2つの要素を含むかどうかを決定することである。
保証問題に対する厳密な量子アルゴリズムを提案するが、これにはO(N2/3)$クエリが必要である。
論文 参考訳（メタデータ） (2022-11-10T09:33:13Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Distributed quantum algorithm for Simon's problem [2.26741603346646]
我々は分散シナリオにおけるSimonの問題を研究し、この問題を解決するために分散量子アルゴリズムを設計する。
分散量子コンピューティングの新しい計算アーキテクチャは、量子回路のノイズと深さを減らすことが期待されている。
論文 参考訳（メタデータ） (2022-04-25T01:22:22Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。