論文の概要: Faster algorithm for achieving minimal-size quantum decision diagrams

• arxiv url: http://arxiv.org/abs/2606.24789v1
• Date: Tue, 23 Jun 2026 16:45:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 22:16:49.093025
• Title: Faster algorithm for achieving minimal-size quantum decision diagrams
• Title（参考訳）: 最小サイズの量子決定図作成のための高速アルゴリズム
• Authors: Juul Sanders, Sebastiaan Brand, Arend-Jan Quist, Tim Coopmans,
• Abstract要約: 本稿では,1つの子ノードを持つ$n$-qubit DDノードに対して,$O(n3)$から$O(n2)$への最悪のケース高速化を実現する。 C/C++でスクラッチから記述した量子回路のパウリLIMDDシミュレータであるQolDDerの一部として,本アルゴリズムを実装した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The decision diagram (DD) data structure enables fast linear-algebra calculations by bringing vectors into a normal form and subsequently merging equivalent ones, yielding a minimally-sized DD modulo the equivalence relation. A fruitful application area is quantum-circuit simulation, where the vectors represent quantum states. The Local Invertible Map Decision Diagram (LIMDD) type, merges LIM-equivalent (typically Pauli-gate equivalent) vectors, can efficiently simulate Clifford circuits as well as some high-T-count circuits, and has theoretically been proven exponentially faster for simulation than other well-developed data structures, including other common DD variants. However, these exponential advantages have not fully materialized yet in existing implementations, for which the normal-form procedure, which is a highly complex algorithm, is either absent or only partially implemented. We here present a novel normal-form algorithm for Pauli-LIMDDs, achieving a worst-case speedup from $O(n^3)$ to $O(n^2)$ for an $n$-qubit DD node with a single child node while keeping the $O(n^3)$ run time in case of two distinct children nodes. We implement the algorithm as part of QolDDer, our Pauli-LIMDD simulator for quantum circuits, written from scratch in C/C++. The implementation realizes the theoretically-proven advantages of Pauli-LIMDDs on Clifford circuits, is significantly faster than the existing LIMDD simulators on such circuits, and on a public quantum-circuit data set often outperforms them by an order of magnitude. In the future, we envision that our work will enable further application and development of LIMDD variants, not only for quantum design tasks, but also for analysis of linear-algebra-based systems in general.
• Abstract（参考訳）: 決定図(DD)データ構造は、ベクトルを正規形式にし、次いで等価なものをマージすることにより、高速な線形代数計算を可能にし、最小サイズのDDが同値関係を変調する。 実りある応用領域は量子回路シミュレーションであり、ベクトルは量子状態を表す。 Local Invertible Map Decision Diagram (LIMDD) 型、LIM-等価ベクトル(典型的にはパウリゲート等価)をマージし、クリフォード回路といくつかの高Tカウント回路を効率的にシミュレートでき、理論上は他のDD変種を含むよく発達したデータ構造よりも指数関数的に高速にシミュレーションできることが証明されている。 しかし、これらの指数関数的優位性は、非常に複雑なアルゴリズムである正規形式プロシージャが欠如しているか、部分的にのみ実装されている既存の実装において完全に実現されていない。 ここでは,1つの子ノードを持つ$n$-qubit DDノードに対して,$O(n^3)$から$O(n^2)$への最悪のケース高速化を実現するとともに,$O(n^3)$ランタイムを2つの子ノードで保持する,新しい正規形式アルゴリズムを提案する。 C/C++でスクラッチから記述した量子回路のパウリLIMDDシミュレータであるQolDDerの一部として,本アルゴリズムを実装した。 この実装は、クリフォード回路上のパウリ-LIMDDの理論的に証明された利点を実現し、これらの回路上の既存のLIMDDシミュレータよりもはるかに高速であり、公開量子回路データセットでは、しばしば桁違いに性能が向上する。 将来的には、量子設計タスクだけでなく、一般の線形代数系の解析にもLIMDDのさらなる応用と開発が期待できる。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Improved quantum circuits for division [42.76841620787673]
  様々な整数分割アルゴリズムのための新しいフォールトトレラント量子回路を開発した。 回路は最大76.08%、68.35%のT数とCNOT数を実現している。
  論文  参考訳（メタデータ） (2026-03-18T13:41:43Z)
• Constant-Factor Improvements in Quantum Algorithms for Linear Differential Equations [0.4199844472131922]
  我々は、ハミルトニアンシミュレーションアルゴリズムの線形結合である有望な新しい量子微分方程式解法に対する定数係数境界を証明した。 我々の新しい公式は、少なくとも2桁の精度で従来の状態よりも改善され、状態の準備にかなりのコストがかかる場合、スピードアップははるかに大きくなる可能性がある。
  論文  参考訳（メタデータ） (2025-06-25T18:50:44Z)
• Quantum many-body simulations with PauliStrings.jl [0.0]
  We present the Julia package PauliStrings for quantum many-body Simulations。 パウリ群上の高速な演算は、パウリ弦をバイナリで符号化することで行う。 この表現は任意の幾何を容易に符号化できることを示す。
  論文  参考訳（メタデータ） (2024-10-12T21:18:47Z)
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
  量子格子ボルツマン法(QLBM)における非圧縮性ナビエ-ストークス方程式の多重回路アルゴリズムを提案する。 提案法は2次元蓋駆動キャビティフローに対して検証および実証を行った。
  論文  参考訳（メタデータ） (2024-01-20T15:32:01Z)
• A Quadratic Speedup in the Optimization of Noisy Quantum Optical Circuits [5.074606924176912]
  光子数分解(PNR)検出器を用いた線形光量子回路は、ガウスボソンサンプリング(GBS)とゴッテマン・キタエフ・プレスキル(GKP)のような非ガウス状態の準備の両方に使用される。 本稿では,回路パラメトリゼーションに関する検出確率,条件状態,およびそれらの勾配を計算するアルゴリズム群を紹介する。 これらのアルゴリズムは、オープンソースのフォトニック最適化ライブラリMrMustardで実装され、使用可能である。
  論文  参考訳（メタデータ） (2023-03-15T18:51:36Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)

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

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