Fugu-MT 論文翻訳(概要): Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction

論文の概要: Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction

arxiv url: http://arxiv.org/abs/2504.06376v1
Date: Tue, 08 Apr 2025 18:53:16 GMT
ステータス: 翻訳完了
システム内更新日: 2025-04-10 16:15:26.921672
Title: Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction
Title（参考訳）: 量子コンバータとコンバータとサブ線形量子コンベックスハルと最大集合構築への応用
Authors: Shion Fukuzawa, Michael T. Goodrich, Sandy Irani,
Abstract要約: コンバインとコンバインという量子アルゴリズム設計パラダイムを導入する。これはカークパトリックとセイデルの「婚前征服」技法の量子版である。
参考スコア（独自算出の注目度）: 0.984963525011891
License:
Abstract: We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in $\tilde{O}(\sqrt{nh})$ time, w.h.p., where $h$ is the size of the output.
Abstract（参考訳）: カークパトリックとセイデルの「婚前征服」技術の量子バージョンであるコンバインとコンバインと呼ばれる量子アルゴリズム設計パラダイムを導入する。量子コンバイン・アンド・コンカアルゴリズムでは、再帰を回避しつつ、コンバイン・アンド・コンカアルゴリズムのコンバインステップの基本的な計算を行う。このモデルは、非再帰的な性質のため、量子設定に適している。 2次元最大集合に対する量子アルゴリズムと、$\tilde{O}(\sqrt{nh})$ time, w.h.p.で実行されるソートされた点集合に対する凸殻問題を提供することにより、このアプローチの有用性を示す。

関連論文リスト

Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文参考訳（メタデータ） (2024-09-06T03:32:02Z)
Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文参考訳（メタデータ） (2024-01-17T18:59:38Z)
A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
論文参考訳（メタデータ） (2023-11-17T20:38:38Z)
Making the cut: two methods for breaking down a quantum algorithm [0.0]
現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
論文参考訳（メタデータ） (2023-05-17T18:00:06Z)
Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [10.79781442303645]
ゼロサムゲームを解くための最初のオンライン量子アルゴリズムを提案する。我々のアルゴリズムは簡潔な記述を伴う古典的な出力を生成する。我々のアルゴリズムの核心は、ギブスサンプリング問題に対する高速な量子マルチサンプリング手法である。
論文参考訳（メタデータ） (2023-04-27T14:02:54Z)
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)
Quantum Approximate Counting for Markov Chains and Application to Collision Counting [0.0]
我々は,ブラザード,ホイヤー,タップ(ICALP 1998)によって開発された量子近似計数法を一般化し,マルコフ連鎖のマーク状態の数を推定する方法を示す。これにより、Magniez、Nayak、Roland、Santhaによって確立された強力な"量子ウォークベースサーチ"フレームワークに基づいて、量子検索アルゴリズムから量子近似カウントアルゴリズムを構築することができる。
論文参考訳（メタデータ） (2022-04-06T03:04:42Z)
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)
Quantum Algorithm for Fidelity Estimation [8.270684567157987]
2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2021-03-16T13:57:01Z)
Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文参考訳（メタデータ） (2020-04-14T11:05:26Z)

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