Fugu-MT 論文翻訳(概要): Fine-Grained Complexity via Quantum Natural Proofs

論文の概要: Fine-Grained Complexity via Quantum Natural Proofs

arxiv url: http://arxiv.org/abs/2504.10363v1
Date: Mon, 14 Apr 2025 16:09:55 GMT
ステータス: 翻訳完了
システム内更新日: 2025-04-15 16:49:29.726143
Title: Fine-Grained Complexity via Quantum Natural Proofs
Title（参考訳）: 量子自然証明による微細結晶複雑度
Authors: Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian Speelman,
Abstract要約: 圧縮不能な性質を必要とするQSETH予想の一部は、量子セキュアな擬ランドム関数の存在を仮定することで、多くの場合どのように置き換えられるかを示す。
参考スコア（独自算出の注目度）: 5.306949367777188
License:
Abstract: Buhrman, Patro, and Speelman presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it the QSETH framework. In this paper, using a notion of quantum natural proofs (built from natural proofs introduced by Razborov and Rudich), we show how part of the QSETH conjecture that requires properties to be `compression oblivious' can in many cases be replaced by assuming the existence of quantum-secure pseudorandom functions, a standard hardness assumption. Combined with techniques from Fourier analysis of Boolean functions, we show that properties such as PARITY and MAJORITY are compression oblivious for certain circuit class $\Lambda$ if subexponentially secure quantum pseudorandom functions exist in $\Lambda$, answering an open question in [Buhrman-Patro-Speelman 2021].
Abstract（参考訳）: バーマン、パトロ、スピールマンは強い指数時間仮説とその変項の量子アナログを形成する予想の枠組みを提示した。彼らはこれをQSETHフレームワークと呼んだ。本稿では、量子自然証明(Razborov と Rudich が導入した自然証明から構築した)の概念を用いて、特性を '圧縮不能' とする QSETH 予想の一部が、標準硬度仮定である量子セキュア擬似ランダム関数の存在を仮定することで、多くの場合においてどのように置き換えられるかを示す。ブール関数のフーリエ解析の手法と組み合わせて、PARITY や MAJORITY のような性質は、ある回路クラス $\Lambda$ に対して圧縮不能であることが示される。

関連論文リスト

Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
近年の分離により、階層構造が崩壊しても持続する硬さの源から量子暗号を構築する可能性が高まっている。量子暗号は、$mathsfP#P notsubseteq mathsf(io)BQP/qpoly$という非常に穏やかな仮定に基づいている。
論文参考訳（メタデータ） (2024-09-23T17:45:33Z)
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文参考訳（メタデータ） (2024-02-29T01:35:46Z)
A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
ランダムなオラクルから構築した擬似乱数発生器(PRG)の(量子)セキュリティについて検討する。我々は、大まかに言えば、そのようなPRGが、ランダムなオラクルに対して無条件に多くのクエリを結び付ける古典的敵に対して無条件に安全であるならば、同じ意味で(無条件で)量子的敵に対して安全であることを示す「持ち上げ定理」を証明している。
論文参考訳（メタデータ） (2024-01-25T17:13:51Z)
On Kirkwood--Dirac quasiprobabilities and unravelings of quantum channel assigned to a tight frame [0.0]
与えられた強フレームのベクトルを使って主クラウス作用素を構築すると、興味深い性質を持つ準確率が生成される。固有値の位置を特徴付けるための新しい不等式が導出される。提示された不等式の効用は、次元2における対称的な情報的完備な測定で例示される。
論文参考訳（メタデータ） (2023-04-27T09:11:11Z)
Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文参考訳（メタデータ） (2023-03-02T14:18:17Z)
Why we should interpret density matrices as moment matrices: the case of (in)distinguishable particles and the emergence of classical reality [69.62715388742298]
一般確率論として量子論(QT)の定式化を導入するが、準観測作用素(QEOs)で表される。区別不可能な粒子と識別不能な粒子の両方に対するQTをこの方法で定式化できることを示します。古典的なダイスに対する有限交換可能な確率は、QTと同じくらい奇数であることを示す。
論文参考訳（メタデータ） (2022-03-08T14:47:39Z)
Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文参考訳（メタデータ） (2021-07-05T17:45:41Z)
Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
Zhandryは、量子クエリアルゴリズムとランダム関数に対応する量子オラクルの間の相互作用を研究した。オラクルがランダム関数の代わりにランダムな置換に対応する場合にも同様の解釈を導入する。乱数関数と乱数置換の両方がセキュリティ証明において極めて重要であるため、本フレームワークが量子暗号に応用されることを期待する。
論文参考訳（メタデータ） (2021-03-16T11:05:48Z)
Quantum Chaos and the Spectrum of Factoring [0.9023847175654603]
離散値のみを取る関数である$E$は、磁気トラップにおける電荷の制限系からのエネルギーの類似であることを示す。これは、量子力学と数論を結びつける量子ファクタリングシミュレータ仮説である。
論文参考訳（メタデータ） (2020-08-24T19:40:28Z)
A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
論文参考訳（メタデータ） (2019-09-04T11:46:26Z)
Quantum-secure message authentication via blind-unforgeability [74.7729810207187]
我々は、ブラインド・アンフォージェビリティ(英語版)と呼ばれる量子敵に対する非フォージェビリティ(英語版)の自然な定義を提案する。この概念は、予測値に「部分的に盲目」アクセスを使用できる敵が存在する場合、関数を予測可能と定義する。標準構造と減量支援のためのブラインド・アンフォージェビリティの適合性を示す。
論文参考訳（メタデータ） (2018-03-10T05:31:38Z)

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