論文の概要: 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}$ のとき, 擬似乱数状態が存在しないことを証明し, 計算複雑性の仮定が必要であることを示した。
我々は、これらの結果が暗号、複雑性理論、量子トモグラフィに与える影響について論じる。
関連論文リスト
- Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Derandomization of quantum algorithm for triangle finding [0.0]
デランドマイゼーション(英: Derandomization)とは、ランダム化アルゴリズムを決定論的アルゴリズムに変換する過程である。
量子コンピューティングでは、量子力学の本質的なランダム性のため、量子アルゴリズムのデランドマイズが困難で興味深い。
グラフが少なくとも1つのターゲット三角形を含むと約束されているとき、その三角形が存在する場合や、存在しない場合は「三角形」を出力しないような決定論的量子アルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2023-09-23T05:24:59Z) - 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 Cryptography in Algorithmica [0.7524721345903025]
ブラックボックス設定では、一方の関数が存在しなくても擬似ランダム状態に基づく量子暗号が可能であることを示す。
また、我々の結果をマルチコピー安全な擬似ランダム状態に一般化する予想も導入する。
論文 参考訳(メタデータ) (2022-12-01T21:33:38Z) - 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) - Cryptography from Pseudorandom Quantum States [6.164147034988822]
片道関数は擬似ランダム状態の存在を暗示するが、Kretschmer (TQC'20) は最近、一方通行関数が存在しないが擬似ランダム状態が存在するという相対的なオラクルを構築した。
疑似ランダム状態における興味深い暗号タスクの基盤となる可能性について検討する。
a)の結果として、疑似ランダム状態は不正にセキュアなマルチパーティプロトコルを構築するのに十分である。
論文 参考訳(メタデータ) (2021-12-18T22:53:16Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳(メタデータ) (2021-07-05T17:45:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。