論文の概要: A full dichotomy for Holant$^c$, inspired by quantum computation
- arxiv url: http://arxiv.org/abs/2201.03375v1
- Date: Mon, 10 Jan 2022 14:45:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-01 19:44:18.455159
- Title: A full dichotomy for Holant$^c$, inspired by quantum computation
- Title（参考訳）: 量子計算にヒントを得たHolant$^c$の完全二分法
- Authors: Miriam Backens
- Abstract要約: 我々は、量子情報理論を用いて、簡潔な方法でホラント問題の結果を説明する。
我々は2つの新しい二分法を導出する: 1つは新しい問題の族のためのもので、Holant$+$と呼び、これに基づいてHolant$c$の完全な二分法を構築する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Holant problems are a family of counting problems parameterised by sets of
algebraic-complex valued constraint functions, and defined on graphs. They
arise from the theory of holographic algorithms, which was originally inspired
by concepts from quantum computation. Here, we employ quantum information
theory to explain existing results about holant problems in a concise way and
to derive two new dichotomies: one for a new family of problems, which we call
Holant$^+$, and, building on this, a full dichotomy for Holant$^c$. These two
families of holant problems assume the availability of certain unary constraint
functions -- the two pinning functions in the case of Holant$^c$, and four
functions in the case of Holant$^+$ -- and allow arbitrary sets of
algebraic-complex valued constraint functions otherwise. The dichotomy for
Holant$^+$ also applies when inputs are restricted to instances defined on
planar graphs. In proving these complexity classifications, we derive an
original result about entangled quantum states.
- Abstract（参考訳）: ホラント問題(英: Holant problem)は、代数複素値制約関数の集合によってパラメータ化され、グラフ上で定義される数え上げ問題の族である。
これらはホログラフィックアルゴリズムの理論から生まれ、もともと量子計算の概念に触発されたものだった。
ここでは、量子情報理論を用いて、ホロアン問題に関する既存の結果を簡潔に説明し、2つの新しいディコトミーを導出する:1つは、holant$^+$と呼ばれる新しい問題群であり、それに基づいてholant$^c$の完全な二分法である。
これら2つのホラント問題の族は、ホラント$^c$のときの2つのピンニング関数とホラント$^+$のときの4つの関数の可用性を仮定し、それ以外は代数的複素値制約関数の任意の集合を許容する。
Holant$^+$の二分法は、入力が平面グラフ上で定義されたインスタンスに制限されるときにも適用される。
これらの複雑性分類の証明では、絡み合った量子状態に関する最初の結果が導かれる。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
本稿では,一元性検定における量子クエリの下位境界を証明するための新しい手法を提案する。
すべての得られる下限は$mathsfC$-testerで$mathsfC subseteq mathsfQMA(2)/mathsfqpoly$である。
我々は、$mathsfQMA(2) notsupset mathsfSBQP$と$mathsfQMA/mathsfqpolyの量子オラクルが存在することを示した。
論文 参考訳（メタデータ） (2024-01-15T19:00:36Z) - Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。
複雑性は量子複雑性クラスによって特徴づけられる。
我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
論文 参考訳（メタデータ） (2023-11-28T21:15:30Z) - Non-Linear Transformations of Quantum Amplitudes: Exponential
Improvement, Generalization, and Applications [0.0]
量子アルゴリズムは量子状態の振幅を操作して計算問題の解を求める。
量子状態の振幅に非線形関数の一般クラスを適用するための枠組みを提案する。
我々の研究は、最適化、状態準備、量子化学、機械学習といった分野において、潜在的に多くの応用が可能な重要かつ効率的なビルディングブロックを提供する。
論文 参考訳（メタデータ） (2023-09-18T14:57:21Z) - A polynomial quantum computing algorithm for solving the dualization
problem [75.38606213726906]
2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。
本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-28T18:12:54Z) - Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant
Viewpoint [0.0]
グラフ準同型(Graph homomorphism)は、$mathcalF$ と $mathcalF'$ のそれぞれが 1 つの対称な 0-1 値のバイナリ制約関数を含む特別な場合である。
任意のペアの集合 $mathcalF$ と $mathcalF'$ は、任意の平面#CSPインスタンスに同じ値を与える実数値で任意のアリティ制約関数を示す。
論文 参考訳（メタデータ） (2022-12-06T21:38:40Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - From Holant to Quantum Entanglement and Back [3.825159708387601]
最初にホラント理論の手法を用いて量子絡み合い理論の新しい改良結果を導出する。
次に、制約関数の絡み合い特性を用いて、奇アリティ符号を含むすべての実数値ホラント問題に対して新しい複雑さを導出する。
論文 参考訳（メタデータ） (2020-04-12T21:58:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。