論文の概要: Robust subspace designs and the power of a unique small quantum witness
- arxiv url: http://arxiv.org/abs/2610.06302v1
- Date: Mon, 05 Oct 2026 13:26:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-09 09:23:10.598506
- Title: Robust subspace designs and the power of a unique small quantum witness
- Title（参考訳）: ロバスト部分空間の設計と特異な小さな量子目撃者の力
- Abstract要約: 部分空間設計は、固定次元の任意の部分空間と小さな交叉を持つ部分空間の族である。
我々の主な応用はヴァリアント・ヴァジラニの定理(Theor.Comput.Sci.'86)の量子空間有界変種である。
我々は、ロバストな部分空間設計の確率論的構成を用いて、空間有界量子メルリン・アーサープロトコルのユニークな目撃者を分離する。
- 参考スコア（独自算出の注目度）: 0.41998444721319217
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The concept of subspace designs was introduced by Guruswami and Xing (STOC'13), and explicit constructions were given by Guruswami and Kopparty (FOCS'13). These are families of subspaces that have small intersection with any given subspace of a fixed dimension. We introduce \emph{robust subspace designs}. Informally, these are a quantitative extension in which we demand that not too many subspaces of the family contain directions that lie close to any given subspace of a fixed dimension. We give a probabilistic construction of such a robust subspace design of polynomial size, as well as a non-trivial explicit construction of superpolynomial size. Our main application of this new concept is a quantum space-bounded variant of the Valiant-Vazirani theorem (Theor.Comput.Sci.'86), which shows that restricting $\mathsf{NP}$-complete problems to instances with at most one accepting witness preserves hardness under randomized reductions. For quantum witnesses, the analogous quantity is the dimension of an accepting witness subspace. We use our probabilistic construction of robust subspace designs to isolate a unique witness for space-bounded quantum Merlin-Arthur protocols with perfect completeness and an acceptance gap outside their perfectly accepting subspace. As further applications, we give a randomized reduction of well-conditioned nullity testing to space-bounded quantum Merlin-Arthur protocols with perfect completeness. Using a similar idea, we find that ordinary subspace designs allow us to recover the classical $\mathsf{C_= L}$ containment of Allender, Beals, and Ogihara (STOC'96) for general nullity testing through a simpler proof.
- Abstract（参考訳）: サブスペースデザインの概念はGuruswami and Xing (STOC'13)によって導入され、明示的な構成はGuruswami and Kopparty (FOCS'13)によって提供された。
これらは、固定次元の任意の部分空間と小さな交叉を持つ部分空間の族である。
ここでは \emph{robust subspace design} を紹介する。
インフォーマルに、これらは数的拡張であり、その族の過度な部分空間は、固定次元の任意の部分空間に近くにある方向を含まないことを要求する。
多項式サイズの頑健な部分空間設計の確率的構成と超多項式サイズの非自明な構成を与える。
この新しい概念の主な応用は、ヴァリアント・ヴァジラニの定理(Theor.Comput.Sci.'86)の量子空間有界変種であり、これは、少なくとも1つの証人を受け入れたインスタンスに対して$\mathsf{NP}$完全問題を制限することは、ランダム化還元の下で硬さを保っていることを示している。
量子目撃者にとって、類似量(英: analogous amount)とは、受理された証人部分空間の次元である。
我々は頑健な部分空間の設計を確率論的に構築し、完全な完全性と完全に受け入れられる部分空間の外の受容ギャップを持つ空間有界量子メルリン・アーサープロトコルの特異な目撃者を分離する。
さらなる応用として、完全性のある空間有界量子メルリン・アーサープロトコルに対して、よく条件付けられた零性試験をランダムに還元する。
同様の考えを用いて、通常の部分空間設計により、より単純な証明により、一般的な零点検定のために、古典的な$\mathsf{C_= L}$ の Allender, Beals, and Ogihara (STOC'96) の包含を復元できることがわかった。
関連論文リスト
- Entangled Subspaces through Algebraic Geometry [3.069335774032178]
本論文では,多部量子系のヒルベルト空間内での絡み合った部分空間を構成するための代数的アプローチを提案する。
この手法を用いることで、最小次元の非直交的かつ拡張不可能な製品基底(nUPB)を構築する。
マルチキューシステムでは、対称 GES の最大到達可能次元を決定し、この構成を通じてその実現を実証する。
論文 参考訳（メタデータ） (2025-04-15T18:00:00Z) - FreeBind: Free Lunch in Unified Multimodal Space via Knowledge Fusion [64.03178918148497]
マルチモーダル表現空間を基本単位として扱うアイデアであるFreeBindを提案する。
我々は「空間結合」を介して外部の専門家空間からの知識を統合する
FreeBindは、9つのデータセットにわたる5つのオーディオ-画像-テキストダウンストリームタスクにおいて、ImageBindよりも優れています。
論文 参考訳（メタデータ） (2024-05-08T08:32:34Z) - A Geometric Notion of Causal Probing [85.49839090913515]
線形部分空間仮説は、言語モデルの表現空間において、動詞数のような概念に関するすべての情報が線形部分空間に符号化されていることを述べる。
理想線型概念部分空間を特徴づける内在的基準のセットを与える。
2つの言語モデルにまたがる少なくとも1つの概念に対して、この概念のサブスペースは、生成された単語の概念値を精度良く操作することができる。
論文 参考訳（メタデータ） (2023-07-27T17:57:57Z) - Non-Isometric Quantum Error Correction in Gravity [0.0]
ダイラトン重力における蒸発ブラックホールのトイモデルにおいて,非等尺誤差補正符号のアンサンブルを構築し,検討した。
このような典型的コードは、ブラックホールのマイクロカノニカルヒルベルト空間次元において指数関数的に大きい状態の集合 S$ でペアの内積を保存する可能性が非常に高いことを示す。
論文 参考訳（メタデータ） (2022-10-24T18:00:00Z) - Continuous percolation in a Hilbert space for a large system of qubits [58.720142291102135]
パーコレーション遷移は無限クラスターの出現によって定義される。
ヒルベルト空間の指数的に増加する次元性は、有限サイズの超球面による被覆を非効率にすることを示す。
コンパクトな距離空間におけるパーコレーション遷移への我々のアプローチは、他の文脈での厳密な処理に有用である。
論文 参考訳（メタデータ） (2022-10-15T13:53:21Z) - Fully non-positive-partial-transpose genuinely entangled subspaces [0.0]
我々は、真に絡み合っただけでなく、完全に非正の部分空間(NPT)である多部部分空間の構成を提供する。
我々の構成は、量子エラー補正で知られている安定な形式主義に由来する。
論文 参考訳（メタデータ） (2022-03-31T09:11:16Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - Implicit Bias of Projected Subgradient Method Gives Provable Robust
Recovery of Subspaces of Unknown Codimension [12.354076490479514]
本稿では,DPCP (Dual principal Component Pursuit) が未知の部分空間次元の問題を確実に解決できることを示す。
プロジェクテッド・サブ段階降下法(PSGM)の複数インスタンスの実行に基づく,非常に単純なアルゴリズムを提案する。
特に、1)すべての問題インスタンスが部分空間のヌル空間のベクトルに収束し、2)問題インスタンスの解のアンサンブルが、部分空間のヌル空間に完全にまたがるほど十分に多様であることを示す。
論文 参考訳（メタデータ） (2022-01-22T15:36:03Z) - Self-testing maximally-dimensional genuinely entangled subspaces within
the stabilizer formalism [0.0]
我々は、与えられた安定化部分空間が真に絡み合っているかどうかを効率的にチェックできるフレームワークを導入する。
次に、真に絡み合った部分空間の最大次元を決定する。
我々は、これらの部分空間からの任意の絡み合った状態によって極大に違反するベルの不等式を構築する。
論文 参考訳（メタデータ） (2020-12-02T13:02:52Z) - Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。
特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。
提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
論文 参考訳（メタデータ） (2020-11-02T14:59:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。