論文の概要: Number Partitioning with Grover's Algorithm in Central Spin Systems
- arxiv url: http://arxiv.org/abs/2009.05549v3
- Date: Thu, 27 May 2021 15:46:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-02 22:19:13.268131
- Title: Number Partitioning with Grover's Algorithm in Central Spin Systems
- Title（参考訳）: 中央スピン系におけるグローバーアルゴリズムによる数分割
- Authors: Galit Anikeeva, Ognjen Markovi\'c, Victoria Borish, Jacob A. Hines,
Shankari V. Rajagopal, Eric S. Cooper, Avikar Periwal, Amir Safavi-Naeini,
Emily J. Davis, Monika Schleier-Smith
- Abstract要約: 本稿では,部分和問題として知られるNP完全決定問題のクラスに対する解を求めるGrover探索を提案する。
各問題インスタンスは、一組の量子ビットの中央スピンやボソンへのカップリングに符号化され、溶液を知らずにオラクルの実現を可能にする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Numerous conceptually important quantum algorithms rely on a black-box device
known as an oracle, which is typically difficult to construct without knowing
the answer to the problem that the algorithm is intended to solve. A notable
example is Grover's search algorithm. Here we propose a Grover search for
solutions to a class of NP-complete decision problems known as subset sum
problems, including the special case of number partitioning. Each problem
instance is encoded in the couplings of a set of qubits to a central spin or
boson, which enables a realization of the oracle without knowledge of the
solution. The algorithm provides a quantum speedup across a known phase
transition in the computational complexity of the partition problem, and we
identify signatures of the phase transition in the simulated performance.
Whereas the naive implementation of our algorithm requires a spectral
resolution that scales exponentially with system size for NP-complete problems,
we also present a recursive algorithm that enables scalability. We propose and
analyze implementation schemes with cold atoms, including Rydberg-atom and
cavity-QED platforms.
- Abstract（参考訳）: 多くの概念上重要な量子アルゴリズムは、オラクルと呼ばれるブラックボックスデバイスに依存しており、アルゴリズムが解決しようとする問題に対する答えを知らずに構築することが通常困難である。
有名な例はグローバーの探索アルゴリズムである。
ここでは,部分和問題と呼ばれるNP完全決定問題のクラスに対する解を求めるグロバー探索を提案する。
各問題インスタンスは、一組の量子ビットの中央スピンやボソンへのカップリングに符号化され、溶液を知らずにオラクルの実現を可能にする。
このアルゴリズムは、分割問題の計算複雑性における既知の相転移の量子スピードアップを提供し、シミュレーション性能における相転移のシグネチャを特定する。
提案アルゴリズムはNP完全問題に対するシステムサイズと指数関数的にスケールするスペクトル分解能を必要とするが,拡張性を実現する再帰的アルゴリズムも提案する。
我々は,rydberg-atom やcavity-qed プラットフォームを含むコールド原子を用いた実装方式を提案し,解析する。
関連論文リスト
- Opening the Black Box Inside Grover's Algorithm [0.0]
グロバーのアルゴリズムは、量子コンピュータが古典的コンピュータよりも有利であることを示す主要なアルゴリズムである。
我々は,古典的コンピュータ上で動作可能な量子インスパイアされたアルゴリズムを構築し,Groverのタスクを,オラクルへの(シミュレーションの)呼び出し数で線形に実行する。
論文 参考訳（メタデータ） (2023-03-20T17:56:20Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation [0.0]
雑音二元線形問題(NBLP)の量子可解性について完全解析する。
NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
論文 参考訳（メタデータ） (2021-09-23T07:46:20Z) - Detailed Account of Complexity for Implementation of Some Gate-Based
Quantum Algorithms [55.41644538483948]
特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。
本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
論文 参考訳（メタデータ） (2021-06-23T16:33:33Z) - A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs [0.4925222726301578]
本稿では、整数線形プログラムの解を見つけることができる任意の量子アルゴリズムをブランチ・アンド・プライス・アルゴリズムに統合する手法を提案する。
量子アルゴリズムの役割は、ブランチ・アンド・プライスに現れるサブプロブレムに対する整数解を見つけることである。
論文 参考訳（メタデータ） (2021-03-29T08:59:26Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - Introducing Structure to Expedite Quantum Search [0.0]
本稿では,非構造化探索問題を1つの有意な要素で解くための新しい量子アルゴリズムを提案する。
我々のアルゴリズムは乗算定数までの基本ゲートの総数で最適である。
本稿では,複数要素を持つ非構造化探索問題の解法に必要な基本ゲートの数をトータルに削減する方法を示す。
論文 参考訳（メタデータ） (2020-06-10T13:29:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。