論文の概要: Quantum advantage from soft decoders
- arxiv url: http://arxiv.org/abs/2411.12553v1
- Date: Tue, 19 Nov 2024 15:12:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-20 13:36:19.584030
- Title: Quantum advantage from soft decoders
- Title（参考訳）: ソフトデコーダによる量子優位性
- Authors: André Chailloux, Jean-Pierre Tillich,
- Abstract要約: 最適多項式補間法(OPI)問題におけるいくつかのインスタンス化の改善について述べる。
我々の結果は自然で説得力のある復号問題をもたらし、量子的優位性を持っていると信じている。
本稿では,Regevのリダクションの設定にデコーダを利用できるように,シンドロームからコセットサンプリング問題への新たなリダクションを提案する。
- 参考スコア（独自算出の注目度）: 0.7728149002473877
- License:
- Abstract: In the last years, Regev's reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of the decoding problem. Following this line of work, the authors of [JSW+24] have recently come up with a quantum algorithm called Decoded Quantum Interferometry that is able to solve in polynomial time several optimization problems. They study in particular the Optimal Polynomial Interpolation (OPI) problem, which can be seen as a decoding problem on Reed-Solomon codes. In this work, we provide strong improvements for some instantiations of the OPI problem. The most notable improvements are for the $ISIS_{\infty}$ problem (originating from lattice-based cryptography) on Reed-Solomon codes but we also study different constraints for OPI. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. Our proof techniques involve the use of a soft decoder for Reed-Solomon codes, namely the decoding algorithm from Koetter and Vardy [KV03]. In order to be able to use this decoder in the setting of Regev's reduction, we provide a novel generic reduction from a syndrome decoding problem to a coset sampling problem, providing a powerful and simple to use theorem, which generalizes previous work and is of independent interest. We also provide an extensive study of OPI using the Koetter and Vardy algorithm.
- Abstract（参考訳）: ここ数年、Regevの還元はデコード問題の変種に対する量子的優位性を提供する量子アルゴリズムツールとして使われてきた。
この一連の研究の後、[JSW+24]の著者らは最近Decoded Quantum Interferometryと呼ばれる量子アルゴリズムを考案した。
彼らは特に、リード・ソロモン符号の復号問題と見なせる最適多項式補間(OPI)問題を研究している。
本研究は,OPI問題の即時化に強い改善をもたらすものである。
最も注目すべき改善は、リード・ソロモン符号上の$ISIS_{\infty}$問題(格子ベースの暗号から派生したもの)であるが、OPIに対する異なる制約も研究している。
我々の結果は自然で説得力のある復号問題をもたらし、量子的優位性を持っていると信じている。
我々の証明手法は、リード・ソロモン符号のソフトデコーダ、すなわちKoetter と Vardy の復号アルゴリズム [KV03] の使用を含む。
このデコーダをレゲフの減算の設定で利用できるように、我々はシンドローム復号問題からコセットサンプリング問題への新たな一般還元を提供し、より強力で簡単な定理を提供し、これは以前の研究を一般化し、独立した関心を持つものである。
また、Koetter and Vardyアルゴリズムを用いたOPIの広範な研究も行っている。
関連論文リスト
- Decoding Quasi-Cyclic Quantum LDPC Codes [23.22566380210149]
量子低密度パリティチェック(qLDPC)符号は耐故障性を求める上で重要な要素である。
近年のqLDPC符号の進歩は、量子的に良好であり、線形時間デコーダが符号ワード量子ビットの一定数に影響を与える誤りを正すという構成に繋がった。
実際には、2つの繰り返し符号の産物である表面/履歴符号は依然としてqLDPC符号として選択されることが多い。
論文 参考訳（メタデータ） (2024-11-07T06:25:27Z) - Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
LPN問題(Learning Parity with Noise)は、いくつかの古典的な暗号プリミティブの根底にある問題である。
本稿では,線形符号の復号化問題から,難易度がいくつか存在することの低減を試みている。
我々は、復号化の効率を、復号化のパラメータと問題の観点から特徴づける。
論文 参考訳（メタデータ） (2024-08-07T12:54:43Z) - Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms [0.0]
本研究では,トラベリングセールスマン問題に対する様々なエンコーディングについて検討する。
置換符号化は、実現可能性の問題に悩まされないため、良好な結果が得られるという証拠が得られます。
論文 参考訳（メタデータ） (2024-04-08T12:30:07Z) - The Quantum Decoding Problem [0.23310087539224286]
量子復号問題について考察し、そこでは、符号語のノイズバージョンを重畳する。
ノイズレートが十分小さい場合、量子復号化問題は量子時間で解けることを示す。
また、関連する古典復号問題の解けない雑音率に対して、原理的に量子的に解けることを示す。
論文 参考訳（メタデータ） (2023-10-31T17:21:32Z) - Viderman's algorithm for quantum LDPC codes [13.916368399461895]
本稿では,量子LDPC符号に対するバイダーマンのアルゴリズムの一般化について述べる。
これは、定数レート量子LDPC符号に対して最大$Omega(D)$エラーを補正できる最初の消去変換アルゴリズムである。
論文 参考訳（メタデータ） (2023-10-11T20:17:21Z) - Quantum Lego Expansion Pack: Enumerators from Tensor Networks [1.489619600985197]
量子量列挙子を最も一般的な形式で計算するための最初のテンソルネットワーク法を提供する。
非(Pauli)安定化器符号の場合、これはコード距離を計算するのに最適なアルゴリズムである。
これらの列挙子は論理的誤り率を正確に計算するために使用することができ、従って任意の単一キュービットやキューディットのエラーチャネルに対してデコーダを構築することができる。
論文 参考訳（メタデータ） (2023-08-09T18:00:02Z) - Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
Reed-Muller (RM) 符号は、一般的なバイナリインプットメモリレス対称チャネルの容量を達成する。
RM符号は制限されたレートのみを許容する。
効率的なデコーダは、RM符号に対して有限長で利用可能である。
論文 参考訳（メタデータ） (2023-01-16T04:11:14Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。