論文の概要: Fourier Spectrum of Noisy Quantum Algorithms

• arxiv url: http://arxiv.org/abs/2510.06385v1
• Date: Tue, 07 Oct 2025 19:07:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.160665
• Title: Fourier Spectrum of Noisy Quantum Algorithms
• Title（参考訳）: 雑音量子アルゴリズムのフーリエスペクトル
• Authors: Uma Girish,
• Abstract要約: 量子アルゴリズムに作用する雑音は、ノイズの種類と複雑に結びついている方法でフーリエ成長を阻害することを示す。 特に,2-Forrelationと3-Forrelationは,それぞれ$mathsfDQC_k$と$frac12mathsfBQP$モデルで,$NOmega(1)$クエリを必要とすることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computing promises exponential speedups for certain problems, yet fully universal quantum computers remain out of reach and near-term devices are inherently noisy. Motivated by this, we study noisy quantum algorithms and the landscape between $\mathsf{BQP}$ and $\mathsf{BPP}$. We build on a powerful technique to differentiate quantum and classical algorithms called the level-$\ell$ Fourier growth (the sum of absolute values of Fourier coefficients of sets of size $\ell$) and show that it can also be used to differentiate quantum algorithms based on the types of resources used. We show that noise acting on a quantum algorithm dampens its Fourier growth in ways intricately linked to the type of noise. Concretely, we study noisy models of quantum computation where highly mixed states are prevalent, namely: $\mathsf{DQC}_k$ algorithms, where $k$ qubits are clean and the rest are maximally mixed, and $\frac{1}{2}\mathsf {BQP}$ algorithms, where the initial state is maximally mixed, but the algorithm is given knowledge of the initial state at the end of the computation. We establish upper bounds on the Fourier growth of $\mathsf{DQC}_k$, $\frac{1}{2}\mathsf{BQP}$ and $\mathsf{BQP}$ algorithms and leverage the differences between these bounds to derive oracle separations between these models. In particular, we show that 2-Forrelation and 3-Forrelation require $N^{\Omega(1)}$ queries in the $\mathsf{DQC}_1$ and $\frac{1}{2}\mathsf{BQP}$ models respectively. Our results are proved using a new matrix decomposition lemma that might be of independent interest.
• Abstract（参考訳）: 量子コンピューティングは特定の問題に対して指数的なスピードアップを約束するが、完全に普遍的な量子コンピュータは手の届かないままであり、近い将来のデバイスは本質的にノイズが多い。 これを動機として、ノイズ量子アルゴリズムと$\mathsf{BQP}$と$\mathsf{BPP}$の間の風景を研究する。 我々は、レベル=$$ell$フーリエ成長(大きさの集合のフーリエ係数の絶対値の和$$$ell$)と呼ばれる量子アルゴリズムと古典的アルゴリズムを区別する強力な技術を構築し、使用したリソースの種類に基づいて量子アルゴリズムを区別することも可能であることを示す。 量子アルゴリズムに作用する雑音は、ノイズの種類と複雑に結びついている方法でフーリエ成長を阻害することを示す。 具体的には、高混合状態が一般的である量子計算のノイズモデル、すなわち、$k$ qubitsがクリーンで残りが最大混合である$\frac{1}{2}\mathsf {BQP}$アルゴリズム、初期状態が最大混合である$\frac{1}{2}\mathsf {BQP}$アルゴリズムについて検討する。 我々は、$\mathsf{DQC}_k$, $\frac{1}{2}\mathsf{BQP}$と$\mathsf{BQP}$アルゴリズムのフーリエ成長上の上限を確立し、これらの境界の差を利用してこれらのモデル間のオラクル分離を導出する。 特に、2-Forrelation と 3-Forrelation は $N^{\Omega(1)}$ のクエリを $\mathsf{DQC}_1$ と $\frac{1}{2}\mathsf{BQP}$ のモデルでそれぞれ要求することを示した。 本結果は, 独立性のある新しい行列分解補題を用いて検証した。

関連論文リスト

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
  論文  参考訳（メタデータ） (2024-11-06T22:51:27Z)
• Quantum State Learning Implies Circuit Lower Bounds [1.5420873135976756]
  状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。 わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
  論文  参考訳（メタデータ） (2024-05-16T16:46:27Z)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。 我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
  論文  参考訳（メタデータ） (2021-12-15T21:44:05Z)
• 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)

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

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