@techreport{oai:ipsj.ixsq.nii.ac.jp:00226758,
 author = {中山, 昌勲 and 鈴木, 泰成 and 徳永, 裕己},
 issue = {18},
 month = {Jun},
 note = {将来的に実現が見込まれている Fault-Tolerant Quantum Computing (FTQC) は，理論的には古典コンピュータを凌駕する計算能力を持つとされており，広範な社会的応用が期待されている．FTQC は製造やメンテナンスが困難と予想されるため，提供の形態はクラウドサービスとなると見られている．この時，ユーザがサービスを通じて投入するジョブをできる限り高い効率で処理するためには，最適化されたスケジューリング手法が必要となる．しかし，これまでの提案手法は主に誤り訂正を用いない NISQ (Noisy Intermediate-Scale Quantum) 計算機を対象としたものであり，FTQC に適用可能なスケジューリングアルゴリズムは提案されていなかった．本研究では，マルチプログラミングに基づく新たなジョブスケジューラを提案する．具体的には，ジョブが必要とするリソース量を元にジョブを 3 次元ブロックへ変換し，ブロックの最適な配置に関する整数計画問題を解くことで，最適なスケジューリングを達成する．数値計算を用いて提案手法の性能を評価し，我々の手法は高い性能を発揮することが分かった．具体的には，我々がベンチマークした設定において，我々の手法はマルチプログラミングを用いないスケジューリングに比べて 10 倍以上の高速化を実現し，貪欲法による最適化と比較して，単位時間に処理できるジョブの処理量は最大 1.7 倍となった．, Fault-Tolerant Quantum Computing (FTQC) is theoretically expected to enable the computational capabilities that surpass those of classical computers and is thereby expected to be applied to wide-ranging application fields. Since FTQC is built based on complicated manufacturing and maintenance, FTQC is likely to be mainly delivered as cloud-based services. To maximize the service capabilities such as a job throughput, scheduling optimization methods are required. However, the existing proposals focus on noisy-intermediate scale (NISQ) quantum computing, and there are no algorithms for FTQC cloud services. In this paper, we introduce a novel job scheduling approach for FTQC based on multi-programming. We optimized job scheduling by converting the problems into instances of packing problems and solved them with integer-programming solvers. For conversion, jobs are represented as three-dimensional blocks according to their time and spatial resource usage, and the scheduling problems can be converted to packing problems, which can be solved by an integer programming solver. We numerically evaluated the proposed methods and compared them with baseline implementations. The results indicate that our methods will significantly improve the job processing capacity per unit time. In our benchmark settings, we achieved about ten times larger throughput compared to sequential optimization and 1.7 times larger throughput to the optimization by greedy optimization algorithms.},
 title = {マルチプログラミングによるFTQCのスループット向上},
 year = {2023}
}