論文の概要: Classical computation of quantum guesswork
- arxiv url: http://arxiv.org/abs/2112.01666v1
- Date: Fri, 3 Dec 2021 01:24:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-06 00:14:16.889670
- Title: Classical computation of quantum guesswork
- Title(参考訳): 量子推測の古典計算
- Authors: Michele Dall'Arno, Francesco Buscemi, Takeshi Koshiba
- Abstract要約: 推測処理は、一度に1つの状態しかクエリできない場合、量子アンサンブルの状態を予測するのに必要なクエリの最小数を定量化する。
従来の計算手法は、半定値の標準的なプログラミング技術に基づいていた。
離散環上の任意の点が入力されると、有限個のステップがその正確な対称性を出力するアルゴリズムを提供する。
- 参考スコア(独自算出の注目度): 3.867363075280544
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The 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, our main result is an algorithm that, upon
the input of any qubit ensemble over a discrete ring and with uniform
probability distribution, after finitely many steps outputs the exact
closed-form analytic expression of its guesswork. The complexity of our
guesswork-computing algorithm is factorial in the number of states, with a
more-than-quadratic speedup for symmetric ensembles. 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つの状態しかクエリできない場合、量子アンサンブルの状態を予測するのに必要なクエリの最小数を定量化する。
従来の計算手法は半定値の標準的なプログラミング手法に基づいており、結果として近似結果が得られた。
対照的に、我々の主な結果は、離散環上の任意のクビットアンサンブルの入力と、有限個のステップの後に一様確率分布によって、その推測の正確な閉形式解析式を出力するアルゴリズムである。
我々の推測計算アルゴリズムの複雑さは、対称アンサンブルのクアドドラティックなスピードアップにより、状態数に因果的である。
そのような対称性を見つけるために、離散環上の任意の点の入力に基づいて、有限個のステップがその正確な対称性を出力するアルゴリズムを提供する。
対称性探索アルゴリズムの複雑さは、点数における多項式である。
例として、正則および準正則なクォービット状態集合の推理を計算する。
関連論文リスト
- 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) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - 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) - Guesswork of a quantum ensemble [3.867363075280544]
有限条件条件下での推測問題の解析解を導出する。
明示的な例として、任意の立方体正則多角形および多面体アンサンブルの推測処理を計算する。
論文 参考訳(メタデータ) (2020-12-17T01:47:18Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳(メタデータ) (2020-11-24T18:44:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。