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

• arxiv url: http://arxiv.org/abs/2410.23353v2
• Date: Sat, 18 Jan 2025 00:52:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-22 14:14:35.707350
• 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 investigate unitary and state $t$-designs from a computational complexity perspective. First, we address the problems of computing frame potentials that characterize (approximate) $t$-designs. We present a quantum algorithm for computing frame potentials and establish the following: (1) exact computation can be achieved by a single query to a $\# \textsf{P}$-oracle and is $\# \textsf{P}$-hard; (2) for state vectors, deciding whether the frame potential is larger than or smaller than certain values is $\textsf{BQP}$-complete, provided the promise gap between the two values is inverse-polynomial in the number of qubits; and (3) for both state vectors and unitaries, this promise problem is $\textsf{PP}$-complete if the promise gap is exponentially small. Second, we address the promise problems of determining whether a given set is a good or bad approximation to a $t$-design. We 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 remains true even when the set is promised to be either exponentially close to or no closer than a constant to a $1$-design, particularly illustrating that, while unitary and state designs are powerful information resources, it is inherently hard to determine their properties. We further identify the implications of our results across diverse areas, including variational methods for constructing designs, diagnosing quantum chaos through out-of-time-ordered correlators (OTOCs), and exploring emergent designs in Hamiltonian systems.
• Abstract（参考訳）: 計算複雑性の観点から、ユニタリおよび状態 $t$-designs について検討する。 まず、(近似)$t$-designsを特徴付けるフレームポテンシャルの計算問題に対処する。 フレームポテンシャルを計算するための量子アルゴリズムを提案し、以下のことを確立する: (1) 正確な計算は、1つのクエリに対して$\# \textsf{P}$-oracleで達成でき、(2) 状態ベクトルに対して$\# \textsf{P}$-hard; (2) フレームポテンシャルが特定の値より大きいか小さいかを決定する$\textsf{BQP}$-complete; 二つの値間の約束ギャップがクォービット数の逆多項式である場合、(3) 状態ベクトルとユニタリの両方に対して$\textsf{PP}$-complete; この約束問題は指数関数的に小さい場合、$\textsf{PP}$-completeである。 第二に、与えられた集合が$t$-designに対する良いか悪い近似であるかどうかを決定するという約束の問題に対処する。 この問題は任意の定数$t$に対して$\textsf{PP}$であり、$t=1,2$と$3$に対して$\textsf{PP}$-hardであることを示す。 注目すべきは、集合が指数関数的に1ドル設計に近づくか、1ドル設計に近づくと約束されたとしても、特にユニタリ設計と状態設計は強力な情報資源である一方で、それらの性質を決定することは本質的に困難である。 さらに、設計方法のバリエーション、時間外秩序付き相関器(OTOC)による量子カオスの診断、ハミルトン系における創発的設計の探索など、さまざまな分野における結果の意味を同定する。

関連論文リスト

• 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)

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

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