論文の概要: Exact Quantum Circuit Optimization is co-NQP-hard

• arxiv url: http://arxiv.org/abs/2510.16420v1
• Date: Sat, 18 Oct 2025 09:31:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 00:56:38.991285
• Title: Exact Quantum Circuit Optimization is co-NQP-hard
• Title（参考訳）: Exact Quantum Circuit Optimization is co-NQP-hard
• Authors: Adam Husted Kjelstrøm, Andreas Pavlogiannis, Jaco van de Pol,
• Abstract要約: 我々は、回路$C$が与えられたとき、量子リソースタイプを最小化する等価回路$C’$が計算されるという自然問題を考える。 H と TOF のゲートを正確に実装できる任意のゲート集合上で$C$ が表現されている場合、上記の最適化問題は $textco-NQP$ では困難である。
• 参考スコア（独自算出の注目度）: 4.554892610576937
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As quantum computing resources remain scarce and error rates high, minimizing the resource consumption of quantum circuits is essential for achieving practical quantum advantage. Here we consider the natural problem of, given a circuit $C$, computing an equivalent circuit $C'$ that minimizes a quantum resource type, expressed as the count or depth of (i) arbitrary gates, or (ii) non-Clifford gates, or (iii) superposition gates, or (iv) entanglement gates. We show that, when $C$ is expressed over any gate set that can implement the H and TOF gates exactly, each of the above optimization problems is hard for $\text{co-NQP}$, and hence outside the Polynomial Hierarchy, unless the Polynomial Hierarchy collapses. This strengthens recent results in the literature which established an $\text{NP}$-hardness lower bound, and tightens the gap to the corresponding $\text{NP}^\text{NQP}$ upper bound known for cases (i)-(iii) over Clifford+T and (i)-(iv) over H+TOF circuits.
• Abstract（参考訳）: 量子コンピューティング資源は依然として乏しく、エラー率が高いため、量子回路のリソース消費を最小限に抑えることは、実用的な量子的優位性を達成するために不可欠である。 ここでは、回路$C$が与えられたとき、量子リソースタイプを最小化する等価回路$C’$を計算し、カウントまたは深さとして表現する自然問題を考える。 (一)任意の門、又は (二)非クリフォード門、又は (三)重ね門、又は (四)関門。 H と TOF のゲートを正確に実装できる任意のゲート集合上で$C$ が表現されるとき、上記の最適化問題は $\text{co-NQP}$ では困難であり、したがってポリノミアル階層が崩壊しない限り、ポリノミアル階層の外側にあることを示す。 これは、$\text{NP}$-hardness lower boundを確立し、対応する$\text{NP}^\text{NQP}$ upper boundにギャップを縮めるという文献の最近の結果を補強する。 (i)- (iii)Clifford+T以上 (i)- (4)H+TOF回路上。

関連論文リスト

• Clifford+V synthesis for multi-qubit unitary gates [0.0]
  基本ゲートの有限集合を用いてターゲットゲートを合成するための一般的な枠組みを開発する。 マルチキュービット制御ゲートを合成するための準最適だが短い実行時アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-10-09T14:57:55Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
  我々は、イオントラップハードウェアに存在するGlobal Molmer-Sorensenゲートのようなグローバルな相互作用を用いて量子回路を最適化し、合成する。 このアルゴリズムはZX計算に基づいており、係留ゲートをGlobal MolmerSorensenゲートにグループ化する特別な回路抽出ルーチンを使用する。 我々は,このアルゴリズムを様々な回路でベンチマークし,最新ハードウェアによる性能向上の方法を示す。
  論文  参考訳（メタデータ） (2025-07-28T10:25:31Z)
• Physics and Computation: A Perspective From Non-Hermitian Quantum Computer [8.73778121120948]
  NQCは極端に強力であり、すべてのNP問題だけでなく、複雑性クラス$textPsharpP$内のすべての問題を時間内に解くことができる。 非単位ゲートを$G$で実装するための2つの物理スキームを調査し、NQCの卓越した計算能力は、指数関数的に大きな物理資源から生じることを見出した。
  論文  参考訳（メタデータ） (2025-06-22T12:26:04Z)
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
  量子格子ボルツマン法(QLBM)における非圧縮性ナビエ-ストークス方程式の多重回路アルゴリズムを提案する。 提案法は2次元蓋駆動キャビティフローに対して検証および実証を行った。
  論文  参考訳（メタデータ） (2024-01-20T15:32:01Z)
• Optimising quantum circuits is generally hard [0.0]
  約普遍量子回路に対する多くのゲート最適化問題はNPハードであることが判明した。 クリフォードゲートの任意の$G$に対して、クリフォード+$G$ゲート集合上の$G$カウントを最適化するのはNPハードであることを示す。
  論文  参考訳（メタデータ） (2023-09-12T09:35:23Z)
• Approaching the theoretical limit in quantum gate decomposition [0.0]
  本稿では,CNOT$ゲート数を持つ1量子および2量子ビットの量子ゲートを用いて,一般量子プログラムを分解する新しい数値計算手法を提案する。 本手法は, 既設計量子回路における単一量子ビット回転ゲートに関するパラメータの逐次最適化に基づく。
  論文  参考訳（メタデータ） (2021-09-14T15:36:22Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Cost-optimal single-qubit gate synthesis in the Clifford hierarchy [0.0]
  合成アルゴリズムは任意の精度で任意の単位ゲートを近似することができる。 現在の手順は、基本ゲートコストの個別割り当てをまだサポートしていない。
  論文  参考訳（メタデータ） (2020-05-12T07:21:12Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。 本稿では,QAOAの回路深度依存性能について実験的に検討する。 この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
  論文  参考訳（メタデータ） (2020-05-11T17:20:51Z)

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

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