論文の概要: Quantum Pseudorandomness and Classical Complexity

• arxiv url: http://arxiv.org/abs/2103.09320v4
• Date: Mon, 26 Feb 2024 16:11:01 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-29 01:31:27.434406
• Title: Quantum Pseudorandomness and Classical Complexity
• Title（参考訳）: 量子擬似性と古典的複雑度
• Authors: William Kretschmer
• Abstract要約: 暗号擬似乱数量子状態と擬似乱数ユニタリ変換が存在することを示す。 本稿では、暗号、複雑性理論、量子トモグラフィーにおけるこれらの結果の影響について論じる。
• 参考スコア（独自算出の注目度）: 0.08158530638728499
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We construct a quantum oracle relative to which $\mathsf{BQP} = \mathsf{QMA}$ but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct pseudorandom states, by proving that pseudorandom states do not exist if $\mathsf{BQP} = \mathsf{PP}$. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
• Abstract（参考訳）: 私たちは、$\mathsf{bqp} = \mathsf{qma}$であるが、暗号的擬似乱数量子状態と擬似乱数ユニタリ変換が存在する量子オラクルを構築し、疑似乱数状態が量子マーリン=アーサーの敵によって「ブローク」できるという事実から直観に反する結果を得る。 このニュアンスは、量子入力と古典入力を演算するアルゴリズムの区別の結果、どのように生じるかを説明する。 一方, 擬似乱数状態を構成するためには, $\mathsf{bqp} = \mathsf{pp}$ のとき, 擬似乱数状態が存在しないことを証明し, 計算複雑性の仮定が必要であることを示した。 我々は、これらの結果が暗号、複雑性理論、量子トモグラフィに与える影響について論じる。

関連論文リスト

• Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
  古典的なオラクルを構築し、$mathsfP = MathsfNP$, but quantum-computable quantum-secure trapdoor one-way function が存在する。 この結果から,複数コピーの擬似乱数状態と擬似乱数ユニタリー,古典通信の公開鍵暗号,シグネチャ,暗黙の転送方式が示唆された。
  論文  参考訳（メタデータ） (2024-11-04T19:40:01Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  我々は、ハミルトニアン相状態(HPS)問題と呼ばれる量子硬度仮定を導入する。 我々は、我々の仮定が少なくとも完全に量子的であることを示し、すなわち片方向関数を構成するのに使用できない。 仮定とその変形により、多くの擬似ランダム量子プリミティブを効率的に構築できることを示す。
  論文  参考訳（メタデータ） (2024-10-10T16:10:10Z)
• A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
  ランダムなオラクルから構築した擬似乱数発生器(PRG)の(量子)セキュリティについて検討する。 我々は、大まかに言えば、そのようなPRGが、ランダムなオラクルに対して無条件に多くのクエリを結び付ける古典的敵に対して無条件に安全であるならば、同じ意味で(無条件で)量子的敵に対して安全であることを示す「持ち上げ定理」を証明している。
  論文  参考訳（メタデータ） (2024-01-25T17:13:51Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Pseudorandom Strings from Pseudorandom Quantum States [6.79244006793321]
  量子世界と古典世界における擬似ランダム性の概念の関連について研究する。 量子擬似乱数発生器(QPRGs)と呼ばれる擬似乱数発生器の自然変種は対数出力長PSRGsの存在に基づいていることを示す。 また、擬似乱数関数のような状態生成器と擬似乱数関数の関係についても検討する。
  論文  参考訳（メタデータ） (2023-06-09T01:16:58Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Pseudoentanglement [4.3053817709507]
  エンタングルメント(英: Entanglement)は、古典計算におけるランダムネスに類似した量子資源である。 カット毎に$log n$ に近い絡み合いエントロピーを持つ擬アンタングル状態の構成を与える。 本稿では, マトリックス製品状態試験, エンタングルメント蒸留, およびAdS/CFT対応の複雑さへの応用について論じる。
  論文  参考訳（メタデータ） (2022-11-01T21:04:49Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。