論文の概要: Computing the quantum guesswork: a quadratic assignment problem
- arxiv url: http://arxiv.org/abs/2112.01666v2
- Date: Fri, 25 Aug 2023 11:59:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-28 18:34:53.435422
- Title: Computing the quantum guesswork: a quadratic assignment problem
- Title（参考訳）: 量子推測の計算 : 二次代入問題
- Authors: Michele Dall'Arno, Francesco Buscemi, Takeshi Koshiba
- Abstract要約: 従来の計算手法は、半定値の標準的なプログラミング技術に基づいていた。
確率分布が均一な量子ビットアンサンブルの量子推定処理を計算すれば、よりクワッドラティックなスピードアップがもたらされることを示す。
例として、正則および準正則なクォービット状態集合の推理を計算する。
- 参考スコア（独自算出の注目度）: 6.445605125467573
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum guesswork quantifies the minimum number of queries needed to
guess the state of a quantum ensemble if one is allowed to query only one state
at a time. Previous approaches to the computation of the guesswork were based
on standard semi-definite programming techniques and therefore lead to
approximated results. In contrast, we show that computing the quantum guesswork
of qubit ensembles with uniform probability distribution corresponds to solving
a quadratic assignment problem and we provide an algorithm that, upon the input
of any qubit ensemble over a discrete ring, after finitely many steps outputs
the exact closed-form expression of its guesswork. While in general the
complexity of our guesswork-computing algorithm is factorial in the number of
states, our main result consists of showing a more-than-quadratic speedup for
symmetric ensembles, a scenario corresponding to the three-dimensional analog
of the maximization version of the turbine-balancing problem. To find such
symmetries, we provide an algorithm that, upon the input of any point set over
a discrete ring, after finitely many steps outputs its exact symmetries. The
complexity of our symmetries-finding algorithm is polynomial in the number of
points. As examples, we compute the guesswork of regular and quasi-regular sets
of qubit states.
- Abstract（参考訳）: 量子推測は、一度に1つの状態しかクエリできない場合、量子アンサンブルの状態を予測するのに必要な最小のクエリ数を定量化する。
従来の計算手法は半定値の標準的なプログラミング手法に基づいており、結果として近似結果が得られた。
対照的に、一様確率分布を持つキュービットアンサンブルの量子推定処理は二次代入問題の解法と一致し、離散環上の任意のキュービットアンサンブルの入力に応じて、有限個のステップでその推定処理の正確な閉形式表現を出力するアルゴリズムを提供する。
一般に, 推測計算アルゴリズムの複雑さは, 状態数に因果関係があるが, 主結果は, 対称アンサンブルに対するよりクアドミックなスピードアップを示すことであり, タービンバランス問題の最大化バージョンの3次元類似に対応するシナリオである。
そのような対称性を見つけるために、離散環上の任意の点の入力に基づいて、有限個のステップがその正確な対称性を出力するアルゴリズムを提供する。
対称性探索アルゴリズムの複雑さは、点数における多項式である。
例として、正則および準正則なクォービット状態集合の推理を計算する。
関連論文リスト
- Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - 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) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - Quantum optimization algorithm based on multistep quantum computation [0.0]
本稿では,多段階量子計算に基づく関数の最小値を求める量子アルゴリズムを提案する。
このアルゴリズムでは、問題の探索空間の次元を指数関数的に段階的に減らすことができる。
連続的なテスト関数のアルゴリズムを検証した。
論文 参考訳（メタデータ） (2023-06-30T01:58:23Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - 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) - Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
振幅の間隔推定のための適応アルゴリズムを提案する。
提案アルゴリズムは、同じレベルの精度を達成するために、同じ数の量子クエリを使用する。
我々は,古典モンテカルロサンプリングに対する2次高速化として,オラクルクエリの数が$O(1/epsilon)$に達することを厳密に証明する。
論文 参考訳（メタデータ） (2022-06-16T21:11:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
我々は、ノイズの多い量子デバイス上で分解可能な数値の範囲を拡大するステップを推し進めるShorのアルゴリズムの縮小版を導入する。
特に、ほとんどのケースで注目すべき結果が得られており、しばしば提案されたアルゴリズムの1つで与えられた数を分解できる。
論文 参考訳（メタデータ） (2021-12-23T15:36:59Z) - Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation [0.0]
雑音二元線形問題(NBLP)の量子可解性について完全解析する。
NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
論文 参考訳（メタデータ） (2021-09-23T07:46:20Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。