論文の概要: On the pseudorandomness of simple quantum processes

• arxiv url: http://arxiv.org/abs/2610.02100v1
• Date: Thu, 01 Oct 2026 17:26:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.331756
• Title: On the pseudorandomness of simple quantum processes
• Title（参考訳）: 単純量子過程の擬ランダム性について
• Abstract要約: ガウワーズは、局所的なランダムな操作を繰り返し構成すると、ランダムとは区別できない大域的な置換が得られると推測した。 ユニタリデザインの形での統計的モーメントマッチングは、一般に擬似ランダム性に繋がらないことを示す。 次に、ランダム量子回路のような単純な量子過程において、擬似ランダム性がどのように出現するかという新しい予想を提案する。
• 参考スコア（独自算出の注目度）: 44.343357884926206
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Can simple processes appear highly complex? Gowers (Comb. Prob. Comp. '96) conjectured that repeatedly composing local random reversible operations can yield global permutations that are indistinguishable from random. In this work, we study the unitary quantum analog of this question, in an attempt to make new progress on this longstanding conjecture. Our first result shows that statistical moment matching in the form of unitary designs does not generically lead to pseudorandomness---even for the simplest quantum processes: for every fixed $t$, we give an efficiently samplable family $\{ν_n\}_n$ of distributions on one- and two-qubit gates such that, after $T=O_t(n^2\log^2 n)$ independent steps, the resulting $n$-qubit ensemble is an approximate unitary $t$-design with negligible error $\exp(-Ω(\log^2 n))$, yet an efficient quantum algorithm distinguishes it from random using only $O_t(\log^2 n)$ queries. This refutes the unitary analog of the Hoory--Magen--Myers--Rackoff conjecture (ICALP '04) for permutations. Our second result is a stronger separation between unitary designs and pseudorandom unitaries at polynomially bounded moments; our counterexample, however, requires highly structured ensembles, in contrast with the simple local walks from before. This suggests caution when using unitary designs to model information scrambling in black-hole physics, as even maximally scrambled systems can exhibit structure which is accessible to efficient experiments. Motivated by these findings, we then propose new conjectures for how pseudorandomness can plausibly emerge within simple quantum processes, such as random quantum circuits.
• Abstract（参考訳）: 単純なプロセスは非常に複雑に見えますか? Gowers (Comb. Comp. '96) は、局所的ランダム可逆演算を繰り返し構成することは、ランダムと区別できない大域的な置換をもたらすと推測した。 本研究では,この問題のユニタリ量子アナログについて研究し,この長年の予想に新たな進展をもたらす試みを行う。 固定されたすべての$t$に対して、効率よくサンプリング可能なファミリー $\{ν_n\}_n$ を 1-および 2-キュービットゲート上の分布として与え、例えば、$T=O_t(n^2\log^2 n) の独立ステップの後、結果として生じる$n$-qubit アンサンブルは、無視可能な誤差 $\exp(-Ω(\log^2 n)$ の近似ユニタリ $t$-design である。 これはホリー--マゲン--マイヤーズ--ラックオフ予想 (ICALP '04) の置換に対するユニタリ類似性を否定する。 第二の結果は、多項式的に有界な瞬間におけるユニタリデザインと擬似ランダムユニタリの分離がより強くなり、反例は、以前の単純な局所ウォークとは対照的に、高度に構造化されたアンサンブルを必要とする。 このことは、ブラックホール物理学で衝突する情報をモデル化するためにユニタリ設計を使用することに注意を喚起する。 これらの発見に触発されて、ランダム量子回路のような単純な量子過程において、擬似ランダム性がどのように出現するかという新たな予想が提案される。

関連論文リスト

• Unconditional Pseudorandomness against Shallow Quantum Circuits [13.400821866479635]
  我々は、浅い深度量子回路クラスに対して、無条件で効率的な擬似ランダム構造を初めて確立する。 我々の研究は、制限された敵の自然クラスに対して、量子計算の擬似ランダム性を無条件で達成できることを実証している。
  論文  参考訳（メタデータ） (2025-07-24T20:33:26Z)
• Real-Valued Somewhat-Pseudorandom Unitaries [5.294604210205507]
  実数値ユニタリは完全に擬似ランダムとは言えなくても、実数値ユニタリを諦めることなく、いくつかの擬似ランダム特性を得ることができることを示す。 我々の分析は、ランダムな(バイナリ)フェーズとランダムな計算ベイシスの置換を適用すると、さらに単純な構成になることを示している。
  論文  参考訳（メタデータ） (2024-03-25T12:37:50Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
  暗号擬似乱数量子状態と擬似乱数ユニタリ変換が存在することを示す。 本稿では、暗号、複雑性理論、量子トモグラフィーにおけるこれらの結果の影響について論じる。
  論文  参考訳（メタデータ） (2021-03-16T20:54:12Z)
• 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)

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

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