論文の概要: The quantum smooth label cover problem is undecidable
- arxiv url: http://arxiv.org/abs/2510.03477v3
- Date: Wed, 05 Nov 2025 18:36:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-06 20:32:09.421358
- Title: The quantum smooth label cover problem is undecidable
- Title（参考訳）: 量子スムーズなラベル被覆問題は決定不能である
- Authors: Eric Culf, Kieran Mastel, Connor Paddock, Taro Spirig,
- Abstract要約: 量子スムーズなラベル被覆問題は決定不能であり、再決定的であることを示す。
一方,本研究の結果は量子ラベル被覆問題のre-hardnessと一致している。
我々の証明手法は、BCSMIP*-プロトコールに対するフェイジの3SATから3SAT5への還元の量子バージョンを含む。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a result of Kempe, Regev, and Toner (FOCS'08). On the other hand, our result aligns with the RE-hardness of the quantum label cover problem, which follows from the celebrated MIP* = RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21). Additionally, we show that the quantum oracularized smooth label cover problem is RE-hard. Our second result fits with the alternative quantum unique games conjecture recently proposed by Mousavi and Spirig (ITCS'25) on the RE-hardness of the quantum oracularized unique label cover problem. Our proof techniques include a quantum version of Feige's reduction from 3SAT to 3SAT5 (STOC'96) for BCSMIP*-protocols, which may be of independent interest.
- Abstract（参考訳）: 量子スムーズなラベル被覆問題は決定不可能で、再決定的であることを示す。
これは、Kempe、Regev、Toner (FOCS'08) の結果として効率的に決定できる量子ユニークなラベルカバー問題とは対照的である。
一方, 量子ラベル被覆問題の結果は, Ji, Natarajan, Vidick, Wright, Yuen (ACM'21) によるMIP* = REの結果と一致する。
さらに、量子オラクル化スムーズなラベルカバー問題は、REハードであることを示す。
第2の結果は、Mousavi と Spirig (ITCS'25) が最近提案した量子論理化ユニークなラベル被覆問題の RE-hardness に関する代替量子一意ゲーム予想と一致する。
我々の証明手法には、BCSMIP*-プロトコールに対するファイジの3SATから3SAT5(STOC'96)への還元の量子バージョンが含まれており、これは独立した関心を持つ可能性がある。
関連論文リスト
- A Quantum Unique Games Conjecture [0.0]
本稿では,ラベル・コーバーとユニク・ラベル・コーヴァーの量子拡張の定義を紹介する。
これらの問題は、古典的な設定で行うように、量子制約満足度問題の非近似性を研究する上でも同様に重要な役割を果たすことを示す。
論文 参考訳（メタデータ） (2024-09-30T07:34:41Z) - Quantum paving: When sphere packings meet Gabor frames [3.05179671246628]
量子パビングは、量子パッキングと量子被覆の両方を同時に最適化することを目的としている。
特定の場合における解を示し、量子舗装に関するいくつかの予想を述べ、いくつかの応用について議論する。
論文 参考訳（メタデータ） (2024-08-16T18:56:11Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Quantum soft-covering lemma with applications to rate-distortion coding, resolvability and identification via quantum channels [7.874708385247353]
我々は、スムーズなミンエントロピーの観点から、ワンショット量子被覆補題を証明した。
量子チャネルの非制限および同時識別能力に新たな上限を与える。
論文 参考訳（メタデータ） (2023-06-21T17:53:22Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum information spreading in a disordered quantum walk [50.591267188664666]
量子ウォークスを用いて量子情報拡散パターンを探索する量子探索プロトコルを設計する。
我々は、異常や古典的輸送を調査するために、コヒーレントな静的および動的障害に焦点を当てる。
以上の結果から,複雑なネットワークで発生する欠陥や摂動の情報を読み取る装置として,量子ウォーク(Quantum Walk)が考えられる。
論文 参考訳（メタデータ） (2020-10-20T20:03:19Z) - Using Quantum Metrological Bounds in Quantum Error Correction: A Simple
Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
本稿では、量子誤り訂正符号の品質と、論理ゲートの普遍的な集合を達成する能力とを結びつける、近似したイージン・クニル定理の証明を示す。
我々の導出は、一般的な量子気象プロトコルにおける量子フィッシャー情報に強力な境界を用いる。
論文 参考訳（メタデータ） (2020-04-24T17:58:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。