論文の概要: Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false

• arxiv url: http://arxiv.org/abs/2510.04411v1
• Date: Mon, 06 Oct 2025 00:56:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:59.637685
• Title: Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false
• Title（参考訳）: 量子プリ計算:カスケード回路の並列化とムーア・ニルソン予想は偽である
• Authors: Adam Bene Watts, Charles R. Chen, J. William Helton, Joseph Slote,
• Abstract要約: クラス内のすべての回路を深さ$O(log n)$に圧縮することで、ムーア・ニルソン予想を負に解決する。 より一般的には、量子ブロックワイドプリ計算技術を導入することにより、量子並列化のプロジェクトを進めていく。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Parallelization is a major challenge in quantum algorithms due to physical constraints like no-cloning. This is vividly illustrated by the conjecture of Moore and Nilsson from their seminal work on quantum circuit complexity [MN01, announced 1998]: unitaries of a deceptively simple form--controlled-unitary "staircases"--require circuits of minimum depth $\Omega(n)$. If true, this lower bound would represent a major break from classical parallelism and prove a quantum-native analogue of the famous NC $\neq$ P conjecture. In this work we settle the Moore-Nilsson conjecture in the negative by compressing all circuits in the class to depth $O(\log n)$, which is the best possible. The parallelizations are exact, ancilla-free, and can be computed in poly($n$) time. We also consider circuits restricted to 2D connectivity, for which we derive compressions of optimal depth $O(\sqrt{n})$. More generally, we make progress on the project of quantum parallelization by introducing a quantum blockwise precomputation technique somewhat analogous to the method of Arlazarov, Dini\v{c}, Kronrod, and Farad\v{z}ev [Arl+70] in classical dynamic programming, often called the "Four-Russians method." We apply this technique to more-general "cascade" circuits as well, obtaining for example polynomial depth reductions for staircases of controlled $\log(n)$-qubit unitaries.
• Abstract（参考訳）: 並列化は、非閉鎖のような物理的制約のため、量子アルゴリズムにおいて大きな課題である。 これはムーアとニルソンの量子回路複雑性に関する基礎研究(MN01, announced 1998)による予想(英語版)によって鮮明に説明される: 最小深度$\Omega(n)$の、知覚的に単純な形式制御単位の「階段」のユニタリである。 もし真なら、この下界は古典的並列性の大きな破れを表し、有名なNC$\neq$P予想の量子ネイティブな類似性を証明している。 この研究において、クラス内のすべての回路を深さ$O(\log n)$に圧縮することで、ムーア・ニルソン予想を負に定め、これが最善である。 並列化は完全でアンシラフリーであり、ポリ($n$)時間で計算できる。 また、2次元接続に制限された回路も検討し、最適深度$O(\sqrt{n})$の圧縮を導出する。 より一般的には、古典的動的プログラミングにおいて、Arlazarov, Dini\v{c}, Kronrod, Farad\v{z}ev [Arl+70] の手法と幾らか類似した量子ブロックワイズプリ計算手法を導入することにより、量子並列化のプロジェクトを進める。 この手法をより一般的な「カスケード」回路にも適用し、例えば、制御された$\log(n)$-qubitユニタリの階段の多項式深さの減少を求める。

関連論文リスト

• Shallow quantum circuit for generating O(1)-entangled approximate state designs [6.161617062225404]
  我々は、非常に低い絡み合い、魔法、コヒーレンスを持ちながら、$epsilon$-approximate state $t$-designとして機能する新しい量子状態の集合を見つける。 これらの資源は理論上の下界である$Omega(log (t/epsilon))$に達することができ、これもこの研究で証明されている。 我々の研究で提案された量子回路のクラスは、ランダムな量子状態の古典的なシミュレーションにコストを削減している。
  論文  参考訳（メタデータ） (2025-07-23T18:56:19Z)
• A log-depth in-place quantum Fourier transform that rarely needs ancillas [0.08113005007481719]
  最適化量子回路」は、より大きな量子アルゴリズムの文脈ではしばしば十分である。 量子フーリエ変換(QFT)のための楽観的な回路を構築する。 提案手法を適用して,全ての入力に対してよく制御された誤差で近似QFTを出力する。
  論文  参考訳（メタデータ） (2025-05-01T17:58:36Z)
• Quantum oracles for the finite element method [45.200826131319815]
  本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。 本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
  論文  参考訳（メタデータ） (2025-04-28T14:28:31Z)
• Nearly Optimal Circuit Size for Sparse Quantum State Preparation [0.0]
  量子状態が$d$スパースであるとは、非ゼロ振幅が$d$である場合に言う。 我々は,アシラリー量子ビット数と回路サイズとのトレードオフを初めて証明した。
  論文  参考訳（メタデータ） (2024-06-23T15:28:20Z)
• Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  本稿では,ニュートンのGDを用いたニューラルネットワークトレーニングの高速化を目的とした,ハイブリッド量子古典スケジューラQ-Newtonを提案する。 Q-Newtonは量子と古典的な線形解法を協調する合理化スケジューリングモジュールを使用している。 評価の結果,Q-Newtonは一般的な量子機械と比較してトレーニング時間を大幅に短縮できる可能性が示された。
  論文  参考訳（メタデータ） (2024-04-30T23:55:03Z)
• 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)
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
  我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。 この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
  論文  参考訳（メタデータ） (2021-02-03T09:20:32Z)
• 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)

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

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