論文の概要: Qudit-based scalable quantum algorithm for solving the integer programming problem

• arxiv url: http://arxiv.org/abs/2508.13906v1
• Date: Tue, 19 Aug 2025 15:06:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-20 15:36:31.976847
• Title: Qudit-based scalable quantum algorithm for solving the integer programming problem
• Title（参考訳）: 整数計画問題の解法のための量子量に基づくスケーラブル量子アルゴリズム
• Authors: Kapil Goswami, Peter Schmelcher, Rick Mukherjee,
• Abstract要約: プログラミング (IP) はNPのハードな最適化問題であり、現実世界の様々な問題を表現するために広く使われている。 IPを解くためのほとんどの量子アルゴリズムは、整数を量子ビットにエンコードするため、非常に非効率である。 本研究では,回路ベースでスケーラブルな量子アルゴリズムを複数の相互作用量子ビットを用いて提案し,量子スピードアップを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Integer programming (IP) is an NP-hard combinatorial optimization problem that is widely used to represent a diverse set of real-world problems spanning multiple fields, such as finance, engineering, logistics, and operations research. It is a hard problem to solve using classical algorithms, as its complexity increases exponentially with problem size. Most quantum algorithms for solving IP are highly resource inefficient because they encode integers into qubits. In [1], the issue of resource inefficiency was addressed by mapping integer variables to qudits. However, [1] has limited practical value due to a lack of scalability to multiple qudits to encode larger problems. In this work, by extending upon the ideas of [1], a circuit-based scalable quantum algorithm is presented using multiple interacting qudits for which we show a quantum speed-up. The quantum algorithm consists of a distillation function that efficiently separates the feasible from the infeasible regions, a phase-amplitude encoding for the cost function, and a quantum phase estimation coupled with a multi-controlled single-qubit rotation for optimization. We prove that the optimal solution has the maximum probability of being measured in our algorithm. The time complexity for the quantum algorithm is shown to be $O(d^{n/2} + m\cdot n^2\cdot \log{d} + n/\epsilon_{QPE})$ for a problem with the number of variables $n$ taking $d$ integer values, satisfying $m$ constraints with a precision of $\epsilon_{QPE}$. Compared to the classical time complexity of brute force $O(d^n)$ and the best classical exact algorithm $O((\log{n})^{3n})$, it incurs a reduction of $d^{n/2}$ in the time complexity in terms of $n$ for solving a general polynomial IP problem.
• Abstract（参考訳）: 整数プログラミング(英: Integer Programming、IP)は、金融、工学、物流、オペレーション研究など、様々な分野にまたがる現実世界の問題の集合を表現するために広く用いられているNPハード組合せ最適化問題である。 複雑性は問題の大きさとともに指数関数的に増加するため、古典的なアルゴリズムを用いることで解決するのは難しい。 IPを解くためのほとんどの量子アルゴリズムは、整数を量子ビットにエンコードするため、非常に非効率である。 [1]では、リソース不効率の問題は整数変数をクォーディットにマッピングすることで対処された。 しかし[1]は、より大きな問題をエンコードする複数のキューディットへのスケーラビリティの欠如により、実用的価値が限られている。 本研究では, [1] の考え方を拡張して, 回路ベースのスケーラブルな量子アルゴリズムを, 量子スピードアップを示す複数の相互作用キューディットを用いて提示する。 量子アルゴリズムは、実現不可能な領域から効率よく分離可能な蒸留関数と、コスト関数の位相振幅符号化と、最適化のためのマルチ制御シングルキュービット回転とを組み合わせた量子位相推定とから構成される。 最適解が我々のアルゴリズムで測定される最大確率を持つことを示す。 量子アルゴリズムの時間複雑性は$O(d^{n/2} + m\cdot n^2\cdot \log{d} + n/\epsilon_{QPE})$で、変数数$n$と$d$の整数値を持ち、$\epsilon_{QPE}$の精度で$m$の制約を満たす。 ブラトフォース$O(d^n)$と古典的正則アルゴリズム$O((\log{n})^{3n})$の古典的時間複雑性と比較すると、一般的な多項式IP問題の解法として$n$の時間複雑性において$d^{n/2}$が減少する。

関連論文リスト

• Quantum Algorithm for the Fixed-Radius Neighbor Search [39.58317527488534]
  本稿では,Grover アルゴリズムの固定点バージョンに基づく固定 RAdius Neighbor Search problem (FRANS) の量子アルゴリズムを提案する。 我々は,FRANSを,粒子数$N$の線形クエリ複雑性で解くための効率的な回路を導出する。 読み出し誤差に対するモデルのレジリエンスを評価し,結果の精度を確認するための誤り訂正フリー戦略を提案する。
  論文  参考訳（メタデータ） (2025-07-04T10:01:10Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Integer Programming Using A Single Atom [0.0]
  我々は,IP問題を元の形で任意の量子システムにマップし,解くアルゴリズムを開発した。 最適解は、最大8つの変数と4つの制約を持つIP問題に対して数マイクロ秒以内に見つかる。
  論文  参考訳（メタデータ） (2024-02-26T12:59:20Z)
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs [0.0]
  そこで我々は, 断熱量子計算に基づく線形線形解法アルゴリズムを開発した。 このアルゴリズムは最適スケーリング$O(kappa/log$)$に改善され、$epsilon$が指数関数的に改善される。 ハミルトンシミュレーションの代わりに、より安価なランダム化されたウォーク演算子法を導入する。
  論文  参考訳（メタデータ） (2023-05-19T00:07:32Z)
• Pauli String Partitioning Algorithm with the Ising Model for Simultaneous Measurement [0.0]
  本研究では,パウリ弦を1つの量子回路で同時に測定可能な部分群に分割する効率的なアルゴリズムを提案する。 我々の分割アルゴリズムは、量子化学のための変分量子固有解法における測定総数を劇的に削減する。
  論文  参考訳（メタデータ） (2022-05-09T01:49:21Z)
• A quantum algorithm for computing the Carmichael function [0.0]
  量子コンピュータは、多くの数理論問題を効率的に解くことができる。 本稿では,任意の整数$N$に対して,所望の 1 に近い確率でカーマイケル関数を計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-03T19:30:27Z)
• Quantum mean value approximator for hard integer value problems [19.4417702222583]
  正確な予想よりも近似を用いることで、最適化を大幅に改善できることを示す。 効率的な古典的サンプリングアルゴリズムとともに、極小ゲート数を持つ量子アルゴリズムは、一般的な整数値問題の効率を向上させることができる。
  論文  参考訳（メタデータ） (2021-05-27T13:03:52Z)

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

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