論文の概要: CNOT-Optimal Clifford Synthesis as SAT

• arxiv url: http://arxiv.org/abs/2504.00634v1
• Date: Tue, 01 Apr 2025 10:35:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-03 13:24:20.607520
• Title: CNOT-Optimal Clifford Synthesis as SAT
• Title（参考訳）: SATとしてのCNOT最適クリフォード合成
• Authors: Irfansha Shaik, Jaco van de Pol,
• Abstract要約: 2量子CNOTゲートのようなノイズゲートの最小化は、実用的な計算に不可欠である。 我々は、CNOTカウントの最適性を保証するために、クリフォード回路上でのみ、一定の正規形式で網羅的な探索を提案する。 実験では、我々の符号化は、ランダムなクリフォード回路における既存のSATアプローチよりも大幅に優れていた。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Clifford circuit optimization is an important step in the quantum compilation pipeline. Major compilers employ heuristic approaches. While they are fast, their results are often suboptimal. Minimization of noisy gates, like 2-qubit CNOT gates, is crucial for practical computing. Exact approaches have been proposed to fill the gap left by heuristic approaches. Among these are SAT based approaches that optimize gate count or depth, but they suffer from scalability issues. Further, they do not guarantee optimality on more important metrics like CNOT count or CNOT depth. A recent work proposed an exhaustive search only on Clifford circuits in a certain normal form to guarantee CNOT count optimality. But an exhaustive approach cannot scale beyond 6 qubits. In this paper, we incorporate search restricted to Clifford normal forms in a SAT encoding to guarantee CNOT count optimality. By allowing parallel plans, we propose a second SAT encoding that optimizes CNOT depth. By taking advantage of flexibility in SAT based approaches, we also handle connectivity restrictions in hardware platforms, and allow for qubit relabeling. We have implemented the above encodings and variations in our open source tool Q-Synth. In experiments, our encodings significantly outperform existing SAT approaches on random Clifford circuits. We consider practical VQE and Feynman benchmarks to compare with TKET and Qiskit compilers. In all-to-all connectivity, we observe reductions up to 32.1% in CNOT count and 48.1% in CNOT depth. Overall, we observe better results than TKET in the CNOT count and depth. We also experiment with connectivity restrictions of major quantum platforms. Compared to Qiskit, we observe up to 30.3% CNOT count and 35.9% CNOT depth further reduction.
• Abstract（参考訳）: クリフォード回路最適化は、量子コンパイルパイプラインの重要なステップである。 主要なコンパイラはヒューリスティックなアプローチを採用する。 速いが、結果はしばしば最適以下である。 2量子CNOTゲートのようなノイズゲートの最小化は、実用的な計算に不可欠である。 ヒューリスティックなアプローチによって残されたギャップを埋めるために、厳密なアプローチが提案されている。 SATベースのアプローチはゲート数や深さを最適化するが、スケーラビリティの問題に悩まされている。 さらに、CNOTカウントやCNOT深さといった、より重要なメトリクスに対する最適性も保証しません。 最近の研究では、CNOTカウントの最適性を保証するために、クリフォード回路上の特定の正規形のみを網羅的に探索することを提案した。 しかし、徹底的なアプローチでは6キュービットを超えるスケールはできない。 本稿では,Clifford正規形式に制限された探索をSATエンコーディングに組み込んで,CNOTカウントの最適性を保証する。 CNOT深度を最適化する第2のSAT符号化法を提案する。 SATベースのアプローチの柔軟性を活用することで、ハードウェアプラットフォームの接続制限にも対処し、qubit relabelingを可能にします。 上記のエンコーディングとバリエーションをオープンソースツールQ-Synthに実装しました。 実験では、我々の符号化は、ランダムなクリフォード回路における既存のSATアプローチよりも大幅に優れていた。 実用的なVQEとFeynmanベンチマークをTKETとQiskitコンパイラと比較する。 全接続では、最大32.1%のCNOT数、48.1%のCNOT深度が減少する。 CNOT計数と深度では,TKETよりも良好な結果が得られた。 また、主要な量子プラットフォームの接続制限についても実験を行った。 Qiskitと比較すると、最大30.3%のCNOT数と35.9%のCNOT深度がさらに減少している。

関連論文リスト

• Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs [46.010796136659536]
  重み付きCSP問題に対する既存の参照アルゴリズムの代替策について検討する。 我々の実証研究は、WCSPにとって最良の選択肢を特定するのは容易ではないことを示している。
  論文  参考訳（メタデータ） (2025-01-13T15:59:28Z)
• Optimal Layout-Aware CNOT Circuit Synthesis with Qubit Permutation [0.0]
  CNOT最適化は量子回路のノイズ低減に重要な役割を果たしている。 CNOTゲート数と回路深度の両方を最適化する。 また,CNOT数では56%,回路深さでは46%まで低減できることを示した。
  論文  参考訳（メタデータ） (2024-08-08T10:20:13Z)
• Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits [0.0]
  スケーラブルなレイアウト合成は、NISQプロセッサにとって非常に重要である。 本稿では,1つのSWAPとCNOTのグループを各ステップで適用する並列計画に基づくSAT符号化を提案する。 初めて、8, 14, 16量子ビット回路を最大17個のSWAPを持つ54, 80, 127量子ビットプラットフォームに最適にマッピングできる。
  論文  参考訳（メタデータ） (2024-03-18T09:19:01Z)
• Quantum State Preparation Using an Exact CNOT Synthesis Formulation [8.078625517374967]
  量子状態生成におけるCNOTゲートの使用を最小限にすることは、量子コンパイルにおける重要なステップである。 正確なCNOT合成定式化を用いた効率的な状態生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-02T03:37:00Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。 そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
  論文  参考訳（メタデータ） (2022-10-04T09:19:13Z)
• A SAT Encoding for Optimal Clifford Circuit Synthesis [3.610459670994051]
  量子回路の重要なサブクラスであるクリフォード回路の最適合成を考える。 本稿では,タスクを満足度問題として符号化したクリフォード回路の最適合成法を提案する。 得られたツールは、最大26ドルキュービットの最適回路を合成する。
  論文  参考訳（メタデータ） (2022-08-24T18:00:03Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• AQD: Towards Accurate Fully-Quantized Object Detection [94.06347866374927]
  本稿では,浮動小数点演算を除去するために,AQDと呼ばれる高精度な量子化オブジェクト検出ソリューションを提案する。 我々のAQDは、非常に低ビットのスキームの下での完全精度と比較して、同等またはそれ以上の性能を実現しています。
  論文  参考訳（メタデータ） (2020-07-14T09:07:29Z)

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

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