論文の概要: Quantum supremacy and hardness of estimating output probabilities of
quantum circuits
- arxiv url: http://arxiv.org/abs/2102.01960v3
- Date: Fri, 10 Dec 2021 13:23:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-12 22:32:31.512341
- Title: Quantum supremacy and hardness of estimating output probabilities of
quantum circuits
- Title(参考訳): 量子回路の出力確率推定の量子超越性と硬さ
- Authors: Yasuhiro Kondo, Ryuhei Mori, Ramis Movassagh
- Abstract要約: 我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by the recent experimental demonstrations of quantum supremacy,
proving the hardness of the output of random quantum circuits is an imperative
near term goal. We prove under the complexity theoretical assumption of the
non-collapse of the polynomial hierarchy that approximating the output
probabilities of random quantum circuits to within $\exp(-\Omega(m\log m))$
additive error is hard for any classical computer, where $m$ is the number of
gates in the quantum computation. More precisely, we show that the above
problem is $\#\mathsf{P}$-hard under $\mathsf{BPP}^{\mathsf{NP}}$ reduction. In
the recent experiments, the quantum circuit has $n$-qubits and the architecture
is a two-dimensional grid of size $\sqrt{n}\times\sqrt{n}$. Indeed for constant
depth circuits approximating the output probabilities to within
$2^{-\Omega(n\log{n})}$ is hard. For circuits of depth $\log{n}$ or $\sqrt{n}$
for which the anti-concentration property holds, approximating the output
probabilities to within $2^{-\Omega(n\log^2{n})}$ and $2^{-\Omega(n^{3/2}\log
n)}$ is hard respectively. We then show that the hardness results extend to any
open neighborhood of an arbitrary (fixed) circuit including the trivial circuit
with identity gates. We made an effort to find the best proofs and proved these
results from first principles, which do not use the standard techniques such as
the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's
result.
- Abstract(参考訳): 量子超越性の最近の実験的実証により、ランダム量子回路の出力の硬さを証明することは、短期的な目標である。
我々は、ランダム量子回路の出力確率を$\exp(-\Omega(m\log)内に近似する多項式階層の非崩壊の複雑性理論の仮定の下で証明する。
m))$加算誤差は、量子計算におけるゲート数である$m$という古典的コンピュータでは難しい。
より正確には、上記の問題は$\#\mathsf{P}$-hard under $\mathsf{BPP}^{\mathsf{NP}}$ reductionである。
最近の実験では、量子回路は$n$-qubitsを持ち、アーキテクチャは$\sqrt{n}\times\sqrt{n}$の2次元グリッドである。
実際、出力確率を2^{-\Omega(n\log{n})}$に近似する定深さ回路は困難である。
深度$\log{n}$ または $\sqrt{n}$ に対して、反集中性を持ち、出力確率を 2^{-\Omega(n\log^2{n})}$ と $2^{-\Omega(n^{3/2}\log に近似する。
n)$は、それぞれ難しい。
次に、ハードネスの結果が自明なidゲートを持つ回路を含む任意の(固定された)回路の任意の開近傍にまで広がることを示す。
我々は最善の証明を見つけようと努力し、ベルレクサンプ=ウェルチアルゴリズム、通常のパトリの補題、ラフマノフの結果のような標準手法を使用しない第一原理からこれらの結果を証明した。
関連論文リスト
- Circuit Complexity of Sparse Quantum State Preparation [0.0]
任意の$n$-qubit $d$-sparse量子状態は、$O(fracdnlog d)$とdeep $Theta(log dn)$の量子回路で、少なくとも$O(fracndlog d )$ acillary qubitsを用いて作成できることを示す。
また、回路サイズに$Omega(fracdnlog(n + m) + log d + n)$ という下界の$Omega(fracdnlog(n + m) + log d + n)$ を設定できる。
論文 参考訳(メタデータ) (2024-06-23T15:28:20Z) - 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) - 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) - On the moments of random quantum circuits and robust quantum complexity [0.0]
我々は、ロバスト量子回路の複雑さの増大に新たな低い境界を証明した。
局所ゲートを持つランダム量子回路に対して、$SU(4)$の部分群から引き出された2つの境界を示す。
論文 参考訳(メタデータ) (2023-03-29T18:06:03Z) - 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) - 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) - Improved spectral gaps for random quantum circuits: large local
dimensions and all-to-all interactions [0.0]
我々は、$D$のランダム量子回路がスペクトルギャップスケーリングを$Omega(n-1)$とすることを示し、$t$が局所次元と比較して小さいことを仮定する:$t2leq O(q)$。
2つ目の結果は、全ての相互作用を持つランダム量子回路に対して、以下に$Omega(n-1log-1(n) t-alpha(q))$で有界な非条件スペクトルギャップである。
論文 参考訳(メタデータ) (2020-12-09T19:00:50Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳(メタデータ) (2020-11-24T18:44:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。