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

• arxiv url: http://arxiv.org/abs/2602.22330v2
• Date: Fri, 27 Feb 2026 13:31:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-02 13:30:11.475638
• 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 $\class{exp} ( n^2)$ in the number of qubits $n$, even approximately. We reduce the problem to solving a $3$-\class{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（参考訳）: 古典計算と量子計算の境界を特定することは、量子情報の中心的な課題である。 マルチキュービットシステムでは、絡み合いと魔法が真に量子的な振る舞いの基礎となる重要なリソースである。 絡み合いはよく理解されているが、普遍的な量子計算には魔法が不可欠である。 ここでは、魔法状態資源理論の自由状態を定義する安定化器ポリトープのメンバシップを決定するには、概して qubits $n$ の数において超指数時間 $\class{exp} (n^2)$ が必要となる。 この問題は、$n^2$変数上の$$$-\class{SAT} インスタンスの解決と指数時間仮説の呼び出しにより、次の結果になる。 その結果、量子化と認証の両方の魔法は基本的に難解であり、一般国家の任意のマジックモノトーンは超指数的に計算が困難であり、オペレータが有効な魔法の証人であるかどうかを決定することは等しく困難である。 結論として,魔法の強靭性はモノトーンの中で計算的に最適であることを示す。 この障壁は古典的にシミュレート可能な状態にまで拡張され、非クリフォードゲートの対数的数によって生成される状態の凸殻に状態が存在しているかどうかを決定することは超指数的に難しい。 これらの結果は、古典的シミュラビリティの評価、病理マジック状態の蒸留、そして究極的には量子資源としての魔法の探索と活用に関する本質的な計算限界を明らかにしている。

関連論文リスト

• Magic state cultivation on a superconducting quantum processor [108.15404500422814]
  超伝導量子プロセッサを用いたマジックステート培養の実験的検討を行った。 培養は40の係数で誤りを減らし、状態忠実度は0.9999(1)である。
  論文  参考訳（メタデータ） (2025-12-15T21:29:40Z)
• 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)
• Magic spreading in random quantum circuits [0.0]
  局所性とユニタリ性の制約の下で、汎用多体ダイナミクスがマジックリソースをいかに迅速に生成するかを示す。 魔法の資源が系の大きさの対数に等しく、反集中やヒルベルト空間の非局在化現象と類似していることを示す。 ランダム回路はカオス力学の最小モデルであるため、この発見はカオス多体系における魔法資源成長の現象を記述していると推測する。
  論文  参考訳（メタデータ） (2024-07-04T13:43:46Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• 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)

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

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