論文の概要: Clifford synthesis is NP-complete

• arxiv url: http://arxiv.org/abs/2610.40886v1
• Date: Thu, 29 Oct 2026 19:06:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 22:05:31.476014
• Title: Clifford synthesis is NP-complete
• Title（参考訳）: クリフォード合成はNP完全である
• Abstract要約: 所与のクリフォード演算子に対して、少なくとも指定された量の資源を用いて量子回路を合成する問題はNP完全であることを示す。 単一キュービットゲートをフリーにし、CNOTを唯一の2キュービットゲートとし、与えられたターゲットが少なくとも指定された数のCNOTゲートを用いて実装を許可するかどうかを決定することはNP完全であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.
• Abstract（参考訳）: 与えられたクリフォード演算子に対して、少なくとも指定されたリソース量を用いて量子回路を合成する問題は、実用的関心を持つ複数のリソースモデルに対してNP完全であることを示す。 具体的には,1量子クリフォードゲートと2量子クリフォードゲートを用いて,与えられたクリフォード作用素の合成について検討する。 単一キュービットゲートをフリーにし、CNOTを唯一の2キュービットゲートとし、与えられたターゲットが少なくとも1つの特定の数のCNOTゲートを使用する実装を許容するかどうかを決定するNP完全であることを示し、この問題が2キュービットクリフォードゲートを許可し、予算がこれらすべてのゲートをカウントした場合にNP完全であることを示す。 さらに,SWAPゲートを無料で挿入した場合と,単一ビットゲートを予算の一部と見なす場合とでは,どちらの結果も維持され続けることを示す。 いずれの場合も、Li と Guan の最近の研究に基づいて、格子グラフのハミルトン経路からこれらの決定問題への多項式時間還元が存在することを示す。

関連論文リスト

• Link-middle-cut lower bounds for Clifford circuit synthesis [0.0]
  クリフォード作用素を合成するために必要なCNOTゲートの数を最小化することは、量子回路最適化における中心的な問題である。 線形回路のためのリンク・ミドルカット(LMC)フレームワークを、二進シンプレクティック・テーブルローで表されるクリフォード作用素に拡張する。
  論文  参考訳（メタデータ） (2026-09-14T18:42:19Z)
• A Complete Equational Theory for Real-Clifford+CH Quantum Circuits [51.56484100374058]
  この断片の回路間の等価性の簡単な集合を与え、他の真の方程式がこれらから導出できることを証明する。 これは有限生成された量子回路の普遍的な断片に対する最初の完全性の結果であり、パラメータ化されたゲートはなく、アシラも不要である。
  論文  参考訳（メタデータ） (2026-02-06T12:11:39Z)
• Optimal constant-cost implementations of Clifford operations using global interactions [0.0]
  任意の単一量子ビット演算とプログラム可能な全量子ビットエンタングゲートを組み合わせた量子回路について検討する。 本研究は,これらのコンパイルを実現するための実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-10-23T16:45:59Z)
• Reduced constant-cost implementations of Clifford operations using global interactions [0.0]
  アンシラを伴わない任意の長さのクリフォード演算列を実現するために、そのようなクリフォードエンタングリング多ビットゲートの6つの応用を一定コストで報告する。 任意の長さのCNOTゲートの任意の列は、アンシラなしで、そのような多重ビットゲートを絡むクリフォードの5つの応用に置き換えることができることを示す。
  論文  参考訳（メタデータ） (2025-10-15T17:10:45Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT回路は一般的な量子回路の共通構成ブロックである。 本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。 シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
  論文  参考訳（メタデータ） (2024-08-07T19:51:22Z)
• One Gate Scheme to Rule Them All: Introducing a Complex Yet Reduced Instruction Set for Quantum Computing [17.731117502015355]
  $XX+YY$結合を持つキュービットのスキームは、単一キュービットゲートまでの任意の2キュービットゲートを実現する。 一般的な$n$-qubitゲート合成、量子ボリューム、キュービットルーティングなど、様々な応用において顕著な改善が見られた。
  論文  参考訳（メタデータ） (2023-12-09T19:30:31Z)
• Optimising quantum circuits is generally hard [0.0]
  約普遍量子回路に対する多くのゲート最適化問題はNPハードであることが判明した。 クリフォードゲートの任意の$G$に対して、クリフォード+$G$ゲート集合上の$G$カウントを最適化するのはNPハードであることを示す。
  論文  参考訳（メタデータ） (2023-09-12T09:35:23Z)
• Software mitigation of coherent two-qubit gate errors [55.878249096379804]
  2量子ゲートは量子コンピューティングの重要な構成要素である。 しかし、量子ビット間の不要な相互作用(いわゆる寄生ゲート)は、量子アプリケーションの性能を低下させる。 寄生性2ビットゲート誤差を軽減するための2つのソフトウェア手法を提案する。
  論文  参考訳（メタデータ） (2021-11-08T17:37:27Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。 CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。 以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
  論文  参考訳（メタデータ） (2021-08-10T15:00:20Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。 本稿では,QAOAの回路深度依存性能について実験的に検討する。 この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
  論文  参考訳（メタデータ） (2020-05-11T17:20:51Z)
• Optimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation [0.0]
  クリフォード+CSゲートセット上の2量子回路について検討する。 2量子Clifford+CS演算子に対する効率的かつ最適な合成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-16T18:55:38Z)

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

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