論文の概要: The quantum smooth label cover problem is undecidable
- arxiv url: http://arxiv.org/abs/2510.03477v1
- Date: Fri, 03 Oct 2025 19:54:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-07 16:52:59.063166
- Title: The quantum smooth label cover problem is undecidable
- Title（参考訳）: 量子スムーズなラベル被覆問題は決定不能である
- Authors: Eric Culf, Kieran Mastel, Connor Paddock, Taro Spirig,
- Abstract要約: 量子スムーズなラベル被覆問題はRe-hardであることを示す。
これは、Kempe, Regev, and Toner (FOCS'08) によって効率的に決定できる量子ユニークなラベルカバー問題とは対照的である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that the quantum smooth label cover problem is RE-hard. This contrasts with the quantum unique label cover problem, which can be decided efficiently by Kempe, Regev, and Toner (FOCS'08). 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 also RE-hard. This aligns with the alternative quantum unique games conjecture on the RE-hardness of the quantum oracularized unique label cover problem proposed by Mousavi and Spirig (ITCS'25). Our techniques employ a series of reductions from the halting problem to the quantum smooth label cover problem, and include a quantum-sound version of Feige's reduction from 3SAT to 3SAT5 (STOC'96), which may be of independent interest.
- Abstract（参考訳）: 量子スムーズなラベル被覆問題はRe-hardであることを示す。
これは、Kempe, Regev, and Toner (FOCS'08) によって効率的に決定できる量子ユニークなラベルカバー問題とは対照的である。
MIP* = RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21。
さらに、量子オラクル化スムーズなラベル被覆問題もREハードであることを示す。
これは、Mousavi and Spirig (ITCS'25) が提唱した量子正則化ユニークなラベル被覆問題(英語版)(quantum oracularized unique label cover problem)のRe-hardnessに関する代替量子一意ゲーム予想と一致する。
本手法では, 停止問題から量子スムーズなラベル被覆問題への一連の還元と, 独立性のある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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。