論文の概要: Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers
- arxiv url: http://arxiv.org/abs/2305.01674v2
- Date: Fri, 2 Jun 2023 13:50:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-05 19:30:32.204412
- Title: Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers
- Title（参考訳）: SATソルバーを用いたクリフォード回路の深さ最適合成
- Authors: Tom Peham, Nina Brandl, Richard Kueng, Robert Wille and Lukas
Burgholzer
- Abstract要約: 最適合成は、量子および古典的ハードウェア設計において中心的な問題である。
エンタングリング入力刺激と安定化ホルマリズムを用いて、クリフォード合成問題をポリサイズ満足度問題の族に還元する。
実験的な評価により、最適合成手法は、ランダムなクリフォード回路とグロバー探索のためのクリフォード+T回路に対して実質的な深さ改善をもたらすことが示された。
- 参考スコア（独自算出の注目度）: 4.208975913508643
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Circuit synthesis is the task of decomposing a given logical functionality
into a sequence of elementary gates. It is (depth-)optimal if it is impossible
to achieve the desired functionality with even shorter circuits. Optimal
synthesis is a central problem in both quantum and classical hardware design,
but also plagued by complexity-theoretic obstacles. Motivated by fault-tolerant
quantum computation, we consider the special case of synthesizing blocks of
Clifford unitaries. Leveraging entangling input stimuli and the stabilizer
formalism allows us to reduce the Clifford synthesis problem to a family of
poly-size satisfiability (SAT) problems -- one for each target circuit depth.
On a conceptual level, our result showcases that the Clifford synthesis problem
is contained in the first level of the polynomial hierarchy ($\mathsf{NP}$),
while the classical synthesis problem for logical circuits is known to be
complete for the second level of the polynomial hierarchy
($\Sigma_2^{\mathsf{P}}$). Based on this theoretical reduction, we formulate a
SAT encoding for depth-optimal Clifford synthesis. We then employ SAT solvers
to determine a satisfying assignment or to prove that no such assignment
exists. From that, the shortest depth for which synthesis is still possible
(optimality) as well as the actual circuit (synthesis) can be obtained.
Empirical evaluations show that the optimal synthesis approach yields a
substantial depth improvement for random Clifford circuits and Clifford+T
circuits for Grover search.
- Abstract（参考訳）: 回路合成は、与えられた論理機能を基本ゲートの列に分解するタスクである。
さらに短い回路で所望の機能を達成することが不可能であれば(深く)最適である。
最適合成は量子および古典的ハードウェア設計において中心的な問題であるが、複雑性理論上の障害にも悩まされている。
フォールトトレラントな量子計算に動機づけられ、クリフォードユニタリのブロックを合成する特別な場合を考える。
入力刺激の絡み合いと安定化形式を利用することで、クリフォード合成問題を、対象回路の深さごとに1つずつのポリサイズ満足度(sat)問題に還元することができる。
概念レベルでは、クリフォード合成問題は多項式階層の第1レベル($Sigma_2^{\mathsf{P}}$)に含まれるが、論理回路の古典的合成問題は多項式階層の第2レベル($Sigma_2^{\mathsf{P}}$)に対して完備であることが知られている。
この理論的な還元に基づき、深さ最適クリフォード合成のためのsat符号化を定式化する。
次にSATソルバを用いて満足な代入を決定するか、そのような代入が存在しないことを証明する。
これにより、合成が可能な最短深度(最適)と実際の回路(合成)が得られる。
経験的評価により、最適合成手法はランダムクリフォード回路とグローバー探索のためのclifford+t回路の大幅な深さ改善をもたらすことが示された。
関連論文リスト
- QuCLEAR: Clifford Extraction and Absorption for Significant Reduction in Quantum Circuit Size [8.043057448895343]
現在利用可能な量子デバイスは、実行された量子回路の忠実さを低下させるノイズの多い量子ゲートに悩まされている。
本稿では,量子回路の最適化を目的としたコンパイルフレームワークQuCLEARを提案する。
論文 参考訳（メタデータ） (2024-08-23T18:03:57Z) - Unitary Synthesis of Clifford+T Circuits with Reinforcement Learning [2.4646794072984477]
ユニタリ合成は、与えられたユニタリを表す量子回路を特定することを目的としている。
木探索法 Gumbel AlphaZero を用いて、正確に合成可能な Clifford+T ユニタリの部分集合の問題を解く。
提案手法は,最大60ゲートのランダム化回路から生成した最大5キュービットの回路を効果的に合成する。
論文 参考訳（メタデータ） (2024-04-23T09:37:52Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - A graph-state based synthesis framework for Clifford isometries [0.0]
我々はクリフォードアイソメトリを実行可能な量子回路に合成する問題に取り組む。
クリフォード群の基本的な性質とシンプレクティック群の1つの方程式を利用する単純な合成フレームワークを提案する。
LNNアーキテクチャ上でのクリフォード回路の実行に必要な2ビット深さの改善について報告する。
論文 参考訳（メタデータ） (2022-12-13T22:50:24Z) - A SAT Encoding for Optimal Clifford Circuit Synthesis [3.610459670994051]
量子回路の重要なサブクラスであるクリフォード回路の最適合成を考える。
本稿では,タスクを満足度問題として符号化したクリフォード回路の最適合成法を提案する。
得られたツールは、最大26ドルキュービットの最適回路を合成する。
論文 参考訳（メタデータ） (2022-08-24T18:00:03Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Symbolic Synthesis of Clifford Circuits and Beyond [0.0]
ユニタリ性問題は一般にコ-NP-ハードであるが、クリフォードパス和に制限された場合、P であることを示す。
次に、一意的なクリフォード経路和からクリフォード回路を合成するアルゴリズムを提供する。
また、任意の経路和に対する抽出アルゴリズムの一般化も提供する。
論文 参考訳（メタデータ） (2022-04-29T16:33:42Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
論文 参考訳（メタデータ） (2021-08-10T15:00:20Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Transformer-based Machine Learning for Fast SAT Solvers and Logic
Synthesis [63.53283025435107]
CNFベースのSATとMaxSATは論理合成と検証システムの中心である。
そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
論文 参考訳（メタデータ） (2021-07-15T04:47:35Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。