論文の概要: Tight Success Probabilities for Quantum Period Finding and Phase Estimation
- arxiv url: http://arxiv.org/abs/2506.20527v2
- Date: Thu, 03 Jul 2025 19:14:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-08 17:51:40.004875
- Title: Tight Success Probabilities for Quantum Period Finding and Phase Estimation
- Title（参考訳）: 量子周期探索と位相推定のためのタイト成功確率
- Authors: Malik Magdon-Ismail, Khai Dong,
- Abstract要約: 我々は、測定された$hatell$ が正の整数倍の 2n / r$ の許容値$M$ 内にあるときに必ず成功する一般的な後処理アルゴリズムを考える。
1 に収束する成功確率について、新しい(八つの)下限と上限を与える。
我々の分析は、量子回路の複雑さと成功確率を最適化する際の古典的な処理に費やした労力との間のトレードオフを慎重に活用することを可能にする。
- 参考スコア（独自算出の注目度）: 2.2329417756084093
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Period finding and phase estimation are fundamental in quantum computing. Prior work has established lower bounds on their success probabilities. Such quantum algorithms measure a state $|\hat\ell\rangle$ in an $n$-qubit computational basis, $\hat\ell \in [0, 2^n - 1]$, and then post-process this measurement to produce the final output, in the case of period finding, a divisor of the period $r$. We consider a general post-processing algorithm which succeeds whenever the measured $\hat\ell$ is within some tolerance $M$ of a positive integer multiple of $2^n / r$. We give new (tight) lower and upper bounds on the success probability that converge to 1. The parameter $n$ captures the complexity of the quantum circuit. The parameter $M$ can be tuned by varying the post-processing algorithm (e.g., additional brute-force search, lattice methods). Our tight analysis allows for the careful exploitation of the tradeoffs between the complexity of the quantum circuit and the effort spent in classical processing when optimizing the probability of success. We note that the most recent prior work in most recent work does not give tight bounds for general $M$.
- Abstract（参考訳）: 周期探索と位相推定は量子コンピューティングにおいて基本的なものである。
以前の作業は、彼らの成功の確率を低く設定しました。
そのような量子アルゴリズムは、状態 $|\hat\ell\rangle$ を$n$-qubit計算ベースで測定し、$\hat\ell \in [0, 2^n - 1]$ とすると、この測定を後処理して最終的な出力を生成する。
我々は、測定された$\hat\ell$が、正の整数倍の2^n / r$の許容値$M$内にあるときに必ず成功する一般的な後処理アルゴリズムを考える。
1 に収束する成功確率について、新しい(八つの)下限と上限を与える。
パラメータ$n$は量子回路の複雑さを捉える。
パラメータ$M$は、後処理アルゴリズム(例えば、追加のブルートフォースサーチ、格子法)を変更することで調整できる。
我々の厳密な分析により、量子回路の複雑さと、成功の確率を最適化する際の古典的な処理に費やされた労力との間のトレードオフを慎重に活用することができる。
最近の研究における最新の先行研究は、一般の$M$に対する厳密な制限を与えていないことに留意する。
関連論文リスト
- Bounds on a Wavefunction Overlap with Hamiltonian Eigen-states: Performance Guarantees for the Quantum Phase Estimation Algorithm [0.0]
近似波動関数とハミルトニアン系の目標固有状態との重なりを推定することは、量子位相推定の効率性に不可欠である。
我々は、ハミルトンパワーの期待値と目標固有エネルギー上の有界値を用いて、この重なり合い上の上界と下界を導出する。
論文 参考訳（メタデータ） (2025-03-15T18:24:12Z) - Quantum Approximate $k$-Minimum Finding [2.810947654192424]
我々は、全ての$k geq 1$に対して近似値を扱う最適量子$k$-minimum探索アルゴリズムを提案する。
我々は、複数の観測可能量のうち、$k$最小の期待値を同定し、ハミルトンの最低基底状態エネルギーを$k$最小に決定するための効率的な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-12-21T11:21:15Z) - Partition function estimation with a quantum coin toss [0.0]
量子分割関数の推定は、様々な分野において重要な課題である。
本稿では,分割関数 $Z_beta$ を乗法誤差まで一般化したハミルトニアン$H$ の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-26T19:01:19Z) - A case study against QSVT: assessment of quantum phase estimation improved by signal processing techniques [0.0]
近年, 量子位相推定を無測定のサブルーチンとしてコヒーレントに利用する量子アルゴリズムが提案されている。
本稿では,カイザーウィンドウ関数の利用がQPEを実現するための最も実用的な選択であることを示す。
論文 参考訳（メタデータ） (2024-04-01T18:08:10Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Simulation of IBM's kicked Ising experiment with Projected Entangled
Pair Operator [71.10376783074766]
我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。
提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。
我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
論文 参考訳（メタデータ） (2023-08-06T10:24:23Z) - Search for Multiple Adjacent Marked Vertices on the Hypercube by a Quantum Walk with Partial Phase Inversion [3.8436076642278754]
マルチループラカダシカル量子ウォークのハイパーキューブへの応用について検討する。
部分位相反転を用いることで、確率振幅を 1 に近い値に増幅できることが示される。
論文 参考訳（メタデータ） (2023-05-31T07:30:04Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Quantum Thermal State Preparation [39.91303506884272]
量子マスター方程式をシミュレートするための簡単な連続時間量子ギブスサンプリングを導入する。
我々は、特定の純ギブス状態を作成するための証明可能かつ効率的なアルゴリズムを構築した。
アルゴリズムのコストは温度、精度、混合時間に依存している。
論文 参考訳（メタデータ） (2023-03-31T17:29:56Z) - 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) - Even shorter quantum circuit for phase estimation on early
fault-tolerant quantum computers with applications to ground-state energy
estimation [5.746732081406236]
異なる特徴を持つ位相推定法を開発した。
アルゴリズムの総コストは、ハイゼンベルク制限スケーリング$widetildemathcalO(epsilon-1)$を満たす。
我々のアルゴリズムは、初期のフォールトトレラント量子コンピュータで位相推定タスクを行う際の回路深さを著しく削減することができる。
論文 参考訳（メタデータ） (2022-11-22T03:15:40Z) - Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
量子計算を古典的な結果によって補う手法を提案する。
予測の利点を生かして、新しいタイプの量子測度がもたらされる。
予測量子測定では、古典計算と量子計算の結果の組み合わせは最後にのみ起こる。
論文 参考訳（メタデータ） (2022-09-12T15:47:44Z) - Improvement of quantum walk-based search algorithms in single marked
vertex graphs [0.0]
増幅増幅は通常、成功確率を増幅するために使用されるが、サッフル問題は続く。
本研究では,探索アルゴリズムの成功確率の向上とソッフル問題回避を両立できる一般化補間量子ウォークを定義する。
論文 参考訳（メタデータ） (2022-09-09T07:43:46Z) - 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) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Reducing the cost of energy estimation in the variational quantum
eigensolver algorithm with robust amplitude estimation [50.591267188664666]
量子化学と材料は、量子コンピューティングの最も有望な応用の1つである。
これらの領域における産業関連問題とそれを解決する量子アルゴリズムとの整合性については、まだ多くの研究が続けられている。
論文 参考訳（メタデータ） (2022-03-14T16:51:36Z) - On the success probability of quantum order finding [0.0]
我々はShorのオーダーフィニングアルゴリズムが単一ランで$r$のオーダーを回復する確率の低い境界を証明した。
漸近的に、$r$が無限大の傾向にあるように、単一のランで$r$を回復する確率は1つになる。
論文 参考訳（メタデータ） (2022-01-19T18:58:18Z) - Success-or-Draw: A Strategy Allowing Repeat-Until-Success in Quantum
Computation [4.014524824655106]
本稿では,確率的高次変換手法であるMuccess-or-drawを提案する。
次に、最適な成功または引き込みプロトコルを得るための半確定的なプログラミング手法を提案し、一般的なユニタリ演算を反転させる問題について詳細に分析する。
論文 参考訳（メタデータ） (2020-11-02T15:38:16Z) - Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
本稿では、QAS(Quantum Architecture Search)と呼ばれるリソースと実行時の効率的なスキームを提案する。
QASは、よりノイズの多い量子ゲートを追加することで得られる利点と副作用のバランスをとるために、自動的にほぼ最適アンサッツを求める。
数値シミュレータと実量子ハードウェアの両方に、IBMクラウドを介してQASを実装し、データ分類と量子化学タスクを実現する。
論文 参考訳（メタデータ） (2020-10-20T12:06:27Z) - Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。
観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
論文 参考訳（メタデータ） (2020-05-05T20:11:53Z) - Communication Cost of Quantum Processes [49.281159740373326]
分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。
重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。
クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
論文 参考訳（メタデータ） (2020-02-17T08:51:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。