論文の概要: Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
- arxiv url: http://arxiv.org/abs/2209.14530v1
- Date: Thu, 29 Sep 2022 03:34:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-30 18:21:56.388182
- Title: Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
- Title（参考訳）: 低安定化-複素量子状態は疑似乱数ではない
- Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
- Abstract要約: 安定度が低い」量子状態は、Haar-randomと効率的に区別できることを示す。
我々は、計算的に擬似ランダムな量子状態を作成するためには、任意のクリフォード+$T$回路に対して$omega(log(n))$$T$-gatesが必要であることを証明した。
- 参考スコア（独自算出の注目度）: 1.0323063834827415
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We show that quantum states with "low stabilizer complexity" can be
efficiently distinguished from Haar-random. Specifically, given an $n$-qubit
pure state $|\psi\rangle$, we give an efficient algorithm that distinguishes
whether $|\psi\rangle$ is (i) Haar-random or (ii) a state with stabilizer
fidelity at least $\frac{1}{k}$ (i.e., has fidelity at least $\frac{1}{k}$ with
some stabilizer state), promised that one of these is the case. With black-box
access to $|\psi\rangle$, our algorithm uses $O\!\left( k^{12}
\log(1/\delta)\right)$ copies of $|\psi\rangle$ and $O\!\left(n k^{12}
\log(1/\delta)\right)$ time to succeed with probability at least $1-\delta$,
and, with access to a state preparation unitary for $|\psi\rangle$ (and its
inverse), $O\!\left( k^{3} \log(1/\delta)\right)$ queries and $O\!\left(n k^{3}
\log(1/\delta)\right)$ time suffice.
As a corollary, we prove that $\omega(\log(n))$ $T$-gates are necessary for
any Clifford+$T$ circuit to prepare computationally pseudorandom quantum
states, a first-of-its-kind lower bound.
- Abstract（参考訳）: 安定度が低い」量子状態は、Haar-randomと効率的に区別できることを示す。
具体的には、$n$-qubit 純粋状態 $|\psi\rangle$ を考えると、$|\psi\rangle$ を区別する効率的なアルゴリズムを与える。
(i)ハールランダム、又は
(ii)安定化子忠実度が少なくとも$\frac{1}{k}$(安定子状態が少なくとも$\frac{1}{k}$である)の状態で、これらのうちの1つが正しいことを約束する。
ブラックボックスで$|\psi\rangle$にアクセスすると、アルゴリズムは$O\!
\left(k^{12} \log(1/\delta)\right)$|\psi\rangle$ と $o\!
\left(n k^{12} \log(1/\delta)\right)$ time to succeed with probability at least $1-\delta$, and with access to a state preparation unitary for $|\psi\rangle$ (and its inverse, $o\!
\left(k^{3} \log(1/\delta)\right)$クエリと$o\!
\left(n k^{3} \log(1/\delta)\right)$ time suffice である。
結論として、計算的に擬似ランダムな量子状態、すなわち一階述語的な下界を作るためには、$\omega(\log(n))$$T$-gates が任意の Clifford+$T$ 回路で必要であることが証明される。
関連論文リスト
- Learning junta distributions and quantum junta states, and QAC$^0$ circuits [0.0]
本稿では,量子ジャンタ分布の学習問題,量子カウンター部,量子ジャンタ状態,QAC$0$回路について考察する。
誤差$varepsilon$を全変動距離で学習できることが示される。
また、$Omega(4k+log (n)/varepsilon2)$コピーの低い境界も証明します。
論文 参考訳（メタデータ） (2024-10-21T09:39:20Z) - Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation [16.499689832762765]
未知の$n$-qubit state $rho$のコピーが与えられたとき、与えられたクラス$C$の何らかの状態を持つフィデリティ$tau$を持ち、そのフィデリティ$ge tau - epsilon$と$rho$を持つ状態を見つける。
我々は,このタスクのための計算効率の良いプロトコルを設計するための新しいフレームワークである安定化器ブートストラッピングを提供し,これを用いて,安定化器状態と離散積状態という,次のクラスに対する新しい非依存トモグラフィープロトコルを得る。
論文 参考訳（メタデータ） (2024-08-13T15:23:17Z) - Sharp Noisy Binary Search with Monotonic Probabilities [5.563988395126509]
我々はKarpとKleinbergのノイズの多いバイナリ検索モデルを再検討する。
我々は[ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta)右から1-delta$の確率で成功するアルゴリズムを作成する。
論文 参考訳（メタデータ） (2023-11-01T20:45:13Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳（メタデータ） (2021-09-21T13:19:04Z) - 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) - The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。
任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
論文 参考訳（メタデータ） (2020-08-20T01:04:32Z) - Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-08T18:00:01Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。