論文の概要: Quantum Algorithms for One-Sided Crossing Minimization
- arxiv url: http://arxiv.org/abs/2409.01942v1
- Date: Tue, 3 Sep 2024 14:39:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-06 01:08:09.485385
- Title: Quantum Algorithms for One-Sided Crossing Minimization
- Title（参考訳）: 一辺交叉最小化のための量子アルゴリズム
- Authors: Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista,
- Abstract要約: 本稿では, 1-Sided Crossing Minimization (CM) 問題に対する量子アルゴリズムを提案する。
量子スピードアップを用いた正確なアルゴリズムでは,OSCMを$V$以上の集合問題と見なすことができる。
- 参考スコア（独自算出の注目度）: 0.2294014185517204
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. Given an $n$-vertex bipartite graph $G=(U,V,E\subseteq U \times V)$, a $2$-level drawing $(\pi_U,\pi_V)$ of $G$ is described by a linear ordering $\pi_U: U \leftrightarrow \{1,\dots,|U|\}$ of $U$ and linear ordering $\pi_V: V \leftrightarrow \{1,\dots,|V|\}$ of $V$. For a fixed linear ordering $\pi_U$ of $U$, the OSCM problem seeks to find a linear ordering $\pi_V$ of $V$ that yields a $2$-level drawing $(\pi_U,\pi_V)$ of $G$ with the minimum number of edge crossings. We show that OSCM can be viewed as a set problem over $V$ amenable for exact algorithms with a quantum speedup with respect to their classical counterparts. First, we exploit the quantum dynamic programming framework of Ambainis et al. [Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. SODA 2019] to devise a QRAM-based algorithm that solves OSCM in $O^*(1.728^n)$ time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in $O^*(2^n)$ time and polynomial space.
- Abstract（参考訳）: 本稿では,1-Sided Crossing Minimization (OSCM) 問題に対する単項量子アルゴリズムを提案する。
$n$-vertex bipartite graph $G=(U,V,E\subseteq U \times V)$, a $2$-level drawing $(\pi_U,\pi_V)$ of $G$は、$\pi_U: U \leftrightarrow \{1,\dots,|U|\}$ of $U$と、$\pi_V: V \leftrightarrow \{1,\dots,|V|\}$ of $V$で表される。
固定線形順序付け $\pi_U$ of $U$ に対して、OSCM 問題は、最小のエッジ交差数を持つ 2$ レベルの描画 $(\pi_U,\pi_V)$ of $G$ を得る線形順序付け $\pi_V$ of $V$ を求める。
我々は、OSCMを古典的なアルゴリズムに対して、量子スピードアップを持つ正確なアルゴリズムに対して、$V$以上の集合問題と見なせることを示す。
まず、Ambainis et al[指数時間動的プログラミングアルゴリズムのための量子スピードアップ]の量子動的プログラミングフレームワークを利用して、OSCMを時間と空間で$O^*(1.728^n)で解くQRAMベースのアルゴリズムを考案する。
第二に、量子分割法を用いて、時間と多項式空間においてQRAMを使わずにOSCMを解くアルゴリズムを得る。
関連論文リスト
- Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。
本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。
微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
論文 参考訳（メタデータ） (2024-10-23T18:00:01Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文 参考訳（メタデータ） (2023-11-06T16:00:07Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳（メタデータ） (2023-08-16T06:46:37Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Efficient quantum algorithms for solving quantum linear system problems [0.0]
拡張行列 $C$ の特異値 0 の右特異ベクトルを求める問題を解くための2つの量子アルゴリズムを提案する。
どちらのアルゴリズムも$kappa $の最適なクエリ複雑性を満たす。
論文 参考訳（メタデータ） (2022-08-14T02:49:26Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。