論文の概要: On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
- arxiv url: http://arxiv.org/abs/2610.25138v1
- Date: Sun, 18 Oct 2026 09:44:51 GMT
- ステータス: 情報取得中
- システム内更新日: 2026-10-20 22:40:36.281163
- Title: On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
- Title（参考訳）: 量子回路検証のためのレベル同期木オートマタの複雑さについて
- Abstract要約: レベル同期ツリーオートマトン (LSTA) は量子状態の集合を表すために最近導入された。
検証に関連する2つの軸に沿ったLSTAについて検討する。
- 参考スコア（独自算出の注目度）: 6.177271244427367
- License:
- Abstract: Reliable quantum computation requires methods for verifying quantum circuits. Level-synchronized tree automata (LSTAs) were recently introduced to represent sets of quantum states for this purpose. We study LSTAs along two axes relevant to verification: the complexity of their decision problems and the size of their representations under circuit operations. We prove that acyclic LSTAs have NP-complete nonemptiness and $Π_2^P$-complete language inclusion, and that general language inclusion is EXPSPACE-complete. We further prove inherent quadratic representation growth under individual quantum gates in a fixed qubit order, and give an adjacent-qubit reordering construction that preserves level synchronization. These results clarify the scope of applicability of the automata-theoretic toolbox for quantum circuit verification.
- Abstract（参考訳）: 信頼性の高い量子計算には、量子回路を検証する方法が必要である。
レベル同期ツリーオートマトン(LSTA)はこの目的のために量子状態の集合を表すために最近導入された。
本稿では,2軸のLSTAについて,回路演算における決定問題の複雑性と表現サイズについて検討する。
我々は,非巡回LSTAがNP完全非空さと$ ^P$完全言語包含を持ち,一般言語包含がEXPSPACE完全であることを証明した。
さらに、固定量子ビット順序で個々の量子ゲートの下での固有二次的表現成長を証明し、レベル同期を保った隣接量子ビットの並べ替え構造を与える。
これらの結果は、量子回路検証のためのオートマタ理論ツールボックスの適用範囲を明らかにした。
関連論文リスト
- Quantum Interactive Oracle Proofs [2.0482700732041397]
量子対話型Oracle Proofs(qIOPs)の研究を紹介する。
我々は、qIOPの2つの主要な構成を示し、どちらも無条件である。
我々は、独立した興味を持つかもしれない多ビット検定の新規な単検定器を導入する。
論文 参考訳（メタデータ） (2026-01-19T09:30:38Z) - Extending Quantum Perceptrons: Rydberg Devices, Multi-Class Classification, and Error Tolerance [67.77677387243135]
量子ニューロモーフィックコンピューティング(QNC)は、量子計算とニューラルネットワークを融合して、量子機械学習(QML)のためのスケーラブルで耐雑音性のあるアルゴリズムを作成する
QNCの中核は量子パーセプトロン(QP)であり、相互作用する量子ビットのアナログダイナミクスを利用して普遍的な量子計算を可能にする。
論文 参考訳（メタデータ） (2024-11-13T23:56:20Z) - QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum
Circuits [82.50620782471485]
QuantumSEAはノイズ適応型量子回路のインタイムスパース探索である。
1)トレーニング中の暗黙の回路容量と(2)雑音の頑健さの2つの主要な目標を達成することを目的としている。
提案手法は, 量子ゲート数の半減と回路実行の2倍の時間節約で, 最先端の計算結果を確立する。
論文 参考訳（メタデータ） (2024-01-10T22:33:00Z) - Complexity for one-dimensional discrete time quantum walk circuits [0.0]
1次元離散時間量子ウォーク(DTQW)から導かれる混合状態密度演算子の複雑性を計算する。
この複雑さは、混合状態の正準浄化から得られる2量子ビット量子回路を用いて計算される。
論文 参考訳（メタデータ） (2023-07-25T12:25:03Z) - Majorization-based benchmark of the complexity of quantum processors [105.54048699217668]
我々は、様々な量子プロセッサの動作を数値的にシミュレートし、特徴付ける。
我々は,各デバイスの性能をベンチマークラインと比較することにより,量子複雑性を同定し,評価する。
我々は、回路の出力状態が平均して高い純度である限り、偏化ベースのベンチマークが成り立つことを発見した。
論文 参考訳（メタデータ） (2023-04-10T23:01:10Z) - Quantum process tomography of continuous-variable gates using coherent
states [49.299443295581064]
ボソニックモード超伝導回路におけるコヒーレント状態量子プロセストモグラフィ(csQPT)の使用を実証する。
符号化量子ビット上の変位とSNAP演算を用いて構築した論理量子ゲートを特徴付けることにより,本手法の結果を示す。
論文 参考訳（メタデータ） (2023-03-02T18:08:08Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。