論文の概要: Linear-Size QAC0 Channels: Learning, Testing and Hardness

• arxiv url: http://arxiv.org/abs/2510.00593v1
• Date: Wed, 01 Oct 2025 07:19:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 21:54:12.79838
• Title: Linear-Size QAC0 Channels: Learning, Testing and Hardness
• Title（参考訳）: 線形サイズQAC0チャンネル:学習、テスト、硬さ
• Authors: Yangjing Dong, Fengning Ou, Penghui Yao,
• Abstract要約: 現在の雑音量子ハードウェアは、短時間で忠実な量子計算しか実行できない。 本稿では,サブ指数実行時間とクエリを用いた$mathbfQAC0$チャネルの最初のアルゴリズムを提案する。 また,Choi行列のスペクトルノルム距離とダイヤモンドノルム距離の両方の下で,$mathbfQAC0$チャネルを学習する際のクエリ複雑性を指数関数的に低くする。
• 参考スコア（独自算出の注目度）: 13.101369903953804
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shallow quantum circuits have attracted increasing attention in recent years, due to the fact that current noisy quantum hardware can only perform faithful quantum computation for a short amount of time. The constant-depth quantum circuits $\mathbf{QAC}^0$, a quantum counterpart of $\mathbf{AC}^0$ circuits, are the polynomial-size and constant-depth quantum circuits composed of only single-qubit unitaries and polynomial-size generalized Toffoli gates. The computational power of $\mathbf{QAC}^0$ has been extensively investigated in recent years. In this paper, we are concerned with $\mathbf{QLC}^0$ circuits, which are linear-size $\mathbf{QAC}^0$ circuits, a quantum counterpart of $\mathbf{LC}^0$. * We show that depth-$d$ $\mathbf{QAC}^0$ circuits working on $n$ input qubits and $a$ ancilla qubits have approximate degree at most $\tilde{O}((n+a)^{1-2^{-d}})$, improving the $\tilde{O}((n+a)^{1-3^{-d}})$ degree upper bound of previous works. Consequently, this directly implies that to compute the parity function, $\mathbf{QAC}^0$ circuits need at least $\tilde{O}(n^{1+2^{-d}})$ circuit size. * We present the first agnostic learning algorithm for $\mathbf{QLC}^0$ channels using subexponential running time and queries. Moreover, we also establish exponential lower bounds on the query complexity of learning $\mathbf{QAC}^0$ channels under both the spectral norm distance of the Choi matrix and the diamond norm distance. * We present a tolerant testing algorithm which determines whether an unknown quantum channel is a $\mathbf{QLC}^0$ channel. This tolerant testing algorithm is based on our agnostic learning algorithm. Our approach leverages low-degree approximations of $\mathbf{QAC}^0$ circuits and Pauli analysis as key technical tools. Collectively, these results advance our understanding of agnostic learning for shallow quantum circuits.
• Abstract（参考訳）: 浅量子回路は、現在のノイズの多い量子ハードウェアが短時間で忠実な量子計算しか実行できないという事実から、近年注目を集めている。 定数深さ量子回路 $\mathbf{QAC}^0$, $\mathbf{AC}^0$ は多項式サイズおよび定数深さ量子回路であり、単量子ユニタリと多項式サイズの一般化されたトフォリゲートからなる。 近年,$\mathbf{QAC}^0$の計算能力が広く研究されている。 本稿では, 線形サイズ$\mathbf{QAC}^0$回路である$\mathbf{QLC}^0$回路について検討する。 * depth-d$ $\mathbf{QAC}^0$ circuits working $n$ input qubits and $a$ ancilla qubits have almost degree at most $\tilde{O}((n+a)^{1-2^{-d}})$, improve the $\tilde{O}((n+a)^{1-3^{-d}})$ degree upper bound of previous works。 したがって、パリティ関数を計算するために、$\mathbf{QAC}^0$回路は少なくとも$\tilde{O}(n^{1+2^{-d}})$回路サイズを必要とする。 ※ サブ指数実行時間とクエリを用いた$\mathbf{QLC}^0$チャネルに対する最初の非依存学習アルゴリズムを提案する。 さらに,Choi行列のスペクトルノルム距離とダイヤモンドノルム距離の両方の下で,$\mathbf{QAC}^0$チャネルを学習する際のクエリ複雑性の指数的下界も確立する。 ※ 未知の量子チャネルが$\mathbf{QLC}^0$チャネルであるかどうかを判定する耐久試験アルゴリズムを提案する。 この寛容なテストアルゴリズムは、我々の無知学習アルゴリズムに基づいている。 提案手法は,$\mathbf{QAC}^0$回路の低次近似とパウリ解析を重要な技術ツールとして活用する。 これらの結果は、浅い量子回路に対する非依存的な学習の理解を促進する。

関連論文リスト

• Quantum oracles for the finite element method [45.200826131319815]
  本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。 本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
  論文  参考訳（メタデータ） (2025-04-28T14:28:31Z)
• On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
  深さ$$d$$mathrmQAC0$回路は、近似次数$ta(n)$の関数を計算するために$n1+3-d$アンシラを必要とする。 これは超線形サイズの$mathrmQAC0$上の最初の超線形下界である。
  論文  参考訳（メタデータ） (2024-10-09T02:55:57Z)
• On the Pauli Spectrum of QAC0 [2.3436632098950456]
  我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。 我々は新しい回路の低境界と学習結果を応用として得る。
  論文  参考訳（メタデータ） (2023-11-16T07:25:06Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  本稿では,一様制御ゲート実装のための2種類の定数深度構造を提案する。 我々は、リードオンリーおよびリードライトメモリデバイスの量子対数に対して、一定の深さの回路を得る。
  論文  参考訳（メタデータ） (2023-08-16T17:54:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• 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)

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

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