論文の概要: An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group
- arxiv url: http://arxiv.org/abs/2610.05752v1
- Date: Mon, 05 Oct 2026 03:57:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-10 04:41:17.59927
- Title: An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group
- Title（参考訳）: 対称群の文字に対する効率的なハミルトン型量子アルゴリズム
- Abstract要約: 我々は、ハミルトン進化の列で量子キャラクタ状態を作成するための、代替的で単純なアルゴリズムを与える。
また、1Dで最寄りのゲートのみを使用する再構成可能なキュービットによる効率的な実装も提供する。
対称オービフォールド共形場理論の絡み合いエントロピーへの応用についても論じる。
- 参考スコア（独自算出の注目度）: 1.4323566945483497
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Consider a quantum state vector proportional to any given column of the character table of the symmetric group ($S_n$), corresponding to a superposition over the irreps weighted by the character values. It was recently argued that sampling from this state is classically hard under reasonable complexity-theoretic assumptions, while there exists an efficient quantum algorithm for preparing this character state using the quantum Fourier transform (QFT) over $S_n$ [arXiv:2501.12579]. We give an alternative, simpler algorithm to prepare this character state with a sequence of Hamiltonian evolutions, as well as an efficient implementation with reconfigurable qubits that uses only nearest-neighbor gates in 1D. The gate complexity, accounting for Hamiltonian simulation errors, depends on the choice of the column: For fixed target state error, the estimated sufficient total gate count ranges from as few as $O(n)$ gates for the $n$-cycle column, to $\widetilde O(n^{1.75})$ gates near the conjecturally classically hard parameter regime, to provably $\widetilde O(n^{2.5})$ gates in the worst case. In contrast, the QFT subroutine in the prior approach uses $\widetilde O(n^3)$ gates. Our gate count estimates come from leading-order state-dependent Trotter error analysis, and the proven worst-case bound relies on a QSVT-based Hamiltonian simulation method; numerical benchmarks of the Trotter-based protocol suggest that the estimates are conservative. Furthermore, we generalize our protocol to give an explicit algorithm for the quantum character transform (QCT) over $S_n$ using $\widetilde O(n^{2.5})$ gates and $O(n)$ qubits. An application to entanglement entropy of symmetric orbifold conformal field theories is also discussed.
- Abstract（参考訳）: 対称群(S_n$)の文字テーブルの任意の列に比例する量子状態ベクトルを、文字値に重み付けされたイデム上の重ね合わせに対応する。
量子フーリエ変換 (QFT) を$S_n$ [arXiv:2501.12579] で生成する効率的な量子アルゴリズムが存在するのに対し、この状態からのサンプリングは古典的には複雑性理論的な仮定の下で難しいと最近議論された。
我々は、ハミルトン進化の列でこの文字状態を作成するための代替的、より単純なアルゴリズムと、1Dに最も近いゲートのみを使用する再構成可能なキュービットを用いた効率的な実装を提供する。
固定された目標状態誤差に対して、推定された合計ゲート数は、$n$-cycle列の$O(n)$ゲートから$\widetilde O(n^{1.75})$ゲートまで、最悪の場合は$\widetilde O(n^{2.5})$ゲートまでの範囲である。
対照的に、以前のアプローチのQFTサブルーチンは$\widetilde O(n^3)$ gatesを使用する。
我々のゲートカウント推定は、先行状態依存型トロッター誤差解析によるものであり、証明された最悪のケース境界はQSVTベースのハミルトンシミュレーション法に依存しており、トロッターベースのプロトコルの数値ベンチマークは、推定が保守的であることを示唆している。
さらに、我々は、$\widetilde O(n^{2.5})$ gates と $O(n)$ qubits を用いて、量子文字変換(QCT)の明示的なアルゴリズムを$S_n$で提供するようにプロトコルを一般化した。
対称オービフォールド共形場理論の絡み合いエントロピーへの応用についても論じる。
関連論文リスト
- Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。
我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文 参考訳（メタデータ） (2026-09-30T17:51:21Z) - Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。
任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
論文 参考訳（メタデータ） (2026-07-22T07:41:32Z) - Adiabatic Quantum Phase Estimation [47.3103723337301]
量子位相推定(QPE)は、ハミルトニアンの固有値をハイゼンベルク制限時間$T= (1/)$の精度で推定する中心的アルゴリズムプリミティブである。
QPEの標準ゲートベースの実装は、深く制御された時間進化回路を必要とし、アナログハードウェアに固有のものではない。
最適ハイゼンベルク制限スケーリング$T = Oleft( frac1 logleft(-1right)right)$を両精度で達成するQPEのための単純な断熱プロトコルを提案する。
論文 参考訳（メタデータ） (2026-05-21T17:31:36Z) - Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。
この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文 参考訳（メタデータ） (2025-08-28T17:04:18Z) - Compact Circuits for Constrained Quantum Evolutions of Sparse Operators [0.0]
我々は、コンパクトな量子回路を構築するための一般的な枠組みを導入し、ハミルトンのリアルタイム進化を$H = sigma P_B$という形で実現する。
我々はまた、量子コンピューティングで広く使われているトランスポジションゲートを構築し、文学における最もよく知られた構成よりも効率的にスケールする。
論文 参考訳（メタデータ） (2025-04-12T08:47:59Z) - High-precision and low-depth eigenstate property estimation: theory and resource estimation [2.6811507121199325]
量子多体系の固有状態特性を推定することは、古典的および量子コンピューティングの双方にとって、長年にわたる、挑戦的な問題である。
本稿では,固有状態に対する固有値と観測可能な期待値を推定するランダムサンプリングアルゴリズムのフルスタック設計を提案する。
論文 参考訳（メタデータ） (2024-06-06T17:54:26Z) - Local Hamiltonian decomposition and classical simulation of parametrized
quantum circuits [0.0]
我々は、量子回路(PQC)を$n$ qubitsでシミュレートするために、O(K, 2n)$という古典的な複雑性のアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-01-24T00:30:31Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。