論文の概要: Qubit-efficient encoding schemes for binary optimisation problems
- arxiv url: http://arxiv.org/abs/2007.01774v2
- Date: Wed, 21 Apr 2021 05:22:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-11 18:25:07.681988
- Title: Qubit-efficient encoding schemes for binary optimisation problems
- Title（参考訳）: 二進最適化問題に対する量子効率符号化スキーム
- Authors: Benjamin Tan, Marc-Antoine Lemonde, Supanut Thanasilp, Jirawat
Tangpanitanon, Dimitris G. Angelakis
- Abstract要約: 本稿では,制約のない二項最適化問題を解くための変分量子アルゴリズムを提案する。
基礎となる符号化スキームは、古典変数間の相関を体系的に増加させることができる。
古典変数間の2体相関を変動量子状態に組み込む方法を示す。
- 参考スコア（独自算出の注目度）: 2.320907642318629
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose and analyze a set of variational quantum algorithms for solving
quadratic unconstrained binary optimization problems where a problem consisting
of $n_c$ classical variables can be implemented on $\mathcal O(\log n_c)$
number of qubits. The underlying encoding scheme allows for a systematic
increase in correlations among the classical variables captured by a
variational quantum state by progressively increasing the number of qubits
involved. We first examine the simplest limit where all correlations are
neglected, i.e. when the quantum state can only describe statistically
independent classical variables. We apply this minimal encoding to find
approximate solutions of a general problem instance comprised of 64 classical
variables using 7 qubits. Next, we show how two-body correlations between the
classical variables can be incorporated in the variational quantum state and
how it can improve the quality of the approximate solutions. We give an example
by solving a 42-variable Max-Cut problem using only 8 qubits where we exploit
the specific topology of the problem. We analyze whether these cases can be
optimized efficiently given the limited resources available in state-of-the-art
quantum platforms. Lastly, we present the general framework for extending the
expressibility of the probability distribution to any multi-body correlations.
- Abstract（参考訳）: 古典変数 $n_c$ からなる問題を $\mathcal o(\log n_c)$ qubits 上で実装できる二次的制約のない二進最適化問題を解くための変分量子アルゴリズムのセットを提案し,解析する。
基礎となる符号化方式は、関連する量子ビットの数を徐々に増加させることで、変動量子状態によって捕捉される古典変数間の相関を体系的に増加させることができる。
まず、すべての相関が無視される最も単純な極限、すなわち量子状態が統計的に独立な古典変数しか記述できない場合を調べる。
この最小エンコーディングを用いて,64個の古典変数からなる一般問題インスタンスの近似解を7量子ビットで求める。
次に,古典変数間の2体相関を変分量子状態に組み込む方法と近似解の品質を改善する方法を示す。
ここでは,42変数のMax-Cut問題を8キュービットで解き,その問題固有のトポロジを利用する例を示す。
最先端の量子プラットフォームで利用可能な限られたリソースを考えると、これらのケースを効率的に最適化できるかどうかを分析する。
最後に,確率分布の表現可能性を多体相関に拡張するための一般的な枠組みを提案する。
関連論文リスト
- 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
本研究では,最適化のための量子および古典的手法の可能性を統合する。
線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。
実量子ハードウェアの計算結果を多数提示する。
論文 参考訳（メタデータ） (2023-02-10T20:12:53Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Variational Quantum Non-Orthogonal Optimization [0.0]
複雑な最適化問題を解くのに必要なキュービットの数を大幅に削減できることを示す。
我々の提案は、今日の限定量子ハードウェアにおいて、現実の有用な最適化問題を解決するための道を開く。
論文 参考訳（メタデータ） (2022-10-06T18:00:02Z) - Quantum Regularized Least Squares [0.0]
ほとんどの実世界のシナリオでは、線形回帰問題はしばしば不備を課されるか、根底にあるモデルは過度な適合に悩まされる。
これはしばしば、正規化として知られる追加の制約を加えることで対処される。
ブロック符号化と量子特異値変換のフレームワークを用いて、量子最小二乗に対する最初の量子アルゴリズムを設計する。
論文 参考訳（メタデータ） (2022-06-27T09:43:39Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Solving Quadratic Unconstrained Binary Optimization with
divide-and-conquer and quantum algorithms [0.0]
分割・対数手法を用いて、元の問題を小さな問題の集合に還元する。
この手法は任意のQUBOインスタンスに適用でき、全古典的またはハイブリッドな量子古典的アプローチにつながる。
論文 参考訳（メタデータ） (2021-01-19T19:00:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。