論文の概要: On the Simulation Cost of Quantum Finite Automata

• arxiv url: http://arxiv.org/abs/2605.10682v1
• Date: Mon, 11 May 2026 14:59:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.918617
• Title: On the Simulation Cost of Quantum Finite Automata
• Title（参考訳）: 量子有限オートマタのシミュレーションコストについて
• Authors: Zeyu Chen, Junde Wu,
• Abstract要約: 本稿では,有限オートマトンに対する量子優位性の自然な定量尺度として,正確な確率的シミュレーションコストを同定する。 2つの代表モデルに対して鋭いシミュレーション法則を与える。
• 参考スコア（独自算出の注目度）: 17.041789070513758
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper identifies exact probabilistic simulation cost as the natural quantitative measure of quantum advantage for finite automata under strict cutpoints. It gives sharp simulation laws for two representative models. A one-way finite automaton with $c$ classical states and a $q$-dimensional quantum register has exact probabilistic simulation cost $Θ(cq^2)$, while an $n$-dimensional measure-once one-way quantum finite automaton has worst-case cost $Θ(n^2)$. The proofs develop a prepare--test framework, in which prefixes generate the relevant real operator degrees of freedom and suffixes convert them into strict-cutpoint tests. The same obstruction is recast through finite sign-rank matrices, clarifying the role of Forster's spectral method. Placed beside the surrounding two-way separations, these results give a clean hierarchy of finite-automata quantum advantage.
• Abstract（参考訳）: 本稿では、厳密なカットポイント下での有限オートマトンに対する量子優位性の自然な定量尺度として、正確な確率的シミュレーションコストを同定する。 2つの代表モデルに対して鋭いシミュレーション法則を与える。 古典的な$c$と$q$次元量子レジスタを持つ一方向有限オートマトンは、正確な確率的シミュレーションコストが$(cq^2)$であり、一方、$n$次元の測度オンス片方向量子有限オートマトンは、最悪のケースコスト$(n^2)$である。 証明は、プレフィックスが関連する実作用素の次数を生成し、接尾辞がそれらを厳格なカットポイントテストに変換する、準備テストフレームワークを開発する。 同じ障害は有限の符号ランク行列を通して再キャストされ、フォースターのスペクトル法の役割を明確にする。 周囲の2方向分離の横に配置され、これらの結果は有限オートマタ量子優位性のクリーンな階層を与える。

関連論文リスト

• Computational Complexity of Non-Hermitian Quantum Systems [0.0]
  条件付き時間進化は、量子システムが監視され、1つのポストセレクトが測定記録に記録されるときに起こる。 我々は、ポストセレクションと任意の非エルミート・ハミルトンの同値性を確立する。 非エルミート物理学は、量子優位性を保証することも、効率的な古典的シミュレーションを妨げない。
  論文  参考訳（メタデータ） (2025-06-03T22:35:28Z)
• Scalable projected entangled-pair state representation of random quantum circuit states [0.0]
  ランダムな量子回路状態を表すバイダルゲージにおいて,投影された絡み合ったペア状態 (PEPS) の更新を示す。 従来のCPUで128ドル(約1万4000円)の大規模回路を使用すれば、状態の忠実さの普遍的なスケーリングの挙動が分かる。
  論文  参考訳（メタデータ） (2025-04-07T06:47:48Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPは1970年代の量子光学のモデルとしてマッキによって導入された。 ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。 バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
  論文  参考訳（メタデータ） (2023-05-25T08:43:11Z)
• More Optimal Simulation of Universal Quantum Computers [0.0]
  最悪のサンプリングコストは$le(2+sqrt2)xi_t delta-1$であり、$t rightarrow infty$である。 我々は、この68倍のプレファクタを、相関サンプリングにより$t$の先行値の低減により削減する。
  論文  参考訳（メタデータ） (2022-02-02T19:00:03Z)
• Cost-efficient QFA Algorithm for Quantum Computers [0.0]
  修正されたムーア・クラッチフィールド量子有限オートマトン (MCQFA) アルゴリズムを言語 $mathttMOD_p$ に対して提案する。 文献で与えられた元のアルゴリズムの実装と比較して,基底ゲートが少なくて短い量子プログラムが得られる。
  論文  参考訳（メタデータ） (2021-07-05T20:41:18Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。 我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。 ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
  論文  参考訳（メタデータ） (2020-11-24T18:44:57Z)
• Preparation of excited states for nuclear dynamics on a quantum computer [117.44028458220427]
  量子コンピュータ上で励起状態を作成するための2つの異なる方法を研究する。 シミュレーションおよび実量子デバイス上でこれらの手法をベンチマークする。 これらの結果から,フォールトトレラントデバイスに優れたスケーリングを実現するために設計された量子技術が,接続性やゲート忠実性に制限されたデバイスに実用的なメリットをもたらす可能性が示唆された。
  論文  参考訳（メタデータ） (2020-09-28T17:21:25Z)
• Emulating Quantum Interference with Generalized Ising Machines [0.0]
  本稿では、量子ゲートの任意の列を確率的pビットのネットワークにマッピングするための、正確で一般的な手順を提案する。 この構造をボルツマンマシンとみなすことができ、それぞれが初期構成から最終構成へと導かれるファインマンパスを表す。 任意の量子回路を複雑なエネルギー関数を持つボルツマンマシンにマッピングする結果は、確率的資源を持つ量子回路のシミュレーション可能性の境界を推し進める助けとなる。
  論文  参考訳（メタデータ） (2020-07-14T22:10:29Z)
• 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)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。 格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。 NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
  論文  参考訳（メタデータ） (2020-02-25T19:18:36Z)

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

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