論文の概要: On the moments of random quantum circuits and robust quantum complexity
- arxiv url: http://arxiv.org/abs/2303.16944v1
- Date: Wed, 29 Mar 2023 18:06:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-31 15:30:51.375348
- Title: On the moments of random quantum circuits and robust quantum complexity
- Title（参考訳）: ランダム量子回路のモーメントとロバスト量子複雑性について
- Authors: Jonas Haferkamp
- Abstract要約: 我々は、ロバスト量子回路の複雑さの増大に新たな低い境界を証明した。
私たちは、ユニタリな$t$-designsの生成に関する既存の結果を使用しません。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove new lower bounds on the growth of robust quantum circuit complexity
-- the minimal number of gates $C_{\delta}(U)$ to approximate a unitary $U$ up
to an error of $\delta$ in operator norm distance -- in random quantum
circuits. First, for $\delta=\Theta(2^{-n})$, we prove a linear growth rate:
$C_{\delta}\geq d/\mathrm{poly}(n)$ for random quantum circuits on $n$ qubits
with $d\leq 2^{n/2}$ gates. Second, for $ \delta=\Omega(1)$, we prove a
square-root growth of complexity: $C_{\delta}\geq \sqrt{d}/\mathrm{poly}(n)$
for all $d\leq 2^{n/2}$. Finally, we provide a simple conjecture regarding the
Fourier support of randomly drawn Boolean functions that would imply linear
growth for constant $\delta$. While these results follow from bounds on the
moments of random quantum circuits, we do not make use of existing results on
the generation of unitary $t$-designs. Instead, we bound the moments of an
auxiliary random walk on the diagonal unitaries acting on phase states. In
particular, our proof is comparably short and self-contained.
- Abstract（参考訳）: 我々は、ランダムな量子回路において、ロバストな量子回路の複雑さの成長の新たな下限を証明している -- 単位値のu$を近似するために最小のゲート数である$c_{\delta}(u)$ -- 演算子ノルム距離で$\delta$という誤差まで -- 。
まず、$\delta=\theta(2^{-n})$ に対して、次の線形成長速度が証明される: $c_{\delta}\geq d/\mathrm{poly}(n)$ $d\leq 2^{n/2}$gates を持つ n$ qubits 上のランダム量子回路に対して、$c_{\delta}\geq d/\mathrm{poly}(n)$。
第二に、$ \delta=\Omega(1)$ に対して、複雑性の平方根成長を証明する: $C_{\delta}\geq \sqrt{d}/\mathrm{poly}(n)$ for all $d\leq 2^{n/2}$。
最後に、任意の$\delta$ に対して線型成長を示唆するランダムに描画されたブール関数のフーリエサポートに関する単純な予想を提供する。
これらの結果はランダム量子回路のモーメントの境界から導かれるが、ユニタリな$t$-designsの生成には既存の結果を使用しない。
代わりに、位相状態に作用する対角ユニタリ上で補助ランダムウォークのモーメントを拘束する。
特に、我々の証明は短く、自己完結している。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Incompressibility and spectral gaps of random circuits [2.359282907257055]
可逆回路と量子回路は、交互群 $mathrmAlt (2n)$ とユニタリ群 $mathrmSU (2n)$ のランダムウォークを形成する。
ランダム可逆回路のギャップは、すべての$tgeq 1$に対して$Omega(n-3)$であり、ランダム量子回路のギャップは$Omega(n-3)$ for $t leq Theta(2n/2)$であることを示す。
論文 参考訳（メタデータ） (2024-06-11T17:23:16Z) - Unitary k-designs from random number-conserving quantum circuits [0.0]
局所ランダム回路は効率よくスクランブルし、量子情報や量子力学に様々な応用がある。
有限モーメントは、数保存ユニタリ群全体のハールアンサンブルから局所ランダム回路が生成するアンサンブルを区別できないことを示す。
論文 参考訳（メタデータ） (2023-06-01T18:00:00Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Optimal (controlled) quantum state preparation and improved unitary
synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
制御量子状態準備(CQSP)は、与えられた$n$-qubit状態に対するすべての$iin 0,1k$に対して、$|irangle |0nrangleから |irangle |psi_irangle $への変換を提供することを目的としている。
我々は、深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$のCQSPを実装するための量子回路を構築する。
論文 参考訳（メタデータ） (2022-02-23T04:19:57Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - 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) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。