論文の概要: Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits
- arxiv url: http://arxiv.org/abs/2511.17856v1
- Date: Sat, 22 Nov 2025 00:51:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-25 18:34:24.480105
- Title: Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits
- Title（参考訳）: 低T層量子回路における厳密な不確かさチェックとゲートテレポーテーションに基づく不特定性難読化はNPハードである
- Authors: Joshua Nevin,
- Abstract要約: 2021年に開発された量子回路の計算不特定性難読化のためのゲート・テレポーテーションに基づくプロトコル。
特に、T-depth $O(log(n))$のクリフォード+T回路に対して、ENICを決定することはNPハードであることを示す。
これにより、P=NPでない限り、効率的な ENIC または効率的なゲートテレポーテーションに基づく計算不能な難読化のいずれかの対数Tディープスのクリフォード+T回路の可能性を効果的に定義できる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: In 2021, Broadbent and Kazmi developed a gate-teleportation-based protocol for computational indistinguishability obfuscation of quantum circuits. This protocol is efficient for Clifford+T circuits with logarithmically many T-gates, where the limiting factor in the efficiency of the protocol is the difficulty, on input a quantum circuit $C$, of the classical task of producing a description of the unitary obtained by conjugating a Pauli $P$ (corresponding to a Bell-measurement outcome) by $C$, where this description only depends on the input-output functionality of $CPC^{\dagger}$. The task above, in turn, is at least as hard as the problem of determining whether two $n$-qubit quantum circuits are perfectly equivalent up to global phase. In 2009, Tanaka defined the corresponding decision problem Exact Non-Identity Check (ENIC) and showed that ENIC is NQP-complete in general. Motivated by this, we consider in this work what happens when we pass from low T-count to low T-depth. In particular, we show that, for Clifford+T circuits of T-depth $O(\log(n))$, deciding ENIC is NP-hard. This effectively rules out the possibility, for Clifford+T circuits of logarithmic T-depth, of either efficient ENIC or efficient gate-teleportation based computational indistinguishability obfuscation, unless P=NP.
- Abstract（参考訳）: 2021年、ブロードベントとカズミは量子回路の計算不能な難読化のためのゲートテレポーテーションベースのプロトコルを開発した。
このプロトコルは、対数的に多くのTゲートを持つクリフォード+T回路に対して効率的であり、このプロトコルの効率の制限要因は、量子回路$C$の入力が困難であり、量子回路$C$は、Pauli$P$(ベル測定結果に対応する)を$C$で共役することで得られるユニタリの記述を生成する古典的なタスクの$C$であり、この記述は$CPC^{\dagger}$の入力出力機能にのみ依存する。
上記の課題は、少なくとも2つの$n$量子ビット量子回路がグローバル位相まで完全に等価であるかどうかを決定する問題と同じくらい難しい。
2009年、田中は対応する決定問題 Exact Non-Identity Check (ENIC) を定義し、一般に ENIC は NQP 完全であることを示した。
このことに動機づけられたこの研究では、低いT数から低いT深度に移動するときに何が起こるかを考える。
特に、T-depth $O(\log(n))$のクリフォード+T回路に対して、ENICを決定することはNPハードであることを示す。
これにより、P=NPでない限り、効率的な ENIC または効率的なゲートテレポーテーションに基づく計算不能な難読化のいずれかの対数Tディープスのクリフォード+T回路の可能性を効果的に定義できる。
関連論文リスト
- Exact Quantum Circuit Optimization is co-NQP-hard [4.554892610576937]
我々は、回路$C$が与えられたとき、量子リソースタイプを最小化する等価回路$C’$が計算されるという自然問題を考える。
H と TOF のゲートを正確に実装できる任意のゲート集合上で$C$ が表現されている場合、上記の最適化問題は $textco-NQP$ では困難である。
論文 参考訳（メタデータ） (2025-10-18T09:31:23Z) - Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
我々は、イオントラップハードウェアに存在するGlobal Molmer-Sorensenゲートのようなグローバルな相互作用を用いて量子回路を最適化し、合成する。
このアルゴリズムはZX計算に基づいており、係留ゲートをGlobal MolmerSorensenゲートにグループ化する特別な回路抽出ルーチンを使用する。
我々は,このアルゴリズムを様々な回路でベンチマークし,最新ハードウェアによる性能向上の方法を示す。
論文 参考訳（メタデータ） (2025-07-28T10:25:31Z) - Implementation and readout of maximally entangled two-qubit gates quantum circuits in a superconducting quantum processor [32.40607221598716]
トランスモンベースの5量子ビット超伝導量子プロセッサにおいて,複雑性の増大に伴う量子回路の性能の比較を行った。
本稿では、2つの読み出しパラダイムを用いて量子回路の出力の分析結果について報告する。
第1の方法はシングルキュービット回路に適しているが、第2の方法は2キュービットゲートを含む回路の出力を正確に解釈するのに不可欠である。
論文 参考訳（メタデータ） (2025-03-31T16:20:56Z) - Optimising quantum circuits is generally hard [0.0]
約普遍量子回路に対する多くのゲート最適化問題はNPハードであることが判明した。
クリフォードゲートの任意の$G$に対して、クリフォード+$G$ゲート集合上の$G$カウントを最適化するのはNPハードであることを示す。
論文 参考訳（メタデータ） (2023-09-12T09:35:23Z) - Simulation of IBM's kicked Ising experiment with Projected Entangled
Pair Operator [71.10376783074766]
我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。
提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。
我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
論文 参考訳（メタデータ） (2023-08-06T10:24:23Z) - Single-shot error mitigation by coherent Pauli checks [6.992823294269743]
完全な誤り訂正を行うことなく、量子回路の出力分布からサンプルを生成する方法を示す。
我々のアプローチは、クリフォード回路の誤差を検出するコヒーレント・パウリ・チェックに基づいている。
論文 参考訳（メタデータ） (2022-12-07T20:03:07Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Clifford Circuits can be Properly PAC Learned if and only if
$\textsf{RP}=\textsf{NP}$ [1.14219428942199]
クラフォード回路の適切な学習は、textsfRP = textsfNP$ がなければ古典的な学習者にとって困難であることを示す。
また,$textsfNP subseteq textsfRQP$。
論文 参考訳（メタデータ） (2022-04-13T21:07:53Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Efficient quantum programming using EASE gates on a trapped-ion quantum
computer [1.9610635155358869]
我々は、最近発明された、トラップイオン量子コンピュータで利用可能な、効率的な、任意の、同時に絡み合う(EASE)ゲートに焦点を当てる。
我々は、$n$-qubit Clifford 回路を$6log(n)$EASEゲートで実装でき、$n$-qubit multiply-control NOT ゲートを$n/2$EASEゲートで実装でき、$n$-qubit 置換を6つのEASEゲートで実装できることを示した。
論文 参考訳（メタデータ） (2021-07-15T20:03:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。