論文の概要: Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography
- arxiv url: http://arxiv.org/abs/2608.20113v1
- Date: Thu, 20 Aug 2026 14:44:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-21 20:28:51.601714
- Title: Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography
- Title（参考訳）: 三重効率シャドウトモグラフィーにおける分画色推定への反例
- Abstract要約: King, Gosset, Kothari, Babbush の Conjecture 13 は、$B_(varrho)$ が任意の量子状態 $varrho$ において期待値が少なくとも$$ であるようなパウリ観測可能な集合であるなら、反可換グラフ $G$ は$B_(varrho)$ によって誘導される。
言い換えれば、$_f cdot 2 le であるような定数 $C$ が存在すると断言する。
- 参考スコア（独自算出の注目度）: 1.529342790344802
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Fractional graph colorings are useful for the Shadow tomography of Pauli observables. In practice, it is desirable that any experimentally interesting set of Pauli operators has a small fractional chromatic number $χ_{f}$ for its anticommutation graph. Conjecture 13 in King, Gosset, Kothari, and Babbush [PRX Quantum 6, 010336 (2025)] states that if $B_ε(\varrho)$ is the set of Pauli observables having expectation value magnitude at least $ε$ in some given quantum state $\varrho$, then the fractional chromatic number of the anticommutation graph $G$ induced by $B_ε(\varrho)$ is $O(ε^{-2})$. In other words, it asserts that there exists a constant $C$ such that $χ_{f} \cdot ε^2 \leq C$ on all states and graphs. If the conjecture were true, it would imply that there exists a triply efficient Pauli shadow tomography algorithm for {\it any} subset $S$ of Pauli observables, provided that there is also an efficient fractional coloring algorithm for the set $B_ε$. Here we show that the conjecture is false by constructing a family of states and observables for which no finite $C$ satisfying the bound exists. We also give a more general construction relying on the commutation index or $β$ number of a graph. The key ingredient in the proofs can be seen as an instance of the amplification trick, where fractional chromatic numbers, $β$ numbers, and expectation values are amplified through lexicographic graph products.
- Abstract（参考訳）: フラクショナルグラフ色付けは、パウリ天文台のシャドウ断層撮影に有用である。
実際には、パウリ作用素の実験的に興味深い集合が、その反可換グラフに対して小さな分数的な色数 $ _{f}$ を持つことが望ましい。
King, Gosset, Kothari, and Babbush [PRX Quantum 6, 010336 (2025)] における帰納法 13 は、$B_ε(\varrho)$ が、ある与えられた量子状態において少なくとも$ε$ の期待値を持つパウリ可観測値の集合であるならば、その反可換グラフの分数色数 $G$ が$B_ε(\varrho)$ によって誘導され$O(ε^{-2})$ となることを言う。
言い換えれば、すべての状態とグラフに対して$ ε^2 \leq C$ となるような定数 $C$ が存在すると断言する。
もしこの予想が真であれば、集合の$B_ε$に対して効率的な分数カラー化アルゴリズムが存在することを仮定すると、任意の部分集合の$S$ of Pauli observablesに対して、三重に効率的なパウリ影トモグラフィーアルゴリズムが存在することを意味する。
ここでは、境界を満たす有限$C$が存在しない状態と可観測物の族を構成することによって、予想が偽であることを示す。
また、より一般的な構成は、可換指数やグラフの$β$数に依存する。
証明の鍵となる要素は、分数的な色数、$β$数、および期待値が語彙グラフ積によって増幅される増幅トリックの例と見なすことができる。
関連論文リスト
- The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。
我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
論文 参考訳（メタデータ） (2026-08-03T17:57:01Z) - Quantum Colorings of Spheres [0.0]
Sn-1$ が量子的に $n$-colorable であれば、$n=2$ または $n$ が 4 の倍数であることを示し、次数 $n$ のアダマール行列が存在するたびに逆が成り立つことを示す。
Sn-1$ が階数 1 の量子 $n$-色付けを認め、かつ、$n が 2,4,8$ である場合に限り、Zeng と Zhang の予想を定めている。
論文 参考訳（メタデータ） (2026-06-09T13:49:08Z) - Nonasymptotic bounds for quantum purity amplification [0.9969485010222057]
量子純度増幅では、ノイズの多い量子状態 $in mathbbCd times d$ の $n$ コピーが与えられ、主固有状態 $|v_drangle$ の $k$ コピーを作成するように要求される。
いくつかの先行研究は、この問題に対して情報理論的に最適なアルゴリズムを導出したが、それらの証明は、標本数$n$が無限大になる傾向にあるため、体制の中でのみ示される。
論文 参考訳（メタデータ） (2026-05-26T16:39:24Z) - Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。
A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。
A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
論文 参考訳（メタデータ） (2025-09-15T14:26:11Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Monogamy of entanglement between cones [43.57338639836868]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。
我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文 参考訳（メタデータ） (2022-06-23T16:23:59Z) - The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum
Security of iMHFs [6.305950347749109]
本稿では,量子コンピューティングにおけるNo-Deletion Theoremによる追加制約を捉える並列可逆ペブブリングゲームを提案する。
我々は、いくつかの重要なグラフの可逆空間時間複雑性を解析するために、新しい可逆ペブブリングゲームを適用した。
論文 参考訳（メタデータ） (2021-10-08T15:24:31Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - Degree vs. Approximate Degree and Quantum Implications of Huang's
Sensitivity Theorem [4.549831511476248]
すべてのブール関数に対して、$f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$:$f$の次数は、f$の近似次数において最も自明な二次数であることを示す。
f$ がその隣接行列で指定される $n$-頂点グラフの非単調グラフ特性であるならば、$mathrmQ(f)=Omega(n)$ もまた最適である。
論文 参考訳（メタデータ） (2020-10-23T19:21:28Z) - 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) - Quantum Implications of Huang's Sensitivity Theorem [4.970364068620607]
ブール関数の総和が$f$の場合、決定論的クエリ複雑性である$D(f)$は、量子的クエリ複雑性において少なくとも準位であることを示す。
また、Aanderaa-Karp-Rosenberg予想の量子アナログを解くためにもこの結果を利用する。
論文 参考訳（メタデータ） (2020-04-28T00:54:23Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。