論文の概要: Worst-case depth hierarchy for shallow quantum circuits

• arxiv url: http://arxiv.org/abs/2606.16425v1
• Date: Mon, 15 Jun 2026 09:02:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-16 16:21:34.258005
• Title: Worst-case depth hierarchy for shallow quantum circuits
• Title（参考訳）: 浅量子回路における極大ケース深さ階層
• Authors: Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian, Xingjian Zhang,
• Abstract要約: 我々は$mathsfQNC0$に対して明示的な深さ階層定理を証明する。 それぞれの$dge 12$に対して、深さ$(d-1)の量子回路がほぼ完全な成功を達成できない2ラウンドのインタラクティブな問題の族を構築する。 深さの増大は$mathsfQNC0$以内の計算パワーを厳密に増加させ、真に量子的階層を確立することを示す。
• 参考スコア（独自算出の注目度）: 8.32379529009722
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$. For each $d\ge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$, yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$, establishing a genuinely quantum hierarchy.
• Abstract（参考訳）: 回路深度は複雑性理論における中心的な資源である。 有界深度古典回路は階層定理をよく理解しているが、定数深度量子計算の内部構造は比較的未解明のままである。 我々は、$\mathsf{QNC}^0$ に対して明示的な深さ階層定理を証明する。 それぞれの$d\ge 12$に対して、深さ$(d-1)の量子回路が、ゲートセット、回路サイズ、またはアシラリー量子ビットに関係なくほぼ完全な成功を達成できない2ラウンドの対話的な問題の族を構築する。 対照的に、我々の構成は、小さな定数係数で$d$より大きい深さの単純な有界ファンイン量子回路による実現を認める。 さらに、(入力サイズにおいて)すべての有界なファンイン古典回路は、$d$ごとにこれらのタスクにおいて完全な成功を達成できず、$\mathsf{QNC}^0$ over $\mathsf{NC}^0$の非条件量子的優位性を示す問題の階層を与える。 鍵となる障害は、量子回路の低いバウンド技術が不足していることである。 そこで本研究では,回路の奥行きが出力キュービット間の非局所的相関をきめ細かな方法で実現する能力にどのように影響するかを解析する手法を開発した。 提案手法は制約系と非局所ゲームとの対応を利用して,群論的構成を厳密な演算子値制約系に変換し,非局所ゲームに変換する。 特に,一意に忠実な演算子評価解が要求される制約系を構築するには,任意の完全戦略と,固定精度のほぼ完全戦略がすべて必要であり,複数制御位相演算を実装する。 これは非局所的なユニタリ合成問題に還元され、浅い量子回路と古典回路の両方の深さの低い境界をもたらす。 これらの結果は、深さの増大が$\mathsf{QNC}^0$内の計算パワーを厳密に増加させ、真に量子的階層を確立することを示している。

関連論文リスト

• Exact Quantum Circuit Optimization is co-NQP-hard [4.554892610576937]
  我々は、回路$C$が与えられたとき、量子リソースタイプを最小化する等価回路$C’$が計算されるという自然問題を考える。 H と TOF のゲートを正確に実装できる任意のゲート集合上で$C$ が表現されている場合、上記の最適化問題は $textco-NQP$ では困難である。
  論文  参考訳（メタデータ） (2025-10-18T09:31:23Z)
• Learning Circuits with Infinite Tensor Networks [0.4972323953932129]
  量子コンピュータ上のハミルトニアンシミュレーションはゲート数によって制約され、回路深さを減らすための技術が動機となっている。 我々はテンソルネットワークを利用して回路設計を支援し、量子機械学習にインスパイアされたユニタリ合成を可能にする。 提案手法は, 基底状態を効率的に生成し, 無限系と有限系の両方で時間発展を行う回路を求める。
  論文  参考訳（メタデータ） (2025-06-02T18:00:01Z)
• Deep Circuit Compression for Quantum Dynamics via Tensor Networks [0.4972323953932129]
  本稿では,デジタル量子コンピュータ上でリアルタイムなシミュレーションが可能な圧縮回路を生成するためのコンパイルアルゴリズムを提案する。 与えられた深さについては、アルゴリズムは同じ深さの全てのトロッター化よりも正確である。 52-qubit 2D Transverse-Field IsingプロパゲータをIBM Heavy-Hexトポロジにコンパイルすることでこれを実証する。
  論文  参考訳（メタデータ） (2024-09-24T18:00:05Z)
• The power of shallow-depth Toffoli and qudit quantum circuits [3.212381039696143]
  量子回路複雑性の主な目的の1つは、量子浅層回路によって解くことができるが、古典的により多くの計算資源を必要とする問題を見つけることである。 我々は古典的回路と量子的定数深さ回路の分離を新たに証明する。 無限大ゲートセットの場合、高次元ヒルベルト空間に対するこれらの量子回路クラスは標準量子ビット実装に何の利点も与えない。
  論文  参考訳（メタデータ） (2024-04-28T07:44:27Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• Escaping from the Barren Plateau via Gaussian Initializations in Deep Variational Quantum Circuits [63.83649593474856]
  近年、変分量子回路は量子シミュレーションや量子機械学習に広く用いられている。 しかし、ランダムな構造を持つ量子回路は、回路深さと量子ビット数に関して指数関数的に消える勾配のため、トレーニング容易性が低い。 この結果は、ディープ量子回路が実用的なタスクでは実現できないという一般的な見解に繋がる。
  論文  参考訳（メタデータ） (2022-03-17T15:06:40Z)
• Toward Trainability of Deep Quantum Neural Networks [87.04438831673063]
  ランダムな構造を持つ量子ニューラルネットワーク(QNN)は、回路深さと量子ビット数が増加するにつれて指数関数的に減少する勾配のため、トレーニング性に乏しい。 理論的保証のある深部QNNに対して、消滅する勾配問題に対する最初の実現可能な解決策を提供する。
  論文  参考訳（メタデータ） (2021-12-30T10:27:08Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。 本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
  論文  参考訳（メタデータ） (2020-02-27T15:32:08Z)

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

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