論文の概要: Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform
- arxiv url: http://arxiv.org/abs/2604.10428v1
- Date: Sun, 12 Apr 2026 02:53:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-14 20:13:16.011584
- Title: Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform
- Title（参考訳）: 平均ケース正量子フーリエ変換を用いた最悪のHarrow-Hassidim-Lloydアルゴリズム
- Authors: Changpeng Shao,
- Abstract要約: 本稿では,Harrow-Hassidim-Lloydアルゴリズムを最悪の性能で実行可能であることを示す。
Harrow-Hassidim-Lloydアルゴリズムは3つの異なるシナリオで実行可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In [\href{https://quantum-journal.org/papers/q-2022-12-07-872/}{Quantum 6, 872, 2022}], Linden and de Wolf proposed a lightweight protocol for verifying the average-case correct behavior of the quantum Fourier transform (QFT). They proved that good average-case QFT performance suffices for good worst-case performance in several quantum tasks. Here we provide another application of this worst-case-to-average-case reduction, using a strengthened Linden-de Wolf protocol. We show that, across three distinct scenarios, the Harrow-Hassidim-Lloyd algorithm can be executed with provably good worst-case performance, assuming only that the QFT is correct on average.
- Abstract（参考訳）: In [\href{https://quantum-journal.org/papers/q-2022-12-07-872/}{Quantum 6, 872, 2022}] において、リンデンとデ・ウルフは量子フーリエ変換(QFT)の平均的な正当性を検証するための軽量なプロトコルを提案した。
彼らは、いくつかの量子タスクにおいて、良い平均ケースQFT性能は、良い最悪のケースパフォーマンスに十分であることを示した。
ここでは、Linden-de Wolfプロトコルを用いて、この最悪のケース対平均ケース削減の別の応用について述べる。
3つの異なるシナリオにおいて,QFTが平均値で正しいと仮定した場合のみ,Harrow-Hassidim-Lloydアルゴリズムが実行可能であることを示す。
関連論文リスト
- Fault-tolerant execution of error-corrected quantum algorithms [1.2841574646218608]
高インパクト問題に対処するために量子アルゴリズムをスケールアップするには、量子エラー補正とフォールトトレランスが必要である。
我々は、フォールトトレラント(FT)コンポーネントのみを用いた論理量子アルゴリズムのエンドツーエンド実行を実演する。
本研究は,FT成分のみを用いた複雑な誤り訂正量子回路の性能を概ね実証する。
論文 参考訳（メタデータ） (2026-03-04T20:26:54Z) - Verifiable Quantum Advantage via Optimized DQI Circuits [2.149968465453488]
Decoded Quantum Interferometry (DQI) はスーパーポリノミカル量子スピードアップのためのフレームワークを提供する。
DQIをリードソロモン(Reed-Solomon, RS)コードである最適多項式区間(OPI)問題に適用する。
我々は、OPIのDQIが、最適スピードアップによる検証可能な量子優位性の最初の候補であることを示す。
論文 参考訳（メタデータ） (2025-10-13T03:19:28Z) - Optimization by Decoded Quantum Interferometry [38.063836468778895]
Decoded Quantum Interferometry (DQI) は、量子フーリエ変換を用いて、復号化問題に対する最適化問題を削減する量子アルゴリズムである。
有限体上の最適適合を近似するために、DQIは既知の古典的アルゴリズムよりも超多項式的なスピードアップを達成する。
論文 参考訳（メタデータ） (2024-08-15T17:47:42Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM
Framework [14.531920189937495]
本稿では,半定値プログラミング(SDP)を高精度に解くために,凸最適化の基本的な問題について検討する。
我々は、その出力の最適性と実現可能性の両方において高精度な量子二階法を提案する。
論文 参考訳（メタデータ） (2022-07-22T15:51:02Z) - Average-Case Verification of the Quantum Fourier Transform Enables
Worst-Case Phase Estimation [0.0]
この結果から,QFTの平均ケース性能は,最悪ケース性能を達成するためにのみ必要であることが判明した。
我々は,このQFTの要求された平均ケース動作を検証するための極めて効率的な手順を提示する。
論文 参考訳（メタデータ） (2021-09-21T14:40:48Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs.
Coded Systems [69.33243249411113]
パウリの誤差は、多数の現実的な量子チャネルの中で最も低いサンプリングオーバーヘッドをもたらすことを示す。
我々はQEMと量子チャネル符号化を併用する手法を考案し、純粋なQEMと比較してサンプリングオーバーヘッドの低減を解析する。
論文 参考訳（メタデータ） (2020-12-15T15:51:27Z) - Improving the Performance of Deep Quantum Optimization Algorithms with
Continuous Gate Sets [47.00474212574662]
変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。
本稿では,QAOAの回路深度依存性能について実験的に検討する。
この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
論文 参考訳（メタデータ） (2020-05-11T17:20:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。