論文の概要: Harnessing problem structure for end-to-end quantum speed-ups

• arxiv url: http://arxiv.org/abs/2609.40105v1
• Date: Wed, 30 Sep 2026 16:37:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.092427
• Title: Harnessing problem structure for end-to-end quantum speed-ups
• Title（参考訳）: エンドツーエンド量子スピードアップのためのハーネス化問題構造
• Abstract要約: 構造認識型量子データ符号化のための汎用フレームワークを提案する。 構造に依存しないエンコーディングにより、量子スピードアップがエンドツーエンドのコスト会計に耐えられることを示す。
• 参考スコア（独自算出の注目度）: 25.80610219990413
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum algorithms can offer substantial computational speed-ups, yet these advantages may disappear once the cost of structure-agnostic classical data encoding is taken into account. Real-world problem instances, however, often possess rich internal structure. This raises a fundamental question: can such structure be harnessed to make quantum speed-ups survive end-to-end cost accounting? Here we show that it can. We introduce a general framework for structure-aware quantum data encoding that compiles compact recursive descriptions of problem structure into efficient state-preparation circuits, translating structural information directly into reduced encoding complexity. For the uncapacitated facility-location problem, structure-agnostic encoding admits a classical dequantization that eliminates the quadratic quantum speed-up, whereas exploiting the underlying problem structure restores this advantage even when state-preparation costs are included. More broadly, the same framework prepares structured quantum states for combinatorial optimization that capture non-trivial relations among constraints, including group balance, conflicts and synergistic rewards, extending previously reported super-polynomial quantum advantages to broader classes of objectives. These results establish exploitable problem structure as a computational resource for quantum algorithms and provide a systematic route towards realizing quantum advantage in data-intensive problems.
• Abstract（参考訳）: 量子アルゴリズムは計算速度を大幅に向上させることができるが、構造に依存しない古典的データ符号化のコストを考慮すると、これらの利点は消滅する可能性がある。 しかし、実世界の問題の場合、しばしば内部構造が豊富である。 このような構造を利用して、量子スピードアップがエンドツーエンドのコスト会計に耐えられるか? ここではそれが可能であることを示す。 本稿では,問題構造のコンパクトな再帰的記述を効率的な状態準備回路にコンパイルし,構造情報を直接符号化複雑性の低減に変換する構造認識型量子データ符号化の汎用フレームワークを提案する。 キャパシタ化されていない施設配置問題に対して、構造非依存の符号化は古典的な量子スピードアップを排除した量子量子化を許容する一方、基礎となる問題構造は、状態準備コストを含む場合でもこの利点を回復する。 より広範に、同じフレームワークは、グループバランス、競合、シナジスティック報酬を含む制約間の非自明な関係をキャプチャする組合せ最適化のための構造化量子状態を準備し、以前報告された超多項式量子の利点をより広範な目的のクラスに拡張する。 これらの結果は、量子アルゴリズムの計算資源として利用可能な問題構造を確立し、データ集約問題における量子優位性を実現するための体系的な経路を提供する。

関連論文リスト

• Exponential Quantum Speedup on Structured Hard Instances of Maximum Independent Set [0.0]
  我々は、古典的にハードな最大独立集合(MIS)のインスタンス群を特定し、非確率的アディバティック量子最適化アルゴリズムの設計と解析を行う。 このアルゴリズムは時間内に実行され、横フィールド量子と最先端の古典的解法の両方に対して指数的なスピードアップを達成する。 これはスピードアップの根底にある特異な量子機構を特定し、なぜ効率的な古典的なアナログが存在しないのかを説明する。
  論文  参考訳（メタデータ） (2026-01-25T04:18:35Z)
• Formal Framework for Quantum Advantage [2.1155908599769764]
  個々の問題インスタンスの観点で量子計算の優位性を定義する。 量子アルゴリズムの待ち時間には指数関数的アルゴリズムが有効であることを示す。 この正式な枠組みはビーコンとして機能し、実際は量子的優位性の探求を導く。
  論文  参考訳（メタデータ） (2025-10-02T12:22:54Z)
• Character Complexity: A Novel Measure for Quantum Circuit Analysis [0.0]
  本稿では,グループ理論の概念を実用的な量子コンピューティングの課題にブリッジする新しい尺度であるキャラクタ複雑度を紹介する。 キャラクタ複雑性のいくつかの重要な性質を証明し、量子回路の古典的シミュラビリティへの驚くべき接続を確立する。 本稿では、量子回路の構造に関する直感的な洞察を提供する、文字複雑性の革新的な可視化手法を提案する。
  論文  参考訳（メタデータ） (2024-08-19T01:58:54Z)
• A perspective on protein structure prediction using quantum computers [0.4397520291340696]
  我々は,タンパク質構造予測問題を選択するための枠組みを構築した。 ユーティリティスケールの量子コンピュータ上で,そのような問題に対する量子資源を推定する。 概念実証として,ジカウイルスNS3ヘリカーゼの触媒ループの構造を正確に予測し,問題選択の枠組みを検証する。
  論文  参考訳（メタデータ） (2023-12-01T19:04:02Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  本稿では,限られた情報伝達と保守的絡み合い生成を含む短期分散量子コンピューティングを提案する。 我々はこれらの概念に基づいて、変分量子アルゴリズムの断片化事前学習のための近似回路切断手法を作成する。
  論文  参考訳（メタデータ） (2023-09-11T18:00:00Z)
• Unitary Complexity and the Uhlmann Transformation Problem [39.6823854861458]
  本稿では, 単項合成問題の枠組みを導入し, 還元と単項複雑性クラスについて考察する。 このフレームワークは、ある絡み合った状態が局所的な操作によって別の状態に変換される複雑さを研究するのに使用します。 そこで我々は,多くの自然量子情報処理タスクの計算複雑性を研究するための新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-06-22T17:46:39Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)

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

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