論文の概要: On computational complexity of unitary and state design properties

• arxiv url: http://arxiv.org/abs/2410.23353v1
• Date: Wed, 30 Oct 2024 18:00:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 16:59:30.435190
• Title: On computational complexity of unitary and state design properties
• Title（参考訳）: ユニタリおよび状態設計特性の計算複雑性について
• Authors: Yoshifumi Nakata, Yuki Takeuchi, Martin Kliesch, Andrew Darmawan,
• Abstract要約: 計算複雑性理論の観点から、ユニタリおよび状態 $t$-designs について研究する。 フレームポテンシャルを計算し、1つの正確な計算が可能であることを示す量子アルゴリズムを提案する。 この結果から,単元設計と状態設計の計算的難易度が示唆された。
• 参考スコア（独自算出の注目度）: 2.06242362470764
• License:
• Abstract: We study unitary and state $t$-designs from a computational complexity theory perspective. First, we address the problems of computing frame potentials that characterize (approximate) $t$-designs. We provide a quantum algorithm for computing the frame potential and show that 1. exact computation can be achieved by a single query to a $\# \textsf{P}$-oracle and is $\# \textsf{P}$-hard, 2. for state vectors, it is $\textsf{BQP}$-complete to decide whether the frame potential is larger than or smaller than certain values, if the promise gap between the two values is inverse-polynomial in the number of qubits, and 3. both for state vectors and unitaries, it is $\textsf{PP}$-complete if the promise gap is exponentially small. As the frame potential is closely related to the out-of-time-ordered correlators (OTOCs), our result implies that computing the OTOCs with exponential accuracy is also hard. Second, we address promise problems to decide whether a given set is a good or bad approximation to a $t$-design and show that this problem is in $\textsf{PP}$ for any constant $t$ and is $\textsf{PP}$-hard for $t=1,2$ and $3$. Remarkably, this is the case even if a given set is promised to be either exponentially close to or worse than constant away from a $1$-design. Our results illustrate the computationally hard nature of unitary and state designs.
• Abstract（参考訳）: 計算複雑性理論の観点から、ユニタリおよび状態 $t$-designs について研究する。 まず、(近似)$t$-designsを特徴付けるフレームポテンシャルの計算問題に対処する。 我々は、フレームポテンシャルを計算し、それを示す量子アルゴリズムを提供する。 1. 正確な計算は、$\# \textsf{P}$-oracleへの単一のクエリで達成でき、$\# \textsf{P}$-hardである。 状態ベクトルに対して、フレームポテンシャルが特定の値よりも大きいか小さいかを決定するのは$\textsf{BQP}$-completeである。 3. 状態ベクトルとユニタリの両方の場合、約束ギャップが指数関数的に小さい場合、$\textsf{PP}$-completeである。 フレームポテンシャルは、時間外順序付き相関器(OTOC)と密接に関連しているため、この結果は、OTOCを指数的精度で計算するのも難しいことを示唆している。 第二に、ある集合が$t$-designに対する良いあるいは悪い近似であるかどうかを決定するための保証問題に対処し、この問題は任意の定数$t$に対して$\textsf{PP}$であり、$t=1,2$と$3$に対して$\textsf{PP}$-hardであることを示す。 注目すべきは、与えられた集合が指数関数的に1ドルの設計から離れるよりも近いか悪いかのどちらかであると約束されたとしても、これは同じである。 この結果から,単元設計と状態設計の計算的難易度が示唆された。

関連論文リスト

• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits [6.844618776091756]
  近似ユニタリ$k$-デザインは、平均が最初の$k$モーメントまでのハールランダムアンサンブルに近いようなユニタリと測度のアンサンブルである。 我々はサブシステム間の通信がシステムサイズで$O(1)$である乗法誤り近似単位の$k$-designアンサンブルを構築する。
  論文  参考訳（メタデータ） (2024-07-10T17:43:23Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation [0.0]
  量子モンテカルロ積分(Quantum Monte Carlo integration, QMCI)は、確率変数の予測を推定する量子アルゴリズムである。 本稿では直交級数密度推定に基づいて$U_X(t)$を分割する手法を提案する。 本手法は,回路深度と総クエリ複雑性のスケーリングを,それぞれ$O(sqrtN)$と$O(N3/2)$として達成する。
  論文  参考訳（メタデータ） (2024-06-04T01:50:21Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。 我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。 アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
  論文  参考訳（メタデータ） (2022-12-19T09:36:33Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• 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)
• Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
  N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。 我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。 我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
  論文  参考訳（メタデータ） (2020-10-16T08:10:02Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。 我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
  論文  参考訳（メタデータ） (2020-02-12T03:40:52Z)

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

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