論文の概要: Improved quantum volume estimation with transducers and amortized quantum walks

• arxiv url: http://arxiv.org/abs/2609.40217v2
• Date: Mon, 05 Oct 2026 16:08:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-07 04:43:28.481046
• Title: Improved quantum volume estimation with transducers and amortized quantum walks
• Title（参考訳）: トランスデューサとアモルティゼーション量子ウォークによる量子体積推定の改善
• Abstract要約: 我々は、Cousins と Vempala が開発した、最先端の$widetildeO(d3.5+d3/varepsilon2)$-queryランダム化アルゴリズムを量子化する。 主要な技術的貢献は、量子ウォークのコストを償却するためのフレームワークである。
• 参考スコア（独自算出の注目度）: 1.1549572298362782
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The volume estimation problem is a classic task in computational geometry. The development of randomized algorithms for this problem spurred the development of many influential algorithmic techniques related to Markov Chain Monte Carlo and simulated annealing, and the problem connects to several important geometrical results, like the KLS conjecture. In this work, we quantize the state-of-the-art $\widetilde{O}(d^{3.5}+d^3/\varepsilon^2)$-query randomized algorithm developed by Cousins and Vempala, and obtain a $\widetilde{O}(d^{3.5} + d^{1.75}/\varepsilon)$-query quantum algorithm, improving over the $\widetilde{O}(d^{3.5} + d^{2.25}/\varepsilon)$ state-of-the-art bound. Our key technical contribution is a framework for amortizing the cost of a quantum walk. The framework is based on the recent transducer toolkit introduced by Belovs, Jeffery and Yolcu. It is this amortized quantum walk framework that allows us to exploit the amortized analysis of the ball walk by Cousins and Vempala, thus overcoming the key barrier that previously barred its quantum implementation.
• Abstract（参考訳）: 体積推定問題は計算幾何学における古典的な課題である。 この問題に対するランダム化アルゴリズムの開発はマルコフ・チェイン・モンテカルロ(英語版)に関連する多くの影響力のあるアルゴリズム技術の開発を刺激し、アニーリングをシミュレートし、この問題はKLS予想のようないくつかの重要な幾何学的結果に結びつく。 本研究では、Cousins と Vempala によって開発された、最先端の $\widetilde{O}(d^{3.5}+d^3/\varepsilon^2)$-query randomized algorithm を定量化し、$\widetilde{O}(d^{3.5} + d^{1.75}/\varepsilon)$-query quantum algorithm を取得し、$\widetilde{O}(d^{3.5} + d^{2.25}/\varepsilon)$ state-of-the-art bound を得る。 私たちの重要な技術的貢献は、量子ウォークのコストを抑えるためのフレームワークです。 このフレームワークは、最近Belovs、Jeffery、Yolcuによって導入されたTransducerツールキットに基づいている。 これは、CousinsとVempalaによるボールウォークのアモート解析を利用することができる、このアモート化された量子ウォークフレームワークであり、これまで量子実装を禁止していた重要な障壁を克服する。

関連論文リスト

• An end-to-end quantum algorithm for nonlinear fluid dynamics with bounded quantum advantage [0.4618037115403289]
  我々は非圧縮性格子ボルツマン方程式の新しいアルゴリズムを開発した。 エンド・ツー・エンドの問題に対しては、選択した観測値に対して、控えめな量子優位性を保持することができる。 我々の結果は、CFDの文脈において、小さいが非自明な量子上の利点が達成できるという確固たる証拠を与える。
  論文  参考訳（メタデータ） (2025-12-03T13:03:08Z)
• Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction [0.984963525011891]
  コンバインとコンバインという量子アルゴリズム設計パラダイムを導入する。 これはカークパトリックとセイデルの「婚前征服」技法の量子版である。
  論文  参考訳（メタデータ） (2025-04-08T18:53:16Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Low-depth Gaussian State Energy Estimation [0.0]
  基底状態エネルギー推定(GSEE)は、量子化学や材料において重要なサブルーチンである。 我々は、O(logDelta)$としてスケールする多数の操作を使用する新しいGSEEアルゴリズムについて詳述する。 このアルゴリズムは、Delta$を$Delta$と$epsilon$の何れかに置き換えることで、低深度とフル深度との間を補間するように適応する。
  論文  参考訳（メタデータ） (2023-09-28T18:29:14Z)
• Alleviating the quantum Big-$M$ problem [0.22615818641180715]
  古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。 我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。 本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-19T18:00:05Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  本稿では,第1量子化における量子力学の実行のための変分量子アルゴリズムを提案する。 シミュレーションでは,従来観測されていた変動時間伝播手法の数値不安定性を示す。
  論文  参考訳（メタデータ） (2022-03-04T19:00:45Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。