論文の概要: Quantum Černý complexity of binary words

• arxiv url: http://arxiv.org/abs/2609.40154v1
• Date: Wed, 30 Sep 2026 16:55:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.114488
• Title: Quantum Černý complexity of binary words
• Title（参考訳）: 二項語の量子エルン複雑性
• Abstract要約: 我々は、$mathrmqc(w)lelceilsqrt|w|+1,rceil$が、純粋なターゲットを持つ唯一の最短同期語であることを示す。 また、$mathrmqc$は実数の一階理論への還元によって計算可能であることも観察する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the quantum Černý complexity $\mathrm{qc}(w)$ of a binary word $w$: the least dimension $d$ for which there exist quantum channels $A_0,A_1$ on $d\times d$ density matrices and a start state $ρ_0$ such that $w$ is the unique shortest word whose associated channel is constant on the reachable set. We show that $2\le\mathrm{qc}(w)\le\lceil\sqrt{|w|+1}\,\rceil$ for every nonempty $w$, a quadratic saving over the classical analogue, and that constant words are extremal: $\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\,\rceil$. In contrast, $\mathrm{qc}(01^n0)=2$ for every $n\ge 1$, realized by a single qubit whose rotation angle acts as a counter; consequently there is no quantum analogue of the Černý function, and $\mathrm{qc}$ is strongly anti-correlated with intuitive notions of descriptive complexity. We further study the variant $\mathrm{qcp}$ in which the synchronization target is required to be a pure state. We prove that in dimension $2$ no word of length at least $2$ can be a unique shortest synchronizing word with pure target, and we exhibit an explicit qutrit instance, combining a coherent rotation with a measure-and-funnel channel, achieving $\mathrm{qcp}(01^n0)=3$ with target a computational basis state and with synchronization holding universally over all input states. Thus purity of the reset state costs exactly one dimension on this family. We also observe that $\mathrm{qc}$ is computable, by reduction to the first-order theory of the reals.
• Abstract（参考訳）: 量子チャネル $A_0,A_1$ on $d\times d$ density matrices and a start state $ρ_0$ is the unique shortest word that associated channel is constant on the reachable set. 量子チャネル $A_0,A_1$ on $d\times d$ and a start state $ρ_0$。 古典的な類似点に対する二次保存であるすべての空でない$w$に対して、$2\le\mathrm{qc}(w)\le\lceil\sqrt{|w|+1}\,\rceil$を示し、定数語は極大である: $\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\,\rceil$。 対照的に、$\mathrm{qc}(01^n0)=2$は、すべての$n\ge 1$に対して、回転角がカウンタとして作用する単一の量子ビットによって実現される。 さらに、同期ターゲットが純粋な状態であることが要求される変数 $\mathrm{qcp}$ についても検討する。 2ドル以上の長さの単語は、純粋ターゲットと一意に最短の同期語であり得ることを証明し、コヒーレントな回転と測度とを組み合わせた明示的なクォートインスタンスを示し、計算基底状態と全ての入力状態を普遍的に保持する目標となる$\mathrm{qcp}(01^n0)=3$を達成した。 したがって、リセット状態の純度はこの族に対してちょうど1次元のコストがかかる。 また、$\mathrm{qc}$ は実数の一階理論への還元によって計算可能であることも観察する。

関連論文リスト

• Exponential lower bounds for low-degree strategies in position-based quantum cryptography [0.764671395172401]
  非局所量子計算 (NLQC) は、2つの遠隔操作者による2部単位のU_AB$の実装に基づいている。 ユニタリな$U_AB$が存在するかどうかを知ることは、大きなオープンな問題である。 このような指数的下界は、位置ベースの量子暗号のセキュリティに不可欠である。
  論文  参考訳（メタデータ） (2026-09-28T16:43:48Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Optimal Temporal Hiding in Correlated Quantum Reference-Frame Processes [0.0]
  $[n,k]_q$コードの一様コセット法則は、$d(Cperp)$スロット以下のすべての集合で同一である。 ネストされたコードに対して$Csubset D$、ペイロード$R=dim D-dim C$、見えない深さ$t=d_mathrmrel(Cperp,Dperp)-1$、セクター距離$d_mathrmrel(D,C)-1leq n$。
  論文  参考訳（メタデータ） (2026-08-06T06:27:12Z)
• 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)
• On estimating the trace of quantum state powers [11.63482880743131]
  量子状態のトレースを推定する計算複雑性を、$n$-qubit混合量子状態$rho$に対して$texttr(rhoq)$で調べる。 我々の高速化は、正のパワー関数の計算可能な一様近似を量子特異値変換に効率よく導入することで達成される。
  論文  参考訳（メタデータ） (2024-10-17T13:57:13Z)
• Monogamy of entanglement between cones [43.57338639836868]
  モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。 我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
  論文  参考訳（メタデータ） (2022-06-23T16:23:59Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• 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)

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

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