論文の概要: 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ドルの設計から離れるよりも近いか悪いかのどちらかであると約束されたとしても、これは同じである。 この結果から,単元設計と状態設計の計算的難易度が示唆された。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
  同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。 我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。 MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
  論文  参考訳（メタデータ） (2024-05-08T02:17:10Z)
• On the Fine-Grained Hardness of Inverting Generative Models [21.566795159091747]
  生成モデル反転は、コンピュータビジョンとNLPを含む多くの現代のアプリケーションにおいて、コア計算プリミティブである。 本稿では,この問題に対する計算硬さの景観を詳細に把握することを目的としている。 強い指数時間仮説 (SETH) の下では、正確な逆転の計算複雑性が$Omega (2n)$で制限されることを示した。 近似反転のより実践的な問題として、モデル範囲の点が与えられた目標に近いかどうかを決定することが目的である。
  論文  参考訳（メタデータ） (2023-09-11T20:03:25Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。 我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。 アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
  論文  参考訳（メタデータ） (2022-12-19T09:36:33Z)
• 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)
• Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes [12.640283469603357]
  正規化定数の計算における計算複雑性について検討する。 例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
  論文  参考訳（メタデータ） (2021-11-28T14:08:25Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• 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)

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

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