論文の概要: Finding the disjointness of stabilizer codes is NP-complete
- arxiv url: http://arxiv.org/abs/2108.04738v1
- Date: Tue, 10 Aug 2021 15:00:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2023-03-18 21:20:26.861991
- Title: Finding the disjointness of stabilizer codes is NP-complete
- Title（参考訳）: 安定化符号の不一致はnp完全である
- Authors: John Bostanci and Aleksander Kubica
- Abstract要約: 我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
- 参考スコア（独自算出の注目度）: 77.34726150561087
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The disjointness of a stabilizer code is a quantity used to constrain the
level of the logical Clifford hierarchy attainable by transversal gates and
constant-depth quantum circuits. We show that for any positive integer constant
$c$, the problem of calculating the $c$-disjointness, or even approximating it
to within a constant multiplicative factor, is NP-complete. We provide bounds
on the disjointness for various code families, including the CSS codes,
concatenated codes and hypergraph product codes. We also describe numerical
methods of finding the disjointness, which can be readily used to rule out the
existence of any transversal gate implementing some non-Clifford logical
operation in small stabilizer codes. Our results indicate that finding
fault-tolerant logical gates for generic quantum error-correcting codes is a
computationally challenging task.
- Abstract（参考訳）: 安定化器符号の不一致性は、横断ゲートと定深さ量子回路によって達成可能な論理クリフォード階層のレベルを制限するために用いられる量である。
任意の正の整数定数 $c$ に対して、$c$-disjointness を計算するか、あるいはそれを定数乗算係数の範囲内で近似する問題は NP-完全であることを示す。
CSSコード、連結コード、ハイパーグラフ製品コードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
また,非クリフォード論理演算を小さな安定化符号で実装した任意のトランスバーサルゲートの存在を排除できる不連続性を求める数値的手法についても述べる。
その結果,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの探索は計算上難しい課題であることがわかった。
関連論文リスト
- QGPU: Parallel logic in quantum LDPC codes [1.9960650656921184]
量子低密度パリティチェックコードは、表面コードに代わるリソース効率のよいコードである。
鍵となる課題は、論理キュービットは必ずしも物理キュービットの解集合に写像されないことである。
有限サイズのインスタンスを持つ量子低密度パリティチェック符号群であるクラスター循環符号を導入する。
論文 参考訳（メタデータ） (2026-03-05T17:26:00Z) - Non-Abelian qLDPC: TQFT Formalism, Addressable Gauging Measurement and Application to Magic State Fountain on 2D Product Codes [1.1087735229999818]
定レート2次元ハイパーグラフ生成符号とClifford-stabilizer変種を用いて,ネイティブな非クリフォード論理ゲートを実現できることを示す。
これは、新しいタイプの0-形式部分複素対称性のアドレス可能なゲージ計測を効果的に実装した時空経路によって達成される。
論文 参考訳（メタデータ） (2026-01-11T01:20:36Z) - Logical gates on Floquet codes via folds and twists [45.88028371034407]
静的量子誤り訂正符号の2つの手法をFloquet符号に実装する方法を示す。
まず、論理的なアダマールとSゲートを得るために、フロッケ符号の折り曲げ操作を実装する方法を提案する。
第二に、DehnツイストによるFloquet符号に論理的CNOTゲートを実装する方法を提案する。
論文 参考訳（メタデータ） (2025-12-19T19:00:06Z) - Average-Case Complexity of Quantum Stabilizer Decoding [42.770940323689445]
1つの論理量子ビットでさえも、ランダムな安定化符号を復号化することは、ランダムな古典符号を一定速度で復号化することと同じくらい難しいことを証明している。
この結果は、最も簡単なランダム量子復号問題は、少なくとも最も難しいランダム古典復号問題と同じくらい難しいことを示唆している。
論文 参考訳（メタデータ） (2025-09-25T03:04:40Z) - No-go theorems for logical gates on product quantum codes [5.529881798520845]
符号のホモロジー積は、量子誤り訂正符号のための汎用的なフレームワークを提供する。
非クリフォード論理ゲートがハイパーグラフ製品コード上で容易に実装できないことを示す。
論文 参考訳（メタデータ） (2025-07-22T17:46:45Z) - Parallel Logical Measurements via Quantum Code Surgery [42.95092131256421]
量子符号手術(Quantum code surgery)は、量子誤り訂正符号の論理的測定を行うための、柔軟で低オーバーヘッドな技術である。
本稿では,量子ビット安定化器の低密度パリティチェック(LDPC)コードに適用可能なコード手術方式を提案する。
論文 参考訳（メタデータ） (2025-03-06T22:05:52Z) - Universal quantum computation via scalable measurement-free error correction [45.29832252085144]
本研究では,中間回路計測を行なわずに誤り訂正を行うシナリオにおいて,普遍的な量子計算をフォールトトレラントにすることができることを示す。
論理的な$mathitCCZ$ゲートを実現するため,Bacon-Shor符号の無測定変形プロトコルを導入する。
特に,回路レベルのエラーレートが10～3ドル以下であれば,破れない論理性能が達成可能であることを示す。
論文 参考訳（メタデータ） (2024-12-19T18:55:44Z) - Targeted Clifford logical gates for hypergraph product codes [61.269295538188636]
ハイパーグラフ製品コードのための論理ゲートを明示的に構築する。
具体的な例として、$[[18,2,3]]$トーリック符号に対して論理回路を与える。
論文 参考訳（メタデータ） (2024-11-26T02:32:44Z) - Measurement-free code-switching for low overhead quantum computation using permutation invariant codes [6.281229317487581]
普遍量子計算のための無測定符号スイッチングプロトコルを提案する。
この符号スイッチングプロトコルによって実現された新しい非クリフォードゲートは、クリフォード$+T$ゲートセットよりも効率的なユニバーサルゲートセットの実装を可能にする。
論文 参考訳（メタデータ） (2024-11-20T09:16:07Z) - Transversal non-Clifford gates for quantum LDPC codes on sheaves [1.0878040851638]
量子コンピューティングの大きな目標は、フォールトトレラントな量子コンピュータを構築することである。
1つのアプローチは、非クリフォードゲートをサポートする量子低密度パリティチェック(qLDPC)コードである。
論文 参考訳（メタデータ） (2024-10-18T17:31:19Z) - Geometric structure and transversal logic of quantum Reed-Muller codes [51.11215560140181]
本稿では,量子リード・ミュラー符号(RM)のゲートを,古典的特性を利用して特徴付けることを目的とする。
RM符号のための安定化器生成器のセットは、特定の次元のサブキューブに作用する$X$と$Z$演算子によって記述することができる。
論文 参考訳（メタデータ） (2024-10-10T04:07:24Z) - Toward Constructing a Continuous Logical Operator for Error-Corrected
Quantum Sensing [0.0]
論理キュービット上の操作はクリフォード+Tのような有限サイズのゲートからなる普遍ゲートセットを通してのみ実行される。
イーストン・クニルの定理は、連続的な信号が局所的な誤りや横方向の誤りに寛容であることを防ぐ。
連続的な論理z回転を設計するためのプロトコルが提案され、Steane Codeに適用される。
論文 参考訳（メタデータ） (2023-04-30T18:22:34Z) - Hierarchical memories: Simulating quantum LDPC codes with local gates [0.05156484100374058]
一定のレートの低密度パリティチェック(LDPC)符号は、効率的なフォールトトレラント量子メモリを構築する上で有望な候補である。
我々は、多くの論理量子ビット K = Omega(N/log(N)2) を符号化する階層符号の新しい族を構築する。
保守的な仮定の下では、階層的コードは、全ての論理量子ビットが曲面コードに符号化される基本符号化よりも優れていることが分かる。
論文 参考訳（メタデータ） (2023-03-08T18:48:12Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Transversal Injection: A method for direct encoding of ancilla states
for non-Clifford gates using stabiliser codes [55.90903601048249]
非クリフォードゲートのこのオーバーヘッドを低減するためのプロトコルを導入する。
予備的な結果は、より広い距離で高品質な忠実さを示唆している。
論文 参考訳（メタデータ） (2022-11-18T06:03:10Z) - A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
ほとんどの人造システム、特にコンピュータは決定論的に機能する。
本稿では、量子物理学が確率法則に従うときの直観的なアプローチである量子情報理論による接続を提供する。
論文 参考訳（メタデータ） (2022-09-08T17:55:30Z) - Finite-rate sparse quantum codes aplenty [1.1279808969568252]
本稿では、ランダムな二部グラフ上の制約満足度問題(CSP)を解決するために、ランダムなマルチキュービット安定化器符号を生成する手法を提案する。
現状のCSPソルバを用いて、満足度しきい値の存在を証明できる証拠を得る。
良好な位相にあるスパース符号は、消去ノイズのチャネル容量を実質的に達成する。
論文 参考訳（メタデータ） (2022-07-07T20:39:39Z) - Partitioning qubits in hypergraph product codes to implement logical
gates [0.0]
トランスバーサルゲートは、最も単純なフォールトトレラント論理ゲートである。
LDPC符号における普遍量子コンピューティングの基盤としてゲートが利用できることを示す。
論文 参考訳（メタデータ） (2022-04-22T16:45:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。