「量子化された複雑さ」に関する研究はありますか?

私はアルゴリズムと複雑さの理論で働く研究学者ですが、私はある程度パラメーター化された複雑さを使用しています。
量子複雑度の研究者がパラメータ化された複雑さを使用し始めたかどうかは分かりませんので、私はそれについてコメントしません。私はGoogleで検索しようとしましたが、何かを見つけることができませんでした。

Question : Are there works on “quantum
parametrized complexity”?

ベストアンサー

私が知る限り、パラメータ化された複雑さ理論はこれまで量子コンピューティングに形式的に導入されていませんでした。

しかし、現場の多くの問題は、局所的なハミルトニアン演算子の一定のスペクトルギャップや様々な行列の有界条件数のような重要なパラメータが固定されると、扱いやすいものとしてよく知られている。パラメータを固定すると、問題の扱いやすいサブクラス(Matrix
Product
StatesとLieb-Robinson境界を参照)や効率的な古典的アルゴリズムや量子アルゴリズム(Harrow-Hassidim-Lloydアルゴリズムなど)が得られることがよくあります。

固定パラメータトラクタビリティ(FPT)文献の標準パラメータを明示的に使用するいくつかの研究がある。

  • Markov and Shi [https://arxiv.org/abs/quant-ph/0511069] show how
    to efficiently and classically compute acceptance probabilities of
    quantum circuits viewed as tensor networks with bounded
    tree-width
  • Bravyi [https://arxiv.org/abs/0801.2989] shows how to
    contract matchgate circuits on non-planar graphs with bounded
    genus
  • Van den Nest and Briegel [https://arxiv.org/pdf/quant-ph/0610040.pdf] show
    that measurement-based quantum computing, which is performed on a
    family of graph states G, can be classically efficiently simulated
    if G has a decidable C$_2$MS logic theory (based on a result of
    Courcelle and Oum implying bounded rank-width of such graphs).

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です