キュービット割り当て

2016年5月、IBMリサーチは一般向けにクラウドで量子プロセッサを提供しました。実際の量子デバイスをプログラムする可能性は大きな関心を呼び起こしています。しかし、量子プログラミングは依然として現代のプログラミング言語が享受するコンパイラサポートを欠いています。IBMのような汎用量子コンピュータを使用するためには、プログラマーは低レベルの回路を設計する必要があります。特に、論理キュービットを接続制約に従う必要がある物理キュービットにマッピングしなければなりません。この作業は、ソフトウェアが機械言語で構築されていた初期のプログラミングの時代に似ています。本論文では、キュービット割り当て問題を正式に紹介し、それに対する正確な解法を提供します。この最適アルゴリズムは、今日利用可能なシンプルな量子機械に対処しますが、今後登場予定のより複雑なアーキテクチャにはスケールアップできません。したがって、キュービット割り当てに対するヒューリスティックな解法も提供し、既存の解決策よりも迅速です。