論文の概要: Quantum Approximate $k$-Minimum Finding
- arxiv url: http://arxiv.org/abs/2412.16586v1
- Date: Sat, 21 Dec 2024 11:21:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-24 15:57:36.860510
- Title: Quantum Approximate $k$-Minimum Finding
- Title(参考訳): 量子近似$k$-minimum Finding
- Authors: Minbo Gao, Zhengfeng Ji, Qisheng Wang,
- Abstract要約: 我々は、全ての$k geq 1$に対して近似値を扱う最適量子$k$-minimum探索アルゴリズムを提案する。
我々は、複数の観測可能量のうち、$k$最小の期待値を同定し、ハミルトンの最低基底状態エネルギーを$k$最小に決定するための効率的な量子アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 2.810947654192424
- License:
- Abstract: Quantum $k$-minimum finding is a fundamental subroutine with numerous applications in combinatorial problems and machine learning. Previous approaches typically assume oracle access to exact function values, making it challenging to integrate this subroutine with other quantum algorithms. In this paper, we propose an (almost) optimal quantum $k$-minimum finding algorithm that works with approximate values for all $k \geq 1$, extending a result of van Apeldoorn, Gily\'{e}n, Gribling, and de Wolf (FOCS 2017) for $k=1$. As practical applications of this algorithm, we present efficient quantum algorithms for identifying the $k$ smallest expectation values among multiple observables and for determining the $k$ lowest ground state energies of a Hamiltonian with a known eigenbasis.
- Abstract(参考訳): 量子$k$-minimum発見は、組合せ問題や機械学習に多くの応用がある基本的なサブルーチンである。
以前のアプローチでは、通常は正確な関数値へのオラクルアクセスを前提としており、このサブルーチンを他の量子アルゴリズムと統合することは困難である。
本稿では、(ほぼ)最適量子$k$-minimum探索アルゴリズムを提案する。このアルゴリズムは、すべての$k \geq 1$に対して近似値で動作し、van Apeldoorn, Gily\'{e}n, Gribling, de Wolf (FOCS 2017) を$k=1$で拡張する。
このアルゴリズムの実用的な応用として、複数の観測可能量のうち、$k$最小の期待値を同定し、既知の固有基底を持つハミルトニアンの最低基底状態エネルギーを$k$最小に決定するための効率的な量子アルゴリズムを提案する。
関連論文リスト
- 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) - Rank Is All You Need: Estimating the Trace of Powers of Density Matrices [1.5133368155322298]
同一の$k$密度行列のパワーのトレースを推定することは、多くのアプリケーションにとって重要なサブルーチンである。
The Newton-Girard method, we developed a algorithm that only $mathcalO(r)$ qubits and $mathcalO(r)$ multi-qubit gates。
論文 参考訳(メタデータ) (2024-08-01T06:23:52Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
本稿では, 加算誤差$varepsilon$内のトレース距離を, ランク$r$の混合量子状態間で推定する効率的な量子アルゴリズムを提案する。
低ランクトレース距離推定の判定版が$mathsfBQP$-completeであることを示す。
論文 参考訳(メタデータ) (2023-01-17T10:16:14Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳(メタデータ) (2022-07-07T08:04:15Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - 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) - 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) - Quantum $k$-nearest neighbors algorithm [0.0]
古典的な$k$NN $-$quantum $k$NN (Q$k$NN) $-$の量子類似を類似度尺度として示す。
従来の$k$NNや既存の$k$NNアルゴリズムとは異なり、提案アルゴリズムは量子データに直接使用することができる。
論文 参考訳(メタデータ) (2020-03-20T10:48:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。