論文の概要: Random unitaries in extremely low depth
- arxiv url: http://arxiv.org/abs/2407.07754v2
- Date: Sat, 04 Jan 2025 09:19:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-07 17:02:02.311177
- Title: Random unitaries in extremely low depth
- Title（参考訳）: 極低深さにおけるランダムユニタリ
- Authors: Thomas Schuster, Jonas Haferkamp, Hsin-Yuan Huang,
- Abstract要約: 1D線を含む任意の幾何学上のランダム量子回路は、$log n$ 深さで$n$ qubits以上の近似ユニタリな設計をすることができることを証明している。
同様の方法で、1D回路では$textpoly(log n)$ depthで、全接続回路では$textpoly(log log n)$ depthで$textpoly(log log n)$ depthで擬似ランダムユニタリ(PRU)を構築する。
- 参考スコア（独自算出の注目度）: 0.8680580889074451
- License:
- Abstract: We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over $n$ qubits in $\log n$ depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in $\text{poly}(\log n)$ depth, and in all-to-all-connected circuits in $\text{poly}(\log \log n)$ depth. In all three cases, the $n$ dependence is optimal and improves exponentially over known results. These shallow quantum circuits have low complexity and create only short-range entanglement, yet are indistinguishable from unitaries with exponential complexity. Our construction glues local random unitaries on $\log n$-sized or $\text{poly}(\log n)$-sized patches of qubits to form a global random unitary on all $n$ qubits. In the case of designs, the local unitaries are drawn from existing constructions of approximate unitary $k$-designs, and hence also inherit an optimal scaling in $k$. In the case of PRUs, the local unitaries are drawn from existing PRU constructions. Applications of our results include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.
- Abstract（参考訳）: 1D線を含む任意の幾何学上のランダムな量子回路は、深さ$\log n$$$で$n$ qubits以上の近似ユニタリな設計をすることができることを証明している。
同様に、1D回路では$\text{poly}(\log n)$ depth、全接続回路では$\text{poly}(\log \log n)$ depth で擬似ランダムユニタリ(PRU)を構成する。
3つのケースすべてにおいて、$n$依存は最適であり、既知の結果よりも指数関数的に改善される。
これらの浅い量子回路は複雑さが低く、短距離の絡み合いしか生じないが、指数複雑性を持つユニタリとは区別できない。
我々の構成は、$\log n$-sized または $\text{poly}(\log n)$-sized qubits のパッチに局所乱ユニタリを貼り付け、すべての$n$ qubits 上の大域的乱ユニタリを形成する。
設計の場合、局所ユニタリは、およそ$k$-設計の既存の構成から引き出され、従って$k$の最適スケーリングを継承する。
PRUの場合、既存のPRU構造から局所的なユニタリが引き出される。
本研究の応用例としては,1次元ログ深度クリフォード回路を用いた古典的影が深部回路と同等に強力であることの証明,低複雑性物理系学習における超ポリノミカル量子の優位性を示すこと,およびトポロジカル秩序による物質相の認識のための量子硬度を確立することなどが挙げられる。
関連論文リスト
- Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits [12.786353781073242]
我々は、一元的ハール測度に対するカーベリーライトスタイルの反集中不等式を証明した。
ランダム量子回路のスクランブル速度が低いことを示す。
論文 参考訳（メタデータ） (2024-07-28T19:10:46Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Does qubit connectivity impact quantum circuit complexity? [5.908927557774895]
量子コンピューティングのいくつかの物理的実装スキームは、特定の量子ビットのペアにのみ2量子ゲートを適用することができる。
本稿では、$O(4n)$ depthと$O(4n)$ sizeの量子回路により、すべての$n$-qubitユニタリ演算を実装可能であることを示す。
論文 参考訳（メタデータ） (2022-11-10T08:38:29Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文 参考訳（メタデータ） (2021-02-03T09:20:32Z) - A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。
我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
論文 参考訳（メタデータ） (2021-01-18T15:40:27Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test [10.386115383285288]
我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。
我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。
本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-28T12:59:27Z) - Epsilon-nets, unitary designs and random quantum circuits [0.11719282046304676]
エプシロンネット(Epsilon-nets)は、量子情報や量子コンピューティングにおける多くの応用に関連するユニタリ演算の概念である。
固定された$d$に対して、$delta$-approx $t$-expanders を構成するユニタリが $epsilon$-nets for $tsimeqfracd5/2epsilon$ および $delta=left(fracepsilon3/2dright)d2$ となることを証明している。
近似tdesign が生成可能であることを示す。
論文 参考訳（メタデータ） (2020-07-21T15:16:28Z) - Average-case Complexity of Teaching Convex Polytopes via Halfspace
Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。
我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文 参考訳（メタデータ） (2020-06-25T19:59:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。