論文の概要: Optimal algorithms for materializing stabilizer states and Clifford gates from compact descriptions
- arxiv url: http://arxiv.org/abs/2604.15405v1
- Date: Thu, 16 Apr 2026 15:34:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-20 22:00:19.590467
- Title: Optimal algorithms for materializing stabilizer states and Clifford gates from compact descriptions
- Title（参考訳）: コンパクト記述による安定化状態とクリフォードゲートの物質化のための最適アルゴリズム
- Authors: Hyunho Cha, Jungwoo Lee,
- Abstract要約: 我々は、O(2n)$時間とO(2n)$空間で動作するアルゴリズムを与える。
その結果,標準チェック行列記述から安定化状態ベクトルを実現するための最適手順が得られた。
これらの結果は密度安定剤とクリフォードの物質化のギャップを埋める。
- 参考スコア（独自算出の注目度）: 5.706918315850497
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Stabilizer states admit compact classical descriptions, but many downstream tasks still require their full amplitude vectors. Since the output itself has size $2^n$, the main algorithmic question is whether one can materialize an $n$-qubit stabilizer state vector in optimal $O(2^n)$ time, rather than paying an additional polynomial overhead. We answer this question in the affirmative. Starting from the standard quadratic-form representation of stabilizer states, we give an algorithm that runs in $O(2^n)$ time and $O(2^n)$ space. The idea is to maintain a cached parity word that records all future off-diagonal quadratic phase increments simultaneously. As consequences, we obtain an optimal procedure for materializing a stabilizer state vector from a standard check-matrix description, and an optimal algorithm for expanding a Clifford tableau into its full dense matrix. These results close the asymptotic gap for dense stabilizer and Clifford materialization.
- Abstract（参考訳）: 安定化器状態はコンパクトな古典的記述を認めるが、多くの下流タスクは依然として完全な振幅ベクトルを必要とする。
出力自体のサイズが 2^n$ であるため、アルゴリズムの主な問題は、追加の多項式オーバーヘッドを支払うのではなく、最適な$O(2^n)$時間で$n$-qubitの安定化状態ベクトルを生成できるかどうかである。
私たちはこの質問を肯定的に答える。
安定化状態の標準的な二次形式表現から始めて、$O(2^n)$時間と$O(2^n)$空間で動作するアルゴリズムを与える。
この考え方はキャッシュされたパリティワードを維持して、全ての未来の対角2次位相を同時に記録することである。
その結果、標準的なチェック行列記述から安定化状態ベクトルを実現するための最適手順と、クリフォードテーブルーをその全密度行列に拡張する最適なアルゴリズムを得る。
これらの結果は密度安定剤とクリフォード物質化のための漸近ギャップを閉じる。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Faster computation of nonstabilizerness [3.8061090528695543]
安定度は、ランクベースのシミュレーターを用いてシミュレーションコストを推定するのに有用なツールである。
安定度を計算するために,より高速な数値アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-24T14:28:15Z) - Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。
また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates [0.9332987715848714]
クリフォードゲートと$O(log n)$非クリフォードゲートで用意された量子状態を効率的に学習するアルゴリズムのペアを与える。
具体的には、$n$-qubit state $|psirangle$を少なくとも$t$非クリフォードゲートで準備するために、我々のアルゴリズムは$mathsfpoly(n,2t,1/varepsilon)$timeと$|psirangle$のコピーを使って、ほとんどのゲートで距離を追跡するために$|psirangle$を学ぶ。
論文 参考訳（メタデータ） (2023-05-22T18:49:52Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
我々は、安定化状態から正準形式への効率よく単純化する方法を示す。
内積の対称性を明らかにするために, 線形依存三重項を特徴付ける。
新たな制御付きPauli $Z$アルゴリズムを用いて、内部積計算のランタイムを$O(n3)$から$O(nd2)$に改善します。
論文 参考訳（メタデータ） (2021-09-20T05:56:25Z) - Improved upper bounds on the stabilizer rank of magic states [0.0]
改良は、マジック状態 $|Trangle=sqrt2-1(|0rangle+eipi/4|1rangle)$ の安定化ランクに $m$ の上限で新しい上限を設定することで得られる。
Clifford ゲートと$m$のインスタンスからなる回路に対して,実行時 $textpoly(n,m) 2m/2$ のシングルキュービット $Z$-rotation ゲートの強いシミュレーションアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-06-14T20:20:51Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。