イジングマシン（非制約二値変数二次最適化ソルバー）の応用事例一覧

はじめに

イジングマシンの応用に関する論文をリストアップしてみました。

イジングマシンは「二次形式の制約なし二値変数最適化」（QUBO、イジング問題とも呼ばれる）を解くマシンやアルゴリズムのことです。D-Wave Systemsの量子アニーラや富士通のデジタルアニーラ、東芝のシミュレーテッド分岐マシンなどが当てはまります。イジング問題の詳しい説明は、私の書いたイジング模型の解説記事を参照してください。この記事では、主にイジングマシンの活用事例及び問題のイジング定式化の論文についてまとめています。

※ 以下の事例について、イジングマシンの有効性は示されていません。量子アニーラを含みイジングマシンにより、通常のコンピュータよりも超高速に解けることが示された組合せ最適化問題は現在までのところありません。

レビュー論文

量子アニーラの産業応用に関するレビューとして、次の論文があります。

• S. Yarkoni, Quantum Annealing for Industry Applications: Introduction and Review, arXiv:2112.07491
  

最適化

イジングマシンの応用の最たる例が、直接的に組合せ最適化問題として定式化されている問題の近似的な最適解を見つけることです。この場合には、解きたい問題のコスト関数をイジング問題として定式化することが重要になります。

NP完全問題

イジングマシンを使って、NP完全問題もしくはNP困難問題を解くことは、数多くの論文で行われています。その中で、よく引用されるのが次の論文です。

• A. Lucas, Ising formulations of many NP problems, arXiv:1302.5843
  • このLucasの論文では、Karpの21のNP完全問題のイジング定式化の仕方がまとめられています。
  • Fixstars社の技術サイトに日本語の解説があります。

スケジュール最適化

• E. Rieffel et al., A case study in programming a quantum annealer for hard operational planning problems, arXiv:1407.2887
• D. Venturelli, Quantum Annealing Implementation of Job-Shop Scheduling, arXiv:1506.08479
  • この論文については、東北大学量子アニーリング研究開発センターT-QARDのサイトで解説がなされています。
• K. Ikeda et al., Application of Quantum Annealing to Nurse Scheduling Problem, Sci. Rep. 9, 12837 (2019)
• K. Kurowski et al., Hybrid Quantum Annealing Heuristic Method for Solving Job Shop Scheduling Problem, ICCS 2020
• F. Phillipson and I. Chiscop, Multimodal Container Planning: a QUBO Formulation and Implementation on a Quantum Annealer, arXiv:2007.01730
• S. Yarkoni et al., Multi-car paint shop optimization with quantum annealing, arXiv:2109.07876
• M. Geitz et al., Solving the Extended Job Shop Scheduling Problem with AGVs -- Classical and Quantum Approaches, arXiv:2109.04830
• J. Ossorio-Castillo and F. Pena-Brage, Optimization of a refinery scheduling process with column generation and a quantum annealer, Optimization and Engineering (2021)

配置最適化

• N. Nishimura et al., Item Listing Optimization for E-Commerce Websites Based on Diversity, Front. Comput. Sci., 16 (2019)
• S. Speziali et al., Solving Sensor Placement Problems In Real Water Distribution Networks Using Adiabatic Quantum Computation, arXiv:2108.04075

代数計算

多項式方程式

• C. Chang et al., Quantum annealing for systems of polynomial equations, Sci Rep 9, 10258 (2019)
• T. H. Chang et al, Least-squares solutions to polynomial systems of equations with quantum annealing, QIP 18, 374 (2019)

素因数分解

• R. Dridi and H. Alghassi, Prime factorization using quantum annealing and computational algebraic geometry, Sci Rep 7, 43048 (2017)
• S. Jiang et al., Quantum Annealing for Prime Factorization, Sci Rep 8, 17667 (2018)
• B. Wang et al., Prime factorization algorithm based on parameter optimization of Ising model, Sci Rep 10, 7106 (2020)

Hadamard行列探索

Blueqatの湊さんによる論文が出版されています。

• A. B. Suksmono and Y. Minato, Finding Hadamard Matrices by a Quantum Annealing Machine, Sci Rep 9, 14380 (2019)
• A. B. Suksmono and Y. Minato,　Finding high-order Hadamard matrices by using quantum computers, arXiv:2009.10919

微分方程式

• S. Srivastava, and V. Sundararaghavan, Box algorithm for the solution of differential equations on a quantum annealer, arXiv:1812.10572

機械学習

分類

クラスタリング

• K. Kurihara et al., Quantum Annealing for Clustering, arXiv:1408.2035
  • 上記のクラスタリングの論文については、著者の田中先生のスライドがslideshareに上がっています。
• V. Kumar et al., Quantum Annealing for Combinatorial Clustering, arXiv:1708.05753
• F. Neukart, Quantum-assisted cluster analysis, arXiv:1803.02886
• T. Jaschek et al., A Quantum Annealing-Based Approach to Extreme Clustering, arXiv:1903.08256
• D. Arthurand and P. Date, Balanced k-Means Clustering on an Adiabatic Quantum Computer, arXiv:2008.04419
• N. Matsumoto et al., Distance-based clustering using QUBO formulations, Sci Rep 12, 2669 (2022)

非負行列分解

• D. O'Malley et al., Nonnegative/binary matrix factorization with a D-Wave quantum annealer, arXiv:1704.01605
  • この論文は、リクルートのアドテクブログに日本語の解説があります。
• D. Ottaviani and A. Amendola, Low Rank Non-Negative Matrix Factorization with D-Wave 2000Q, arXiv:1808.08721
• J. Golden and D. O'Malley, Reverse annealing for nonnegative/binary matrix factorization, PLoS ONE 16, 1 (2021)

半教師あり学習

• Y. Zheng et al., Quantum Annealing for Semi-Supervised Learning, arXiv:2003.12459
  • ファーウェイの人によるアニーラーを使った半教師あり学習(semi-supervised Learning)の提案。QUBOを使ったクラスタリングを少し発展させて、ラベル付きのデータについては磁場のバイアスをかけることで正しいラベル付けがさせるようにしています。また単純にデータの類似度を結合パラメータ$J_{ij}$にすると、クラスタに含まれるデータ数が等しくなる作用が強く働きますが、$J_{ij}$をスパースになるように設定することで、その問題を回避しています。
• S. Yarkoni et al., Semi-supervised time series classification method for quantum computing, arXiv:2006.11031

ブースティング

• H. Neven et al., Training a Binary Classifier with the Quantum Adiabatic Algorithm, arXiv:0811.0416
  • 上の論文がQBoostアルゴリズムの提案論文です。
• H. Neven et al., Training a Large Scale Classifier with the Quantum Adiabatic Algorithm, arXiv:0912.0779
• H. Neven et al., Demonstration: Binary Classification using Hardware Implementation of Quantum Annealing, NIPS2009
• V. S. Denchev et al., Robust Classification with Adiabatic Quantum Optimization, arXiv:1205.1148
• H. Neven et al., QBoost: Large Scale Classifier Training withAdiabatic Quantum Optimization, MLR 25, 333 (2012)

サポートベクターマシン

• D. Willsch, Support vector machines on the D-Wave quantum annealer, arXiv:1906.06283
• P. Date et al., QUBO Formulations for Training Machine Learning Models, arXiv:2008.02369
• A. Dalal et al., Quantum-Assisted Support Vector Regression for Detecting Facial Landmarks, arXiv:2111.09304
  

回帰

線形回帰

• A. Borle and S. J. Lomonaco, Analyzing the Quantum Annealing Approach for Solving Linear Least Squares Problems, arXiv:1809.07649
• P. Date and T. Potok, Adiabatic Quantum Linear Regression, arXiv:2008.02355

サンプリング

制限ボルツマンマシン

• S. H. Adachi and M. P. Henderson, Application of Quantum Annealing to Training of Deep Neural Networks, arXiv:1510.06356
• T. Sato et al., Assessment of image generation by quantum annealer, Sci Rep. 11, 13523 (2021)

生成モデル

• M. Benedetti et al., Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models, arXiv:1609.02542

強化学習

• F. Neukart et al., Quantum-enhanced reinforcement learning for finite-episode games with discrete state spaces, arXiv:1708.09354

正則化

• T. Yokota et al., Derivation of QUBO formulations for sparse estimation, arXiv:2001.03715

運輸・物流

交通流最適化

• F. Neukart et al., Traffic flow optimization using a quantum annealer, arXiv:1708.01625
  • Volkswagenによる有名な論文で、北京の交通流最適化をD-Wave 2Xを使って行っています。この論文の日本語の解説は、東北大学量子アニーリング研究開発センターT-QARDのサイトにあります。
• T. Stollenwerk et al., Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management, arXiv:1711.04889
• M. Ohzeki et al., Control of automated guided vehicles without collision by quantum annealer and digital devices, arXiv:1812.01532
  • この論文はSigma-i、$J_{ij}$、DENSOによる工場内無人搬送車の運行制御最適化に関する共同研究の成果です。
• J. Clark et al., Towards Real Time Multi-robot Routing using Quantum Computing Technologies, HPC Asia 2019
• S. Yarkoni et al., Quantum Shuttle: Traffic Navigation with Quantum Computing, arXiv:2006.14162
  
• A. Singh et al., Quantum Annealing Approach for the Optimal Real-time Traffic Control using QUBO, IEEE/ACIS SNPD (2021)

信号機制御最適化

• H. Hussain et al., Optimal Control of Traffic Signals using Quantum Annealing, arXiv:1912.07134
• D. Inoue et al., Traffic Signal Optimization on a Square Lattice using the D-Wave Quantum Annealer, arXiv:2003.07527
  • 上記の論文は、イジングマシンの活用を目指すベンチャー企業$J_{ij}$のテックブログで詳しい解説がなされています。

経路最適化

• S. Feld et al., A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer, arXiv:1811.07403
• M. Borowski et al., New Hybrid Quantum Annealing Algorithms for Solving Vehicle Routing Problem, ICCS 2020
• R. Harikrishnakumar et al., A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem, arXiv:2005.12478
  
• Y. Mukasa et al., Visiting-Route Recommendation in Amusement Parks and its Evaluations by an Ising Machine, ICCE 2021
• S. Yu and T. Nabil, Applying the Hubbard-Stratonovich Transformation to Solve Scheduling Problems Under Inequality Constraints With Quantum Annealing, Front. Phys., 14 (2021)
• O. Salehi et al., Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization, arXiv:2106.09056

金融工学

ポートフォリオ最適化

• G. Rosenberg et al., Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer, arXiv:1508.06182
• D. Venturelli and A. Kondratyev, Reverse Quantum Annealing Approach to Portfolio Optimization Problems, arXiv:1810.08584
• S. Mugel et al., Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks, arXiv:2007.00017
  
• J. Cohen, A. Khan, C. Alexander, Portfolio Optimization of 40 Stocks Using DWaves Quantum Annealer, arXiv:2007.01430
• E. Grant, T. Humble, B. Stump, Benchmarking Quantum Annealing Controls with Portfolio Optimization, arXiv:2007.03005
• J. Cohen, A. Khan, C. Alexander, Portfolio Optimization of 60 Stocks Using Classical and Quantum Algorithms, arXiv:2008.08669
• K. Steinhauer et al., Solving the Optimal Trading Trajectory Problem Using Simulated Bifurcation, arXiv:2009.08412
• F. Phillipson and H. Bhatia, Portfolio Optimisation Using the D-Wave Quantum Annealer, arXiv:2012.01121

アセットアロケーション

• S. Dasgupta, A. Banerjee, Quantum Annealing Algorithm for Expected Shortfall based Dynamic Asset Allocation, arXiv:1909.12904
• H. Xu et al., Dynamic Asset Allocation via Quantum Annealing, arXiv:2112.03188

リスクパリティ最適化

• G. Rosenberg and M. Rounds, Long-Short Minimum Risk Parity Optimization Using a Quantum or Digital Annealer, 1QBit-White-Paper

スコアリングの特徴量抽出

• A. Milne et al., Optimal Feature Selection in Credit Scoring and Classification Using a Quantum Annealer, 1QBit-White-Paper

金融危機予測

• R. Orus et al., Forecasting financial crashes with quantum computing, arXiv:1810.07690
• Y. Ding et al., Towards Prediction of Financial Crashes with a D-Wave Quantum Computer, arXiv:1904.05808

為替裁定取引計算

• G. Rosenberg, Finding optimal arbitrage opportunities using a quantum annealer. 1QBit-White-Paper
• K. Tatsumura et al., A Currency Arbitrage Machine Based on the Simulated Bifurcation Algorithm for Ultrafast Detection of Optimal Opportunity, 2020 IEEE International Symposium on Circuits and Systems

物質科学

タンパク質構造計算

• A. Perdomo-Ortiz et al., Finding low-energy conformations of lattice protein models by quantum annealing, arXiv:1204.5485
• T. Babej et al., Coarse-grained lattice protein folding on a quantum annealer, arXiv:1811.00713
• V. Mulligan et al., Designing Peptides on a Quantum Computer, bioRxiv:752485

ポリマー構造計算

• C. Micheletti et al., Polymer Physics by Quantum Computing, arXiv:2104.10102

量子化学計算

• R. Babbush et al., Adiabatic Quantum Simulation of Quantum Chemistry, arXiv:1311.3967
• R. Xia et al., Electronic Structure Calculations and the Ising Hamiltonian, arXiv:1706.00271
• M. Streif et al., Solving Quantum Chemistry Problems with a D-Wave Quantum Annealer, arXiv:1811.05256
• A. Teplukhin et al., Calculation of molecular vibrational spectra on a quantum annealer, arXiv:1812.05211
• S. N. Genin et al., Quantum chemistry on quantum annealers, arXiv:1901.04715

異性体探索

• J. P. Terry et al., Quantum Isomer Search, arXiv:1908.00542

コンピュータビジョン

物体追跡

• J. Zaech et al., Adiabatic Quantum Computing for Multi Object Tracking, arXiv:2202.08837
  

音声処理

作曲

• A. Arya et al., Music Composition Using Quantum Annealing, arXiv:2201.10557

むすび

網羅的なページを目指しているので、抜けている論文等があったら教えてください。