論文の概要: Learning Random Quantum Circuits and the Emergence of Pseudorandomness
- arxiv url: http://arxiv.org/abs/2609.39821v1
- Date: Wed, 30 Sep 2026 14:24:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:27.886484
- Title: Learning Random Quantum Circuits and the Emergence of Pseudorandomness
- Title（参考訳）: ランダム量子回路の学習と擬似ランダム性の創発
- Abstract要約: 全ゼロ入力に$U$を適用することで得られる出力状態のコピーのみを用いてランダムな量子回路を学習するための効率的なアルゴリズムを提供する。
ランダムな$2ell$-qubitゲートを持つ$n$サイトの深さ$d$回路に対して、アルゴリズムは、任意の定次元格子に対して$textpoly(n,2ell d)$時間で高い確率で元の回路$U$を学習する。
- 参考スコア（独自算出の注目度）: 2.8640809297516747
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give an efficient algorithm for learning $k$-dimensional brickwork random quantum circuits using only copies of the output state obtained by applying $U$ to the all-zero input. For a depth-$d$ circuit on $n$ sites with random $2\ell$-qubit gates, the algorithm learns the original circuit $U$ with high probability in $\text{poly}(n,2^{\ell d})$ time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as $\ell d = O(\log n)$. In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require $\ell d=ω(\log n)$, and structured cryptographic constructions suggest that this scale may be achievable from above. In higher dimensions, it remains plausible that the same $\ell d=ω(\log n)$ scale remains the threshold for ancilla-free pseudorandomness, and our results help clarify the conditions under which pseudorandomness can arise in this setting. The main idea behind our algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches. A key technical ingredient is a Carbery-Wright type anticoncentration inequality for low-degree polynomials of Haar random unitaries whose small-ball exponent is independent of the matrix dimension. The dimension-independent exponent is crucial for handling gates of growing locality. This anticoncentration result may also be of independent interest.
- Abstract（参考訳）: 全ゼロ入力に$U$を適用することで得られる出力状態のコピーのみを用いて、$k$のブロックワークランダムな量子回路を学習するための効率的なアルゴリズムを提供する。
ランダムな$2\ell$-qubitゲートを持つ$n$サイトの深さ$d$回路に対して、アルゴリズムは任意の定次元格子に対して$\text{poly}(n,2^{\ell d})$時間で高い確率で元の回路$U$を学習する。
特に、アルゴリズムは$\ell d = O(\log n)$ の多項式時間である。
擬ランダム状態は$\ell d=ω(\log n)$を必要とし、構造化された暗号構造は、このスケールが上から達成可能であることを示唆している。
より高次元では、同じ$\ell d=ω(\log n)$スケールがアンシラのない擬似ランダム性のしきい値であり続けることが証明され、この設定で擬似ランダム性が発生する条件を明らかにするのに役立つ。
アルゴリズムの背後にある主要な考え方は、最終層のゲートを、後方の光円錐全体を学ぶことなく識別し、以前のアプローチのボトルネックを避ける、局所的な相関基準である。
重要な技術的要素は、小さな球指数が行列次元に依存しないハールランダムユニタリの低次多項式に対するカーベリー・ライト型反集中不等式である。
次元非依存指数は、局所性の増大するゲートを扱うために重要である。
この反濃縮結果は、独立的な関心事でもあるかもしれない。
関連論文リスト
- Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。
我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文 参考訳（メタデータ） (2026-09-30T17:51:21Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。
我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
論文 参考訳（メタデータ） (2024-04-25T17:08:34Z) - Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。
純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。
本稿では,総和,数,投票の単純な統計量について両問題を解く。
論文 参考訳（メタデータ） (2023-09-27T17:09:36Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳（メタデータ） (2023-09-15T14:01:13Z) - On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Approximate unitary $t$-designs by short random quantum circuits using
nearest-neighbor and long-range gates [0.0]
ply(t)cdot n1/D$-depth local random quantum circuits with two qudit Near-ighbor gates are almost $t$-designs in various measures。
また,異なるモデルを用いた深度O(log(n)loglog(n)において,反濃縮が可能であることを証明した。
論文 参考訳（メタデータ） (2018-09-18T22:28:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。