論文の概要: A SAT Encoding for Optimal Clifford Circuit Synthesis
- arxiv url: http://arxiv.org/abs/2208.11713v1
- Date: Wed, 24 Aug 2022 18:00:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-29 23:49:43.282764
- Title: A SAT Encoding for Optimal Clifford Circuit Synthesis
- Title(参考訳): 最適クリフォード回路合成のためのSAT符号化
- Authors: Sarah Schneider, Lukas Burgholzer, Robert Wille
- Abstract要約: 量子回路の重要なサブクラスであるクリフォード回路の最適合成を考える。
本稿では,タスクを満足度問題として符号化したクリフォード回路の最適合成法を提案する。
得られたツールは、最大26ドルキュービットの最適回路を合成する。
- 参考スコア(独自算出の注目度): 3.610459670994051
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Executing quantum algorithms on a quantum computer requires compilation to
representations that conform to all restrictions imposed by the device. Due to
device's limited coherence times and gate fidelities, the compilation process
has to be optimized as much as possible. To this end, an algorithm's
description first has to be synthesized using the device's gate library. In
this paper, we consider the optimal synthesis of Clifford circuits -- an
important subclass of quantum circuits, with various applications. Such
techniques are essential to establish lower bounds for (heuristic) synthesis
methods and gauging their performance. Due to the huge search space, existing
optimal techniques are limited to a maximum of six qubits. The contribution of
this work is twofold: First, we propose an optimal synthesis method for
Clifford circuits based on encoding the task as a satisfiability (SAT) problem
and solving it using a SAT solver in conjunction with a binary search scheme.
The resulting tool is demonstrated to synthesize optimal circuits for up to
$26$ qubits -- more than four times as many as the current state of the art.
Second, we experimentally show that the overhead introduced by state-of-the-art
heuristics exceeds the lower bound by $27\%$ on average. The resulting tool is
publicly available at https://github.com/cda-tum/qmap.
- Abstract(参考訳): 量子コンピュータ上で量子アルゴリズムを実行するには、デバイスが課す全ての制限に適合する表現へのコンパイルが必要である。
デバイスのコヒーレンス時間とゲートフィディリティが限られているため、コンパイルプロセスは可能な限り最適化する必要がある。
この目的のために、まずアルゴリズムの記述をデバイスのゲートライブラリを使って合成する必要がある。
In this paper, we consider the optimal synthesis of Clifford circuits -- an important subclass of quantum circuits, with various applications. Such techniques are essential to establish lower bounds for (heuristic) synthesis methods and gauging their performance. Due to the huge search space, existing optimal techniques are limited to a maximum of six qubits. The contribution of this work is twofold: First, we propose an optimal synthesis method for Clifford circuits based on encoding the task as a satisfiability (SAT) problem and solving it using a SAT solver in conjunction with a binary search scheme. The resulting tool is demonstrated to synthesize optimal circuits for up to $26$ qubits -- more than four times as many as the current state of the art.
第2に,最先端のヒューリスティックスが導入するオーバーヘッドが平均で下限を27%下回ることを実験的に示した。
ツールはhttps://github.com/cda-tum/qmapで公開されている。
関連論文リスト
- Compilation for Surface Code Quantum Computers [8.093450284837559]
表面符号を実装した量子コンピュータにおける量子回路のコンパイル問題について検討する。
問題となるのは、(1)回路キュービットをデバイスキュービットにマッピングし、(2)相互作用するキュービットのペア間で実行経路をルーティングすることである。
例えば,ノード不連続経路の問題を解くために,グリーディアルゴリズムを利用してSCMRを効率的に緩和する手法を提案する。
論文 参考訳(メタデータ) (2023-11-29T19:36:19Z) - Improving Quantum Circuit Synthesis with Machine Learning [0.7894596908025954]
機械学習をユニタリデータセットに適用することで、合成アルゴリズムの大幅な高速化が可能になることを示す。
本稿では,学習モデルを用いたシード合成アルゴリズムQSeedについて述べる。
論文 参考訳(メタデータ) (2023-06-09T01:53:56Z) - Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers [4.208975913508643]
最適合成は、量子および古典的ハードウェア設計において中心的な問題である。
エンタングリング入力刺激と安定化ホルマリズムを用いて、クリフォード合成問題をポリサイズ満足度問題の族に還元する。
実験的な評価により、最適合成手法は、ランダムなクリフォード回路とグロバー探索のためのクリフォード+T回路に対して実質的な深さ改善をもたらすことが示された。
論文 参考訳(メタデータ) (2023-05-02T18:00:00Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳(メタデータ) (2022-01-06T21:02:30Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - QFAST: Conflating Search and Numerical Optimization for Scalable Quantum
Circuit Synthesis [5.406226763868874]
本稿では,短絡回路を創出し,実際によくスケールするように設計された量子合成アルゴリズムを提案する。
主な貢献は、一般的な「ゲート」を用いて配置と位相をエンコードできる回路の新たな表現である。
最適深度、検索に基づく最先端技術と比較すると、QFASTは同等の結果が得られる。
論文 参考訳(メタデータ) (2021-03-12T05:20:12Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳(メタデータ) (2020-06-21T15:32:21Z) - QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space [5.406226763868874]
短絡回路を製造するために設計された量子合成ツールQFASTを提案する。
最適なサードパーティ合成アルゴリズムを与えられた階層レベルでプラグインすることで、より短い回路を生成する方法を示す。
論文 参考訳(メタデータ) (2020-03-09T23:55:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。