論文の概要: Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity
- arxiv url: http://arxiv.org/abs/2609.02687v1
- Date: Wed, 02 Sep 2026 14:54:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-03 17:53:18.423923
- Title: Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity
- Title（参考訳）: 量子メタ複雑度は、時間境界のコルモゴロフ複雑度によるワンウェイプッズのキャラクタリゼーション
- Abstract要約: 量子暗号の時間境界メタ複雑化プログラムを開始する。
最近の研究は、ワンウェイ関数を持たない量子暗号の最小探索プリミティブであるワンウェイパズルを特徴づけている。
- 参考スコア（独自算出の注目度）: 0.30458514384586394
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We initiate the time-bounded meta-complexity program for quantum cryptography. Recent work characterizes one-way puzzles, the minimal search primitive of quantum cryptography without one-way functions, by the average-case hardness of approximating the plain, uncomputable Kolmogorov complexity over quantumly samplable distributions; the classical program of Liu and Pass, by contrast, lives at polynomial time bounds. We define a probabilistic time-bounded quantum program complexity pKq^t for classical strings and prove two unconditional theorems. First, a quantum coding theorem: any string output by a quantum polynomial-time sampler with probability delta admits a description of the information-theoretically optimal length log(1/delta) plus logarithmic terms, decodable by a quantum machine in time O(sqrt(1/delta)) times a polynomial, via amplitude amplification over the coherently executed sampler. Second, an exact characterization at subexponential time: one-way puzzles exist if and only if the gap problem for pKq at time bound 2^(n/2) poly(n) is weakly quantum-average-hard, refining the plain-complexity characterizations. We then isolate the polynomial-time coding theorem as the single load-bearing open conjecture of the program, prove that it implies the full polynomial-time characterization, analyze why the classical derandomization proof resists quantization, and formulate a relativized barrier conjecture delimiting string-valued meta-complexity at one-way puzzles. Conjectures are labeled as such throughout.
- Abstract（参考訳）: 量子暗号の時間境界メタ複雑化プログラムを開始する。
最近の研究は、量子的にサンプリング可能な分布上の平易で計算不能なコルモゴロフ複雑性を近似する平均的なケース硬さによって、一方向関数のない量子暗号の最小探索プリミティブであるワンウェイパズルを特徴づけている。
古典弦に対する確率論的時間有界量子プログラム複雑性 pKq^t を定義し、2つの無条件定理を証明した。
第一に、確率デルタを持つ量子多項式時間サンプリング器によって出力される任意の文字列は、情報理論的に最適な長さのログ(1/delta)と対数項の記述を認め、これは多項式の時間 O(sqrt(1/delta)) の時間 O(sqrt(1/delta)) で多項式の振幅増幅を行う。
第二に、一方向パズルが存在するのは、pKq の時間境界 2^(n/2) ポリ(n) のギャップ問題が弱量子平均ハードであることと、平複素性特徴づけを洗練することである。
次に、多項式時間符号化定理をプログラムの単一負荷付き開予想として分離し、この定理が完全多項式時間特性を示すことを証明し、古典的なデランドマイズ証明が量子化に抵抗する理由を解析し、一方のパズルにおいて文字列値のメタ錯体を除いた相対的バリア予想を定式化する。
コンジェクターは、至る所でそのようにラベル付けされる。
関連論文リスト
- Verifiable quantum advantage in extremely low depth [52.51019642214249]
浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。
浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
論文 参考訳（メタデータ） (2026-09-01T15:54:34Z) - A Meta-Complexity Characterization of Quantum Cryptography [2.8311451575532156]
量子暗号プリミティブの最初のメタ複雑性のキャラクタリゼーションを証明した。
片方向パズルが存在することは、カルモゴロフ複雑性を近似することが困難であるような二進弦の量子サンプリング可能な分布が存在する場合に限る。
論文 参考訳（メタデータ） (2024-10-07T12:29:27Z) - 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) - Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions [0.0]
我々は、高速量子再帰と呼ばれる量子再帰の基本形式を導入し、初等量子関数の$EQS$を定式化する。
このクラスは、BQPOLYLOGTIMEという複雑性クラスを形成する、正確に量子多対数時間計算可能性を取得する。
また、よく知られた分割・分散戦略を実装するアルゴリズム的スキームについても検討する。
論文 参考訳（メタデータ） (2023-11-27T14:53:45Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。