論文の概要: Qubit Routing for (Almost) Free

• arxiv url: http://arxiv.org/abs/2604.19717v1
• Date: Tue, 21 Apr 2026 17:43:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-22 22:41:49.907892
• Title: Qubit Routing for (Almost) Free
• Title（参考訳）: ほとんど)無料のクビットルーティング
• Authors: Arianne Meijer-van de Griend,
• Abstract要約: CNOTゲートは、少なくとも$O(fracgnmax (log g, 1))$であるために$g$項を持つ$n$ qubitを合成する必要がある。 制限されたハードウェアをターゲットとする場合、すべてのCNOTが許可されるわけではない。 位相とアダマール門は共に普遍ゲート集合を形成し、ほとんど自由なキュービットルーティングを得る。
• 参考スコア（独自算出の注目度）: 2.0305676256390934
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper, we give a mathematical proof that bounds the number of CNOT gates required to synthesize an $n$ qubit phase polynomial with $g$ terms to be at least $O(\frac{gn}{\max (\log g, 1)})$ and at most $O(gn)$. However, when targeting restricted hardware, not all CNOTs are allowed. If we were to use SWAP-based methods to route the qubits on the architecture such that the earlier synthesized gates are natively allowed, we increase the number of CNOTs by a routing overhead factor of $O(\log n) \leq α\leq O(n \log^2 n)$. However, if we only synthesize allowed gates, we do not need to route any qubits. Moreover, in that case the routing overhead factor is $1 \leq α\leq 4 \simeq O(1)$. Additionally, since phase polynomials and Hadamard gates together form a universal gate set, we get qubit routing for almost free.
• Abstract（参考訳）: 本稿では、$n$ qubit相多項式を少なくとも$O(\frac{gn}{\max (\log g, 1)})$および少なくとも$O(gn)$であるような$g$項で合成するために必要なCNOTゲートの数に有界な数学的証明を与える。 しかし、制限されたハードウェアをターゲットとする場合、すべてのCNOTが許可されるわけではない。 SWAPベースの手法を用いて、初期の合成ゲートがネイティブに許されるようなアーキテクチャ上のキュービットをルーティングする場合、ルーティングオーバーヘッド係数$O(\log n) \leq α\leq O(n \log^2 n)$によってCNOTの数が増加する。 しかし、許容ゲートのみを合成すれば、量子ビットをルートする必要はない。 さらに、ルーティングオーバーヘッド係数は1 \leq α\leq 4 \simeq O(1)$である。 さらに、位相多項式とアダマールゲートが共に普遍ゲート集合を形成するので、ほとんど自由なキュービットルーティングが得られる。

関連論文リスト

• Multi-Controlled Quantum Gates in Linear Nearest Neighbor [0.0]
  マルチコントロールシングルターゲット(MC)ゲートは、様々な量子アルゴリズムにとって重要なビルディングブロックである。 本稿では,$sim 4k+8n$ CNOT ゲートを使用せずに MC ゲートを実装する手法について述べる。 提案手法は, MCゲートの任意の場合において, 上界よりもCNOTゲートを少なくする回路を提供する。
  論文  参考訳（メタデータ） (2025-05-31T20:01:21Z)
• Efficient Circuit-Based Quantum State Tomography via Sparse Entry Optimization [0.6008132390640295]
  我々は、$n$量子ビット状態を$k$非ゼロエントリで再構成する効率的な回路ベースの量子状態トモグラフィー手法を提案する。 我々は、$|psirangle$ における 0 でないエントリの位置に基づいて、CNOT ゲートの数に上限を与える。
  論文  参考訳（メタデータ） (2024-07-29T02:59:13Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  本稿では,一様制御ゲート実装のための2種類の定数深度構造を提案する。 我々は、リードオンリーおよびリードライトメモリデバイスの量子対数に対して、一定の深さの回路を得る。
  論文  参考訳（メタデータ） (2023-08-16T17:54:56Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。 我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
  論文  参考訳（メタデータ） (2023-03-03T18:23:20Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)

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

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