論文の概要: Span programs and quantum time complexity
- arxiv url: http://arxiv.org/abs/2005.01323v1
- Date: Mon, 4 May 2020 08:43:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-21 05:24:11.396253
- Title: Span programs and quantum time complexity
- Title（参考訳）: スパンプログラムと量子時間複雑性
- Authors: Arjan Cornelissen and Stacey Jeffery and Maris Ozols and Alvaro
Piedrafita
- Abstract要約: 時間複雑性が$f$で量子アルゴリズムを$f$でスパンプログラムに変換し、時間複雑性が$widetildeO(T)$で$f$で量子アルゴリズムにコンパイルする方法を示す。
特に、時間複雑性$T$で量子アルゴリズムを$f$でスパンプログラムに変換し、時間複雑性$widetildeO(T)$で量子アルゴリズムにコンパイルする方法を示す。
- 参考スコア（独自算出の注目度）: 2.4182732872327186
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Span programs are an important model of quantum computation due to their
tight correspondence with quantum query complexity. For any decision problem
$f$, the minimum complexity of a span program for $f$ is equal, up to a
constant factor, to the quantum query complexity of $f$. Moreover, this
correspondence is constructive. A span program for $f$ with complexity $C$ can
be compiled into a bounded error quantum algorithm for $f$ with query
complexity $O(C)$, and vice versa.
In this work, we prove an analogous connection for quantum time complexity.
In particular, we show how to convert a quantum algorithm for $f$ with time
complexity $T$ into a span program for $f$ such that it compiles back into a
quantum algorithm for $f$ with time complexity $\widetilde{O}(T)$. While the
query complexity of quantum algorithms obtained from span programs is
well-understood, it is not generally clear how to implement certain
query-independent operations in a time-efficient manner. We show that for span
programs derived from algorithms with a time-efficient implementation, we can
preserve the time efficiency when implementing the span program. This means in
particular that span programs not only fully capture quantum query complexity,
but also quantum time complexity.
One practical advantage of being able to convert quantum algorithms to span
programs in a way that preserves time complexity is that span programs compose
very nicely. We demonstrate this by improving Ambainis's variable-time quantum
search result using our construction through a span program composition for the
OR function.
- Abstract（参考訳）: スパンプログラムは、量子クエリの複雑さとの密接な対応のため、量子計算の重要なモデルである。
任意の決定問題である $f$ に対して、$f$ のスパンプログラムの最小複雑性は、定数係数から$f$ の量子クエリ複雑性まで等しい。
さらに、この対応は構成的です。
複雑性を持つ$f$ のスパンプログラムは、クエリ複雑性 $o(c)$ で$f$ の有界エラー量子アルゴリズムにコンパイルでき、その逆も可能である。
本研究では、量子時間複雑性の類似関係を証明した。
特に、時間複雑性を持つ$f$の量子アルゴリズムを、時間複雑性を持つ$T$のスパンプログラムに変換して、時間複雑性を持つ$f$の量子アルゴリズムにコンパイルする方法を示す。
スパンプログラムから得られる量子アルゴリズムのクエリ複雑性はよく理解されているが、特定のクエリ非依存操作を時間効率良く実装する方法は一般には明確ではない。
時間効率のよい実装のアルゴリズムから派生したスパンプログラムでは,スパンプログラムを実装する際の時間効率を保てることを示す。
これは特に、プログラムが量子クエリの複雑さをフルに捉えるだけでなく、量子時間の複雑さも捉えることを意味する。
時間的複雑さを保ちながら量子アルゴリズムをプログラムに変換できるという現実的な利点は、プログラムにまたがる構成が非常に良いことである。
我々は, OR関数のスパンプログラム構成を用いて, アンバイニスの可変時間量子探索結果を改善することでこれを実証する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Accelerated Quantum Amplitude Estimation without QFT [0.0]
我々は、現在利用可能なアプローチと比較して優れた性能(より低い量子計算複雑性と高速な古典計算部分)を実現する量子振幅推定アルゴリズムを提唱した。
このアルゴリズムの正しさと量子計算複雑性に縛られる$O(frac1varepsilon)$は、正確な証明によって支持される。
論文 参考訳（メタデータ） (2024-07-23T18:49:11Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv
Factorization [2.684542790908823]
我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。
2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
論文 参考訳（メタデータ） (2023-11-03T09:09:23Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Intermediate-qudit assisted Improved quantum algorithm for string
matching with an Advanced Decomposition of Fredkin gate [1.9798034349981157]
本稿では,高次元中間クォーディットを用いた文字列マッチング問題に対する量子回路の実装について述べる。
また、中間クォーディットの助けを借りれば、深さの複雑さを低減できるだけでなく、クエリの複雑さを減らせることも示される。
論文 参考訳（メタデータ） (2023-04-06T13:11:07Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Variational learning algorithms for quantum query complexity [3.980076328494117]
量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。
量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。
本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
論文 参考訳（メタデータ） (2022-05-16T05:16:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。