論文の概要: Quantum Complexity of Solving Linear Equations on Higher-Order Networks
- arxiv url: http://arxiv.org/abs/2610.05806v1
- Date: Mon, 05 Oct 2026 04:57:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-10 04:14:41.687568
- Title: Quantum Complexity of Solving Linear Equations on Higher-Order Networks
- Title（参考訳）: 高次ネットワーク上の線形方程式の解く量子複雑性
- Abstract要約: ラプラシア線型系の正規化最小ノルム解を符号化する量子状態が$mathsfBQP$-hardであることを示す。
この結果は,HON解析における量子優位性を評価するために,最悪の複雑性基盤を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Higher-order networks (HONs) represent interactions among groups of objects, supporting the study of collective behaviour that pairwise models can miss. In simplicial models of these networks, Hodge Laplacian linear systems provide a common mathematical framework for analysis, for example, for solving statistical ranking problems and investigating long-term stability in coupled oscillator systems. The large number of variables associated with edges, triangles, and higher-dimensional simplices can make these systems costly to solve. Recent quantum algorithms address this bottleneck. However, comparisons with particular classical algorithms do not decision output whether solving these linear system problems establishes a quantum complexity foundation for provable quantum advantage. We prove that preparing a quantum state encoding the normalized minimum-norm solution of Hodge Laplacian linear systems is $\mathsf{BQP}$-hard under the specified sparse oracle model and parameter promises. Our sequence of reductions maps an arbitrary polynomial-time bounded-error quantum computation to such linear systems. Each reduction allows efficient recovery of the normalized minimum-norm solution of the preceding linear system. Together with an efficient quantum algorithm for the associated decision problem from the approximate solution state, we show that this problem is $\mathsf{BQP}$-complete. These results provide a worst-case complexity foundation for evaluating quantum advantage in HON analysis and show that the $\mathsf{BQP}$-hardness of the quantum linear system problem (QLSP) persists even when the matrices are restricted to Hodge Laplacians.
- Abstract（参考訳）: 高次ネットワーク(HON)は、オブジェクトのグループ間の相互作用を表現し、ペアワイズモデルが見逃す可能性のある集合的挙動の研究を支援する。
これらのネットワークの単純なモデルにおいて、ホッジ・ラプラシアン線形系は、例えば統計ランク問題の解法や結合振動子系の長期安定性の研究など、分析のための一般的な数学的枠組みを提供する。
エッジ、三角形、高次元の単純化に関連する多数の変数は、これらのシステムを解くのにコストがかかる。
最近の量子アルゴリズムはこのボトルネックに対処する。
しかし、古典的アルゴリズムとの比較では、これらの線形系問題の解決が証明可能な量子優位性のための量子複雑性基盤を確立するかどうかを決定できない。
ホッジ・ラプラシア線型系の正規化最小ノルム解を符号化する量子状態は、特定のスパースオラクルモデルとパラメータ約束の下で$\mathsf{BQP}$-hardであることを示す。
我々のリダクションのシーケンスは、任意の多項式時間有界エラー量子計算をそのような線形系にマッピングする。
各還元は、前の線形系の正規化最小ノルム解の効率的な回復を可能にする。
近似解状態から決定問題を解くための効率的な量子アルゴリズムとともに、この問題は$\mathsf{BQP}$-completeであることを示す。
これらの結果は、HON分析における量子優位性を評価するための最悪の複雑性基盤を提供し、量子線形系問題(QLSP)の$\mathsf{BQP}$-hardnessがホッジ・ラプラシアンに制限された場合でも持続することを示す。
関連論文リスト
- Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity [19.524934592701157]
線形代数方程式をODEの観点から解く量子アルゴリズムを開発した。
フーリエ法におけるハミルトンシミュレーション(LCHS)の線形結合に着想を得た。
2つのLCHSインスタンスを持つLCHSベースの量子アルゴリズムを構築し,その1つは時間マーチングのためのもので,1つは数値積分のためのものである。
論文 参考訳（メタデータ） (2026-09-17T04:22:23Z) - Shadow Quantum Linear Solver: A Resource Efficient Quantum Algorithm for Linear Systems of Equations [1.1024591739346294]
本稿では,デジタル量子デバイス上での量子線形システム問題(QLSP)の解法を提案する。
その結果、大きな制御されたユニタリの必要性を回避し、システムサイズで対数的な多くの量子ビットを必要とする量子アルゴリズムが実現した。
これを、線形代数の分解定理を利用して、2次元格子における離散化されたラプラス方程式を解くことで、実用的妥当性の物理問題に適用する。
論文 参考訳（メタデータ） (2024-09-13T15:46:32Z) - An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
本稿では,最近のアディバティック・インスパイアされたQLSAの進歩に基づく量子アルゴリズムを提案する。
実装の全体的な複雑さは、その次元において多対数的であることを厳密に示します。
論文 参考訳（メタデータ） (2024-03-28T20:37:32Z) - Hybrid quantum-classical and quantum-inspired classical algorithms for
solving banded circulant linear systems [0.8192907805418583]
帯状循環系に対する量子状態の組み合わせの凸最適化に基づく効率的なアルゴリズムを提案する。
帯状循環行列を巡回置換に分解することにより, 量子状態の組み合わせによる近似解を$K$とする。
我々は,従来のシミュレーションと実際のIBM量子コンピュータ実装を用いて本手法を検証し,熱伝達などの物理問題への適用性を示した。
論文 参考訳（メタデータ） (2023-09-20T16:27:16Z) - Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization [39.58317527488534]
本稿では,線形システムの解法を提案する。
線形系を二進最適化問題に変換し、元の問題の幾何学からインスピレーションを得る。
問題固有の幾何学の部分的知識を活用することで、元の問題をより小さく独立したサブプロブレムに分解できることを実証する。
論文 参考訳（メタデータ） (2023-09-18T16:51:03Z) - Quantum Relaxation for Linear Systems in Finite Element Analysis [0.0]
ゲートベース量子コンピュータの反復的アプローチとして,リニアシステム(qRLS)の量子緩和を提案する。
このシステムは、QLSAの最先端量子信号処理(QSP)変種を用いて、有限要素問題の実用的な反復解を可能にする。
これは指数効率の向上を表しており、量子ハードウェア上での反復有限要素問題の解法に対する新しいアプローチを提供する。
論文 参考訳（メタデータ） (2023-08-02T18:31:33Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳（メタデータ） (2022-09-27T17:56:15Z) - Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary
Optimization [44.96576908957141]
本稿では,量子コンピュータ上での2次線形反復問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
論文 参考訳（メタデータ） (2022-03-23T18:00:03Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。