論文の概要: Noisy decoding by shallow circuits with parities: classical and quantum
- arxiv url: http://arxiv.org/abs/2302.02870v2
- Date: Tue, 19 Dec 2023 10:35:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-21 03:04:35.724807
- Title: Noisy decoding by shallow circuits with parities: classical and quantum
- Title（参考訳）: パリティを持つ浅い回路による雑音復号:古典的および量子的
- Authors: Jop Bri\"et, Harry Buhrman, Davi Castro-Silva and Niels M. P. Neumann
- Abstract要約: 符号語が正の誤差率で雑音の多いチャネル上で送信される場合, 従来の回路では, 消滅した少数のメッセージのみを正確に復元できることが示される。
我々は、コードワードの$(1/2 - varepsilon)$-fractionが逆向きに破損しても、確率$Omega(varepsilon2)$でアダマール符号を正しく復号する単純な量子回路を与える。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of decoding corrupted error correcting codes with
NC$^0[\oplus]$ circuits in the classical and quantum settings. We show that any
such classical circuit can correctly recover only a vanishingly small fraction
of messages, if the codewords are sent over a noisy channel with positive error
rate. Previously this was known only for linear codes with large dual distance,
whereas our result applies to any code. By contrast, we give a simple quantum
circuit that correctly decodes the Hadamard code with probability
$\Omega(\varepsilon^2)$ even if a $(1/2 - \varepsilon)$-fraction of a codeword
is adversarially corrupted.
Our classical hardness result is based on an equidistribution phenomenon for
multivariate polynomials over a finite field under biased input-distributions.
This is proved using a structure-versus-randomness strategy based on a new
notion of rank for high-dimensional polynomial maps that may be of independent
interest.
Our quantum circuit is inspired by a non-local version of the
Bernstein-Vazirani problem, a technique to generate ``poor man's cat states''
by Watts et al., and a constant-depth quantum circuit for the OR function by
Takahashi and Tani.
- Abstract（参考訳）: 古典的, 量子的設定において, NC$^0[\oplus]$回路で誤り訂正符号を復号する問題を考察する。
符号語が正の誤差率で雑音の多いチャネル上で送信される場合、そのような古典的回路は、わずかなメッセージのみを正確に復元できることを示す。
以前は、これは大きな双対距離を持つ線形コードでしか知られていなかったが、我々の結果はどんなコードにも当てはまる。
対照的に、コードワードの$(1/2 - \varepsilon)$-fractionが逆向きに破損しても、確率$\Omega(\varepsilon^2)$でアダマール符号を正しく復号する単純な量子回路を与える。
我々の古典的硬度結果は、偏りのある入力分布の有限体上の多変量多項式に対する等分散現象に基づいている。
これは独立興味を持つかもしれない高次元多項式写像の新しい階数の概念に基づく構造反転ランダム性戦略を用いて証明される。
我々の量子回路は、bernstein-vazirani問題の非局所バージョン、wattsらによって'poor man's cat states'を生成する技術、そして高橋と谷によるor関数の定数深さ量子回路から着想を得ている。
関連論文リスト
- Quantum Lego Expansion Pack: Enumerators from Tensor Networks [1.489619600985197]
量子量列挙子を最も一般的な形式で計算するための最初のテンソルネットワーク法を提供する。
非(Pauli)安定化器符号の場合、これはコード距離を計算するのに最適なアルゴリズムである。
これらの列挙子は論理的誤り率を正確に計算するために使用することができ、従って任意の単一キュービットやキューディットのエラーチャネルに対してデコーダを構築することができる。
論文 参考訳（メタデータ） (2023-08-09T18:00:02Z) - Pauli Manipulation Detection codes and Applications to Quantum Communication over Adversarial Channels [0.08702432681310403]
我々は、高い確率で全てのパウリエラーを検出する「パウリマニピュレーション検出」コード(PMD)を作成した量子コードを導入し、明示的に構築する。
逆チャネル上での量子通信において,2つのタスクに対して,第1次準最適符号を構築する。
論文 参考訳（メタデータ） (2023-04-13T05:05:35Z) - Local Probabilistic Decoding of a Quantum Code [0.0]
フリップは極めてシンプルで 極端に局所的な古典復号器です
このデコーダの最も低ウェイトな修正不能なエラーは、他の修正不能なエラーよりも修正不能なエラーに近い。
デコーダにランダム性を導入することで、これらの「修正不可能な」エラーを有限確率で修正することができる。
論文 参考訳（メタデータ） (2022-12-14T02:44:26Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array [59.24209911146749]
本稿では,1次元に制約された量子ビット格子の幅と物理閾値の関係について検討する。
我々は、表面コードを用いた最小レベルのエンコーディングでエラーバイアスを設計する。
このバイアスを格子サージャリングサーフェスコードバスを用いて高レベルなエンコーディングで処理する。
論文 参考訳（メタデータ） (2022-12-03T06:16:07Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Towards Demonstrating Fault Tolerance in Small Circuits Using Bacon-Shor
Codes [5.352699766206807]
我々は、量子回路をフォールトトレラントに実装する次のステップについて研究する。
偏極雑音モデルにおけるパウリ誤差率$p$の擬似閾値を計算する。
複数ラウンドの安定化器測定により、最後に1ラウンドを実施した場合よりも改善が期待できる。
論文 参考訳（メタデータ） (2021-08-04T14:24:14Z) - Fault-tolerant Coding for Quantum Communication [71.206200318454]
ノイズチャネルの多くの用途でメッセージを確実に送信するために、回路をエンコードしてデコードする。
すべての量子チャネル$T$とすべての$eps>0$に対して、以下に示すゲートエラー確率のしきい値$p(epsilon,T)$が存在し、$C-epsilon$より大きいレートはフォールトトレラント的に達成可能である。
我々の結果は、遠方の量子コンピュータが高レベルのノイズの下で通信する必要があるような、大きな距離での通信やオンチップでの通信に関係している。
論文 参考訳（メタデータ） (2020-09-15T15:10:50Z) - Describing quantum metrology with erasure errors using weight
distributions of classical codes [9.391375268580806]
我々は、古典的な$[n,k,d]$二進ブロック符号に対応する構造を持つ量子プローブ状態について検討する。
これらのプローブ状態が古典場の未知の大きさを推定できるという究極の精度の限界を得る。
論文 参考訳（メタデータ） (2020-07-06T16:22:40Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。