論文の概要: Potential for Polynomial Solution for NP-Complete Problems using Quantum Computation
- arxiv url: http://arxiv.org/abs/2504.15529v2
- Date: Sat, 26 Apr 2025 18:23:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-02 19:15:52.765839
- Title: Potential for Polynomial Solution for NP-Complete Problems using Quantum Computation
- Title（参考訳）: 量子計算を用いたNP完全問題に対する多項式解の可能性
- Authors: Neema Rustin Badihian,
- Abstract要約: 本稿では,量子計算を用いた集合制約問題の解法とNP-Complete問題の解法を提案する。
NP-Complete問題に対する潜在的な解が量子計算によってどのように見つかるかを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In this paper, we propose two new methods for solving Set Constraint Problems, as well as a potential polynomial solution for NP-Complete problems using quantum computation. While current methods of solving Set Constraint Problems focus on classical techniques, we offer both a quantum-inspired matrix method and a quantum matrix method that neutralizes common contradictions and inconsistencies that appear in these types of problems. We then use our new method to show how a potential polynomial solution for NP-Complete problems could be found using quantum computation. We state this as a potential solution, rather than an actual solution, as the outcome of any quantum computation may not be the same as the expected outcome. We start by formally defining a Set Constraint Problem. We then explain current, classical methods that are used to solve these problems and the drawbacks of such methods. After this, we explain a new quantum-inspired matrix method that allows us to solve these problems, with classical limitations. Then, we explain a new quantum matrix method that solves these problems using quantum information science. Finally, we describe how we can extend this method to potentially solve NP-Complete problems in polynomial time using quantum computation.
- Abstract（参考訳）: 本稿では,集合制約問題の解法と,量子計算を用いたNP-Complete問題の多項式解法を提案する。
現在のセット制約問題の解法は古典的手法に重点を置いているが、これらの問題に現れる共通矛盾や矛盾を和らげる量子的行列法と量子行列法の両方を提供する。
次に、新しい手法を用いて、NP-Complete問題の多項式解が量子計算によってどのように見つかるかを示す。
量子計算の結果は期待された結果と同じではないかもしれないので、実際の解ではなく、潜在的な解であると我々は主張する。
まず、集合制約問題(Set Constraint problem)を正式に定義することから始める。
次に、これらの問題を解決するために使用される現在の古典的手法と、そのような方法の欠点について説明する。
その後、古典的制限を伴ってこれらの問題を解ける新しい量子インスピレーション行列法について説明する。
次に、量子情報科学を用いてこれらの問題を解決する新しい量子行列法について説明する。
最後に、この方法を拡張して、量子計算を用いて多項式時間におけるNP-Complete問題を解く方法について述べる。
関連論文リスト
- Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
計算問題はすべて、解を返却する厳密な明示的な方程式を持つことを示す。
本稿では, インバージョン, 制約満足度, 最適化の両面から, 正確に任意の問題を解く方程式を得る方法を提案する。
論文 参考訳（メタデータ） (2025-02-09T18:16:53Z) - Solving Sharp Bounded-error Quantum Polynomial Time Problem by Evolution methods [10.891099517614037]
局所ハミルトニアンの基底状態の縮退は、物理学の多くの分野において重要である。
局所ハミルトニアン$kの基底状態を見つけることは、量子メルリンアーサーのより簡単な問題である。
論文 参考訳（メタデータ） (2024-06-05T13:00:22Z) - Solving non-native combinatorial optimization problems using hybrid
quantum-classical algorithms [0.0]
組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。
量子コンピューティングは、様々なアルゴリズムを用いてこれらの問題を解決するために使われてきた。
この研究は、量子と古典のリソースをハイブリッドなアプローチで統合することで、これらの課題を克服する枠組みを提示している。
論文 参考訳（メタデータ） (2024-03-05T17:46:04Z) - Lower bounds for quantum-inspired classical algorithms via communication complexity [0.5461938536945723]
線形回帰の解法,クラスタリングの監督,主成分分析,レコメンデーションシステム,ハミルトニアンシミュレーションに焦点をあてる。
基底行列のフロベニウスノルムの観点で二次下界を証明する。
これらの問題に対する量子アルゴリズムはフロベニウスノルムにおいて線型であるため、この結果は量子古典的分離が少なくとも二次的であることを意味する。
論文 参考訳（メタデータ） (2024-02-24T02:15:00Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - 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-based Distributed Algorithms for Edge Node Placement and
Workload Allocation [8.937905773981702]
最適なエッジサーバ配置とワークロード割り当てのための混合整数線形プログラミング(MILP)モデルを提案する。
既存の量子解法は制約のないバイナリプログラミング問題の解法に限られる。
数値実験により,エッジコンピューティングの複雑な最適化問題を解くために量子超越性を活用できることが実証された。
論文 参考訳（メタデータ） (2023-06-01T21:33:08Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Metropolis Solver: A Quantum Walks Approach to Optimization
Problems [0.0]
本稿では,量子ウォークに基づくメトロポリス・ハスティングス量子アルゴリズムについて述べる。
私たちはこのアルゴリズムを使ってQuantum Solver(QMS)という量子ソフトウェアツールを構築します。
我々は,N-Queen問題を用いてQMSを検証することで,人工知能領域に容易に外挿可能な量子優位性を示す。
論文 参考訳（メタデータ） (2022-07-13T18:26:36Z) - Near-term quantum algorithm for computing molecular and materials
properties based on recursive variational series methods [44.99833362998488]
本稿では,分子の特性を短期量子デバイスを用いて推定する量子アルゴリズムを提案する。
エネルギー領域における一粒子グリーン関数と時間領域における自己相関関数を計算し,本手法を検証した。
論文 参考訳（メタデータ） (2022-06-20T16:33:23Z) - Canonically consistent quantum master equation [68.8204255655161]
我々は、無限小弱い系-バス結合限界を超えた開量子系の状態を正しく再現する新しい量子マスター方程式を提唱した。
本手法は, 定常状態の減少に関する知識を力学に取り入れることに基づいている。
論文 参考訳（メタデータ） (2022-05-25T15:22:52Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Theoretical survey of unconventional quantum annealing methods applied
to adifficult trial problem [2.2209333405427585]
量子アニーリング(QA)に対する異例の修正について考察する。
この問題では、大規模システムにおける「横磁場カオス」にインスパイアされた古典的および量子的手法は、偽の局所的最小値に向けて操られる。
本稿では,この問題を文献からの様々な新しい手法を用いて数値的に研究する。
論文 参考訳（メタデータ） (2020-11-12T05:54:57Z) - Quantum Geometric Machine Learning for Quantum Circuits and Control [78.50747042819503]
我々は、量子幾何学的制御問題に対するディープラーニングの適用をレビューし、拡張する。
量子回路合成問題における時間-最適制御の強化について述べる。
我々の研究結果は、時間-最適制御問題に対する機械学習と幾何学的手法を組み合わせた量子制御と量子情報理論の研究者にとって興味深いものである。
論文 参考訳（メタデータ） (2020-06-19T19:12:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。