論文の概要: Circuit Extraction for ZX-diagrams can be #P-hard

• arxiv url: http://arxiv.org/abs/2202.09194v1
• Date: Fri, 18 Feb 2022 13:50:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-24 17:32:35.921255
• Title: Circuit Extraction for ZX-diagrams can be #P-hard
• Title（参考訳）: ZXダイアグラムの回路抽出は#Pハードである
• Authors: Niel de Beaudrap, Aleks Kissinger, John van de Wetering
• Abstract要約: ZX-計算のいくつかの応用は、ZX-ダイアグラムを同等の大きさの量子回路に効率的に変換できることに依存している。 本稿では、回路抽出問題は#P-hardであり、量子回路の強いシミュレーションのように、それ自体が困難であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The ZX-calculus is a graphical language for reasoning about quantum computation using ZX-diagrams, a certain flexible generalisation of quantum circuits that can be used to represent linear maps from $m$ to $n$ qubits for any $m,n \geq 0$. Some applications for the ZX-calculus, such as quantum circuit optimisation and synthesis, rely on being able to efficiently translate a ZX-diagram back into a quantum circuit of comparable size. While several sufficient conditions are known for describing families of ZX-diagrams that can be efficiently transformed back into circuits, it has previously been conjectured that the general problem of circuit extraction is hard. That is, that it should not be possible to efficiently convert an arbitrary ZX-diagram describing a unitary linear map into an equivalent quantum circuit. In this paper we prove this conjecture by showing that the circuit extraction problem is #P-hard, and so is itself at least as hard as strong simulation of quantum circuits. In addition to our main hardness result, which relies specifically on the circuit representation, we give a representation-agnostic hardness result. Namely, we show that any oracle that takes as input a ZX-diagram description of a unitary and produces samples of the output of the associated quantum computation enables efficient probabilistic solutions to NP-complete problems.
• Abstract（参考訳）: zx-calculusは、zx-diagramsを使って量子計算を推論するためのグラフィカル言語であり、任意の$m,n \geq 0$に対して$m$から$n$ qubitsの線形写像を表現するのに使用できる量子回路の柔軟な一般化である。 量子回路最適化や合成などのZX-計算の応用は、ZX-ダイアグラムを同等の大きさの量子回路に効率的に変換できることに依存している。 効率的に回路に変換できるZX-ダイアグラムの族を記述するのに十分な条件がいくつか知られているが、回路抽出の一般的な問題は難しいと推測されている。 すなわち、ユニタリ線型写像を記述する任意のZX-ダイアグラムを等価な量子回路に効率的に変換することは不可能である。 本稿では, 回路抽出問題は#pハードであり, 量子回路の強いシミュレーションと同程度に困難であることを示すことにより, この予想を証明する。 特に回路表現に依存する主要なハードネス結果に加えて、表現非依存のハードネス結果を与える。 すなわち、ユニタリのZX-ダイアグラム記述を入力とし、関連する量子計算の出力のサンプルを生成するようなオラクルは、NP完全問題に対する効率的な確率的解を可能にする。

関連論文リスト

• The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus [55.58528469973086]
  量子コンピュータは、古典的コンピュータが決して起こらない重要な問題を効率的に解決することを約束する。 完全に自動化された量子ソフトウェアスタックを開発する必要がある。 この研究は、今日のツールの"内部"の外観を提供し、量子回路のシミュレーション、コンパイル、検証などにおいてこれらの手段がどのように利用されるかを示す。
  論文  参考訳（メタデータ） (2023-01-10T19:00:00Z)
• Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
  本稿では,高レベル言語で記述された量子回路から,アルゴリズム固有のグラフ状態を作成する量子回路コンパイラを提案する。 この計算は、このグラフ状態に関する一連の非パウリ測度を用いて実装することができる。
  論文  参考訳（メタデータ） (2022-09-15T14:52:31Z)
• Vanishing 2-Qubit Gates with Non-Simplification ZX-Rules [1.0089382889894247]
  量子回路はZX-ダイアグラムに変換することができ、ZX-計算の規則を用いて単純化することができる。 最もよく知られた抽出手順は、2量子ゲートの数を劇的に増やすことができる。 ZX-ダイアグラムの局所的な変化が抽出回路の複雑さに大きく影響するという事実を生かしている。
  論文  参考訳（メタデータ） (2022-09-14T18:43:21Z)
• Equivalence Checking of Quantum Circuits with the ZX-Calculus [3.610459670994051]
  最先端の量子コンピュータは、ますます複雑なアルゴリズムを実行することができる。 潜在的なアプリケーションの設計とテストのための自動メソッドの必要性が高まっます。 近年,この問題に対処する新しい手法が提案されている。
  論文  参考訳（メタデータ） (2022-08-26T18:00:01Z)
• Diagrammatic Analysis for Parameterized Quantum Circuits [0.0]
  本稿では、特にパラメータ化量子回路に適したZX計算の拡張について述べる。 いくつかの新しいZXダイアグラムの書き直し規則とこの設定の一般化を提供する。 ダイアグラム的アプローチは,アルゴリズムの構造と性能に関する有用な洞察を提供する。
  論文  参考訳（メタデータ） (2022-04-04T08:26:20Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。 我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
  論文  参考訳（メタデータ） (2022-02-10T18:59:52Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  現在の世代のノイズの多い中間スケール量子コンピュータ(NISQ)は、チップサイズとエラー率に大きく制限されている。 我々は、自由フェルミオンとして知られる特定のスピンハミルトニアンをシミュレーションするために、量子回路を効率よく圧縮するために局所化回路変換を導出する。 提案した数値回路圧縮アルゴリズムは、後方安定に動作し、$mathcalO(103)$スピンを超える回路合成を可能にするスピンの数で3次スケールする。
  論文  参考訳（メタデータ） (2021-08-06T19:38:03Z)
• Simplification Strategies for the Qutrit ZX-Calculus [0.0]
  ZX-calculusは、ZX-diagramと呼ばれるテンソルネットワークを適切に表現するためのグラフィカル言語である。 ZX計算は、量子回路、凝縮物質系、量子アルゴリズム、量子エラー符号、および数え上げ問題に関する推論に応用を見出した。
  論文  参考訳（メタデータ） (2021-03-11T19:17:28Z)
• Quantum Garbled Circuits [9.937090317971313]
  我々は、与えられた量子回路と量子入力のエンコーディングの計算方法を示し、そこから計算の出力を導出することができる。 我々のプロトコルは、いわゆる$Sigma$フォーマットで、シングルビットチャレンジがあり、入力を最終ラウンドまで遅らせることができる。
  論文  参考訳（メタデータ） (2020-06-01T17:07:01Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。 本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
  論文  参考訳（メタデータ） (2020-02-27T15:32:08Z)
• PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations [77.34726150561087]
  本稿では,量子演算のコヒーレント制御を含む量子計算を表現・推論するためにPBS計算を導入する。 我々はこの言語に方程式理論を加え、それが健全で完備であることが証明された。 我々は、制御された置換の実装やループのアンロールのようなアプリケーションを考える。
  論文  参考訳（メタデータ） (2020-02-21T16:15:58Z)

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

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