論文の概要: Unconditional Pseudorandomness against Shallow Quantum Circuits
- arxiv url: http://arxiv.org/abs/2507.18796v1
- Date: Thu, 24 Jul 2025 20:33:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-28 16:16:48.751414
- Title: Unconditional Pseudorandomness against Shallow Quantum Circuits
- Title（参考訳）: 浅量子回路に対する無条件擬似的擬似性
- Authors: Soumik Ghosh, Sathyawageeswar Subramanian, Wei Zhan,
- Abstract要約: 我々は、浅い深度量子回路クラスに対して、無条件で効率的な擬似ランダム構造を初めて確立する。
我々の研究は、制限された敵の自然クラスに対して、量子計算の擬似ランダム性を無条件で達成できることを実証している。
- 参考スコア（独自算出の注目度）: 13.400821866479635
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that: $\bullet$ Any quantum state 2-design yields unconditional pseudorandomness against both $\mathsf{QNC}^0$ circuits with arbitrarily many ancillae and $\mathsf{AC}^0\circ\mathsf{QNC}^0$ circuits with nearly linear ancillae. $\bullet$ Random phased subspace states, where the phases are picked using a 4-wise independent function, are unconditionally pseudoentangled against the above circuit classes. $\bullet$ Any unitary 2-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $\mathsf{QNC}^0$ adversaries, even with limited $\mathsf{AC}^0$ postprocessing. Our indistinguishability results for 2-designs stand in stark contrast to the standard setting of quantum pseudorandomness against $\mathsf{BQP}$ circuits, wherein they can be distinguishable from Haar random ensembles using more than two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.
- Abstract（参考訳）: 量子計算の擬似ランダム性は、複雑性理論、暗号、基礎物理学とのつながりにまたがる基本的な概念として登場した。
しかし、効率的な量子セキュアな擬似ランダムオブジェクトのすべての既知の構成は、複雑性理論の仮定に依存している。
本研究では、浅層量子回路クラスに対する非条件で安全な擬似ランダム構造を初めて確立する。
任意の量子状態 2-設計は、任意の多くのアンシラを持つ$\mathsf{QNC}^0$回路と、ほぼ線形アンシラを持つ$\mathsf{AC}^0\circ\mathsf{QNC}^0$回路の両方に対して無条件の擬似ランダム性をもたらす。
$\bullet$ランダム位相部分空間状態では、位相は4次元独立関数を使って選択され、上記の回路クラスに対して無条件に擬似絡み合わされる。
$\bullet$ 任意のユニタリ2-設計は、幾何的に局所的な $\mathsf{QNC}^0$ に対して無条件に保護された並列クエリの擬似ランダムなユニタリをもたらす。
量子擬似ランダム性の標準的な設定は$\mathsf{BQP}$回路とは対照的であり、2つのコピーやクエリを使ってハールランダムアンサンブルと区別することができる。
我々の研究は、量子計算の擬似ランダム性は、制限された敵の自然なクラスに対して無条件に達成できることを示し、量子複雑性理論における新しい方向を開く。
関連論文リスト
- Entanglement dynamics and Page curves in random permutation circuits [0.0]
計算基底をランダムに透過する量子回路によって生成されるアンサンブルについて検討する。
本研究は,多体システムにおけるエンタングルメント生成における古典的特徴の影響を明らかにするものである。
論文 参考訳（メタデータ） (2025-05-09T16:09:48Z) - How to Construct Random Unitaries [2.8237889121096034]
量子セキュアな片方向関数が存在すると仮定して、PRUが存在することを証明する。
本研究では,Haar-randomユニタリに対するクエリを量子コンピュータ上で効率的にシミュレートできることを証明した。
論文 参考訳（メタデータ） (2024-10-14T03:07:36Z) - Pseudorandom unitaries with non-adaptive security [43.15464425520681]
本稿では、ランダムなクリフォードユニタリ、擬似乱数二相演算子、擬似乱数置換演算子の結合であるPRU構成を提案する。
このPRU構造は、量子セキュア片方向関数の存在を前提として、非適応微分器に対して安全であることを示す。
論文 参考訳（メタデータ） (2024-02-22T18:56:37Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Fast pseudorandom quantum state generators via inflationary quantum gates [3.5072186061740904]
本研究では,浅い対数n深度量子回路を用いて,Haarランダムと計算的に区別できない擬似ランダム量子状態に到達するための機構を提案する。
IQゲートは2量子ゲートで実装することはできないが、$U(d2)$の2量子ゲートのサブセットとして$dge 3$と$d$ Primeを持つか、特別な3量子ゲートとして実現することができる。
論文 参考訳（メタデータ） (2023-04-19T18:00:01Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
暗号擬似乱数量子状態と擬似乱数ユニタリ変換が存在することを示す。
本稿では、暗号、複雑性理論、量子トモグラフィーにおけるこれらの結果の影響について論じる。
論文 参考訳（メタデータ） (2021-03-16T20:54:12Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z) - Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
ランダム量子回路は古典的にシミュレートするのは難しいと見なされる。
典型例の近似シミュレーションは, 正確なシミュレーションとほぼ同程度に困難であることを示す。
また、十分に浅いランダム回路はより一般的に効率的にシミュレーション可能であると推測する。
論文 参考訳（メタデータ） (2019-12-31T19:00:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。