論文の概要: (A Variant of) Clifford Circuit Synthesis is NP-Complete

• arxiv url: http://arxiv.org/abs/2610.02029v1
• Date: Thu, 01 Oct 2026 16:47:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.308205
• Title: (A Variant of) Clifford Circuit Synthesis is NP-Complete
• Title（参考訳）: (変種)クリフォード回路合成はNP-コンプリートである
• Abstract要約: 最適回路合成は、量子回路設計と古典回路設計の両方において問題となる。 Clifford回路合成には様々な機能がある。 最適クリフォード合成の変種はNPハードである。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.
• Abstract（参考訳）: 最適回路合成は、指定された基本ゲートセットに対して、与えられた機能の最短深度回路表現を求める問題である。 これは量子設計と古典的ハードウェア設計の両方において中心的な問題である。 古典的なバージョンは、ヒューリスティックスと厳密な硬さのアサーションの両方の観点から非常によく理解されているが、最適量子回路合成についてはあまり知られていない。 本稿では,様々なヒューリスティックが知られているクリフォード回路の最適合成,例えば3SATへの還元に着目する。 最適クリフォード合成の変種はNPハードである。 証明は2つの部分に分かれる。 (i)CZゲートのみを含む回路合成問題に3つの正則グラフ上の3辺色度を減少させる。 (II) 追加の基本クリフォードゲート(特にアダマール、位相、CNOT)が利用可能であることは、最適回路深さをさらに改善することができないことを証明する。 我々の研究はクリフォード回路の複雑性理論的理解を強化し、シミュレーションと等価チェックはPにあるが、クリフォードユニタリが所定の深さで実装を許すか否かはNP完全である。

関連論文リスト

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。 浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
  論文  参考訳（メタデータ） (2026-09-01T15:54:34Z)
• AlphaClifford: Efficient Clifford Synthesis and Transpilation with Model-based RL [2.018550249418405]
  我々はモンテカルロ木探索を利用したモデルベースの強化学習フレームワークであるAlphaCliffordを紹介する。 シンプレクティック群の代数的性質を通して状態空間をモデル化することにより、AlphaCliffordはこの空間を効果的に探求し、全体的な回路コストを最小化する。 ハードウェア制約のCliffordトランスパイレーションと,完全なClifford+T論理パイプライン内での合成後最適化コンポーネントである。
  論文  参考訳（メタデータ） (2026-08-19T14:13:26Z)
• Clifford and Non-Clifford Splitting in Quantum Circuits: Applications and ZX-Calculus Detection Procedure [49.1574468325115]
  我々は、クリフォードと非クリフォードのユニタリの間の積として記述できる量子回路から得られるユースケースを提案し、分析する。 ZX-カルキュラスとその資産を用いてこれらの回路の限界境界を検出し、クリフォード切断と非クリフォード切断の分離を可能にする。
  論文  参考訳（メタデータ） (2025-04-22T16:10:34Z)
• Heuristic and Optimal Synthesis of CNOT and Clifford Circuits [3.1952340441132474]
  CNOTゲートからなる回路に相当する線形可逆回路は、古典計算において重要な応用である。 CNOTと一般クリフォード回路合成の手法として,絡み合う2ビットゲート数や回路深さを最小化する手法を提案する。 アルゴリズムは、古典的および量子コンピューティングコミュニティが使用するGitHubリポジトリに実装されている。
  論文  参考訳（メタデータ） (2025-03-18T19:09:58Z)
• Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers [4.208975913508643]
  最適合成は、量子および古典的ハードウェア設計において中心的な問題である。 エンタングリング入力刺激と安定化ホルマリズムを用いて、クリフォード合成問題をポリサイズ満足度問題の族に還元する。 実験的な評価により、最適合成手法は、ランダムなクリフォード回路とグロバー探索のためのクリフォード+T回路に対して実質的な深さ改善をもたらすことが示された。
  論文  参考訳（メタデータ） (2023-05-02T18:00:00Z)
• Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
  古典的に容易に生成できる理想的な状態準備プロトコルを特徴付けることができる。 繰り返し量子ビット結合クラスタ(iQCC)の変種を導入して,これらの要件を満たす手法を提案する。 本研究では, チタン系化合物Ti(C5H5)(CH3)3と (20, 20) 活性空間の複雑な系に研究を拡張した。
  論文  参考訳（メタデータ） (2022-11-18T20:31:10Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。