論文の概要: Quantum State Learning Implies Circuit Lower Bounds

• arxiv url: http://arxiv.org/abs/2405.10242v1
• Date: Thu, 16 May 2024 16:46:27 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-17 13:43:00.177455
• Title: Quantum State Learning Implies Circuit Lower Bounds
• Title（参考訳）: 量子状態学習は回路の低境界に影響を及ぼす
• Authors: Nai-Hui Chia, Daniel Liang, Fang Song,
• Abstract要約: 状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。 わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
• 参考スコア（独自算出の注目度）: 2.2667044928324747
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let $\mathfrak{C}$ be a family of non-uniform quantum circuits of polynomial size and suppose that there exists an algorithm that, given copies of $|\psi \rangle$, distinguishes whether $|\psi \rangle$ is produced by $\mathfrak{C}$ or is Haar random, promised one of these is the case. For arbitrary fixed constant $c$, we show that if the algorithm uses at most $O(2^{n^c})$ time and $2^{n^{0.99}}$ samples then $\mathsf{stateBQE} \not\subset \mathsf{state}\mathfrak{C}$. Here $\mathsf{stateBQE} := \mathsf{stateBQTIME}[2^{O(n)}]$ and $\mathsf{state}\mathfrak{C}$ are state synthesis complexity classes as introduced by Rosenthal and Yuen (ITCS 2022), which capture problems with classical inputs but quantum output. Note that efficient tomography implies a similarly efficient distinguishing algorithm against Haar random states, even for nearly exponential-time algorithms. Because every state produced by a polynomial-size circuit can be learned with $2^{O(n)}$ samples and time, or $O(n^{\omega(1)})$ samples and $2^{O(n^{\omega(1)})}$ time, we show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis. Finally, a slight modification of our proof shows that distinguishing algorithms for quantum states can imply circuit lower bounds for decision problems as well. This help sheds light on why time-efficient tomography algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results by Arunachalam et al. (FOCS 2021) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes, but modified for the purposes of state tomography and state synthesis.
• Abstract（参考訳）: 我々は,状態トモグラフィ,擬似ランダム性,量子状態合成,回路下界の接続を確立する。 特に、$\mathfrak{C}$ を多項式サイズの非一様量子回路の族とし、$|\psi \rangle$ のコピーが与えられたとき、$|\psi \rangle$ が $\mathfrak{C}$ によって生成されるか、またはハールランダムであるかを区別するアルゴリズムが存在すると仮定する。 任意の固定定数$c$に対して、アルゴリズムが少なくとも$O(2^{n^c})$時間と$2^{n^{0.99}}$サンプルを使用するなら、$\mathsf{stateBQE} \not\subset \mathsf{state}\mathfrak{C}$である。 ここで、$\mathsf{stateBQE} := \mathsf{stateBQTIME}[2^{O(n)}]$と$\mathsf{state}\mathfrak{C}$は、古典的な入力と量子出力の問題を捉えるRosenhal and Yuen (ITCS 2022)によって導入された状態合成複雑性クラスである。 効率的なトモグラフィーは、ほぼ指数時間アルゴリズムであっても、Haarランダム状態に対して同様に効率的に区別するアルゴリズムである。 多項式サイズの回路で生成される全ての状態はサンプルと時間で、$O(n^{\omega(1)})と$O(n^{\omega(1)})と$2(n^{\omega(1)})で学習できるので、わずかに自明な量子状態トモグラフィーアルゴリズムでさえ量子状態合成に関する新しい言明をもたらすことが示される。 最後に、我々の証明のわずかな修正により、量子状態の区別アルゴリズムは、決定問題に対する下位境界を導出できることを示している。 このことは、非一様量子回路クラスに対する時間効率のトモグラフィーアルゴリズムが、限定的で部分的な進歩しか持たない理由を明かすのに役立っている。 Arunachalam et al (FOCS 2021) は、ブール関数の量子学習と古典回路クラスの回路下界との類似性を明らかにしたが、状態トモグラフィーと状態合成の目的で修正した。

関連論文リスト

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
  論文  参考訳（メタデータ） (2024-11-06T22:51:27Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
  二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。 このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
  論文  参考訳（メタデータ） (2023-02-06T15:14:34Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• 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)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。 我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-16T13:57:01Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。 このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-09-09T18:00:09Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)
• Quantum $k$-nearest neighbors algorithm [0.0]
  古典的な$k$NN $-$quantum $k$NN (Q$k$NN) $-$の量子類似を類似度尺度として示す。 従来の$k$NNや既存の$k$NNアルゴリズムとは異なり、提案アルゴリズムは量子データに直接使用することができる。
  論文  参考訳（メタデータ） (2020-03-20T10:48:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。