論文の概要: On the Hardness of Approximate Quantum Circuit Membership and Optimization

• arxiv url: http://arxiv.org/abs/2611.04381v1
• Date: Tue, 03 Nov 2026 06:12:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-10 01:01:54.603786
• Title: On the Hardness of Approximate Quantum Circuit Membership and Optimization
• Title（参考訳）: 近似量子回路の硬さと最適化について
• Abstract要約: 我々は,QMA完全約束版よりも,約束なし入力よりも近似メンバシップが難しいことを示す。 以上の結果から,QMA完全約束版よりも有意な入力が困難であることが示唆された。
• 参考スコア（独自算出の注目度）: 4.554892610576937
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries $S$, decide whether a given circuit $C$ is within distance $\varepsilon$ of a unitary in $S$ under some metric $m$. Membership is a special case of optimization, where $S$ is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case $S=\{I\}$ (approximate identity) is QMA-complete when $C$ is promised to be either close to the identity or far from it. We generalize this setting in three directions: (i) promise-free inputs, (ii) besides $S=\{I\}$, sets $S$ containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of $\varepsilon$, provided $C$'s gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If $S=\{I\}$, or if $S$ contains only generalized permutation matrices, $I\in S$, and $m$ is a trace-based distance, PP-hardness holds for all non-trivial $\varepsilon$. If $S=\{I\}$ and $m$ is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets. Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.
• Abstract（参考訳）: 量子回路最適化は、ノイズの低減、性能の最大化、量子エラー補正のコスト軽減、あるいは特定のハードウェアをターゲットにした量子ソフトウェアスタックの必須コンポーネントである。 関連する問題は、固定されたユニタリの集合 S$ に対して、与えられた回路 $C$ が距離$\varepsilon$ の範囲内かどうかを決定する。 メンバーシップは最適化の特別なケースであり、$S$は実装可能なユニタリのセットで、コストがかからない(例えば、ノイズ最小回路やマジック状態がない)。 Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) は作用素計量について、$S=\{I\}$ (近似恒等式) が QMA 完全であることを示した。 この設定を3つの方向に一般化する。 (i)約束なしの入力 (ii)$S=\{I\}$の他に、クリフォードユニタリのみを含む$S$、あるいは一般化された置換行列のみを含む$S$を設定する(すなわち、重ね合わせがない)。 (iii)トレースベース、スペクトル、演算子メトリクス。 すべてのケースにおいて、C$のゲートセットが標準ハードウェアのゲートセットとしてClifford+Tを実装することができれば、近い範囲の$\varepsilon$に対して近似メンバシップがPPハードであることが示される。 S=\{I\}$ あるいは $S$ が一般化された置換行列のみを含む場合、$I\in S$ と $m$ はトレースベース距離であり、PP-ハードネスはすべての非自明な $\varepsilon$ に対して成り立つ。 S=\{I\}$ と $m$ がトレースベース距離であるなら、PP-ハードネスは古典的可逆ゲート集合上の回路に対しても成り立つ。 以上の結果から,QMA完全約束版よりも確率自由な入力よりも近似メンバシップが困難であること,量子リソース(ゲート,非クリフォード,重ね合わせ)と距離測定値が持続していることが示唆された。 これらは、合計、非クリフォード、または重畳ゲート深さまたはカウントを最小化する場合、回路最適化のPP硬度を直接意味する。

関連論文リスト

• Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points [31.45779401617503]
  タルスキの不動点問題は、幅$n$の$k$次元格子上の単調写像の固定点を求め、ゲーム理論、経済学、検証に応用できる。 量子下界に対する2つのブートストラッピング定理を証明する。
  論文  参考訳（メタデータ） (2026-10-12T05:39:35Z)
• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Optimal learning of covariant quantum states and channels [0.0]
  我々は、既知の対称性を持つ量子状態やチャネルに対する集合トモグラフィープロトコルを提供する。 我々は, 最適な純状態推定のために, 林測度を近似する効率的な量子回路を構築した。
  論文  参考訳（メタデータ） (2026-09-30T08:30:12Z)
• Efficient Fuzzy Private Set Intersection from Secret-shared OPRF [41.88845480337768]
  Fuzzy PSI (FPSI) は、受信者がQ$で$qを学習するPSI変種であり、W$に約$wが存在する。 本稿では, [1, infty]$ distance における$L_p に対する効率的な FPSI プロトコルを提案する。 我々のプロトコルは、集合サイズ$m,n$、次元$d$、距離しきい値$$で線形通信と計算の複雑さを実現する。
  論文  参考訳（メタデータ） (2026-04-16T11:51:25Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。 我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
  論文  参考訳（メタデータ） (2026-03-20T01:53:44Z)
• Exact Quantum Circuit Optimization is co-NQP-hard [4.554892610576937]
  我々は、回路$C$が与えられたとき、量子リソースタイプを最小化する等価回路$C’$が計算されるという自然問題を考える。 H と TOF のゲートを正確に実装できる任意のゲート集合上で$C$ が表現されている場合、上記の最適化問題は $textco-NQP$ では困難である。
  論文  参考訳（メタデータ） (2025-10-18T09:31:23Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Quantum Algorithms for Projection-Free Sparse Convex Optimization [32.34794896079469]
  ベクトル領域に対しては、$O(sqrtd/varepsilon)$のクエリ複雑性を持つ$varepsilon$-optimal解を求めるスパース制約に対する2つの量子アルゴリズムを提案する。 行列領域に対しては、時間複雑性を$tildeO(rd/varepsilon2)$と$tildeO(sqrtrd/varepsilon3)$に改善する2つの核ノルム制約の量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-11T12:43:58Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)

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

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