論文の概要: The unbearable hardness of deciding about magic

• arxiv url: http://arxiv.org/abs/2602.22330v1
• Date: Wed, 25 Feb 2026 19:00:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-27 18:41:22.377821
• Title: The unbearable hardness of deciding about magic
• Title（参考訳）: 魔法の決心の難しさ
• Authors: Lorenzo Leone, Jens Eisert, Salvatore F. E. Oliviero,
• Abstract要約: 魔法状態資源理論の自由状態を定義する安定化器ポリトープの定式化には超指数時間が必要であることを示す。 また,モノトーンの計算的最適性としてマジックの堅牢性を確立した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Identifying the boundary between classical and quantum computation is a central challenge in quantum information. In multi-qubit systems, entanglement and magic are the key resources underlying genuinely quantum behaviour. While entanglement is well understood, magic -- essential for universal quantum computation -- remains relatively poorly characterised. Here we show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time $\exp( n^2)$ in the number of qubits $n$, even approximately. We reduce the problem to solving a $3$-SAT instance on $n^2$ variables and, by invoking the exponential time hypothesis, the result follows. As a consequence, both quantifying and certifying magic are fundamentally intractable: any magic monotone for general states must be super-exponentially hard to compute, and deciding whether an operator is a valid magic witness is equally difficult. As a corollary, we establish the robustness of magic as computationally optimal among monotones. This barrier extends even to classically simulable regimes: deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard. Together, these results reveal intrinsic computational limits on assessing classical simulability, distilling pathological magic states, and ultimately probing and exploiting magic as a quantum resource.
• Abstract（参考訳）: 古典計算と量子計算の境界を特定することは、量子情報の中心的な課題である。 マルチキュービットシステムでは、絡み合いと魔法が真に量子的な振る舞いの基礎となる重要なリソースである。 絡み合いはよく理解されているが、普遍的な量子計算に欠かせない魔法は、いまだにあまり特徴づけられていない。 ここでは、魔法状態資源理論の自由状態を定義する安定化器ポリトープのメンバシップを決定するには、量子ビット数$n$の超指数時間$\exp(n^2)$が必要である。 この問題を、$n^2$変数上の$$$-SATインスタンスの解決と指数時間仮説の呼び出しに還元する。 その結果、量子化と認証の両方の魔法は基本的に難解であり、一般国家の任意のマジックモノトーンは超指数的に計算が困難であり、オペレータが有効な魔法の証人であるかどうかを決定することは等しく困難である。 結論として,魔法の強靭性はモノトーンの中で計算的に最適であることを示す。 この障壁は古典的にシミュレート可能な状態にまで拡張され、非クリフォードゲートの対数的数によって生成される状態の凸殻に状態が存在しているかどうかを決定することは超指数的に難しい。 これらの結果は、古典的シミュラビリティの評価、病理マジック状態の蒸留、そして究極的には量子資源としての魔法の探索と活用に関する本質的な計算限界を明らかにしている。

関連論文リスト

• Quantum States with Maximal Magic [0.0]
  ワイル・ハイゼンベルク(WH)の共変対称情報完全(SIC)量子測定が存在すれば、その状態は境界を飽和させることで安定度エントロピーを一意に最大化する。 この結果は,25年前のSICの存在問題と関連する数論の深い疑問を,この最大魔法の概念が受け継いでいることを実証するため,実用レベルでの量子計算に影響を及ぼす可能性がある。
  論文  参考訳（メタデータ） (2024-12-30T17:02:22Z)
• Experimental Demonstration of Logical Magic State Distillation [62.77974948443222]
  中性原子量子コンピュータ上での論理量子ビットによるマジック状態蒸留の実験的実現について述べる。 提案手法では,多くの論理量子ビット上で並列に量子演算を符号化し,実行するために動的に再構成可能なアーキテクチャを用いる。
  論文  参考訳（メタデータ） (2024-12-19T18:38:46Z)
• Noise robustness and threshold of many-body quantum magic [0.5524804393257919]
  絡み合った多体量子状態における雑音がマジック特性にどう影響するかを考察する。 高次ゲートによって誘導される相互作用は、ノイズに対して脆弱であることを示す。 また、離散ウィグナー形式に基づくクーディト事件についても論じる。
  論文  参考訳（メタデータ） (2024-10-28T17:01:47Z)
• Unconditional quantum magic advantage in shallow circuit computation [2.517043342442487]
  量子理論は古典的アプローチよりも計算スピードアップを約束する。 Gottesman-Knill理論は、量子計算の完全なパワーが「魔法の」状態の特定のリソースに存在することを示唆している。 本研究は,最初の非条件魔法の優位性を実証するものである。
  論文  参考訳（メタデータ） (2024-02-19T15:59:48Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Many-body quantum magic [0.609170287691728]
  我々は、$n$-qubit状態の最大マジックが本質的に$n$であり、同時に様々な「良い」マジック測度を示すことを示した。 魔法が理解できる高度に絡み合った状態の明示的でスケーラブルなケースを求める中で、ハイパーグラフ状態のマジックと基礎となるブール関数の2階非線形性とを結びつける。 約$n$の量子状態、または実際にはほぼすべての状態は、古典的なコンピュータに非自明なスピードアップを供給できないことを示す。
  論文  参考訳（メタデータ） (2020-10-26T18:06:45Z)
• Operational Resource Theory of Imaginarity [48.7576911714538]
  量子状態は、実際の要素しか持たなければ、生成や操作が容易であることを示す。 応用として、想像力は国家の差別にとって重要な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2020-07-29T14:03:38Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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