論文の概要: Complexity of detecting large coefficients in the Pauli basis

• arxiv url: http://arxiv.org/abs/2606.19545v1
• Date: Wed, 17 Jun 2026 19:37:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-19 18:23:39.510743
• Title: Complexity of detecting large coefficients in the Pauli basis
• Title（参考訳）: パウリ基底における大係数検出の複雑さ
• Authors: Santiago Cifuentes,
• Abstract要約: 我々は、量子状態$を準備するメカニズムが与えられたとき、ある同一でないパウリ行列$P$が存在して、$|Tr(P)| geq varepsilon$であるかどうかを判断する問題を考える。 BQP$ に属するなら、$NP subseteq BQP$ である。 このことは、パウリ基底における量子状態の最大の係数を見つけるための効率的なトモグラフィー手順の存在に関するオープンな疑問を解決している。
• 参考スコア（独自算出の注目度）: 0.913755431537592
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of deciding, given a mechanism to prepare a quantum state $ρ$ and a value $\varepsilon > 0$, whether there is some non-identity Pauli matrix $P$ such that $|Tr(P ρ)| \geq \varepsilon$. We consider that the state $ρ$ is described as the result of tracing out some of the qubits of a pure state prepared by a circuit $C$, and we assume the promise that either there is a Pauli matrix satisfying the stated condition or, instead, that for all non-identity Pauli matrices $P$ it is the case that $|Tr(Pρ)|\leq \varepsilon/2$. The problem is in $QCMA$, and we prove that if it belongs to $BQP$ then $NP \subseteq BQP$. The result is obtained through a reduction from the minimum-weight code problem, and it holds even when $ρ$ is assumed to be a pure state (i.e. when no qubits are discarded) and $\varepsilon$ is constant. This resolves an open question regarding the existence of efficient tomographic procedures to find the largest coefficients of a quantum state in the Pauli basis: namely, they do not exist under the standard hypothesis $NP \nsubseteq BQP$.
• Abstract（参考訳）: 量子状態 $ρ$ と値 $\varepsilon > 0$ を準備するメカニズムが与えられたとき、ある同一でないパウリ行列 $P$ が存在して $|Tr(P ρ)| \geq \varepsilon$ となるかどうかを判断する。 状態 $ρ$ は、回路$C$ で用意された純粋状態の量子ビットのいくつかを追跡した結果であると考え、その条件を満たすパウリ行列が存在するか、あるいは、全ての非同一性パウリ行列が$P$ であるという約束を、$|Tr(Pρ)|\leq \varepsilon/2$ と仮定する。 問題は$QCMA$であり、もしそれが$BQP$であるなら、$NP \subseteq BQP$である。 その結果は最小ウェイト符号問題からの還元によって得られ、$ρ$が純粋な状態(すなわち、クォービットが破棄されない場合)であり、$\varepsilon$が定数であるとしても成り立つ。 これは、パウリ基底における量子状態の最大の係数を見つけるための効率的なトモグラフィープロシージャの存在に関するオープンな疑問を解決している:すなわち、それらは標準仮説 $NP \nsubseteq BQP$ の下に存在しない。

関連論文リスト

• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
  論文  参考訳（メタデータ） (2024-10-10T06:15:42Z)
• Polynomial-time tolerant testing stabilizer states [4.65004369765875]
  アルゴリズムは未知の$n$-qubit量子状態 $|psirangle promise $(i)$ $|psirangle$のコピーを与える。 すべての$varepsilon_1>0$と$varepsilonleq varepsilon_C$に対して、どちらが正しいかを決定する$textsfpolyが存在することを示す。 我々の証明には、量子状態に対するガウワーズノルムの新しい定義、量子状態のガウワーズ-3$のノルムに対する逆定理、および安定化器被覆に対する新しい境界が含まれる。
  論文  参考訳（メタデータ） (2024-08-12T16:56:33Z)
• Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
  計算基底の部分集合である$S$に対する部分集合状態は [ frac1sqrt|S|sum_iin S |irangle である。 固定された部分集合サイズ $|S|=s$ に対して、$s = 2n/omega(mathrmpoly(n))$ と $s=omega(mathrmpoly(n))$ が与えられたとき、ランダムな部分集合状態は情報理論上はHaarランダム状態と区別できないことを示す。
  論文  参考訳（メタデータ） (2023-12-23T15:52:46Z)
• Pauli-based model of quantum computation with higher-dimensional systems [0.0]
  パウリベースの計算(英: Pauli-based calculation、PBC)は、量子ビットを用いた量子計算の普遍モデルである。 奇数原始次元系のPBCを一般化し、その普遍性を実証する。
  論文  参考訳（メタデータ） (2023-02-27T12:05:13Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。 偏光理論への我々の結果の即時適用について述べる。
  論文  参考訳（メタデータ） (2022-05-30T18:01:34Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Testing matrix product states [5.225550006603552]
  未知の状態$|psirangle$が特性試験モデルにおける行列積状態(MPS)かどうかをテストする。 MPS(英: MPS)は、量子多体系の研究で生じる物理関連量子状態のクラスである。
  論文  参考訳（メタデータ） (2022-01-05T21:10:50Z)
• 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)

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

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