論文の概要: Linear growth of quantum circuit complexity

• arxiv url: http://arxiv.org/abs/2106.05305v3
• Date: Wed, 22 Dec 2021 10:57:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-27 04:11:18.446528
• Title: Linear growth of quantum circuit complexity
• Title（参考訳）: 量子回路複雑性の線形成長
• Authors: Jonas Haferkamp, Philippe Faist, Naga B. T. Kothakonda, Jens Eisert, Nicole Yunger Halpern
• Abstract要約: ブラウンとススキンドによるランダム量子回路の複雑さの増大に関する予想を証明した。 回路の複雑さを下げることの難しさを考えると、我々の証明は驚くほど短い。
• 参考スコア（独自算出の注目度）: 0.6299766708197883
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantifying quantum states' complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. We prove a prominent conjecture by Brown and Susskind about how random quantum circuits' complexity increases. Consider constructing a unitary from Haar-random two-qubit quantum gates. Implementing the unitary exactly requires a circuit of some minimal number of gates - the unitary's exact circuit complexity. We prove that this complexity grows linearly with the number of random gates, with unit probability, until saturating after exponentially many random gates. Our proof is surprisingly short, given the established difficulty of lower-bounding the exact circuit complexity. Our strategy combines differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.
• Abstract（参考訳）: 量子状態の複雑性の定量化は、量子コンピューティングからブラックホール物理学まで、科学の様々な分野において重要な問題である。 ブラウンとサスキンドによるランダム量子回路の複雑性の増大に関する顕著な予想を証明する。 Haar-random 2-qubit 量子ゲートからユニタリを構築することを考える。 ユニタリを実装するには、最小数のゲート(ユニタリの正確な回路の複雑さ)の回路が必要である。 この複雑性は、指数関数的に多数のランダムゲートの後に飽和するまで、単位確率を持つランダムゲートの数で線形に増加することが証明される。 回路の複雑さを下げることの難しさを考えると、我々の証明は驚くほど短い。 本手法は微分トポロジーと基本代数幾何学とクリフォード回路の帰納的構成を組み合わせる。

関連論文リスト

• Learning marginals suffices! [14.322753787990036]
  量子状態の学習におけるサンプル複雑度と状態の回路複雑度との関係について検討する。 量子状態の限界を回路の複雑さが低く学習すれば、状態トモグラフィーに十分であることを示す。
  論文  参考訳（メタデータ） (2023-03-15T21:09:29Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• A Complete Equational Theory for Quantum Circuits [58.720142291102135]
  量子回路に対する最初の完全方程式理論を導入する。 2つの回路が同じユニタリ写像を表すのは、方程式を用いて1つをもう1つに変換できる場合に限る。
  論文  参考訳（メタデータ） (2022-06-21T17:56:31Z)
• Estimating the randomness of quantum circuit ensembles up to 50 qubits [9.775777593425452]
  ランダム回路が任意のランダムなユニタリを近似する能力は,その複雑性,表現性,訓練性に影響を及ぼすことを示す。 我々の研究は、大規模テンソルネットワークシミュレーションが量子情報科学におけるオープンな問題に重要なヒントを与える可能性を示唆している。
  論文  参考訳（メタデータ） (2022-05-19T23:43:15Z)
• Short Proofs of Linear Growth of Quantum Circuit Complexity [3.8340125020400366]
  量子ゲートの複雑さは、それを構築するための基本ゲートの最小数として定義され、量子情報と計算において重要な概念である。 近年、ランダムな量子回路から構築される量子ゲートの複雑さは、ビルディングブロックの数とともにほぼ確実に線形に増加することが示されている。
  論文  参考訳（メタデータ） (2022-05-11T17:53:57Z)
• Gaussian initializations help deep variational quantum circuits escape from the barren plateau [87.04438831673063]
  近年、変分量子回路は量子シミュレーションや量子機械学習に広く用いられている。 しかし、ランダムな構造を持つ量子回路は、回路深さと量子ビット数に関して指数関数的に消える勾配のため、トレーニング容易性が低い。 この結果、ディープ量子回路は実用的なタスクでは実現できないという一般的な信念が導かれる。
  論文  参考訳（メタデータ） (2022-03-17T15:06:40Z)
• Transitions in Entanglement Complexity in Random Circuits [0.0]
  簡単な絡み合いのパターンから普遍的で複雑なパターンへのクロスオーバーは、ランダムなクリフォード回路を$T$ゲートでドーピングすることで、どのように駆動できるかを数値的に示す。 この研究は、量子複雑性と複雑な絡み合いは、絡み合いと非安定化剤資源(マジックとしても知られる)の結合に由来することを示している。
  論文  参考訳（メタデータ） (2022-02-05T22:30:24Z)
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
  時間依存ハミルトニアンの下でのユニタリ進化は、量子ハードウェアにおけるシミュレーションの重要な構成要素である。 本稿では、トロッターステップを1ブロックの量子ゲートに圧縮するアルゴリズムを提案する。 この結果、ハミルトニアンのある種のクラスに対する固定深度時間進化がもたらされる。
  論文  参考訳（メタデータ） (2021-08-06T19:38:01Z)
• Sample Complexity of Learning Quantum Circuits [4.329298109272386]
  物理量子回路は、経験的リスク最小化により、量子コンピュータ上でPACを学習可能であることを示す。 我々の結果は、理論と実験の両方において量子機械学習のための貴重なガイドを提供する。
  論文  参考訳（メタデータ） (2021-07-19T18:00:04Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。 本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
  論文  参考訳（メタデータ） (2020-02-27T15:32:08Z)

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

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