論文の概要: 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回路の大幅な深さ改善をもたらすことが示された。
関連論文リスト
- 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) - Iterative Qubit Coupled Cluster using only Clifford circuits [52.77024349608834]
クリフォード回路のみを用いる反復量子結合クラスタ (iQCC) の変種に着目した。
この方法は、優れた初期パラメータを生成するため、短期変動量子アルゴリズムの応用に有用である。
NISQ時代を超えて、短い深さのクリフォード事前最適化回路を作るのにも有用かもしれない。
論文 参考訳(メタデータ) (2022-11-18T20:31:10Z) - 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) - Towards a SAT Encoding for Quantum Circuits: A Journey From Classical
Circuits to Clifford Circuits and Beyond [3.610459670994051]
任意の量子回路に適用可能な命題SAT符号化を提案する。
量子状態を表現することの本質的な複雑さのため、そのようなエンコーディングを構築することは一般には不可能である。
提案手法がClifford回路のクラスにどのように適用できるかを明確に示す。
論文 参考訳(メタデータ) (2022-03-01T19:00:02Z) - 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) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z) - QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space [5.406226763868874]
短絡回路を製造するために設計された量子合成ツールQFASTを提案する。
最適なサードパーティ合成アルゴリズムを与えられた階層レベルでプラグインすることで、より短い回路を生成する方法を示す。
論文 参考訳(メタデータ) (2020-03-09T23:55:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。