論文の概要: The Parameterized Complexity of Quantum Verification

• arxiv url: http://arxiv.org/abs/2202.08119v1
• Date: Wed, 16 Feb 2022 14:53:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-25 16:27:17.655180
• Title: The Parameterized Complexity of Quantum Verification
• Title（参考訳）: 量子検証のパラメータ化複雑性
• Authors: Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, Bryan O'Gorman
• Abstract要約: 量子回路の整合性の問題に対して,非クリフォードゲート数で指数関数的にスケーリングすることで問題を解くアルゴリズムが存在することを示す。 我々は、サーキット適合性のインスタンスの$T$-countと$W$-stateの$$$-countに新しい下位境界を導出する。
• 参考スコア（独自算出の注目度）: 7.7155343772895275
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We initiate the study of parameterized complexity of $\textsf{QMA}$ problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem of parameterized quantum circuit satisfiability, there exists a classical algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates but only polynomially with the system size. This result follows from our main result, that for any Clifford + $t$ $T$-gate quantum circuit satisfiability problem, the search space of optimal witnesses can be reduced to a stabilizer subspace isomorphic to at most $t$ qubits (independent of the system size). Furthermore, we derive new lower bounds on the $T$-count of circuit satisfiability instances and the $T$-count of the $W$-state assuming the classical exponential time hypothesis ($\textsf{ETH}$). Lastly, we explore the parameterized complexity of the quantum non-identity check problem.
• Abstract（参考訳）: 我々は,問題記述における非クリフォードゲート数の観点から,$\textsf{qma}$ 問題のパラメータ化複雑性の研究を開始する。 パラメータ化量子回路の整合性の問題に対して,非クリフォードゲートの数で指数関数的にスケールするが,システムサイズでのみ多項式的にしか解決できない古典的アルゴリズムが存在することを示す。 この結果は,任意の Clifford + $t$$T$-gate 量子回路整合性問題に対して,最適目撃者の探索空間は,少なくとも$t$ qubits に同型な安定化部分空間に還元することができる(システムサイズに依存しない)。 さらに、回路充足可能性インスタンスの$t$-countと古典的な指数時間仮説($\textsf{eth}$)を仮定した$w$-stateの$t$-countの新たな下限を導出する。 最後に,量子非同一性チェック問題のパラメータ化複雑性について検討する。

関連論文リスト

• Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
  本稿では,AQC(Adiabatic Quantum Computation)と同様,量子計算のためのフレームワークを提案する。 ポアソン過程によって決定された間隔でランダムデファーズ演算を行うことにより、特定の固有値に関連する固有空間を追跡することができる。 有限性に対する単純な微分方程式を導出し、アルゴリズムのクラスの時間複雑性を境界とする一般定理を導出する。
  論文  参考訳（メタデータ） (2024-06-06T11:33:29Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
  平均ケース複雑性理論に基づいて,$m=Omega(n2+delta+epsilon)$のとき,max-k-SSAT が平均計算アルゴリズムであることを示す。 また、平均ケース複雑性理論に基づいて$m=Omega(n2+delta+epsilon)$のとき、max-k-SSATが平均であることが証明される。
  論文  参考訳（メタデータ） (2024-03-05T15:03:47Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。 提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。 我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
  論文  参考訳（メタデータ） (2023-08-06T10:24:23Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Estimating Gibbs partition function with quantumClifford sampling [6.656454497798153]
  分割関数を推定するハイブリッド量子古典アルゴリズムを開発した。 我々のアルゴリズムは浅い$mathcalO(1)$-depth量子回路を必要とする。 浅層量子回路は、現在利用可能なNISQ(ノイズ中間スケール量子)デバイスにとって極めて重要であると考えられている。
  論文  参考訳（メタデータ） (2021-09-22T02:03:35Z)

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

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