論文の概要: Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?
- arxiv url: http://arxiv.org/abs/2609.35239v1
- Date: Mon, 28 Sep 2026 14:13:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-02 07:17:44.102461
- Title: Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?
- Title（参考訳）: クリフォードテンプレートコンパイルの計算複雑性:量子コンピュータは量子回路のコンパイルに有効か?
- Abstract要約: クリフォードテンプレート(Clifford template)は、クリフォード演算の有限順序族である。
コンパイル問題は、テンプレートがパウリ作用素のターゲット変換を実現するために繰り返し数を選択する方法を求める。
自己逆クリフォード作用の可換化では、二項実現可能性と1つの解の回復は古典的に時間分解可能であるが、全反復数に対する有界はNP完全である。
- 参考スコア（独自算出の注目度）: 3.9083778058145864
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied. The Clifford template compilation problem asks how to choose these repetition numbers so that the template realizes a target transformation of Pauli operators. This problem arises, for example, when searching for logical operations in quantum error correction using only Clifford operations permitted by physical or fault-tolerance constraints. Although forward Clifford dynamics is efficiently classically simulable, this inverse problem has sharp complexity transitions. For commuting templates with unrestricted integer exponents, feasibility lies in $\mathrm{NP}\cap\mathrm{BQP}$ and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at $k=1$, recovering the repetition number contains finite-field discrete logarithm over $\mathbb{F}_{2^r}^{\times}$. In general, restricting every exponent to $\{0,1\}$ removes the Abelian-group closure and makes feasibility NP-complete for variable $k$, even for exactly commuting CNOT-only operations and X-type Paulis. For commuting self-inverse Clifford actions, both binary feasibility and recovery of one solution are classically polynomial-time solvable, but imposing a bound on the total repetition count is NP-complete, even for CNOT-only operations. These results reveal a rich complexity landscape within Clifford template compilation, spanning classically tractable cases, problems admitting quantum polynomial-time algorithms, and NP-complete variants.
- Abstract（参考訳）: クリフォードテンプレートは繰り返し可能なクリフォード演算の有限順序族であり、インスタンス化は各演算が適用された回数を特定する。
クリフォードテンプレートコンパイル問題は、テンプレートがパウリ作用素のターゲット変換を実現するために、これらの繰り返し数をどのように選択するかを問う。
この問題は例えば、物理やフォールトトレランスの制約によって許されるクリフォード演算のみを用いて量子エラー補正における論理演算を探索する際に発生する。
フォワードクリフォード力学は効率よく古典的にシミュレートできるが、この逆問題には急激な複雑性遷移がある。
制限のない整数指数を持つ可換テンプレートに対して、実現可能性(英語版)は$\mathrm{NP}\cap\mathrm{BQP}$にあり、構成的量子アルゴリズムは完全な指数関係格子と共に特定の解を返す。
一般に、すべての指数を$\{0,1\}$に制限すると、アベリア群閉包が取り除かれ、変数 $k$ に対して実現可能な NP-完全 が成立する。
自己逆クリフォード作用の可換化では、二項実現可能性と1つの解の回復は古典的には多項式時間可解であるが、CNOT のみの操作であっても、全反復数に対する境界は NP 完全である。
これらの結果はクリフォードテンプレートのコンパイルにおいて、古典的に抽出可能なケース、量子多項式時間アルゴリズムを許容する問題、NP完全変種にまたがるリッチな複雑さの景観を明らかにしている。
関連論文リスト
- Efficient learning of Clifford disentanglers and typical $t$-doped unitaries with exponentially more $T$ gates [0.0]
未知の純状態ベクトルに隠れたテンソル積構造を検証・復元するための効率的なアルゴリズムを提供する。
我々のフレームワークはまた、構造化多体ハミルトン多様体を圧縮するためのツールも提供する。
論文 参考訳（メタデータ） (2026-09-23T08:48:39Z) - Clifford Circuit Synthesis for Distributed Quantum Architectures with Arbitrary Network Topology [0.0]
O(nk)インターブロックCNOTとブロック内パウリ測定を用いて、kブロックにn個の論理量子ビットを符号化したCSSコードにCNOT回路を実装する方法を示す。
論文 参考訳（メタデータ） (2026-08-13T17:55:40Z) - From Hilbert's Tenth Problem to Quantum Speedup: Explicit Oracles for Bounded Diophantine Systems [0.0]
我々は、有界整数領域上のディオファント方程式を解くために、完全に可逆的なアルゴリズムフレームワークを導入する。
抽象ブラックボックスの仮定を超えて、この明示的なアーキテクチャ合成は、必要な量子演算が有界なオーバーヘッドとして働くことを保証している。
論文 参考訳（メタデータ） (2026-05-13T18:01:01Z) - Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
計算問題はすべて、解を返却する厳密な明示的な方程式を持つことを示す。
本稿では, インバージョン, 制約満足度, 最適化の両面から, 正確に任意の問題を解く方程式を得る方法を提案する。
論文 参考訳（メタデータ） (2025-02-09T18:16:53Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
古典的に容易に生成できる理想的な状態準備プロトコルを特徴付けることができる。
繰り返し量子ビット結合クラスタ(iQCC)の変種を導入して,これらの要件を満たす手法を提案する。
本研究では, チタン系化合物Ti(C5H5)(CH3)3と (20, 20) 活性空間の複雑な系に研究を拡張した。
論文 参考訳（メタデータ） (2022-11-18T20:31:10Z) - The Parameterized Complexity of Quantum Verification [7.7155343772895275]
量子回路の整合性の問題に対して,非クリフォードゲート数で指数関数的にスケーリングすることで問題を解くアルゴリズムが存在することを示す。
我々は、サーキット適合性のインスタンスの$T$-countと$W$-stateの$$$-countに新しい下位境界を導出する。
論文 参考訳（メタデータ） (2022-02-16T14:53:42Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
論文 参考訳（メタデータ） (2021-08-10T15:00:20Z) - Hadamard-free circuits expose the structure of the Clifford group [9.480212602202517]
クリフォード群は量子ランダム化ベンチマーク、量子トモグラフィ、誤り訂正プロトコルにおいて中心的な役割を果たす。
任意のクリフォード作用素が標準形式$F_HSF$で一意に書けることを示す。
ランダムな一様クリフォード作用素と対称群上のマロース分布の間の驚くべき接続が強調される。
論文 参考訳（メタデータ） (2020-03-20T17:51:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。