1IBM Quantum、IBM Research –チューリッヒ、Säumerstrasse4、8803Rüschlikon、スイス
2チェコ工科大学、カルロヴォナム。 13、プラハ2、チェコ共和国
この論文を興味深いと思うか、議論したいですか？ SciRateを引用するかコメントを残す.
抽象
整数計画法と組み合わせ最適化の問題に対する量子アルゴリズムへの関心が高まっています。 このような問題の古典的なソルバーは、たとえば高次元の行列値問題（半正定値計画法）の形で、バイナリ変数を連続変数に置き換える緩和を採用しています。 ユニークゲーム予想の下では、これらの緩和は、多項式時間で古典的に利用可能な最高のパフォーマンス比を提供することがよくあります。 ここでは、組み合わせ最適化問題の緩和の解に対応する初期状態で量子最適化をウォームスタートする方法と、関連する量子アルゴリズムの特性を分析する方法について説明します。 特に、これにより、量子アルゴリズムは従来のアルゴリズムのパフォーマンス保証を継承できます。 ポートフォリオ最適化のコンテキストでこれを説明します。この結果は、量子近似最適化アルゴリズム（QAOA）のウォームスタートが低深度で特に有益であることを示しています。 同様に、MAXCUT問題の再帰的QAOAは、Goemans-Williamsonランダム化丸めがウォームスタートで使用される場合、ランダムな重みを持つ完全に接続されたグラフに対して取得されたカットのサイズの体系的な増加を示します。 同じアイデアを他のランダム化された丸めスキームや最適化問題に適用するのは簡単です。
注目の画像：ウォームスタートQAOAの量子回路。
人気の要約
►BibTeXデータ
►参照
【1] Nikolaj Moll、Panagiotis Barkoutsos、Lev S. Bishop、Jerry M. Chow、Andrew Cross、Daniel J. Egger、Stefan Filipp、Andreas Fuhrer、Jay M. Gambetta、Marc Ganzhorn、他短期量子デバイスで変分アルゴリズムを使用した量子最適化。 量子科学。 Technol。、3（3）：030503、2018。10.1088 / 2058-9565 / aab822。
https：/ / doi.org/ 10.1088 / 2058-9565 / aab822
【2] Abhinav Kandala、Kristan Temme、Antonio D. Corcoles、Antonio Mezzacapo、Jerry M. Chow、JayM.Gambetta。 エラー軽減は、ノイズの多い量子プロセッサの計算範囲を拡張します。 Nature、567：491–495、2018。10.1038 / s41586-019-1040-7。
https://doi.org/10.1038/s41586-019-1040-7
【3] Marc Ganzhorn、Daniel J. Egger、PanagiotisKl。 Barkoutsos、Pauline Ollitrault、Gian Salis、Nikolaj Moll、Andreas Fuhrer、Peter Mueller、Stefan Woerner、Ivano Tavernelli、Stefan Filipp 量子コンピューター上での分子固有状態のゲート効率の良いシミュレーション。 物理学Rev. Applied、11：044092、2019年10.1103月。11.044092/ PhysRevApplied.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevApplied.11.044092
【4] ジェイコブ・ビアモンテ、ピーター・ヴィッテク、ニコラ・パンコッティ、パトリック・レベントロスト、ネイサン・ウィーブ、セス・ロイド。 量子機械学習。 Nature、549（7671）：195–202、2017。10.1038 / nature23474。
https：/ / doi.org/ 10.1038 / nature23474
【5] Vojtech Havlicek、Antonio D. Corcoles、Kristan Temme、Aram W. Harrow、Abhinav Kandala、Jerry M. Chow、JayM.Gambetta。 量子強化特徴空間による教師あり学習。 Nature、567：209 – 212、2019。10.1038 / s41586-019-0980-2。
https://doi.org/10.1038/s41586-019-0980-2
【6] Daniel J. Egger、Claudio Gambella、JakubMareček、Scott McFaddin、Martin Mevissen、Rudy Raymond、Aandrea Simonetto、Sefan Woerner、Elena Yndurain 金融のための量子コンピューティング：最先端および将来の展望。 IEEETrans。 Quantum Eng。、1：1–24、2020。10.1109 /TQE.2020.3030314。
https：/ / doi.org/ 10.1109 / TQE.2020.3030314
【7] StefanWoernerとDanielJ。Egger 量子リスク分析。 npj Quantum Inf。、5：15、2019。10.1038 / s41534-019-0130-6。
https://doi.org/10.1038/s41534-019-0130-6
【8] Patrick Rebentrost、Brajesh Gupt、およびThomas R.Bromley。 量子計算金融：金融デリバティブのモンテカルロ価格設定。 物理学Rev.A、98：022321、2018年10.1103月。98.022321/ PhysRevA.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevA.98.022321
【9] Nikitas Stamatopoulos、Daniel J. Egger、Yue Sun、Christa Zoufal、Raban Iten、Ning Shen、Stefan Woerner 量子コンピューターを使用したオプション価格。 Quantum、4：291、2020。10.22331 / q-2020-07-06-291。
https://doi.org/10.22331/q-2020-07-06-291
【10] Ana Martin、Bruno Candelas、ÁngelRodríguez-Rozas、JoséD.Martín-Guerrero、Xi Chen、Lucas Lamata、RománOrús、Enrique Solano、Mikel Sanz IBM量子コンピューターによる金融デリバティブの価格設定に向けて。 物理学Rev. Research、3：013167、2021年10.1103月。3.013167/ PhysRevResearch.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevResearch.3.013167
【11] Roman Orus、Samuel Mugel、およびEnriqueLizaso。 金融のための量子コンピューティング：概要と展望。 Rev. Phys。、4：100028、2019。10.1016 /j.revip.2019.100028。
https：/ / doi.org/ 10.1016 / j.revip.2019.100028
【12] Daniel J. Egger、Ricardo G. Gutierrez、Jordi Cahue Mestre、Stefan Woerner 量子コンピューターを用いた信用リスク分析。 IEEETrans。 計算、1：1–1、2020年10.1109月。2020.3038063/ TC.XNUMX。
https：/ / doi.org/ 10.1109 / TC.2020.3038063
【13] Almudena CarreraVazquezとStefanWoerner。 量子振幅推定のための効率的な状態準備。 物理学Rev. Applied、15：034027、2021年10.1103月。15.034027/ PhysRevApplied.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevApplied.15.034027
【14] Lee Braine、Daniel J. Egger、Jennifer Glick、およびStefanWoerner。 トランザクション決済に適用される混合バイナリ最適化のための量子アルゴリズム。 IEEETrans。 Quantum Eng。、2：1–8、2021。10.1109 /TQE.2021.3063635。
https：/ / doi.org/ 10.1109 / TQE.2021.3063635
【15] パナギオティスKl。 Barkoutsos、Giacomo Nannicini、Anton Robert、Ivano Tavernelli、StefanWoerner。 cvarを使用した変分量子最適化の改善。 Quantum、4：256、2020年10.22331月。2020/ q-04-20-256-XNUMX。
https://doi.org/10.22331/q-2020-04-20-256
【16] エドワード・ファーリ、ジェフリー・ゴールドストーン、サム・ガットマン。 量子近似最適化アルゴリズム、2014a。 URL https：/ / arxiv.org/ abs /1411.4028。
arXiv：1411.4028
【17] エドワード・ファーリ、ジェフリー・ゴールドストーン、サム・ガットマン。 有界発生制約問題に適用される量子近似最適化アルゴリズム、2014b。 URL https：/ / arxiv.org/ abs /1412.6062。
arXiv：1412.6062
【18] ジーチェンヤン、アーミンラーマニ、アリレザシャバニ、ハルトムートネヴェン、クラウディオチャモン。 ポントリャーギンの最小原理を使用した変分量子アルゴリズムの最適化。 物理学Rev. X、7：021027、2017年10.1103月。7.021027/ PhysRevX.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevX.7.021027
【19] マーク・W・ジョンソン、モハマド・HSアミン、スザンヌ・ギルデルト、トレバー・ランティング、フィラス・ハムゼ、ニール・ディクソン、リチャード・ハリス、アンドリュー・J・バークレー、ヤン・ヨハンソン、ポール・ブニックなど。 製造されたスピンによる量子アニーリング。 Nature、473（7346）：194–198、2011年10.1038月。10012/ natureXNUMX。
https：/ / doi.org/ 10.1038 / nature10012
【20] グレンビガンムベン、ロザリオファジオ、ジュゼッペサントロ。 量子アニーリング：デジタル化、制御、ハイブリッド量子変分スキームの旅、2019年。URLhttps：/ / arxiv.org/ abs /1906.08948。
arXiv：1906.08948
【21] Michael Juenger、Elisabeth Lobe、Petra Mutzel、Gerhard Reinelt、Franz Rendl、Giovanni Rinaldi、およびTobiasStollenwerk。 キメラグラフのイジング基底状態計算のための量子アニーラーのパフォーマンス、2019年。URLhttps：/ / arxiv.org/ abs /1904.11965。
arXiv：1904.11965
【22] ラミ・バレンズ、アリレザ・シャバニ、ルーカス・ラマタ、ジュリアン・ケリー、アントニオ・メザカポ、ウルツィ・ラス・ヘラス、ライアン・バブッシュ、オースティン・G・ファウラー、ブルックス・キャンベル、ユー・チェンなど。 超伝導回路を備えたデジタル化された断熱量子計算。 Nature、534（7606）：222–226、2016年10.1038月。17658/ natureXNUMX。
https：/ / doi.org/ 10.1038 / nature17658
【23] Madita Willsch、Dennis Willsch、Fengping Jin、Hans De Raedt、およびKristelMichielsen。 量子近似最適化アルゴリズムのベンチマーク。 QuantumInf。 Process。、19（7）：197、2020年10.1007月。11128/ s020-02692-8-XNUMX。
https://doi.org/10.1007/s11128-020-02692-8
【24] Sergey Bravyi、Alexander Kliesch、Robert Koenig、およびEugeneTang。 対称性保護からの変分量子最適化への障害。 物理学Rev. Lett。、125：260505、2020年10.1103月a。 125.260505 /PhysRevLett.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevLett.125.260505
【25] ギャヴィンE.クルック。 最大カット問題に対する量子近似最適化アルゴリズムのパフォーマンス、2018年。URLhttps：/ / arxiv.org/ abs /1811.08419。
arXiv：1811.08419
【26] エドワード・ファーリ、ジェフリー・ゴールドストーン、サム・ガットマン、ハルトムート・ネヴェン。 固定キュービットアーキテクチャの量子アルゴリズム、2017年。URLhttps：/ / arxiv.org/ abs /1703.06199。
arXiv：1703.06199
【27] スチュアート・ハドフィールド、ジフイ・ワン、ブライアン・オゴーマン、エレナー・リーフェル、ダビデ・ベントゥレッリ、ルパック・ビスワス。 量子近似最適化アルゴリズムから量子交互演算子ansatzまで。 アルゴリズム、12（2）：34、2019年10.3390月。12020034/ aXNUMX。
https：/ / doi.org/ 10.3390 / a12020034
【28] Linghua Zhu、Ho Lun Tang、George S. Barron、Nicholas J. Mayhall、Edwin Barnes、およびSophiaE.Economou。 量子コンピューター上の組み合わせ問題を解決するための適応量子近似最適化アルゴリズム、2020年。URLhttps：/ / arxiv.org/ abs /2005.10258。
arXiv：2005.10258
【29] Zhihui Wang、Nicholas C. Rubin、Jason M. Dominy、およびEleanor G.Rieffel。 XYミキサー：量子交互演算子ansatzの分析結果と数値結果。 物理学Rev. A、101：012320、2020年10.1103月。101.012320/ PhysRevA.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevA.101.012320
【30] Sami Khairy、Ruslan Shaydulin、Lukasz Cincio、Yuri Alexeev、Prasanna Balaprakash 組み合わせ問題を解決するために変分量子回路を最適化することを学ぶ。 人工知能に関するAAAI会議の議事録、34（03）：2367–2375、2020年10.1609月。34/ aaai.v03.5616iXNUMX。
https：/ / doi.org/ 10.1609 / aaai.v34i03.5616
【31] Matteo M. Wauters、Emanuele Panizon、Glen B. Mbeng、およびGiuseppe E.Santoro。 強化学習支援量子最適化。 物理学Rev. Research、2：033446、2020年10.1103月。2.033446/ PhysRevResearch.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevResearch.2.033446
【32] Ruslan Shaydulin、Ilya Safro、およびJeffreyLarson。 量子近似最適化のためのマルチスタート法。 2019 IEEE High Performance Extreme Computing Conference（HPEC）、1〜8ページ、2019年10.1109月。2019.8916288/ HPEC.XNUMX。
https：/ / doi.org/ 10.1109 / HPEC.2019.8916288
【33] RuslanShaydulinとYuriAlexeev。 量子近似最適化アルゴリズムの評価：事例研究。 2019年第1回国際グリーンおよび持続可能なコンピューティング会議（IGSC）、6〜2019ページ、10.1109年。48788.2019.8957201/ IGSCXNUMX。
https：/ / doi.org/ 10.1109 / IGSC48788.2019.8957201
【34] Roeland Wiersema、Cunlu Zhou、Yvette de Sereville、Juan Felipe Carrasquilla、Yong Baek Kim、HenryYuen。 ハミルトニアン変分仮説内のエンタングルメントと最適化の調査。 PRX Quantum、1：020319、2020年10.1103月。1.020319/ PRXQuantum.XNUMX。
https：/ / doi.org/ 10.1103 / PRXQuantum.1.020319
【35] フェルナンドGSLブランダオ、マイケルブロートン、エドワードファーリ、サムグートマン、ハルトムートネヴェン。 固定制御パラメーターの場合、量子近似最適化アルゴリズムの目的関数値は、2018年の典型的なインスタンスに集中します。URLhttps：/ / arxiv.org/ abs /1812.04170。
arXiv：1812.04170
【36] マシューB.ヘイスティングス。 古典的および量子有界深度近似アルゴリズム、2019年。URLhttps：/ / arxiv.org/ abs /1905.07047。
arXiv：1905.07047
【37] Sergey Bravyi、Alexander Kliesch、Robert Koenig、およびEugeneTang。 近似グラフ彩色のためのハイブリッド量子古典アルゴリズム、2020b。 URL https：/ / arxiv.org/ abs /2011.13420。
arXiv：2011.13420
【38] Mahabubul Alam、Abdullah Ash-Saki、およびSwaroopGhosh。 超伝導キュビットの現実的なノイズの下での量子近似最適化アルゴリズムの分析、2019年。URLhttps：/ / arxiv.org/ abs /1907.09631。
arXiv：1907.09631
【39] Vishwanathan Akshay、Hariphan Philathong、Mauro ES Morales、およびJacob D.Biamonte。 量子近似最適化における到達可能性の欠陥。 物理学Rev. Lett。、124：090504、2020年10.1103月a。 124.090504 /PhysRevLett.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevLett.124.090504
【40] マシュー・P・ハリガン、ケビン・J・ソン、マシュー・ニーリー、ケビン・J・サッツィンガー、フランク・アルテ、クナル・アリヤ、フアン・アタラヤ、ジョセフ・C・バーディン、ラミ・バレンズ、セルジオ・ボイクソ他平面超伝導プロセッサ上の非平面グラフ問題の量子近似最適化。 ナットPhys。、17（3）：332–336、2021年10.1038月。41567/ s020-01105-XNUMX-y。
https：/ / doi.org/ 10.1038 / s41567-020-01105-y
【41] Yulong Dong、Xiang Meng、Lin Lin、Robert Kosut、およびK. BirgittaWhaley。 量子近似最適化アルゴリズムのためのロバスト制御最適化。 IFAC-PapersOnLine、53（2）：242–249、2020。10.1016 /j.ifacol.2020.12.130。 第21回IFAC世界会議。
https：/ / doi.org/ 10.1016 / j.ifacol.2020.12.130
【42] Nathan Lacroix、Christoph Hellings、Christian Kraglund Andersen、Agustin Di Paolo、Ants Remm、Stefania Lazar、Sebastian Krinner、Graham J. Norris、Mihai Gabureac、JohannesHeinsooなど。 連続ゲートセットを使用した深層量子最適化アルゴリズムのパフォーマンスの向上。 PRX Quantum、1：110304、2020年10.1103月。1.020304/ PRXQuantum.XNUMX。
https：/ / doi.org/ 10.1103 / PRXQuantum.1.020304
【43] ネイサン・アーネスト、キャロライン・トーノウ、ダニエル・J・エガー。 クロスレゾナンスベースのハードウェアでの量子アプリケーション向けのパルス効率の高い回路変換、2021年。URLhttps：/ / arxiv.org/ abs /2105.01063。
arXiv：2105.01063
【44] Pranav Gokhale、Ali Javadi-Abhari、Nathan Earnest、Yunong Shi、およびFrederic T.Chong。 openpulse、2020を使用した短期アルゴリズム用に最適化された量子コンパイル。URLhttps：/ / www.microarch.org/ micro53 / papers /738300a186.pdf。 10.1109 /MICRO50266.2020.00027。
https：/ / doi.org/ 10.1109 / MICRO50266.2020.00027
https：/ / www.microarch.org/ micro53 / papers / 738300a186.pdf
【45] David C. McKay、Thomas Alexander、Luciano Bello、Michael J. Biercuk、Lev Bishop、Jiayin Chen、Jerry M. Chow、AntonioD.Córcoles、Daniel J. Egger、Stefan Filipp、他OpenQASMおよびOpenPulse実験のQiskitバックエンド仕様、2018年。URLhttps：/ / arxiv.org/ abs /1809.03452。
arXiv：1809.03452
【46] トーマス・アレクサンダー、金沢直樹、ダニエル・J・エガー、ローレン・カペルト、クリストファー・J・ウッド、アリ・ジャバディ・アバリ、デビッド・C・マッケイ。 Qiskitパルス：パルスを使用してクラウドを介して量子コンピューターをプログラミングします。 量子科学。 Technol。、5（4）：044006、2020年10.1088月。2058/ 9565-404 / abaXNUMX。
https：/ / doi.org/ 10.1088 / 2058-9565 / aba404
【47] アニルーダマジュムダール、ジョージナホール、アミールアリアフマディ。 機械学習、制御、ロボット工学のアプリケーションを使用した半正定値計画法の最近のスケーラビリティの向上。 アンヌ。 制御ロボット牧師。 Auton。 Syst。、3：331–360、2020。10.1146 / annurev-control-091819-074326。
https：/ / doi.org/ 10.1146 / annurev-control-091819-074326
【48] ミゲル・F・アンジョスとジャン・B・ラサール。 半確定、円錐および多項式の最適化に関するハンドブック、第166巻。SpringerScience＆Business Media、2011年。10.1007/ 978-1-4614-0769-0。
https://doi.org/10.1007/978-1-4614-0769-0
【49] レノア・ブルーム、フェリペ・カッカー、マイケル・シューブ、スティーブ・スマレ。 複雑さと実際の計算。 Springer Science＆Business Media、2012年。10.1007/ 978-1-4612-0701-6。
https://doi.org/10.1007/978-1-4612-0701-6
【50] LorantPorkolabとLeonidKhachiyan。 半正定値計画の複雑さについて。 J.グロブ。 Optim。、10（4）：351–365、1997。10.1023 / A：1008203903341。
https：/ / doi.org/ 10.1023 / A：1008203903341
【51] Alp Yurtsever、Joel A. Tropp、Olivier Fercoq、Madeleine Udell、VolkanCevher。 スケーラブルな半正定値計画法。 SIAM J.Math。 Data Sci。、3（1）：171–200、2021。10.1137 / 19M1305045。
https：/ / doi.org/ 10.1137 / 19M1305045
【52] プラバカールラガヴァンとクラークD.トンプソン。 ランダム化された丸め：証明可能な優れたアルゴリズムとアルゴリズムによる証明のための手法。 Combinatorica、7（4）：365–374、1987年10.1007月。02579324/ BFXNUMX。
https：/ / doi.org/ 10.1007 / BF02579324
【53] ミシェルX.ゲーマンズとデビッドP.ウィリアムソン。 半正定値計画法を使用した最大カットおよび充足可能性問題の近似アルゴリズムの改善。 J. ACM、42（6）：1115–1145、1995年10.1145月。227683.227684/ XNUMX。
https：/ / doi.org/ 10.1145 / 227683.227684
【54] ハワード・カルロフ。 Goemans–Williamson MAX CUTアルゴリズムはどの程度優れていますか？ SIAM J. Comput。、29（1）：336–350、1999。10.1137 / S0097539797321481。
https：/ / doi.org/ 10.1137 / S0097539797321481
【55] Subhash Khot、Guy Kindler、Elchanan Mossel、RyanO'Donnell。 MAX-CUTおよびその他の2変数CSPの最適な非近似性の結果？ SIAM J. Comput。、37（1）：319–357、2007。10.1137 / S0097539705447372。
https：/ / doi.org/ 10.1137 / S0097539705447372
【56] SubhasKhot。 ユニークなゲーム予想について（招待調査）。 2012年にIEEE27th Conference on Computational Complexity、99〜121ページ、米国カリフォルニア州ロスアラミトス、2010年10.1109月。IEEEComputerSociety。 2010.19 /CCC.XNUMX。
https：/ / doi.org/ 10.1109 / CCC.2010.19
【57] Subhash A.KhotおよびNisheethK。Vishnoi ユニークなゲーム予想、カット問題の完全性ギャップ、および負のタイプのメトリックのl1への埋め込み可能性。 J. ACM、62（1）：1–39、2015。10.1145 / 2629614。
https：/ / doi.org/ 10.1145 / 2629614
【58] クナルマルワハ。 ローカルの古典的なMAX-CUTアルゴリズムは、高周長正則グラフで$ p = 2 $ QAOAよりも優れています。 Quantum、5：437、2021年10.22331月。2021/ q-04-20-437-XNUMX。
https://doi.org/10.22331/q-2021-04-20-437
【59] ピーター・L・ハマーとセルギウ・ルデアヌ。 オペレーションズリサーチおよび関連分野におけるブールメソッド。 Springer Science＆Business Media、1968年。10.1007/ 978-3-642-85823-9。
https://doi.org/10.1007/978-3-642-85823-9
【60] ジャン・B・ラサール。 0/1プログラムのMAX-CUT定式化。 オペラ。 解像度Lett。、44（2）：158 – 164、2016。10.1016 /j.orl.2015.12.014。
https：/ / doi.org/ 10.1016 / j.orl.2015.12.014
【61] パノスM.パルダロスとゲオルクシュニッガー。 制約付き二次計画法で局所最適性をチェックすることはnp困難です。 オペラ。 解像度Lett。、7（1）：33–35、1988。10.1016 / 0167-6377（88）90049-1。
https://doi.org/10.1016/0167-6377(88)90049-1
【62] キム・アレマンド、福田光明、トーマス・M・リーブリング、エリック・シュタイナー。 制約のないゼロ91二次最適化の多項式の場合。 数学。 Program。、1（49）：52–2001、10.1007。101070100233 / sXNUMX。
https：/ / doi.org/ 10.1007 / s101070100233
【63] ミラン・ハラディーク、ミハル・チャルニー、ミロスラフ・ラダ。 ボックス制約のある二次最適化問題の新しい多項式解けるクラス。 arXiv：1911.10877、2019。URL https：/ / arxiv.org/ abs /1911.10877。
arXiv：1911.10877
【64] JacekGondzioとAndreasGrothey。 超並列アーキテクチャでの$ 10 ^ 9 $決定変数を使用した非線形財務計画問題の解決。 WIT Trans Modeling Simul。、43：11、2006。10.2495 / CF060101。
https：/ / doi.org/ 10.2495 / CF060101
【65] Svatopluk Poljak、Franz Rendl、およびHenryWolkowicz。 （0、1）-二次計画法の半正定値緩和のレシピ。 J.グロブ。 Optim。、7（1）：51–73、1995。10.1007 / BF01100205。
https：/ / doi.org/ 10.1007 / BF01100205
【66] Joran Van Apeldoorn、AndrásGilyén、Sander Gribling、およびRonald deWolf。 量子SDPソルバー：より良い上限と下限。 Quantum、4：230、2020。10.22331 / q-2020-02-14-230。
https://doi.org/10.22331/q-2020-02-14-230
【67] フェルナンドGSLブランダン、アミールカレフ、トンヤンリー、セドリックイェンユーリン、クリスタM.スヴォア、シャオディウー。 量子SDPソルバー：大幅な高速化、最適性、および量子学習への応用。 Automata、Languages、and Programmingに関する第46回国際コロキウム（ICALP 2019）、Leibniz International Proceedings in Informatics（LIPIcs）の第132巻、27：1–27：14ページ、ドイツ、ダグストゥール、2019年。SchlossDagstuhl–Leibniz-Zentrumfür Informatik。 ISBN978-3-95977-109-2。 10.4230 /LIPIcs.ICALP.2019.27。
https：/ / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
【68] Nai-Hui Chia、Tongyang Li、Han-Hsuan Lin、ChunhaoWang。 低ランク半正定値計画法を解くための量子に着想を得た劣線形アルゴリズム。 コンピュータサイエンスの数学的基礎に関する第45回国際シンポジウム（MFCS 2020）、ライプニッツ国際情報会議（LIPIcs）の第170巻、23：1–23：15ページ、ドイツ、ダグストゥール、2020年。SchlossDagstuhl–Leibniz-ZentrumfürInformatik 。 ISBN978-3-95977-159-7。 10.4230 /LIPIcs.MFCS.2020.23。
https：/ / doi.org/ 10.4230 / LIPIcs.MFCS.2020.23
【69] Jacek Gondzio 切断面スキームで適用される主双対法のウォームスタート。 数学。 Program。、83（1-3）：125–143、1998。10.1007 / BF02680554。
https：/ / doi.org/ 10.1007 / BF02680554
【70] アンドリュー・ルーカス。 多くのNP問題のイジング定式化。 前面。 Phys。、2：5、2014。10.3389 /fphy.2014.00005。
https：/ / doi.org/ 10.3389 / fphy.2014.00005
【71] バスローデワイク。 np困難およびNP完全最適化問題を1911.08043次制約なしバイナリ最適化問題にマッピングします。 arXiv：2019、1911.08043。URL https：/ / arxiv.org/ abs /XNUMX。
arXiv：1911.08043
【72] ジャン・B・ラサール。 多項式とモーメント問題による大域的最適化。 SIAM J. Optim。、11（3）：796–817、2001。10.1137 / S1052623400366802。
https：/ / doi.org/ 10.1137 / S1052623400366802
【73] ジャン・B・ラサール。 スパース性を伴う多項式最適化における収束SDP緩和。 SIAM J. Optim。、17（3）：822–843、2006年。10.1137/ 05064504X。
https：/ / doi.org/ 10.1137 / 05064504X
【74] Bissan Ghaddar、Juan C. Vera、およびMiguel F.Anjos。 二次二次多項式プログラムの二次錐緩和。 SIAM J. Optim。、21（1）：391–414、2011。10.1137 / 100802190。
https：/ / doi.org/ 10.1137 / 100802190
【75] モーゼス・チャリカルとアンソニー・ワース。 二次計画法の最大化：グロタンディークの不平等の拡大。 コンピュータサイエンスの基礎に関する第45回年次IEEEシンポジウム、54〜60ページ。 IEEE、2004年。10.1109/ FOCS.2004.39。
https：/ / doi.org/ 10.1109 / FOCS.2004.39
【76] ミハイル・クレチェトフ、ヤクブ・マレチェク、ユーリー・マキシモフ、マーティン・テイキャッチ。 エントロピーペナルティ付き半正定値計画法。 人工知能に関する第2019回国際合同会議の議事録、10.24963年。2019/ ijcai.157 / XNUMX。
https：/ / doi.org/ 10.24963 / ijcai.2019 / 157
【77] サルタージ・サーニーとテオフィロ・ゴンザレス。 P-完全近似問題。 J. ACM、23（3）：555–565、1976。10.1145 /321958.321975。 補題A2を参照してください。
https：/ / doi.org/ 10.1145 / 321958.321975
【78] マイケルミッツェンマッハーとイーライアップファル。 確率とコンピューティング：アルゴリズムとデータ分析におけるランダム化と確率的手法。 ケンブリッジ大学出版局、2017年。
【79] Sepehr Abbasi-Zadeh、Nikhil Bansal、Guru Guruganesh、Aleksandar Nikolov、Roy Schwartz、およびMohitSingh。 スティッキーブラウン丸めとその制約充足問題への応用離散アルゴリズムに関する第854回ACM-SIAMシンポジウムの議事録、873〜2020ページ。 SIAM、10.1137年。1.9781611975994.52/ XNUMX。
https：/ / doi.org/ 10.1137 / 1.9781611975994.52
【80] ロネン・エルダンとアサフ・ナオル。 Krivine拡散は、goemans-williamson近似比を達成します。 arXiv：1906.10615、2019。URL https：/ / arxiv.org/ abs /1906.10615。
arXiv：1906.10615
【81] ジェイミー・モルゲンシュテルン、サミラ・サマディ、モヒット・シン、ウタイポン・タンティポンピパット、サントッシュ・ベンパラ。 SDPの公正な次元削減と反復丸め。 arXiv：1902.11281、2019。URL https：/ / arxiv.org/ abs /1902.11281v1。
arXiv：1902.11281
【82] サミュエルカーリンとハワードE.テイラー。 確率過程の1981番目のコース。 エルゼビア、257年。p。 XNUMX以降。
【83] ユリア・ケンペ、オデッド・レジェブ、ベン・トナー。 絡み合った証明者とのユニークなゲーム予想は誤りです。 計算の複雑さにおける代数的方法、2007年。
【84] ユリア・ケンペ、オデッド・レジェブ、ベン・トナー。 絡み合った証明者とのユニークなゲームは簡単です。 SIAM J. Comput。、39（7）：3207–3229、2010。10.1137 / 090772885。
https：/ / doi.org/ 10.1137 / 090772885
【85] チャールズH.ベネット、イーサンバーンスタイン、ジルブラサード、ウメシュヴァジラーニ。 量子コンピューティングの長所と短所。 SIAM J. Comput。、26（5）：1510–1523、1997. 10.1137 / S0097539796300933。
https：/ / doi.org/ 10.1137 / S0097539796300933
【86] ハリー・マーコウィッツ。 ポートフォリオの選択。 J.ファイナンス、7（1）：77–91、1952。10.2307 / 2975974。
https：/ / doi.org/ 10.2307 / 2975974
【87] H.アブラハム他Qiskit：量子コンピューティングのオープンソースフレームワーク、2019年。URLhttps：/ / doi.org/ 10.5281 /zenodo.2562111。
https：/ / doi.org/ 10.5281 / zenodo.2562111
【88] JohanHåstad。 いくつかの最適な近似不可能性の結果。 J. ACM、48（4）：798–859、2001。10.1145 /502090.502098。
https：/ / doi.org/ 10.1145 / 502090.502098
【89] Vishwanathan Akshay、Hariphan Philathong、Igor Zacharov、およびJacob D.Biamonte。 グラフ問題のグーグルの量子近似最適化、2020bに暗黙の到達可能性の欠陥。 URL https：/ / arxiv.org/ abs /2007.09148。
arXiv：2007.09148
【90] レベッカ・ヘルマン、ジェームズ・オストロフスキー、トラビス・S・ハンブル、ジョージ・シオプシス。 量子近似最適化アルゴリズムの回路深度の下限。 QuantumInf。 Process。、20（2）：59、2021年10.1007月。11128/ s021-03001-7-XNUMX。
https://doi.org/10.1007/s11128-021-03001-7
【91] Zhihui Wang、Stuart Hadfield、Zhang Jiang、EleanorG.Rieffel。 maxcutの量子近似最適化アルゴリズム：フェルミ粒子ビュー。 物理学Rev.A、97：022304、2018年10.1103月。97.022304/ PhysRevA.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevA.97.022304
【92] Leo Zhou、Sheng-Tao Wang、Soonwon Choi、Hannes Pichler、Mikhail D. Lukin。 量子近似最適化アルゴリズム: 近い将来のデバイスでのパフォーマンス、メカニズム、および実装。 物理学Rev. X、10: 021067、2020 年 10.1103 月。10.021067/ PhysRevX.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevX.10.021067
【93] ジェイソン・ラーキン、マティアス・ジョンソン、ダニエル・ジャスティス、ジャン・ジャコモ・ゲレスキ。 単一サンプルの近似比に基づく量子近似最適化アルゴリズムの評価、2020年。URLhttps：/ / arxiv.org/ abs /2006.04831。
arXiv：2006.04831
【94] qiskit-最適化。 https：/ / github.com/ Qiskit / qiskit-optimization。 アクセス：25年04月2021日。
https：/ / github.com/ Qiskit / qiskit-optimization
【95] AndreasBärtschiとStephanEidenbenz。 qaoa用のGroverミキサー：ミキサーの設計から状態の準備への複雑さのシフト。 2020年のIEEEInternational Conference on Quantum Computing and Engineering（QCE）、72〜82ページ、2020年。10.1109/ QCE49297.2020.00020。
https：/ / doi.org/ 10.1109 / QCE49297.2020.00020
【96] Reuben Tate、Majid Farhadi、Creston Herold、Greg Mohler、およびSwatiGupta。 クラシックとクォンタムをSDPでブリッジし、2020年のQAOAのウォームスタートを初期化しました。URLhttps：/ / arxiv.org/ abs /2010.14021。
arXiv：2010.14021
【97] イアン・ダンニング、スワティ・グプタ、ジョン・ジルバーホルツ。 何が最も効果的ですか？ Max-CutとQUBOのヒューリスティックの体系的な評価。 INFORMS J. Comput。、30（3）：608–624、2018。10.1287 /ijoc.2017.0798。
https：/ / doi.org/ 10.1287 / ijoc.2017.0798
【98] パナギオティスKl。 Barkoutsos、Jerome F. Gonthier、Igor Sokolov、Nikolaj Moll、Gian Salis、Andreas Fuhrer、Marc Ganzhorn、Daniel J. Egger、Matthias Troyer、AntonioMezzacapoなど。 電子構造計算のための量子アルゴリズム：粒子-穴ハミルトニアンおよび最適化された波動関数展開。 物理学Rev.A、98：022322、2018年10.1103月。98.022322/ PhysRevA.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevA.98.022322
【99] サンジーブアローラとシュムエルサフラ。 証明の確率的チェック：npの新しい特性。 J. ACM、45（1）：70–122、1998。10.1145 /273865.273901。
https：/ / doi.org/ 10.1145 / 273865.273901
【100] Sanjeev Arora、Carsten Lund、Rajeev Motwani、Madhu Sudan、およびMarioSzegedy。 証明の検証と近似問題の硬さ。 J. ACM、45（3）：501–555、1998。10.1145 /278298.278306。
https：/ / doi.org/ 10.1145 / 278298.278306
【101] IritDinur。 ギャップ増幅によるPCP定理。 J. ACM、54（3）：12–es、2007年10.1145月。1236457.1236459/ XNUMX。
https：/ / doi.org/ 10.1145 / 1236457.1236459
【102] サンジーブアローラとボアズバラク。 計算の複雑さ：最新のアプローチ。 ケンブリッジ大学出版局、2009年。
【103] スバスコート。 ユニークな2プロバー1ラウンドゲームの力について。 コンピューティング理論に関する第02回ACMシンポジウムの議事録、STOC '767、775〜2002ページ、ニューヨーク、ニューヨーク、米国、10.1145年。AssociationforComputingMachinery。 509907.510017 /XNUMX。
https：/ / doi.org/ 10.1145 / 509907.510017
【104] プラサードラガヴェンドラ。 すべてのCSPの最適なアルゴリズムと近似不可能な結果？ コンピューティング理論に関する第245回ACMシンポジウムの議事録、ページ254–2008、10.1145年。1374376.1374414/ XNUMX。
https：/ / doi.org/ 10.1145 / 1374376.1374414
【105] プラサードラガヴェンドラとデビッドステューラー。 CSPを丸める方法。 2009年に第50回コンピュータサイエンスの基礎に関するIEEEシンポジウム、ページ586–594、2009年。10.1109/ FOCS.2009.74。
https：/ / doi.org/ 10.1109 / FOCS.2009.74
【106] Subhash Khot、Dor Minzer、およびMuliSafra。 グラスマングラフの疑似乱数集合は、ほぼ完全に展開されます。 コンピュータサイエンスの基礎に関する第592回年次シンポジウム（FOCS）の議事録、ページ601–2018、10.1109年。2018.00062/ FOCS.XNUMX。
https：/ / doi.org/ 10.1109 / FOCS.2018.00062
【107] ボアズバラク、プラサードラガヴェンドラ、デビッドステューラー。 グローバル相関による半正定値計画階層の丸め。 コンピュータサイエンスの基礎に関する第472回年次シンポジウムの議事録、481〜2011ページ。 IEEE、10.1109年。2011.95/ FOCS.XNUMX。
https：/ / doi.org/ 10.1109 / FOCS.2011.95
【108] サミュエル・B・ホプキンス、ツェリル・シュラム、ルカ・トレヴィサン。 サブ指数LPは最大カットに近似します。 コンピュータサイエンスの基礎に関する第943回年次シンポジウム（FOCS）の議事録、953〜2020ページ。 IEEE、10.1109年。46700.2020.00092/ FOCSXNUMX。
https：/ / doi.org/ 10.1109 / FOCS46700.2020.00092
【109] アルバート・アインシュタイン、ボリス・ポドリスキー、ネイサン・ローゼン。 物理的現実の量子力学的記述は完全であると見なすことができますか？ 物理学Rev.、47（10）：777、1935。10.1103 /PhysRev.47.777。
https：/ / doi.org/ 10.1103 / PhysRev.47.777
【110] ボリスS.シレルソン。 ベルの不等式の量子一般化。 レット。 数学。 Phys。、4（2）：93–100、1980。10.1007 / BF00417500。
https：/ / doi.org/ 10.1007 / BF00417500
【111] A.ナタラジャンとT.ヴィディック。 量子状態の低次テスト、およびQMAの量子もつれゲームPCP。 コンピュータサイエンスの基礎に関する第731回年次シンポジウム（FOCS）の議事録、742〜2018ページ、10.1109年。2018.00075/ FOCS.XNUMX。
https：/ / doi.org/ 10.1109 / FOCS.2018.00075
【112] ドリット・アハラノフ、イタイ・アラド、ゼフ・ランドウ、ウメーシュ・ヴァジラーニ。 検出可能性の補題と量子ギャップ増幅。 コンピューティング理論に関する第09回年次ACMシンポジウムの議事録、STOC '417、ページ426–2009、ニューヨーク、ニューヨーク、米国、9781605585062年。AssociationforComputingMachinery。 ISBN10.1145。1536414.1536472/ XNUMX。
https：/ / doi.org/ 10.1145 / 1536414.1536472
【113] Moses Charikar、Konstantin Makarychev、およびYuryMakarychev。 ユニークなゲームのためのほぼ最適なアルゴリズム。 コンピューティング理論に関する第205回ACMシンポジウムの議事録、214〜2006ページ、10.1145年。1132516.1132547/ XNUMX。
https：/ / doi.org/ 10.1145 / 1132516.1132547
【114] Dimitris Achlioptas、Assaf Naor、およびYuvalPeres。 ハード最適化問題における相転移の厳密な位置。 Nature、435（7043）：759–764、2005。10.1038 / nature03602。
https：/ / doi.org/ 10.1038 / nature03602
【115] ドン・コッパースミス、デビッド・ガマルニク、モハマド・T・ハジアガイ、グレゴリー・B・ソーキン。 ランダムMAXSAT、ランダムMAX CUT、およびそれらの相転移。 ランダム構造。 Algorithms、24（4）：502–545、2004。10.1002 /rsa.20015。
https：/ / doi.org/ 10.1002 / rsa.20015
によって引用
[1] Kishor Bharti、Alba Cervera-Lierta、Thi Ha Kyaw、Tobias Haug、Sumner Alperin-Lea、Abhinav Anand、Matthias Degroote、Hermanni Heimonen、Jakob S. Kottmann、Tim Menke、Wai-Keong Mok、Sukin Sim、Leong- Chuan Kwek、およびAlánAspuru-Guzik、「ノイズの多い中規模量子（NISQ）アルゴリズム」、 arXiv：2101.08448.
[2] Austin Gilliam、Stefan Woerner、およびConstantin Gonciulea、「Grover Adaptive Search for Constrained Polynomial Binary Optimization」、 arXiv：1912.04088.
[3] Sergey Bravyi、Alexander Kliesch、Robert Koenig、およびEugene Tang、「近似グラフ彩色のためのハイブリッド量子古典アルゴリズム」、 arXiv：2011.13420.
[4] Amir M Aghaei、Bela Bauer、Kirill Shtengel、およびRyan V. Mishmash、「高度に絡み合った試行状態の効率的な行列積状態の準備：三角格子上の弱いモット絶縁体の再検討」、 arXiv：2009.12435.
[5] Stefan H.SackおよびMaksymSerbyn、「量子近似最適化アルゴリズムの量子アニーリング初期化」、 arXiv：2101.05742.
[6] M. Werninghaus、DJ Egger、およびS. Filipp、「量子ビットリセットなしの超伝導量子プロセッサの高速キャリブレーションと特性評価」、 PRX Quantum 2 2、020324（2021）.
[7] Constantin Dalyac、LoïcHenriet、Emmanuel Jeandel、Wolfgang Lechner、Simon Perdrix、Marc Porcheron、およびMargaritaVeshchezerovaは次のように述べています。 電気自動車のスマート充電の分野におけるケーススタディ」、 arXiv：2012.14859.
[8] Sami Boulebnane、「事後選択による量子近似最適化アルゴリズムの改善」、 arXiv：2011.05425.
[9] Stuart M. Harwood、Dimitar Trenev、Spencer T. Stober、Panagiotis Barkoutsos、Tanvi P. Gujarati、およびSarah Mostame、「変分断熱量子計算を使用した変分量子固有ソルバーの改善」、 arXiv：2102.02875.
[10] Johanna Barzen、「デジタルヒューマニティーズからクォンタムヒューマニティーズへ：可能性と応用」、 arXiv：2103.11825.
[11] JonathanWurtzとPeterLove、「古典的に最適な変分量子アルゴリズム」、 arXiv：2103.17065.
[12] IoannisKolotourosおよびPetrosWallden、「改良された変分量子最適化のための進化する目的関数」、 arXiv：2105.11766.
上記の引用は SAO / NASA ADS （最後に正常に更新された2021-06-17 13:56:21）。 すべての出版社が適切で完全な引用データを提供するわけではないため、リストは不完全な場合があります。
取得できませんでした クロスリファレンス被引用データ 最終試行2021-06-17 13:56:19：10.22331 / q-2021-06-17-479の被引用データをCrossrefから取得できませんでした。 DOIが最近登録された場合、これは正常です。
この論文は、 Creative Commons Attribution 4.0 International（CC BY 4.0） ライセンス。 著作権は、著者やその機関などの元の著作権者にあります。
コインスマート。 BesteBitcoin-ヨーロッパのBörse
ソース：https://quantum-journal.org/papers/q-2021-06-17-479/
