論文の概要: Fast classical simulation algorithms for free-fermion dynamics with magic input

• arxiv url: http://arxiv.org/abs/2609.40187v1
• Date: Wed, 30 Sep 2026 17:07:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.130167
• Title: Fast classical simulation algorithms for free-fermion dynamics with magic input
• Title（参考訳）: マジック入力による自由フェルミオンダイナミクスの高速古典シミュレーションアルゴリズム
• Abstract要約: 非ガウス的な入力を持つ回路のアルゴリズムを開発し、正確なサンプリングと加算誤差と予測値の正確な推定に対処する。 一定サイズのブロックからなる偶数の積入力に対して、対数重みのMajorana単項の期待値を正確に計算できることが示される。
• 参考スコア（独自算出の注目度）: 0.1449880056570423
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical cost of simulating free-fermion (matchgate) circuits depends on both the input state and the computational task. We develop classical algorithms for circuits with non-Gaussian inputs, addressing exact sampling and both additive-error and exact estimation of expectation values. For inputs consisting of $n$ copies of the four-mode magic state, we give exact sampling algorithms, generalizing the Clifford and Clifford algorithm for Boson sampling, for passive and active free-fermion dynamics with worst-case arithmetic cost $O(2^n)$ per sample, without any multiplicative polynomial prefactor. The passive algorithm enables an exact simulation of the non-interacting regime of a recent trapped-ion experiment. We also extend recently developed additive-error estimation of number correlators and related observables from passive to active dynamics with runtime polynomial in $n$ and the inverse additive-error, for input states formed by products of $n$ four-mode even parity states. Our estimator uses a Gaussian-state decomposition adapted to each sampled state to control its second moment. This includes estimation of individual output probabilities. Finally, we show that for even-parity product inputs composed of constant-size blocks, expectation values of Majorana monomials of logarithmic weight can be computed exactly in polynomial time, improving on prior Majorana propagation-style algorithms with quasi-polynomial runtime. The exact algorithm processes the input blocks by dynamic programming, sharing calculations across subsets of Majorana factors. Our suite of algorithms provide classical benchmarks for fermionic quantum simulations across a broad spectrum of computational tasks.
• Abstract（参考訳）: フリーフェミオン回路をシミュレートする古典的なコストは、入力状態と計算タスクの両方に依存する。 非ガウス的な入力を持つ回路に対する古典的アルゴリズムを開発し、正確なサンプリングと加算誤差と予測値の正確な推定に対処する。 4モードマジック状態の$n$のコピーからなる入力に対して、ボーソンサンプリングのためのクリフォードとクリフォードのアルゴリズムを一般化した正確なサンプリングアルゴリズムを与える。 受動的アルゴリズムは、最近の閉じ込められたイオン実験の非相互作用状態の正確なシミュレーションを可能にする。 また、最近開発された数相関器および関連する可観測値の加法エラー推定を、n$のランタイム多項式と逆加法エラーを用いて、$n$4モードのパリティ状態の積によって形成される入力状態に対して、パッシブからアクティブなダイナミクスへ拡張した。 我々の推定器は、各サンプル状態に適応したガウス状態分解を用いて第2モーメントを制御する。 これには、個々の出力確率の推定が含まれる。 最後に, 定数ブロックからなる偶数の積入力に対して, 対数重みのMajoranaモノミアルの期待値を多項式時間で正確に計算し, 準ポリノミカルランタイムを用いたMajorana伝搬式アルゴリズムの改良を図っている。 正確なアルゴリズムは入力ブロックを動的プログラミングによって処理し、Majorana因子のサブセット間で計算を共有する。 我々のアルゴリズムは、幅広い計算タスクにわたるフェルミオン量子シミュレーションのための古典的なベンチマークを提供する。

関連論文リスト

• Are Randomized Quantum Linear Systems Solvers Practical? [0.0]
  ランダム化量子アルゴリズムは、量子シミュレーションと量子線型代数の文脈で提案されている。 ランダム化量子線形系解法における全誤差を制御する全ての関連するパラメータに明示的な境界を与える。 私たちの研究は、理論的なアルゴリズムの提案と効率的なハードウェア実装の橋渡しとして役立ちます。
  論文  参考訳（メタデータ） (2025-10-15T17:12:55Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Solving Free Fermion Problems on a Quantum Computer [0.0]
  計算コストを大幅に削減した量子アルゴリズムにより解くことができる自由フェルミオン問題をいくつか提示する。 メモリコストは指数関数的に改善され、poly log$(N)$である。 シミュレーションアルゴリズムは,自由なボソンシステムを含む他の有望な対象に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2024-09-06T18:25:03Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Unbiased random circuit compiler for time-dependent Hamiltonian simulation [8.694056486825318]
  時間依存ハミルトニアンシミュレーションは量子コンピューティングにおいて重要な課題である。 我々はTDHSのための非バイアスランダムコンパイラを開発した。 相互作用図に基づくスピンモデルと分子系の断熱基底状態の数値シミュレーションを行う。
  論文  参考訳（メタデータ） (2022-12-19T13:40:05Z)
• Algorithms for perturbative analysis and simulation of quantum dynamics [0.0]
  我々はダイソン級数とマグナス展開の両方を計算・利用するための汎用アルゴリズムを開発した。 モデルパラメータ空間の領域における忠実度を近似するためにこれらのツールの使い方を実証する。 計算前のステップを,元法よりも少ない項数で多変数展開問題と表現できることを示す。
  論文  参考訳（メタデータ） (2022-10-20T21:07:47Z)
• 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)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)

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

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