Fugu-MT 論文翻訳(概要): IQP circuits for 2-Forrelation

論文の概要: IQP circuits for 2-Forrelation

arxiv url: http://arxiv.org/abs/2604.15248v1
Date: Thu, 16 Apr 2026 17:24:25 GMT
ステータス: 翻訳完了
システム内更新日: 2026-04-17 21:29:32.024832
Title: IQP circuits for 2-Forrelation
Title（参考訳）: 2重リレーションのためのIQP回路
Authors: Quentin Buzet, André Chailloux,
Abstract要約: 2-Forrelation問題は、古典的および量子的クエリの複雑さを最適に分離する。 Instantaneous Quantum Polynomial-time (mathsfIQP$) 回路を用いて2-Forrelationを解くことができることを示す。
参考スコア（独自算出の注目度）: 2.5782420501870296
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The 2-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating $\mathsf{BQP}$ and $\mathsf{PH}$ relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that 2-Forrelation can be solved using Instantaneous Quantum Polynomial-time ($\mathsf{IQP}$) circuits, a restricted model of quantum computation in which all gates commute. Concretely, two $\mathsf{IQP}$ circuits with two quantum queries and efficient classical processing suffice. For the signed variant of 2-Forrelation, even a single $\mathsf{IQP}$ circuit and query suffices. This answers a recent open question of Girish (arXiv:2510.06385) on the power of commuting quantum computations. We use this to show that $(\mathsf{BPP}^{\mathsf{IQP}})^O \not\subseteq \mathsf{PH}^O$ relative to an oracle $O$, strengthening the result of Raz and Tal (STOC 2019). Our results show that $\mathsf{IQP}$ circuits can be used for classically hard decision problems, thus providing a new route for showing quantum advantage with $\mathsf{IQP}$ circuits, avoiding the verification difficulties associated with sampling tasks. We also prove Fourier growth bounds for $\mathsf{IQP}$ circuits in terms of the size of their accepting set. The key ingredient is an algebraic identity of the quadratic function $Q(x) = \sum_{i < j} x_ix_j$ that allows extracting inner-product phases within an $\mathsf{IQP}$ circuit.
Abstract（参考訳）: 2-Forrelation問題は古典的および量子的クエリの複雑さを最適に分離し、また、$\mathsf{BQP}$と$\mathsf{PH}$をオラクルに対して分離するためにも用いられる問題である。したがって自然の疑問は、この問題を解決するのに必要な最小の量子資源が何であるかを問うことである。我々は,全てのゲートが交換される量子計算の制限モデルであるInstantaneous Quantum Polynomial-time(\mathsf{IQP}$)回路を用いて,2-Forrelationを解くことができることを示す。具体的には、2つの量子クエリーと効率的な古典的処理サッフィスを持つ2つの$\mathsf{IQP}$回路である。 2-Forrelationの符号付き変種の場合、単一の$\mathsf{IQP}$回路とクエリサッフィスさえあればよい。これは、交換量子計算のパワーに関する最近のGirish(arXiv:2510.06385)のオープンな疑問に答える。これを用いて、(\mathsf{BPP}^{\mathsf{IQP}})^O \not\subseteq \mathsf{PH}^O$ がオラクル $O$ に対して成立し、Raz と Tal (STOC 2019) の結果が強まることを示す。以上の結果から,$\mathsf{IQP}$回路は古典的に難しい決定問題に利用できることが明らかとなり,サンプリング作業に伴う検証困難を回避するために,$\mathsf{IQP}$回路を用いた量子優位性を示す新たな経路が提供される。また、受容集合のサイズの観点から、$\mathsf{IQP}$回路のフーリエ成長境界も証明する。鍵成分は二次関数 $Q(x) = \sum_{i < j} x_ix_j$ の代数的恒等式であり、$\mathsf{IQP}$回路内で内積位相を抽出することができる。

関連論文リスト

Quantum oracles for the finite element method [45.200826131319815]
本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
論文参考訳（メタデータ） (2025-04-28T14:28:31Z)
Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文参考訳（メタデータ） (2024-11-01T18:00:56Z)
Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [6.8680041558282054]
並列量子計算は,従来よりも計算能力が高いことを示す。我々は、新しい量子コンピュータに計算上の優位性を持たせて、より高次元の非局所ゲーム理論を橋渡しする。
論文参考訳（メタデータ） (2024-08-29T09:40:55Z)
Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文参考訳（メタデータ） (2024-05-14T15:28:37Z)
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds [1.3927943269211591]
本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
論文参考訳（メタデータ） (2024-01-03T09:12:25Z)
On the Pauli Spectrum of QAC0 [2.3436632098950456]
我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。我々は新しい回路の低境界と学習結果を応用として得る。
論文参考訳（メタデータ） (2023-11-16T07:25:06Z)
Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文参考訳（メタデータ） (2022-10-12T17:54:02Z)
On quantum algorithms for the Schr\"odinger equation in the semi-classical regime [27.175719898694073]
半古典的状態におけるシュル・オーディンガーの方程式を考える。このようなシュル・オーディンガー方程式はボルン=オッペンハイマーの分子動力学やエレンフェストの動力学など多くの応用を見出す。
論文参考訳（メタデータ） (2021-12-25T20:01:54Z)
Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
論文参考訳（メタデータ） (2021-08-13T09:47:11Z)
Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文参考訳（メタデータ） (2020-12-03T14:03:20Z)

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

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