論文の概要: Prefix-free quantum Kolmogorov complexity
- arxiv url: http://arxiv.org/abs/2101.11686v1
- Date: Wed, 27 Jan 2021 21:03:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-13 19:51:34.025683
- Title: Prefix-free quantum Kolmogorov complexity
- Title（参考訳）: プレフィックスフリー量子コルモゴロフ複雑性
- Authors: Tejas Bhojraj
- Abstract要約: 弱ソロワ乱数および量子シュノーラー乱数状態の初期セグメントは、$QK$という意味では非圧縮的であることを示す。
ソロワランダムネスと$K$の間のいくつかの接続は、ソロワランダムネスのシャイティン型特徴づけを含むが、弱ソロワランダムネスと$QK$の間にあるものへと続く。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce quantum-K ($QK$), a measure of the descriptive complexity of
density matrices using classical prefix-free Turing machines and show that the
initial segments of weak Solovay random and quantum Schnorr random states are
incompressible in the sense of $QK$. Many properties enjoyed by prefix-free
Kolmogorov complexity ($K$) have analogous versions for $QK$; notably a
counting condition.
Several connections between Solovay randomness and $K$, including the Chaitin
type characterization of Solovay randomness, carry over to those between weak
Solovay randomness and $QK$. We work towards a Levin-Schnorr type
characterization of weak Solovay randomness in terms of $QK$.
Schnorr randomness has a Levin-Schnorr characterization using $K_C$; a
version of $K$ using a computable measure machine, $C$. We similarly define
$QK_C$, a version of $QK$. Quantum Schnorr randomness is shown to have a
Levin-Schnorr and a Chaitin type characterization using $QK_C$. The latter
implies a Chaitin type characterization of classical Schnorr randomness using
$K_C$.
- Abstract（参考訳）: 古典的なプレフィックスのないチューリングマシンを用いて密度行列の記述的複雑性を測る量子-K(QK$)を導入し、弱ソロワ乱数状態と量子シュノーラー乱数状態の初期セグメントが$QK$の意味では非圧縮的であることを示す。
プレフィックスフリーのコルモゴロフ複雑性(k$)が享受する多くの特性は、類似のバージョンが$qk$、特にカウント条件を持つ。
solovayランダムネスと$k$のいくつかの関係は、solovayランダムネスのchaitin型キャラクタリゼーションを含む、弱いsolovayランダムネスと$qk$の間の関係に引き継がれる。
我々は、$QK$という観点で弱ソロワ確率のレヴィン・シュノーラー型特徴づけについて研究する。
シュノアランダムネスは、$K_C$、計算可能な測度マシンを使用する$K$のバージョンである$C$を用いてレヴィン=シュノア特性を持つ。
同様に$qk_c$という$qk$のバージョンを定義します。
量子Schnorrランダム性は、$QK_C$を用いてLevin-SchnorrとChaitin型の特徴を持つ。
後者は、$K_C$ を用いた古典的なシュノアランダムネスのChaitin型特徴づけを意味する。
関連論文リスト
- Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity [6.812247730094931]
任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。
また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
論文 参考訳（メタデータ） (2023-09-25T09:50:15Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Efficient Certifiable Randomness from a Single Quantum Device [6.531546527140474]
本研究では,ランダム性の発生率に対処するために,Learning With問題におけるリークレジリエンス特性を用いる。
我々の新しいプロトコルは、一定ラウンドで$Omega(n)$new bits of randomnessを証明できる。
論文 参考訳（メタデータ） (2022-04-24T20:32:17Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Algorithmic Randomness and Kolmogorov Complexity for Qubits [0.0]
Nies and Scholz defined quantum Martin-L of randomness (q-MLR) for state ( qubitstrings)
量子ソロワランダム性の概念を定義し、純粋に線型代数的手法を用いてq-MLRと等価であることを示す。
大数の法則の量子アナログが量子シュノーラーランダム状態に対して成り立つことが示されている。
論文 参考訳（メタデータ） (2021-06-27T16:52:56Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z) - Variational Quantum Linear Solver [0.3774866290142281]
本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。
リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
論文 参考訳（メタデータ） (2019-09-12T17:28:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。